Paper 2024/296

Attacking ECDSA with Nonce Leakage by Lattice Sieving: Bridging the Gap with Fourier Analysis-based Attacks

Yiming Gao, University of Science and Technology of China
Jinghui Wang, University of Science and Technology of China
Honggang Hu, University of Science and Technology of China
Binang He, University of Science and Technology of China
Abstract

The Hidden Number Problem (HNP) has found extensive applications in side-channel attacks against cryptographic schemes, such as ECDSA and Diffie-Hellman. There are two primary algorithmic approaches to solving the HNP: lattice-based attacks and Fourier analysis-based attacks. Lattice-based attacks exhibit better efficiency and require fewer samples when sufficiently long substrings of the nonces are known. However, they face significant challenges when only a small fraction of the nonce is leaked, such as 1-bit leakage, and their performance degrades in the presence of errors. In this paper, we address an open question by introducing an algorithmic tradeoff that significantly bridges the gap between these two approaches. By introducing a parameter $x$ to modify Albrecht and Heninger's lattice, the lattice dimension is reduced by approximately $(\log_2{x})/ l$, where $l$ represents the number of leaked bits. We present a series of new methods, including the interval reduction algorithm, several predicates, and the pre-screening technique. Furthermore, we extend our algorithms to solve the HNP with erroneous input. Our attack outperforms existing state-of-the-art lattice-based attacks against ECDSA. We break several records including 1-bit and less than 1-bit leakage on a 160-bit curve, while the best previous lattice-based attack for 1-bit leakage was conducted only on a 112-bit curve.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in ASIACRYPT 2024
Keywords
ECDSAHidden Number ProblemLattice SievingLattice-based Attacks
Contact author(s)
qw1234567 @ mail ustc edu cn
liqing21 @ mail ustc edu cn
hghu2005 @ ustc edu cn
hebinang @ mail ustc edu cn
History
2024-09-18: last of 4 revisions
2024-02-21: received
See all versions
Short URL
https://ia.cr/2024/296
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/296,
      author = {Yiming Gao and Jinghui Wang and Honggang Hu and Binang He},
      title = {Attacking {ECDSA} with Nonce Leakage by Lattice Sieving: Bridging the Gap with Fourier Analysis-based Attacks},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/296},
      year = {2024},
      url = {https://eprint.iacr.org/2024/296}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.