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

391–400 of 433 posts

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

#391

Post by littlestymaar »

DarkmSparks wrote: post #390
littlestymaar wrote: post #385

Earlier quoted context omitted.

I'll keep trying to explain it to you: you cannot take the square of a price. If my Yuan exchange rate example didn't convince you, let's have a few thoughts experiments: - let say you can do can do some amount of work for less than $1 (maybe even factoring a 512 bits number) let's call that amount of work X, and you do it for say $0.9. Do you think you can do X² work for price^2, which is $0.81 ? Yes, much more work…

every time you double the number of bits, you increase the search space by the square of what came before 2^16 = 65536 2^32 = 4294967296 4294967296/65536 = 65536 so if a search space of 65536 costs you $8, then a search space of 4294967296 = 65536 x 65536 = 8 x 8 = 8^2 = $64 2^64 = 1.844674e+19 1.844674e+19/4294967296 = 4294967296 so a search space of 1.844674e+19 = 4294967296 x 4294967296 = 65536 x 65536 x 65536 x 6…

> so if a search space of 65536 costs you $8, then a search space of 4294967296 = 65536 x 65536 = 8 x 8 = 8^2 = 64

So close, yet so far: the correct answer here is “65536 x 8 = $525k”, not “8x8 = $64”. If a $8 worth of hard drive can store 65536, then to store 4294967296 you need 65536 of such drives, not 8…

Man this is really embarrassing.

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

#392

Post by DarkmSparks »

littlestymaar wrote: post #391
DarkmSparks wrote: post #390

Earlier quoted context omitted.

every time you double the number of bits, you increase the search space by the square of what came before 2^16 = 65536 2^32 = 4294967296 4294967296/65536 = 65536 so if a search space of 65536 costs you $8, then a search space of 4294967296 = 65536 x 65536 = 8 x 8 = 8^2 = $64 2^64 = 1.844674e+19 1.844674e+19/4294967296 = 4294967296 so a search space of 1.844674e+19 = 4294967296 x 4294967296 = 65536 x 65536 x 65536 x 6…

> so if a search space of 65536 costs you $8, then a search space of 4294967296 = 65536 x 65536 = 8 x 8 = 8^2 = 64 So close, yet so far: the correct answer here is “65536 x 8 = $525k”, not “8x8 = $64”. If a $8 worth of hard drive can store 65536, then to store 4294967296 you need 65536 of such drives, not 8… Man this is really embarrassing.

thats linear search

in gnfs the search space is number fields, so you increase the number of the number fields by the square of what came before.

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

#393

Post by lelandfe »

myself248 wrote: post #366
lelandfe wrote: post #285

Earlier quoted context omitted.

But also Apple, and Uber, etc. It was surprising.

(My joke was that McMaster's website is one of the fastest in the world, and Home Depot's is one of the slowest.)

I'm well aware! :) McMaster-Carr's perf story is legendary, and is frequently cited as inspiration by other companies. I've actually done deep dives on both (Home Depot has other good qualities).

...Yet companies you'd think would be similarly obsessed with FE perf are, at least in the hiring stage, totally nonplussed by that background. C'est la vie.

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

#394

Post by rstuart4133 »

tptacek wrote: post #384
rstuart4133 wrote: post #383

Earlier quoted context omitted.

Yes, it's a pretty good way of proving the server sent the email. That's all it proves. If the email came from gmail.com, it's up to Google to prove the person in the From: address composed the email. The signature can't prove that. Nonetheless almost everyone will accept that is what happened. If Gmail received the email, it's likely they simply drop email with no or bad DKIM signatures. So if it's in your gmail inb…

I really don't follow what you're trying to say here. The point is that the durable verifiable signature has no value to users, but lots of value to attackers; in other words: it only has value to attackers. People are confused because in a formal analysis, journalists getting stories from leaked mail spools are attackers; they are a thing secure messengers are designed to thwart.

> The point is that the durable verifiable signature has no value to users,

