idnits 2.17.1 draft-irtf-cfrg-curves-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 : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** There are 10 instances of too long lines in the document, the longest one being 11 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (January 28, 2015) is 3375 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 461 -- Looks like a reference, but probably isn't: '1' on line 308 -- Looks like a reference, but probably isn't: '2' on line 308 -- Looks like a reference, but probably isn't: '31' on line 461 Summary: 3 errors (**), 0 flaws (~~), 1 warning (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 CFRG A. Langley 3 Internet-Draft Google 4 Intended status: Informational R. Salz 5 Expires: August 1, 2015 Akamai Technologies 6 S. Turner 7 IECA, Inc. 8 January 28, 2015 10 Elliptic Curves for Security 11 draft-irtf-cfrg-curves-01 13 Abstract 15 This memo describes an algorithm for deterministically generating 16 parameters for elliptic curves over prime fields offering high 17 practical security in cryptographic applications, including Transport 18 Layer Security (TLS) and X.509 certificates. It also specifies a 19 specific curve at the ~128-bit security level. 21 Status of This Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF). Note that other groups may also distribute 28 working documents as Internet-Drafts. The list of current Internet- 29 Drafts is at http://datatracker.ietf.org/drafts/current/. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 This Internet-Draft will expire on August 1, 2015. 38 Copyright Notice 40 Copyright (c) 2015 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (http://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. Code Components extracted from this document must 49 include Simplified BSD License text as described in Section 4.e of 50 the Trust Legal Provisions and are provided without warranty as 51 described in the Simplified BSD License. 53 Table of Contents 55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 56 2. Requirements Language . . . . . . . . . . . . . . . . . . . . 3 57 3. Security Requirements . . . . . . . . . . . . . . . . . . . . 3 58 4. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 3 59 5. Parameter Generation . . . . . . . . . . . . . . . . . . . . 4 60 5.1. Edwards Curves . . . . . . . . . . . . . . . . . . . . . 4 61 5.2. Twisted Edwards Curves . . . . . . . . . . . . . . . . . 5 62 6. Recommended Curves . . . . . . . . . . . . . . . . . . . . . 6 63 7. The curve25519 function . . . . . . . . . . . . . . . . . . . 7 64 7.1. Test vectors . . . . . . . . . . . . . . . . . . . . . . 10 65 8. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . . 11 66 8.1. Test vectors . . . . . . . . . . . . . . . . . . . . . . 11 67 9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 11 68 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 12 69 10.1. Normative References . . . . . . . . . . . . . . . . . . 12 70 10.2. Informative References . . . . . . . . . . . . . . . . . 12 71 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 13 73 1. Introduction 75 Since the initial standardization of elliptic curve cryptography 76 (ECC) in [SEC1] there has been significant progress related to both 77 efficiency and security of curves and implementations. Notable 78 examples are algorithms protected against certain side-channel 79 attacks, various 'special' prime shapes which allow faster modular 80 arithmetic, and a larger set of curve models from which to choose. 81 There is also concern in the community regarding the generation and 82 potential weaknesses of the curves defined in [NIST]. 84 This memo describes a deterministic algorithm for generating 85 cryptographic elliptic curves over a given prime field. The 86 constraints in the generation process produce curves that support 87 constant-time, exception-free scalar multiplications that are 88 resistant to a wide range of side-channel attacks including timing 89 and cache attacks, thereby offering high practical security in 90 cryptographic applications. The deterministic algorithm operates 91 without any input parameters that would permit manipulation of the 92 resulting curves. The selection between curve models is determined 93 by choosing the curve form that supports the fastest (currently 94 known) complete formulas for each modularity option of the underlying 95 field prime. Specifically, the Edwards curve x^2 + y^2 = 1 + dx^2y^2 96 is used with primes p with p = 3 mod 4, and the twisted Edwards curve 97 -x^2 + y^2 = 1 + dx^2y^2 is used when p = 1 mod 4. 99 2. Requirements Language 101 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 102 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 103 document are to be interpreted as described in RFC 2119 [RFC2119]. 105 3. Security Requirements 107 For each curve at a specific security level: 109 1. The domain parameters SHALL be generated in a simple, 110 deterministic manner, without any secret or random inputs. The 111 derivation of the curve parameters is defined in Section 5. 113 2. The trace of Frobenius MUST NOT be in {0, 1} in order to rule out 114 the attacks described in [Smart], [AS], and [S], as in [EBP]. 116 3. MOV Degree: the embedding degree k MUST be greater than (r - 1) / 117 100, as in [EBP]. 119 4. CM Discriminant: discriminant D MUST be greater than 2^100, as in 120 [SC]. 122 4. Notation 124 Throughout this document, the following notation is used: 126 p Denotes the prime number defining the underlying field. 128 GF(p) The finite field with p elements. 130 d An element in the finite field GF(p), not equal to -1 or zero. 132 Ed An Edwards curve: an elliptic curve over GF(p) with equation x^2 + 133 y^2 = 1 + dx^2y^2. 135 tEd A twisted Edwards curve where a=-1: an elliptic curve over GF(p) 136 with equation -x^2 + y^2 = 1 + dx^2y^2. 138 oddDivisor The largest odd divisor of the number of GF(p)-rational 139 points on a (twisted) Edwards curve. 141 oddDivisor' The largest odd divisor of the number of GF(p)-rational 142 points on the non-trivial quadratic twist of a (twisted) Edwards 143 curve. 145 cofactor The cofactor of the subgroup of order oddDivisor in the 146 group of GF(p)-rational points of a (twisted) Edwards curve. 148 cofactor' The cofactor of the subgroup of order oddDivisor in the 149 group of GF(p)-rational points on the non-trivial quadratic twist 150 of a (twisted) Edwards curve. 152 trace The trace of Frobenius of Ed or tEd such that #Ed(GF(p)) = p + 153 1 - trace or #tEd(GF(p)) = p + 1 - trace, respectively. 155 P A generator point defined over GF(p) of prime order oddDivisor on 156 Ed or tEd. 158 X(P) The x-coordinate of the elliptic curve point P. 160 Y(P) The y-coordinate of the elliptic curve point P. 162 5. Parameter Generation 164 This section describes the generation of the curve parameter, namely 165 d, of the elliptic curve. The input to this process is p, the prime 166 that defines the underlying field. The size of p determines the 167 amount of work needed to compute a discrete logarithm in the elliptic 168 curve group and choosing a precise p depends on many implementation 169 concerns. The performance of the curve will be dominated by 170 operations in GF(p) and thus carefully choosing a value that allows 171 for easy reductions on the intended architecture is critical. This 172 document does not attempt to articulate all these considerations. 174 5.1. Edwards Curves 176 For p = 3 mod 4, the elliptic curve Ed in Edwards form is determined 177 by the non-square element d from GF(p) (not equal to -1 or zero) with 178 smallest absolute value such that #Ed(GF(p)) = cofactor * oddDivisor, 179 #Ed'(GF(p)) = cofactor' * oddDivisor', cofactor = cofactor' = 4, and 180 both subgroup orders oddDivisor and oddDivisor' are prime. In 181 addition, care must be taken to ensure the MOV degree and CM 182 discriminant requirements from Section 3 are met. 184 These cofactors are chosen because they are minimal. 186 Input: a prime p, with p = 3 mod 4 187 Output: the parameter d defining the curve Ed 188 1. Set d = 0 189 2. repeat 190 repeat 191 if (d > 0) then 192 d = -d 193 else 194 d = -d + 1 195 end if 196 until d is not a square in GF(p) 198 Compute oddDivisor, oddDivisor', cofactor and cofactor' where #Ed(GF(p)) = 199 cofactor * oddDivisor, #Ed'(GF(p)) = cofactor' * oddDivisor', cofactor and 200 cofactor' are powers of 2 and oddDivisor, oddDivisor' are odd. 201 until ((cofactor = cofactor' = 4), oddDivisor is prime and oddDivisor' is prime) 202 3. Output d 204 GenerateCurveEdwards 206 5.2. Twisted Edwards Curves 208 For a prime p = 1 mod 4, the elliptic curve tEd in twisted Edwards 209 form is determined by the non-square element d from GF(p) (not equal 210 to -1 or zero) with smallest absolute value such that #tEd(GF(p)) = 211 cofactor * oddDivisor, #tEd'(GF(p)) = cofactor' * oddDivisor', 212 cofactor = 8, cofactor' = 4 and both subgroup orders oddDivisor and 213 oddDivisor' are prime. In addition, care must be taken to ensure the 214 MOV degree and CM discriminant requirements from Section 3 are met. 216 These cofactors are chosen so that they are minimal such that the 217 cofactor of the main curve is greater than the cofactor of the twist. 218 For 1 mod 4 primes, the cofactors are never equal. If the cofactor 219 of the twist is larger than the cofactor of the curve, algorithms may 220 be vulnerable to a small-subgroup attack if a point on the twist is 221 incorrectly accepted. 223 Input: a prime p, with p = 1 mod 4 224 Output: the parameter d defining the curve tEd 225 1. Set d = 0 226 2. repeat 227 repeat 228 if (d > 0) then 229 d = -d 230 else 231 d = -d + 1 232 end if 233 until d is not a square in GF(p) 235 Compute oddDivisor, oddDivisor', cofactor, cofactor' where #tEd(GF(p)) = 236 cofactor * oddDivisor, #tEd'(GF(p)) = cofactor' * oddDivisor', cofactor 237 and cofactor' are powers of 2 and oddDivisor, oddDivisor' are odd. 238 until (cofactor = 8 and cofactor' = 4 and rd is prime and rd' is prime) 239 3. Output d 241 GenerateCurveTEdwards 243 6. Recommended Curves 245 For the ~128-bit security level, the prime 2^255-19 is recommended 246 for performance on a wide-range of architectures. This prime is 247 congruent to 1 mod 4 and the above procedure results in the following 248 twisted Edwards curve, called "intermediate25519": 250 p 2^255-19 252 d 121665 254 order 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed 256 cofactor 8 258 In order to be compatible with widespread existing practice, the 259 recommended curve is an isogeny of this curve. An isogeny is a 260 "renaming" of the points on the curve and thus cannot affect the 261 security of the curve: 263 p 2^255-19 265 d 370957059346694393431380835087545651895421138798432190163887855330 266 85940283555 268 order 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed 270 cofactor 8 271 X(P) 151122213495354007725011514095885315114540126930418572060461132 272 83949847762202 274 Y(P) 463168356949264781694283940034751631413079938662562256157830336 275 03165251855960 277 The d value in this curve is much larger than the generated curve and 278 this might slow down some implementations. If this is a problem then 279 implementations are free to calculate on the original curve, with 280 small d, as the isogeny map can be merged into the affine transform 281 without any performance impact. 283 The latter curve is isomorphic to a Montgomery curve defined by v^2 = 284 u^3 + 486662u^2 + u where the maps are: 286 (u, v) = ((1+y)/(1-y), sqrt(-1)*sqrt(486664)*u/x) 287 (x, y) = (sqrt(-1)*sqrt(486664)*u/v, (u-1)/(u+1) 289 The base point maps onto the Montgomery curve such that u = 9, v = 14 290 781619447589544791020593568409986887264606134616475288964881837755586 291 237401. 293 The Montgomery curve defined here is equal to the one defined in 294 [curve25519] and the isomorphic twisted Edwards curve is equal to the 295 one defined in [ed25519]. 297 7. The curve25519 function 299 The "curve25519" function performs scalar multiplication on the 300 Montgomery form of the above curve. (This is used when implementing 301 Diffie-Hellman.) The function takes a scalar and a u-coordinate as 302 inputs and produces a u-coordinate as output. Although the function 303 works internally with integers, the inputs and outputs are 32-byte 304 strings and this specification defines their encoding. 306 U-coordinates are elements of the underlying field GF(2^255-19) and 307 are encoded as an array of bytes, u, in little-endian order such that 308 u[0] + 256 * u[1] + 256^2 * u[2] + ... + 256^n * u[n] is congruent to 309 the value modulo p and u[n] is minimal. When receiving such an 310 array, implementations MUST mask the most-significant bit in the 311 final byte. This is done to preserve compatibility with point 312 formats which reserve the sign bit for use in other protocols and to 313 increase resistance to implementation fingerprinting. 315 For example, the following functions implement this in Python, 316 although the Python code is not intended to be performant nor side- 317 channel free: 319 def decodeLittleEndian(b): 320 return sum([b[i] << 8*i for i in range(32)]) 322 def decodeUCoordinate(u): 323 u_list = [ord(b) for b in u] 324 u_list[31] &= 0x7f 325 return decodeLittleEndian(u_list) 327 def encodeUCoordinate(u): 328 u = u % p 329 return ''.join([chr((u >> 8*i) & 0xff) for i in range(32)]) 331 (EDITORS NOTE: draft-turner-thecurve25519function also says 332 "Implementations MUST reject numbers in the range [2^255-19, 333 2^255-1], inclusive." but I'm not aware of any implementations that 334 do so.) 336 Scalars are assumed to be randomly generated bytes. In order to 337 decode 32 bytes into an integer scalar, set the three least 338 significant bits of the first byte and the most significant bit of 339 the last to zero, set the second most significant bit of the last 340 byte to 1 and, finally, decode as little-endian. This means that 341 resulting integer is of the form 2^254 + 8 * {0, 1, ..., 2^(251) - 342 1}. 344 def decodeScalar(k): 345 k_list = [ord(b) for b in k] 346 k_list[0] &= 248 347 k_list[31] &= 127 348 k_list[31] |= 64 349 return decodeLittleEndian(k_list) 351 To implement the "curve25519(k, u)" function (where "k" is the scalar 352 and "u" is the u-coordinate) first decode "k" and "u" and then 353 perform the following procedure, taken from [curve25519] and based on 354 formulas from [montgomery]. All calculations are performed in GF(p), 355 i.e., they are performed modulo p. The constant a24 is (486662 - 2) 356 / 4 = 121665. 358 x_1 = u 359 x_2 = 1 360 z_2 = 0 361 x_3 = u 362 z_3 = 1 363 swap = 0 365 For t = 254 down to 0: 366 k_t = (k >> t) & 1 367 swap ^= k_t 368 // Conditional swap; see text below. 369 (x_2, x_3) = cswap(swap, x_2, x_3) 370 (z_2, z_3) = cswap(swap, z_2, z_3) 371 swap = k_t 373 A = x_2 + z_2 374 AA = A^2 375 B = x_2 - z_2 376 BB = B^2 377 E = AA - BB 378 C = x_3 + z_3 379 D = x_3 - z_3 380 DA = D * A 381 CB = C * B 382 x_3 = (DA + CB)^2 383 z_3 = x_1 * (DA - CB)^2 384 x_2 = AA * BB 385 z_2 = E * (AA + a24 * E) 387 // Conditional swap; see text below. 388 (x_2, x_3) = cswap(swap, x_2, x_3) 389 (z_2, z_3) = cswap(swap, z_2, z_3) 390 Return x_2 * (z_2^(p - 2)) 392 (TODO: Note the difference in the formula from Montgomery's original 393 paper. See https://www.ietf.org/mail-archive/web/cfrg/current/ 394 msg05872.html.) 396 Finally, encode the resulting value as 32 bytes in little-endian 397 order. 399 When implementing this procedure, due to the existence of side- 400 channels in commodity hardware, it is important that the pattern of 401 memory accesses and jumps not depend on the values of any of the bits 402 of "k". It is also important that the arithmetic used not leak 403 information about the integers modulo p (such as having b*c be 404 distinguishable from c*c). 406 The cswap instruction SHOULD be implemented in constant time 407 (independent of "swap") as follows: 409 cswap(swap, x_2, x_3): 410 dummy = swap * (x_2 - x_3) 411 x_2 = x_2 - dummy 412 x_3 = x_3 + dummy 413 Return (x_2, x_3) 415 where "swap" is 1 or 0. Alternatively, an implementation MAY use the 416 following: 418 cswap(swap, x_2, x_3): 419 dummy = mask(swap) AND (x_2 XOR x_3) 420 x_2 = x_2 XOR dummy 421 x_3 = x_3 XOR dummy 422 Return (x_2, x_3) 424 where "mask(swap)" is the all-1 or all-0 word of the same length as 425 x_2 and x_3, computed, e.g., as mask(swap) = 1 - swap. The latter 426 version is often more efficient. 428 7.1. Test vectors 430 Input scalar: 431 a546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4 432 Input scalar as a number (base 10): 433 31029842492115040904895560451863089656472772604678260265531221036453811406496 434 Input U-coordinate: 435 e6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c 436 Input U-coordinate as a number: 437 34426434033919594451155107781188821651316167215306631574996226621102155684838 438 Output U-coordinate: 439 c3da55379de9c6908e94ea4df28d084f32eccf03491c71f754b4075577a28552 441 Input scalar: 442 4b66e9d4d1b4673c5ad22691957d6af5c11b6421e0ea01d42ca4169e7918ba0d 443 Input scalar as a number (base 10): 444 35156891815674817266734212754503633747128614016119564763269015315466259359304 445 Input U-coordinate: 446 e5210f12786811d3f4b7959d0538ae2c31dbe7106fc03c3efc4cd549c715a493 447 Input U-coordinate as a number: 448 8883857351183929894090759386610649319417338800022198945255395922347792736741 449 Output U-coordinate: 450 95cbde9476e8907d7aade45cb4b873f88b595a68799fa152e6f8f7647aac7957 452 8. Diffie-Hellman 454 The "curve25519" function can be used in an ECDH protocol as follows: 456 Alice generates 32 random bytes in f[0] to f[31] and transmits K_A = 457 curve25519(f, 9) to Bob, where 9 is the u-coordinate of the base 458 point and is encoded as a byte with value 9, followed by 31 zero 459 bytes. 461 Bob similarly generates 32 random bytes in g[0] to g[31] and computes 462 K_B = curve25519(g, 9) and transmits it to Alice. 464 Alice computes curve25519(f, K_B); Bob computes curve25519(g, K_A) 465 using their generated values and the received input. 467 Both now share K = curve25519(f, curve25519(g, 9)) = curve25519(g, 468 curve25519(f, 9)) as a shared secret. Alice and Bob can then use a 469 key-derivation function, such as hashing K, to compute a key. 471 Note that this Diffie-Hellman protocol is not contributory, e.g. if 472 the u-coordinate is zero then the output will always be zero. A 473 contributory Diffie-Hellman function would ensure that the output was 474 unpredictable no matter what the peer's input. This is not a problem 475 for the vast majority of cases but, if a contributory function is 476 specifically required, then "curve25519" should not be used. 478 8.1. Test vectors 480 Alice's private key, f: 481 77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a 482 Alice's public key, curve25519(f, 9): 483 8520f0098930a754748b7ddcb43ef75a0dbf3a0d26381af4eba4a98eaa9b4e6a 484 Bob's private key, g: 485 5dab087e624a8a4b79e17f8b83800ee66f3bb1292618b6fd1c2f8b27ff88e0eb 486 Bob's public key, curve25519(g, 9): 487 de9edb7d7b7dc1b4d35b61c2ece435373f8343c85b78674dadfc7e146f882b4f 488 Their shared secret, K: 489 4a5d9d5ba4ce2de1728e3bf480350f25e07e21c947d19e3376f09b3c1e161742 491 9. Acknowledgements 493 This document merges "draft-black-rpgecc-01" and "draft-turner- 494 thecurve25519function-01". The following authors of those documents 495 wrote much of the text and figures but are not listed as authors on 496 this document: Benjamin Black, Joppe W. Bos, Craig Costello, Patrick 497 Longa, Michael Naehrig and Watson Ladd. 499 The authors would also like to thank Tanja Lange and Rene Struik for 500 their reviews. 502 10. References 504 10.1. Normative References 506 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 507 Requirement Levels", BCP 14, RFC 2119, March 1997. 509 10.2. Informative References 511 [AS] Satoh, T. and K. Araki, "Fermat quotients and the 512 polynomial time discrete log algorithm for anomalous 513 elliptic curves", 1998. 515 [EBP] ECC Brainpool, "ECC Brainpool Standard Curves and Curve 516 Generation", October 2005, . 519 [NIST] National Institute of Standards, "Recommended Elliptic 520 Curves for Federal Government Use", July 1999, 521 . 524 [S] Semaev, I., "Evaluation of discrete logarithms on some 525 elliptic curves", 1998. 527 [SC] Bernstein, D. and T. Lange, "SafeCurves: choosing safe 528 curves for elliptic-curve cryptography", June 2014, 529 . 531 [SEC1] Certicom Research, "SEC 1: Elliptic Curve Cryptography", 532 September 2000, 533 . 535 [Smart] Smart, N., "The discrete logarithm problem on elliptic 536 curves of trace one", 1999. 538 [curve25519] 539 Bernstein, D., "Curve25519 -- new Diffie-Hellman speed 540 records", 2006, 541 . 544 [ed25519] Bernstein, D., Duif, N., Lange, T., Schwabe, P., and B. 545 Yang, "High-speed high-security signatures", 2011, 546 . 548 [montgomery] 549 Montgomery, P., "Speeding the Pollard and elliptic curve 550 methods of factorization", 1983, 551 . 554 Authors' Addresses 556 Adam Langley 557 Google 558 345 Spear St 559 San Francisco, CA 94105 560 US 562 Email: agl@google.com 564 Rich Salz 565 Akamai Technologies 566 8 Cambridge Center 567 Cambridge, MA 02142 568 US 570 Email: rsalz@akamai.com 572 Sean Turner 573 IECA, Inc. 574 3057 Nutley Street 575 Suite 106 576 Fairfax, VA 22031 577 US 579 Email: turners@ieca.com