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."

Join the PC World newsletter!

Error: Please check your email address.

Our Back to Business guide highlights the best products for you to boost your productivity at home, on the road, at the office, or in the classroom.

Keep up with the latest tech news, reviews and previews by subscribing to the Good Gear Guide newsletter.

Lucian Constantin

IDG News Service
Show Comments

Most Popular Reviews

Latest News Articles

Resources

PCW Evaluation Team

Azadeh Williams

HP OfficeJet Pro 8730

A smarter way to print for busy small business owners, combining speedy printing with scanning and copying, making it easier to produce high quality documents and images at a touch of a button.

Andrew Grant

HP OfficeJet Pro 8730

I've had a multifunction printer in the office going on 10 years now. It was a neat bit of kit back in the day -- print, copy, scan, fax -- when printing over WiFi felt a bit like magic. It’s seen better days though and an upgrade’s well overdue. This HP OfficeJet Pro 8730 looks like it ticks all the same boxes: print, copy, scan, and fax. (Really? Does anyone fax anything any more? I guess it's good to know the facility’s there, just in case.) Printing over WiFi is more-or- less standard these days.

Ed Dawson

HP OfficeJet Pro 8730

As a freelance writer who is always on the go, I like my technology to be both efficient and effective so I can do my job well. The HP OfficeJet Pro 8730 Inkjet Printer ticks all the boxes in terms of form factor, performance and user interface.

Michael Hargreaves

Windows 10 for Business / Dell XPS 13

I’d happily recommend this touchscreen laptop and Windows 10 as a great way to get serious work done at a desk or on the road.

Aysha Strobbe

Windows 10 / HP Spectre x360

Ultimately, I think the Windows 10 environment is excellent for me as it caters for so many different uses. The inclusion of the Xbox app is also great for when you need some downtime too!

Mark Escubio

Windows 10 / Lenovo Yoga 910

For me, the Xbox Play Anywhere is a great new feature as it allows you to play your current Xbox games with higher resolutions and better graphics without forking out extra cash for another copy. Although available titles are still scarce, but I’m sure it will grow in time.

Featured Content

Latest Jobs

Don’t have an account? Sign up here

Don't have an account? Sign up now

Forgot password?