Apparently I'm the exception to that rule, because I have a DKIM extension installed on Thunderbird. I use it to do what you say isn't useful - as another way to check phishing messages long after they have been sent.

Until DKIM is universally enforced checking it after the fact will be useful. When DKIM is universally enforced rotating the keys won't matter to either the user or attacher, because both can be sure everything in the inbox (stolen or otherwise) was DKIM signed.

> I really don't follow what you're trying to say here.

It's simple. As things stand now much of the time you don't need a verifiable DKIM signature to know if the message had a valid DKIM signature when it was sent. Therefore it doesn't matter much to the user or attacker if keys were rotated - your "privacy violation" is still a thing whether the keys are rotated or not.

Unfortunately the "much" qualifier must be in there, and compounding that is the stuff that does skip through without being signed are almost always attacks on me - phishing or otherwise. Such messages are rarely sent from a bulk provider that insists on signing because it gets shut down promptly. The sender would probably prefer they were signed so the rejects weren't so frequent, but there are operating on low probability of people taking their message seriously so the even lower probability imposed by invalid DKIM signatures not a disaster.

Unfortunately for your argument legit email is now almost universally signed because the sender is relying on it getting through. If someone steals an inbox and an email that doesn't looked like spam was DKIM signed, then you can pretty safely assume it was validly signed when sent. Being able to validate the DKIM signature after the fact doesn't add much confidence.

It's not rocket science.

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

#395

Post by jonahx »

rstuart4133 wrote: post #394
tptacek wrote: post #384

Earlier quoted context omitted.

I really don't follow what you're trying to say here. The point is that the durable verifiable signature has no value to users, but lots of value to attackers; in other words: it only has value to attackers. People are confused because in a formal analysis, journalists getting stories from leaked mail spools are attackers; they are a thing secure messengers are designed to thwart.

> The point is that the durable verifiable signature has no value to users, Apparently I'm the exception to that rule, because I have a DKIM extension installed on Thunderbird. I use it to do what you say isn't useful - as another way to check phishing messages long after they have been sent. Until DKIM is universally enforced checking it after the fact will be useful. When DKIM is universally enforced rotating the k…

Correct me if I'm missing something, but isn't tptacek's point that if the DKIM's keys are public, I can now just make up any email I want with a "correct signature" and claim it was sent from X and I found it in Y's inbox (for any X, Y). And therefore even if you really found it there you can't prove it. At that point you'd just be trusting the reputation of the accuser (perhaps a respected journalist, perhaps a shady criminal).

I'm not clear how the universal DKIM argument comes into play. Even if we were sure Google only accepts valid DKIM, you still have to trust that the accuser did in fact find it in the alleged Google inbox.

Whereas with the non-rotated key, the accuser has cryptographic proof their alleged email is genuine, because they couldn't have created it without the key.

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

#396

Post by jedwards1211 »

DarkmSparks wrote: post #392
littlestymaar wrote: post #391

Earlier quoted context omitted.

> so if a search space of 65536 costs you $8, then a search space of 4294967296 = 65536 x 65536 = 8 x 8 = 8^2 = 64 So close, yet so far: the correct answer here is “65536 x 8 = $525k”, not “8x8 = $64”. If a $8 worth of hard drive can store 65536, then to store 4294967296 you need 65536 of such drives, not 8… Man this is really embarrassing.

thats linear search in gnfs the search space is number fields, so you increase the number of the number fields by the square of what came before.

Right, so if it costs $8 to search the space for a 16-bit key, a proper equation for the cost of cracking an n-bit key is

Cost(n) = search_space(n) * $8 / search_space(16)

And search_space(x) = 2^x so

Cost(n) = 2^n * $2^3 / 2^16 = $2^(n - 13)

Cost(32) = $2^(32 - 13) = $524288 Cost(64) = $2^(64 - 13) = $2251799813685248

So it quickly becomes astronomically expensive.

If you double the number of bits n you get

Cost(2n) = $2^(2n - 13)

You were assuming that Cost(32) = Cost(16)^2, in other words Cost(2n) = Cost(n)^2. But this equality doesn't hold:

