idnits 2.17.1 draft-turner-thecurve25519function-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 (August 12, 2014) is 3545 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 210 -- Looks like a reference, but probably isn't: '31' on line 210 -- Looks like a reference, but probably isn't: '1' on line 114 -- Looks like a reference, but probably isn't: '2' on line 114 Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group W. Ladd 3 Internet-Draft Grad Student UC Berkley 4 Intended status: Informational R. Salz 5 Expires: February 13, 2015 Akamai Technologies 6 S. Turner 7 IECA, Inc. 8 August 12, 2014 10 The Curve25519 Function 11 draft-turner-thecurve25519function-01 13 Abstract 15 This document specifies the Curve25519 function, an ECDH (Elliptic- 16 Curve Diffie-Hellman) key-agreement scheme for use in cryptographic 17 applications. It was designed with performance and security in mind. 18 This document is based on information in the public domain. 20 Status of This Memo 22 This Internet-Draft is submitted in full conformance with the 23 provisions of BCP 78 and BCP 79. 25 Internet-Drafts are working documents of the Internet Engineering 26 Task Force (IETF). Note that other groups may also distribute 27 working documents as Internet-Drafts. The list of current Internet- 28 Drafts is at http://datatracker.ietf.org/drafts/current/. 30 Internet-Drafts are draft documents valid for a maximum of six months 31 and may be updated, replaced, or obsoleted by other documents at any 32 time. It is inappropriate to use Internet-Drafts as reference 33 material or to cite them other than as "work in progress." 35 This Internet-Draft will expire on February 13, 2015. 37 Copyright Notice 39 Copyright (c) 2014 IETF Trust and the persons identified as the 40 document authors. All rights reserved. 42 This document is subject to BCP 78 and the IETF Trust's Legal 43 Provisions Relating to IETF Documents 44 (http://trustee.ietf.org/license-info) in effect on the date of 45 publication of this document. Please review these documents 46 carefully, as they describe your rights and restrictions with respect 47 to this document. Code Components extracted from this document must 48 include Simplified BSD License text as described in Section 4.e of 49 the Trust Legal Provisions and are provided without warranty as 50 described in the Simplified BSD License. 52 1. Introduction 54 This document specifies the Curve25519 function, an ECDH (Elliptic- 55 curve Diffie-Hellman) key-agreement scheme for use in cryptographic 56 applications. It was designed with performance and security in mind. 57 This document is based on information in the public domain. 59 This document provides a stable reference for the Curve25519 function 60 [Curve25519] to which other specifications may refer when defining 61 their use of Curve25519. It specifies how to use Curve25519 for key 62 exchange. This document defines the algorithm, the "wire format" 63 (how to serialize and parse bytes sent over a network, for example), 64 and provides some implementation guidance to avoid known side-channel 65 timing exposures. 67 This document does not specify the use of Curve25519 in any other 68 specific protocol, such as TLS (Transport Layer Security) or IPsec 69 (Internet Protocol Security). It does not specify how to use 70 Curve25519 for digital signatures. 72 Readers are assumed to be familiar with the concepts of elliptic 73 curves, modular arithmetic, group operations, and finite fields 74 [RFC6090] as well as rings [Curve25519]. 76 1.1. Terminology 78 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 79 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 80 document are to be interpreted as described in [RFC2119]. 82 2. Notation and Definitions 84 The following notation and definitions are used in this document 85 (notation is to the left of the ":"): 87 A: A value used in the elliptic-curve equation E. 89 E: An elliptic-curve equation. 91 p: A prime. 93 GF(p): The field with p elements. 95 _#: Subscript notation, where # is a number or letter. 97 Q 99 =: Assignment. 101 ^: Exponentiation. 103 +, -, *, /: Addition, subtraction, multiplication, and division, 104 respectively. 106 Note that all operations are performed modulo p. 108 3. The Curve25519 Function 110 Let p = 2^255 - 19. Let E be the elliptic curve with the equation 111 y^2 = x^3 + 486662 * x^2 + x over GF(p). 113 Each element x of GF(p) has a unique little-endian representation as 114 32 bytes x[0] ... x[31], such that x[0] + 256 * x[1] + 256^2 * x[2] + 115 ... + 256^31 * x[31] is congruent to x modulo p, and x[31] is 116 minimal. Implementations MUST only produce points in this form. On 117 receiving a point, implementations MUST mask the leftmost bit of byte 118 31 to zero. This is done to preserve compatibility with point 119 formats which reserve the sign bit for use in other protocols and 120 increase resistance to implementation fingerprinting. 121 Implementations MUST reject numbers in the range [2^255-19, 2^255-1], 122 inclusive. 124 Let X denote the projection map from a point (x,y) on E, to x, 125 extended so that X of the point at infinity is zero. X is surjective 126 onto GF(p) if the y coordinate takes on values in GF(p) and in a 127 quadratic extension of GF(p). 129 Then Curve25519(s, X(Q)) = X(sQ) is a function defined for all 130 integers s and elements X(Q) of GF(p). Proper implementations use a 131 restricted set of integers for s and only x-coordinates of points Q 132 defined over GF(p). The remainder of this document describes how to 133 compute this function quickly and securely, and use it in a Diffie- 134 Hellman scheme. 136 4. Implementing the Curve25519 Function 138 Let s be a 255 bits long integer, where 139 s = sum s_i * 2^i with s_i in {0, 1}. 141 Computing Curve25519(s, x) is done by the following procedure, taken 142 from [Curve25519] based on formulas from [Mont]. All calculations 143 are performed in GF(p), i.e., they are performed modulo p. The 144 parameter a24 is a24 = (486662 - 2) / 4 = 121665. 146 x_1 = x 147 x_2 = 0 148 z_2 = 1 149 x_3 = x 150 z_3 = 1 151 For t = 254 down to 0: 152 // Conditional swap; see text below. 153 (x_2, x_3) = cswap (s_t, x_2, x_3) 154 (z_2, z_3) = cswap (s_t, z_2, z_3) 155 A = x_2 + z_2 156 AA = A^2 157 B = x_2 - z_2 158 BB = B^2 159 E = AA - BB 160 C = x_3 + z_3 161 D = x_3 - z_3 162 DA = D * A 163 CB = C * B 164 x_3 = (DA + CB)^2 165 z_3 = x_1 * (DA - CB)^2 166 x_2 = AA * BB 167 z_2 = E * (AA + a24 * E) 168 // Conditional swap; see text below. 169 (x_2, x_3) = cswap (s_t, x_2, x_3) 170 (z_2, z_3) = cswap (s_t, z_2, z_3) 171 Return x_2 * (z_2^(p - 1)) 173 In implementing this procedure, due to the existence of side-channels 174 in commodity hardware, it is important that the pattern of memory 175 accesses and jumps not depend on the values of any of the bits of s. 176 It is also important that the arithmetic used not leak information 177 about the integers modulo p (such as having b * c distinguishable 178 from c * c). 180 The cswap instruction SHOULD be implemented in constant time 181 (independent of s_t) as follows: 183 cswap(s_t, x_2, x_3) dummy = s_t * (x_2 - x_3) x_2 = x_2 - dummy x_3 184 = x_3 + dummy Return (x_2, x_3) 186 where s_t is 1 or 0. Alternatively, an implementation MAY use the 187 following: 189 dummy = mask(s_t) AND (x_2 XOR x_3) 190 x_2 = x_2 XOR dummy 191 x_3 = x_3 XOR dummy 193 where mask(s_t) is the all-1 or all-0 word of the same length as x_2 194 and x_3, computed, e.g., as mask(s_t) = 1 - s_t. The latter version 195 is often more efficient. 197 5. Use of the Curve25519 function 199 The Curve25519 function can be used in an ECDH protocol as follows: 201 Alice generates 32 random bytes in f[0] to f[31]. She masks the 202 three rightmost bits of f[0] and the leftmost bit of f[31] to zero 203 and sets the second leftmost bit of f[31] to 1. This means that f is 204 of the form 2^254 + 8 * {0, 1, ..., 2^(251) - 1} as a little-endian 205 integer. 207 Alice then transmits K_A = Curve25519(f, 9) to Bob, where 9 is the 208 number 9. 210 Bob similarly generates 32 random bytes in g[0] to g[31], applies the 211 same masks, computes K_B = Curve25519(g, 9) and transmits it to 212 Alice. 214 Alice computes Curve25519(f, Curve25519(g, 9)); Bob computes 215 Curve25519(g, Curve25519(f, 9)) using their generated values and the 216 received input. 218 Both of them now share K = Curve25519(f, Curve25519(g, 9)) = 219 Curve25519(g, Curve25519(f, 9)) as a shared secret. Alice and Bob 220 can then use a key-derivation function, such as hashing K, to compute 221 a key. 223 6. Test Vectors 225 The following test vectors are taken from [NaCl]. All numbers are 226 shown as little-endian hexadecimal byte strings: 228 Alice's private key, f: 230 77 07 6d 0a 73 18 a5 7d 3c 16 c1 72 51 b2 66 45 231 df 4c 2f 87 eb c0 99 2a b1 77 fb a5 1d b9 2c 2a 233 Alice's public key, Curve25519(f, 9): 235 85 20 f0 09 89 30 a7 54 74 8b 7d dc b4 3e f7 5a 236 0d bf 3a 0d 26 38 1a f4 eb a4 a9 8e aa 9b 4e 6a 238 Bob's private key, g: 240 5d ab 08 7e 62 4a 8a 4b 79 e1 7f 8b 83 80 0e e6 241 6f 3b b1 29 26 18 b6 fd 1c 2f 8b 27 ff 88 e0 eb 243 Bob's public key, Curve25519(g, 9): 245 de 9e db 7d 7b 7d c1 b4 d3 5b 61 c2 ec e4 35 37 246 3f 83 43 c8 5b 78 67 4d ad fc 7e 14 6f 88 2b 4f 248 Their shared secret, K: 250 4a 5d 9d 5b a4 ce 2d e1 72 8e 3b f4 80 35 0f 25 251 e0 7e 21 c9 47 d1 9e 33 76 f0 9b 3c 1e 16 17 42 253 7. Security Considerations 255 Curve25519 meets all standard assumptions on DH and DLP difficulty. 257 In addition, Curve25519 is twist secure: the co-factor of the curve 258 is 8, that of the twist is 4. Protocols that require contributory 259 behavior must ban outputs K_A = 0, K_B = 0 or K = 0. 261 Curve25519 is designed to enable very high performance software 262 implementations, thus reducing the cost of highly secure cryptography 263 to a point where it can be used more widely. 265 8. IANA Considerations 267 None. 269 9. Acknowledgements 271 We would like to thank Tanja Lange (Technische Universiteit 272 Eindhoven) for her review and comments. 274 10. References 276 10.1. Normative References 278 [Curve25519] 279 Bernstein, D., "Curve25519 - new Diffie-Hellman speed 280 records", April 2006, 281 . 284 [Mont] Montgomery, P., "Speeding the Pollard and elliptic curve 285 methods of factorization", 1983, 286 . 289 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 290 Requirement Levels", BCP 14, RFC 2119, March 1997. 292 [RFC6090] McGrew, D., Igoe, K., and M. Salter, "Fundamental Elliptic 293 Curve Cryptography Algorithms", RFC 6090, February 2011. 295 10.2. Informative References 297 [NaCl] Bernstein, D., "Cryptography in NaCl", 2013, 298 . 300 Authors' Addresses 302 Watson Ladd 303 Grad Student UC Berkley 305 Email: watsonbladd@gmail.com 307 Rich Salz 308 Akamai Technologies 309 8 Cambridge Center 310 Cambridge, MA 02142 311 USA 313 Phone: +1-617-714-6169 314 Email: rsalz@akamai.com 316 Sean Turner 317 IECA, Inc. 318 Suite 106 319 Fairfax, VA 22031 320 USA 322 Phone: +1-703-628-3180 323 Email: turners@ieca.com