Hacker News new | past | comments | ask | show | jobs | submit login

Well, if they could crack 1024-bit primes in under a day, how long would you anticipate 2048-bit would last? That's why I said eye it suspiciously.

I don't think the NSA can do this on demand.

> People should just use 2048 bit keys, or stop using conventional prime field public key algorithms altogether, is what I think.

I believe moving towards ECC (especially djb's work) is probably the right move.




Much much longer. We can reason about how an attacker with very large compute resources can break 1024 bit DH/RSA. Given the feasibility of a 1024 break, we can also reason about optimizations that would serve to make that attack deployable in the real world.

We can't do the former thing at all for 2048 bit DH/RSA, let alone the latter.

Entities attacking 1024 bit keys are doing something we've believed would be inevitable for something like a decade.

When 2048 bit DH/RSA falls, DH and RSA will probably fall with them; they won't fall because compute resources eventually catch up to them, but rather because we discover something about integer factorization or discrete logs that makes prime field cryptography altogether unsafe.


If you look at the chart on the top of page 8 of the technical paper (https://weakdh.org/imperfect-forward-secrecy.pdf), they have some intelligent guesses for core-years to crack a DH-512, 768, and 1024 group, as well as associated memory requirements.

512, which they actually did, is 10.2 core-years for the precomputation plus 10 core-minutes per actual crack. 768 they estimate at 29,300 core-years plus 2 core-days per crack. 1024 is estimated at 45M core-years plus 30 core-days per crack. On top of that while 10M of those core-years are easily parallelizable with specialized hardware (the sieving stages) 35M of them are spent doing linear algebra on a square matrix with 5 billion rows. The authors of the paper note that there's been little work on designing custom systems suitable for this task and only give a rough estimate of the resulting cost (somewhere in the order of hundreds of millions of dollars).

As you can see the challenges presented (hence cost) doesn't scale linearly with problem difficulty. The linear algebra step looks completely implausible at 2048.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: