Makes More Sense than a Mysterious Breakthrough in Mathematics

There have been a number of reports, some of which appear to have come from the NSA itself, that the secretive organization can decrypt what should be unbreakable codes.

It now appears that this is not some sort of mathematics breakthrough. Instead,a recent paper suggests the basic algorithm used for key exchange appear to be flawed.

They further suggest, and I agree, that the NSA is to some degree responsible for the ubiquity of this security flaw:

There have been rumors for years that the NSA can decrypt a significant fraction of encrypted Internet traffic. In 2012, James Bamford published an article quoting anonymous former NSA officials stating that the agency had achieved a “computing breakthrough” that gave them “the ability to crack current public encryption.” The Snowden documents also hint at some extraordinary capabilities: they show that NSA has built extensive infrastructure to intercept and decrypt VPN traffic and suggest that the agency can decrypt at least some HTTPS and SSH connections on demand.

However, the documents do not explain how these breakthroughs work, and speculation about possible backdoors or broken algorithms has been rampant in the technical community. Yesterday at ACM CCS, one of the leading security research venues, we and twelve coauthors presented a paper that we think solves this technical mystery.

The key is, somewhat ironically, Diffie-Hellman key exchange, an algorithm that we and many others have advocated as a defense against mass surveillance. Diffie-Hellman is a cornerstone of modern cryptography used for VPNs, HTTPS websites, email, and many other protocols. Our paper shows that, through a confluence of number theory and bad implementation choices, many real-world users of Diffie-Hellman are likely vulnerable to state-level attackers.

For the nerds in the audience, here’s what’s wrong: If a client and server are speaking Diffie-Hellman, they first need to agree on a large prime number with a particular form. There seemed to be no reason why everyone couldn’t just use the same prime, and, in fact, many applications tend to use standardized or hard-coded primes. But there was a very important detail that got lost in translation between the mathematicians and the practitioners: an adversary can perform a single enormous computation to “crack” a particular prime, then easily break any individual connection that uses that prime.

………

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.

My money is on the NSA creating this problem, rather than it merely exploiting it.

Based on what I've read, it seems more consistent with the social norms of that organization.