A Tale of Three Signatures: practical attack of ECDSA with wNAF

Gabrielle De Micheli; Rémi Piau; Cécile Pierrot

Paper 2019/861

A Tale of Three Signatures: practical attack of ECDSA with wNAF

Gabrielle De Micheli, Rémi Piau, and Cécile Pierrot

Abstract

One way of attacking ECDSA with wNAF implementation for the scalar multiplication is to perform a side-channel analysis to collect information, then use a lattice based method to recover the secret key. In this paper, we reinvestigate the construction of the lattice used in one of these methods, the Extended Hidden Number Problem (EHNP). We find the secret key with only 3 signatures, thus reaching the theoretical bound given by Fan, Wang and Cheng, whereas best previous methods required at least 4 signatures in practice. Our attack is more efficient than previous attacks, in particular compared to times reported by Fan et al. at CCS 2016 and for most cases, has better probability of success. To obtain such results, we perform a detailed analysis of the parameters used in the attack and introduce a preprocessing method which reduces by a factor up to 7 the overall time to recover the secret key for some parameters. We perform an error resilience analysis which has never been done before in the setup of EHNP. Our construction is still able to find the secret key with a small amount of erroneous traces, up to 2% of false digits, and 4% with a specific type of error. We also investigate Coppersmith's methods as a potential alternative to EHNP and explain why, to the best of our knowledge, EHNP goes beyond the limitations of Coppersmith's methods.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Major revision. AFRICACRYPT 2020
DOI: 10.1007/978-3-030-51938-4_18
Keywords: ECDSA lattice techniques cryptanalysis digital signatures
Contact author(s): gabrielle de-micheli @ inria fr
cecile pierrot @ inria fr
History: 2020-07-17: last of 3 revisions; 2019-07-24: received; See all versions
Short URL: https://ia.cr/2019/861
License: CC BY

BibTeX

@misc{cryptoeprint:2019/861,
      author = {Gabrielle De Micheli and Rémi Piau and Cécile Pierrot},
      title = {A Tale of Three Signatures: practical attack of {ECDSA} with {wNAF}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/861},
      year = {2019},
      doi = {10.1007/978-3-030-51938-4_18},
      url = {https://eprint.iacr.org/2019/861}
}