client-side DH tracker

Cryptanalysis of 1024-bit trapdoored primes

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:

This work was done by:

The academic article describing the work is here.

Additional links: Computer Security Research group at UPenn; INRIA/LORIA CARAMBA project.

Note (10/07): an earlier version of this note had a typo regarding the comparison to a non-trapdoored 1024-bit prime.

Last modification: Tue 18 Oct 2016 12:34:06 PM CEST
© 2006– members of the project-team ; valid XHTML 1.0, valid CSS