1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
|
<pre>Independent Submission A. Brusilovsky
Request for Comments: 5683 I. Faynberg
Category: Informational Z. Zeltsan
ISSN: 2070-1721 Alcatel-Lucent
S. Patel
Google, Inc.
February 2010
<span class="h1">Password-Authenticated Key (PAK) Diffie-Hellman Exchange</span>
Abstract
This document proposes to add mutual authentication, based on a
human-memorizable password, to the basic, unauthenticated Diffie-
Hellman key exchange. The proposed algorithm is called the Password-
Authenticated Key (PAK) exchange. PAK allows two parties to
authenticate themselves while performing the Diffie-Hellman exchange.
The protocol is secure against all passive and active attacks. In
particular, it does not allow either type of attacker to obtain any
information that would enable an offline dictionary attack on the
password. PAK provides Forward Secrecy.
Status of This Memo
This document is not an Internet Standards Track specification; it is
published for informational purposes.
This is a contribution to the RFC Series, independently of any other
RFC stream. The RFC Editor has chosen to publish this document at
its discretion and makes no statement about its value for
implementation or deployment. Documents approved for publication by
the RFC Editor are not a candidate for any level of Internet
Standard; see <a href="./rfc5741#section-2">Section 2 of RFC 5741</a>.
Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
<a href="http://www.rfc-editor.org/info/rfc5683">http://www.rfc-editor.org/info/rfc5683</a>.
<span class="grey">Brusilovsky, et al. Informational [Page 1]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-2" ></span>
<span class="grey"><a href="./rfc5683">RFC 5683</a> PAK Diffie-Hellman Exchange February 2010</span>
Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to <a href="https://www.rfc-editor.org/bcp/bcp78">BCP 78</a> and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http:trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document.
Table of Contents
<a href="#section-1">1</a>. Introduction ....................................................<a href="#page-3">3</a>
<a href="#section-2">2</a>. Conventions .....................................................<a href="#page-3">3</a>
<a href="#section-3">3</a>. Password-Authenticated Key Exchange .............................<a href="#page-4">4</a>
<a href="#section-4">4</a>. Selection of Parameters .........................................<a href="#page-5">5</a>
<a href="#section-4.1">4.1</a>. General Considerations .....................................<a href="#page-5">5</a>
4.2. Over-the-Air Service Provisioning (OTASP) and Wireless
Local Area Network (WLAN) Diffie-Hellman Parameters and
Key Expansion Functions ....................................<a href="#page-5">5</a>
<a href="#section-5">5</a>. Security Considerations .........................................<a href="#page-7">7</a>
<a href="#section-6">6</a>. Acknowledgments .................................................<a href="#page-8">8</a>
<a href="#section-7">7</a>. References ......................................................<a href="#page-8">8</a>
<a href="#section-7.1">7.1</a>. Normative References .......................................<a href="#page-8">8</a>
<a href="#section-7.2">7.2</a>. Informative References .....................................<a href="#page-8">8</a>
<span class="grey">Brusilovsky, et al. Informational [Page 2]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-3" ></span>
<span class="grey"><a href="./rfc5683">RFC 5683</a> PAK Diffie-Hellman Exchange February 2010</span>
<span class="h2"><a class="selflink" id="section-1" href="#section-1">1</a>. Introduction</span>
PAK has the following advantages:
- It provides a secure, authenticated key-exchange protocol.
- It is secure against offline dictionary attacks when passwords are
used.
- It ensures Forward Secrecy.
- It has been proven to be as secure as the Diffie-Hellman solution.
The PAK protocol ([<a href="#ref-BMP00" title=""Provably secure password authentication and key exchange using Diffie- Hellman"">BMP00</a>], [<a href="#ref-MP05" title=""Hard Bits of the Discrete Log with Applications to Password Authentication"">MP05</a>], [<a href="#ref-X.1035" title=""Password-authenticated key exchange (PAK) protocol"">X.1035</a>]) has been proven to be as
secure as the Diffie-Hellman ([<a href="./rfc2631" title=""Diffie-Hellman Key Agreement Method"">RFC2631</a>], [<a href="#ref-DH76" title=""New directions in cryptography"">DH76</a>]) in the random oracle
model [<a href="#ref-BR93" title=""Random Oracles are Practical: A Paradigm for Designing Efficient Protocols"">BR93</a>]. That is, PAK retains its security when used with low-
entropy passwords. Therefore, it can be seamlessly integrated into
existing applications, requiring secure authentication based on such
low-entropy shared secrets.
<span class="h2"><a class="selflink" id="section-2" href="#section-2">2</a>. Conventions</span>
- A is an identity of Alice.
- B is an identity of Bob.
- Ra is a secret random exponent selected by A.
- Rb is a secret random exponent selected by B.
- Xab denotes a value (X presumably computed by A) as derived by B.
- Yba denotes a value (Y presumably computed by B) as derived by A.
- A mod b denotes the least non-negative remainder when a is divided
by b.
- Hi(u) denotes an agreed-on function (e.g., based on SHA-1,
SHA-256, etc.) computed over a string u; the various H() act as
independent random functions. H1(u) and H2(u) are the key
derivation functions. H3(u), H4(u), and H5(u) are the hash
functions.
- s|t denotes concatenation of the strings s and t.
- ^ denotes exponentiation.
- Multiplication, division, and exponentiation are performed over
(Zp)*; in other words:
<span class="grey">Brusilovsky, et al. Informational [Page 3]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-4" ></span>
<span class="grey"><a href="./rfc5683">RFC 5683</a> PAK Diffie-Hellman Exchange February 2010</span>
1) a*b always means a*b (mod p).
2) a/b always means a * x (mod p), where x is the multiplicative
inverse of b modulo p.
3) a^b means a^b (mod p).
<span class="h2"><a class="selflink" id="section-3" href="#section-3">3</a>. Password-Authenticated Key Exchange</span>
Diffie-Hellman key agreement requires that both the sender and
recipient of a message create their own secret, random numbers and
exchange the exponentiation of their respective numbers.
PAK has two parties, Alice (A) and Bob (B), sharing a secret password
PW that satisfies the following conditions:
H1(A|B|PW) != 0
H2(A|B|PW) != 0
The global Diffie-Hellman publicly known constants, a prime p and a
generator g, are carefully selected so that:
1. A safe prime p is large enough to make the computation of
discrete logarithms infeasible, and
2. Powers of g modulo p cover the entire range of p-1 integers from
1 to p-1. (References demonstrate working examples of
selections).
Initially, Alice (A) selects a secret, random exponent Ra and
computes g^Ra; Bob (B) selects a secret, random exponent Rb and
computes g^Rb. For efficiency purposes, short exponents could be
used for Ra and Rb, provided they have a certain minimum size. Then:
A --> B: {A, X = H1(A|B|PW)*(g^Ra)}
(The above precondition on PW ensures that X != 0)
Bob
receives Q (presumably Q = X), verifies that Q != 0
(if Q = 0, Bob aborts the procedure);
divides Q by H1(A|B|PW) to get Xab, the recovered value of g^Ra
<span class="grey">Brusilovsky, et al. Informational [Page 4]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-5" ></span>
<span class="grey"><a href="./rfc5683">RFC 5683</a> PAK Diffie-Hellman Exchange February 2010</span>
B --> A: {Y = H2(A|B|PW)*(g^Rb), S1 = H3(A|B|PW|Xab|g^Rb|(Xab)^Rb)}
(The above precondition on PW ensures that Y != 0)
Alice
verifies that Y != 0;
divides Y by H2(A|B|PW) to get Yba, the recovered value of g^Rb,
and computes S1' = H3(A|B|PW|g^Ra|Yba|(Yba)^Ra);
authenticates Bob by checking whether S1' = S1;
if authenticated, then sets key K = H5(A|B|PW|g^Ra|Yba|(Yba)^Ra)
A --> B: S2 = H4(A|B|PW|g^Ra|Yba|(Yba)^Ra)
Bob
Computes S2' = H4(A|B|PW|Xab|g^Rb|(Xab)^Rb) and
authenticates Alice by checking whether S2' = S2;
if authenticated, then sets K = H5(A|B|PW|Xab|g^Rb|(Xab)^Rb)
If any of the above verifications fails, the protocol halts;
otherwise, both parties have authenticated each other and established
the key.
<span class="h2"><a class="selflink" id="section-4" href="#section-4">4</a>. Selection of Parameters</span>
This section provides guidance on selection of the PAK parameters.
First, it addresses general considerations, then it reports on
specific implementations.
<span class="h3"><a class="selflink" id="section-4.1" href="#section-4.1">4.1</a>. General Considerations</span>
In general implementations, the parameters must be selected to meet
algorithm requirements of [<a href="#ref-BMP00" title=""Provably secure password authentication and key exchange using Diffie- Hellman"">BMP00</a>].
<span class="h3"><a class="selflink" id="section-4.2" href="#section-4.2">4.2</a>. Over-the-Air Service Provisioning (OTASP) and Wireless Local Area</span>
<span class="h3"> Network (WLAN) Diffie-Hellman Parameters and Key Expansion</span>
Functions
[<a href="#ref-OTASP" title=""Over-the-Air Service Provisioning of Mobile Stations in Spread Spectrum Systems"">OTASP</a>], [<a href="#ref-TIA683" title=""Over-the-Air Service Provisioning of Mobile Stations in Spread Spectrum Systems"">TIA683</a>], and [<a href="#ref-WLAN" title=""Wireless Local Area Network (WLAN) Interworking"">WLAN</a>] pre-set public parameters p and g to
their "published" values. This is necessary to protect against an
attacker sending bogus p and g values, tricking the legitimate user
to engage in improper Diffie-Hellman exponentiation and leaking some
information about the password.
According to [<a href="#ref-OTASP" title=""Over-the-Air Service Provisioning of Mobile Stations in Spread Spectrum Systems"">OTASP</a>], [<a href="#ref-TIA683" title=""Over-the-Air Service Provisioning of Mobile Stations in Spread Spectrum Systems"">TIA683</a>], and [<a href="#ref-WLAN" title=""Wireless Local Area Network (WLAN) Interworking"">WLAN</a>], g shall be set to
00001101, and p to the following 1024-bit prime number (most
significant bit first):
<span class="grey">Brusilovsky, et al. Informational [Page 5]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-6" ></span>
<span class="grey"><a href="./rfc5683">RFC 5683</a> PAK Diffie-Hellman Exchange February 2010</span>
0xFFFFFFFF 0xFFFFFFFF 0xC90FDAA2 0x2168C234 0xC4C6628B
0x80DC1CD1 0x29024E08 0x8A67CC74 0x020BBEA6 0x3B139B22
0x514A0879 0x8E3404DD 0xEF9519B3 0xCD3A431B 0x302B0A6D
0xF25F1437 0x4FE1356D 0x6D51C245 0xE485B576 0x625E7EC6
0xF44C42E9 0xA637ED6B 0x0BFF5CB6 0xF406B7ED 0xEE386BFB
0x5A899FA5 0xAE9F2411 0x7C4B1FE6 0x49286651 0xECE65381
0xFFFFFFFF 0xFFFFFFFF
In addition, if short exponents [<a href="#ref-MP05" title=""Hard Bits of the Discrete Log with Applications to Password Authentication"">MP05</a>] are used for Diffie-Hellman
parameters Ra and Rb, then they should have a minimum size of 384
bits. The independent, random functions H1 and H2 should each output
1152 bits, assuming prime p is 1024 bits long and session keys K are
128 bits long. H3, H4, and H5 each output 128 bits. More
information on instantiating random functions using hash functions
can be found in [<a href="#ref-BR93" title=""Random Oracles are Practical: A Paradigm for Designing Efficient Protocols"">BR93</a>]. We use the FIPS 180 SHA-1 hashing function
[<a href="#ref-FIPS180" title=""Secure Hash Standard"">FIPS180</a>] below to instantiate the random function as done in [<a href="#ref-WLAN" title=""Wireless Local Area Network (WLAN) Interworking"">WLAN</a>];
however, SHA-256 can also be used:
H1(z):
SHA-1(1|1|z) mod 2^128 | SHA-1(1|2|z) mod 2^128 |...|
| SHA-1(1|9|z) mod 2^128
H2(z):
SHA-1(2|1|z) mod 2^128 | SHA-1(2|2|z) mod 2^128 |...|
| SHA-1(2|9|z) mod 2^128
H3(z): SHA-1(3|len(z)|z|z) mod 2^128
H4(z): SHA-1(4|len(z)|z|z) mod 2^128
H5(z): SHA-1(5|len(z)|z|z) mod 2^128
In order to create 1152 output bits for H1 and H2, nine calls to
SHA-1 are made and the 128 least significant bits of each output are
used. The input payload of each call to SHA-1 consists of:
a) 32 bits of function type, which for H1 is set to 1 and for H2 is
set to 2;
b) a 32-bit counter value, which is incremented from 1 to 9 for each
call to SHA-1;
c) the argument z [for (A|B|PW)].
The functions H3, H4, and H5 require only one call to the SHA-1
hashing function and their respective payloads consist of:
a) 32 bits of function type (e.g., 3 for H3);
b) a 32-bit value for the bit length of the argument z;
c) the actual argument repeated twice.
Finally, the 128 least significant bits of the output are used.
<span class="grey">Brusilovsky, et al. Informational [Page 6]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-7" ></span>
<span class="grey"><a href="./rfc5683">RFC 5683</a> PAK Diffie-Hellman Exchange February 2010</span>
<span class="h2"><a class="selflink" id="section-5" href="#section-5">5</a>. Security Considerations</span>
Security considerations are as follows:
- Identifiers
Any protocol that uses PAK must specify a method for producing a
single representation of identity strings.
- Shared secret
PAK involves the use of a shared secret. Protection of the shared
values and managing (limiting) their exposure over time is
essential and can be achieved using well-known security policies
and measures. If a single secret is shared among more than two
entities (e.g., Alice, Bob, and Mallory), then Mallory can
represent himself as Alice to Bob without Bob being any the wiser.
- Selection of Diffie-Hellman parameters
The parameters p and g must be carefully selected in order not to
compromise the shared secret. Only previously agreed-upon values
for parameters p and g should be used in the PAK protocol. This
is necessary to protect against an attacker sending bogus p and g
values and thus tricking the other communicating party in an
improper Diffie-Hellman exponentiation. Both parties also need to
randomly select a new exponent each time the key-agreement
protocol is executed. If both parties re-use the same values,
then Forward Secrecy property is lost.
In addition, if short exponents Ra and Rb are used, then they
should have a minimum size of 384 bits (assuming that 128-bit
session keys are used). Historically, the developers, who strived
for 128-bit security (and thus selected 256-bit exponents), added
128 bits to the exponents to ensure the security reduction proofs.
This should explain how an "odd" length of 384 has been arrived
at.
- Protection against attacks
a) There is a potential attack, the so-called discrete logarithm
attack on the multiplicative group of congruencies modulo p, in
which an adversary can construct a table of discrete logarithms
to be used as a "dictionary". A sufficiently large prime, p,
must be selected to protect against such an attack. A proper
1024-bit value for p and an appropriate value for g are
published in [<a href="#ref-WLAN" title=""Wireless Local Area Network (WLAN) Interworking"">WLAN</a>] and [<a href="#ref-TIA683" title=""Over-the-Air Service Provisioning of Mobile Stations in Spread Spectrum Systems"">TIA683</a>]. For the moment, this is what
has been implemented; however, a larger prime (i.e., one that
<span class="grey">Brusilovsky, et al. Informational [Page 7]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-8" ></span>
<span class="grey"><a href="./rfc5683">RFC 5683</a> PAK Diffie-Hellman Exchange February 2010</span>
is 2048 bits long, or even larger) will definitely provide
better protection. It is important to note that once this is
done, the generator must be changed too, so this task must be
approached with extreme care.
b) An online password attack can be launched by an attacker by
repeatedly guessing the password and attempting to
authenticate. The implementers of PAK should consider
employing mechanisms (such as lockouts) for preventing such
attacks.
- Recommendations on H() functions
The independent, random functions H1 and H2 should output 1152
bits each, assuming prime p is 1024 bits long and session keys K
are 128 bits long. The random functions H3, H4, and H5 should
output 128 bits.
An example of secure implementation of PAK is provided in [<a href="#ref-Plan9" title=""Plan 9 from Bell Labs"">Plan9</a>].
<span class="h2"><a class="selflink" id="section-6" href="#section-6">6</a>. Acknowledgments</span>
The authors are grateful for the thoughtful comments received from
Shehryar Qutub, Ray Perlner, and Yaron Sheffer. Special thanks go to
Alfred Hoenes, Tim Polk, and Jim Schaad for their careful reviews and
invaluable help in preparing the final version of this document.
<span class="h2"><a class="selflink" id="section-7" href="#section-7">7</a>. References</span>
<span class="h3"><a class="selflink" id="section-7.1" href="#section-7.1">7.1</a>. Normative References</span>
[<a id="ref-X.1035">X.1035</a>] ITU-T, "Password-authenticated key exchange (PAK)
protocol", ITU-T Recommendation X.1035, 2007.
[<a id="ref-TIA683">TIA683</a>] TIA, "Over-the-Air Service Provisioning of Mobile
Stations in Spread Spectrum Systems", TIA-683-D, May
2006.
<span class="h3"><a class="selflink" id="section-7.2" href="#section-7.2">7.2</a>. Informative References</span>
[<a id="ref-Plan9">Plan9</a>] Alcatel-Lucent, "Plan 9 from Bell Labs",
<a href="http://netlib.bell-labs.com/plan9/">http://netlib.bell-labs.com/plan9/</a>.
[<a id="ref-BMP00">BMP00</a>] Boyko, V., MacKenzie, P., and S. Patel, "Provably secure
password authentication and key exchange using Diffie-
Hellman", Proceedings of Eurocrypt 2000.
<span class="grey">Brusilovsky, et al. Informational [Page 8]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-9" ></span>
<span class="grey"><a href="./rfc5683">RFC 5683</a> PAK Diffie-Hellman Exchange February 2010</span>
[<a id="ref-BR93">BR93</a>] Bellare, M. and P. Rogaway, "Random Oracles are
Practical: A Paradigm for Designing Efficient Protocols",
Proceedings of the 5th Annual ACM Conference on Computer
and Communications Security, 1998.
[<a id="ref-DH76">DH76</a>] Diffie, W. and M.E. Hellman, "New directions in
cryptography", IEEE Transactions on Information Theory 22
(1976), 644-654.
[<a id="ref-FIPS180">FIPS180</a>] NIST Federal Information Processing Standards,
Publication FIPS 180-3, "Secure Hash Standard", 2008.
[<a id="ref-MP05">MP05</a>] MacKenzie, P. and S. Patel, "Hard Bits of the Discrete
Log with Applications to Password Authentication", CT-RSA
2005.
[<a id="ref-OTASP">OTASP</a>] 3GPP2, "Over-the-Air Service Provisioning of Mobile
Stations in Spread Spectrum Systems", 3GPP2 C.S0016-C v.
1.0 5, October 2004.
[<a id="ref-RFC2631">RFC2631</a>] Rescorla, E., "Diffie-Hellman Key Agreement Method", <a href="./rfc2631">RFC</a>
<a href="./rfc2631">2631</a>, June 1999.
[<a id="ref-WLAN">WLAN</a>] 3GPP2, "Wireless Local Area Network (WLAN) Interworking",
3GPP2 X.S0028-0, v.1.0, April 2005.
<span class="grey">Brusilovsky, et al. Informational [Page 9]</span></pre>
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-10" ></span>
<span class="grey"><a href="./rfc5683">RFC 5683</a> PAK Diffie-Hellman Exchange February 2010</span>
Authors' Addresses
Alec Brusilovsky
Alcatel-Lucent
Room 9B-226, 1960 Lucent Lane
Naperville, IL 60566-7217 USA
Tel: +1 630 979 5490
EMail: Alec.Brusilovsky@alcatel-lucent.com
Igor Faynberg
Alcatel-Lucent
Room 2D-144, 600 Mountain Avenue
Murray Hill, NJ 07974 USA
Tel: +1 908 582 2626
EMail: igor.faynberg@alcatel-lucent.com
Sarvar Patel
Google, Inc.
76 Ninth Avenue
New York, NY 10011 USA
Tel: +1 212 565 5907
EMail: sarvar@google.com
Zachary Zeltsan
Alcatel-Lucent
Room 2D-150, 600 Mountain Avenue
Murray Hill, NJ 07974 USA
Tel: +1 908 582 2359
EMail: zeltsan@alcatel-lucent.com
Brusilovsky, et al. Informational [Page 10]
</pre>
|
