Practical Key Recovery for Discrete-Logarithm Based Authentication Schemes from Random Nonce Bits.

Aurélie Bauer 1 Damien Vergnaud 2
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : We propose statistical cryptanalysis of discrete-logarithm based authentication schemes such as Schnorr identification scheme or Girault-Poupard-Stern identification and signature schemes. We consider two scenarios where an adversary is given some information on the nonces used during the signature generation process or during some identification sessions. In the first scenario, we assume that some bits of the nonces are known exactly by the adversary, while no information is provided about the other bits. We show, for instance, that the GPS scheme with 128-bit security can be broken using only 710 signatures assuming that the adversary knows (on average) one bit per nonce. In the second scenario, we assume that all bits of the nonces are obtained from the correct ones by independent bit flipping with some small probability. A detailed heuristic analysis is provided, supported by extensive experiments.
Type de document :
Communication dans un congrès
Tim Güneysu, Helena Handschuh. Cryptographic Hardware and Embedded Systems - CHES 2015, Sep 2015, Saint-Malo, France. Springer, Cryptographic Hardware and Embedded Systems - CHES 2015, 9293, pp.287-306, Lecture Notes in Computer Science. 〈http://link.springer.com/book/10.1007/978-3-662-48324-4〉. 〈10.1007/978-3-662-48324-4_15〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01214701
Contributeur : Damien Vergnaud <>
Soumis le : lundi 12 octobre 2015 - 20:05:51
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Identifiants

Collections

Citation

Aurélie Bauer, Damien Vergnaud. Practical Key Recovery for Discrete-Logarithm Based Authentication Schemes from Random Nonce Bits.. Tim Güneysu, Helena Handschuh. Cryptographic Hardware and Embedded Systems - CHES 2015, Sep 2015, Saint-Malo, France. Springer, Cryptographic Hardware and Embedded Systems - CHES 2015, 9293, pp.287-306, Lecture Notes in Computer Science. 〈http://link.springer.com/book/10.1007/978-3-662-48324-4〉. 〈10.1007/978-3-662-48324-4_15〉. 〈hal-01214701〉

Partager

Métriques

Consultations de la notice

208