idnits 2.17.1 draft-irtf-cfrg-spake2-06.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 15, 2018) is 2052 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: '-1' is mentioned on line 272, but not defined -- Looks like a reference, but probably isn't: '0' on line 274 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: February 16, 2019 Akamai 6 August 15, 2018 8 SPAKE2, a PAKE 9 draft-irtf-cfrg-spake2-06 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 strong 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 February 16, 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 . . . . . . . . . . . . . . . . . . . . . . . 7 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 strong security proof. Predetermined parameters 70 for a selection of commonly used groups are also provided for use by 71 other 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 and security proof appear in [TDH]. We use the same 143 setup as for SPAKE2, except that we have two secrets, w0 and w1. B 144 stores L=w1*g and w0. 146 When executing SPAKE2+, A selects x uniformly at random from the 147 numbers in the range [0, p*h) divisible by h, and lets X=x*G+w0*M, 148 then transmits X to B. B selects y uniformly at random from the 149 numbers in [0, p*h) divisible by h, then computes Y=y*G+w0*N, and 150 transmits it to Alice. 152 A computes Z as x(Y-w0*N), and V as w1(Y-w0*N). B computes Z as y(X- 153 w0*M) and V as y*L. Both share Z and V as common keys. It is 154 essential that both Z and V be used in combination with the 155 transcript to derive the keying material. For higher-level protocols 156 without sufficient transcript hashing, let K' be H(len(A) || A || 157 len(B) || B || len(X) || X || len(Y) || Y || len(Z) || Z || len(V) || 158 V || len(w0) || w0) and use K' as the established key. 160 4. Table of points for common groups 162 For each curve in the table below, we construct a string using the 163 curve OID from [RFC5480] (as an ASCII string) or its name, combined 164 with the needed constant, for instance "1.3.132.0.35 point generation 165 seed (M)" for P-512. This string is turned into a series of blocks 166 by hashing with SHA256, and hashing that output again to generate the 167 next 32 bytes, and so on. This pattern is repeated for each group 168 and value, with the string modified appropriately. 170 A byte string of length equal to that of an encoded group element is 171 constructed by concatenating as many blocks as are required, starting 172 from the first block, and truncating to the desired length. The byte 173 string is then formatted as required for the group. In the case of 174 Weierstrass curves, we take the desired length as the length for 175 representing a compressed point (section 2.3.4 of [SEC1]), and use 176 the low-order bit of the first byte as the sign bit. In order to 177 obtain the correct format, the value of the first byte is set to 0x02 178 or 0x03 (clearing the first six bits and setting the seventh bit), 179 leaving the sign bit as it was in the byte string constructed by 180 concatenating hash blocks. For the [RFC8032] curves a different 181 procedure is used. For edwards448 the 57-byte input has the least- 182 significant 7 bits of the last byte set to zero, and for edwards25519 183 the 32-byte input is not modified. For both the [RFC8032] curves the 184 (modified) input is then interpreted as the representation of the 185 group element. If this interpretation yields a valid group element 186 with the correct order (p), the (modified) byte string is the output. 187 Otherwise, the initial hash block is discarded and a new byte string 188 constructed from the remaining hash blocks. The procedure of 189 constructing a byte string of the appropriate length, formatting it 190 as required for the curve, and checking if it is a valid point of the 191 correct order, is repeated until a valid element is found. 193 These bytestrings are compressed points as in [SEC1] for curves from 194 [SEC1]. 196 For P256: 198 M = 199 02886e2f97ace46e55ba9dd7242579f2993b64e16ef3dcab95afd497333d8fa12f 200 seed: 1.2.840.10045.3.1.7 point generation seed (M) 202 N = 203 03d8bbd6c639c62937b04d997f38c3770719c629d7014d49a24b4f98baa1292b49 204 seed: 1.2.840.10045.3.1.7 point generation seed (N) 206 For P384: 208 M = 209 030ff0895ae5ebf6187080a82d82b42e2765e3b2f8749c7e05eba366434b363d3dc 210 36f15314739074d2eb8613fceec2853 211 seed: 1.3.132.0.34 point generation seed (M) 213 N = 214 02c72cf2e390853a1c1c4ad816a62fd15824f56078918f43f922ca21518f9c543bb 215 252c5490214cf9aa3f0baab4b665c10 216 seed: 1.3.132.0.34 point generation seed (N) 218 For P521: 220 M = 221 02003f06f38131b2ba2600791e82488e8d20ab889af753a41806c5db18d37d85608 222 cfae06b82e4a72cd744c719193562a653ea1f119eef9356907edc9b56979962d7aa 223 seed: 1.3.132.0.35 point generation seed (M) 225 N = 226 0200c7924b9ec017f3094562894336a53c50167ba8c5963876880542bc669e494b25 227 32d76c5b53dfb349fdf69154b9e0048c58a42e8ed04cef052a3bc349d95575cd25 228 seed: 1.3.132.0.35 point generation seed (N) 230 For edwards25519: 232 M = 233 d048032c6ea0b6d697ddc2e86bda85a33adac920f1bf18e1b0c6d166a5cecdaf 234 seed: edwards25519 point generation seed (M) 236 N = 237 d3bfb518f44f3430f29d0c92af503865a1ed3281dc69b35dd868ba85f886c4ab 238 seed: edwards25519 point generation seed (N) 240 For edwards448: 242 M = 243 b6221038a775ecd007a4e4dde39fd76ae91d3cf0cc92be8f0c2fa6d6b66f9a12 244 942f5a92646109152292464f3e63d354701c7848d9fc3b8880 245 seed: edwards448 point generation seed (M) 247 N = 248 6034c65b66e4cd7a49b0edec3e3c9ccc4588afd8cf324e29f0a84a072531c4db 249 f97ff9af195ed714a689251f08f8e06e2d1f24a0ffc0146600 250 seed: edwards448 point generation seed (N) 252 The following python snippet generates the above points, assuming an 253 elliptic curve implementation following the interface of 254 Edwards25519Point.stdbase() and Edwards448Point.stdbase() in 255 [RFC8032] appendix A: 257 def iterated_hash(seed, n): 258 h = seed 259 for i in range(n): 260 h = hashlib.sha256(h).digest() 261 return h 263 def bighash(seed, start, sz): 264 n = -(-sz // 32) 265 hashes = [iterated_hash(seed, i) for i in range(start, start + n)] 266 return b''.join(hashes)[:sz] 268 def canon_pointstr(ecname, s): 269 if ecname == 'edwards25519': 270 return s 271 elif ecname == 'edwards448': 272 return s[:-1] + bytes([s[-1] & 0x80]) 273 else: 274 return bytes([(s[0] & 1) | 2]) + s[1:] 276 def gen_point(seed, ecname, ec): 277 for i in range(1, 1000): 278 hval = bighash(seed, i, len(ec.encode())) 279 pointstr = canon_pointstr(ecname, hval) 280 try: 281 p = ec.decode(pointstr) 282 if p != ec.zero_elem() and p * p.l() == ec.zero_elem(): 283 return pointstr, i 284 except Exception: 285 pass 287 5. Security Considerations 289 A security proof of SPAKE2 for prime order groups is found in [REF]. 290 Note that the choice of M and N is critical for the security proof. 291 The generation method specified in this document is designed to 292 eliminate concerns related to knowing discrete logs of M and N. 294 SPAKE2+ appears in [TDH], along with a security proof (though the 295 corresponding model excludes precomputation attacks). 297 There is no key-confirmation as this is a one-round protocol. It is 298 expected that a protocol using this key exchange mechanism will 299 provide key confirmation separately if desired. 301 Elements received from a peer MUST be checked for group membership: 302 failure to properly validate group elements can lead to attacks. In 303 particular it is essential to verify that received points are valid 304 compressions of points on an elliptic curve when using elliptic 305 curves. It is not necessary to validate membership in the prime 306 order subgroup: the multiplication by cofactors eliminates the 307 potential for mebership in a small-order subgroup. 309 The choices of random numbers MUST BE uniform. Note that to pick a 310 random multiple of h in [0, p*h) one can pick a random integer in [0, 311 p) and multiply by h. Ephemeral values MUST NOT be reused; such 312 reuse permits dictionary attacks on the password. 314 SPAKE2 does not support augmentation. As a result, the server has to 315 store a password equivalent. This is considered a significant 316 drawback, and so SPAKE2+ also appears in this document. 318 As specified, the shared secret K is not suitable for direct use as a 319 shared key. It MUST be passed to a hash function along with the 320 public values used to derive it and the identities of the 321 participating parties in order to avoid attacks. In protocols which 322 do not perform this separately, the value denoted K' MUST be used 323 instead of K. 325 6. IANA Considerations 327 No IANA action is required. 329 7. Acknowledgments 331 Special thanks to Nathaniel McCallum and Greg Hudson for generation 332 of test vectors. Thanks to Mike Hamburg for advice on how to deal 333 with cofactors. Greg Hudson also suggested the addition of warnings 334 on the reuse of x and y. Thanks to Fedor Brunner, Adam Langley, and 335 the members of the CFRG for comments and advice. Trevor Perrin 336 informed me of SPAKE2+. 338 8. References 340 8.1. Normative References 342 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 343 Requirement Levels", BCP 14, RFC 2119, 344 DOI 10.17487/RFC2119, March 1997, 345 . 347 [RFC5480] Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk, 348 "Elliptic Curve Cryptography Subject Public Key 349 Information", RFC 5480, DOI 10.17487/RFC5480, March 2009, 350 . 352 [RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms 353 (SHA and SHA-based HMAC and HKDF)", RFC 6234, 354 DOI 10.17487/RFC6234, May 2011, 355 . 357 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 358 Signature Algorithm (EdDSA)", RFC 8032, 359 DOI 10.17487/RFC8032, January 2017, 360 . 362 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 363 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 364 May 2017, . 366 [SEC1] SEC, "STANDARDS FOR EFFICIENT CRYPTOGRAPHY, "SEC 1: 367 Elliptic Curve Cryptography", version 2.0", May 2009. 369 8.2. Informative References 371 [REF] Abdalla, M. and D. Pointcheval, "Simple Password-Based 372 Encrypted Key Exchange Protocols.", Feb 2005. 374 Appears in A. Menezes, editor. Topics in Cryptography- 375 CT-RSA 2005, Volume 3376 of Lecture Notes in Computer 376 Science, pages 191-208, San Francisco, CA, US. Springer- 377 Verlag, Berlin, Germany. 379 [RFC8265] Saint-Andre, P. and A. Melnikov, "Preparation, 380 Enforcement, and Comparison of Internationalized Strings 381 Representing Usernames and Passwords", RFC 8265, 382 DOI 10.17487/RFC8265, October 2017, 383 . 385 [TDH] Cash, D., Kiltz, E., and V. Shoup, "The Twin-Diffie 386 Hellman Problem and Applications", 2008. 388 EUROCRYPT 2008. Volume 4965 of Lecture notes in Computer 389 Science, pages 127-145. Springer-Verlag, Berlin, Germany. 391 Authors' Addresses 393 Watson Ladd 394 UC Berkeley 396 Email: watsonbladd@gmail.com 398 Benjamin Kaduk (editor) 399 Akamai Technologies 401 Email: kaduk@mit.edu