SCIENCE CHINA Information Sciences, Volume 61, Issue 3: 032105(2018) https://doi.org/10.1007/s11432-016-9030-0

## Attacking OpenSSL ECDSA with a small amount of side-channel information

• AcceptedJan 21, 2017
• PublishedAug 30, 2017
Share
Rating

### Abstract

In this work, we mount a lattice attack on the ECDSA signatures implemented by the latest version of OpenSSL which uses the windowed non-adjacent form method to implement the scalar multiplication. We first develop a new way of extracting information from the side-channel results of the ECDSA signatures. Just given a small fraction of the information about a side-channel result denoted as double-and-add chain, we take advantage of the length of the chain together with positions of two non-zero digits to recover information about the ephemeral key. Combining the information of both the most significant digits and the least significant bits, we are able to gain more information about the ephemeral key. The problem of recovering ECDSA secret key is then translated to the hidden number problem which can be solved by lattice reduction algorithms. Our attack is mounted to the series secp256k1curve, and the result shows that 85 signatures would be enough to recover the secret key, which is better than the result that previous attack gained only utilizing the information extracted from the least significant bits, using about 200 signatures to recover the secret key.

### Acknowledgment

This work was supported by National Basic Research Program of China (973 Program) (Grant No. 2013CB338003).

### References

[1] Bellare M, Canetti R, Krawczyk H. A modular approach to the design and analysis of authentication and key exchange protocols (extended abstract). In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, Dallas, 1998. 419--428. Google Scholar

[2] Blake-Wilson S, Menezes A. Entity authentication and authenticated key transport protocols employing asymmetric techniques. In: Proceedings of the 5th International Workshop on Security Protocols, Paris, 1998. 137--158. Google Scholar

[3] Diffie W, van Oorschot P C, Wiener M J. Authentication and authenticated key exchanges. Design Code Cryptoger, 1992, 2: 107--125. Google Scholar

[4] National Institute of Standards and Technology. Digital signature standard (DSS). FIPS PUB 186. http://csrc.nist.gov/publications/PubsFIPS.html. Google Scholar

[5] National Institute of Standards and Technology. Digital signature standard (DSS). FIPS PUB 186-4. http://csrc.nist.gov/publications/fips/fips186-3. Google Scholar

