Paper 2004/277

Experimenting with Faults, Lattices and the DSA

David Naccache, Phong Q. Nguyen, Michael Tunstall, and Claire Whelan

Abstract

We present an attack on DSA smart-cards which combines physical fault injection and lattice reduction techniques. This seems to be the first (publicly reported) physical experiment allowing to concretely pull-out DSA keys out of smart-cards. We employ a particular type of fault attack known as a glitch attack, which will be used to actively modify the DSA nonce k used for generating the signature: k will be tampered with so that a number of its least significant bytes will flip to zero. Then we apply well-known lattice attacks on El Gamal-type signatures which can recover the private key, given sufficiently many signatures such that a few bits of each corresponding k are known. In practice, when one byte of each k is zeroed, 27 signatures are sufficient to disclose the private key. The more bytes of k we can reset, the fewer signatures will be required. This paper presents the theory, methodology and results of the attack as well as possible countermeasures.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. To be presented at PKC 2005
Keywords
DSApublic keysmart cardsfaultsattacks
Contact author(s)
david naccache @ gemplus com
History
2004-11-19: last of 7 revisions
2004-10-30: received
See all versions
Short URL
https://ia.cr/2004/277
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/277,
      author = {David Naccache and Phong Q.  Nguyen and Michael Tunstall and Claire Whelan},
      title = {Experimenting with Faults, Lattices and the DSA},
      howpublished = {Cryptology ePrint Archive, Paper 2004/277},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/277}},
      url = {https://eprint.iacr.org/2004/277}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.