Curve25519

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In cryptography, Curve25519 is an elliptic curve offering 128 bits of security and designed for use with the elliptic curve Diffie–Hellman (ECDH) key agreement scheme. It is one of the fastest ECC curves and is not covered by any known patents.[1] The reference implementation is public domain software.[2]

The original Curve25519 paper defined it as a Diffie–Hellman (DH) function. Daniel J. Bernstein has since proposed that the name Curve25519 be used for the underlying curve, and the name X25519 for the DH function.[3]

Mathematical properties[edit]

The curve used is , a Montgomery curve, over the prime field defined by the prime number , and it uses the base point . This point generates a cyclic subgroup whose order is the prime and is of index . Using a prime order subgroup prevents mounting a Pohlig–Hellman algorithm attack.[4]

The protocol uses compressed elliptic point (only X coordinates), so it allows efficient use of the Montgomery ladder for ECDH, using only XZ coordinates.[5]

Curve25519 is constructed such that it avoids many potential implementation pitfalls.[6] By design, it is immune to timing attacks and it accepts any 32-byte string as a valid public key and does not require validating that a given point belongs to the curve, or is generated by the base point.

The curve is birationally equivalent to a twisted Edwards curve used in Ed25519[7][8] signature scheme.[9]

Popularity[edit]

Curve25519 was first released by Daniel J. Bernstein in 2005,[4] but interest increased considerably after 2013 when it was discovered that the NSA had potentially implemented a backdoor into Dual_EC_DRBG[10]. While not directly related,[11] suspicious aspects of the NIST's P curve constants[12] led to concerns[13] that the NSA had chosen values that gave them an advantage in breaking the encryption.[14][15]

I no longer trust the constants. I believe the NSA has manipulated them through their relationships with industry.

— Bruce Schneier, The NSA Is Breaking Most Encryption on the Internet (2013)

Since then, Curve25519 has become the de facto alternative to P-256, and is used in a wide variety of applications.[16] Starting in 2014, OpenSSH[17] defaults to Curve25519-based ECDH. Behavior for general SSH protocol is still being standardized as of 2018.[18]

In 2017, NIST announced that Curve25519 and Curve448 would be added to Special Publication 800-186, which specifies approved elliptic curves for use by the US Federal Government.[19] Both are described in RFC 7748.

In 2018, DKIM specification was amended so as to allow signatures with this algorithm.[20]

In 2018, RFC 8446 was published as the new Transport Layer Security v1.3 standard and it requires mandatory support for X25519, Ed25519 and X448, Ed448 algorithms.[21]

Libraries[edit]

Protocols[edit]

Applications[edit]

Notes[edit]

  1. ^ Starting with Windows 10 (1607), Windows Server 2016
  2. ^ a b c Via the OMEMO protocol
  3. ^ Only in "secret conversations"
  4. ^ a b c d Via the Signal Protocol
  5. ^ Only in "incognito mode"
  6. ^ Used to sign releases and packages[45][46]
  7. ^ Exclusive key exchange in OpenSSH 6.7 when compiled without OpenSSL.[47][48]