[6] Johnson D, Menezes A, Vanstone S A. The elliptic curve digital signature algorithm (ECDSA. Int J Inf Secur, 2001, 1: 36--63. Google Scholar

[7] Vanstone S. Responses to NISTs proposal. Commun ACM, 1992, 35: 50--52. Google Scholar

[8] Nakamoto S. Bitcoin: a peer-to-peer electronic cash system. 2008.. Google Scholar

[9] The openssl project. OpenSSL — cryptography and SSL/TLS toolkit. Version 1.0.2h. 2016. Google Scholar

[10] Yarom Y, Benger N. Recovering OpenSSL ECDSA nonces using the Ftextsclush+Rtextsceload cache side-channel attack. IACR Cryptology ePrint Archive, 2014, 140. http://eprint.iacr.org/. Google Scholar

[11] Kocher P C, Jaff J, Jun B. Differential power analysis. In: Proceedings of the 19th Annual International Cryptology Conference, Santa Barbara, 1999. 388--397. Google Scholar

[12] Page D. Theoretical use of cache memory as a cryptanalytic side-channel. IACR Cryptology ePrint Archive 2002, 2002: 169. http://eprint.iacr.org/. Google Scholar

[13] Acı içmez O, Koç Ç K, Seifert J P. On the power of simple branch prediction analysis. In: Proceedings of the 2nd ACM Symposium on Information, Computer and Communications Security, Singapore, 2007. 312--320. Google Scholar

[14] Brumley B B, Hakala R M. Cache-timing template attacks. In: Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, 2009. 667--684. Google Scholar

[15] Tromer E, Osvik D A, Shamir A. Efficient cache attacks on AES and countermeasures. J Cryptol, 2010, 23: 37--71. Google Scholar

[16] Brumley B B, Tuveri N. Remote timing attacks are still practical. In: Proceedings of the 16th European Symposium on Research in Computer Security, Leuven, 2011. 355--371. Google Scholar

[17] Zhang Y, Juels A, Reiter M K, et al. Cross-VM side channels and their use to extract private keys. In: Proceedings of the ACM Conference on Computer and Communications Security, Raleigh, 2012. 305--316. Google Scholar

[18] Irazoqui G, Inci M S, Eisenbarth T, et al. Lucky 13 strikes back. In: Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security, Singapore, 2015. 85--96. Google Scholar

[19] Yarom Y, Falkner K. Ftextsclush+Rtextsceload: a high resolution, low noise, L3 cache side-channel attack. In: Proceedings of the 23rd USENIX Security Symposium (USENIX Security 2014), San Diego, 2014. 719--732. Google Scholar

[20] Allan T, Brumley B B, Falkner K, et al. Amplifying side channels through performance degradation. In: Proceedings of the 32nd Annual Conference on Computer Security Applications, Los Angeles, 2016. 422--435. Google Scholar

[22] Benger N, van de Pol J, Smart N P, et al. “Ooh aah… just a little bit: a small amount of side channel can go a long way. In: Proceedings of the 16th International Workshop on Cryptographic Hardware and Embedded System, Busan, 2014. 75--92. Google Scholar

[23] Howgrave-Graham N, Smart N P. Lattice attacks on digital signature schemes. Design Code Cryptoger, 2001, 23: 283--290. Google Scholar

[24] Nguyen P Q, Shparlinski I. The insecurity of the digital signature algorithm with partially known nonces. J Cryptol, 2002, 15: 151--176. Google Scholar

[25] Nguyen P Q, Shparlinski I. The insecurity of the elliptic curve digital signature algorithm with partially known nonces. Design Code Cryptoger, 2003, 30: 201--217. Google Scholar

[26] Liu M, Nguyen P Q. Solving BDD by enumeration: an update. In: Proceedings of Cryptographers Track at the RSA Conference, San Francisco, 2013. 293--309. Google Scholar

[27] Chen Y, Nguyen P. BKZ2.0: better lattice security estimates. In: Proceedings of the 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, 2011. 1--20. Google Scholar

[28] van de Pol J, Smart N P, Yarom Y. Just a little bit more. In: Proceedings of Cryptographers Track at the RSA Conference, San Francisco, 2015. 3--21. Google Scholar

[29] Fan S, Wang W, Cheng Q. Attacking OpenSSL implementation of ECDSA with a few signatures. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, 2016. 1505--1515. Google Scholar

[30] Genkin D, Pachmanov L, Pipman I, et al. ECDSA key extraction from mobile devices via nonintrusive physical side channels. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, 2016. 1626--1638. Google Scholar

•

Algorithm 1 Conversion to wNAF form

Require:Scalar $k$ and window size $w$;

Output:$e_0$, $e_1$, $e_2$, …, $e_{\lambda_l}$ is the wNAF form of $k$;

$i~\Leftarrow~0$;

while $k~>~0$ do

if $k~\boldsymbolod~2~=~1$ then

$e_i~=~k~\boldsymbolod~2^{w+1}$;

if $e_i~>=~2^w$ then

$e_i~\Leftarrow~e_i~-~2^{w+1}$;

end if

$k~\Leftarrow~k~-~e_i$;

else

$e_i~~\Leftarrow~0$;

end if

$k~\Leftarrow~k/2$;

$i~\Leftarrow~i+1$;

end while

• Table 1   Comparisons of the selection rules
 Selection rule Average number Lattice dimensions Signature number Signature Pr.$^{\rm~a)}$ (%) of leaked bits (in theory) (in theory) 0 3.990 67 65 100 1 4.248 63 77 79.325 2 4.800 56 110 49.400 3 4.990 54 104 50.000
•

Algorithm 2 OpenSSL implementation of $kG$ using wNAF

Require:Scalar $k$ in the wNAF form $e_0$, $e_1$, …, $e_{\lambda_l}$ and precomputed points $\{\pm{}G,~\pm{}3G,~\ldots,~\pm{}(2^w-1)G\}$;

Output:$Q~=~kG$;

$Q~\Leftarrow~0$;

for $i~=~\lambda_l,~\lambda_l-1,~\ldots,~0$

$Q~\Leftarrow~2\cdot~Q$;

if $e_i~\neq~0$ then

$Q~\Leftarrow~Q+e_{i}G$;

end if

end for

• Table 2   Experiment results$^{\rm~a)}$
 Lattice Selection Number of Reduction $p$ (%) Average noalign dimension rule signatures algorithm time (min) noalign67 0 65 BKZ-30 $\times$ $\times$ 1 82 $\times$ $\times$ 2 132 16 13.67 3 130 16.5 72 0 70 BKZ-30 $\times$ $\times$ 1 89 $\times$ $\times$ 2 142 35 20.96 3 140 30.5 77 0 75 BKZ-30 $\times$ $\times$ 1 94 0.5 35.78 2 152 36.5 3 150 42 82 0 80 BKZ-30 $\times$ $\times$ 1 101 BKZ-25 1.5 7.58 2 166 42 3 160 46.5 87 0 85 BKZ-30 1.5 26.97 1 107 BKZ-25 6 10.48 2 172 49.5 3 170 52.5 92 0 90 BKZ-25 5 15.77 1 113 25 2 182 44.5 3 180 50

a

• #### 0

Citations

• Altmetric

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有