Curve25519

From HandWiki
Short description: Elliptic curve used in Internet cryptography

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

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.[4]

Mathematical properties

The curve used is [math]\displaystyle{ y^2 = x^3 + 486662x^2 + x }[/math], a Montgomery curve, over the prime field defined by the prime number [math]\displaystyle{ 2^{255} - 19 }[/math] (hence the numeric "25519" in the name), and it uses the base point [math]\displaystyle{ x = 9 }[/math]. This point generates a cyclic subgroup whose order is the prime [math]\displaystyle{ 2^{252} + 27742317777372353535851937790883648493 }[/math]. This subgroup has a co-factor of [math]\displaystyle{ 8 }[/math], meaning the number of elements in the subgroup is [math]\displaystyle{ 1/8 }[/math] that of the elliptic curve group. Using a prime order subgroup prevents mounting a Pohlig–Hellman algorithm attack.[5]

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

Curve25519 is constructed such that it avoids many potential implementation pitfalls.[7]

By design, Curve25519 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.[citation needed]

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

History

In 2005, Curve25519 was first released by Daniel J. Bernstein.[5]

In 2013, interest began to increase considerably when it was discovered that the NSA had potentially implemented a backdoor into the P-256 curve based Dual EC DRBG algorithm.[11] While not directly related,[12] suspicious aspects of the NIST's P curve constants[13] led to concerns[14] that the NSA had chosen values that gave them an advantage in breaking the encryption.[15][16]

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

Since 2013, Curve25519 has become the de facto alternative to P-256, being used in a wide variety of applications.[17] Starting in 2014, OpenSSH[18] defaults to Curve25519-based ECDH and GnuPG adds support for Ed25519 keys for signing and encryption.[19] Behavior for general SSH protocol is still being standardized as of 2018.[20][needs update]

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.[21] Both are described in RFC 7748.[22] A 2019 draft of "FIPS 186-5" notes the intention to allow usage of Ed25519[23] for digital signatures. A 2019 draft of Special Publication 800-186 notes the intention to allow usage of Curve25519.[24]

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

Also in 2018, RFC 8446 was published as the new Transport Layer Security v1.3 standard. It recommends support for X25519, Ed25519, X448, and Ed448 algorithms.[26]

Libraries


Protocols

Applications


Notes

  1. Starting with Windows 10 (1607), Windows Server 2016
  2. 2.0 2.1 2.2 Via the OMEMO protocol
  3. Only in "secret conversations"
  4. 4.0 4.1 4.2 4.3 Via the Signal Protocol
  5. Only in "incognito mode"
  6. Used to sign releases and packages[51][52]
  7. Exclusive key exchange in OpenSSH 6.7 when compiled without OpenSSL.[53][54]

