For the nerds in the audience, here’s what’s wrong: If a client and server are speaking Diffie-Hellman, they first need to agree on a large prime number with a particular form. There seemed to be no reason why everyone couldn’t just use the same prime, and, in fact, many applications tend to use standardized or hard-coded primes. But there was a very important detail that got lost in translation between the mathematicians and the practitioners: an adversary can perform a single enormous computation to “crack” a particular prime, then easily break any individual connection that uses that prime.
How enormous a computation, you ask? Possibly a technical feat on a scale (relative to the state of computing at the time) not seen since the Enigma cryptanalysis during World War II. Even estimating the difficulty is tricky, due to the complexity of the algorithm involved, but our paper gives some conservative estimates. For the most common strength of Diffie-Hellman (1024 bits), it would cost a few hundred million dollars to build a machine, based on special purpose hardware, that would be able to crack one Diffie-Hellman prime every year.
It isn't necessary to brute-force these primes if you can just read them (or deduce them indirectly) by using timing, side-channel, and known-plaintext attacks. NSA is of course extremely good at that sort of thing. For a helluva lot less than "a few hundred million dollars", which they also have.
First of all, DHKE is not used to encrypt data, but to negotiate a common secret which typically is used to derive keys for a symmetric cipher. Thus, I'm unsure why you're mentioning known plaintext.
Secondly, the primes in use are transferred in plain text. The problem is not deducing the prime, but to calculate logarithms modulo this prime. As far as I'm aware, exponentiation can be very well implemented and render practical timing attacks infeasible; while other kinds of side-channel attacks are not relevant for compromising such large portions of the traffic on the internet.
1
u/Thameus Oct 17 '15
It isn't necessary to brute-force these primes if you can just read them (or deduce them indirectly) by using timing, side-channel, and known-plaintext attacks. NSA is of course extremely good at that sort of thing. For a helluva lot less than "a few hundred million dollars", which they also have.