If The NSA's Not Complaining About Encryption, It's Likely Because It Has Already Found A Way In

from the we-left-ourselves-a-key-to-the-back-door-under-the-mat dept

The NSA hasn't said much (well... compared to the FBI) over the past several months about the default phone encryption offered by Google and Apple. This lack of public outcry has to do with the NSA's capabilities, rather than a sudden interest in ensuring people around the world have access to secure communications. If it truly felt the world would be a better place with safer computing, it wouldn't have invested so much in hardware implants, software exploits and -- its biggest black budget line -- defeating encryption.

Where there's no smoke, there's a great deal of fire which can neither be confirmed nor denied. The NSA has very likely punched holes in encryption in existing encryption. But how does it do it? A brute force attack on encryption would be largely futile, even with the computing power the agency possesses. Alex Halderman and Nadia Heninger at Freedom to Tinker have a theory, and it involves a "flaw" in a highly-recommended encryption algorithm.

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.

The belief that these common primes (or at least some of them) wouldn't be cracked relied on the assumption that no one entity would have the money to assemble the computing force needed to break the code. The problem is that the NSA likely has the time, money and power to tackle this enormous project. Here's why it first seemed unlikely:

For the most common strength of Diffie-Hellman (1024 bits), it would cost a few hundred million dollars to build a machine, based on special purpose hardware, that would be able to crack one Diffie-Hellman prime every year.

And here's the reality of the situation, as exposed by documents leaked by Snowden.

The 2013 “black budget” request, leaked as part of the Snowden cache, states that NSA has prioritized “investing in groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic.” It shows that the agency’s budget is on the order of $10 billion a year, with over $1 billion dedicated to computer network exploitation, and several subprograms in the hundreds of millions a year.

What was once considered to be beyond the capabilities of even the biggest intelligence agency is obviously well within its reach. As the authors point out, this would explain the other information seen in leaked documents, like the NSA's ability to decrypt some secured connections "on command" or eavesdrop on VPN traffic.

This is still just a theory, but it does seem to explain much of what's been uncovered in leaked documents. It also shows the NSA is still doing what the NSA does best: leaving lots of stuff poorly-secured, despite directives otherwise.

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.

As the authors point out, the NSA has recommended better encryption methods, but no one's in any hurry to adopt them because no one trusts the NSA to recommend a method it hasn't already weakened, if not completely compromised. If there's any truth to what's covered here, the NSA has sat quietly by and allowed researchers to recommend yet another encryption method that it's already made large strides towards defeating. And, once again, we can see that when the word "security" is combined with the word "national," it means something completely different than when it stands on its own.

Filed Under: alex halderman, backdoors, diffie hellman, diffie hellman key exchange, encryption, hacking, https, nadia heninger, nsa, surveillance, vpns