Cost(n)^2 = $2^(n - 13)^2 = $2^(2n - 26)

This is significantly smaller than Cost(2n) = $2^(2n - 13) as stated above.

An equation with different units on each side like "512 bit = $8" doesn't work mathematically and will lead to contradictory conclusions.

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

#397

Post by littlestymaar »

DarkmSparks wrote: post #392
littlestymaar wrote: post #391

Earlier quoted context omitted.

> so if a search space of 65536 costs you $8, then a search space of 4294967296 = 65536 x 65536 = 8 x 8 = 8^2 = 64 So close, yet so far: the correct answer here is “65536 x 8 = $525k”, not “8x8 = $64”. If a $8 worth of hard drive can store 65536, then to store 4294967296 you need 65536 of such drives, not 8… Man this is really embarrassing.

thats linear search in gnfs the search space is number fields, so you increase the number of the number fields by the square of what came before.

Do you even read?

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

#398

Post by brohee »

throw0101c wrote: post #373
brohee wrote: post #362

Earlier quoted context omitted.

THE CABForum just updated its guidelines (in December) and elliptic curve wise only NIST P-256, NIST P-384 and NIST P-521 are accepted. (See https://cabforum.org/working-groups/server/baseline- requirements/requirements/#615-key-sizes) So on the general web it seems remote at best.

> THE CABForum just updated its guidelines (in December) and elliptic curve wise only NIST P-256, NIST P-384 and NIST P-521 are accepted. NIST P-curve certs were acceptable per the Base Requirements all the way back in 2012 * https://cabforum.org/uploads/Baseline_Requirements_V1_1.pdf See "Appendix A - Cryptographic Algorithm and Key Requirements (Normative)", (3) Subscriber Certificates.

I'm well aware I should have added a "still" in the sentence somewhere. All efforts to have Ed25519 on the general web seem to run out of steam, we can find https://www.ietf.org/archive/id/draft-moskowitz-eddsa-pki-06... IETF side, https://lists.cabforum.org/pipermail/servercert-wg/2024-June... is the last discussion CABforum side.

Ed25519 certs do work with TLS (OpenSSL support at least), but without browser adoption it's machine to machine with private CA only .

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

#399

Post by kbolino »

bluGill wrote: post #363
tptacek wrote: post #252

Earlier quoted context omitted.

No, we are not in fact 5 years from breaking RSA-2048.

I have no idea what NIST means when they give 5 years for 2048 bit keys, but in generally I trust them more than some random poster on the internet.

My inclination would be that it has less to do with the keys getting broken in that timeframe and more to do with moving to larger key sizes as soon as possible. As pointed out by others, RSA depends on the asymmetric difficulty of multiplication vs factorization of integers, but the degree of that asymmetry has no hard bounds. Advances in mathematics could reduce it, and NSA may already know of or at least suspect the existence of techniques which are not public. Larger key sizes mitigate against these developments, and pushing the software and hardware stacks to their limits sooner rather than later allows both the vendors and standards bodies to adapt before cryptographic breaks actually occur.

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

#400

Post by DarkmSparks »

jedwards1211 wrote: post #396
DarkmSparks wrote: post #392

Earlier quoted context omitted.

thats linear search in gnfs the search space is number fields, so you increase the number of the number fields by the square of what came before.

Right, so if it costs $8 to search the space for a 16-bit key, a proper equation for the cost of cracking an n-bit key is Cost(n) = search_space(n) * $8 / search_space(16) And search_space(x) = 2^x so Cost(n) = 2^n * $2^3 / 2^16 = $2^(n - 13) Cost(32) = $2^(32 - 13) = $524288 Cost(64) = $2^(64 - 13) = $2251799813685248 So it quickly becomes astronomically expensive. If you double the number of bits n you get Cost(2n)…

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 costs are because you seem to think you need to check if 4817 x 5693 is a prime fractorisation of 26768069 when in fact you already know the prime factorisation by that point.

Post reply on HN