NSA broke trillions of encrypted connections due to a flaw

Pierluigi Paganini October 17, 2015

A flaw affecting the way encryption software implements the Diffie-Hellman key exchange algorithm allowed the NSA to break trillions of encrypted connections.

Edward Snowden has revealed to the world that the NSA was able to crack also the almost encryption to conduct a large-scale online surveillance. According to Snowden, the intelligence Agency was able to decrypt and intercept nearly Trillions of Internet connections. The US cyber spies were able to spy on every connection, including VPN ones, SSH and HTTPs were not able to protect netizens from prying eyes.

How was it possible?

Now the mystery has a solution, the computer scientists Alex Halderman and Nadia Heninger have presented a paper at the ACM Conference on Computer and Communications Security that explained how the NSA has intercepted encrypted connections breaking the Internet encryption.

nsa spy on North Korea

HTTPS, SSH, and VPNs rely on the Diffie-Hellman encryption to establish a secure connection by swapping cryptographic keys and running them through an algorithm that is known only to the sender and the receiver.
The critical flaw was exploited by the NSA to break and eavesdrop on trillions of encrypted connections.

The NSA hasn’t broken the Diffie-Hellman, instead, they target the start of the process. For each actor involved in the communication is generated a couple of keys, the public key is shared with the interlocutor, meanwhile, the private key is kept secret. The algorithm generates a common public key, a large prime number which is agreed upon at the start of the process.

Unfortunately, due to a wrong implementation of the algorithm, only a few prime numbers are commonly used.


Prime numbers are public and it is computationally expensive to generate new ones, for this reason, many encryption systems reuse them to improve performance.

The experts noticed that one single prime is used to encrypt two-thirds of all VPNs and a quarter of all the SSH servers. A second prime is used to encrypt “nearly 20% of the top million HTTPS websites”.

Do you want an idea of how law diffused it the problem? 

Around 92% of the top 1 Million Alexa HTTPS domains use of the same two primes for Diffie-Hellman, the NSA may have exploited this issue to intercept the traffic.

“Based on the evidence we have, we can’t prove for certain that NSA is doing this. However, our proposed Diffie-Hellman break fits the known technical details about their large-scale decryption capabilities better than any competing explanation.”

Since a handful of primes are so widely reused, the payoff, in terms of connections they could decrypt, would be enormous,” wrote the researchers in a blog post.

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.


[adrotate banner=”9″] [adrotate banner=”12″]

Pierluigi Paganini

(Security Affairs – NSA, Diffie-Hellman)

[adrotate banner=”5″]

[adrotate banner=”13″]

you might also like

leave a comment