Using Bleichenbacher's Solution to the Hidden Number Problem to Attack Nonce Leaks in 384-Bit ECDSA

Elke De Mulder; Michael Hutter; Mark E.  Marson; Peter Pearson

Paper 2013/346

Using Bleichenbacher's Solution to the Hidden Number Problem to Attack Nonce Leaks in 384-Bit ECDSA

Elke De Mulder, Michael Hutter, Mark E. Marson, and Peter Pearson

Abstract

In this paper we describe an attack against nonce leaks in 384-bit ECDSA using an FFT-based attack due to Bleichenbacher. The signatures were computed by a modern smart card. We extracted the low-order bits of each nonce using a template-based power analysis attack against the modular inversion of the nonce. We also developed a BKZ-based method for the range reduction phase of the attack, as it was impractical to collect enough signatures for the collision searches originally used by Bleichenbacher. We confirmed our attack by extracting the entire signing key using a 5-bit nonce leak from 4000 signatures.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Accepted at CHES 2013,
Keywords: cryptanalysis digital signatures lattice techniques public-key cryptography smart cards
Contact author(s): elke @ cryptography com
History: 2013-06-09: received
Short URL: https://ia.cr/2013/346
License: CC BY

BibTeX

@misc{cryptoeprint:2013/346,
      author = {Elke De Mulder and Michael Hutter and Mark E.  Marson and Peter Pearson},
      title = {Using Bleichenbacher's Solution to the Hidden Number Problem to Attack Nonce Leaks in 384-Bit {ECDSA}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/346},
      year = {2013},
      url = {https://eprint.iacr.org/2013/346}
}