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.

Featured

Slideshows

Educating from the epicentre - Why distributors are the pulse checkers of the channel

Educating from the epicentre - Why distributors are the pulse checkers of the channel

​As the channel changes and industry voices deepen, the need for clarity and insight heightens. Market misconceptions talk of an “under pressure” distribution space, with competitors in that fateful “race for relevance” across New Zealand. Amidst the cliched assumptions however, distribution is once again showing its strength, as a force to be listened to, rather than questioned. Traditionally, the role was born out of a need for vendors and resellers to find one another, acting as a bridge between the testing lab and the marketplace. Yet despite new technologies and business approaches shaking the channel to its very core, distributors remain tied to the epicentre - providing the voice of reason amidst a seismic industry shift. In looking across both sides of the vendor and partner fences, the middle concept of the three-tier chain remains centrally placed to understand the metrics of two differing worlds, as the continual pulse checkers of the local channel. This exclusive Reseller News Roundtable, in association with Dicker Data and rhipe, examined the pivotal role of distribution in understanding the health of the channel, educating from the epicentre as the market transforms at a rapid rate.

Educating from the epicentre - Why distributors are the pulse checkers of the channel
Kiwi channel reunites as After Hours kicks off 2017

Kiwi channel reunites as After Hours kicks off 2017

After Hours made a welcome return to the channel social calendar last night, with a bumper crowd of distributors, vendors and resellers descending on The Jefferson in Auckland to kickstart 2017. Photos by Maria Stefina.

Kiwi channel reunites as After Hours kicks off 2017
Arrow exclusively introduces Tenable Network Security to A/NZ channel

Arrow exclusively introduces Tenable Network Security to A/NZ channel

Arrow Electronics introduced Tenable Network Security to local resellers in Sydney last week, officially launching the distributor's latest security partnership across Australia and New Zealand. Representing the first direct distribution agreement locally for Tenable specifically, the deal sees Arrow deliver security solutions directly to mid-market and enterprise channel partners on both sides of the Tasman.

Arrow exclusively introduces Tenable Network Security to A/NZ channel
Show Comments