A kilobit hidden SNFS discrete logarithm computation
This work highlights a security vulnerability in cryptographic systems like DSA by showing that trapdoored primes, which are hard to detect, can be practically exploited, urging the need for verifiably random primes to defend against such attacks.
The authors performed the first known discrete logarithm computation for a 1024-bit prime field using a trapdoored prime, demonstrating that such back-doored parameters are feasible with current technology, taking just over two months on an academic cluster. They also computed discrete logarithms for multiple weak primes found in use, though no widespread trapdoored primes were detected.
We perform a special number field sieve discrete logarithm computation in a 1024-bit prime field. To our knowledge, this is the first kilobit-sized discrete logarithm computation ever reported for prime fields. This computation took a little over two months of calendar time on an academic cluster using the open-source CADO-NFS software. Our chosen prime $p$ looks random, and $p--1$ has a 160-bit prime factor, in line with recommended parameters for the Digital Signature Algorithm. However, our p has been trapdoored in such a way that the special number field sieve can be used to compute discrete logarithms in $\mathbb{F}\_p^*$ , yet detecting that p has this trapdoor seems out of reach. Twenty-five years ago, there was considerable controversy around the possibility of back-doored parameters for DSA. Our computations show that trapdoored primes are entirely feasible with current computing technology. We also describe special number field sieve discrete log computations carried out for multiple weak primes found in use in the wild. As can be expected from a trapdoor mechanism which we say is hard to detect, our research did not reveal any trapdoored prime in wide use. The only way for a user to defend against a hypothetical trapdoor of this kind is to require verifiably random primes.