idnits 2.17.1 draft-irtf-cfrg-spake2-04.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 separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There is 1 instance of too long lines in the document, the longest one being 1 character in excess of 72. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 93: '...ashing algorithm SHOULD be designed to...' RFC 2119 keyword, line 97: '...both protocols, this MUST NOT be done....' RFC 2119 keyword, line 113: '... K MUST be combined with the values ...' RFC 2119 keyword, line 115: '...r doing so, that SHOULD be used. Othe...' RFC 2119 keyword, line 237: '...f random numbers MUST BE uniform. Not...' (3 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (October 16, 2017) is 2377 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 194 Summary: 3 errors (**), 0 flaws (~~), 1 warning (==), 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: April 19, 2018 Akamai 6 October 16, 2017 8 SPAKE2, a PAKE 9 draft-irtf-cfrg-spake2-04 11 Abstract 13 This Internet-Draft describes SPAKE2, a secure, efficient password 14 based key exchange protocol. 16 Status of This Memo 18 This Internet-Draft is submitted in full conformance with the 19 provisions of BCP 78 and BCP 79. 21 Internet-Drafts are working documents of the Internet Engineering 22 Task Force (IETF). Note that other groups may also distribute 23 working documents as Internet-Drafts. The list of current Internet- 24 Drafts is at https://datatracker.ietf.org/drafts/current/. 26 Internet-Drafts are draft documents valid for a maximum of six months 27 and may be updated, replaced, or obsoleted by other documents at any 28 time. It is inappropriate to use Internet-Drafts as reference 29 material or to cite them other than as "work in progress." 31 This Internet-Draft will expire on April 19, 2018. 33 Copyright Notice 35 Copyright (c) 2017 IETF Trust and the persons identified as the 36 document authors. All rights reserved. 38 This document is subject to BCP 78 and the IETF Trust's Legal 39 Provisions Relating to IETF Documents 40 (https://trustee.ietf.org/license-info) in effect on the date of 41 publication of this document. Please review these documents 42 carefully, as they describe your rights and restrictions with respect 43 to this document. Code Components extracted from this document must 44 include Simplified BSD License text as described in Section 4.e of 45 the Trust Legal Provisions and are provided without warranty as 46 described in the Simplified BSD License. 48 Table of Contents 50 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 51 2. Definition of SPAKE2 . . . . . . . . . . . . . . . . . . . . 2 52 3. Table of points for common groups . . . . . . . . . . . . . . 3 53 4. Security Considerations . . . . . . . . . . . . . . . . . . . 5 54 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 6 55 6. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 6 56 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 6 57 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 7 59 1. Introduction 61 This document describes a means for two parties that share a password 62 to derive a shared key. This method is compatible with any group, is 63 computationally efficient, and has a strong security proof. 65 2. Definition of SPAKE2 67 2.1. Setup 69 Let G be a group in which the Diffie-Hellman problem is hard of order 70 ph, with p a big prime and h a cofactor. We denote the operations in 71 the group additively. Let H be a hash function from arbitrary 72 strings to bit strings of a fixed length. Common choices for H are 73 SHA256 or SHA512. We assume there is a representation of elements of 74 G as byte strings: common choices would be SEC1 uncompressed [SEC1] 75 for elliptic curve groups or big endian integers of a particular 76 length for prime field DH. 78 || denotes concatenation of strings. We also let len(S) denote the 79 length of a string in bytes, represented as an eight-byte little- 80 endian number. 82 We fix two elements M and N as defined in the table in this document 83 for common groups, as well as a generator G of the group. G is 84 specified in the document defining the group, and so we do not recall 85 it here. 87 Let A and B be two parties. We will assume that A and B are also 88 representations of the parties such as MAC addresses or other names 89 (hostnames, usernames, etc). We assume they share an integer w. 90 Typically w will be the hash of a user-supplied password, truncated 91 and taken mod p. Protocols using this protocol must define the 92 method used to compute w: it may be necessary to carry out 93 normalization. The hashing algorithm SHOULD be designed to slow down 94 brute force attackers. 96 We present two protocols below. Note that it is insecure to use the 97 same password with both protocols, this MUST NOT be done. 99 2.2. SPAKE2 101 A picks x randomly and uniformly from the integers in [0,ph) 102 divisible by h, and calculates X=xG and T=wM+X, then transmits T to 103 B. 105 B selects y randomly and uniformly from the integers in [0,ph), 106 divisible by h and calculates Y=yG, S=wN+Y, then transmits S to A. 108 Both A and B calculate a group element K. A calculates it as 109 x(S-wN), while B calculates it as y(T-wM). A knows S because it has 110 received it, and likewise B knows T. 112 This K is a shared secret, but the scheme as described is not secure. 113 K MUST be combined with the values transmitted and received via a 114 hash function to have a secure protocol. If higher-level protocols 115 prescribe a method for doing so, that SHOULD be used. Otherwise we 116 can compute K' as H(len(A)||A||len(B)||B||len(S)||S|| 117 len(T)||T||len(K)||K || len(w) || w) and use K' as the key. 119 2.3. SPAKE2+ 121 This protocol and security proof appear in [TDH]. We use the same 122 setup as for SPAKE2, except that we have two secrets, w0 and w1. The 123 server, here Bob, stores L=w1*g and w0. 125 When executing SPAKE2+, A selects x uniformly at random from the 126 numbers in the range [0, ph) divisible by h, and lets X=xG+w0*M, then 127 transmits X to B. B selects y uniformly at random from the numbers 128 in [0, ph) divisible by h, then computes Y=yG+w0*N, and transmits it 129 to Alice. 131 A computes Z as x(Y-w0*N), and V as w1(Y-w0*N). B computes Z as y(X- 132 w0*M) and V as yL. Both share Z and V as common keys. It is 133 essential that both Z and V be used in combination with the 134 transcript to derive the keying material. For higher-level protocols 135 without sufficient transcript hashing, let K' be 136 H(len(A)||A||len(B)||B||len(X)||X||len(Y)||Y||len(Z)||Z||len(V)||V) 137 and use K' as the established key. 139 3. Table of points for common groups 141 Every curve presented in the table below has an OID from [RFC5480]. 142 We construct a string using the OID and the needed constant, for 143 instance "1.3.132.0.35 point generation seed (M)" for P-512. This 144 string is turned into an infinite sequence of bytes by hashing with 145 SHA256, and hashing that output again to generate the next 32 bytes, 146 and so on. This pattern is repeated for each group and value, with 147 the string modified appropriately. 149 The initial segment of bytes of length equal to that of an encoded 150 group element is taken, and is then formatted as required for the 151 group. In the case of Weierstrass points, this means setting the 152 first byte to 0x02 or 0x03 depending on the low-order bit. For 153 Ed25519 style formats this means taking all the bytes as the 154 representation of the group element. This string of bytes is then 155 interpreted as a point in the group. If this is impossible, then the 156 next non-overlapping segment of sufficient length is taken. We 157 multiply that point by the cofactor h, and if that is not the 158 identity, output it. 160 These bytestrings are compressed points as in [SEC1] for curves from 161 [SEC1]. 163 For P256: 165 M = 166 02886e2f97ace46e55ba9dd7242579f2993b64e16ef3dcab95afd497333d8fa12f 168 N = 169 03d8bbd6c639c62937b04d997f38c3770719c629d7014d49a24b4f98baa1292b49 171 For P384: 173 M = 174 030ff0895ae5ebf6187080a82d82b42e2765e3b2f8749c7e05eba366434b363d3dc 175 36f15314739074d2eb8613fceec2853 177 N = 178 02c72cf2e390853a1c1c4ad816a62fd15824f56078918f43f922ca21518f9c543bb 179 252c5490214cf9aa3f0baab4b665c10 181 For P521: 183 M = 184 02003f06f38131b2ba2600791e82488e8d20ab889af753a41806c5db18d37d85608 185 cfae06b82e4a72cd744c719193562a653ea1f119eef9356907edc9b56979962d7aa 187 N = 188 0200c7924b9ec017f3094562894336a53c50167ba8c5963876880542bc669e494b25 189 32d76c5b53dfb349fdf69154b9e0048c58a42e8ed04cef052a3bc349d95575cd25 191 The following python snippet generates the above points: 193 def canon_pointstr(self, s): 194 return chr(ord(s[0]) & 1 | 2) + s[1:] 196 def iterated_hash(seed, n): 197 h = seed 198 for i in xrange(n): 199 h = SHA256.new(h).digest() 200 return h 202 def bighash(seed, start, sz): 203 n = -(-sz // 32) 204 hashes = [iterated_hash(seed, i) for i in xrange(start, start + n)] 205 return ''.join(hashes)[:sz] 207 def gen_point(seed, ec, order): 208 for i in xrange(1, 1000): 209 pointstr = ec.canon_pointstr(bighash(seed, i, ec.nbytes_point())) 210 try: 211 p = ec.decode_point(pointstr) 212 if ec.mul(p, order) == ec.identity(): 213 return pointstr, i 214 except Exception: 215 pass 217 4. Security Considerations 219 A security proof of SPAKE2 for prime order groups is found in [REF]. 220 Note that the choice of M and N is critical for the security proof. 221 The generation method specified in this document is designed to 222 eliminate concerns related to knowing discrete logs of M and N. 224 SPAKE2+ appears in [TDH], along with proof. 226 There is no key-confirmation as this is a one round protocol. It is 227 expected that a protocol using this key exchange mechanism provides 228 key confirmation separately if desired. 230 Elements should be checked for group membership: failure to properly 231 validate group elements can lead to attacks. In particular it is 232 essential to verify that received points are valid compressions of 233 points on an elliptic curve when using elliptic curves. It is not 234 necessary to validate membership in the prime order subgroup: the 235 multiplication by cofactors eliminates this issue. 237 The choices of random numbers MUST BE uniform. Note that to pick a 238 random multiple of h in [0, ph) one can pick a random integer in 239 [0,p) and multiply by h. Reuse of ephemerals results in dictionary 240 attacks and MUST NOT be done. 242 SPAKE2 does not support augmentation. As a result, the server has to 243 store a password equivalent. This is considered a significant 244 drawback, and so SPAKE2+ also appears in this document. 246 As specified the shared secret K is not suitable for use as a shared 247 key. It MUST be passed to a hash function along with the public 248 values used to derive it and the party identities to avoid attacks. 249 In protocols which do not perform this separately, the value denoted 250 K' MUST be used instead. 252 5. IANA Considerations 254 No IANA action is required. 256 6. Acknowledgments 258 Special thanks to Nathaniel McCallum for generation of test vectors. 259 Thanks to Mike Hamburg for advice on how to deal with cofactors. 260 Greg Hudson suggested addition of warnings on the reuse of x and y. 261 Thanks to Fedor Brunner, Adam Langley, and the members of the CFRG 262 for comments and advice. Trevor Perrin informed me of SPAKE2+. 264 7. References 266 [REF] Abdalla, M. and D. Pointcheval, "Simple Password-Based 267 Encrypted Key Exchange Protocols.", Feb 2005. 269 Appears in A. Menezes, editor. Topics in Cryptography- 270 CT-RSA 2005, Volume 3376 of Lecture Notes in Computer 271 Science, pages 191-208, San Francisco, CA, US. Springer- 272 Verlag, Berlin, Germany. 274 [RFC5480] Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk, 275 "Elliptic Curve Cryptography Subject Public Key 276 Information", RFC 5480, DOI 10.17487/RFC5480, March 2009, 277 . 279 [SEC1] SEC, "STANDARDS FOR EFFICIENT CRYPTOGRAPHY, "SEC 1: 280 Elliptic Curve Cryptography", version 2.0", May 2009. 282 [TDH] Cash, D., Kiltz, E., and V. Shoup, "The Twin-Diffie 283 Hellman Problem and Applications", 2008. 285 EUROCRYPT 2008. Volume 4965 of Lecture notes in Computer 286 Science, pages 127-145. Springer-Verlag, Berlin, Germany. 288 Authors' Addresses 290 Watson Ladd 291 UC Berkeley 293 Email: watsonbladd@gmail.com 295 Benjamin Kaduk (editor) 296 Akamai Technologies 298 Email: kaduk@mit.edu