idnits 2.17.1 draft-josefsson-tls-curve25519-05.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 (April 13, 2014) is 3666 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) Summary: 3 errors (**), 0 flaws (~~), 1 warning (==), 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: October 15, 2014 April 13, 2014 8 Curve25519 for ephemeral key exchange in Transport Layer Security (TLS) 9 draft-josefsson-tls-curve25519-05 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 October 15, 2014. 35 Copyright Notice 37 Copyright (c) 2014 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], a new elliptic curve function for use in 53 cryptographic applications was specified. Curve25519 is a Diffie- 54 Hellman function designed with performance and security in mind. 56 [RFC4492] defines the usage of elliptic curves for authentication and 57 key agreement in TLS 1.0 and TLS 1.1, and these mechanisms are also 58 applicable to TLS 1.2 [RFC5246]. The use of ECC curves for key 59 exchange requires the definition and assignment of additional 60 NamedCurve IDs. This document specify that value for Curve25519, as 61 well as the minor changes in key selection and representation that 62 are required to accommodate for Curve25519's slightly different 63 nature. 65 This document only describes usage of Curve25519 for ephemeral key 66 exchange (ECDHE). It does not define its use for signature, since 67 the primitive considered here is a Diffie-Hellman function; the 68 related signature scheme, Ed25519, is outside the scope of this 69 document. The use of Curve25519 with long-term keys embedded in 70 X.509 certificates is also out of scope here. 72 1.1. Requirements Terminology 74 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 75 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 76 document are to be interpreted as described in [RFC2119]. 78 2. Data Structures and Computations 80 2.1. Cryptographic computations 82 All cryptographic computations are done using the Curve25519 function 83 defined in [Curve25519]. In this memo, this function is considered 84 as a black box that takes as input a (secret key, public key) pair 85 and outputs a public key. Public keys are defined as strings of 32 86 bytes. Secret keys are defined as 255 bits numbers such as the high- 87 order bit (bit 254) is set, and the three lowest-order bits are 88 unset. In addition, a common public key, denoted by G, is shared by 89 all users. 91 An ECDHE key exchange using Curve25519 goes as follows. Each party 92 picks a secret key d uniformly at random and computes the 93 corresponding public key x = Curve25519(d, G). Parties exchange 94 their public keys (see Section 2.3) and compute a shared secret as 95 x_S = Curve25519(d, x_peer). This shared secret is used directly as 96 the premaster secret, which is always exactly 32 bytes when ECDHE 97 with Curve25519 is used. 99 A complete description of the Curve25519 function, as well as a few 100 implementation notes, are provided in Appendix A. 102 2.2. Curve negotiation and new NamedCurve value 104 Curve negotiation uses the mechanisms introduced by [RFC4492], 105 without modification except the following restriction: in the 106 ECParameters structure, only the named_curve case can be used with 107 Curve25519. Accordingly, arbitrary_explicit_prime_curves in the 108 Supported Curves extension does not imply support for Curve25519, 109 even though the Curve25519 function happens to be defined using an 110 elliptic curve over a prime field. 112 The reason for this restriction is that explicit_prime is only suited 113 to the so-called Short Weierstrass representation of elliptic curves, 114 while Curve25519 uses a different representation for performance and 115 security reasons. 117 This document adds a new NamedCurve value for Curve25519 as follows. 119 enum { 120 Curve25519(TBD1), 121 } NamedCurve; 123 Curve25519 is suitable for use with DTLS [RFC6347]. 125 Since Curve25519 is not designed to be used in signatures, clients 126 who offer ECDHE_ECDSA ciphersuites and advertise support for 127 Curve25519 in the elliptic_curves ClientHello extension SHOULD also 128 advertise support for at least one curve suitable for ECDSA. Servers 129 MUST NOT select an ECDHE_ECDSA ciphersuite if there are no common 130 curves suitable for ECDSA. 132 2.3. Public Key representation and new ECPointFormat value 134 This section defines a new point format suitable to encode Curve25519 135 public keys, as well as an identifier to negotiate this new format in 136 TLS, and includes guidance on their use. 138 The curves defined in [RFC4492] define a public key as a point on the 139 curve. In order to exchange public keys, the points are serialized 140 as a string of bytes using one of the formats defined in [SEC1]. 141 These encodings begin with a leading byte identifying the format, 142 followed by a string of bytes, whose length is uniquely determined by 143 the leading byte and curve used. 145 Since Curve25519 public keys already are string of bytes, no 146 serialization is needed. However, a leading byte with value 0x41 is 147 prepended to the public key to identify the format. The goal, 148 besides consistency with the SEC1 formats, is to allow using other 149 formats with Curve25519 in the future if needed. 151 In order to negotiate this format in TLS, a new ECPointFormat is 152 defined as follows. 154 enum { 155 montgomery_x_le(TBD2), 156 } ECPointFormat; 158 This format is currently the only format defined for use with 159 Curve25519. Clients offering Curve25519 in the Supported Elliptic 160 Curves extension MUST also offer montgomery_x_le in the Supported 161 Point Format extension. Servers selecting Curve25519 for key 162 exchange MUST include montgomery_x_le in their Supported Point Format 163 extension. Servers willing to use Curve25519 MUST NOT assume that 164 the client supports the montgomery_x_le format if the client did not 165 advertise it explicitly. 167 When included in a ServerKeyExchange or ClientKeyExchange message, 168 the public key is wrapped in an ECPoint structure as defined in 169 [RFC4492], whose payload is as described above. For example, a 170 public key with value 2A ... 2A appears on the wire as follows 171 (including the length byte of ECPoint.point). 173 21 41 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 174 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 176 2.4. Public key validation 178 With the curves defined by [RFC4492], each party must validate the 179 public key sent by its peer before performing cryptographic 180 computations with it. Failing to do so allows attackers to gain 181 information about the private key, to the point that they may recover 182 the entire private key in a few requests, if that key is not really 183 ephemeral. 185 Curve25519 was designed in a way that the result of Curve25519(x, d) 186 will never reveal information about d, provided is was chosen as 187 prescribed, for any value of x. 189 Let's define legitimate values of x as the values that can be 190 obtained as x = Curve25519(G, d') for some d, and call the other 191 values illegitimate. The definition of the Curve25519 function shows 192 that legitimate values all share the following property: the high- 193 order bit of the last byte is not set. 195 Since there are some implementation of the Curve25519 function that 196 impose this restriction on their input and others that don't, 197 implementations of Curve25519 in TLS SHOULD reject public keys when 198 the high-order bit of the last byte is set (in other words, when the 199 value of the leftmost byte is greater than 0x7F) in order to prevent 200 implementation fingerprinting. 202 Other than this recommended check, implementations do not need to 203 ensure that the public keys they receive are legitimate: this is not 204 necessary for security with Curve25519. 206 3. IANA Considerations 208 IANA is requested to assign numbers for Curve25519 listed in 209 Section 2.2 to the Transport Layer Security (TLS) Parameters registry 210 EC Named Curve [IANA-TLS] as follows. 212 +-------+-------------+---------+-----------+ 213 | Value | Description | DTLS-OK | Reference | 214 +-------+-------------+---------+-----------+ 215 | TBD1 | Curve25519 | Y | This doc | 216 +-------+-------------+---------+-----------+ 218 IANA is also requested to assign numbers for Curve25519 listed in 219 Section 2.3 to the Transport Layer Security (TLS) Parameters registry 220 EC Point Format [IANA-TLS] as follows. 222 +-------+-----------------+---------+-----------+ 223 | Value | Description | DTLS-OK | Reference | 224 +-------+-----------------+---------+-----------+ 225 | TBD2 | montgomery_x_le | Y | This doc | 226 +-------+-----------------+---------+-----------+ 228 4. Security Considerations 230 The security considerations of [RFC5246] and most of the security 231 considerations of [RFC4492] apply accordingly. 233 Curve25519 is designed to facilitate the production of high- 234 performance constant-time implementations of the Curve25519 function. 235 Implementors are encouraged to use a constant-time implementation of 236 the Curve25519 function. This point is of crucial importance if the 237 implementation chooses to reuse its supposedly ephemeral key pair for 238 many key exchanges, which some implementations do in order to improve 239 performance. 241 Curve25519 is believed to be at least as secure as the secp256r1 242 curve defined in [RFC4492], also know as NIST P-256. While the NIST 243 curves are advertised as being chosen verifiably at random, there is 244 no explanation for the seeds used to generate them. In contrast, the 245 process used to pick Curve25519 is fully documented and rigid enough 246 so that independent verification has been done. This is widely seen 247 as a security advantage for Curve25519, since it prevents the 248 generating party from maliciously manipulating the parameters. 250 Another family of curves available in TLS, generated in a fully 251 verifiable way, is the Brainpool curves [RFC7027]. Specifically, 252 brainpoolP256 is expected to provide a level of security comparable 253 to Curve25519 and NIST P-256. However, due to the use of pseudo- 254 random prime, it is significantly slower than NIST P-256, which is 255 itself slower than Curve25519. 257 See [SafeCurves] for more comparisons between curves. 259 5. Acknowledgements 261 Several people provided comments and suggestions that helped improve 262 this document: Kurt Roeckx, Andrey Jivsov, Robert Ransom, Rich Salz, 263 David McGrew. 265 6. References 267 6.1. Normative References 269 [Curve25519] 270 Bernstein, J., "Curve25519: New Diffie-Hellman Speed 271 Records", LNCS 3958, pp. 207-228, February 2006, 272 . 274 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 275 Requirement Levels", BCP 14, RFC 2119, March 1997. 277 [RFC4492] Blake-Wilson, S., Bolyard, N., Gupta, V., Hawk, C., and B. 278 Moeller, "Elliptic Curve Cryptography (ECC) Cipher Suites 279 for Transport Layer Security (TLS)", RFC 4492, May 2006. 281 [RFC5246] Dierks, T. and E. Rescorla, "The Transport Layer Security 282 (TLS) Protocol Version 1.2", RFC 5246, August 2008. 284 [RFC6347] Rescorla, E. and N. Modadugu, "Datagram Transport Layer 285 Security Version 1.2", RFC 6347, January 2012. 287 6.2. Informative References 289 [IANA-TLS] 290 Internet Assigned Numbers Authority, "Transport Layer 291 Security (TLS) Parameters", . 294 [SafeCurves] 295 Bernstein, D. and T. Lange, "SafeCurves: choosing safe 296 curves for elliptic-curve cryptography.", January 2014, 297 . 299 [RFC7027] Merkle, J. and M. Lochter, "Elliptic Curve Cryptography 300 (ECC) Brainpool Curves for Transport Layer Security 301 (TLS)", RFC 7027, October 2013. 303 [SEC1] Certicom Research, , "Standards for Efficient Cryptography 304 (SEC) 1", September 2000. 306 [EFD] Bernstein, D. and T. Lange, "Explicit-Formulas Database: 307 XZ coordinates for Montgomery curves", January 2014, 308 . 311 [NaCl] Bernstein, D., "Cryptography in NaCL", March 2013, 312 . 314 Appendix A. The curve25519 function 316 A.1. Formulas 318 This section completes Section 2.1 by defining the Curve25519 319 function and the common public key G. It is meant as an alternative, 320 self-contained specification for the Curve25519 function, possibly 321 easier to follow than the original paper for most implementors. 323 A.1.1. Field Arithmetic 325 Throughout this section, P denotes the integer 2^255-19 = 326 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED. 327 The letters X and Z, and their numbered variants such as x1, z2, etc. 328 denote integers modulo P, that is integers between 0 and P-1 and 329 every operation between them is implictly done modulo P. For 330 addition, subtraction and multiplication this means doing the 331 operation in the usual way and then replacing the result with the 332 remainder of its division by P. For division, "X / Z" means 333 mutliplying (mod P) X by the modular inverse of Z mod P. 335 A convenient way to define the modular inverse of Z mod P is as 336 Z^(P-2) mod P, that is Z to the power of 2^255-21 mod P. It is also a 337 practical way of computing it, using a square-and-multiply method. 339 The four operations +, -, *, / modulo P are known as the field 340 operations. Techniques for efficient implementation of the field 341 operations are outside the scope of this document. 343 A.1.2. Conversion to and from internal format 345 For the purpose of this section, we will define a Curve25519 point as 346 a pair (X, Z) were X and Z are integers mod P (as defined above). 347 Though public keys were defined to be strings of 32 bytes, internally 348 they are represented as curve points. This subsection describes the 349 conversion process as two functions: PubkeyToPoint and PointToPubkey. 351 PubkeyToPoint: 352 Input: a public key b_0, ..., b_31 353 Output: a Curve25519 point (X, Z) 354 1. Set X = b_0 + 256 * b_1 + ... + 256^31 * b_31 mod P 355 2. Set Z = 1 356 3. Output (X, Z) 358 PointToPubkey: 359 Input: a Curve25519 point (X, Z) 360 Output: a public key b_0, ..., b_31 361 1. Set x1 = X / Z mod P 362 2. Set b_0, ... b_31 such that 363 x1 = b_0 + 256 * b_1 + ... + 256^31 * b_31 mod P 364 3. Output b_0, ..., b_31 366 A.1.3. Scalar Multiplication 368 We first introduce the DoubleAndAdd function, defined as follows 369 (formulas taken from [EFD]). 371 DoubleAndAdd: 372 Input: two points (X2, Z2), (X3, Z3), and an integer mod P: X1 373 Output: two points (X4, Z4), (X5, Z5) 374 Constant: the integer mod P: a24 = 121666 = 0x01DB42 375 Variables: A, AA, B, BB, E, C, D, DA, CB are integers mod P 376 1. Do the following computations mod P: 377 A = X2 + Z2 378 AA = A2 379 B = X2 - Z2 380 BB = B2 381 E = AA - BB 382 C = X3 + Z3 383 D = X3 - Z3 384 DA = D * A 385 CB = C * B 386 X5 = (DA + CB)^2 387 Z5 = X1 * (DA - CB)^2 388 X4 = AA * BB 389 Z4 = E * (BB + a24 * E) 390 2. Output (X4, Z4) and (X5, Z5) 392 This may be taken as the abstract definition of an arbitrary-looking 393 function. However, let's mention "the true meaning" of this 394 function, without justification, in order to help the reader make 395 more sense of it. It is possible to define operations "+" and "-" 396 between Curve25519 points. Then, assuming (X2, Z2) - (X3, Z3) = (X1, 397 1), the DoubleAndAdd function returns points such that (X4, Z4) = 398 (X2, Z2) + (X2, Z2) and (X5, Z5) = (X2, Z2) + (X3, Z3). 400 Taking the "+" operation as granted, we can define multiplication of 401 a Curve25519 point by a positive integer as N * (X, Z) = (X, Z) + ... 402 + (X, Z), with N point additions. It is possible to compute this 403 operation, known as scalar multiplication, using an algorithm called 404 the Montgomery ladder, as follows. 406 ScalarMult: 407 Input: a Curve25519 point: (X, 1) and a 255-bits integer: N 408 Output: a point (X1, Z1) 409 Variable: a point (X2, Z2) 410 0. View N as a sequence of bits b_254, ..., b_0, 411 with b_254 the most significant bit 412 and b_0 the least significant bit. 413 1. Set X1 = 1 and Z1 = 0 414 2. Set X2 = X and Z2 = 1 415 3. For i from 254 downwards to 0, do: 416 If b_i == 0, then: 417 Set (X2, Z2) and (X1, Z1) to the output of 418 DoubleAndAdd((X2, Z2), (X1, Z1), X) 419 else: 420 Set (X1, Z1) and (X2, Z2) to the output of 421 DoubleAndAdd((X1, Z1), (X2, Z2), X) 422 4. Output (X1, Z1) 424 A.1.4. Conclusion 426 We are now ready to define the Curve25519 function itself. 428 Curve25519: 429 Input: a public key P and a secret key S 430 Output: a public key Q 431 Variables: two Curve25519 points (X, Z) and (X1, Z1) 432 1. Set (X, Z) = PubkeyToPoint(P) 433 2. Set (X1, Z1) = ScalarMult((X, Z), S) 434 3. Set Q = PointToPubkey((X1, Z1)) 435 4. Output Q 437 The common public key G mentioned in the first paragraph of 438 Section 2.1 is defined as G = PointToPubkey((9, 1). 440 A.2. Test vectors 442 The following test vectors are taken from [NaCl]. Compared to this 443 reference, the private key strings have been applied the ClampC 444 function of the reference and converted to integers in order to fit 445 the description given in [Curve25519] and the present memo. 447 The secret key of party A is denoted by S_a, it public key by P_a, 448 and similarly for party B. The shared secret is SS. 450 S_a = 0x6A2CB91DA5FB77B12A99C0EB872F4CDF 451 4566B25172C1163C7DA518730A6D0770 453 P_a = 85 20 F0 09 89 30 A7 54 74 8B 7D DC B4 3E F7 5A 454 0D BF 3A 0D 26 38 1A F4 EB A4 A9 8E AA 9B 4E 6A 456 S_b = 0x6BE088FF278B2F1CFDB6182629B13B6F 457 E60E80838B7FE1794B8A4A627E08AB58 459 P_b = DE 9E DB 7D 7B 7D C1 B4 D3 5B 61 C2 EC E4 35 37 460 3F 83 43 C8 5B 78 67 4D AD FC 7E 14 6F 88 2B 4F 462 SS = 4A 5D 9D 5B A4 CE 2D E1 72 8E 3B F4 80 35 0F 25 463 E0 7E 21 C9 47 D1 9E 33 76 F0 9B 3C 1E 16 17 42 465 A.3. Side-channel considerations 467 Curve25519 was specifically designed so that correct, fast, constant- 468 time implementations are easier to produce. In particular, using a 469 Montgomery ladder as described in the previous section ensures that, 470 for any valid value of the secret key, the same sequence of field 471 operations are performed, which eliminates a major source of side- 472 channel leakage. 474 However, merely using Curve25519 with a Montgomery ladder does not 475 prevent all side-channels by itself, and some point are the 476 responsibility of implementors: 478 1. In step 3 of SclarMult, avoid branches depending on b_i, as well 479 as memory access patterns depending on b_i, for example by using 480 safe conditional swaps on the inputs and outputs of DoubleAndAdd. 482 2. Avoid data-dependant branches and memory access patterns in the 483 implementation of field operations. 485 Techniques for implementing the field operations in constant time and 486 with high performance are out of scope of this document. Let's 487 mention however that, provided constant-time multiplication is 488 available, division can be computed in constant time using 489 exponentiation as described in Appendix A.1.1. 491 If using constant-time implementations of the field operations is not 492 convenient, an option to reduce the information leaked this way is to 493 replace step 2 of the SclarMult function with: 495 2a. Pick Z uniformly randomly between 1 and P-1 included 496 2b. Set X2 = X * Z and Z2 = Z 498 This method is known as randomizing projective coordinates. However, 499 it is no guaranteed to avoid all side-channel leaks related to field 500 operations. 502 Side-channel attacks are an active reseach domain that still sees new 503 significant results, so implementors of the Curve25519 function are 504 advised to follow recent security research closely. 506 Authors' Addresses 508 Simon Josefsson 509 SJD AB 511 Email: simon@josefsson.org 513 Manuel Pegourie-Gonnard 514 Independent / PolarSSL 516 Email: mpg@elzevir.fr