idnits 2.17.1 draft-ietf-tls-curve25519-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- -- The draft header indicates that this document updates RFC4492, but the abstract doesn't seem to directly say this. It does mention RFC4492 though, so this could be OK. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year (Using the creation date from RFC4492, updated by this document, for RFC5378 checks: 1998-03-18) -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (June 9, 2015) is 3237 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- ** Obsolete normative reference: RFC 4492 (Obsoleted by RFC 8422) ** Obsolete normative reference: RFC 5246 (Obsoleted by RFC 8446) ** Obsolete normative reference: RFC 6347 (Obsoleted by RFC 9147) == Outdated reference: A later version (-11) exists of draft-irtf-cfrg-curves-01 Summary: 3 errors (**), 0 flaws (~~), 2 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group S. Josefsson 3 Internet-Draft SJD AB 4 Updates: 4492, 5246 (if approved) M. Pegourie-Gonnard 5 Intended status: Informational Independent / PolarSSL 6 Expires: December 11, 2015 June 9, 2015 8 Curve25519 for ephemeral key exchange in Transport Layer Security (TLS) 9 draft-ietf-tls-curve25519-00 11 Abstract 13 This document specifies the use of Curve25519 for ephemeral key 14 exchange in the Transport Layer Security (TLS) protocol, as well as 15 its DTLS variant. It updates RFC 5246 (TLS 1.2) and RFC 4492 16 (Elliptic Curve Cryptography for TLS). 18 Status of This Memo 20 This Internet-Draft is submitted in full conformance with the 21 provisions of BCP 78 and BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF). Note that other groups may also distribute 25 working documents as Internet-Drafts. The list of current Internet- 26 Drafts is at http://datatracker.ietf.org/drafts/current/. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 This Internet-Draft will expire on December 11, 2015. 35 Copyright Notice 37 Copyright (c) 2015 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (http://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. Code Components extracted from this document must 46 include Simplified BSD License text as described in Section 4.e of 47 the Trust Legal Provisions and are provided without warranty as 48 described in the Simplified BSD License. 50 1. Introduction 52 In [Curve25519] [I-D.irtf-cfrg-curves], a new elliptic curve function 53 for use in cryptographic applications was specified. Curve25519 is a 54 Diffie-Hellman function designed with performance and security in 55 mind. 57 [RFC4492] defines the usage of elliptic curves for authentication and 58 key agreement in TLS 1.0 and TLS 1.1, and these mechanisms are also 59 applicable to TLS 1.2 [RFC5246]. The use of ECC curves for key 60 exchange requires the definition and assignment of additional 61 NamedCurve IDs. This document specify that value for Curve25519, as 62 well as the minor changes in key selection and representation that 63 are required to accommodate for Curve25519's slightly different 64 nature. 66 This document only describes usage of Curve25519 for ephemeral key 67 exchange (ECDHE). It does not define its use for signature, since 68 the primitive considered here is a Diffie-Hellman function; the 69 related signature scheme, Ed25519, is outside the scope of this 70 document. The use of Curve25519 with long-term keys embedded in 71 X.509 certificates is also out of scope here. 73 1.1. Requirements Terminology 75 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 76 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 77 document are to be interpreted as described in [RFC2119]. 79 2. Data Structures and Computations 81 2.1. Cryptographic computations 83 All cryptographic computations are done using the Curve25519 function 84 defined in [Curve25519] [I-D.irtf-cfrg-curves]. In this memo, this 85 function is considered as a black box that takes as input a (secret 86 key, public key) pair and outputs a public key. Public keys are 87 defined as strings of 32 bytes. Secret keys are defined as 255 bits 88 numbers such as the high-order bit (bit 254) is set, and the three 89 lowest-order bits are unset. In addition, a common public key, 90 denoted by G, is shared by all users. 92 An ECDHE key exchange using Curve25519 goes as follows. Each party 93 picks a secret key d uniformly at random and computes the 94 corresponding public key x = Curve25519(d, G). Parties exchange 95 their public keys (see Section 2.3) and compute a shared secret as 96 x_S = Curve25519(d, x_peer). This shared secret is used directly as 97 the premaster secret, which is always exactly 32 bytes when ECDHE 98 with Curve25519 is used. 100 A complete description of the Curve25519 function, as well as a few 101 implementation notes, are provided in Appendix A. 103 2.2. Curve negotiation and new NamedCurve value 105 Curve negotiation uses the mechanisms introduced by [RFC4492], 106 without modification except the following restriction: in the 107 ECParameters structure, only the named_curve case can be used with 108 Curve25519. Accordingly, arbitrary_explicit_prime_curves in the 109 Supported Curves extension does not imply support for Curve25519, 110 even though the Curve25519 function happens to be defined using an 111 elliptic curve over a prime field. 113 The reason for this restriction is that explicit_prime is only suited 114 to the so-called Short Weierstrass representation of elliptic curves, 115 while Curve25519 uses a different representation for performance and 116 security reasons. 118 This document adds a new NamedCurve value for Curve25519 as follows. 120 enum { 121 Curve25519(TBD1), 122 } NamedCurve; 124 Curve25519 is suitable for use with DTLS [RFC6347]. 126 Since Curve25519 is not designed to be used in signatures, clients 127 who offer ECDHE_ECDSA ciphersuites and advertise support for 128 Curve25519 in the elliptic_curves ClientHello extension SHOULD also 129 advertise support for at least one curve suitable for ECDSA. Servers 130 MUST NOT select an ECDHE_ECDSA ciphersuite if there are no common 131 curves suitable for ECDSA. 133 2.3. Public Key representation and new ECPointFormat value 135 This section defines a new point format suitable to encode Curve25519 136 public keys, as well as an identifier to negotiate this new format in 137 TLS, and includes guidance on their use. 139 The curves defined in [RFC4492] define a public key as a point on the 140 curve. In order to exchange public keys, the points are serialized 141 as a string of bytes using one of the formats defined in [SEC1]. 142 These encodings begin with a leading byte identifying the format, 143 followed by a string of bytes, whose length is uniquely determined by 144 the leading byte and curve used. 146 Since Curve25519 public keys already are string of bytes, no 147 serialization is needed. However, a leading byte with value 0x41 is 148 prepended to the public key to identify the format. The goal, 149 besides consistency with the SEC1 formats, is to allow using other 150 formats with Curve25519 in the future if needed. 152 In order to negotiate this format in TLS, a new ECPointFormat is 153 defined as follows. 155 enum { 156 montgomery_x_le(TBD2), 157 } ECPointFormat; 159 This format is currently the only format defined for use with 160 Curve25519. Clients offering Curve25519 in the Supported Elliptic 161 Curves extension MUST also offer montgomery_x_le in the Supported 162 Point Format extension. Servers selecting Curve25519 for key 163 exchange MUST include montgomery_x_le in their Supported Point Format 164 extension. Servers willing to use Curve25519 MUST NOT assume that 165 the client supports the montgomery_x_le format if the client did not 166 advertise it explicitly. 168 When included in a ServerKeyExchange or ClientKeyExchange message, 169 the public key is wrapped in an ECPoint structure as defined in 170 [RFC4492], whose payload is as described above. For example, a 171 public key with value 2A ... 2A appears on the wire as follows 172 (including the length byte of ECPoint.point). 174 21 41 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 175 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 177 2.4. Public key validation 179 With the curves defined by [RFC4492], each party must validate the 180 public key sent by its peer before performing cryptographic 181 computations with it. Failing to do so allows attackers to gain 182 information about the private key, to the point that they may recover 183 the entire private key in a few requests, if that key is not really 184 ephemeral. 186 Curve25519 was designed in a way that the result of Curve25519(x, d) 187 will never reveal information about d, provided it was chosen as 188 prescribed, for any value of x. 190 Let's define legitimate values of x as the values that can be 191 obtained as x = Curve25519(G, d') for some d, and call the other 192 values illegitimate. The definition of the Curve25519 function shows 193 that legitimate values all share the following property: the high- 194 order bit of the last byte is not set. 196 Since there are some implementation of the Curve25519 function that 197 impose this restriction on their input and others that don't, 198 implementations of Curve25519 in TLS SHOULD reject public keys when 199 the high-order bit of the last byte is set (in other words, when the 200 value of the leftmost byte is greater than 0x7F) in order to prevent 201 implementation fingerprinting. 203 Other than this recommended check, implementations do not need to 204 ensure that the public keys they receive are legitimate: this is not 205 necessary for security with Curve25519. 207 3. IANA Considerations 209 IANA is requested to assign numbers for Curve25519 listed in 210 Section 2.2 to the Transport Layer Security (TLS) Parameters registry 211 EC Named Curve [IANA-TLS] as follows. 213 +-------+-------------+---------+-----------+ 214 | Value | Description | DTLS-OK | Reference | 215 +-------+-------------+---------+-----------+ 216 | TBD1 | Curve25519 | Y | This doc | 217 +-------+-------------+---------+-----------+ 219 IANA is also requested to assign numbers for Curve25519 listed in 220 Section 2.3 to the Transport Layer Security (TLS) Parameters registry 221 EC Point Format [IANA-TLS] as follows. 223 +-------+-----------------+---------+-----------+ 224 | Value | Description | DTLS-OK | Reference | 225 +-------+-----------------+---------+-----------+ 226 | TBD2 | montgomery_x_le | Y | This doc | 227 +-------+-----------------+---------+-----------+ 229 4. Security Considerations 231 The security considerations of [RFC5246] and most of the security 232 considerations of [RFC4492] apply accordingly. 234 Curve25519 is designed to facilitate the production of high- 235 performance constant-time implementations of the Curve25519 function. 236 Implementors are encouraged to use a constant-time implementation of 237 the Curve25519 function. This point is of crucial importance if the 238 implementation chooses to reuse its supposedly ephemeral key pair for 239 many key exchanges, which some implementations do in order to improve 240 performance. 242 Curve25519 is believed to be at least as secure as the secp256r1 243 curve defined in [RFC4492], also know as NIST P-256. While the NIST 244 curves are advertised as being chosen verifiably at random, there is 245 no explanation for the seeds used to generate them. In contrast, the 246 process used to pick Curve25519 is fully documented and rigid enough 247 so that independent verification has been done. This is widely seen 248 as a security advantage for Curve25519, since it prevents the 249 generating party from maliciously manipulating the parameters. 251 Another family of curves available in TLS, generated in a fully 252 verifiable way, is the Brainpool curves [RFC7027]. Specifically, 253 brainpoolP256 is expected to provide a level of security comparable 254 to Curve25519 and NIST P-256. However, due to the use of pseudo- 255 random prime, it is significantly slower than NIST P-256, which is 256 itself slower than Curve25519. 258 See [SafeCurves] for more comparisons between curves. 260 5. Acknowledgements 262 Several people provided comments and suggestions that helped improve 263 this document: Kurt Roeckx, Andrey Jivsov, Robert Ransom, Rich Salz, 264 David McGrew, Simon Huerlimann. 266 6. References 268 6.1. Normative References 270 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 271 Requirement Levels", BCP 14, RFC 2119, March 1997. 273 [RFC4492] Blake-Wilson, S., Bolyard, N., Gupta, V., Hawk, C., and B. 274 Moeller, "Elliptic Curve Cryptography (ECC) Cipher Suites 275 for Transport Layer Security (TLS)", RFC 4492, May 2006. 277 [RFC5246] Dierks, T. and E. Rescorla, "The Transport Layer Security 278 (TLS) Protocol Version 1.2", RFC 5246, August 2008. 280 [RFC6347] Rescorla, E. and N. Modadugu, "Datagram Transport Layer 281 Security Version 1.2", RFC 6347, January 2012. 283 [I-D.irtf-cfrg-curves] 284 Langley, A., Salz, R., and S. Turner, "Elliptic Curves for 285 Security", draft-irtf-cfrg-curves-01 (work in progress), 286 January 2015. 288 6.2. Informative References 290 [Curve25519] 291 Bernstein, J., "Curve25519: New Diffie-Hellman Speed 292 Records", LNCS 3958, pp. 207-228, February 2006, 293 . 295 [IANA-TLS] 296 Internet Assigned Numbers Authority, "Transport Layer 297 Security (TLS) Parameters", 298 . 301 [SafeCurves] 302 Bernstein, D. and T. Lange, "SafeCurves: choosing safe 303 curves for elliptic-curve cryptography.", January 2014, 304 . 306 [RFC7027] Merkle, J. and M. Lochter, "Elliptic Curve Cryptography 307 (ECC) Brainpool Curves for Transport Layer Security 308 (TLS)", RFC 7027, October 2013. 310 [SEC1] Certicom Research, , "Standards for Efficient Cryptography 311 (SEC) 1", September 2000. 313 [EFD] Bernstein, D. and T. Lange, "Explicit-Formulas Database: 314 XZ coordinates for Montgomery curves", January 2014, 315 . 318 [NaCl] Bernstein, D., "Cryptography in NaCL", March 2013, 319 . 321 Appendix A. The curve25519 function 323 A.1. Formulas 325 This section completes Section 2.1 by defining the Curve25519 326 function and the common public key G. It is meant as an alternative, 327 self-contained specification for the Curve25519 function, possibly 328 easier to follow than the original paper for most implementors. 330 A.1.1. Field Arithmetic 332 Throughout this section, P denotes the integer 2^255-19 = 333 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED. 334 The letters X and Z, and their numbered variants such as x1, z2, etc. 335 denote integers modulo P, that is integers between 0 and P-1 and 336 every operation between them is implictly done modulo P. For 337 addition, subtraction and multiplication this means doing the 338 operation in the usual way and then replacing the result with the 339 remainder of its division by P. For division, "X / Z" means 340 mutliplying (mod P) X by the modular inverse of Z mod P. 342 A convenient way to define the modular inverse of Z mod P is as 343 Z^(P-2) mod P, that is Z to the power of 2^255-21 mod P. It is also 344 a practical way of computing it, using a square-and-multiply method. 346 The four operations +, -, *, / modulo P are known as the field 347 operations. Techniques for efficient implementation of the field 348 operations are outside the scope of this document. 350 A.1.2. Conversion to and from internal format 352 For the purpose of this section, we will define a Curve25519 point as 353 a pair (X, Z) were X and Z are integers mod P (as defined above). 354 Though public keys were defined to be strings of 32 bytes, internally 355 they are represented as curve points. This subsection describes the 356 conversion process as two functions: PubkeyToPoint and PointToPubkey. 358 PubkeyToPoint: 359 Input: a public key b_0, ..., b_31 360 Output: a Curve25519 point (X, Z) 361 1. Set X = b_0 + 256 * b_1 + ... + 256^31 * b_31 mod P 362 2. Set Z = 1 363 3. Output (X, Z) 365 PointToPubkey: 366 Input: a Curve25519 point (X, Z) 367 Output: a public key b_0, ..., b_31 368 1. Set x1 = X / Z mod P 369 2. Set b_0, ... b_31 such that 370 x1 = b_0 + 256 * b_1 + ... + 256^31 * b_31 mod P 371 3. Output b_0, ..., b_31 373 A.1.3. Scalar Multiplication 375 We first introduce the DoubleAndAdd function, defined as follows 376 (formulas taken from [EFD]). 378 DoubleAndAdd: 379 Input: two points (X2, Z2), (X3, Z3), and an integer mod P: X1 380 Output: two points (X4, Z4), (X5, Z5) 381 Constant: the integer mod P: a24 = 121666 = 0x01DB42 382 Variables: A, AA, B, BB, E, C, D, DA, CB are integers mod P 383 1. Do the following computations mod P: 384 A = X2 + Z2 385 AA = A2 386 B = X2 - Z2 387 BB = B2 388 E = AA - BB 389 C = X3 + Z3 390 D = X3 - Z3 391 DA = D * A 392 CB = C * B 393 X5 = (DA + CB)^2 394 Z5 = X1 * (DA - CB)^2 395 X4 = AA * BB 396 Z4 = E * (BB + a24 * E) 397 2. Output (X4, Z4) and (X5, Z5) 399 This may be taken as the abstract definition of an arbitrary-looking 400 function. However, let's mention "the true meaning" of this 401 function, without justification, in order to help the reader make 402 more sense of it. It is possible to define operations "+" and "-" 403 between Curve25519 points. Then, assuming (X2, Z2) - (X3, Z3) = (X1, 404 1), the DoubleAndAdd function returns points such that (X4, Z4) = 405 (X2, Z2) + (X2, Z2) and (X5, Z5) = (X2, Z2) + (X3, Z3). 407 Taking the "+" operation as granted, we can define multiplication of 408 a Curve25519 point by a positive integer as N * (X, Z) = (X, Z) + ... 409 + (X, Z), with N point additions. It is possible to compute this 410 operation, known as scalar multiplication, using an algorithm called 411 the Montgomery ladder, as follows. 413 ScalarMult: 414 Input: a Curve25519 point: (X, 1) and a 255-bits integer: N 415 Output: a point (X1, Z1) 416 Variable: a point (X2, Z2) 417 0. View N as a sequence of bits b_254, ..., b_0, 418 with b_254 the most significant bit 419 and b_0 the least significant bit. 420 1. Set X1 = 1 and Z1 = 0 421 2. Set X2 = X and Z2 = 1 422 3. For i from 254 downwards to 0, do: 423 If b_i == 0, then: 424 Set (X2, Z2) and (X1, Z1) to the output of 425 DoubleAndAdd((X2, Z2), (X1, Z1), X) 426 else: 427 Set (X1, Z1) and (X2, Z2) to the output of 428 DoubleAndAdd((X1, Z1), (X2, Z2), X) 429 4. Output (X1, Z1) 431 A.1.4. Conclusion 433 We are now ready to define the Curve25519 function itself. 435 Curve25519: 436 Input: a public key P and a secret key S 437 Output: a public key Q 438 Variables: two Curve25519 points (X, Z) and (X1, Z1) 439 1. Set (X, Z) = PubkeyToPoint(P) 440 2. Set (X1, Z1) = ScalarMult((X, Z), S) 441 3. Set Q = PointToPubkey((X1, Z1)) 442 4. Output Q 444 The common public key G mentioned in the first paragraph of 445 Section 2.1 is defined as G = PointToPubkey((9, 1). 447 A.2. Test vectors 449 The following test vectors are taken from [NaCl]. Compared to this 450 reference, the private key strings have been applied the ClampC 451 function of the reference and converted to integers in order to fit 452 the description given in [Curve25519] and the present memo. 454 The secret key of party A is denoted by S_a, it public key by P_a, 455 and similarly for party B. The shared secret is SS. 457 S_a = 0x6A2CB91DA5FB77B12A99C0EB872F4CDF 458 4566B25172C1163C7DA518730A6D0770 460 P_a = 85 20 F0 09 89 30 A7 54 74 8B 7D DC B4 3E F7 5A 461 0D BF 3A 0D 26 38 1A F4 EB A4 A9 8E AA 9B 4E 6A 463 S_b = 0x6BE088FF278B2F1CFDB6182629B13B6F 464 E60E80838B7FE1794B8A4A627E08AB58 466 P_b = DE 9E DB 7D 7B 7D C1 B4 D3 5B 61 C2 EC E4 35 37 467 3F 83 43 C8 5B 78 67 4D AD FC 7E 14 6F 88 2B 4F 469 SS = 4A 5D 9D 5B A4 CE 2D E1 72 8E 3B F4 80 35 0F 25 470 E0 7E 21 C9 47 D1 9E 33 76 F0 9B 3C 1E 16 17 42 472 A.3. Side-channel considerations 474 Curve25519 was specifically designed so that correct, fast, constant- 475 time implementations are easier to produce. In particular, using a 476 Montgomery ladder as described in the previous section ensures that, 477 for any valid value of the secret key, the same sequence of field 478 operations are performed, which eliminates a major source of side- 479 channel leakage. 481 However, merely using Curve25519 with a Montgomery ladder does not 482 prevent all side-channels by itself, and some point are the 483 responsibility of implementors: 485 1. In step 3 of SclarMult, avoid branches depending on b_i, as well 486 as memory access patterns depending on b_i, for example by using 487 safe conditional swaps on the inputs and outputs of DoubleAndAdd. 489 2. Avoid data-dependant branches and memory access patterns in the 490 implementation of field operations. 492 Techniques for implementing the field operations in constant time and 493 with high performance are out of scope of this document. Let's 494 mention however that, provided constant-time multiplication is 495 available, division can be computed in constant time using 496 exponentiation as described in Appendix A.1.1. 498 If using constant-time implementations of the field operations is not 499 convenient, an option to reduce the information leaked this way is to 500 replace step 2 of the SclarMult function with: 502 2a. Pick Z uniformly randomly between 1 and P-1 included 503 2b. Set X2 = X * Z and Z2 = Z 505 This method is known as randomizing projective coordinates. However, 506 it is no guaranteed to avoid all side-channel leaks related to field 507 operations. 509 Side-channel attacks are an active reseach domain that still sees new 510 significant results, so implementors of the Curve25519 function are 511 advised to follow recent security research closely. 513 Authors' Addresses 515 Simon Josefsson 516 SJD AB 518 Email: simon@josefsson.org 520 Manuel Pegourie-Gonnard 521 Independent / PolarSSL 523 Email: mpg@elzevir.fr