Interesting summary of research by Team Caramba on trapdooring primes. Essentially they created primes in a way that they wouldn’t be obvious that they were trapdoored, but would still give them (and potential attackers) the ability to crack the primes much more efficiently than if they had been random.
We have completed a cryptanalysis computation which is at the same time a formidable achievement in terms of size (a 1024-bit discrete logarithm computation), and a small-scale undertaking in terms of computational resources (two months of calendar time on 2000 to 3000 cores). In comparison, the “real” record for discrete logarithm is 768 bits (announced this spring) and required 10 times as much computational power.
To achieve this, we cheated. Deliberately. We chose the prime number which defines the problem to be solved in a special way, so that the computation can be made much more efficient. However, we did this in a subtle way, so that the trapdoor we inserted cannot be detected.
Unfortunately, for most of the prime numbers used in cryptography today, we have no guarantee that they have not been generated with such a trapdoor. We estimate that breaking a non-trapdoored 1024-bit prime is at least 10,000 times harder than breaking our trapdoored prime was for us once we knew the trapdoor.
Our computation raises questions about some Internet standards that contain opaque, fixed primes. Theoretically, we know how to guarantee that primes have not been generated with a trapdoor, but most widely used primes come with no such public guarantee. A malicious party who inserted a trapdoored prime into a standard or an implementation would be able to break any communication whose security relies on one of these primes in a short amount of time.
Brief summary for technically inclined readers:
We performed a 1024-bit special number sieve discrete log. The special number field sieve is faster than the general number field sieve for (rare) inputs that have a special form.
Discrete log is the computational hardness assumption underlying Diffie-Hellman key exchange and DSA digital signatures. Concrete discrete log computations are used by cryptographers to set appropriate key sizes.
Solving discrete log for a Diffie-Hellman key exchange lets an attacker decrypt messages encrypted with the negotiated key. Solving discrete log for a DSA signature lets an attacker forge signatures.
We have not been able to find any documented seeds or verifiable randomness for widely used 1024-bit primes such as the RFC 5114 primes. Using “nothing up my sleeve” numbers to generate primes like the Oakley groups or the TLS 1.3 negotiated finite field Diffie-Hellman groups (RFC 7919) is a reasonable guarantee of not containing a backdoor.
The attack we describe affects only Diffie-Hellman and DSA, not ECDH or ECDSA. For RSA, there are not global public parameters like the primes used for Diffie-Hellman that could contain a backdoor like this.
If you run a server, use elliptic-curve cryptography or primes of at least 2048 bits.
If you are a developer or standards committee member, use verifiable randomness to generate any fixed cryptographic parameters, and publicly document your seeds. Appendix A.1.1.2 of FIPS 186 describes how to do this for DSA primes.