How NSA successfully Broke Trillions of Encrypted Connections

Yes, it seems like the mystery has been solved.

We are aware of the United States National Security Agency (NSA) powers to break almost unbreakable encryption used on the Internet and intercept nearly Trillions of Internet connections – thanks to the revelations made by whistleblower Edward Snowden in 2013.



However, what we are not aware of is exactly how did the NSA apparently intercept VPN connections, and decrypt SSH and HTTPS, allowing the agency to read hundreds of Millions of personal, private emails from persons around the globe.

Now, computer scientists Alex Halderman and Nadia Heninger have presented a paper at the ACM Conference on Computer and Communications Security that advances the most plausible theory as to how the NSA broke some of the most widespread encryption used on the Internet.

According to the paper, the NSA has exploited common implementations of the Diffie-Hellman key exchange algorithm – a common means of exchanging cryptographic keys over untrusted channels – to decrypt a large number of HTTPS, SSH, and VPN connections.

Diffie-Hellman – the encryption used for HTTPS, SSH, and VPNs – helps users communicate by swapping cryptographic keys and running them through an algorithm that nobody else knows except the sender and receiver.

It is described as secure against surveillance from the NSA and other state-sponsored spies, as it would take hundreds or thousands of years and by them and a nearly unimaginable amount of money to decrypt directly.

However, a serious vulnerability in the way the Diffie-Hellman key exchange is implemented is allowing the intelligence agencies and spies to break and eavesdrop on trillions of encrypted connections.

To crack just one of the extremely large prime numbers of a Diffie-Hellman in the most commonly used 1024-bit Diffie-Hellman keys would take about a year and cost a few hundred Million dollars.

However, according to researchers, only a few prime numbers are commonly used that might have fit well within the agency's $11 Billion-per-year budget dedicated to "groundbreaking cryptanalytic capabilities."

"Since a handful of primes are so widely reused, the payoff, in terms of connections they could decrypt, would be enormous," said Alex Halderman and Nadia Heninger in a blog post published Wednesday.

"Breaking a single, 1024-bit prime would allow the NSA to passively decrypt connections to two-thirds of VPNs and a quarter of all SSH servers globally. Breaking a second 1024-bit prime would allow passive eavesdropping on connections to nearly 20% of the top million HTTPS websites. In other words, a one-time investment in massive computation would make it possible to eavesdrop on trillions of encrypted connections."

Around 92% of the top 1 Million Alexa HTTPS domains make use of the same two primes for Diffie-Hellman, possibly enabling the agency to pre-compute a crack on those two prime numbers and read nearly all Internet traffic through those servers.

According to the duo, this NSA technological project to crack crypto on a scale has "not seen since the Enigma cryptanalysis during World War II."

For in-depth detail, you can read the full paper entitled Imperfect Forward Secrecy: How Diffie-Hellman Fails In Practice [PDF].
SC:THN