Shuqin Fan
ABSTRACT
In this work, we give a lattice attack on the ECDSA implementation in the latest version of OpenSSL, which implement the scalar multiplication by windowed Non-Adjacent Form method. We propose a totally different but more efficient method of extracting and utilizing information from the side-channel results, remarkably improving the previous attacks. First, we develop a new efficient method, which can extract almost all information from the side-channel results, obtaining 105.8 bits of information per signature on average for 256-bit ECDSA. Then in order to make the utmost of our extracted information, we translate the problem of recovering secret key to the Extended Hidden Number Problem, which can be solved by lattice reduction algorithms. Finally, we introduce the methods of elimination, merging, most significant digit recovering and enumeration to improve the attack. Our attack is mounted to the {series secp256k1} curve, and the result shows that only 4 signatures would be enough to recover the secret key if the Flush+Reload attack is implemented perfectly without any error,which is much better than the best known result needing at least 13 signatures.
- The openssl project. OpenSSL -- cryptography and SSL/TLS toolkit. http://www.openssl.org.Google Scholar
- O. Aciiçmez, Ç. K. Koç, and J.-P. Seifert. On the power of simple branch prediction analysis. In Proceedings of the 2nd ACM Symposium on Information, Computer and Communications Security, ASIACCS 2007, pages 312--320, New York, NY, USA, 2007. ACM. Google ScholarDigital Library
- N. Benger, J. van de Pol, N. P. Smart, and Y. Yarom. "Ooh aahłdots, just a little bit": A small amount of side channel can go a long way. In L. Batina and M. Robshaw, editors, Cryptographic Hardware and Embedded System -- CHES 2014, volume 8731 of Lecture Notes in Computer Science, pages 75--92. Springer Berlin Heidelberg, 2014. Google ScholarDigital Library
- B. B. Brumley and R. M. Hakala. Cache-timing template attacks. In M. Matsui, editor, Advances in Cryptology -- ASIACRYPT 2009, volume 5912 of Lecture Notes in Computer Science, pages 667--684. Springer Berlin Heidelberg, 2009. Google ScholarDigital Library
- B. B. Brumley and N. Tuveri. Remote timing attacks are still practical. In V. Atluri and C. Diaz, editors, Computer Security -- ESORICS 2011: 16th European Symposium on Research in Computer Security, Leuven, Belgium, September 12--14, 2011. Proceedings, pages 355--371. Springer Berlin Heidelberg, 2011. Google ScholarDigital Library
- Y. Chen and P. Nguyen. BKZ2.0: better lattice security estimates. In Advances in Cryptology -- ASIACRYPT 2011, volume 7073 of Lecture Notes in Computer Science, pages 1--20. Springer Berlin Heidelberg, 2011. Google ScholarDigital Library
- H. Cohen, A. Miyaji, and T. Ono. Efficient elliptic curve exponentiation. In Advances in Cryptology -- Proceedings of ICICS 1997, volume 1334 of Lecture Notes in Computer Science, pages 282--290. Springer Berlin Heidelberg, 1997. Google ScholarDigital Library
- P. FIPS. 186--4 digital signature standard (DSS). National Institude of Standards and Technology (NIST), 2013.Google Scholar
- N. Gama and P. Q. Nguyen. Predicting lattice reduction. In N. Smart, editor, Advances in Cryptology -- EUROCRYPT 2008: 27th Annual International Conference on the Theory and Application of Cryptographic Techniques, Istanbul, Turkey, April 13--17, 2008. Proceedings, pages 31--51. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008. Google ScholarDigital Library
- M. Hlaváč and T. Rosa. Extended hidden problem and its cryptanalytic applications. In E. Biham and A. M. Youssef, editors, Selected areas in Cryptography, volume 4356 of Lecture Notes in Computer Science, pages 114--133. Springer Berlin Heidelberg, 2007. Google ScholarDigital Library
- A. Hollosi, G. Karlinger, T. Rossler, M. Centner, and et al. Die österreichische bürgerkarte, 2008.Google Scholar
- N. Howgrave-Grahm and N. P. Smart. Lattice attacks on digital signature schemes. Designs, Codes and Cryptography, 23:283--290, 2001. Google ScholarDigital Library
- G. Irazoqui, M. S. Inci, T. Eisenbarth, and B. Sunar. Lucky 13 strikes back. In Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security, ASIA CCS '15, pages 85--96, New York, NY, USA, 2015. ACM. Google ScholarDigital Library
- D. Johnson, A. Menezes, and S. A. Vanstone. The elliptic curve digital signature algorithm (ECDSA). International Journal of Information Security, 1:36--63, 2001. Google ScholarDigital Library
- P. C. Kocher, J. Jaff, and B. Jun. Differential power analysis. In M. Wiener, editor, Advances in Cryptology -- CRYPTO 1999, volume 1666 of Lecture Notes in Computer Science, pages 388--397. Springer Berlin Heidelberg, 1999. Google ScholarDigital Library
- K. Koyama and Y. Tsuruoka. Speeding up elliptic curve cryptosystems using a signed binary windows method. In Advances in Cryptology - CRYPTO 1992, volume 740 of Lecture Notes in Computer Science, pages 345--357. Springer Berlin Heidelberg, 1992. Google ScholarDigital Library
- A. K. Lenstra, H. W. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515--534, 1982.Google ScholarCross Ref
- M. Liu and P. Q. Nguyen. Solving BDD by enumeration: An update. In E. Dawson, editor, Topics in Cryptology -- CT-RSA 2013: The Cryptographers' Track at the RSA Conference 2013, San Francisco,CA, USA, February 25-March 1, 2013. Proceedings, volume 7779 of Lecture Notes in Computer Science, pages 293--309. Springer Berlin Heidelberg, 2013. Google ScholarDigital Library
- S. Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008.Google Scholar
- P. Q. Nguyen and I. Shparlinski. The insecurity of the digital signature algorithm with partially known nonces. Journal of Cryptology, 15:151--176, 2002. Google ScholarDigital Library
- P. Q. Nguyen and I. Shparlinski. The insecurity of the elliptic curve digital signature algorithm with partially known nonces. Designs, Codes and Cryptography, 30:201--217, 2003. Google ScholarDigital Library
- D. Page. Theoretical use of cache memory as a cryptanalytic side-channel. IACR Cryptology ePrint Archive, 2002:169, 2002.Google Scholar
- C.-P. Schnorr and M. Euchner. Lattice basis reduction: improved practical algorithms and solving subset sum problems. In Fundamentals of Computation Theory -- FCT 1991, volume 529 of Lecture Notes in Computer Science, pages 68--85. Springer Berlin Heidelberg, 1991. Google ScholarDigital Library
- J. Solinas. Efficient arithmetic on Koblitz curves. Design, Codes and Cryptography, 19(2):195--249, 2000. Google ScholarDigital Library
- E. Tromer, D. A. Osvik, and A. Shamir. Efficient cache attacks on AES, and countermeasures. Journal of Cryptology, 23(1):37--71, 2010. Google ScholarDigital Library
- J. van de Pol, N. P. Smart, and Y. Yarom. Just a little bit more. In K. Nyberg, editor, Topics in Cryptology -- CT-RSA 2015, volume 9048 of Lecture Notes in Computer Science, pages 3--21. Springer International Publishing, 2015.Google ScholarCross Ref
- S. Vanstone. Responses to NIST's proposal. Communications of the ACM, 35:50--52, 1992. Google ScholarDigital Library
- Y. Yarom and N. Benger. Recovering OpenSSL ECDSA nonces using the F\textsclushGoogle Scholar
- R\textsceload cache side-channel attack. IACR Cryptology ePrint Archive, 2014:140, 2014.Google Scholar
- Y. Yarom and K. Falkner. Flush+Reload: a high resolution, low noise, L3 cache side-channel attack. In 23rd USENIX Security Symposium (USENIX Security 2014), pages 719--732, San Diego, CA, Aug. 2014. USENIX Association. Google ScholarDigital Library
- Y. Zhang, A. Juels, M. K. Reiter, and T. Ristenpart. Cross-VM side channels and their use to extract private keys. In Proceedings of the 2012 ACM Conference on Computer and Communications Security, CCS 2012, pages 305--316, New York, NY, USA, 2012. ACM. Google ScholarDigital Library
Index Terms
- Attacking OpenSSL Implementation of ECDSA with a Few Signatures
Recommendations
LadderLeak: Breaking ECDSA with Less than One Bit of Nonce Leakage
CCS '20: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications SecurityAlthough it is one of the most popular signature schemes today, ECDSA presents a number of implementation pitfalls, in particular due to the very sensitive nature of the random value (known as the nonce) generated as part of the signing algorithm. It is ...
New ECDSA-Verifiable Multi-receiver Generalization Signcryption
HPCC '08: Proceedings of the 2008 10th IEEE International Conference on High Performance Computing and CommunicationsMulti-receiver signcryption is a new cryptographic primitive that simultaneously fulfills both the functions of signature and multi-receiver encryption. Generalized Multi-Receiver signcryption can provide authenticity or confidentiality separately under ...
Attacking ECDSA-Enabled RFID Devices
ACNS '09: Proceedings of the 7th International Conference on Applied Cryptography and Network SecurityThe elliptic curve digital signature algorithm (ECDSA) is used in many devices to provide authentication. In the last few years, more and more ECDSA implementations have been proposed that allow the integration into resource-constrained devices like ...
Comments