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

DOI:

https://doi.org/10.46586/tches.v2023.i2.568-586

Keywords:

ECDSA, Lattice Sieving, Hidden Number Problem, Side-channel Attack, Cryptanalysis

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.

Downloads

Published

2023-03-06

How to Cite

Xu, L., Dai, Z., Wu, B., & Lin, D. (2023). Improved Attacks on (EC)DSA with Nonce Leakage by Lattice Sieving with Predicate. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2023(2), 568–586. https://doi.org/10.46586/tches.v2023.i2.568-586

Issue

Section

Articles