nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

How to Manipulate Curve Standards: A White Paper for the Black Hat `http://bada55.cr.yp.to`

verfasst von : Daniel J. Bernstein, Tung Chou, Chitchanok Chuengsatiansup, Andreas Hülsing, Eran Lambooij, Tanja Lange, Ruben Niederhagen, Christine van Vredendaal

Erschienen in: Security Standardisation Research

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This paper analyzes the cost of breaking ECC under the following assumptions: (1) ECC is using a standardized elliptic curve that was actually chosen by an attacker; (2) the attacker is aware of a vulnerability in some curves that are not publicly known to be vulnerable.

This cost includes the cost of exploiting the vulnerability, but also the initial cost of computing a curve suitable for sabotaging the standard. This initial cost depends heavily upon the acceptability criteria used by the public to decide whether to allow a curve as a standard, and (in most cases) also upon the chance of a curve being vulnerable.

This paper shows the importance of accurately modeling the actual acceptability criteria: i.e., figuring out what the public can be fooled into accepting. For example, this paper shows that plausible models of the “Brainpool acceptability criteria” allow the attacker to target a one-in-a-million vulnerability and that plausible models of the “Microsoft NUMS criteria” allow the attacker to target a one-in-a-hundred-thousand vulnerability.

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

Vorheriges Kapitel Analysis of the PKCS#11 API Using the Maude-NPA Tool

Nächstes Kapitel Security of the SM2 Signature Scheme Against Generalized Key Substitution Attacks

Accredited Standards Committee X9: American national standard X9.62-1999, public key cryptography for the financial services industry: the elliptic curve digital signature algorithm (ECDSA) (1999)

Accredited Standards Committee X9: American national standard X9.63-2001, public key cryptography for the financial services industry: key agreement and key transport using elliptic curve cryptography (2001)

Agence nationale de la sécurité des systèmes d’information: Publication d’un paramétrage de courbe elliptique visant des applications de passeport électronique et de l’administration électronique française (2011)

Aumasson, J.P.: Generator of “nothing-up-my-sleeve" (NUMS) constants (2015). https://github.com/veorq/numsgen/blob/master/numsgen.py

Bach, E., Peralta, R.: Asymptotic semismoothness probabilities. Math. Comput. 65(216), 1701–1715 (1996)MathSciNetCrossRefMATH

Bernstein, D.J.: Curve25519: New Diffie-Hellman speed records. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 207–228. Springer, Heidelberg (2006) CrossRef

Bernstein, D.J., Duif, N., Lange, T., Schwabe, P., Yang, B.Y.: High-speed high-security signatures. J. Crypt. Eng. 2, 77–89 (2012)CrossRefMATH

Bernstein, D.J., Hamburg, M., Krasnova, A., Lange, T.: Elligator: elliptic-curve points indistinguishable from uniform random strings. In: Sadeghi, A., Gligor, V.D., Yung, M. (eds.) ACM CCS 2013, pp. 967–980. ACM (2013)

Bernstein, D.J., Lange, T.: SafeCurves: choosing safe curves for elliptic-curve cryptography (2015). http://safecurves.cr.yp.to. Accessed 21 May 2015

10.

Bernstein, D.J., Schwabe, P.: NEON Crypto. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol. 7428, pp. 320–339. Springer, Heidelberg (2012). http://dx.doi.org/10.1007/9783642330278 CrossRef

11.

Black, B., Bos, J.W., Costello, C., Langley, A., Longa, P., Naehrig, M.: Rigid parameter generation for elliptic curve cryptography (2015). https://tools.ietf.org/html/draft-black-rpgecc-01

12.

Black, B., Bos, J.W., Costello, C., Longa, P., Naehrig, M.: Elliptic curve cryptography (ECC) nothing up my sleeve (NUMS) curves and curve generation (2014). https://tools.ietf.org/html/draft-black-numscurves-00

13.

Bos, J.W., Costello, C., Longa, P., Naehrig, M.: Selecting elliptic curves for cryptography: an efficiency and security analysis. J. Cryptographic Eng. 1–28 (2015). doi:10.1007/s13389-015-0097-y

14.

ECC Brainpool: ECC Brainpool standard curves and curve generation (2005). http://www.ecc-brainpool.org/download/Domain-parameters.pdf

15.

Brier, E., Joye, M.: Weierstraß elliptic curves and side-channel attacks. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 335–345. Springer, Heidelberg (2002) CrossRef

16.

Certicom Research: SEC 1: Elliptic curve cryptography, version 1.0 (2000)

17.

Certicom Research: SEC 2: Recommended elliptic curve domain parameters, version 1.0 (2000)

18.

Certicom Research: SEC 1: Elliptic curve cryptography, version 2.0 (2009)

19.

Certicom Research: SEC 2: Recommended elliptic curve domain parameters, version 2.0 (2010)

20.

Checkoway, S., Fredrikson, M., Niederhagen, R., Everspaugh, A., Green, M., Lange, T., Ristenpart, T., Bernstein, D.J., Maskiewicz, J., Shacham, H.: On the practical exploitability of Dual EC in TLS implementations. In: 23rd USENIX Security Symposium (USENIX Security 2014). USENIX Association, San Diego (2014)

21.

Chou, T.: Sandy2x: fastest Curve25519 implementation ever (2015). http://csrc.nist.gov/groups/ST/ecc-workshop-2015/presentations/session6-chou-tung.pdf

22.

Costigan, N., Schwabe, P.: Fast elliptic-curve cryptography on the Cell Broadband engine. In: Preneel, B. (ed.) AFRICACRYPT 2009. LNCS, vol. 5580, pp. 368–385. Springer, Heidelberg (2009) CrossRef

23.

