Paper 2021/455

Guessing Bits: Improved Lattice Attacks on (EC)DSA with Nonce Leakage

Chao Sun, Thomas Espitau, Mehdi Tibouchi, and Masayuki Abe

Abstract

The lattice reduction attack on (EC)DSA (and other Schnorr-like signature schemes) with partially known nonces, originally due to Howgrave-Graham and Smart, has been at the core of many concrete cryptanalytic works, side-channel based or otherwise, in the past 20 years. The attack itself has seen limited development, however: improved analyses have been carried out, and the use of stronger lattice reduction algorithms has pushed the range of practically vulnerable parameters further, but the lattice construction based on the signatures and known nonce bits remain the same. In this paper, we propose a new idea to improve the attack based on the same data in exchange for additional computation: carry out an exhaustive search on some bits of the secret key. This turns the problem from a single bounded distance decoding (BDD) instance in a certain lattice to multiple BDD instances in a fixed lattice of larger volume but with the same bound (making the BDD problem substantially easier). Furthermore, the fact that the lattice is fixed lets us use batch/preprocessing variants of BDD solvers that are far more efficient than repeated lattice reductions on non-preprocessed lattices of the same size. As a result, our analysis suggests that our technique is competitive or outperforms the state of the art for parameter ranges corresponding to the limit of what is achievable using lattice attacks so far (around 2-bit leakage on 160-bit groups, or 3-bit leakage on 256-bit groups). We also show that variants of this idea can also be applied to bits of the nonces (leading to a similar improvement) or to filtering signature data (leading to a data-time trade-off for the lattice attack). Finally, we use our technique to obtain an improved exploitation of the TPM--FAIL dataset similar to what was achieved in the Minerva attack.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in TCHES 2022
Contact author(s)
sun chao 46s @ st kyoto-u ac jp
History
2021-10-14: revised
2021-04-08: received
See all versions
Short URL
https://ia.cr/2021/455
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/455,
      author = {Chao Sun and Thomas Espitau and Mehdi Tibouchi and Masayuki Abe},
      title = {Guessing Bits: Improved Lattice Attacks on (EC)DSA with Nonce Leakage},
      howpublished = {Cryptology ePrint Archive, Paper 2021/455},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/455}},
      url = {https://eprint.iacr.org/2021/455}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.