EHNP Strikes Back: Analyzing SM2 Implementations

The SM2 digital signature algorithm is part of the Chinese standard public key cryptography suite designed on elliptic curves and has been included in various Chinese commercial applications. Due to the structure of the algorithm and quality of coding, some implementations are vulnerable to potential side-channel attacks and leak information about the double-and-add chains. Popular SM2 libraries such as GmSSL, TASSL and old versions of OpenSSL still use sliding-window (recommended by standard) or wNAF to conduct scalar multiplication of points, which is vulnerable to side-channel attacks like Flush+Reload: key recovery is then an instance of the Extended Hidden Number Problem (EHNP). The EHNP can be reduced to the Shortest Vector Problem (SVP) and solved with lattice algorithms. In this paper, we propose an extended key-recovery attack with leaked double-and-add chains from signature schemes such as SM2 and ECDSA. The side-channel leakage is possible in libraries which use wNAF or sliding-window multiplication. Our approach translates side information of different implementations to an EHNP instance, then propose novel strategies to reduce the EHNP to SVP in a lattice of smaller dimension than previous method, and introduce our algorithms to solve the problem. To evaluate the probability, we provide new estimations for the norm of the target vector, and formulate a tradeoff function. Finally, we show the new record of attacking SM2 with provided information. We are able to recover the secret key with only three signatures, while previous attacks required more than six signatures. We also attack the SM2 traces with improved probability and efficiency. Our new algorithm does not rely on any specific digital signature scheme, thus can be used to attack other signature algorithms.