logo

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

More info
  • ReceivedAug 25, 2016
  • AcceptedJan 21, 2017
  • PublishedAug 30, 2017

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

[21] Hlav. 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

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

京ICP备18024590号-1