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

DOI:

https://doi.org/10.46586/tches.v2021.i4.1-26

Keywords:

Public-key cryptography, Digital signature, ECDSA, Scalar multiplication, Side-channel analysis, Collision attack

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.

Downloads

Published

2021-08-11

Issue

Section

Articles

How to Cite

Novel Key Recovery Attack on Secure ECDSA Implementation by Exploiting Collisions between Unknown Entries. (2021). IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021(4), 1-26. https://doi.org/10.46586/tches.v2021.i4.1-26