Research Article
Another Lattice Attack Against ECDSA with the wNAF to Recover More Bits per Signature
@INPROCEEDINGS{10.1007/978-3-031-25538-0_7, author={Ziqiang Ma and Shuaigang Li and Jingqiang Lin and Quanwei Cai and Shuqin Fan and Fan Zhang and Bo Luo}, title={Another Lattice Attack Against ECDSA with the wNAF to Recover More Bits per Signature}, proceedings={Security and Privacy in Communication Networks. 18th EAI International Conference, SecureComm 2022, Virtual Event, October 2022, Proceedings}, proceedings_a={SECURECOMM}, year={2023}, month={2}, keywords={ECDSA windowed Non-Adjacent-Form Lattice attack Hidden number problem Extended hidden number problem Cache side channel}, doi={10.1007/978-3-031-25538-0_7} }- Ziqiang Ma
Shuaigang Li
Jingqiang Lin
Quanwei Cai
Shuqin Fan
Fan Zhang
Bo Luo
Year: 2023
Another Lattice Attack Against ECDSA with the wNAF to Recover More Bits per Signature
SECURECOMM
Springer
DOI: 10.1007/978-3-031-25538-0_7
Abstract
In the resource-constrained environment such as the Internet of Things, the windowed Non-Adjacent-Form (wNAF) representation is usually used to improve the calculation speed of the scalar multiplication of ECDSA. This paper presents a practical cache side channel attack on ECDSA implementations which use wNAF representation. Compared with existing works, our method exploits more information from the cache side channels, which is then efficiently used to construct lattice attacks in the ECDSA private key recovery. First, we additionally monitor the invert function which is related to the sign of the wNAF digits, and obtain a Double-Add-Invert chain through the Flush+Flush cache side channel. Then, we develop effective methods extracting 154.2 bits information of the ephemeral key per signature for 256-bit ECDSA from this chain, much more than the best known result which extracts 105.8 bits per signature. Finally, to efficiently use the extracted information, we convert the problem of recovering the private key to the Hidden Number Problem (HNP) and the Extended Hidden Number Problem (EHNP) respectively, which are solved by lattice reduction algorithms. We applied the attack on ECDSA with the secp256k1 curve in OpenSSL 1.1.0h. The experimental results show that only 3 signatures are enough to recover the private key. To the best of our knowledge, this work exploits the signs of the wNAF representation, along with the Double-Add chain against ECDSA, to recover the private key withthe least number of signatures.
