idnits 2.17.1 draft-brusilovsky-pak-10.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Found new IETF Trust Provisions of 12 Sep 2009 boilerplate, which is fine, but *also* found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 383. ** Found new IETF Trust Provisions of 12 Sep 2009 boilerplate, which is fine, but *also* found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 390. ** Found new IETF Trust Provisions of 12 Sep 2009 boilerplate, which is fine, but *also* found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 396. ** The document seems to lack a License Notice according IETF Trust Provisions of 28 Dec 2009, Section 6.b.ii or Provisions of 12 Sep 2009 Section 6.b -- however, there's a paragraph with a matching beginning. Boilerplate error? (You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Feb 2009 rather than one of the newer Notices. See https://trustee.ietf.org/license-info/.) Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 5 longer pages, the longest (page 8) being 92 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 8 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Authors' Addresses Section. ** There are 96 instances of too long lines in the document, the longest one being 19 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 273 has weird spacing: '... better prote...' == Line 277 has weird spacing: '...ord and attem...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (April 2009) is 5489 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: 'FIPS180' is defined on line 326, but no explicit reference was found in the text == Unused Reference: 'IEEE1363' is defined on line 329, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'TIA 683' Summary: 6 errors (**), 0 flaws (~~), 8 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group A. Brusilovsky 2 Internet-Draft I. Faynberg 3 Expires: September 2009 Z. Zeltsan 4 Alcatel-Lucent 6 S. Patel 7 Google, Inc. 9 April 2009 11 Password-Authenticated Diffie-Hellman Exchange (PAK) 13 draft-brusilovsky-pak-10.txt 15 Status of this Memo 17 This Internet-Draft is submitted to IETF in full conformance with the 18 provisions of BCP 78 and BCP 79. 20 Internet-Drafts are working documents of the Internet Engineering 21 Task Force (IETF), its areas, and its working groups. Note that 22 other groups may also distribute working documents as Internet- 23 Drafts. 25 Internet-Drafts are draft documents valid for a maximum of six months 26 and may be updated, replaced, or obsoleted by other documents at any 27 time. It is inappropriate to use Internet-Drafts as reference 28 material or to cite them other than as "work in progress." 30 The list of current Internet-Drafts can be accessed at 31 http://www.ietf.org/ietf/1id-abstracts.txt. 33 The list of Internet-Draft Shadow Directories can be accessed at 34 http://www.ietf.org/shadow.html. 36 This Internet-Draft will expire in September, 2009. 38 Copyright Notice 40 Copyright (c) 2009 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents in effect on the date of 45 publication of this document (http://trustee.ietf.org/license-info). 46 Please review these documents carefully, as they describe your rights 47 and restrictions with respect to this document. 49 Abstract 51 This document proposes to add mutual authentication, based on 52 human-memorizable password, to the basic unauthenticated Diffie-Hellman 53 key exchange. The proposed algorithm is called Password-authenticated 54 Key exchange (PAK). PAK allows two parties to authenticate themselves 55 while performing the Diffie-Hellman exchange. 57 The protocol is secure against all passive and active attacks. 58 In particular, it does not allow either type of attackers to obtain any 59 information that would enable an off-line dictionary attack on the 60 password. PAK provides Forward Secrecy. 62 Table of Contents 64 1. Introduction 65 2. Conventions 66 3. Password-Authenticated Key exchange 67 4. Selection of parameters 68 4.1 General considerations 69 4.2 OTASP and WLAN Diffie-Hellman parameters and key expansion functions 70 5. Security considerations 71 6. IANA considerations 72 7. Acknowledgments 73 8. References 74 8.1 Normative references 75 8.2 Informative references 76 Authors' and contributors' addresses 78 1. Introduction 80 PAK has the following advantages: 82 - It provides a secure authenticated key exchange protocol. 83 - It is secure against offline dictionary attacks when passwords are used. 84 - It ensures Forward Secrecy. 85 - It is proved to be as secure as the Diffie-Hellman solution. 87 The PAK protocol [BMP00], [MP05], [X.1035] has been proven to be as secure 88 as the Diffie-Hellman [RFC2631], [DH76] in the random oracle model [BR93]. That is, 89 PAK retains its security when used with low-entropy passwords. Therefore, 90 it can be seamlessly integrated into existing applications, requiring 91 secure authentication based on such low-entropy shared secrets. 93 2. Conventions 95 - A is an identity of Alice 96 - B is an identity of Bob 97 - Ra is a secret random exponent selected by A 98 - Rb is a secret random exponent selected by B 99 - Xab denotes a value (X presumably computed by A) as derived by B 100 - Yba denotes a value (Y presumably computed by B) as derived by A 101 - a mod b denotes the least non-negative remainder when a is divided by b; 102 - Hi(u) denotes an agreed-on function (e.g., based on SHA-1, SHA-256, 103 etc.) computed over a string u; The various H() act as independent random 104 functions. H1(u) and H2(u) are the key derivation functions. 105 H3(u), H4(u), and H5(u) are the hash functions. 106 - s|t denotes concatenation of the strings s and t; 107 - ^ denotes exponentiation; 108 - multiplication, division, and exponentiation are performed over (Zp)*; 109 in other words: 111 1) a*b always means a*b (mod p) 112 2) a/b always means a * x (mod p), where x is the multiplicative inverse 113 of b modulo p 114 3) a^b means a^b (mod p). 116 3. Password Authenticated Key exchange 118 Diffie-Hellman key agreement requires that both the sender and 119 recipient of a message create their own secret random numbers and 120 exchange the exponentiation of their respective numbers. 122 PAK has two parties, Alice (A) and Bob (B), sharing a secret password PW 123 that satisfies the following conditions: 124 - H1(A|B|PW) != 0 125 - H2(A|B|PW) != 0. 126 The global Diffie-Hellman publicly-known constants, a prime p and a 127 generator g, are carefully selected so that: 129 1. A safe prime p is large enough to make the computation of discrete 130 logarithms infeasible and 132 2. Powers of g modulo p cover the entire range of p-1 integers from 1 to 133 p-1. (References demonstrate working example of selections). 135 Initially, Alice (A) selects a secret random exponent Ra and computes g^Ra; 136 Bob (B) selects a secret random exponent Rb and computes g^Rb. 137 For efficiency purposes, short exponents could be used for Ra and Rb 138 provided they have a certain minimum size. Then: 140 - A --> B: {A, X = H1(A|B|PW)*(g^Ra)} (The above precondition on PW 141 ensures that X != 0); 143 Bob 144 receives Q (presumably Q = X), verifies that Q != 0 (if Q = 0, 145 Bob aborts the procedure); 146 divides Q by H1(A|B|PW) to get Xab, the recovered value of g^Ra; 148 - B --> A: {Y = H2(A|B|PW)*(g^Rb), S1 = H3(A|B|PW|Xab|g^Rb|(Xab)^Rb)} 149 (The above precondition on PW ensures that Y != 0) 151 Alice 152 verifies that Y != 0; 153 divides Y by H2(A|B|PW) to get Yba, the recovered value of g^Rb 154 and computes S1' = H3(A|B|PW|g^Ra|Yba|(Yba)^Ra); 155 authenticates Bob by checking whether S1' equals the received S1; 156 if authenticated, then sets key K = H5(A|B|PW|g^Ra|Yba|(Yba)^Ra) 158 - A --> B: S2 = H4(A|B|PW|g^Ra|Yba|(Yba)^Ra) 160 Bob 161 Computes S2' = H4(A|B|PW|Xab|g^Rb|(Xab)^Rb) and 162 authenticates Alice by checking whether S2' equals the received S2; 163 if authenticated then sets K = H5(A|B|PW|Xab|g^Rb|(Xab)^Rb) 165 If any of the above verifications fails, the protocol halts; otherwise, 166 both parties have authenticated each other and established the key. 168 4. Selection of parameters 170 This section provides guidance on selection of the PAK parameters. First, it 171 addresses general considerations, then it reports on specific implementations. 173 4.1 General considerations 175 In general implementations, the parameters must be selected to meet algorithm 176 requirements of [BMP00]. 178 4.2 OTASP and WLAN Diffie-Hellman parameters and key expansion functions 180 [OTASP], [TIA 683], and [WLAN] pre-set public parameters p and g to their "published" 181 values. This is necessary to protect against an attacker sending bogus p 182 and g values tricking the legitimate user to engage in improper 183 Diffie-Hellman exponentiation and leaking some information about the 184 password. 186 According to [OTASP], [TIA 683], and [WLAN], g shall be set to 00001101, and p to the 187 following 1024-bit prime number (Most-significant-bit first): 189 0xFFFFFFFF 0xFFFFFFFF 0xC90FDAA2 0x2168C234 0xC4C6628B 190 0x80DC1CD1 0x29024E08 0x8A67CC74 0x020BBEA6 0x3B139B22 191 0x514A0879 0x8E3404DD 0xEF9519B3 0xCD3A431B 0x302B0A6D 192 0xF25F1437 0x4FE1356D 0x6D51C245 0xE485B576 0x625E7EC6 193 0xF44C42E9 0xA637ED6B 0x0BFF5CB6 0xF406B7ED 0xEE386BFB 194 0x5A899FA5 0xAE9F2411 0x7C4B1FE6 0x49286651 0xECE65381 195 0xFFFFFFFF 0xFFFFFFFF 197 In addition, if short exponents [MP05] are used for Diffie-Hellman 198 parameters Ra and Rb, then they should have a minimum size of 384 bits. The independent 199 random functions H1 and H2 should each output 1152 bits assuming prime p is 1024 bits 200 long and session keys K are 128 bits long. H3, H4, and H5 each output 128 bits. 201 More information on instantiating random functions using hash functions 202 can be found in [BR93]. We use the FIPS 180 SHA-1 hashing function below 203 to instantiate the random function as done in [WLAN], however, SHA-256 204 can also be used: 206 H1(z): SHA-1(1|1|z) mod 2^128 | SHA-1(1|2|z) mod 2^128 |. . .| SHA-1(1|9|z) 207 mod 2^128 209 H2(z): SHA-1(2|1|z) mod 2^128 | SHA-1(2|2|z) mod 2^128 |. . .| SHA-1(2|9|z) 210 mod 2^128 211 H3(z): SHA-1(3|len(z)|z|z) mod 2^128 212 H4(z): SHA-1(4|len(z)|z|z) mod 2^128 213 H5(z): SHA-1(5|len(z)|z|z) mod 2^128 215 In order to create 1152 output bits for H1 and H2, nine calls to SHA-1 216 are made and the 128 least-significant bits of each output are used. The input 217 payload of each call to SHA-1 consists of: 219 a) 32 bits of function type which for H1 is set to 1 and for H2 is set to 2; 220 b) a 32 bit counter value, which is incremented from 1 to 9 for each call to 221 SHA-1; 222 c) the argument z [for (A|B|PW)]. 224 The functions H3, H4, and H5 require only one call to the SHA-1 hashing 225 function and their respective payloads consist of: 227 a) 32 bits of function type (e.g. 3 for H3); 228 b) a 32 bit value for the bit length of the argument z; 229 c) the actual argument repeated twice. 231 Finally, the 128 least-significant bits of the output are used. 233 5. Security considerations 235 Those are as follows: 237 - Identifiers 238 Any protocol that uses PAK must specify a method for producing a single 239 representation of identity strings. 241 - Shared secret 242 PAK involves the use of a shared secret. Protection of the shared 243 values and managing (limiting) their exposure over time is essential, and 244 it can be achieved using well-known security policies and measures. 245 If a single secret is shared among more than two entities (e.g., Alice, Bob, and 246 Mallory), then Mallory can represent himself as Alice to Bob without Bob being 247 any the wiser. 249 - Selection of Diffie-Hellman parameters 250 The parameters, p and g, must be carefully selected in order not to 251 compromise the shared secret. Only previously agreed upon values for 252 parameters p and g should be used in the PAK protocol. This is necessary to 253 protect against an attacker sending bogus p and g values and thus tricking 254 the other communicating party in an improper Diffie-Hellman exponentiation. 255 Both parties also need to randomly select a new exponent each time the key 256 agreement protocol is executed. If both parties re-use the same values, 257 then Forward Secrecy property is lost. 258 In addition, if short exponents Ra and Rb are used then they should have a 259 minimum size of 384 bits (assuming that 128-bit session keys are used). 260 Historically, the developers, who strived for 128-bit security (and thus 261 selected 256-bit exponents) added 128 bits to the exponents to ensure the 262 security reductions proofs. This should explain how an "odd" length of 384 has 263 been arrived at. 265 - Protection against attacks 266 a) There is a potential attack, the so-called discrete logarithm attack on the 267 multiplicative group of congruencies modulo p, in which an adversary can 268 construct a table of discrete logarithms to be used as a "dictionary". A 269 sufficiently large prime, p, must be selected to protect against such an 270 attack. A proper 1024-bit value for p and an appropriate value for g are 271 published in [WLAN] and [TIA 683]. For the moment, this is what has been 272 implemented; however, a larger prime (i.e., one that is 2048-bit long 273 or even larger) will definitely provide better protection. It is important 274 to note that once this is done, the generator must be changed, too, so this 275 task must be approached with extreme care. 276 b) An on-line password attack can be launched by an attacker by repeatedly 277 guessing the password and attempting to authenticate. The implementers of 278 PAK should consider employing mechanisms (such as lockouts) for preventing 279 such attacks. 281 - Recommendations on H() functions 282 The independent random functions H1 and H2 should output 1152 bits each, 283 assuming prime p is 1024 bits long and session keys K are 128 bits long. The 284 random functions H3, H4, and H5 should output 128 bits. 286 An example of secure implementation of PAK is provided in [Plan 9]. 288 6. IANA considerations 290 No IANA considerations at this time 292 7. Acknowledgments 294 The authors are grateful for the thoughtful comments received from Shehryar 295 Qutub, Yaron Sheffer, and Ray Perlner. Special thanks go to Alfred Hoenes, 296 Tim Polk, and Jim Schaad for the careful reviews and invaluable help in 297 preparing the final version of this document. 299 8. References 301 8.1 Normative references 303 [X.1035] ITU-T Recommendation X.1035 (2007), Password-authenticated key exchange 304 (PAK) protocol 306 [TIA 683] Over-the-Air Service Provisioning of Mobile Stations in 307 Spread Spectrum Systems, TIA TIA-683-D 309 8.2 Informative references 311 [Plan 9] Plan 9 ? An open source operating system, which implements PAK 312 http://netlib.bell-labs.com/plan9dist/ 314 [BMP00] V. Boyko, P. MacKenzie, S. Patel, Provably secure password 315 authentication and key exchange using Diffie-Hellman, 316 Proc. of Eurocrypt 2000. 318 [BR93] M. Bellare and P. Rogaway, Random Oracles are Practical: 319 A Paradigm for Designing Efficient Protocols, Proc. Of the 320 fifth annual conference on computer and communications 321 security, 1993. 323 [DH76] W. Diffie and M.E. Hellman, New directions in cryptography, 324 IEEE Transactions on Information Theory 22 (1976), 644-654. 326 [FIPS180] NIST Federal Information Processing Standards, Publication 327 FIPS 180-3, 2008 329 [IEEE1363] IEEE P1363.2, April 24, 2002, The PAK suite: Protocols for 330 Password-Authentication Key Exchange, P. MacKenzie 332 [MP05] P. MacKenzie, S. Patel, Hard Bits of the Discrete Log with 333 Applications to Password Authentication, CT-RSA 2005. 335 [OTASP] Over-the-Air Service Provisioning of Mobile Stations in Spread 336 Spectrum Systems, 3GPP2 C.S0016-C v. 1.0 5, 3GPP2, 10/2004. 338 [RFC2631] IETF RFC 2631, E. Rescorla, Diffie-Hellman Key Agreement 339 Method, Standards track,1999 341 [WLAN] Wireless Local Area Network (WLAN) Interworking, 3GPP2 X.S0028-0, 342 v.1.0, 3GPP2, 4/2005 344 Authors' and Contributors' Addresses 346 Alec Brusilovsky 347 Alcatel-Lucent 348 Room 9B-226, 1960 Lucent Lane 349 Naperville, IL 60566-7217 U S 350 Tel: +1 630 979 5490 351 Email: abrusilovsky@alcatel-lucent.com 353 Igor Faynberg 354 Alcatel-Lucent 355 Room 2D-144, 600 Mountain Avenue 356 Murray Hill, NJ 07974 357 Tel: +1 908 582 2626 358 Email: faynberg@alcatel-lucent.com 360 Sarvar Patel 361 Google, Inc. 362 76 Ninth Avenue 363 New York, NY 10011 364 Tel: +1 212 565 5907 365 Email: sarvar@google.com 367 Zachary Zeltsan 368 Alcatel-Lucent 369 Room 2D-150, 600 Mountain Avenue 370 Murray Hill, NJ 07974 371 Tel: +1 908 582 2359 372 Email: zeltsan@alcatel-lucent.com 374 Intellectual Property 376 The IETF takes no position regarding the validity or scope of any 377 Intellectual Property Rights or other rights that might be claimed to 378 pertain to the implementation or use of the technology described in 379 this document or the extent to which any license under such rights 380 might or might not be available; nor does it represent that it has 381 made any independent effort to identify any such rights. Information 382 on the procedures with respect to rights in RFC documents can be 383 found in BCP 78 and BCP 79. 385 Copies of IPR disclosures made to the IETF Secretariat and any 386 assurances of licenses to be made available, or the result of an 387 attempt made to obtain a general license or permission for the use of 388 such proprietary rights by implementers or users of this 389 specification can be obtained from the IETF on-line IPR repository at 390 http://www.ietf.org/ipr. 392 The IETF invites any interested party to bring to its attention any 393 copyrights, patents or patent applications, or other proprietary 394 rights that may cover technology that may be required to implement 395 this standard. Please address the information to the IETF at 396 ietf-ipr@ietf.org.