International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Novel Key Recovery Attack on Secure ECDSA Implementation by Exploiting Collisions between Unknown Entries

Authors:
Sunghyun Jin , School of Cyber Security, Korea University, Seoul, Republic of Korea; Center for Information Security Technologies, Institute of Cyber Security and Privacy, Korea University, Seoul, Republic of Korea
Sangyub Lee , National Institute for Mathematical Sciences, Daejeon, Republic of Korea
Sung Min Cho , CIOT, Seongnam, Republic of Korea
HeeSeok Kim , Department of Cyber Security, College of Science and Technology, Korea University, Sejong, Republic of Korea
Seokhie Hong , School of Cyber Security, Korea University, Seoul, Republic of Korea; 2 Center for Information Security Technologies, Institute of Cyber Security and Privacy, Korea University, Seoul, Republic of Korea
Download:
DOI: 10.46586/tches.v2021.i4.1-26
URL: https://tches.iacr.org/index.php/TCHES/article/view/9058
Search ePrint
Search Google
Abstract: In this paper, we propose a novel key recovery attack against secure ECDSA signature generation employing regular table-based scalar multiplication. Our attack exploits novel leakage, denoted by collision information, which can be constructed by iteratively determining whether two entries loaded from the table are the same or not through side-channel collision analysis. Without knowing the actual value of the table entries, an adversary can recover the private key of ECDSA by finding the condition for which several nonces are linearly dependent by exploiting only the collision information. We show that this condition can be satisfied practically with a reasonable number of digital signatures and corresponding traces. Furthermore, we also show that all entries in the pre-computation table can be recovered using the recovered private key and a sufficient number of digital signatures based on the collision information. As case studies, we find that fixed-base comb and T_SM scalar multiplication are vulnerable to our attack. Finally, we verify that our attack is a real threat by conducting an experiment with power consumption traces acquired during T_SM scalar multiplication operations on an ARM Cortex-M based microcontroller. We also provide the details for validation process.
Video from TCHES 2021
BibTeX
@article{tches-2021-31309,
  title={Novel Key Recovery Attack on Secure ECDSA Implementation by Exploiting Collisions between Unknown Entries},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universit├Ąt Bochum},
  volume={2021, Issue 4},
  pages={1-26},
  url={https://tches.iacr.org/index.php/TCHES/article/view/9058},
  doi={10.46586/tches.v2021.i4.1-26},
  author={Sunghyun Jin and Sangyub Lee and Sung Min Cho and HeeSeok Kim and Seokhie Hong},
  year=2021
}