NSA may have had ability to bypass ‘unbreakable’ encryption for years

The NSA could have been able to peer into a large amount of encrypted communications thanks to a commonplace weakness in cryptographic technology, according to the findings of two researchers.

There have long been rumors that NSA has a way to get past cryptography that is otherwise considered to be bulletproof. Computer scientists J Alex Halderman and Nadia Heninger may have just proven those rumors true in a paper that they published with a team of a dozen experts who pieces together clues from Edward Snowden’s leaked documents.

Privacy advocates have encouraged developers of websites and other internet communications to use a cryptographic protocol called the “Diffie-Hellman key exchange,” saying that it would keep data safe from prying eyes. In fact, the researchers note, one single prime is used to encrypt two-thirds of all virtual private networks (VPNs) and a quarter of secure shell (SSH) servers globally, two major security protocols used by a number of businesses. A second prime is used to encrypt “nearly 20 [percent] of the top million HTTPS websites.” This is a commonly used way of keeping data indecipherable for anyone except its intended recipient – almost anyone, that is.

READ MORE: NSA, GCHQ targeted Kaspersky, other cybersecurity companies – Snowden docs

The paper, titled 'Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice’, describes the key exchange as a way of saving a lot of computation and programmer time by using a few, widely agreed-upon large prime numbers. The theoreticians who came up with Diffie-Hellman in 1976 described it as a way to keep data safe from anyone but exceptionally well-funded and determined institutions.

According to Halderman and Heninger, the NSA is the exceptional institution that proved the rule.

“Diffie-Hellman is a cornerstone of modern cryptography used for [virtual private networks], HTTPS websites, email, and many other protocols,” the two wrote on the Freedom to Tinker blog. “We and many others have advocated [for it] as a defense against mass surveillance.” But thanks to advances in computing power and some weaknesses in implementation, it’s less secure than widely believed, they write in their paper.

The first and simplest part of the problem is that some implementations of Diffie-Hellman simply don’t require large enough prime numbers in the exchange. If the protocol uses 512-bit primes instead of 1024-bit prime, then breaking it is “well within reach” by powerful modern computers, the researchers wrote. “Two decades of algorithmic and computational improvements have significantly lowered the bar to attacks on such key sizes,” they added.

Getting past 1024-bit primes would require a machine that costs a few hundred million dollars, yet that supercomputer would still only be able to crack about one 1024-bit prime a year, the authors wrote.

READ MORE: FBI director pleads with Silicon Valley for access to encrypted data

But the 1024-prime version is vulnerable to another flaw in Diffie-Hellman that researchers discovered, which lies in the exchange at the start of the process. Each person generates a public key, available to everyone transferring their info, and a private key, which they keep secret. But they also generate a common public key at the start of the process in the form of a very large prime number.

The problem is that many of these 1024-bit prime numbers are reused because of how (previously) inconceivably expensive it would be to break them. As noted above, the researchers found that one single prime number is used to encrypt two-thirds of all VPNs and a quarter of all SSH servers, two security measures used by businesses globally. Another is used to encrypt 18 percent of the “top million HTTPS websites.” That means that a single instance of the aforementioned year-long cracking effort could give the NSA access to all of this information.

“This isn’t a flaw in a particular protocol, it’s a property of the math [that] underlies Diffie-Hellman, which is part of the foundation of almost every important cryptographic protocol we use,” Halderman said. “It’s certainly not an overnight [fix]. One of the problems is that the standards behind any important protocols like the IPsec VPN protocol specify that everyone will use these particular primes that by virtue of being so lightly used are made weaker. I think it’s going to be years unfortunately before standards and implementations are widely updated to account for this threat.”