idnits 2.17.1 draft-irtf-cfrg-spake2-03.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. ** 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 95: '...ashing algorithm SHOULD be designed to...' RFC 2119 keyword, line 99: '...both protocols, this MUST NOT be done....' RFC 2119 keyword, line 115: '... K MUST be combined with the values...' RFC 2119 keyword, line 117: '...r doing so, that SHOULD be used. Other...' RFC 2119 keyword, line 230: '...f random numbers MUST BE uniform. Note...' (3 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The "Author's Address" (or "Authors' Addresses") section title is misspelled. -- The document date (13 February 2016) is 2967 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 195 Summary: 2 errors (**), 0 flaws (~~), 2 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Draft W. Ladd 3 UC Berkeley 4 Category: Informational 5 Expires 16 August 2016 13 February 2016 7 SPAKE2, a PAKE 8 10 Status of this Memo 12 Distribution of this memo is unlimited. 14 This Internet-Draft is submitted in full conformance with the 15 provisions of BCP 78 and BCP 79. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that 19 other groups may also distribute working documents as Internet- 20 Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at any 24 time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt. 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 This Internet-Draft will expire on date. 35 Copyright Notice 37 Copyright (c) 2016 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 (http://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. 47 Abstract 49 This Internet-Draft describes SPAKE2, a secure, efficient password 50 based key exchange protocol. 52 Table of Contents 54 1. Introduction ....................................................3 55 2. Definition of SPAKE2.............................................3 56 3. Table of points .................................................4 57 4. Security considerations .........................................5 58 5. IANA actions ....................................................5 59 6. Acknowledgements.................................................5 60 7. References.......................................................5 62 1. Introduction 64 This document describes a means for two parties that share a password 65 to derive a shared key. This method is compatible with any group, is 66 computationally efficient, and has a strong security proof. 68 2. Definition of SPAKE2 69 2.1 Setup 71 Let G be a group in which the Diffie-Hellman problem is hard of order 72 ph, with p a big prime and h a cofactor. We denote the operations in 73 the group additively. Let H be a hash function from arbitrary strings 74 to bit strings of a fixed length. Common choices for H are SHA256 or 75 SHA512. We assume there is a representation of elements of G as byte 76 strings: common choices would be SEC1 uncompressed [SEC1] for 77 elliptic curve groups or big endian integers of a particular length 78 for prime field DH. 80 || denotes concatenation of strings. We also let len(S) denote the 81 length of a string in bytes, represented as an eight-byte little- 82 endian number. 84 We fix two elements M and N as defined in the table in this document 85 for common groups, as well as a generator G of the group. G is 86 specified in the document defining the group, and so we do not recall 87 it here. 89 Let A and B be two parties. We will assume that A and B are also 90 representations of the parties such as MAC addresses or other names 91 (hostnames, usernames, etc). We assume they share an integer w. 92 Typically w will be the hash of a user-supplied password, truncated 93 and taken mod p. Protocols using this protocol must define the method 94 used to compute w: it may be necessary to carry out normalization. 95 The hashing algorithm SHOULD be designed to slow down brute force 96 attackers. 98 We present two protocols below. Note that it is insecure to use the 99 same password with both protocols, this MUST NOT be done. 101 2.2 SPAKE2 103 A picks x randomly and uniformly from the integers in [0,ph) 104 divisible by h, and calculates X=xG and T=wM+X, then transmits T to 105 B. 107 B selects y randomly and uniformly from the integers in [0,ph), 108 divisible by h and calculates Y=yG, S=wN+Y, then transmits S to A. 110 Both A and B calculate a group element K. A calculates it as x(S-wN), 111 while B calculates it as y(T-wM). A knows S because it has received 112 it, and likewise B knows T. 114 This K is a shared secret, but the scheme as described is not secure. 115 K MUST be combined with the values transmitted and received via a 116 hash function to have a secure protocol. If higher-level protocols 117 prescribe a method for doing so, that SHOULD be used. Otherwise we 118 can compute K' as H(len(A)||A||len(B)||B||len(S)||S|| 119 len(T)||T||len(K)||K || len(w) || w) and use K' as the key. 121 2.3 SPAKE2+ 123 This protocol and security proof appear in [TDH]. We use the same 124 setup as for SPAKE2, except that we have two secrets, w0 and w1. The 125 server, here Bob, stores L=w1*g and w0. 127 When executing SPAKE2+, A selects x uniformly at random from the 128 numbers in the range [0, ph) divisible by h, and lets X=xG+w0*M, then 129 transmits X to B. B selects y uniformly at random from the numbers in 130 [0, ph) divisible by h, then computes Y=yG+w0*N, and transmits it to 131 Alice. 133 A computes Z as x(Y-w0*N), and V as w1(Y-w0*N). B computes Z as y(X- 134 w0*M) and V as yL. Both share Z and V as common keys. It is essential 135 that both Z and V be used in combination with the transcript to 136 derive the keying material. For higher-level protocols without 137 sufficient transcript hashing, let K' be 138 H(len(A)||A||len(B)||B||len(X)||X||len(Y)||Y||len(Z)||Z||len(V)||V) 139 and use K' as the established key. 141 3. Table of points for common groups 143 Every curve presented in the table below has an OID from [OID]. We 144 construct a string using the OID and the needed constant, for 145 instance "1.3.132.0.35 point generation seed (M)" for P-512. This 146 string is turned into an infinite sequence of bytes by hashing with 147 SHA256, and hashing that output again to generate the next 32 bytes, 148 and so on. This pattern is repeated for each group and value, with 149 the string modified appropriately. 151 The initial segment of bytes of length equal to that of an encoded 152 group element is taken, and is then formatted as required for the 153 group. In the case of Weierstrass points, this means setting the 154 first byte to 0x02 or 0x03 depending on the low-order bit. For 155 Ed25519 style formats this means taking all the bytes as the 156 representation of the group element. This string of bytes is then 157 interpreted as a point in the group. If this is impossible, then the 158 next non-overlapping segment of sufficient length is taken. We 159 multiply that point by the cofactor h, and if that is not the 160 identity, output it. 162 These bytestrings are compressed points as in [SEC1] for curves from 163 [SEC1]. 165 For P256: 167 M = 168 02886e2f97ace46e55ba9dd7242579f2993b64e16ef3dcab95afd497333d8fa12f 170 N = 171 03d8bbd6c639c62937b04d997f38c3770719c629d7014d49a24b4f98baa1292b49 173 For P384: 175 M = 176 030ff0895ae5ebf6187080a82d82b42e2765e3b2f8749c7e05eba366434b363d3dc 177 36f15314739074d2eb8613fceec2853 179 N = 180 02c72cf2e390853a1c1c4ad816a62fd15824f56078918f43f922ca21518f9c543bb 181 252c5490214cf9aa3f0baab4b665c10 183 For P521: 185 M = 186 02003f06f38131b2ba2600791e82488e8d20ab889af753a41806c5db18d37d85608 187 cfae06b82e4a72cd744c719193562a653ea1f119eef9356907edc9b56979962d7aa 189 N = 190 0200c7924b9ec017f3094562894336a53c50167ba8c5963876880542bc669e494b25 191 32d76c5b53dfb349fdf69154b9e0048c58a42e8ed04cef052a3bc349d95575cd25 193 The following python snippet generates the above points: 195 def canon_pointstr(self, s): return chr(ord(s[0]) & 1 | 2) + 196 s[1:] 197 def iterated_hash(seed, n): h = seed for i in xrange(n): 198 h = SHA256.new(h).digest() return h 200 def bighash(seed, start, sz): n = -(-sz // 32) hashes = 201 [iterated_hash(seed, i) for i in xrange(start, start + n)] 202 return ''.join(hashes)[:sz] 204 def gen_point(seed, ec, order): for i in xrange(1, 1000): 205 pointstr = ec.canon_pointstr(bighash(seed, i, ec.nbytes_point())) 206 try: p = ec.decode_point(pointstr) 207 if ec.mul(p, order) == ec.identity(): return 208 pointstr, i except Exception: pass 210 4. Security Considerations 212 A security proof of SPAKE2 for prime order groups is found in [REF]. 213 Note that the choice of M and N is critical for the security proof. 214 The generation method specified in this document is designed to 215 eliminate concerns related to knowing discrete logs of M and N. 217 SPAKE2+ appears in [TDH], along with proof. 219 There is no key-confirmation as this is a one round protocol. It is 220 expected that a protocol using this key exchange mechanism provides 221 key confirmation separately if desired. 223 Elements should be checked for group membership: failure to properly 224 validate group elements can lead to attacks. In particular it is 225 essential to verify that received points are valid compressions of 226 points on an elliptic curve when using elliptic curves. It is not 227 necessary to validate membership in the prime order subgroup: the 228 multiplication by cofactors eliminates this issue. 230 The choices of random numbers MUST BE uniform. Note that to pick a 231 random multiple of h in [0, ph) one can pick a random integer in 232 [0,p) and multiply by h. Reuse of ephemerals results in dictionary 233 attacks and MUST NOT be done. 235 SPAKE2 does not support augmentation. As a result, the server has to 236 store a password equivalent. This is considered a significant 237 drawback, and so SPAKE2+ also appears in this document. 239 As specified the shared secret K is not suitable for use as a shared 240 key. It MUST be passed to a hash function along with the public 241 values used to derive it and the party identities to avoid attacks. 242 In protocols which do not perform this separately, the value denoted 243 K' MUST be used instead. 245 5. IANA Considerations 247 No IANA action is required. 249 6. Acknowledgments 251 Special thanks to Nathaniel McCallum for generation of test vectors. 252 Thanks to Mike Hamburg for advice on how to deal with cofactors. Greg 253 Hudson suggested addition of warnings on the reuse of x and y. Thanks 254 to Fedor Brunner, Adam Langley, and the members of the CFRG for 255 comments and advice. Trevor Perrin informed me of SPAKE2+. 257 7. References 259 [REF] Abdalla, M. and Pointcheval, D. Simple Password-Based Encrypted 260 Key Exchange Protocols. Appears in A. Menezes, editor. Topics in 261 Cryptography-CT-RSA 2005, Volume 3376 of Lecture Notes in Computer 262 Science, pages 191-208, San Francisco, CA, US Feb. 14-18, 2005. 263 Springer-Verlag, Berlin, Germany. 265 [SEC1] STANDARDS FOR EFFICIENT CRYPTOGRAPHY, "SEC 1: Elliptic Curve 266 Cryptography", version 2.0, May 2009, 269 [TDH] Cash, D. Kiltz, E. and Shoup, V. The Twin-Diffie Hellman 270 Problem and Applications. Advances in Cryptology--EUROCRYPT 2008. 271 Volume 4965 of Lecture notes in Computer Science, pages 127-145. 272 Springer-Verlag, Berlin, Germany. 274 [OID] Turner, S. and D. Brown and K. Yiu and R. Housley and T. Polk. 275 Elliptic Curve Cryptography Subject Public Key Information. RFC 5480. 276 March 2009. 278 Author Addresses 279 Watson Ladd 280 watsonbladd@gmail.com 281 Berkeley, CA