In a recent IDG Network World article, author Lucian Constantin points to research by the University of Pennsylvania, INRIA, CNRS and Universite de Lorraine that exposes a serious implementation weakness in public key cryptography.
In their snappily titled paper (“a kilobit hidden SNFS discrete logarithm computation”), the team determines that the standardization of key elements of popular cryptographic algorithms (such as Diffie-Hellman and RSA) means that the primes used to generate the algorithms could have been intentionally back-doored, without our knowledge.
The existence of the back-door is brought about by a basic lack of true randomness. The net effect of which was a significant reduction in the security of the algorithm.
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 back-doored 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 “back-doored” — selected to simplify the computation that would normally be required to crack the encryption.
The research team created a back-doored 1024-bit Diffie-Hellman prime and demonstrated how easy (relatively speaking) it was to crack, compared to a truly random prime.
This has some pretty wide-ranging implications for public key encryption. Short-cutting the generation of truly random primes is a common practice. Unfortunately, the generation of weak primes is, for all intents and purposes, undetectable.
This means that so-called secure communications could have an inherent, undetectable weakness. One that only comes to light when the crypto is cracked.
Back in 2013, Edward Snowden suggested that the NSA was able to decrypt a significant percentage of VPN traffic. Given the wide-spread practice of using a small number of standardized primes within cryptography, it’s easy to see why.
In the 2015 paper, Imperfect Forward Secrecy: How Diffie-Hellman fails in practice, it is estimated that cracking a single 1024-bit group would allow for passive eavesdropping on one in five popular HTTPS sites. Breaking a second group would allow for decryption of traffic to two-thirds of IPSec VPNs and a quarter of SSH servers.
Predictability is the enemy of security
When it comes to cryptography, entropy (randomness) is the key to security. Predictability is the enemy of secure cryptography, as the entire cryptographic system is only as strong as the source of randomness used to generate the primes.
However, not all sources of randomness are the same. Random number generators come in two basic forms: software and hardware. Software solutions are not capable of providing true randomness as they are based on deterministic computer programs.
Most hardware random number generators rely on classical physics to produce what looks like a random stream of bits. However, in reality, determinism is hidden behind complexity. For truly random numbers, you need to look to quantum physics.
To find out more about quantum random number generation and quantum cryptography, contact IDQ direct on +41 22 301 83 71 or email email@example.com