Menu
Encrypted communications could have an undetectable backdoor

Encrypted communications could have an undetectable backdoor

Researchers warn about the use of standardized or hard-coded primes in existing cryptosystems

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.

Furthermore, 1024-bit keys are still widely used online, despite the U.S. National Institute of Standards and Technology recommending a transition to larger key sizes since 2010. According to the SSL Pulse project, 22 percent of the internet's top 140,000 HTTPS-enabled websites use 1024-bit keys.

"Our results are yet another reminder that 1024-bit primes should be considered insecure for the security of cryptosystems based on the hardness of discrete logarithms," the researchers said. "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 estimate that performing similar computations for 2048-bit keys, even with backdoored primes, would be 16 million times harder than for 1024-bit keys and will remain infeasible for many years to come. The immediate solution is to switch to 2048-bit keys, but in the future all standardized primes should be published together with their seeds, the researchers said.

Documents leaked in 2013 by former NSA contractor Edward Snowden suggested that the agency has the ability to decrypt a lot of VPN traffic. Last year, a group of researchers speculated that the reason for this was the widespread use in practice of a small number of fixed or standardized groups of primes.

"Performing precomputation for a single 1024-bit group would allow passive eavesdropping on 18% of popular HTTPS sites, and a second group would allow decryption of traffic to 66% of IPsec VPNs and 26% of SSH servers," the researchers said in their paper at that time. "A close reading of published NSA leaks shows that the agency’s attacks on VPNs are consistent with having achieved such a break."

Follow Us

Join the New Zealand Reseller News newsletter!

Error: Please check your email address.

Slideshows

Top 50 defining moments of the New Zealand channel in 2016

Top 50 defining moments of the New Zealand channel in 2016

Reseller News looks back on a tumultuous 12 months for the New Zealand channel, assessing the fallout from a year of sizeable industry change. Whether it be local or global mergers and acquisitions, distribution deals or job changes, the channel that started the year differs somewhat to the one set to finish it - Reseller News assesses the key moments that made 2016.​

Top 50 defining moments of the New Zealand channel in 2016
​Hewlett Packard Enterprise honours high achieving NZ channel

​Hewlett Packard Enterprise honours high achieving NZ channel

Hewlett Packard Enterprise honoured its top performing Kiwi partners at the second running of its HPE Partner Awards in New Zealand, held at a glitzy ceremony in Auckland. Recognising excellence across eight categories - from distributors to resellers - the tech giant celebrated its first year as a standalone company, following its official split from HP in 2015.

​Hewlett Packard Enterprise honours high achieving NZ channel
Nutanix treats channel partners to Christmas cruise

Nutanix treats channel partners to Christmas cruise

Nutanix recently took to the seas for a Christmas Cruise around Sydney Harbour with its Australia and New Zealand staff, customers and partners to celebrate a stellar year for the vendor. With the sun out, they were all smiles and mingled over drinks and food.

Nutanix treats channel partners to Christmas cruise
Show Comments