Problem solve Get help with specific problems with your technologies, process and projects.

# 1024-bit encryption keys: How 'trapdoored' primes have caused insecurity

## Encryption algorithms using 1024-bit keys are no longer secure, due to the emergence of 'trapdoored' primes. Expert Michael Cobb explains how the encryption backdoor works.

The National Institute of Standards and Technology (NIST) has recommended minimum key sizes of 2048-bits for the...

Digital Signature Algorithm (DSA), Rivest-Shamir-Adleman algorithm (RSA) and Diffie-Hellman Algorithm since 2010, and has disallowed the use of 1024-bit keys for government agencies since 2014.

However, 1024-bit keys are still commonly used. Implementation and compatibility problems are one reason for this -- for example, the Domain Name System Security Extensions' specifications limit DSA keys to a maximum of 1024-bits, and Java has only supported Diffie-Hellman and DSA keys larger than 1024-bits since version 8 was released in 2014.

The general view that 1024-bit keys can only be broken at a cost beyond the resources of most attackers has also created a lack of any sense of urgency regarding increasing key sizes.

However, due to a new phenomenon known as trapdoored primes, described in the paper "A Kilobit Hidden SNFS Discrete Logarithm Computation," successful attacks on 1024-bit keys are no longer theoretical. Trapdoored primes allow an attacker to efficiently break certain 1024-bit keys to decrypt communications and cryptographically impersonate key owners to sign data, all unbeknownst to the victim.

The security of many encryption systems is based on mathematical problems involving prime numbers so large that the problems are prohibitively hard for attackers to solve -- a discrete logarithm problem. Unlike prime numbers in RSA keys, which are always supposed to be unique, the primes used by Diffie-Hellman and DSA are frequently standardized, and used by a large number of applications.

There is the possibility that some of these primes have been trapdoored. These are specially crafted prime numbers, where the special number field sieve, a special-purpose integer factorization algorithm, can be used to solve the discrete logarithm problem that underpins the key's security. It makes breaking a trapdoored 1024-bit prime at least 10,000 times easier.

What's even worse is that there is no known, feasible way of telling if a key has been compromised, as a key with a trapdoored prime looks like any other key. Once cracked, an attacker can trivially crack any encryption made using this prime. This encryption backdoor can be used to decrypt communications encrypted using the Diffie-Hellman key exchange or to forge signatures using the DSA algorithm, which are both cornerstones of network and data security.

The attacker has to get the victim to use the trapdoored prime, but if the attacker gets one or more trapdoored primes incorporated into a standard or widely used library, then hundreds of millions of users become potential victims, as the attacker will have possession of the shared secret used to generate the keys encrypting their data and communications.

Top secret National Security Agency memos leaked by Edward Snowden implied that the integrity of a number of encryption systems had been intentionally weakened, and this research shows that some standardized 1024-bit primes may be trapdoored, as they cannot be properly verified. For example, Diffie-Hellman group parameters are specified in RFC 5114, and are widely used as the basis for generating encryption keys in sensitive applications that use the Transport Layer Security protocol, the Secure Shell protocol for remotely administering servers and the Internet Key Exchange protocol.

These parameters were drawn from NIST test data, but there's no public information about the seeds used to generate the finite field parameters. Also, the Federal Information Processing Standard Publication 186, Digital Signature Standard doesn't require mandatory publication of the seeds used in prime number generation. This means that it is certainly possible that trapdoored primes exist and are actively being used -- any 1024-bit primes that can't be verified as truly random should now be considered insecure.

Enterprises and software developers that use cryptosystems based on the hardness of discrete logarithm problems need to start using keys of at least 2048-bits as soon as possible, and move to using elliptic curve cryptography wherever possible. The researchers estimate that keys with trapdoored primes of 2048-bits take 16 million times longer to crack.

Until standardized primes are generated using a verifiable randomness procedure, and the seeds are published, there will be no way to properly verify them, leaving any cryptosystems based upon finite field discrete logarithms open to being successfully broken.

#### Next Steps

Find out how to differentiate a security backdoor from a vulnerability

Discover how a cryptographic algorithm led to a backdoor in Juniper firewall products

Learn how the Pork Explosion vulnerability led to the creation of an Android backdoor

This was last published in March 2017

## Content

Find more PRO+ content and other member only offers, here.

### 1 comment

Send me notifications when other members comment.
What has your enterprise's experience been moving to larger encryption key sizes?
Cancel

## SearchCloudSecurity

• ### Cloudflare Access takes on VPNs with reverse proxy approach

Cloudflare takes inspiration from Google's BeyondCorp with a new service called Cloudflare Access, which aims to replace ...

• ### TLS 1.3: What it means for enterprise cloud use

The latest draft version of TLS 1.3 is out, and it will likely affect enterprises that use cloud services. Expert Ed Moyle ...

• ### The biggest cloud security threats, according to the CSA

The Cloud Security Alliance reported what it found to be the biggest cloud security threats. Expert Rob Shapland looks at how ...

## SearchNetworking

• ### ExtremeLocation latest addition to Extreme wireless portfolio

Extreme Networks is targeting retailers with a new set of services, called ExtremeLocation. The latest technology adds ...

• ### Take network configuration management tools to the next level

Script management systems and intent-based networking are driving the future of network configuration management tools, shifting ...

• ### Cybersecurity skills shortage continues to worsen

This week, bloggers explore the cybersecurity skills shortage, the challenges of deploying edge computing and how best to ...

## SearchCIO

• ### Wayfair's chief architect talks AI-driven innovation, impactful IT

Wayfair sells home furnishings, but under the covers, it's a tech juggernaut. Chief Architect Ben Clark explains how AI-driven ...

• ### Synthetic data could ease the burden of training data for AI models

Sometimes it's better to manufacture training data for machine learning models than it is to collect it.

• ### CES 2018 for CIOs: Rise of the AI voice assistant class

What happens in Vegas doesn't stay there -- not at CES 2018, where AI voice assistants and sentient objects were ubiquitous and ...

## SearchEnterpriseDesktop

• ### Ten Windows 10 Fall Creators Update features to know

Microsoft introduced some significant changes to Windows 10 in the Fall Creators Update. The My People app, for example, lets ...

• ### Guard the line with Windows Defender features

The Windows 10 Fall Creators Update took Windows 10 security up a notch by adding advanced features to Windows Defender, ...

• ### Ready to master virtualization-based security in Windows 10?

Put your knowledge of virtualization-based security in Windows 10 on the line with this quiz covering the ins and outs of ...

## SearchCloudComputing

• ### Google Cloud Dedicated Interconnect offers VPN alternative

Google's Dedicated Interconnect enables an enterprise to privately connect its data center to the public cloud. Here's a ...

• ### Chip bugs hit cloud computing usage less than first feared

IT shops expected their cloud usage to flag due to recent chip bugs, but most environments survived the patches unscathed.

• ### Providers continue to push hybrid cloud technologies in 2018

The hybrid cloud market changes rapidly, as major cloud providers release new services to bridge private and public platforms, ...

## ComputerWeekly.com

• ### UK and France to collaborate on digital tech

The UK and French governments have joined forces to increase technology and innovation cooperation between the two nations

• ### Create security culture to boost cyber defences, says Troy Hunt

Security suffers when there is tension between software developers and security professionals, but it is common in many ...

• ### Nordic IT executive interview: Daniel Kjellén, CEO, Tink

Sweden could have a head start in the race to open up banking through the European Union’s PSD2 regulation

Close