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

311–320 of 433 posts

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

#311

Post by inopinatus »

cbozeman wrote: post #255
withinboredom wrote: post #237

Earlier quoted context omitted.

Counter-example example: I've been an expert witness in court to prove an email was a forgery; using DKIM.

That would be a counter-counterexample, wouldn't it?

The stacking of either term is unnecessary, because all counter-examples are also examples, thus:

* an example supporting the counter-example is simply another counter-example, and

* an example contradicting the counter-example is, by definition, also another counter-example.

Corollary: all examples that can be opposed or contradicted by counter-examples are themselves also counter-examples.

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

#312

Post by btdmaster »

DarkmSparks wrote: post #250
littlestymaar wrote: post #225

Earlier quoted context omitted.

Oh, I wasn't aware of the end of the challenge. But 1024 was definitely not broken by then, at least not by brute force.

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…

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 give an approximation of math.exp(math.cbrt(512 * 64/9))*$8 = $40 million for 1024 bits.

[0] https://en.wikipedia.org/wiki/General_number_field_sieve

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

#313

Post by SahAssar »

jaza wrote: post #299
gauravphoenix wrote: post #218

I don't understand why didn't Yahoo fail due to SPF check failure.

Considering that Yahoo doesn't really exist anymore, and that Yahoo Mail is just a relic of Yahoo's heyday that is somehow still hanging around, I assume nobody has bothered to actually maintain its handling of security protocols for about a decade.

Yahoo mail still has plenty of users and yahoo still have many employees. It'd be borderline criminal to not have somebody at yahoo oversee their email security.

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

#314

Post by jillyboel »

qingcharles wrote: post #260
jillyboel wrote: post #247

Earlier quoted context omitted.

Which is why you say "No". Then when they try to prove that you did in fact send it, this comes up.

Well, if you did send it then you just perjured yourself, so you better hope you don't get caught :)

You'd be lying to the court either way if you did send it and meant to conceal it.

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

#315

Post by SahAssar »

DarkmSparks wrote: post #83

"as RSA keys shorter than 1,024 bits are considered insecure, and their use in DKIM has been deprecated since the introduction of RFC 8301 in 2018." LOL. One of my favourite internet flame wars was circa 2007 (in and around discussing the incoming financial crises) and we got talking about encryption and how none of it actually "works". Particularly vile troll, and iirc also owner of the site bet me $50,000 I couldn'…

> not sure I would trust 8192 bit RSA in 2024

Do you have any proof/quote for that? Some pretty knowledgeable and well-known people in this thread 2048 bit RSA is quite safe with current capabilities[1]

1: https://news.ycombinator.com/item?id=42635066

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

#316

Post by SahAssar »

DarkmSparks wrote: post #100
littlestymaar wrote: post #31

Earlier quoted context omitted.

1024 is still many orders of magnitude hard to crack than 512. For the record, the last RSA number having been broken was RSA-250 (829 bits) and it took 2700 core-years to crack back in 2020[1]. In comparison, RSA-155 (512 bits) was factorized as early as 1999! You aren't in danger. [1]: https://sympa.inria.fr/sympa/arc/cado-nfs/2020-02/msg00001.h...

There are several open source GNFS tools that can do 1024 very efficiently on GPUs, and even cheap consumer GPUs have 10s of thousands of cores now, even by your measure "2700 core-years" is only around a month or so on a single consumer grade GPU. Not "free", but any malicious actor has access to a lot more than a single GPU. The UK government also has several huge arm based solutions dedicated to cracking internet…

> The UK government also has several huge arm based solutions dedicated to cracking internet encryption, zero chance that isn't breaking mostly everything, for sure the Chinese and Russians have similar.

So you seriously think that almost all current RSA is being decrypted in real time by at least UK, China and Russia (and I would assume US)? Do you have any source or reference for this at all?

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

#317

Post by DarkmSparks »

btdmaster wrote: post #312
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…

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

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

#318

Post by tomesco »

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…

There exist certain classes of prime numbers that should not be used for some cryptographic operations because algorithms exist that reduce the computation required for factoring attacks. This more often applies to cases where smaller primes are applied. Sources for this king of knowledge are mathematics or cryptography textbooks.

For other cryptographic operations, almost any sufficiently large prime can be used. Even a 50% reduction on a computation that will take trillions of years, has no practical impact.

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

#319

Post by coppsilgold »

tptacek wrote: post #96
bluGill wrote: post #57

Earlier quoted context omitted.

RSA 2048 isn't broken, but experts consider it a matter of time. How long I don't know, but since the attacks are known (prime numbers) someone (read not me) can make an estimate with error bars that are concerning enough to consider it as good as broken.

What expert considers it a matter of time before 2048 is broken? 2048 is 112-bit-equivalent security.

RSA2048 is 112-bit-equivalent symmetric security under currently known methods. Number theory advances may change that. It is hard to imagine any significant advances in the breaking of symmetric cryptography (mathematically-unstructured permutations).

Cryptographically-relevant quantum computers (CRQC's) will also break smaller RSA keys long before (years?) the bigger ones. CRQC's can theoretically halve symmetric cryptography keys for brute force complexity (256-bit key becomes 128-bit for a CRQC cracker).

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

#320

Post by croemer »

Uriopass wrote: post #195
croemer wrote: post #186

Slight change of title. The leading "How" was dropped. Original: "How We Cracked a 512-Bit DKIM Key for Less Than $8 in the Cloud"

Dropping the How is part of Hackernews guidelines

Couldn't find it in the guidelines. Can you quote the relevant part?
Post reply on HN