Abstract
In this paper we describe an attack against nonce leaks in 384-bit ECDSA using an FFT-based attack due to Bleichenbacher. The signatures were computed by a modern smart card. We extracted the low-order bits of each nonce using a template-based power analysis attack against the modular inversion of the nonce. We also developed a BKZ-based method for the range reduction phase of the attack, as it was impractical to collect enough signatures for the collision searches originally used by Bleichenbacher. We confirmed our attack by extracting the entire signing key using a 5-bit nonce leak from 4000 signatures.
Chapter PDF
Similar content being viewed by others
References
Minutes from the IEEE P1363 Working Group for Public-Key Cryptography Standards (November 15, 2000)
ANSI X9.62:2005: Public Key Cryptography for the Financial Services Industry. In: The Elliptic Curve Digital Signature Algorithm, ECDSA (2005)
Babai, L.: On Lovász’ Lattice Reduction and the Nearest Lattice Point Problem. Combinatorica 6(1), 1–13 (1986)
Bleichenbacher, D.: On The Generation of One-Time Keys in DL Signature Schemes. Presentation at IEEE P1363 Working Group meeting (November 2000)
Bleichenbacher, D.: On the Generation of DSA One-Time Keys. Presentation at Cryptography Research, Inc., San Francisco (2007)
Boneh, D., Venkatesan, R.: Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 129–142. Springer, Heidelberg (1996)
Cadé, D., Pujol, X., Stehlé, D.: fplll-4.0.1 Lattice Reduction Library (2012)
Chari, S., Rao, J.R., Rohatgi, P.: Template Attacks. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 13–28. Springer, Heidelberg (2003)
Chen, Y., Nguyen, P.Q.: BKZ 2.0: Better Lattice Security Estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 1–20. Springer, Heidelberg (2011)
Hachez, G., Quisquater, J.-J.: Montgomery Exponentiation with no Final Subtractions: Improved Results. In: Paar, C., Koç, Ç.K. (eds.) CHES 2000. LNCS, vol. 1965, pp. 293–301. Springer, Heidelberg (2000)
Hamburg, M.: Fast and Compact Elliptic-Curve Cryptography. IACR Cryptology ePrint Archive, 309 (2012)
Hedabou, M., Pinel, P., Bènèteau, L.: A Comb Method to Render ECC Resistant Against Side Channel Attacks. IACR Cryptology ePrint Archive, 342 (2004)
Howgrave-Graham, N., Smart, N.P.: Lattice Attacks on Digital Signature Schemes. Designs, Codes and Cryptography 23(3), 283–290 (2001)
Hutter, M., Medwed, M., Hein, D., Wolkerstorfer, J.: Attacking ECDSA-Enabled RFID Devices. In: Abdalla, M., Pointcheval, D., Fouque, P.-A., Vergnaud, D. (eds.) ACNS 2009. LNCS, vol. 5536, pp. 519–534. Springer, Heidelberg (2009)
Joye, M., Tunstall, M.: Exponent Recoding and Regular Exponentiation Algorithms. In: Preneel, B. (ed.) AFRICACRYPT 2009. LNCS, vol. 5580, pp. 334–349. Springer, Heidelberg (2009)
Kocher, P.C.: Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996)
Kocher, P.C., Jaffe, J., Jun, B.: Differential Power Analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999)
Lenstra, A.K., Lenstra, H., Lovász, L.: Factoring Polynomials with Rational Coefficients. Mathematische Annalen 261, 515–534 (1982)
Liu, M., Nguyen, P.Q.: Solving BDD by Enumeration: An Update. In: Dawson, E. (ed.) CT-RSA 2013. LNCS, vol. 7779, pp. 293–309. Springer, Heidelberg (2013)
Lochter, M., Merkle, J.: Elliptic Curve Cryptography (ECC) Brainpool Standard Curves and Curve Generation. In: RFC 5639 (Informational) (March 2010)
Naccache, D., Nguyen, P.Q., Tunstall, M., Whelan, C.: Experimenting with Faults, Lattices and the DSA. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 16–28. Springer, Heidelberg (2005)
National Institute of Standards and Technology (NIST). FIPS-186-2 (+Change Notice): Digital Signature Standard (DSS) (January 2000), http://www.itl.nist.gov/fipspubs/
Nguyen, P.Q., Shparlinski, I.: The Insecurity of the Digital Signature Algorithm with Partially Known Nonces. J. Cryptology 15(3), 151–176 (2002)
Nguyen, P.Q., Shparlinski, I.: The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces. Des. Codes Cryptography 30(2), 201–217 (2003)
Quisquater, J.-J., Koeune, F.: DSA Security Evaluation of the Signature Scheme and Primitive. Technical report, Math RiZK, K2Crypt (February 2002)
Schnorr, C.-P., Euchner, M.: Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems. Mathematical Programming 66, 181–199 (1994)
Shoup, V.: NTL: A Library for doing Number Theory (2012)
Vaudenay, S.: Evaluation Report on DSA. IPA Work Delivery 1002 (2001)
Walter, C.D.: Montgomery Exponentiation needs no Final Subtractions. Electronics Letters 35, 1831–1832 (1999)
Walter, C.D., Thompson, S.: Distinguishing Exponent Digits by Observing Modular Subtractions. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 192–207. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 International Association for Cryptologic Research
About this paper
Cite this paper
De Mulder, E., Hutter, M., Marson, M.E., Pearson, P. (2013). Using Bleichenbacher”s Solution to the Hidden Number Problem to Attack Nonce Leaks in 384-Bit ECDSA. In: Bertoni, G., Coron, JS. (eds) Cryptographic Hardware and Embedded Systems - CHES 2013. CHES 2013. Lecture Notes in Computer Science, vol 8086. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40349-1_25
Download citation
DOI: https://doi.org/10.1007/978-3-642-40349-1_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40348-4
Online ISBN: 978-3-642-40349-1
eBook Packages: Computer ScienceComputer Science (R0)