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.

 

The NSA sure breaks a lot of “unbreakable” crypto. This is probably how they do it. / Boing Boing