14 DAY TRIAL // A group of 14 researchers presented a paper at the 22nd ACM Conference on Computer and Communications Security (ACM CCS) in Denver on Wednesday, October 14, a paper on which they base a theory of how the NSA can break most of the Web's HTTP and VPN traffic due to a flaw in the implementation of the Diffie-Hellman algorithm used to encrypt Web traffic.
The research paper is not new, having already been released to the public back in May, when it caused a lot of ruckus in the infosec community, exposing the famous Logjam attack, which could be used to compromise secure communications between a client and a server by downgrading the TLS connection to the vulnerable 512-bit, export-grade cryptography.
Now, along with the presentation that its authors gave to the ACM CCS audience, an explanatory article on one of Princeton University's blogs also sheds some light on the theory its creators have around their research.
A design and implementation flaw puts all secure Web connections at risk
According to their research, the scientists claim that, despite being a very strong cryptographic algorithm, Diffie-Hellman is plagued by a series of flaws, which mainly reside in the way it was implemented.
Because the algorithm was designed to encrypt traffic around an extremely large prime number, on which both the server and the client need to agree beforehand, breaking the algorithm usually requires huge computational resources and a lot of time to do so, which makes it impossible to implement in real-world traffic decryption scenarios.
"How enormous a computation, you ask? Possibly a technical feat on a scale (relative to the state of computing at the time) not seen since the Enigma cryptanalysis during World War II," say Alex Halderman and Nadia Heninger, two of the researchers.
Researchers estimate that the cost of decrypting Diffie-Hellman traffic is around a few hundred million dollars per year, if the attackers wanted to crack traffic encrypted only with one prime number alone.
The problem lies in the fact that most parties that used Diffie-Hellman to encrypt traffic usually agreed on a few sets of prime numbers, which they heavily reused.
This design flaw, despite the enormous complexity of the Diffie-Hellman algorithm, makes it quite vulnerable, and allows state-powered attackers to rethink their budget when it comes to cracking Diffie-Hellman-encrypted traffic, even if it's at a steady pace of one prime number per year.
Theory: This is how the NSA is breaking encrypted traffic
Even if not holding any solid evidence, the researchers believe that their findings explain how the NSA has been able to break and decrypt VPN and HTTPS connections for a while.
They base their theory on a series of documents Edward Snowden released in the past, which detailed an internal NSA infrastructure that perfectly fits their theory's MO for a machine that's purposely set to break Diffie-Hellman traffic.
As the researchers explain, breaking only one single 1024-bit prime number used with the algorithm would allow the NSA to spy on two-thirds of all VPN connections, and a quarter of all SSH traffic.
A second 1024-bit prime number would boost up the NSA's capabilities to 20% of all HTTPS traffic in the top one million sites on the Web.
If taking into account the Electronic Frontier Foundation's findings that the US is allocating around $10 billion per year to the NSA's black budget, all of a sudden, a few hundred million invested in cracking encrypted Web traffic looks like quite a solid investment.
Since the Diffie-Hellman algorithm has been used in so many applications and fields, this weakness in its vendor implementation makes this theory quite hard to argue down.
This is not the first case of researchers making a claim to fame by boasting to have found the NSA's secret method of decrypting traffic, but it makes more sense than everything else we've heard until now.
If you'd like to read the full report and all the technical details, the Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice report is available for download.