October 12, 2016
In the year 2014, we came to know about the NSA’s ability to break Trillions of encrypted connections by exploiting common implementations of the Diffie-Hellman key exchange algorithm – thanks to classified documents leaked by ex-NSA employee Edward Snowden.
At that time, computer scientists and senior cryptographers had presented the most plausible theory: Only a few prime numbers were commonly used by 92 percent of the top 1 Million Alexa HTTPS domains that might have fit well within the NSA’s $11 Billion-per-year budget dedicated to “groundbreaking cryptanalytic capabilities.”
And now, researchers from University of Pennsylvania, INRIA, CNRS and Université de Lorraine have practically proved how the NSA broke the most widespread encryption used on the Internet.
Diffie-Hellman key exchange (DHE) algorithm is a standard means of exchanging cryptographic keys over untrusted channels, which allows protocols such as HTTPS, SSH, VPN, SMTPS and IPsec to negotiate a secret key and create a secure connection.
Since applications that rely on the Diffie-Hellman key exchange algorithm generates ephemeral keys using groups of large prime numbers, it would take hundreds or thousands of years and a nearly unimaginable amount of money to decrypt secure communications directly.
However, it took researchers just two months and as many as 3,000 CPUs to break one of the 1024-bit keys, which could have allowed them to passively decrypt hundreds of millions of HTTPS-based communications and other Transport Layer Security (TLS) channels.