Attacking (EC)DSA Given Only an Implicit Hint

Jean-Charles Faugère 1, 2 Christopher Goyet 1, 2, 3 Guénaël Renault 1, 2, *
* Auteur correspondant
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : We describe a lattice attack on DSA-like signature schemes under the assumption that implicit infor- mation on the ephemeral keys is known. Inspired by the implicit oracle of May and Ritzenhofen presented in the context of RSA (PKC2009), we assume that the ephemeral keys share a certain amount of bits without knowing the value of the shared bits. This work also extends results of Leadbitter, Page and Smart (CHES2004) which use a very similar type of partial information leakage. By eliminating the shared blocks of bits between the ephemeral keys, we provide lattices of small dimension (e.g. equal to the number of signatures) and thus obtain an efficient attack. More precisely, by using the LLL algorithm, the complexity of the attack is polynomial. We show that this method can work when ephemeral keys share certain amount of MSBs and/or LSBs, as well as contiguous blocks of shared bits in the middle. Under the Gaussian heuristic assumption, theoretical bounds on the number of shared bits in function of the number of signed messages are proven. Experimental results show that we are often able to go a few bits beyond the theoretical bound. For instance, if only 2 shared LSBs on each ephemeral keys of 200 signed messages (with no knowledge about the secret key) then the attack reveals the secret key. The success rate of this attack is about 90% when only 1 LSB is shared on each ephemeral keys associated with about 400 signed messages.
Type de document :
Communication dans un congrès
Knudsen, Lars R. and Wu, Huapeng. Selected Areas in Cryptography, Aug 2012, Windsor, Canada. Springer, 7707, pp.252-274, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-35999-6_17〉
Liste complète des métadonnées

Littérature citée [38 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00777804
Contributeur : Guénaël Renault <>
Soumis le : vendredi 18 janvier 2013 - 10:45:17
Dernière modification le : lundi 29 mai 2017 - 14:21:59
Document(s) archivé(s) le : samedi 1 avril 2017 - 06:56:43

Fichier

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

Identifiants

Collections

Citation

Jean-Charles Faugère, Christopher Goyet, Guénaël Renault. Attacking (EC)DSA Given Only an Implicit Hint. Knudsen, Lars R. and Wu, Huapeng. Selected Areas in Cryptography, Aug 2012, Windsor, Canada. Springer, 7707, pp.252-274, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-35999-6_17〉. 〈hal-00777804〉

Partager

Métriques

Consultations de la notice

365

Téléchargements de fichiers

572