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

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.