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

So the NSA can break 1024-bit DHE? Is ECDHE good enough to hold us for now, or do we need to find an alternative to DHE ASAP?



Two parts to your question: 1. Yes, the NSA can likely break 1024-bit DHE at scale - as well as 1024-bit RSA or anything smaller. (Probably also the RC4 stream cipher, if you didn't listen and are still using that.)

2. ECDHE is totally different to traditional finite-field DHE. ECDHE over P-256 (or better curves) is not vulnerable to this attack.


Depends on what we mean by "at scale", right? That's why the shared parameter aspect of this attack is so meaningful: they probably can't solve 1024 bit DH problems "on demand".


If they can solve the 1024-bit DH problem "on demand" we should probably be eying 2048-bit DH with some suspicion.

(I'm agreeing with your point.)


Attacks don't really scale like that. If 2048 bit prime field discrete logs fail, all of prime field discrete logs (and with it probably RSA) will probably be done for.

There is, as I understand it, a huge performance penalty for using keys larger than 2048 bits. People should just use 2048 bit keys, or stop using conventional prime field public key algorithms altogether, is what I think.


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.


What does ECDHE have to do with DHE? DHE is prime field Diffie Hellman. ECDHE is Elliptic Curve Diffie Hellman. There is no 1024-bit ECDHE.


Or if there is, it's probably snakeoil.

http://bindshell.nl/pub/zines/OandE/exp03.txt

(Ctrl+F: Vpn24.org)




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: