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

351–360 of 433 posts

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

#351

Post by DarkmSparks »

littlestymaar wrote: post #330
DarkmSparks wrote: post #250

Earlier quoted context omitted.

none of it is "brute force", GNFS is a process that rapidly excludes numbers from the search space that cannot be the answer, in principle similar to the way they broke enigma. numberphile has a great video on that one https://www.youtube.com/watch?v=V4V2bpZlqx8 Also, taking the OP as a "worse case", afaik: 512bit = $8 so 1024 = 8^2 = $64 2048 = 8^2^2 = $4,096 4096 = 8^2^2 = $16,777,216 noting $8 for 512 seems very e…

Come on! Not only your math is ridiculous (you can't just square amounts of money, just consider how it would work if you changed currency: $8 is 1260¥, squares it makes it 1587000¥ which is $10k != $64) but believing that RSA-2048 is factorizable in $4k is hilarious. > none of it is "brute force" It's not exhaustive search like it would be for symmetric encryption, but it's still somewhat brute-force (especially sin…

I personally factored 512 bit numbers in 2007 for a lot less than $8, so tbh I'm going to say your overestimation of your knowledge of cryptology is far more hilarious than my paranoia about the potential truth of claims made by people claiming to be experts in cryoptology.

Your claim that factoring a 256bit number would cost fractions of a cent rather than my claim of roughly $3 is also very easily verifiable.

Further I'll note you sound exactly like the kind of person insisting diffie hillman was a good key exchange mechanism prior to Snowdens disclosures. good luck with that.

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

#352

Post by password4321 »

matja wrote: post #219
matthewdgreen wrote: post #39

Earlier quoted context omitted.

For a number of years it was (non-officially) thought to be a feature to use weak DKIM keys. Some folks argued that short keys allowed you to preserve deniability, since DKIM signatures would only be short-lived and nobody would be able to use DKIM signatures to prove that any email was authentic. (I’m not saying that this is why most companies used short keys, just that there was a general view that short keys were…

I don't think this rationale is correct. DKIM doesn't authenticate a user, since the user doesn't the private key - DKIM authenticates that the MTA knows the private key on behalf of the domain owner, which isn't necessarily the users using that domain to send email. What's more dangerous is that a jury wouldn't know the difference.

For 20 years Fastmail allowed any customer to spoof From: another

https://news.ycombinator.com/item?id=42536750#42539217

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

#353

Post by GTP »

tptacek wrote: post #303
GTP wrote: post #301

Earlier quoted context omitted.

Sorry, I'm missing what you're trying to say here, maybe that a politician would be more careful about which message system he's using? I don't think that's necessarily the case. Anyway, to further add to my point, depending on the context you don't even need to claim that someone stole your password. In the company where I am now , it is custom that, if someone finds out someone else didn't lock their computer, that…

What I'm saying is that the "crooked politician" use case you're talking about for DKIM is a way in which you're pleased that a messaging system is insecure , because that insecurity works in your favor (because you're not the user; you just want to violate that user's privacy). But no rational user would want that property for themself; they can only lose from it.

Thank you, I get it now. The reason why I focused on that specific example, is because it is used in the blog post as proof that DKIM is being actively used to prove that someone actually sent an email.

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

#354

Post by cryptizard »

DarkmSparks wrote: post #317
btdmaster wrote: post #312

Earlier quoted context omitted.

That's not correct. Consider, for example, a processor that can handle 2^31 computations per second. 2^32 operations can be computed in 2 time units, whereas 2^64 operations will take 2^33 time units. search_space(n: number_of_bits) = 2^n * k so search_space(1024)/search_space(512)=2^512, not 2^2. Asymptotics in GNFS are better[0], but only on the order of e^(cbrt(512 * 64/9)) times more work, not 2^2. This would giv…

Pretty sure the search cost of GNFS is (bits)^2, the search cost of brute force is 2^(bits), if it was 2^(bits) GNFS would be no better than brute force. ->but only on the order of e^(cbrt(512 * 64/9)) e^(log(n)) = n

[dead]

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

#355

Post by bmacho »

littlestymaar wrote: post #330
DarkmSparks wrote: post #250

Earlier quoted context omitted.

none of it is "brute force", GNFS is a process that rapidly excludes numbers from the search space that cannot be the answer, in principle similar to the way they broke enigma. numberphile has a great video on that one https://www.youtube.com/watch?v=V4V2bpZlqx8 Also, taking the OP as a "worse case", afaik: 512bit = $8 so 1024 = 8^2 = $64 2048 = 8^2^2 = $4,096 4096 = 8^2^2 = $16,777,216 noting $8 for 512 seems very e…

Come on! Not only your math is ridiculous (you can't just square amounts of money, just consider how it would work if you changed currency: $8 is 1260¥, squares it makes it 1587000¥ which is $10k != $64) but believing that RSA-2048 is factorizable in $4k is hilarious. > none of it is "brute force" It's not exhaustive search like it would be for symmetric encryption, but it's still somewhat brute-force (especially sin…

> (you can't just square amounts of money, just consider how it would work if you changed currency: $8 is 1260¥, squares it makes it 1587000¥ which is $10k != $64)

What can you square then? For example, can you square lengths? E.g. 1km is 1000m, what is its square?

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

#356

Post by linsomniac »

Ar-Curunir wrote: post #144
linsomniac wrote: post #40

Earlier quoted context omitted.

I forget where but someone proposed regularly rotating your DKIM key and publishing old keys for deniability. So you can still use strong keys and provide a level of deniability.

That was Matt Green, the person you replied to =)

There is a better than even chance that you are correct. :-)

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

#357

Post by speerer »

singpolyma3 wrote: post #322
jonas21 wrote: post #286

Earlier quoted context omitted.

Nah, it supports the counter-example, so it's a counter-example example.

I'd say it refutes the counter-example. The court doesn't care about DKIM, they care about witness testimony. DKIM might have convinced the witness sometimes though.

Courts typically do not care as much about what an expert witness thinks, as rather why they think it - and whether their reasons hold up enough that the conclusions they support should be accepted.

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

#358

Post by cryptizard »

supernova87a wrote: post #310

This is a little bit of a layman's question but maybe someone is interested: When people go searching for prime numbers / bitcoin with massive compute, I assume that there are huge libraries of "shortcuts" to reduce the searching space, like prime numbers only appear with certain patterns, or there are large "holes" in the number space that do not need to be searched, etc. (see videos e.g. about how prime numbers mak…

That's not really how it works. There aren't any noticeable patterns in prime numbers (besides trivial ones like they are all odd numbers) and they remain dense (no big gaps) even for very large numbers like what are used in RSA. The best algorithm for generating prime numbers is to just pick a really big random odd number and then test if it is prime, repeat until you find one.

Now, factoring large numbers is a separate thing. You don't brute force all the possible factors, that would be a really bad approach. Modern algorithms are called "sieves," this is a gross oversimplification but essentially they keep picking random numbers and computing relations between them until they come up with enough that have a certain property that you can combine them together to find one of the factors. It doesn't have anything to do with shortcuts or patterns or tricks, it is just a fundamental number theory algorithm.

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

#359

Post by littlestymaar »

bmacho wrote: post #355
littlestymaar wrote: post #330

Earlier quoted context omitted.

Come on! Not only your math is ridiculous (you can't just square amounts of money, just consider how it would work if you changed currency: $8 is 1260¥, squares it makes it 1587000¥ which is $10k != $64) but believing that RSA-2048 is factorizable in $4k is hilarious. > none of it is "brute force" It's not exhaustive search like it would be for symmetric encryption, but it's still somewhat brute-force (especially sin…

> (you can't just square amounts of money, just consider how it would work if you changed currency: $8 is 1260¥, squares it makes it 1587000¥ which is $10k != $64) What can you square then? For example, can you square lengths? E.g. 1km is 1000m, what is its square?

1km² aka 1,000,000m², note how the resulting units aren't km and m but square kilometers and square meters.

> What can you square then?

In that case it's the number of operations (which is unitless) that must be squared and then multiplied by the cost of each operation. For instance (figures are completely made up for illustration purpose) if one individual operation costs 0.1 cent, and you have 8000 ops for the factorization, it costs $8, and the operation number squared means you have 64,000,000 operations, and the total cost is $64k. In practice we're talking about trillions of very cheap operations but when you square that number you get an insanely big number which even multiplied by a small individual cost ends up costing trillions of dollars, putting it out of reach of factorization from anyone.

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

#360

Post by cryptizard »

bmacho wrote: post #355
littlestymaar wrote: post #330

Earlier quoted context omitted.

Come on! Not only your math is ridiculous (you can't just square amounts of money, just consider how it would work if you changed currency: $8 is 1260¥, squares it makes it 1587000¥ which is $10k != $64) but believing that RSA-2048 is factorizable in $4k is hilarious. > none of it is "brute force" It's not exhaustive search like it would be for symmetric encryption, but it's still somewhat brute-force (especially sin…

> (you can't just square amounts of money, just consider how it would work if you changed currency: $8 is 1260¥, squares it makes it 1587000¥ which is $10k != $64) What can you square then? For example, can you square lengths? E.g. 1km is 1000m, what is its square?

That is because "square length" is its own unit, which we call area. Square money is not meaningful as a unit, that is the problem. You can square anything you want but it turns it into a different unit, which the original commenter did not do (they presumed squaring dollars still gives you dollars back).
Post reply on HN