SpringerLink
Log in

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

  • Conference paper
  • First Online:
Security Standardisation Research (SSR 2015)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 9497))

Included in the following conference series:

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.

This work was supported by the European Commission under contracts INFSO-ICT-284833 (PUFFIN) and H2020-ICT-645421 (ECRYPT-CSA), by the Netherlands Organisation for Scientific Research (NWO) under grant 639.073.005, and by the U.S. National Science Foundation under grant 1018836. “Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.” Calculations were carried out on two GPU clusters: the Saber cluster at Technische Universiteit Eindhoven; and the K10 cluster at the University of Haifa, funded by ISF grant 1910/12. Permanent ID of this document: bada55ecd325c5bfeaf442a8fd008c54. Date: 2015.09.25. See web site: bada55.cr.yp.to .

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. 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)

    Google Scholar 

  2. 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)

    Google Scholar 

  3. 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)

    Google Scholar 

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

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

    Article  MathSciNet  MATH  Google Scholar 

  6. 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)

    Chapter  Google Scholar 

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

    Article  MATH  Google Scholar 

  8. 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)

    Google Scholar 

  9. 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

    Chapter  Google Scholar 

  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)

    Chapter  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  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)

    Google Scholar 

  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)

    Chapter  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Google Scholar 

  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)

    Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  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)

    Google Scholar 

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

    Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  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)

    Google Scholar 

  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  Google Scholar 

  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)

    Chapter  Google Scholar 

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

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, P.O. Box 513, 5600 MB, Eindhoven, Netherlands

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

  2. Department of Computer Science, University of Illinois at Chicago, Chicago, IL, 60607–7045, USA

    Daniel J. Bernstein

Authors
  1. Daniel J. Bernstein
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tung Chou
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Chitchanok Chuengsatiansup
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Andreas Hülsing
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Eran Lambooij
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Tanja Lange
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Ruben Niederhagen
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Christine van Vredendaal
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Daniel J. Bernstein , Tung Chou , Chitchanok Chuengsatiansup , Andreas Hülsing , Eran Lambooij , Tanja Lange , Ruben Niederhagen or Christine van Vredendaal .

Editor information

Editors and Affiliations

  1. Hewlett Packard Laboratories, Bristol, United Kingdom

    Liqun Chen

  2. NICT, Tokyo, Japan

    Shin'ichiro Matsuo

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Bernstein, D.J. et al. (2015). How to Manipulate Curve Standards: A White Paper for the Black Hat http://bada55.cr.yp.to . In: Chen, L., Matsuo, S. (eds) Security Standardisation Research. SSR 2015. Lecture Notes in Computer Science(), vol 9497. Springer, Cham. https://doi.org/10.1007/978-3-319-27152-1_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-27152-1_6

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-27151-4

  • Online ISBN: 978-3-319-27152-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation