idnits 2.17.1 draft-nir-ipsecme-curve25519-01.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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (July 7, 2015) is 3187 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Outdated reference: A later version (-11) exists of draft-irtf-cfrg-curves-02 ** Downref: Normative reference to an Informational draft: draft-irtf-cfrg-curves (ref. 'CFRG-Curves') -- Obsolete informational reference (is this intentional?): RFC 4753 (Obsoleted by RFC 5903) Summary: 1 error (**), 0 flaws (~~), 2 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group Y. Nir 3 Internet-Draft Check Point 4 Intended status: Standards Track S. Josefsson 5 Expires: January 8, 2016 SJD 6 July 7, 2015 8 New Safe Curves for IKEv2 Key Agreement 9 draft-nir-ipsecme-curve25519-01 11 Abstract 13 This document describes the use of Curve25519 and Curve448 14 ("Goldilocks") for ephemeral key exchange in the Internet Key 15 Exchange (IKEv2) protocol. 17 Status of This Memo 19 This Internet-Draft is submitted in full conformance with the 20 provisions of BCP 78 and BCP 79. 22 Internet-Drafts are working documents of the Internet Engineering 23 Task Force (IETF). Note that other groups may also distribute 24 working documents as Internet-Drafts. The list of current Internet- 25 Drafts is at http://datatracker.ietf.org/drafts/current/. 27 Internet-Drafts are draft documents valid for a maximum of six months 28 and may be updated, replaced, or obsoleted by other documents at any 29 time. It is inappropriate to use Internet-Drafts as reference 30 material or to cite them other than as "work in progress." 32 This Internet-Draft will expire on January 8, 2016. 34 Copyright Notice 36 Copyright (c) 2015 IETF Trust and the persons identified as the 37 document authors. All rights reserved. 39 This document is subject to BCP 78 and the IETF Trust's Legal 40 Provisions Relating to IETF Documents 41 (http://trustee.ietf.org/license-info) in effect on the date of 42 publication of this document. Please review these documents 43 carefully, as they describe your rights and restrictions with respect 44 to this document. Code Components extracted from this document must 45 include Simplified BSD License text as described in Section 4.e of 46 the Trust Legal Provisions and are provided without warranty as 47 described in the Simplified BSD License. 49 Table of Contents 51 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 52 1.1. Conventions Used in This Document . . . . . . . . . . . . 2 53 2. Curve25519 & Curve448 . . . . . . . . . . . . . . . . . . . . 3 54 3. Use and Negotiation in IKEv2 . . . . . . . . . . . . . . . . 3 55 3.1. Key Exchange Payload . . . . . . . . . . . . . . . . . . 4 56 3.2. Recipient Tests . . . . . . . . . . . . . . . . . . . . . 4 57 4. Security Considerations . . . . . . . . . . . . . . . . . . . 5 58 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 5 59 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 5 60 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 6 61 7.1. Normative References . . . . . . . . . . . . . . . . . . 6 62 7.2. Informative References . . . . . . . . . . . . . . . . . 6 63 Appendix A. The curve25519 function . . . . . . . . . . . . . . 6 64 A.1. Formulas . . . . . . . . . . . . . . . . . . . . . . . . 7 65 A.1.1. Field Arithmetic . . . . . . . . . . . . . . . . . . 7 66 A.1.2. Conversion to and from internal format . . . . . . . 7 67 A.1.3. Scalar Multiplication . . . . . . . . . . . . . . . . 8 68 A.1.4. Conclusion . . . . . . . . . . . . . . . . . . . . . 9 69 A.2. Test vectors . . . . . . . . . . . . . . . . . . . . . . 9 70 A.3. Side-channel considerations . . . . . . . . . . . . . . . 10 71 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11 73 1. Introduction 75 [CFRG-Curves] specifies two new elliptic curve functions for use in 76 cryptographic applications. Curve25519 and Curve448 (also known as 77 "Goldilocks") are Diffie-Hellman functions designed with performance 78 and security in mind. 80 Almost ten years ago [RFC4753] specified the first elliptic curve 81 Diffie-Hellman groups for the Internet Key Exchange protocol (IKEv2 - 82 [RFC7296]). These were the so-called NIST curves. The state of the 83 art has advanced since then. More modern curves allow faster 84 implementations while making it much easier to write constant-time 85 implementations free from side-channel attacks. This document 86 defines such a curve for use in IKE. See [Curve25519] for details 87 about the speed and security of the Curve25519 function. 89 1.1. Conventions Used in This Document 91 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 92 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 93 document are to be interpreted as described in [RFC2119]. 95 2. Curve25519 & Curve448 97 All cryptographic computations are done using the Curve25519 and 98 Curve448 functions defined in [CFRG-Curves]. In this document, these 99 functions are considered black boxes that take for input a (secret 100 key, public key) pair and output a public key. Public keys for are 101 defined as strings of 32 octets. A common public key, denoted below 102 as G (or "base point" in the curves document) is shared by all users. 103 Since the functions only use the u-coordinate of the public key, only 104 the u coordinate of the base points is necessary. For Curve25519 105 Gu=9 ; for Curve448 Gu=5. 107 For Curve25519 secret keys are defined as 255-bit numbers such that 108 the high-order bit (bit 254) is set, and the three lowest-order bits 109 are unset. 111 For Curve448 secret keys are defined as 448-bit numbers such that the 112 high-order bit (bit 447) is set, and the two lowest-order bits are 113 unset. 115 An ephemeral Diffie-Hellman key exchange using Curve25519 or Curve448 116 goes as follows: Each party picks a secret key d uniformly at random 117 and computes the corresponding public key. "curve_function" is used 118 below to denote either Curve25519 or Curve448: 120 x_mine = curve_function(d, G) 122 Parties exchange their public keys (see Section 3.1) and compute a 123 shared secret: 125 SHARED_SECRET = curve_function(d, x_peer). 127 This shared secret is used directly as the value denoted g^ir in 128 section 2.14 of RFC 7296. It is always exactly 32 octets when these 129 functions are used. 131 A complete description of the Curve25519 function, as well as a few 132 implementation notes, are provided in Appendix A. 134 3. Use and Negotiation in IKEv2 136 The use of Curve25519 and Curve448 in IKEv2 is negotiated using a 137 Transform Type 4 (Diffie-Hellman group) in the SA payload of either 138 an IKE_SA_INIT or a CREATE_CHILD_SA exchange. 140 3.1. Key Exchange Payload 142 The diagram for the Key Exchange Payload from section 3.4 of RFC 7296 143 is copied below for convenience: 145 1 2 3 146 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 147 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 148 | Next Payload |C| RESERVED | Payload Length | 149 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 150 | Diffie-Hellman Group Num | RESERVED | 151 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 152 | | 153 ~ Key Exchange Data ~ 154 | | 155 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 157 o Payload Length - Since the public key is 32 octets, the Payload 158 Length field always contains 40. 159 o The Diffie-Hellman Group Num is xx for Curve25519, or yy for 160 Curve448 (both TBA by IANA). 161 o The Key Exchange Data is 32 octets encoded as an array of bytes in 162 little-endian order as described in section 8 of [CFRG-Curves] 164 3.2. Recipient Tests 166 This section describes the checks that a recipient of a public key 167 needs to perform. It is the equivalent of the tests described in 168 [RFC6989] for other Diffie-Hellman groups. We use "func" to denote 169 either Curve25519 or Curve448, as the tests are similar to both. 171 Both functions were designed in a way that the result of func(d, x) 172 will never reveal information about d, provided it was chosen as 173 prescribed, for any value of x. 175 Define legitimate values of x as the values that can be obtained as x 176 = func(d, G) for some d, and call the other values illegitimate. The 177 definitions of the functions show that legitimate values all share 178 the following property: the high-order bit of the last byte is not 179 set. 181 Since there are some implementation of these functions that impose 182 this restriction on their input and others that don't, IKEv2 183 implementations SHOULD reject public keys when the high-order bit of 184 the last byte is set (in other words, when the value of the leftmost 185 byte is greater than 0x7F) in order to prevent implementation 186 fingerprinting. 188 Other than this recommended check, implementations do not need to 189 ensure that the public keys they receive are legitimate: this is not 190 necessary for security. 192 4. Security Considerations 194 Curve25519 is designed to facilitate the production of high- 195 performance constant-time implementations. Implementors are 196 encouraged to use a constant-time implementation of the Curve25519 197 function. This point is of crucial importance if the implementation 198 chooses to reuse its supposedly ephemeral key pair for many key 199 exchanges, which some implementations do in order to improve 200 performance. The same is true for Curve448. 202 Curve25519 is believed to be at least as secure as the 256-bit random 203 ECP group (group 19) defined in RFC 4753, also known as NIST P-256 or 204 secp256r1. Curve448 is believed to be more secure than the 384-bit 205 random ECP group (group 20), also known as NIST P-384 or secp384r1. 207 While the NIST curves are advertised as being chosen verifiably at 208 random, there is no explanation for the seeds used to generate them. 209 In contrast, the process used to pick these curves is fully 210 documented and rigid enough so that independent verification has been 211 done. This is widely seen as a security advantage for Curve25519, 212 since it prevents the generating party from maliciously manipulating 213 the parameters. 215 Another family of curves available in IKE, generated in a fully 216 verifiable way, is the Brainpool curves [RFC6954]. Specifically, 217 brainpoolP256 (group 28) is expected to provide a level of security 218 comparable to Curve25519 and NIST P-256. However, due to the use of 219 pseudo-random prime, it is significantly slower than NIST P-256, 220 which is itself slower than Curve25519. 222 5. IANA Considerations 224 IANA is requested to assign two values from the IKEv2 "Transform Type 225 4 - Diffie-Hellman Group Transform IDs" registry, with names 226 "Curve25519" and "Curve448" and this document as reference. The 227 Recipient Tests field should also point to this document. 229 6. Acknowledgements 231 Curve25519 was designed by D. J. Bernstein and Tanja Lange. 232 Curve448 ("Goldilocks") is by Mike Hamburg. The specification of 233 wire format is Sean Turner, Rich Salz, and Watson Ladd, with Adam 234 Langley editing the current document. Much of the text in this 235 document is copied from Simon's draft for the TLS working group. 237 7. References 239 7.1. Normative References 241 [CFRG-Curves] 242 Langley, A., Salz, R., and S. Turner, "Elliptic Curves for 243 Security", draft-irtf-cfrg-curves-02 (work in progress), 244 March 2015. 246 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 247 Requirement Levels", BCP 14, RFC 2119, March 1997. 249 [RFC7296] Kivinen, T., Kaufman, C., Hoffman, P., Nir, Y., and P. 250 Eronen, "Internet Key Exchange Protocol Version 2 251 (IKEv2)", RFC 7296, October 2014. 253 7.2. Informative References 255 [Curve25519] 256 Bernstein, J., "Curve25519: New Diffie-Hellman Speed 257 Records", LNCS 3958, February 2006, 258 . 260 [EFD] Bernstein, D. and T. Lange, "Explicit-Formulas Database: 261 XZ coordinates for Montgomery curves", January 2014, 262 . 265 [NaCl] Bernstein, D., "Cryptography in NaCL", March 2013, 266 . 268 [RFC4753] Fu, D. and J. Solinas, "ECP Groups For IKE and IKEv2", RFC 269 4753, January 2007. 271 [RFC6954] Merkle, J. and M. Lochter, "Using the Elliptic Curve 272 Cryptography (ECC) Brainpool Curves for the Internet Key 273 Exchange Protocol Version 2 (IKEv2)", RFC 6954, July 2013. 275 [RFC6989] Sheffer, Y. and S. Fluhrer, "Additional Diffie-Hellman 276 Tests for the Internet Key Exchange Protocol Version 2 277 (IKEv2)", RFC 6989, July 2013. 279 Appendix A. The curve25519 function 280 A.1. Formulas 282 This section completes Section 2 by defining the Curve25519 function 283 and the common public key G. It is meant as an alternative, self- 284 contained specification for the Curve25519 function, possibly easier 285 to follow than the original paper for most implementors. 287 A.1.1. Field Arithmetic 289 Throughout this section, P denotes the integer 2^255-19 = 290 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED. 291 The letters X and Z, and their numbered variants such as x1, z2, etc. 292 denote integers modulo P, that is integers between 0 and P-1 and 293 every operation between them is implictly done modulo P. For 294 addition, subtraction and multiplication this means doing the 295 operation in the usual way and then replacing the result with the 296 remainder of its division by P. For division, "X / Z" means 297 mutliplying (mod P) X by the modular inverse of Z mod P. 299 A convenient way to define the modular inverse of Z mod P is as 300 Z^(P-2) mod P, that is Z to the power of 2^255-21 mod P. It is also 301 a practical way of computing it, using a square-and-multiply method. 303 The four operations +, -, *, / modulo P are known as the field 304 operations. Techniques for efficient implementation of the field 305 operations are outside the scope of this document. 307 A.1.2. Conversion to and from internal format 309 For the purpose of this section, we will define a Curve25519 point as 310 a pair (X, Z) were X and Z are integers mod P (as defined above). 311 Though public keys were defined to be strings of 32 bytes, internally 312 they are represented as curve points. This subsection describes the 313 conversion process as two functions: PubkeyToPoint and PointToPubkey. 315 PubkeyToPoint: 316 Input: a public key b_0, ..., b_31 317 Output: a Curve25519 point (X, Z) 318 1. Set X = b_0 + 256 * b_1 + ... + 256^31 * b_31 mod P 319 2. Set Z = 1 320 3. Output (X, Z) 322 PointToPubkey: 323 Input: a Curve25519 point (X, Z) 324 Output: a public key b_0, ..., b_31 325 1. Set x1 = X / Z mod P 326 2. Set b_0, ... b_31 such that 327 x1 = b_0 + 256 * b_1 + ... + 256^31 * b_31 mod P 328 3. Output b_0, ..., b_31 330 A.1.3. Scalar Multiplication 332 We first introduce the DoubleAndAdd function, defined as follows 333 (formulas taken from [EFD]). 335 DoubleAndAdd: 336 Input: two points (X2, Z2), (X3, Z3), and an integer mod P: X1 337 Output: two points (X4, Z4), (X5, Z5) 338 Constant: the integer mod P: a24 = 121666 = 0x01DB42 339 Variables: A, AA, B, BB, E, C, D, DA, CB are integers mod P 340 1. Do the following computations mod P: 341 A = X2 + Z2 342 AA = A2 343 B = X2 - Z2 344 BB = B2 345 E = AA - BB 346 C = X3 + Z3 347 D = X3 - Z3 348 DA = D * A 349 CB = C * B 350 X5 = (DA + CB)^2 351 Z5 = X1 * (DA - CB)^2 352 X4 = AA * BB 353 Z4 = E * (BB + a24 * E) 354 2. Output (X4, Z4) and (X5, Z5) 356 This may be taken as the abstract definition of an arbitrary-looking 357 function. However, let's mention "the true meaning" of this 358 function, without justification, in order to help the reader make 359 more sense of it. It is possible to define operations "+" and "-" 360 between Curve25519 points. Then, assuming (X2, Z2) - (X3, Z3) = (X1, 361 1), the DoubleAndAdd function returns points such that (X4, Z4) = 362 (X2, Z2) + (X2, Z2) and (X5, Z5) = (X2, Z2) + (X3, Z3). 364 Taking the "+" operation as granted, we can define multiplication of 365 a Curve25519 point by a positive integer as N * (X, Z) = (X, Z) + ... 366 + (X, Z), with N point additions. It is possible to compute this 367 operation, known as scalar multiplication, using an algorithm called 368 the Montgomery ladder, as follows. 370 ScalarMult: 371 Input: a Curve25519 point: (X, 1) and a 255-bits integer: N 372 Output: a point (X1, Z1) 373 Variable: a point (X2, Z2) 374 0. View N as a sequence of bits b_254, ..., b_0, 375 with b_254 the most significant bit 376 and b_0 the least significant bit. 377 1. Set X1 = 1 and Z1 = 0 378 2. Set X2 = X and Z2 = 1 379 3. For i from 254 downwards to 0, do: 380 If b_i == 0, then: 381 Set (X2, Z2) and (X1, Z1) to the output of 382 DoubleAndAdd((X2, Z2), (X1, Z1), X) 383 else: 384 Set (X1, Z1) and (X2, Z2) to the output of 385 DoubleAndAdd((X1, Z1), (X2, Z2), X) 386 4. Output (X1, Z1) 388 A.1.4. Conclusion 390 We are now ready to define the Curve25519 function itself. 392 Curve25519: 393 Input: a public key P and a secret key S 394 Output: a public key Q 395 Variables: two Curve25519 points (X, Z) and (X1, Z1) 396 1. Set (X, Z) = PubkeyToPoint(P) 397 2. Set (X1, Z1) = ScalarMult((X, Z), S) 398 3. Set Q = PointToPubkey((X1, Z1)) 399 4. Output Q 401 The common public key G mentioned in the first paragraph of Section 2 402 is defined as G = PointToPubkey((9, 1). 404 A.2. Test vectors 406 The following test vectors are taken from [NaCl]. Compared to this 407 reference, the private key strings have been applied the ClampC 408 function of the reference and converted to integers in order to fit 409 the description given in [Curve25519] and the present memo. 411 The secret key of party A is denoted by S_a, it public key by P_a, 412 and similarly for party B. The shared secret is SS. 414 S_a = 0x6A2CB91DA5FB77B12A99C0EB872F4CDF 415 4566B25172C1163C7DA518730A6D0770 417 P_a = 85 20 F0 09 89 30 A7 54 74 8B 7D DC B4 3E F7 5A 418 0D BF 3A 0D 26 38 1A F4 EB A4 A9 8E AA 9B 4E 6A 420 S_b = 0x6BE088FF278B2F1CFDB6182629B13B6F 421 E60E80838B7FE1794B8A4A627E08AB58 423 P_b = DE 9E DB 7D 7B 7D C1 B4 D3 5B 61 C2 EC E4 35 37 424 3F 83 43 C8 5B 78 67 4D AD FC 7E 14 6F 88 2B 4F 426 SS = 4A 5D 9D 5B A4 CE 2D E1 72 8E 3B F4 80 35 0F 25 427 E0 7E 21 C9 47 D1 9E 33 76 F0 9B 3C 1E 16 17 42 429 A.3. Side-channel considerations 431 Curve25519 was specifically designed so that correct, fast, constant- 432 time implementations are easier to produce. In particular, using a 433 Montgomery ladder as described in the previous section ensures that, 434 for any valid value of the secret key, the same sequence of field 435 operations are performed, which eliminates a major source of side- 436 channel leakage. 438 However, merely using Curve25519 with a Montgomery ladder does not 439 prevent all side-channels by itself, and some point are the 440 responsibility of implementors: 442 1. In step 3 of SclarMult, avoid branches depending on b_i, as well 443 as memory access patterns depending on b_i, for example by using 444 safe conditional swaps on the inputs and outputs of DoubleAndAdd. 445 2. Avoid data-dependant branches and memory access patterns in the 446 implementation of field operations. 448 Techniques for implementing the field operations in constant time and 449 with high performance are out of scope of this document. Let's 450 mention however that, provided constant-time multiplication is 451 available, division can be computed in constant time using 452 exponentiation as described in Appendix A.1.1. 454 If using constant-time implementations of the field operations is not 455 convenient, an option to reduce the information leaked this way is to 456 replace step 2 of the SclarMult function with: 458 2a. Pick Z uniformly randomly between 1 and P-1 included 459 2b. Set X2 = X * Z and Z2 = Z 461 This method is known as randomizing projective coordinates. However, 462 it is no guaranteed to avoid all side-channel leaks related to field 463 operations. 465 Side-channel attacks are an active reseach domain that still sees new 466 significant results, so implementors of the Curve25519 function are 467 advised to follow recent security research closely. 469 Authors' Addresses 471 Yoav Nir 472 Check Point Software Technologies Ltd. 473 5 Hasolelim st. 474 Tel Aviv 6789735 475 Israel 477 Email: ynir.ietf@gmail.com 479 Simon Josefsson 480 SJD AB 482 Email: simon@josefsson.org