References

  1. Bernstein. "Irrelevant patents on elliptic-curve cryptography". https://cr.yp.to/ecdh/patents.html. 
  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. "X25519". 5 March 2019. https://www.cryptopp.com/wiki/X25519. 
  4. "[Cfrg 25519 naming"]. https://www.ietf.org/mail-archive/web/cfrg/current/msg04996.html. 
  5. 5.0 5.1 Bernstein, Daniel J. (2006). "Public Key Cryptography - PKC 2006". in Yung, Moti; Dodis, Yevgeniy; Kiayias, Aggelos et al.. Public Key Cryptography. 3958. New York: Springer. pp. 207–228. doi:10.1007/11745853_14. ISBN 978-3-540-33851-2. 
  6. Lange, Tanja. "EFD / Genus-1 large-characteristic / XZ coordinates for Montgomery curves". https://www.hyperelliptic.org/EFD/g1p/auto-montgom-xz.html. 
  7. Bernstein, Daniel J.; Lange, Tanja (2017-01-22). "SafeCurves: Introduction". SafeCurves: choosing safe curves for elliptic-curve cryptography. https://safecurves.cr.yp.to. 
  8. Bernstein, Daniel J.; Duif, Niels; Lange, Tanja; Schwabe, Peter; Yang, Bo-Yin (2017-01-22). "Ed25519: high-speed high-security signatures". http://ed25519.cr.yp.to/. 
  9. Bernstein, Daniel J.; Duif, Niels; Lange, Tanja; Schwabe, Peter; Yang, Bo-Yin (2011-09-26). "High-speed high-security signatures". http://ed25519.cr.yp.to/ed25519-20110926.pdf. 
  10. Bernstein, Daniel J.; Lange, Tanja (2007). "Advances in Cryptology – ASIACRYPT 2007". in Kurosawa, Kaoru. Advances in cryptology—ASIACRYPT. 4833. Berlin: Springer. pp. 29–50. doi:10.1007/978-3-540-76900-2_3. ISBN 978-3-540-76899-9. 
  11. Kelsey, John (May 2014). "Dual EC in X9.82 and SP 800-90". https://csrc.nist.gov/csrc/media/projects/crypto-standards-development-process/documents/dualec_in_x982_and_sp800-90.pdf. 
  12. Green, Matthew (2015-01-14). "A Few Thoughts on Cryptographic Engineering: The Many Flaws of Dual_EC_DRBG". http://blog.cryptographyengineering.com/2013/09/the-many-flaws-of-dualecdrbg.html. 
  13. "SafeCurves: Introduction". https://safecurves.cr.yp.to/. 
  14. Maxwell, Gregory (2013-09-08). "[tor-talk NIST approved crypto in Tor?"]. https://lists.torproject.org/pipermail/tor-talk/2013-September/029956.html. 
  15. "SafeCurves: Rigidity". https://safecurves.cr.yp.to/rigid.html. 
  16. "The NSA Is Breaking Most Encryption on the Internet - Schneier on Security". https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html#c1675929. 
  17. "Things that use Curve25519". https://ianix.com/pub/curve25519-deployment.html. 
  18. 18.0 18.1 Adamantiadis, Aris (2013-11-03). "OpenSSH introduces curve25519-sha256@libssh.org key exchange !". libssh.org. https://www.libssh.org/2013/11/03/openssh-introduces-curve25519-sha256libssh-org-key-exchange/. 
  19. "GnuPG - What's new in 2.1". August 2021. https://gnupg.org/faq/whats-new-in-2.1.html. 
  20. 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, https://tools.ietf.org/html/draft-ietf-curdle-ssh-curves-08 
  21. "Transition Plans for Key Establishment Schemes" (in EN-US). 2017-10-31. https://csrc.nist.gov/News/2017/Transition-Plans-for-Key-Establishment-Schemes. 
  22. RFC 7748. Retrieved from rfc:7748.
  23. Regenscheid, Andrew (31 October 2019). FIPS PUB 186-5. doi:10.6028/NIST.FIPS.186-5-draft. https://csrc.nist.gov/publications/detail/fips/186/5/draft. 
  24. "Recommendations for Discrete Logarithm-Based Cryptography". https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186-draft.pdf. 
  25. John Levine (September 2018), A New Cryptographic Signature Method for DomainKeys Identified Mail (DKIM), IETF, doi:10.17487/RFC8463, RFC 8463, https://tools.ietf.org/html/rfc8463 
  26. E Rescorla (September 2018), The Transport Layer Security (TLS) Protocol Version 1.3, IETF, doi:10.17487/RFC8446, RFC 8446, https://tools.ietf.org/html/rfc8446 
  27. Werner Koch (15 April 2016). "Libgcrypt 1.7.0 release announcement". https://lists.gnupg.org/pipermail/gnupg-announce/2016q2/000386.html. 
  28. 28.0 28.1 28.2 28.3 28.4 28.5 28.6 SSH implementation comparison. "Comparison of key exchange methods". http://ssh-comparison.quendi.de/comparison/kex.html. 
  29. "Introduction". yp.to. https://nacl.cr.yp.to/. 
  30. "nettle: curve25519.h File Reference". http://fossies.org/dox/nettle-3.1.1/curve25519_8h.html. 
  31. Limited, ARM. "PolarSSL 1.3.3 released - Tech Updates - mbed TLS (Previously PolarSSL)". https://tls.mbed.org/tech-updates/releases/polarssl-1.3.3-released. 
  32. "wolfSSL Embedded SSL/TLS Library | Products – wolfSSL". https://www.wolfssl.com/products/wolfssl/. 
  33. "Botan: src/lib/pubkey/curve25519/curve25519.cpp Source File". http://botan.randombit.net/doxygen/curve25519_8cpp_source.html. 
  34. Justinha. "TLS (Schannel SSP)" (in en-us). https://docs.microsoft.com/en-us/windows-server/security/tls/tls-schannel-ssp-changes-in-windows-10-and-windows-server. 
  35. Denis, Frank. "Introduction · libsodium". https://libsodium.org. 
  36. "OpenSSL 1.1.0 Series Release Notes". https://www.openssl.org/news/openssl-1.1.0-notes.html. 
  37. "Add support for ECDHE with X25519. · openbsd/src@0ad90c3". https://github.com/openbsd/src/commit/0ad90c3e6b15b9b6b8463a8a0f87d70c83a07ef4. 
  38. "NSS 3.28 release notes". https://developer.mozilla.org/en-US/docs/Mozilla/Projects/NSS/NSS_3.28_release_notes. 
  39. "A pure-Rust implementation of group operations on ristretto255 and Curve25519". https://github.com/dalek-cryptography/curve25519-dalek/. 
  40. "Ed25519.java". 13 October 2021. https://github.com/bcgit/bc-java/blob/bc3b92f1f0e78b82e2584c5fb4b226a13e7f8b3b/core/src/main/java/org/bouncycastle/math/ec/rfc8032/Ed25519.java. 
  41. Straub, Andreas (25 October 2015). "OMEMO Encryption". https://conversations.im/xeps/multi-end.html#usecases-setup. 
  42. "Cryptocat - Security". https://crypto.cat/security.html#encryption. 
  43. Frank Denis. "DNSCrypt version 2 protocol specification". https://github.com/jedisct1/dnscrypt-proxy/blob/master/DNSCRYPT-V2-PROTOCOL.txt/. 
  44. Matt Johnston. "Dropbear SSH - Changes". https://matt.ucc.asn.au/dropbear/CHANGES. 
  45. Bahtiar Gadimov. "Gajim plugin for OMEMO Multi-End Message and Object Encryption". https://github.com/omemo/gajim-omemo. 
  46. "GNUnet 0.10.0". gnunet.org. https://gnunet.org/gnunet0-10-0. 
  47. zzz (2014-09-20). "0.9.15 Release - Blog". https://geti2p.net/en/blog/post/2014/09/20/0.9.15-Release. 
  48. "go-ipfs_keystore.go at master". Github.com. 30 March 2022. https://github.com/ipfs/go-ipfs/blob/master/core/commands/keystore.go#L68. 
  49. "Apple Platform Security". https://support.apple.com/guide/security/welcome/web. 
  50. "MRL-0003 - Monero is Not That Mysterious". https://lab.getmonero.org/pubs/MRL-0003.pdf. 
  51. Murenin, Constantine A. (2014-01-19). "OpenBSD Moving Towards Signed Packages — Based On D. J. Bernstein Crypto". in Soulskill. Slashdot. http://bsd.slashdot.org/story/14/01/19/0124202/openbsd-moving-towards-signed-packages-based-on-d-j-bernstein-crypto. 
  52. Murenin, Constantine A. (2014-05-01). "OpenBSD 5.5 Released". in timothy. Slashdot. http://bsd.slashdot.org/story/14/05/01/1656209/openbsd-55-released. 
  53. Friedl, Markus (2014-04-29). "ssh/kex.c#kexalgs". http://bxr.su/OpenBSD/usr.bin/ssh/kex.c#kexalgs. 
  54. Murenin, Constantine A. (2014-04-30). "OpenSSH No Longer Has To Depend On OpenSSL". in Soulskill. Slashdot. http://it.slashdot.org/story/14/04/30/1822209/openssh-no-longer-has-to-depend-on-openssl. 
  55. "How does Peerio implement end-to-end encryption?". https://peerio.zendesk.com/hc/en-us/articles/204155895-How-does-Peerio-implement-end-to-end-encryption. 
  56. "Proton Mail now offers elliptic curve cryptography for advanced security and faster speeds". 25 April 2019. https://proton.me/blog/elliptic-curve-cryptography. 
  57. "PuTTY Change Log". http://www.chiark.greenend.org.uk/~sgtatham/putty/changes.html. 
  58. Steve Gibson (December 2019). "SQRL Cryptography whitepaper". https://www.grc.com/sqrl/SQRL_Cryptography.pdf. 
  59. "Threema Cryptography Whitepaper". https://threema.ch/press-files/cryptography_whitepaper.pdf. 
  60. Roger Dingledine & Nick Mathewson. "Tor's Protocol Specifications - Blog". https://gitweb.torproject.org/torspec.git/tree/tor-spec.txt?id=b5b771b19df9fc052b424228045409467a7b6414#n81. 
  61. "Viber Encryption Overview". Viber. 3 May 2016. https://www.viber.com/en/security-overview. 
  62. Nidhi Rastogi; James Hendler (2017-01-24). "WhatsApp security and role of metadata in preserving privacy". arXiv:1701.06817 [cs.CR].

External links