References[edit]

  1. ^ Bernstein. "Irrelevant patents on elliptic-curve cryptography". cr.yp.to. Retrieved 2016-02-08.
  2. ^ A state-of-the-art Diffie-Hellman function by Daniel J. Bernstein"My curve25519 library computes the Curve25519 function at very high speed. The library is in the public domain. "
  3. ^ "[Cfrg] 25519 naming". Retrieved 2016-02-25.
  4. ^ a b Bernstein, Daniel J. (2006). Yung, Moti; Dodis, Yevgeniy; Kiayias, Aggelos; et al. (eds.). Curve25519: New Diffie-Hellman Speed Records (PDF). Public Key Cryptography. Lecture Notes in Computer Science. 3958. New York: Springer. pp. 207–228. doi:10.1007/11745853_14. ISBN 978-3-540-33851-2. MR 2423191.
  5. ^ Lange, Tanja. "EFD / Genus-1 large-characteristic / XZ coordinates for Montgomery curves". EFD / Explicit-Formulas Database. Retrieved 8 February 2016.
  6. ^ "SafeCurves: Introduction". safecurves.cr.yp.to. Retrieved 2016-02-08.
  7. ^ Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, Bo-Yin Yang (2017-01-22). "Ed25519: high-speed high-security signatures". Retrieved 2019-11-09.CS1 maint: multiple names: authors list (link)
  8. ^ Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, Bo-Yin Yang (2011-09-26). "High-speed high-security signatures" (PDF). Retrieved 2019-11-09.CS1 maint: multiple names: authors list (link)
  9. ^ Bernstein, Daniel J.; Lange, Tanja (2007). Kurosawa, Kaoru (ed.). Faster addition and doubling on elliptic curves. Advances in cryptology—ASIACRYPT. Lecture Notes in Computer Science. 4833. Berlin: Springer. pp. 29–50. doi:10.1007/978-3-540-76900-2_3. ISBN 978-3-540-76899-9. MR 2565722.
  10. ^ Kelsey, John (May 2014). "Dual EC in X9.82 and SP 800-90" (PDF). National Institute of Standards in Technology. Retrieved December 2, 2018.
  11. ^ Green, Matthew (January 14, 2015). "A Few Thoughts on Cryptographic Engineering: The Many Flaws of Dual_EC_DRBG". blog.cryptographyengineering.com. Retrieved 2015-05-20.
  12. ^ https://safecurves.cr.yp.to/
  13. ^ Maxwell, Gregory (2013-09-08). "[tor-talk] NIST approved crypto in Tor?". Retrieved 2015-05-20.
  14. ^ "SafeCurves: Rigidity". safecurves.cr.yp.to. Retrieved 2015-05-20.
  15. ^ "The NSA Is Breaking Most Encryption on the Internet - Schneier on Security". www.schneier.com. Retrieved 2015-05-20.
  16. ^ "Things that use Curve25519". Retrieved 2015-12-23.
  17. ^ a b Adamantiadis, Aris (2013-11-03). "OpenSSH introduces curve25519-sha256@libssh.org key exchange !". libssh.org. Retrieved 2014-12-27.
  18. ^ A. Adamantiadis; libssh; S. Josefsson; SJD AB; M. Baushke; Juniper Networks, Inc. (2018-06-26). Secure Shell (SSH) Key Exchange Method using Curve25519 and Curve448. I-D draft-ietf-curdle-ssh-curves-08.
  19. ^ Computer Security Division, Information Technology Laboratory (2017-10-31). "Transition Plans for Key Establishment Schemes | CSRC". CSRC | NIST. Retrieved 2019-09-04.
  20. ^ John Levine (September 2018). A New Cryptographic Signature Method for DomainKeys Identified Mail (DKIM). IETF. doi:10.17487/RFC8463. RFC 8463.
  21. ^ E Rescorla (September 2018). The Transport Layer Security (TLS) Protocol Version 1.3. IETF. doi:10.17487/RFC8446. RFC 8446.
  22. ^ Werner Koch (15 April 2016). "Libgcrypt 1.7.0 release announcement". Retrieved 22 April 2016.
  23. ^ a b c d e f g SSH implementation comparison. "Comparison of key exchange methods". Retrieved 2016-02-25.
  24. ^ "Introduction". yp.to. Retrieved 11 December 2014.
  25. ^ "nettle: curve25519.h File Reference - doxygen documentation | Fossies Dox". fossies.org. Archived from the original on 2015-05-20. Retrieved 2015-05-19.
  26. ^ Limited, ARM. "PolarSSL 1.3.3 released - Tech Updates - mbed TLS (Previously PolarSSL)". tls.mbed.org. Retrieved 2015-05-19.
  27. ^ "wolfSSL Embedded SSL/TLS Library - wolfSSL Products".
  28. ^ "Botan: src/lib/pubkey/curve25519/curve25519.cpp Source File". botan.randombit.net.
  29. ^ Justinha. "TLS (Schannel SSP)". docs.microsoft.com. Retrieved 2017-09-15.
  30. ^ Denis, Frank. "Introduction · libsodium". libsodium.org.
  31. ^ Inc., OpenSSL Foundation,. "OpenSSL". www.openssl.org. Retrieved 2016-06-24.CS1 maint: extra punctuation (link)
  32. ^ "Add support for ECDHE with X25519. · openbsd/src@0ad90c3". GitHub.
  33. ^ "Tclers Wiki - NaCl for Tcl".
  34. ^ "NSS 3.28 release notes". Retrieved 25 July 2017.
  35. ^ Straub, Andreas (25 October 2015). "OMEMO Encryption". conversations.im.
  36. ^ "Cryptocat - Security". crypto.cat. Archived from the original on 2016-04-07. Retrieved 2016-05-24.
  37. ^ Frank Denis. "DNSCrypt version 2 protocol specification". Archived from the original on 2015-08-13. Retrieved 2016-03-03.
  38. ^ Matt Johnston. "Dropbear SSH - Changes". Retrieved 2016-02-25.
  39. ^ Bahtiar Gadimov; et al. "Gajim plugin for OMEMO Multi-End Message and Object Encryption". Retrieved 2016-10-01.
  40. ^ "GNUnet 0.10.0". gnunet.org. Retrieved 11 December 2014.
  41. ^ zzz (2014-09-20). "0.9.15 Release - Blog". Retrieved 20 December 2014.
  42. ^ https://github.com/ipfs/go-ipfs/blob/master/core/commands/keystore.go#L68
  43. ^ "iOS Security Guide" (PDF).
  44. ^ "MRL-0003 - Monero is Not That Mysterious" (PDF). getmonero.com.
  45. ^ Murenin, Constantine A. (2014-01-19). Soulskill (ed.). "OpenBSD Moving Towards Signed Packages — Based On D. J. Bernstein Crypto". Slashdot. Retrieved 2014-12-27.
  46. ^ Murenin, Constantine A. (2014-05-01). timothy (ed.). "OpenBSD 5.5 Released". Slashdot. Retrieved 2014-12-27.
  47. ^ Friedl, Markus (2014-04-29). "ssh/kex.c#kexalgs". BSD Cross Reference, OpenBSD src/usr.bin/. Retrieved 2014-12-27.
  48. ^ Murenin, Constantine A. (2014-04-30). Soulskill (ed.). "OpenSSH No Longer Has To Depend On OpenSSL". Slashdot. Retrieved 2014-12-26.
  49. ^ "How does Peerio implement end-to-end encryption?". Peerio.
  50. ^ "PuTTY Change Log". www.chiark.greenend.org.uk.
  51. ^ "Threema Cryptography Whitepaper" (PDF).
  52. ^ Roger Dingledine & Nick Mathewson. "Tor's Protocol Specifications - Blog". Retrieved 20 December 2014.
  53. ^ "Viber Encryption Overview". Viber. 3 May 2016. Retrieved 24 September 2016.
  54. ^ Nidhi Rastogi, James Hendler (2017-01-24). "WhatsApp security and role of metadata in preserving privacy" (PDF). Retrieved 2019-11-09.

External links[edit]