Network Working Group A. Brusilovsky
Internet-Draft I. Faynberg
Expires: May 2008 S. Patel
Z. Zeltsan
Alcatel-Lucent
November 2007
Password-Authenticated Diffie-Hellman Exchange (PAK)
draft-brusilovsky-pak-06.txt
Status of this Memo
By submitting this Internet-Draft, each author represents that
any applicable patent or other IPR claims of which he or she
is aware have been or will be disclosed, and any of which he
or she becomes aware will be disclosed, in accordance with
Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as
Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on January 7, 2008.
Copyright Notice
Copyright (C) The Internet Society (2007).
Abstract
This document proposes to add mutual authentication, based on
human-memorizable password, to the basic unauthenticated Diffie-Hellman
key exchange. The proposed algorithm is called Password-authenticated
Key exchange (PAK). 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 attackers to obtain any
information that would enable an off-line dictionary attack on the
password. The use of Diffie-Hellman exchange ensures Forward Secrecy.
Brusilovsky [Page 1]
Internet Draft draft-brusilovsky-pak-06.txt November 2007
Table of Contents
1. Introduction
2. Password Authendicated Key exchange
3. Diffie-Hellman parameters
4. IANA considerations
5. Security Considerations
6. Acknowledgments
7. References
Authors' and Contributors' Addresses
1. Introduction
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 is proved to be as secure as the Diffie-Hellman solution.
The PAK protocol [BMP00, MP05, X.1035] has been proven to be as secure
as the Diffie-Hellman [DH76] in the random oracle model [BR93]. 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.
2. Password Authenticated Key exchange
We briefly describe PAK in this section. Details of the protocol are
omitted for simplicity.
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 and Bob, sharing a secret password PW. The
global Diffie-Hellman publicly known constants:
a prime p and a generator g are carefully selected so that:
Brusilovsky [Page 2]
Internet Draft draft-brusilovsky-pak-06.txt November 2007
1. A safe prime p is large enough to make the computation of discrete
logarithm infeasible and
2. Powers of g modulo p cover the entire range of p-1 integers from 1 to
p-1. (References demonstrate working example of selections).
Conventions in this I-D:
- a mod b denotes the least non-negative remainder when a is divided by b;
- Hi(u) denotes an agreed-on hash function (e.g., based on SHA-1, SHA-256,
etc.) computed over a string u; The various H() act as independent random
functions.
- s|t denotes concatenation of the strings s and t;
- ^ denotes exponentiation.
- multiplication, division, and exponentiation is performed over (Zp)*;
in other words:
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 module p
3) a^b means a^b (mod p).
Initially, Alice selects a secret random exponent Ra and computes g^Ra;
Bob 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: X = H1(A|B|PW)*g^Ra
Bob
verifies that X <> 0;
divides X by H1(A|B|PW) to get g^Ra?, the recovered value of g^Ra.
B --> A: Y = H2(A|B|PW)*g^Rb
S1 = H3(A|B|PW|g^Ra?|g^Rb|(g^Ra?)^Rb)
Alice
verifies that Y <> 0;
divides Y by H2(A|B|PW) to get g^Rb?, the recovered value of g^Rb.
authenticates Bob by checking if computed S1 equals received S1;
Computed S1 = H3(A|B|PW|g^Ra|g^Rb?|(g^Rb?)^Ra).
If authenticated then sets key K = H5(A|B|PW|g^Ra|g^Rb?|(g^Rb?)^Ra)
Brusilovsky [Page 3]
Internet Draft draft-brusilovsky-pak-06.txt November 2007
A --> B: S2 = H4(A|B|PW|g^Ra|g^Rb?|(g^Rb?)^Ra)
Bob
authenticates Alice by checking if computed S2 equals received S2;
Computed S2 = H3(A|B|PW|g^Ra?|g^Rb|(g^Ra?)^Rb).
If authenticated then sets K = H5(A|B|PW|g^Ra?|g^Rb|(g^Ra?)^Rb)
If any of the above verifications fails, the protocol halts; otherwise,
both parties have authenticated each other and established the key.
3. Diffie-Hellman parameters:
[OTASP] and [WLAN] pre-sets 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 [WLAN] g shall be set to 00001101, and p to the following 1024-bit
prime number (Most Significant Bit first):
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 [MP05] are used for Diffie-Hellman
parameters x and y, then they should have a minimum size of 384 bits as also
required in [WLAN]. 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 [BR93]. We use the FIPS 180 SHA-1 hashing function below to instantiate
the random function as done in [WLAN], however, SHA-256 could 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
Brusilovsky [Page 4]
Internet Draft draft-brusilovsky-pak-06.txt November 2007
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 128 lsbs 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 counter value which is incremented from 1 to 9 for each call of SHA-1;
c) and, finally, the argument z to the function which in our application is
(A|B|PW).
The functions H3, H4, and H5 require only one call to the SHA-1 hashing function
and its payload consists of:
a) 32 bits of function type (e.g. 3 for H3);
b) a 32 bit value for the length of the argument z;
c) the actual argument repeated twice.
Finally, the 128 least significant bits of the output are used.
4. IANA considerations
No IANA considerations at this time
5. Security Considerations
PAK involves the use of shared secret. Protection of the shared values and managing
(limiting) their exposure over time is of outmost importance.
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. The use of the parameters p and g that do not meet
the requirements described in this Recommendation may result in a compromise of
the password PW (shared secret). A proper 1024-bit value for p and an appropriate
value for g are published in the TIA Standard TIA-683-D.
In addition, if short exponents are used for Diffie-Hellman parameters Ra and Rb
then they should have a minimum size of 384 bits (assuming 128 bit session keys
are used) as also required in TIA Standard TIA-683-D.
The independent random functions H1 and H2 should have 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 have output 128 bits.
Brusilovsky [Page 5]
Internet Draft draft-brusilovsky-pak-06.txt November 2007
6. Acknowledgments
The authors are grateful for the thoughtful comments received from Shehryar Qutub
and Yaron Sheffer.
7. References and bibliography
[BMP00] V. Boyko, P. MacKenzie, S. Patel, Provably secure password
authentication and key exchange using Diffie-Hellman,
Proc. of Eurocrypt 2000.
[BR93] M. Bellare and P. Rogaway, Random Oracles are Practical:
A Paradigm for Designing Efficient Protocols, Proc. Of the
fifth annual conference on computer and communications
security, 1993.
[DH76] W. Diffie and M.E. Hellman, New directions in cryptography,
IEEE Transactions on Information Theory 22 (1976), 644-654.
[MP05] P. MacKenzie, S. Patel, Hard Bits of the Discrete Log with
Applications to Password Authentication, CT-RSA 2005.
[RFC2631] IETF RFC 2631, E. Rescorla, Diffie-Hellman Key Agreement
Method, Standards track,1999
[SHA1] National Institute of Standards and Technology (NIST),
"Announcing the Secure Hash Standard", FIPS 180-1, U.S.
Department of Commerce, April 1995.
[OTASP] Over-the-Air Service Provisioning of Mobile Stations in Spread
Spectrum Systems, 3GPP2 C.S0016-C v. 1.0 5, 3GPP2, 10/2004.
[WLAN] Wireless Local Area Network (WLAN) Interworking, 3GPP2 X.S0028-0,
v.1.0, 3GPP2, 4/2005
[X.805] ITU-T Recommendation X.805 (2003), Security Architecture for
Systems Providing End to end Communications.
[X.1035] ITU-T Recommendation X.1035, Password-authenticated key exchange
(PAK) protocol
[FIPS180] NIST Federal Information Processing Standards,
Publication FIPS 180-1
[IEEE1363] IEEE P1363.2, April 24, 2002, The PAK suite: Protocols for
Password-Authentication Key Exchange, P. MacKenzie
Brusilovsky [Page 6]
Internet Draft draft-brusilovsky-pak-06.txt November 2007
Authors' and Contributors' Addresses
Alec Brusilovsky
Alcatel-Lucent
Tel: +1 630 979 5490
Email: abrusilovsky@alcatel-lucent.com
Igor Faynberg
Alcatel-Lucent
Tel: +1 908 582 2626
Email: faynberg@alcatel-lucent.com
Sarvar Patel
Alcatel-Lucent
Tel: +1 973 386 6558
Email: sarvar@alcatel-lucent.com
Zachary Zeltsan
Alcatel-Lucent
Tel: +1 908 582 2359
Email: zeltsan@alcatel-lucent.com
Intellectual Property Statement
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Brusilovsky [Page 7]
Internet Draft draft-brusilovsky-pak-06.txt November 2007
Copyright Statement
Copyright (C) The IETF Trust (2007).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided
on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE
REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE
IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL
WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY
WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE
ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS
FOR A PARTICULAR PURPOSE.
Brusilovsky [Page 8]