Researchers warn that many 1024-bit keys used to secure communications on the internet today might be based on prime numbers that have been intentionally backdoored in an undetectable way.
Many public-key cryptography algorithms that are used to secure web, email, VPN, SSH and other types of connections on the internet derive their strength from the mathematical complexity of discrete logarithms -- computing discrete logarithms for groups of large prime numbers cannot be efficiently done using classical methods. This is what makes cracking strong encryption computationally impractical.
Most key-generation algorithms rely on prime parameters whose generation is supposed to be verifiably random. However, many parameters have been standardized and are being used in popular crypto algorithms like Diffie-Hellman and DSA without the seeds that were used to generate them ever being published. That makes it impossible to tell whether, for example, the primes were intentionally "backdoored" -- selected to simplify the computation that would normally be required to crack the encryption.
Researchers from University of Pennsylvania, INRIA, CNRS and Université de Lorraine recently published a paper in which they show why this lack of cryptographic transparency is problematic and could mean that many encryption keys used today are based on backdoored primes without anyone -- aside from those who created them -- knowing.
To demonstrate this, the researchers created a backdoored 1024-bit Diffie-Hellman prime and showed that solving the discrete log problem for it is several orders of magnitude easier than for a truly random one.
"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 said in their paper. "In contrast, we were able to perform a discrete log computation on a specially trapdoored prime in two months on an academic cluster."
The problem is that for someone who doesn't know about the backdoor, demonstrating that a prime has been trapdoored in the first place would be nearly impossible.
"The near universal failure of implementers to use verifiable prime generation practices means that use of weak primes would be undetectable in practice and unlikely to raise eyebrows."
This is conceptually similar to the backdoor found in the Dual_EC random number generator, which is believed to have been introduced by the U.S. National Security Agency. However, that backdoor was much easier to find and, unlike Diffie-Hellman or DSA, Dual_EC never received widespread adoption.
Diffie-Hellman ephemeral (DHE) is slowly replacing RSA as the preferred key exchange algorithm in TLS due to its perfect forward secrecy property that's supposed to keep past communications secure even if the key is compromised in the future. However, the use of backdoored primes would defeat that security benefit.
Sign up for CIO Asia eNewsletters.