NSA compromised Diffie-Hellman protocol?

It has long been rumored that the NSA is capable of decrypting much of the encrypted Internet traffic. This is indirect evidence. In 2012, an NSA employee, on condition of anonymity, argued that the agency had achieved a “breakthrough in computing,” which gives them “the opportunity to crack the current public cryptography”. The Snowden documents also point to some exceptional opportunities for the NSA: it follows that the agency has built a broad infrastructure for intercepting and decrypting VPN traffic, and that it probably has the ability to decrypt at least some HTTPS and SSH connections on request.

Documents do not make it clear how this is possible. On October 13, at the ACM CCS conference, well-known cryptographers Alex Halderman (Alex Halderman) and Nadia Heninger (Nadia Heninger) gave a presentation in which they assumed that they had solved this mysterious mystery. By the way, their work is recognized as the best conference report.

According to experts, the problem is in the Diffie-Hellman algorithm, which is widely used on the Internet for key exchange when installing a secure channel. It is the cornerstone of robust cryptographic security. It is used in VPN, HTTPS and many other protocols.

The Diffie-Hellman protocol allows two or more parties to obtain a shared secret key using an unprotected communication channel. The resulting key is used to encrypt further exchange using symmetric encryption algorithms.
')
The problem is this. If the client and the server exchange keys according to the Diffie-Hellman protocol, then initially they need to agree on a large prime number, which is used for further calculations. It would seem that there are no problems if everyone uses the same number, and in reality many numbers are hard-wired in many applications. But there is one important detail. And what if some intruder invests huge amounts of money in order to perform a single calculation and “crack” a particular prime number, and then it will be easy to decipher the communications of everyone who uses this number.

In their work, Halderman and Heninger assess the scale of investment. For the most common type of Diffie-Hellman (1024 bits), such a supercomputer, made on standard hardware, will cost several hundred million dollars. He will be able to crack one prime number in about a year.

Does it make sense for the intelligence agency to invest such money to process one number per year? Halderman and Heninger believe that there is. The fact is that if you crack the most common prime number in real-world applications, you can decipher two thirds of the global VPN traffic and get access to a quarter of the SSH servers!

Hacking the second most popular number gives you access to passive tapping of about 20% of HTTPS servers from the list of the million most popular sites.

In other words, a one-time investment in hardware will allow deciphering trillions of encrypted connections.

The NSA budget is undoubtedly sufficient for this.

For more information, see Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice .