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.

The other users of VPNs, those who tunnel their web surfing for "privacy" reasons, are already trackable and tracked when their traffic leaves the VPN and reenters the Internet. The NSA can’t mind those who use VPNs to web surf, most such users are still vulnerable to information captured from requests generated by the World Wide Web of Spies.

This may be the only NSA capability suggested to date that is mostly-NOBUS (Nobody But Us). Today, building such a supercomputer truly is a $100M program (and add another 0 for classified markups and trusted fabs), limiting the ability of others to perform the same attack. Unfortunately Moore’s law on price/performance remains. What takes a $100M supercomputer today takes a $10M supercomputer tomorrow and a $1M supercomputer the day after that. It may be NOBUS today but will not be NOBUS tomorrow.

This interacts badly with the reality of upgrades. Much of the vulnerable VPNs involve VPN hardware, not software. Hardware fielded today might be in use a decade from now, so if the NSA did know this trick, and continued to let US businesses and individuals field such equipment without warning, these users are now at risk for a decade to come.

The NSA’s Information Assurance mission appears to only extend to classified data, so I completely trust Suite B (which requires Diffie-Hellman to use 3072b keys). The NSA would never risk something like Weak-DH knowingly happening to Top Secret communication. But between Weak-DH and Dual_EC, sabotage which directly impacts unclassified communication, any advice for unclassified systems needs to be taken with a huge grain of salt.

additional thought added:

If the NSA indeed used Weak-DH, i think this is one of the classic examples of the "exploit or secure" debate that occur within the NSA in these situations. Since I defend and use unclassified systems, I would always want them to vote "secure". But if I was in the NSA's position, I'd probably vote "exploit" as well: the foreign intelligence value from bulk breaking VPNs is immense.