Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Cracking a 512-bit DKIM key for less than $8 in the cloud

dmarcchecker.app

Post reply on HN
Print view View original

411–420 of 433 posts

Re: Cracking a 512-bit DKIM key for less than $8 in the cloud

#411

Post by colmmacc »

tptacek wrote: post #387
colmmacc wrote: post #369

Earlier quoted context omitted.

I think many in cryptography would see cracking a key as a precondition to "actually exploiting it" ... because you've only gotten a cryptographic secret, not "actual data". But I think many others, and many in law enforcement, will see cracking a key as "actually exploiting it". You've exploited the cracking vulnerability to target a particular key, is how they'll see it. Law enforcement also have a natural incentiv…

The US law most at play in criminal prosecution of computer usage is CFAA, and a clear CFAA predicate is intentional access to a protected computer (18 USC 1030(a)(2)). This distinction is what makes vulnerability research on things like Chrome vulnerabilities generally safe (as long as you don't knowingly spirit exploits to people who are actually attacking people), while vulnerability research on other people's web…

By this interpretation it would be perfectly legal to abuse a wifi encryption vulnerability to spy on your neighbors, because that doesn't involve accessing a computer of theirs.

My understanding, and IANAL, is that decrypting things that aren't yours is a bad idea and is covered mainly by electronic communications and wire acts, e.g. U.S. Code § 2511 and others.

Re: Cracking a 512-bit DKIM key for less than $8 in the cloud

#412

Post by tptacek »

colmmacc wrote: post #411
tptacek wrote: post #387

Earlier quoted context omitted.

The US law most at play in criminal prosecution of computer usage is CFAA, and a clear CFAA predicate is intentional access to a protected computer (18 USC 1030(a)(2)). This distinction is what makes vulnerability research on things like Chrome vulnerabilities generally safe (as long as you don't knowingly spirit exploits to people who are actually attacking people), while vulnerability research on other people's web…

By this interpretation it would be perfectly legal to abuse a wifi encryption vulnerability to spy on your neighbors, because that doesn't involve accessing a computer of theirs. My understanding, and IANAL, is that decrypting things that aren't yours is a bad idea and is covered mainly by electronic communications and wire acts, e.g. U.S. Code § 2511 and others.

A wifi encryption vulnerability that required you to interact with a base station or remote computer would implicate CFAA. A wifi encryption vulnerability that allowed for pure passive interception --- a devastating flaw in 802.11/WPA3 --- might not actually violate any federal law directly. There are probably state laws (I believe Michigan has one) that implicate packet sniffing directly (they were problematic in the early oughts for security researchers).

Worth remembering: when CFAA was originally passed, an objection to it was "we already have laws that proscribe hacking computers"; the fraud statutes encompass most of this activity. CFAA's original motivation was literally WarGames: attacks with no financial motivation, just to mess things up. So even without statutory issues, breaking an encryption key and using it to steal stuff (or to gain information and ferry it to others who will use it for crimes) is still illegal.

Your guess is as good as mine about whether ECPA covers wifi sniffing. But: presuming you obtain an encryption key through lawful means, ECPA can't (by any obvious reading) make cracking that key unlawful; it's what you'd do with the key afterwards that would be problematic.

Re: Cracking a 512-bit DKIM key for less than $8 in the cloud

#413

Post by jedwards1211 »

DarkmSparks wrote: post #410
littlestymaar wrote: post #397

Earlier quoted context omitted.

Do you even read?

Did you? you linked https://en.wikipedia.org/wiki/General_number_field_sieve already That gives the worst case complexity right at the top. > 2^16 [1] 65536 > n > exp(((64/9)^(1/3)+1) (log(n)^(1/3)) (log(log(n))^(2/3))) [1] 38178499 > 38178499/65536 [1] 582 2^16 -> 2^32 ~ x 2^9 > n > exp(((64/9)^(1/3)+1) (log(n)^(1/3)) (log(log(n))^(2/3))) [1] 84794674511 > 84794674511/38178499 [1] 2221 2^32-> 2^64 ~ x 2^11 > n > exp…

function ops(n) { return Math.exp (((64/9) * (1/3) + 1) * (Math.log(n) * (1/3)) * (Math.log(Math.log(n)) * (2/3))) }

> ops(2*16)

121106.42245436447

> ops(2*32)

38178499.24944067

> ops(2*32) / ops(2*16)

315.24751929508244

So if ops(2*16) costs $8, then ops(2*32) costs $8 * ops(2*32) / ops(2*16) = $2521.98. Far more than $8^2.

The cost reaches the millions for 64 bits, and ~$165 trillion for 128 bits:

> 8 * ops(2*64) / ops(2*16)

5601332.962726709 (far more than $8^2^2)

> 8 * ops(2*128) / ops(2*16)

165647073370.16437 (far more than $8^2^2^2)

Note that this is increasing faster than the number of bits squared:

> ops(2*32) / 32 * 2

37283.690673281904

> ops(2*64) / 64 * 2

20701824.831895076

> ops(2*128) / 128 * 2

153052707259.34015

As the wiki page says, it's super-polynomial in the number of bits.

If you still disagree with all of this, can you explain what's wrong with this method of calculating the worst-case cost of factoring the number n?

Cost(n) = ops(n) * Cost(2^16) / ops(2^16)

Or what you don't understand about this way of calculating it?

Re: Cracking a 512-bit DKIM key for less than $8 in the cloud

#414

Post by DarkmSparks »

jedwards1211 wrote: post #413
DarkmSparks wrote: post #410

Earlier quoted context omitted.

Did you? you linked https://en.wikipedia.org/wiki/General_number_field_sieve already That gives the worst case complexity right at the top. > 2^16 [1] 65536 > n > exp(((64/9)^(1/3)+1) (log(n)^(1/3)) (log(log(n))^(2/3))) [1] 38178499 > 38178499/65536 [1] 582 2^16 -> 2^32 ~ x 2^9 > n > exp(((64/9)^(1/3)+1) (log(n)^(1/3)) (log(log(n))^(2/3))) [1] 84794674511 > 84794674511/38178499 [1] 2221 2^32-> 2^64 ~ x 2^11 > n > exp…

function ops(n) { return Math.exp (((64/9) * (1/3) + 1) * (Math.log(n) * (1/3)) * (Math.log(Math.log(n)) * (2/3))) } > ops(2*16) 121106.42245436447 > ops(2*32) 38178499.24944067 > ops(2*32) / ops(2*16) 315.24751929508244 So if ops(2*16) costs $8, then ops(2*32) costs $8 * ops(2*32) / ops(2*16) = $2521.98. Far more than $8^2. The cost reaches the millions for 64 bits, and ~$165 trillion for 128 bits: > 8 * ops(2*64) /…

->The cost reaches the millions for 64 bits, and ~$165 trillion for 128 bits:

meanwhile 512 bits costs $8

But you just keep believing 128 bits costs $165 trillion ROFL.

>> ops(2 * 16)

>121106.42245436447

>> ops(2 * 32)

>38178499.24944067

>> ops(2 * 32) / ops(2 * 16)

>315.24751929508244

So if ops(216) costs $8, then ops(232) costs $8 * ops(232) / ops(216) = $2521.98. Far more than $8^2.

And I said $256, because as an "embarrassingly parallel" algorithm you get significant benefits from cached results (quickly discard entire number fields that were previously calculated).

Which, btw, is how they break 512bit DH in less than a minute.

Also still a lot closer than your >$165 trillion

sigh

Re: Cracking a 512-bit DKIM key for less than $8 in the cloud

#415

Post by colmmacc »

tptacek wrote: post #412
colmmacc wrote: post #411

Earlier quoted context omitted.

By this interpretation it would be perfectly legal to abuse a wifi encryption vulnerability to spy on your neighbors, because that doesn't involve accessing a computer of theirs. My understanding, and IANAL, is that decrypting things that aren't yours is a bad idea and is covered mainly by electronic communications and wire acts, e.g. U.S. Code § 2511 and others.

A wifi encryption vulnerability that required you to interact with a base station or remote computer would implicate CFAA. A wifi encryption vulnerability that allowed for pure passive interception --- a devastating flaw in 802.11/WPA3 --- might not actually violate any federal law directly. There are probably state laws (I believe Michigan has one) that implicate packet sniffing directly (they were problematic in th…

My understanding of the ECPA and other acts is that you can't intercept, decode, or receive by other intentional means any information or communications that aren't "generally accessible" without permission. It's pretty broad and doesn't care about the "how".

Private keys are not "generally accessible" and my concern is that the authorities will see cracking the key itself as issue enough, and unlawful. If a security researcher triggers painful breach notifications, which could well happen for a compromised private key, I don't think it's unthinkable at all that an upset target will find a DA who is happy to take this interpretation.

I don't think this specific DKIM case is particularly high-risk, but I still wouldn't do it without permission from the key holder.

Re: Cracking a 512-bit DKIM key for less than $8 in the cloud

#416

Post by DarkmSparks »

bmacho wrote: post #405
DarkmSparks wrote: post #400

Earlier quoted context omitted.

Firstly, the number of prime numbers So moving from 2^16 = 65536 to 2^32 = 4294967296 Increases the size of the total potential search space from 5909 to 193635251, which is ~ 5909 x 32769 secondly, the reason it grows by only n^2, is you only need to search along the curve n = a x b - which is the "sieve" part. if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 Thirdly, your stupidly high c…

> if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 Can you answer a) If 1 apple costs you 8$ then (1)^2 apple costs you: ??? b) If 10 apples cost you 8$ then (10)^2 apples costs you: ??? edit: between the price and the amount, usually there is a ~linear relationship. So if you can buy 2^512 something for 8$, then chances are that for 8 times the price you'll only get ~8 times more amount,…

the ^2's are

https://en.m.wikipedia.org/wiki/Big_O_notation

The tldr is bigO gives you how the cost of apples changes with the number of apples in the worst case.

its a rough simplification, the precise formula is close but not exactly that. the simplification is also actually (2n)^2 but in my defense I was going from memory of work from more than 2 decades ago (testing generated prime factors were good prime factors, overwhelmingly they were not).

using your apples example if the bigO of eating apples is O(n^2), and it takes you 8 minutes to eat 2 apples, it will take you no more than 64 minutes to eat 4 apples.

Re: Cracking a 512-bit DKIM key for less than $8 in the cloud

#417

Post by lazide »

alt227 wrote: post #404
lazide wrote: post #348

Earlier quoted context omitted.

By what metric? In India, it is exceptionally rare for any services (gov’t and commercial) to use email address. They use mobile. One of many examples [ https://web.umang.gov.in/landing/department/aadhaar.html ] That accounts for 1.3+ billion distinct accounts in 2023 right there. [ https://uidai.gov.in/en/about-uidai/unique-identification-au... ] Do you think those folks in Asia and Africa sharing mobile devices hav…

Not really sure what you are saying here, it seems like you are a bit confused. You were talking about phone numbers being used to access online services, and now you are posting links about the Indian governments Personal Identification number which is more akin to a National Insurance number in the UK or social security number in the US > Do you think those folks in Asia and Africa sharing mobile devices have email…

Facebook only requires a mobile, not an email.

Re: Cracking a 512-bit DKIM key for less than $8 in the cloud

#418

Post by DarkmSparks »

jedwards1211 wrote: post #407
DarkmSparks wrote: post #400

Earlier quoted context omitted.

Firstly, the number of prime numbers So moving from 2^16 = 65536 to 2^32 = 4294967296 Increases the size of the total potential search space from 5909 to 193635251, which is ~ 5909 x 32769 secondly, the reason it grows by only n^2, is you only need to search along the curve n = a x b - which is the "sieve" part. if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 Thirdly, your stupidly high c…

Okay I hadn't read about how many calculations it takes to cover the search space, so my equations aren't right about that. However, you will do yourself a big favor if you take the time to understand why this is wrong: > if 2^512 calculations costs you $8 then (2^512)^2 calculations costs you $64 The cost per calculation is some constant C: Cost(n calcs) = n calcs * C Therefore, Cost(n^2 calcs) = n^2 calcs * C In th…

I wouldnt argue with a claim of $2425 tbh.

The $8 will vary, and the actual cost function completely depends on the implimentation, its definitely possible to do worse, very likely possible to do better - there was rumors a few years ago that some Riemann surface based math can do it in O(1), but I know nothing about Riemann surfaces so can't judge their veracity.

Re: Cracking a 512-bit DKIM key for less than $8 in the cloud

#419

Post by littlestymaar »

DarkmSparks wrote: post #410
littlestymaar wrote: post #397

Earlier quoted context omitted.

Do you even read?

Did you? you linked https://en.wikipedia.org/wiki/General_number_field_sieve already That gives the worst case complexity right at the top. > 2^16 [1] 65536 > n > exp(((64/9)^(1/3)+1) (log(n)^(1/3)) (log(log(n))^(2/3))) [1] 38178499 > 38178499/65536 [1] 582 2^16 -> 2^32 ~ x 2^9 > n > exp(((64/9)^(1/3)+1) (log(n)^(1/3)) (log(log(n))^(2/3))) [1] 84794674511 > 84794674511/38178499 [1] 2221 2^32-> 2^64 ~ x 2^11 > n > exp…

You still cannot take the square of a dollar count… What don't you understand.

You're trying to seek refuge in math you barely understand to escape contradiction but it's not even a problem with GNFS, the fundamental problem is that you're trying to do something you mathematically cannot do, which is squaring sums of money. It's equivalent to a division by zero in a demonstration, it just nullifies all the reasoning around it.

And I've given plenty of illustrations why you cannot do that you definitely should read instead of obsessing yourself in proving you're right.

Re: Cracking a 512-bit DKIM key for less than $8 in the cloud

#420

Post by 1oooqooq »

kbolino wrote: post #364
dspillett wrote: post #349

Earlier quoted context omitted.

> but it can be tricky to configure properly on a name server. I wouldn't say it is tricky with a good name server: for instance with bind just split the value into multiple quoted strings and it'll do the rest¹. Though while it is well known, it doesn't seem to be well documented away from many forum posts discussing the matter: after a little searching I can't find reference to the issue in bind documentation or re…

You're only halfway there. Also from RFC 1035: TXT-DATA One or more s. Looking up what a character-string is: .... is a single length octet followed by that number of characters. is treated as binary information, and can be up to 256 characters in length (including the length octet). So the 255-byte limit for each string within the TXT record is a core part of DNS. But so is having more than one such string in the re…

yeah my point is that most dns servers used outside the major markets do not support any of this double key stuff.

if you want TLD not available at your us registrar, you're stuck with low dkim keys. period. doesn't matter what specs says.

dunno if that's just a consequence of the monopoly design of the dns business, or more nefarious reasons, but that's the situation on most TLD not easily registered such as .br

Post reply on HN