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.
Encrypted communications could have an undetectable backdoor
You might be wondering how the researchers managed to do something which practically takes hundreds of years, with the computational hardware available today.
In a research paper [PDF] published Tuesday, the researchers explained that the Diffie-Hellman algorithm does not contain any backdoor itself, but it has been intentionally weakened in an undetectable way by hiding the fact how various applications generate prime numbers.
Additionally, the size of keys (i.e. less than or equals to 1024-bit) chosen to be used in the Diffie-Hellman algorithm also matters a lot.
The researchers created a weak 1024-bit Diffie-Hellman trapdoor function, i.e. randomly selecting large prime number but from a predefined group, and showed that solving the discrete logarithm problem that underpins its security is about 10,000 times easier.
"Current estimates for 1024-bit discrete log in general suggest that such computations are likely within range for an adversary who can afford hundreds of millions of dollars of special-purpose hardware," the researchers wrote in their paper.So, advanced hackers or well-resourced agencies who are aware of the fact how prime numbers are being generated for trapdoor function and looking to decrypt 1024-bit secured communications can unscramble the discrete logarithm in order to decrypt hundreds of millions of Diffie-Hellman-protected communications.
"The discrete logarithm computation for our backdoored prime was only feasible because of the 1024-bit size, and the most effective protection against any backdoor of this type has always been to use key sizes for which any computation is infeasible," the researchers said.Researchers also estimate that conducting similar computations for 2048-bit keys, even with backdoored prime numbers, would be 16 Million times harder in comparison to 1024-bit keys and will remain infeasible for many upcoming years.
Despite the U.S. National Institute of Standards and Technology (NIST) recommending a transition to key sizes of at least 2,048 bits since 2010, the 1024-bit keys are still widely used online.
According to a survey performed by the SSL Pulse project, 22% of the Internet's top 140,000 HTTPS-protected sites use 1024-bit keys as of last month, which can be broken by nation-sponsored adversaries or intelligence agencies like NSA.
Therefore, the immediate solution to this issue is to switch to 2048-bit or even 4,096-bit keys, but, according to the researchers, in the future, all standardized prime numbers should be published together with their seeds.
The concept of backdooring primes used in the Diffie-Hellman key exchange algorithm is almost similar to the one discovered in the Dual Elliptic Curve Deterministic Random Bit Generator, better known as Dual_EC_DRBG, which is also believed to have been introduced by the NSA.
Almost three years ago, Snowden leaks revealed that RSA received $10 Million bribe from the NSA to implement their flawed cryptographic algorithm Dual_EC_DRBG in its bSafe Security tool as a default protocol in its products to keep encryption weak.
So, it is not at all surprising if the NSA would be using these undetectable and weakened "trapdoors" in millions of cryptographic keys to decrypt encrypted traffic over the Internet.
