Why I believe the NSA broke DH…

The “Weak Diffie-Hellman” paper is almost certainly correct in the implication that this is how the NSA is breaking a large amount of cryptography. Simply because the NSA’s architecture for IPsec, a popular VPN protocol, only makes sense if they are using large-scale cryptanalysis rather than just Applied Kleptography.

To decrypt IPsec, a large number of wiretaps monitor for IKE (Internet Key Exchange) handshakes, the protocol that sets up a new IPsec encrypted connection. The handshakes are forwarded to a decryption oracle, a black box system that performs the magic. While this happens, the wiretaps also record all traffic in the associated IPsec connections.

After a period of time, this oracle either returns the private keys or says “i give up”. If the oracle provides the keys, the wiretap decrypts all the stored traffic and continues to decrypt the connection going forward.

Applied Kleptography, simply stealing private keys, is undoubtedly a cornerstone of NSA cryptanalysis. Likewise there is a large amount of product sabotage. But absent a cryptanalysis breakthrough such as the one described by Adrian et al, the NSA’s architecture is overkill: it would be far easier to just forward the decryptable connections back to the central system if the oracle can decrypt the communication.

This would also better match the security implications: just the fact that the NSA can decrypt a particular flow is a critical secret. Forwarding a small number of potentially-crackable flows to a central point better matches what is needed to maintain such secrecy.

Thus by performing the decryption in bulk at the wiretaps, complete with hardware acceleration to keep up with the number of encrypted streams, this architecture directly implies that the NSA can break a massive amount of IPsec traffic, a degree of success which implies a cryptanalysis breakthrough.

Similarly, the focus on IPsec further suggests that Adrian et al’s analysis is correct, and their technique is being exploited by the NSA. IPsec is the only major encryption protocol that uses Diffie-Hellman in a commonly vulnerable form (1024b with prime number reuse) on a near-ubiquitous basis. TLS (the protocol that secures web traffic) can use DH for key exchanges, but this is hardly ever the default, and new configurations which do use DH by default generally use larger values or elliptic curve Diffie-Hellman, neither of which are vulnerable to this attack.

The other remarkable thing is that, for now, this is a near-NOBUS (NOBody But Us) capability of the NSA: actually building a dedicated supercomputer to do this is a massive task (today), and only a couple of adversaries might even try. This makes the capability to target IPsec in this manner nearly unique among the NSA revelations, most of the rest of their techniques are amenable to hobbiest implementation or make good homework assignments.

Unfortunately Moore’s law of processing per dollar shows no sign of slowing. What takes a $100M investment today takes only a $10M investment tomorrow and a $1M investment the day after. So what is NOBUS today is not NOBUS tomorrow, but equipment purchased today is still used tomorrow.

It is critical to move away from 1024b Diffie-Hellman, because devices fielded today will be in use for a decade, a decade which can see our adversaries use these techniques against us.