International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Improved Attacks on (EC)DSA with Nonce Leakage by Lattice Sieving with Predicate

Authors:
Luyao Xu , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China
Zhengyi Dai , College of Computer, National University of Defense Technology, Changsha 410073, China
Baofeng Wu , State Key Laboratory of Information Security, Institute of Information Engineering, ChineseAcademy of Sciences, Beijing 100093, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China
Dongdai Lin , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China
Download:
DOI: 10.46586/tches.v2023.i2.568-586
URL: https://tches.iacr.org/index.php/TCHES/article/view/10294
Search ePrint
Search Google
Abstract: Lattice reduction algorithms have been proved to be one of the most powerful and versatile tools in public key cryptanalysis. In this work, we primarily concentrate on lattice attacks against (EC)DSA with nonce leakage via some sidechannel analysis. Previous works relying on lattice reduction algorithms such as LLL and BKZ will finally lead to the “lattice barrier”: lattice algorithms become infeasible when only fewer nonce is known. Recently, Albrecht and Heninger introduced lattice algorithms augmented with a predicate and broke the lattice barrier (Eurocrypt 2021). We improve their work in several aspects.We first propose a more efficient predicate algorithm which aims to search for the target lattice vector in a large database. Then, we combine sieving with predicate algorithm with the “dimensions for free” and “progressive sieving” techniques to further improve the performance of our attacks. Furthermore, we give a theoretic analysis on how to choose the optimal Kannan embedding factor.As a result, our algorithm outperforms the state-of-the-art lattice attacks for existing records such as 3-bit nonce leakage for a 256-bit curve and 2-bit nonce leakage for a 160-bit curve in terms of running time, sample numbers and success probability. We also break the lattice records on the 384-bit curve with 3-bit nonce leakage and the 256-bit curve with 2-bit nonce leakage which are thought infeasible previously. Finally, we give the first lattice attack against ECDSA with a single-bit nonce leakage, which enables us to break a 112-bit curve with 1-bit nonce leakage in practical time.
BibTeX
@article{tches-2023-33048,
  title={Improved Attacks on (EC)DSA with Nonce Leakage by Lattice Sieving with Predicate},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2023, Issue 2},
  pages={568-586},
  url={https://tches.iacr.org/index.php/TCHES/article/view/10294},
  doi={10.46586/tches.v2023.i2.568-586},
  author={Luyao Xu and Zhengyi Dai and Baofeng Wu and Dongdai Lin},
  year=2023
}