There have long been rumors, leaks, and statements about the NSA “breaking” crypto that is widely believed to be unbreakable, and over the years, there’s been mounting evidence that in many cases, they can do just that. Now, Alex Halderman and Nadia Heninger, along with a dozen eminent cryptographers have presented a paper at the ACM Conference on Computer and Communications Security (a paper that won the ACM’s prize for best paper at the conference) that advances a plausible theory as to what’s going on. In some ways, it’s very simple — but it’s also very, very dangerous, for all of us.
The paper describes how in Diffie-Hellman key exchange — a common means of exchanging cryptographic keys over untrusted channels — it’s possible to save a lot of computation and programmer time by using one of a few, widely agreed-upon large prime numbers. The theoreticians who first proposed this described it as secure against anyone who didn’t want to spend a nearly unimaginable amount of money attacking it.
Lost in transition between the theoreticians and practicioners was the distinction between “secure against anyone who doesn’t have a titanic amount of money to blow” and “secure against anyone,” and so many of our cryptographic tools use hard-coded and/or standardized large primes for Diffie-Hellman.
The paper’s authors posit that the NSA has undertaken a technological project on a scale “not seen since the Enigma cryptanalysis during World War II,” spending an appreciable fraction of the entire black budget to break the standard widely used primes.
It’s like the (spoiler alert) scene at the end of Real Genius when we learn that Lazlo has won the entire Frito Lay Sweepstakes by entering it 1.65 million times — attacking a problem that requires an unimaginable amount of resource with…an unimaginable amount of resource. See also: Penn and Teller painstakingly training live cockroaches to behave in a certain way to attain a magic effect, and the Penguin taping shredded documents back together.
The NSA has two missions, and they’re in tension with one another: first, to defend America’s electronic realm; second, to attack other countries’ electronic realms. If the NSA has broken these standard primes, then they have a serious advantage in the second mission, but they’re failing the first mission. The NSA isn’t the only agency with this kind of budget, and the breaks they attain will be attained by their competitors (assuming the important data doesn’t just leak first). That means that Americans who rely on hard-coded standard primes for Diffie-Hellman are in serious jeopardy, and the NSA isn’t doing anything to solve it.
Though that’s not quite true. The NSA has been advising people to stay away from Diffie-Hellman for a while, telling us to use elliptic curves instead. But since the NSA was caught sabotaging elliptic curve standards, many people have assumed that they were cynically trying to manipulate us into using weak crypto, not obliquely warning us about weaknesses in “strong” crypto.
There is a legitimate debate to be had about the best way to attain good security: nonstandard primes for Diffie-Hellman, elliptic curves, or something else. Though it’s a highly technical debate, it is also a critical one, which will determine the long-term security of everything from your car’s steering to your pacemaker to the seismic dampener in your apartment building. The NSA seems to have withheld this vital contribution to this long-term solution in order to realize an extremely short-term advantage, with lasting consequences.
Based on the evidence we have, we can’t prove for certain that NSA is doing this. However, our proposed Diffie-Hellman break fits the known technical details about their large-scale decryption capabilities better than any competing explanation. For instance, the Snowden documents show that NSA’s VPN decryption infrastructure involves intercepting encrypted connections and passing certain data to supercomputers, which return the key. The design of the system goes to great lengths to collect particular data that would be necessary for an attack on Diffie-Hellman but not for alternative explanations, like a break in AES or other symmetric crypto. While the documents make it clear that NSA uses other attack techniques, like software and hardware “implants,” to break crypto on specific targets, these don’t explain the ability to passively eavesdrop on VPN traffic at a large scale.
Since weak use of Diffie-Hellman is widespread in standards and implementations, it will be many years before the problems go away, even given existing security recommendations and our new findings. In the meantime, other large governments potentially can implement similar attacks, if they haven’t already.
Our findings illuminate the tension between NSA’s two missions, gathering intelligence and defending U.S. computer security. If our hypothesis is correct, the agency has been vigorously exploiting weak Diffie-Hellman, while taking only small steps to help fix the problem. On the defensive side, NSA has recommended that implementors should transition to elliptic curve cryptography, which isn’t known to suffer from this loophole, but such recommendations tend to go unheeded absent explicit justifications or demonstrations. This problem is compounded because the security community is hesitant to take NSA recommendations at face value, following apparent efforts to backdoor cryptographic standards.
This state of affairs puts everyone’s security at risk. Vulnerability on this scale is indiscriminate—it impacts everybody’s security, including American citizens and companies—but we hope that a clearer technical understanding of the cryptanalytic machinery behind government surveillance will be an important step towards better security for everyone.
How is NSA breaking so much crypto?
[Alex Halderman and Nadia Heninger/Freedom to Tinker]
(Image: Deviant Ollam)