Düll, M., Haase, B., Hinterwälder, G., Hutter, M., Paar, C., Sánchez, A.H., Schwabe, P.: High-speed Curve25519 on 8-bit, 16-bit, and 32-bit microcontrollers. Designs, Codes and Cryptography (to appear, 2015). https://cryptojedi.org/papers/mu25519-20150417.pdf

24.

Flori, J.P., Plût, J., Reinhard, J.R., Ekerå, M.: Diversity and transparency for ECC (2015). http://csrc.nist.gov/groups/ST/ecc-workshop-2015/papers/session4-flori-jean-pierre.pdf

25.

Galbraith, S.D., McKee, J.: The probability that the number of points on an elliptic curve over a finite field is prime. J. London Math. Soc. 62, 671–684 (2000)MathSciNetCrossRefMATH

26.

Gaudry, P., Thomé, E.: The mpFq library and implementing curve-based key exchanges. In: SPEED: Software Performance Enhancement for Encryption and Decryption, pp. 49–64 (2007). http://www.loria.fr/gaudry/papers.en.html

27.

Granville, A.: Smooth Numbers: Computational Number Theory and Beyond, pp. 267–323. Cambridge University Press (2008). http://en.scientificcommons.org/43534098, http://www.math.leidenuniv.nl/ psh/ANTproc/09andrew.pdf

28.

Institute of Electrical and Electronics Engineers: IEEE 1363–2000: Standard specifications for public key cryptography (2000)

29.

Kelsey, J.: Choosing a DRBG algorithm (2003?). https://github.com/matthewdgreen/nistfoia/blob/master/6.4.2014

30.

LaMacchia, B., Costello, C.: Deterministic generation of elliptic curves (a.k.a. “NUMS" curves) (2014). https://www.ietf.org/proceedings/90/slides/slides-90-cfrg-5.pdf

31.

Langley, A., Moon, A.: Implementations of a fast elliptic-curve digital signature algorithm (2013). https://github.com/floodyberry/ed25519-donna

32.

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

33.

Lochter, M., Merkle, J., Schmidt, J.M., Schütze, T.: Requirements for standard elliptic curves (2014), position Paper of the ECC Brainpool. http://www.ecc-brainpool.org/20141001_ECCBrainpool_PositionPaper.pdf

34.

Luca, F., Mireles, D.J., Shparlinski, I.E.: MOV attack in various subgroups on elliptic curves. Illinois J. Math. 48(3), 1041–1052 (2004)MathSciNetMATH

35.

Mahé, E.M., Chauvet, J.M.: Fast GPGPU-based elliptic curve scalar multiplication (2014). https://eprint.iacr.org/2014/198.pdf

36.

Merkle, J.: Re: [Cfrg] ECC reboot (Was: When’s the decision?) (2014). https://www.ietf.org/mail-archive/web/cfrg/current/msg05353.html

37.

National Institute for Standards and Technology: FIPS PUB 186–2: Digital signature standard (2000)

38.

National Institute for Standards and Technology: FIPS PUB 186–4: Digital signature standard (DSS) (2013)

39.

National Security Agency: Suite B cryptography / cryptographic interoperability (2005). https://web.archive.org/web/20150724150910/www.nsa.gov/ia/programs/suiteb_cryptography/

40.

State Commercial Cryptography Administration (OSCCA), China: Public key cryptographic algorithm SM2 based on elliptic curves, December 2010. http://www.oscca.gov.cn/UpFile/2010122214822692.pdf

41.

State Commercial Cryptography Administration (OSCCA), China: Recommanded curve parameters for public key cryptographic algorithm SM2 based on elliptic curves, December 2010. http://www.oscca.gov.cn/UpFile/2010122214836668.pdf

42.

Rosser, J.B., Schoenfeld, L.: Approximate formulas for some functions of prime numbers. Illinois J. Math. 6, 64–94 (1962)MathSciNetMATH

43.

Sasdrich, P., Güneysu, T.: Efficient elliptic-curve cryptography using Curve25519 on reconfigurable devices. In: Goehringer, D., Santambrogio, M.D., Cardoso, J.M.P., Bertels, K. (eds.) ARC 2014. LNCS, vol. 8405, pp. 25–36. Springer, Heidelberg (2014)

44.

Scott, M.: Re: NIST announces set of Elliptic Curves (1999). https://groups.google.com/forum/message/raw?msg=sci.crypt/mFMukSsORmI/FpbHDQ6hM_MJ

45.

Silverman, J.H.: The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics, vol. 106. Springer, New York (2009) MATH

46.

Stein, W., et al.: Sage Mathematics Software (Version 6.1.1). The Sage Development Team (2014). http://www.sagemath.org

47.

Hutter, M., Schilling, J., Schwabe, P., Wieser, W.: NaCl’s crypto\(\_\)box in hardware. In: Güneysu, T., Handschuh, H. (eds.) CHES 2015. LNCS, vol. 9293, pp. 81–101. Springer, Heidelberg (2015)CrossRef

48.

Wikipedia: Nothing up my sleeve number (2015). http://www.en.wikipedia.org/wiki/Nothing_up_my_sleeve_number. Accessed 20 May 2015

Titel: How to Manipulate Curve Standards: A White Paper for the Black Hat http://bada55.cr.yp.to
verfasst von: Daniel J. Bernstein
Tung Chou
Chitchanok Chuengsatiansup
Andreas Hülsing
Eran Lambooij
Tanja Lange
Ruben Niederhagen
Christine van Vredendaal
Verlag: Springer International Publishing
Buch: Security Standardisation Research
Print ISBN: 978-3-319-27151-4

Electronic ISBN: 978-3-319-27152-1

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-27152-1_6

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"