nach oben

Journal of Cryptographic Engineering

Erschienen in:

01.04.2014 | CHES 2013

Using Bleichenbacher’s solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA: extended version

verfasst von: Elke De Mulder, Michael Hutter, Mark E. Marson, Peter Pearson

Erschienen in: Journal of Cryptographic Engineering | Ausgabe 1/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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 4,000 signatures.

Vorheriger Artikel Stealthy dopant-level hardware Trojans: extended version

Nächster Artikel Masking vs. multiparty computation: how large is the gap for AES?

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

\(Pr\{K_{j,hi} == \lfloor q_b\rfloor \}\) will be less than for all other values of \(K_{j,hi}\) in the interval.

We wrote Eq. (4) as an equality because the \(k_j\) can take on negative values. With this understanding, for the remainder of the paper, we will simply write ‘\(\,\mathrm{mod}\,\ {q}\)’.

We acknowledge the abuse of notation in writing \(B_q(w)\) instead of \(B_q(V_w)\), but this is consistent with Bleichenbacher’s notes and will simplify the exposition.

Throughout the paper, we will refer to the size of \(B_q(w)\), by which we mean \(|B_q(w)|\). With this understanding, for the remainder of the paper, we will leave off the absolute value bars.

Curiously, the coefficient distributions output by LLL were better modeled by geometric distributions.

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, 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)CrossRefMATHMathSciNet

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, CA (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, volume 1109 of LNCS, pp. 129–142 (1996)

D. Cadé, Pujol, X., Stehlé, D.: fplll-4.0.1 Lattice Reduction Library (2012)

Chari, S., Rao, J.R., Rohatgi, P.: Template attacks. In: Kaliski B.S. Jr., Koç, Ç.K., Paar, C. (eds.) CHES 2002, volume 2523 of LNCS, pp 13–28. Springer, New York (2002)

Chen, Y., Nguyen, P.Q.: BKZ 2.0: Better lattice security estimates. In: ASIACRYPT, volume 7073 of Lecture Notes in Computer Science, pp 1–20. Springer (2011)

10.

Hachez, G., Quisquater, J.-J.: Montgomery exponentiation with no final subtractions: improved results. In: Koç, Ç.K., Paar, C. (eds.) CHES 2000, volume 1965 of LNCS, pp. 91–100. Springer (2000)

11.

Hamburg M.: Fast and compact elliptic-curve cryptography. IACR Cryptology ePrint Archive 309 (2012)

12.

Hedabou, M., Pinel, P., Beneteau, L.: A comb method to render ECC resistant against side channel attacks. IACR Cryptology ePrint Archive 342 (2004)

13.

Howgrave-Graham, N., Smart, N.P.: Lattice attacks on digital signature schemes. Des. Codes Cryptogr. 23(3), 283–290 (August 2001)

14.

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, volume 5536 of LNCS, pp 519–534. Springer (2009)

15.

Joye, M., Tunstall, M.: Exponent recoding and regular exponentiation algorithms. In: Preneel B. (ed.) AFRICACRYPT 2009, volume 5580 of LNCS, pp 334–349 (2009)

16.

Kocher, P.C.: Timing attacks on implementations of Diffie–Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed) CRYPTO 1996, volume 1109 of LNCS, pp 104–113. Springer (1996)

17.

Kocher, P.C., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener, M.J. (ed) CRYPTO 1999, volume 1666 of LNCS, pp 388–397 (1999)

18.

Lenstra, A.K., Lenstra, H., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261, 515–534 (1982)CrossRefMATHMathSciNet

19.

Liu, M., Nguyen, P.Q.: Solving BDD by enumeration: an update. In: Dawson, E. (ed) Topics in cryptology-CT-RSA 2013, volume 7779 of LNCS, pp 293–309. Springer (2013)

20.

Lochter, M., Merkle, J.: Elliptic curve cryptography (ECC) brainpool standard curves and curve generation. RFC 5639 (Informational), March (2010)

21.

Naccache, D., Nguyen, P.Q., Tunstall, M., Whelan, C.: Experimenting with faults, lattices and the DSA. In: Vaudenay, S. (ed) PKC 2005, volume 3386 of LNCS, pp 16–28. Springer, New York (2005)

22.

National Institute of Standards and Technology (NIST). FIPS-186-2 (+Change Notice): Digital Signature Standard (DSS), January 2000. Available online at http://www.itl.nist.gov/fipspubs/

23.

Nguyen, P.Q., Shparlinski, I.: The insecurity of the digital signature algorithm with partially known nonces. J. Cryptol. 15(3), 151–176 (2002)CrossRefMATHMathSciNet

24.

Nguyen, P.Q., Shparlinski, I.: The insecurity of the elliptic curve digital signature algorithm with partially known nonces. Des. Codes Cryptogr. 30(2), 201–217 (2003)CrossRefMATHMathSciNet

25.

Quisquater, J.-J., Koene, F.: DSA security evaluation of the signature scheme and primitive. Technical report, Math RiZK, K2Crypt, February (2002)

26.

Schnorr, C.-P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66, 181–199 (1994)CrossRefMATHMathSciNet

27.

Shoup, V.: NTL: a library for doing number theory (2012)

28.

Vaudenay, S.: Evaluation report on DSA. IPA work delivery 1002 (2001)

29.

Walter, C.D.: Montgomery exponentiation needs no final subtractions. Electron. Lett. 35, 1831–1832 (1999)CrossRef

30.

Walter, C.D., Thompson, S.: Distinguishing exponent digits by observing modular subtractions. In: Naccache, D. (ed) CT-RSA 2001, volume 2020 of LNCS, pp 192–207. Springer, New York (2001)

Titel: Using Bleichenbacher’s solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA: extended version
verfasst von: Elke De Mulder
Michael Hutter
Mark E. Marson
Peter Pearson
Publikationsdatum: 01.04.2014
Verlag: Springer Berlin Heidelberg
Erschienen in: Journal of Cryptographic Engineering / Ausgabe 1/2014
Print ISSN: 2190-8508
Elektronische ISSN: 2190-8516
DOI: https://doi.org/10.1007/s13389-014-0072-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2014

On measurable side-channel leaks inside ASIC design primitives

Stealthy dopant-level hardware Trojans: extended version

Two is the fastest prime: lambda coordinates for binary elliptic curves

Introduction to the CHES 2013 special issue

Masking vs. multiparty computation: how large is the gap for AES?