Thursday, 2 June 2016
For years, privacy advocates have pushed developers of websites, virtual private network apps, and other cryptographic software to adopt the Diffie-Hellman cryptographic key exchange as a defense against surveillance from the US National Security Agency and other state-sponsored spies. Now, researchers are renewing their warning that a serious flaw in the way the key exchange is implemented is allowing the NSA to break and eavesdrop on trillions of encrypted connections.
The cost for adversaries is by no means modest. For commonly used 1024-bit keys, it would take about a year and cost a "few hundred million dollars" to crack just one of the extremely large prime numbers that form the starting point of a Diffie-Hellman negotiation. But it turns out that only a few primes are commonly used, putting the price well within the NSA's $11 billion-per-year budget dedicated to "groundbreaking cryptanalytic capabilities."
Halderman and Heninger say their theory fits what's known about the NSA's mass decryption capabilities better than any competing explanation. Documents leaked by former NSA subcontractor Edward Snowden, for instance, showed the agency was able to monitor encrypted VPN connections, pass intercepted data to supercomputers, and then obtain the key required to decrypt the communications.
"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," the researchers wrote. "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."
The blog post came as Halderman, Heninger, and a raft of other researchers formally presented their academic paper detailing their findings to the 22nd ACM Conference on Computer and Communications Security in Denver on Wednesday. The paper, titled "Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice," received extensive media coverage in May when the paper was first released. Besides exposing the likely secret behind the NSA's mass interception of encrypted communications, the paper also revealed a closely related attack that left tens of thousands of HTTPS-protected websites, mail servers, and other widely used Internet services open to less sophisticated eavesdroppers.
The Logjam weakness was the result of export restrictions the US government mandated in the 1990s on US developers who wanted their software to be used abroad. The regimen was established by the Clinton administration so that the FBI and other agencies could break the encryption used by foreign entities. In the five months since the paper was released, most widely used browsers, VPNs, and server apps have removed support for 512-bit Diffie-Hellman, making Logjam much less of a threat. But a similar vulnerability can still be exploited by attackers with nation-state-sized budgets to passively decrypt the 1024-bit Diffie-Hellman key sizes that many implementations still use by default.
Halderman and Heninger's team arrived at this unsettling conclusion in May, but it's likely the NSA reached it long before then. While that knowledge makes it possible for the NSA to decrypt communications on a mass scale, it gives the same capability to other countries, some of which are adversaries to the US. Halderman and Heninger wrote:
Diffie-Hellman is the breakthrough that lets two parties that have never met before negotiate a secret key even when communicating over an unsecured, public channel that's monitored by a sophisticated adversary. It also makes possible perfect forward secrecy, which periodically changes the encryption key. That vastly increases the work of eavesdropping because attackers must obtain the ephemeral key anew each time it changes, as opposed to only once with other encryption schemes, such as those based on RSA keys. The research is significant because it shows a potentially crippling weakness in a crypto regimen widely favored by privacy and security advocates.
The original research team recommended that websites use 2048-bit Diffie-Hellman keys and published this Guide to Deploying Diffie-Hellman for TLS. The team also recommended SSH users upgrade both server and client software to the latest version of OpenSSH, which favors Elliptic-Curve Diffie-Hellman Key Exchange. Update: Nicholas Weaver, a security researcher at the University of California at Berkeley and the International Computer Science Institute, said the researchers' theory is "almost certainly correct" has analysis here.