Open AccessNovel Key Recovery Attack on Secure ECDSA Implementation by Exploiting Collisions between Unknown Entries
Author(s) -
Sunghyun Jin,
Sangyub Lee,
Sung Min Cho,
Hee Seok Kim,
Seokhie Hong
Publication year - 2021
Publication title -
iacr transactions on cryptographic hardware and embedded systems
Language(s) - English
Resource type - Journals
ISSN - 2569-2925
DOI - 10.46586/tches.v2021.i4.1-26
Subject(s) - elliptic curve digital signature algorithm , computer science , scalar multiplication , collision , collision attack , timing attack , digital signature , cryptographic nonce , side channel attack , key (lock) , power analysis , public key cryptography , scalar (mathematics) , cryptography , computer security , elliptic curve cryptography , mathematics , hash function , encryption , geometry , double hashing , cryptographic hash function
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.