A kilobit hidden SNFS discrete logarithm computation

Joshua Fried 1 Pierrick Gaudry 2 Nadia Heninger 1 Emmanuel Thomé 2
1 CIS - Department of Computer and Information Science [Pennsylvania]
2 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : 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.
Keywords : Number Field Sieve Cryptanalysis Discrete Logarithm Problem Computer Security
Type de document :
Communication dans un congrès
Jean-Sébastien Coron; Jesper Buus Nielsen. 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques - Eurocrypt 2017, Apr 2017, Paris, France. Springer, Lecture Notes in Computer Science, 10210, 2017, Advances in Cryptology – EUROCRYPT 2017. 〈https://eurocrypt2017.di.ens.fr/〉. 〈10.1007/978-3-319-56620-7_8〉
Liste complète des métadonnées

Littérature citée [43 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01376934
Contributeur : Emmanuel Thomé <>
Soumis le : mardi 18 juillet 2017 - 08:41:07
Dernière modification le : jeudi 11 janvier 2018 - 06:27:51
Document(s) archivé(s) le : samedi 27 janvier 2018 - 03:01:02

Fichiers

paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

UNIV-LORRAINE | LORIA-ALGO | LORIA | INRIA2017 | INRIA | GRID5000

Citation

Joshua Fried, Pierrick Gaudry, Nadia Heninger, Emmanuel Thomé. A kilobit hidden SNFS discrete logarithm computation. Jean-Sébastien Coron; Jesper Buus Nielsen. 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques - Eurocrypt 2017, Apr 2017, Paris, France. Springer, Lecture Notes in Computer Science, 10210, 2017, Advances in Cryptology – EUROCRYPT 2017. 〈https://eurocrypt2017.di.ens.fr/〉. 〈10.1007/978-3-319-56620-7_8〉. 〈hal-01376934v2〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

343

Téléchargements de fichiers

152

Contact


archive-ouverte@inria.fr