The NSA and Weak-DH
The authors of the weak Diffie-Hellman work are almost certainly correct that the technique they describe is used by the NSA, in bulk, to perform a massive amount of decryption on Internet traffic. This is perhaps the biggest technical revelation about NSA capabilities in the past few years, as it reveals a potential huge capability possessed by the NSA. In particular, the IPsec Virtual Private Network (VPN) protocol used by businesses, governments, and individuals around the world is particularly vulnerable to this weakness.
The point of Diffie-Hellman public key exchange (DHE) is for two parties, commonly referred to as “Alice” and “Bob”, to agree on a secret value in a way that someone listening in can’t determine this value. This process begins with two public prime numbers, p and g. Then Alice creates a random number a that she keeps secret and Bob creates b. Through some math, they agree on a number, which represents the shared encryption key that Alice and Bob can use to encrypt their traffic. This is why this protocol is termed a “key exchange” protocol.
Adrian et al, the authors of the CCS paper, observed a subtle detail. It is computationally very hard to compute the agreed number if someone doesn’t know either a or b (which is why this is a “public key exchange” protocol, it assumes that the adversary can see all the communication between Alice and Bob). But this work actually consists of two parts, a huge amount of work that applies to any a and b using the same p and g and a very small amount of work for the next a and b using the same p and g. They further observed that most servers using this for IPsec, a major Virtual Private Network protocol that encrypts a large amount of business traffic, commonly use the same p and g, and most of these systems are using 1024b Diffie-Hellman.
So with an NSA-style budget of a few hundred million dollars, one could build a supercomputer that can first perform a huge amount of work, running for months, in order to break a particular 1024b p and g and then, using the same supercomputer, quickly break any key exchange using that particular p and g. This wouldn’t work for longer keys (such as 3072b Diffie-Hellman), elliptic curve Diffie-Hellman, or RSA encryption.
This paper almost certainly upset some in the NSA. Either the NSA knew this trick, in which case the researchers revealed a very powerful (and possibly unique) NSA capability. Or the NSA did not know this trick, in which case the NSA missed a golden opportunity to decrypt a huge amount of Internet traffic. Based on how the NSA systems decrypt traffic, I’m almost certain its the former.
Although somewhat useful against other protocols, this attack primarily works against IPsec, because it only uses Diffie-Hellman for public key and most implementations use one of only a few values of p and g. It does affect a fair amount of ssh (another protocol system administrators use to remotely access machines) and some HTTPS traffic. This attack does not work against PGP, Mojahadeen Secrets, or iMessage.
If indeed the NSA is using the weak-DH attack, they gained a huge amount of foreign intelligence data with it but almost no intelligence about terrorism. Businesses and governments use IPsec to protect their traffic back to their home institutions, jihadis likely don’t. This is the VPN information that the NSA could not get any other way.
I’ve always considered IPsec to be a weak compromise. Good grief. Sometimes I surprise myself.
IVPN – use OpenVPN not IPsec – with 4096 bit RSA keys and perfect forward secrecy.