Since [Snowden]’s release of thousands of classified documents in 2013, one question has tugged at the minds of security researchers: how, exactly, did the NSA apparently intercept VPN traffic, and decrypt SSH and HTTP, allowing the NSA to read millions of personal, private emails from persons around the globe? Every guess is invariably speculation, but a paper presented at the ACM Conference on Computer and Communications Security might shed some light on how the NSA appears to have broken some of the most widespread encryption used on the Internet (PDF).

The relevant encryption discussed in the paper is Diffie–Hellman key exchange (D-H), the encryption used for HTTPS, SSH, and VPN. D-H relies on a shared very large prime number. By performing many, many computations, an attacker could pre-compute a ‘crack’ on an individual prime number, then apply a relatively small computation to decrypt any individual message that uses that prime number. If all applications used a different prime number, this wouldn’t be a problem. This is the difference between cryptography theory and practice; 92% of the top 1 Million Alexa HTTPS domains use the same two prime numbers for D-H. An attacker could pre-compute a crack on those two prime numbers and consequently be able to read nearly all Internet traffic through those servers.

This sort of attack was discussed last spring by the usual security researchers, and in that time the researchers behind the paper have been hard at work. The earlier discussion focused on 512-bit D-H primes and the LogJam exploit. Since then, the researchers have focused on the possibility of cracking longer 768- and 1024-bit D-H primes. They conclude that someone with the resources of cracking a single 1024-bit prime would allow an attacker to decrypt 66% of IPsec VPNs and 26% of SSH servers.

There is a bright side to this revelation: the ability to pre-compute the ‘crack’ on these longer primes is a capability that can only be attained by nation states as it’s on a scale that has been compared to cracking Enigma during WWII. The hardware alone to accomplish this would cost millions of dollars, and although this computation could be done faster with dedicated ASICs or other specialized hardware, this too would require an enormous outlay of cash. The downside to this observation is, of course, the capability to decrypt the most prevalent encryption protocols may be in the hands of our governments. This includes the NSA, China, and anyone else with hundreds of millions of dollars to throw at a black project.