idnits 2.17.1 draft-irtf-cfrg-spake2-07.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 (November 4, 2018) is 1993 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: '-1' is mentioned on line 273, but not defined -- Looks like a reference, but probably isn't: '0' on line 275 Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group W. Ladd 3 Internet-Draft UC Berkeley 4 Intended status: Informational B. Kaduk, Ed. 5 Expires: May 8, 2019 Akamai 6 November 4, 2018 8 SPAKE2, a PAKE 9 draft-irtf-cfrg-spake2-07 11 Abstract 13 This document describes SPAKE2, a means for two parties that share a 14 password to derive a strong shared key with no risk of disclosing the 15 password. This method is compatible with any group, is 16 computationally efficient, and has a security proof. 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 https://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 May 8, 2019. 35 Copyright Notice 37 Copyright (c) 2018 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 (https://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 Table of Contents 52 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 53 2. Requirements Notation . . . . . . . . . . . . . . . . . . . . 2 54 3. Definition of SPAKE2 . . . . . . . . . . . . . . . . . . . . 2 55 4. Table of points for common groups . . . . . . . . . . . . . . 4 56 5. Security Considerations . . . . . . . . . . . . . . . . . . . 7 57 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7 58 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 8 59 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 60 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9 62 1. Introduction 64 This document describes SPAKE2, a means for two parties that share a 65 password to derive a strong shared key with no risk of disclosing the 66 password. This password-based key exchange protocol is compatible 67 with any group (requiring only a scheme to map a random input of 68 fixed length per group to a random group element), is computationally 69 efficient, and has a security proof. Predetermined parameters for a 70 selection of commonly used groups are also provided for use by other 71 protocols. 73 2. Requirements Notation 75 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 76 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 77 "OPTIONAL" in this document are to be interpreted as described in BCP 78 14 [RFC2119] [RFC8174] when, and only when, they appear in all 79 capitals, as shown here. 81 3. Definition of SPAKE2 83 3.1. Setup 85 Let G be a group in which the Diffie-Hellman (DH) problem is hard of 86 order p*h, with p a big prime and h a cofactor. We denote the 87 operations in the group additively. Let H be a hash function from 88 arbitrary strings to bit strings of a fixed length. Common choices 89 for H are SHA256 or SHA512 [RFC6234]. We assume there is a 90 representation of elements of G as byte strings: common choices would 91 be SEC1 compressed [SEC1] for elliptic curve groups or big endian 92 integers of a fixed (per-group) length for prime field DH. 94 || denotes concatenation of strings. We also let len(S) denote the 95 length of a string in bytes, represented as an eight-byte little- 96 endian number. 98 We fix two elements M and N as defined in the table in this document 99 for common groups, as well as a generator G of the group. G is 100 specified in the document defining the group, and so we do not repeat 101 it here. 103 Let A and B be two parties. We will assume that A and B also have 104 digital representations of the parties' identities such as MAC 105 addresses or other names (hostnames, usernames, etc). We assume they 106 share an integer w; typically w will be the hash of a user-supplied 107 password, truncated and taken mod p. Protocols using this 108 specification must define the method used to compute w: it may be 109 necessary to carry out various forms of normalization of the password 110 before hashing. [RFC8265] The hashing algorithm SHOULD be designed 111 to slow down brute-force attackers. 113 We present two protocols below. Note that it is insecure to use the 114 same password with both protocols; passwords MUST NOT be used for 115 both SPAKE2 and SPAKE2+. 117 3.2. SPAKE2 119 A picks x randomly and uniformly from the integers in [0,ph) 120 divisible by h, and calculates X=x*G and T=w*M+X, then transmits T to 121 B. 123 B selects y randomly and uniformly from the integers in [0,p*h), 124 divisible by h and calculates Y=y*G, S=w*N+Y, then transmits S to A. 126 Both A and B calculate a group element K. A calculates it as 127 x(S-wN), while B calculates it as y(T-w*M). A knows S because it has 128 received it, and likewise B knows T. 130 This K is a shared value, but the scheme as described is not secure. 131 K MUST be combined with the values transmitted and received via a 132 hash function to prevent man-in-the-middle attackers from being able 133 to insert themselves into the exchange. Higher-level protocols 134 SHOULD prescribe a method for incorporating a "transcript" of the 135 exchanged values and endpoint identity information into the shared 136 secret. One such approach would be to compute a K' as H(len(A) || 137 A || len(B) || B || len(S) || S || len(T) || T || len(K) || K || 138 len(w) || w) and use K' as the key. 140 3.3. SPAKE2+ 142 This protocol appears in [TDH]. We use the same setup as for SPAKE2, 143 except that we have two secrets, w0 and w1, derived by hashing the 144 password with the identities of the two participants. B stores 145 L=w1*g and w0. 147 When executing SPAKE2+, A selects x uniformly at random from the 148 numbers in the range [0, p*h) divisible by h, and lets X=x*G+w0*M, 149 then transmits X to B. B selects y uniformly at random from the 150 numbers in [0, p*h) divisible by h, then computes Y=y*G+w0*N, and 151 transmits it to Alice. 153 A computes Z as x(Y-w0*N), and V as w1(Y-w0*N). B computes Z as y(X- 154 w0*M) and V as y*L. Both share Z and V as common keys. It is 155 essential that both Z and V be used in combination with the 156 transcript to derive the keying material. For higher-level protocols 157 without sufficient transcript hashing, let K' be H(len(A) || A || 158 len(B) || B || len(X) || X || len(Y) || Y || len(Z) || Z || len(V) || 159 V || len(w0) || w0) and use K' as the established key. 161 4. Table of points for common groups 163 For each curve in the table below, we construct a string using the 164 curve OID from [RFC5480] (as an ASCII string) or its name, combined 165 with the needed constant, for instance "1.3.132.0.35 point generation 166 seed (M)" for P-512. This string is turned into a series of blocks 167 by hashing with SHA256, and hashing that output again to generate the 168 next 32 bytes, and so on. This pattern is repeated for each group 169 and value, with the string modified appropriately. 171 A byte string of length equal to that of an encoded group element is 172 constructed by concatenating as many blocks as are required, starting 173 from the first block, and truncating to the desired length. The byte 174 string is then formatted as required for the group. In the case of 175 Weierstrass curves, we take the desired length as the length for 176 representing a compressed point (section 2.3.4 of [SEC1]), and use 177 the low-order bit of the first byte as the sign bit. In order to 178 obtain the correct format, the value of the first byte is set to 0x02 179 or 0x03 (clearing the first six bits and setting the seventh bit), 180 leaving the sign bit as it was in the byte string constructed by 181 concatenating hash blocks. For the [RFC8032] curves a different 182 procedure is used. For edwards448 the 57-byte input has the least- 183 significant 7 bits of the last byte set to zero, and for edwards25519 184 the 32-byte input is not modified. For both the [RFC8032] curves the 185 (modified) input is then interpreted as the representation of the 186 group element. If this interpretation yields a valid group element 187 with the correct order (p), the (modified) byte string is the output. 188 Otherwise, the initial hash block is discarded and a new byte string 189 constructed from the remaining hash blocks. The procedure of 190 constructing a byte string of the appropriate length, formatting it 191 as required for the curve, and checking if it is a valid point of the 192 correct order, is repeated until a valid element is found. 194 These bytestrings are compressed points as in [SEC1] for curves from 195 [SEC1]. 197 For P256: 199 M = 200 02886e2f97ace46e55ba9dd7242579f2993b64e16ef3dcab95afd497333d8fa12f 201 seed: 1.2.840.10045.3.1.7 point generation seed (M) 203 N = 204 03d8bbd6c639c62937b04d997f38c3770719c629d7014d49a24b4f98baa1292b49 205 seed: 1.2.840.10045.3.1.7 point generation seed (N) 207 For P384: 209 M = 210 030ff0895ae5ebf6187080a82d82b42e2765e3b2f8749c7e05eba366434b363d3dc 211 36f15314739074d2eb8613fceec2853 212 seed: 1.3.132.0.34 point generation seed (M) 214 N = 215 02c72cf2e390853a1c1c4ad816a62fd15824f56078918f43f922ca21518f9c543bb 216 252c5490214cf9aa3f0baab4b665c10 217 seed: 1.3.132.0.34 point generation seed (N) 219 For P521: 221 M = 222 02003f06f38131b2ba2600791e82488e8d20ab889af753a41806c5db18d37d85608 223 cfae06b82e4a72cd744c719193562a653ea1f119eef9356907edc9b56979962d7aa 224 seed: 1.3.132.0.35 point generation seed (M) 226 N = 227 0200c7924b9ec017f3094562894336a53c50167ba8c5963876880542bc669e494b25 228 32d76c5b53dfb349fdf69154b9e0048c58a42e8ed04cef052a3bc349d95575cd25 229 seed: 1.3.132.0.35 point generation seed (N) 231 For edwards25519: 233 M = 234 d048032c6ea0b6d697ddc2e86bda85a33adac920f1bf18e1b0c6d166a5cecdaf 235 seed: edwards25519 point generation seed (M) 237 N = 238 d3bfb518f44f3430f29d0c92af503865a1ed3281dc69b35dd868ba85f886c4ab 239 seed: edwards25519 point generation seed (N) 241 For edwards448: 243 M = 244 b6221038a775ecd007a4e4dde39fd76ae91d3cf0cc92be8f0c2fa6d6b66f9a12 245 942f5a92646109152292464f3e63d354701c7848d9fc3b8880 246 seed: edwards448 point generation seed (M) 248 N = 249 6034c65b66e4cd7a49b0edec3e3c9ccc4588afd8cf324e29f0a84a072531c4db 250 f97ff9af195ed714a689251f08f8e06e2d1f24a0ffc0146600 251 seed: edwards448 point generation seed (N) 253 The following python snippet generates the above points, assuming an 254 elliptic curve implementation following the interface of 255 Edwards25519Point.stdbase() and Edwards448Point.stdbase() in 256 [RFC8032] appendix A: 258 def iterated_hash(seed, n): 259 h = seed 260 for i in range(n): 261 h = hashlib.sha256(h).digest() 262 return h 264 def bighash(seed, start, sz): 265 n = -(-sz // 32) 266 hashes = [iterated_hash(seed, i) for i in range(start, start + n)] 267 return b''.join(hashes)[:sz] 269 def canon_pointstr(ecname, s): 270 if ecname == 'edwards25519': 271 return s 272 elif ecname == 'edwards448': 273 return s[:-1] + bytes([s[-1] & 0x80]) 274 else: 275 return bytes([(s[0] & 1) | 2]) + s[1:] 277 def gen_point(seed, ecname, ec): 278 for i in range(1, 1000): 279 hval = bighash(seed, i, len(ec.encode())) 280 pointstr = canon_pointstr(ecname, hval) 281 try: 282 p = ec.decode(pointstr) 283 if p != ec.zero_elem() and p * p.l() == ec.zero_elem(): 284 return pointstr, i 285 except Exception: 286 pass 288 5. Security Considerations 290 A security proof of SPAKE2 for prime order groups is found in [REF]. 291 Note that the choice of M and N is critical for the security proof. 292 The generation method specified in this document is designed to 293 eliminate concerns related to knowing discrete logs of M and N. 295 SPAKE2+ appears in [TDH] along with a path to a proof that server 296 compromise does not lead to password compromise under the DH 297 assumption (though the corresponding model excludes precomputation 298 attacks). 300 There is no key-confirmation as this is a one-round protocol. It is 301 expected that a protocol using this key exchange mechanism will 302 provide key confirmation separately if desired. 304 Elements received from a peer MUST be checked for group membership: 305 failure to properly validate group elements can lead to attacks. In 306 particular it is essential to verify that received points are valid 307 compressions of points on an elliptic curve when using elliptic 308 curves. It is not necessary to validate membership in the prime 309 order subgroup: the multiplication by cofactors eliminates the 310 potential for mebership in a small-order subgroup. 312 The choices of random numbers MUST BE uniform. Note that to pick a 313 random multiple of h in [0, p*h) one can pick a random integer in [0, 314 p) and multiply by h. Ephemeral values MUST NOT be reused; such 315 reuse permits dictionary attacks on the password. 317 SPAKE2 does not support augmentation. As a result, the server has to 318 store a password equivalent. This is considered a significant 319 drawback, and so SPAKE2+ also appears in this document. 321 As specified, the shared secret K is not suitable for direct use as a 322 shared key. It MUST be passed to a hash function along with the 323 public values used to derive it and the identities of the 324 participating parties in order to avoid attacks. In protocols which 325 do not perform this separately, the value denoted K' MUST be used 326 instead of K. 328 6. IANA Considerations 330 No IANA action is required. 332 7. Acknowledgments 334 Special thanks to Nathaniel McCallum and Greg Hudson for generation 335 of test vectors. Thanks to Mike Hamburg for advice on how to deal 336 with cofactors. Greg Hudson also suggested the addition of warnings 337 on the reuse of x and y. Thanks to Fedor Brunner, Adam Langley, and 338 the members of the CFRG for comments and advice. Trevor Perrin 339 informed me of SPAKE2+. 341 8. References 343 8.1. Normative References 345 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 346 Requirement Levels", BCP 14, RFC 2119, 347 DOI 10.17487/RFC2119, March 1997, 348 . 350 [RFC5480] Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk, 351 "Elliptic Curve Cryptography Subject Public Key 352 Information", RFC 5480, DOI 10.17487/RFC5480, March 2009, 353 . 355 [RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms 356 (SHA and SHA-based HMAC and HKDF)", RFC 6234, 357 DOI 10.17487/RFC6234, May 2011, 358 . 360 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 361 Signature Algorithm (EdDSA)", RFC 8032, 362 DOI 10.17487/RFC8032, January 2017, 363 . 365 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 366 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 367 May 2017, . 369 [SEC1] SEC, "STANDARDS FOR EFFICIENT CRYPTOGRAPHY, "SEC 1: 370 Elliptic Curve Cryptography", version 2.0", May 2009. 372 8.2. Informative References 374 [REF] Abdalla, M. and D. Pointcheval, "Simple Password-Based 375 Encrypted Key Exchange Protocols.", Feb 2005. 377 Appears in A. Menezes, editor. Topics in Cryptography- 378 CT-RSA 2005, Volume 3376 of Lecture Notes in Computer 379 Science, pages 191-208, San Francisco, CA, US. Springer- 380 Verlag, Berlin, Germany. 382 [RFC8265] Saint-Andre, P. and A. Melnikov, "Preparation, 383 Enforcement, and Comparison of Internationalized Strings 384 Representing Usernames and Passwords", RFC 8265, 385 DOI 10.17487/RFC8265, October 2017, 386 . 388 [TDH] Cash, D., Kiltz, E., and V. Shoup, "The Twin-Diffie 389 Hellman Problem and Applications", 2008. 391 EUROCRYPT 2008. Volume 4965 of Lecture notes in Computer 392 Science, pages 127-145. Springer-Verlag, Berlin, Germany. 394 Authors' Addresses 396 Watson Ladd 397 UC Berkeley 399 Email: watsonbladd@gmail.com 401 Benjamin Kaduk (editor) 402 Akamai Technologies 404 Email: kaduk@mit.edu