Network Working Group
Independent Submission                                    A. Brusilovsky
Internet-Draft
Request for Comments: 5683                                   I. Faynberg
Expires: September 2009
Category: Informational                                       Z. Zeltsan
ISSN: 2070-1721                                           Alcatel-Lucent
                                                                S. Patel
                                                            Google, Inc.

                                                April 2009
                                                            January 2010

        Password-Authenticated Key (PAK) Diffie-Hellman Exchange

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)

                   draft-brusilovsky-pak-10.txt 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 This Memo

   This Internet-Draft document is not an Internet Standards Track specification; it is submitted
   published for informational purposes.

   This is a contribution to IETF in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents RFC Series, independently of the Internet Engineering
   Task Force (IETF), any other
   RFC stream.  The RFC Editor has chosen to publish this document at
   its areas, discretion and makes no statement about its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid value for
   implementation or deployment.  Documents approved for publication by
   the RFC Editor are not a maximum candidate for any level of Internet
   Standard; see Section 2 of RFC 5741.

   Information about the current status of six months this document, any errata,
   and how to provide feedback on it may be updated, replaced, or obsoleted by other documents obtained at any
   time.  It
   http://www.rfc-editor.org/info/rfc5683.

IESG Note

   This RFC is inappropriate not a candidate for any level of Internet Standard.  The
   IETF disclaims any knowledge of the fitness of this RFC for any
   purpose and in particular notes that the decision to use Internet-Drafts publish is not
   based on IETF review for such things as reference
   material security, congestion control,
   or to cite them other than as "work in progress." inappropriate interaction with deployed protocols.  The list of current Internet-Drafts can be accessed RFC Editor
   has chosen to publish this document at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list its discretion.  Readers of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire
   this document should exercise caution in September, 2009. evaluating its value for
   implementation and deployment.  See RFC 3932 for more information.

Copyright Notice

   Copyright (c) 2009 2010 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 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 (http://trustee.ietf.org/license-info). document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.

Abstract

   This document proposes to add mutual authentication, based on
   human-memorizable password, to the basic unauthenticated Diffie-Hellman
   key exchange. may contain material from IETF Documents or IETF
   Contributions published or made publicly available before November
   10, 2008.  The proposed algorithm is called Password-authenticated
   Key exchange (PAK). PAK allows two parties person(s) controlling the copyright in some of this
   material may not have granted the IETF Trust the right to authenticate themselves
   while performing allow
   modifications of such material outside the Diffie-Hellman exchange.

   The protocol is secure against all passive IETF Standards Process.
   Without obtaining an adequate license from the person(s) controlling
   the copyright in such materials, this document may not be modified
   outside the IETF Standards Process, and active attacks.
   In particular, derivative works of it does may
   not allow either type of attackers be created outside the IETF Standards Process, except to obtain any
   information that would enable format
   it for publication as an off-line dictionary attack on the
   password. PAK provides Forward Secrecy. RFC or to translate it into languages other
   than English.

Table of Contents

   1. Introduction ....................................................3
   2. Conventions .....................................................3
   3. Password-Authenticated Key exchange Exchange .............................4
   4. Selection of parameters
   4.1 Parameters .........................................5
      4.1. General considerations
   4.2 OTASP Considerations .....................................5
      4.2. Over-the-Air Service Provisioning (OTASP) and WLAN Wireless
           Local Area Network (WLAN) Diffie-Hellman parameters Parameters and key expansion functions
           Key Expansion Functions ....................................5
   5. Security considerations Considerations .........................................7
   6.  IANA considerations
   7. Acknowledgments
   8. .................................................8
   7. References
   8.1 ......................................................8
      7.1. Normative references
   8.2 References .......................................8
      7.2. Informative references
   Authors' and contributors' addresses References .....................................8

1.  Introduction

   PAK has the following advantages:

   -  It provides a secure secure, authenticated key exchange key-exchange protocol.
   -  It is secure against offline dictionary attacks when passwords are
      used.
   -  It ensures Forward Secrecy.
   -  It is proved has been proven to be as secure as the Diffie-Hellman solution.

   The PAK protocol [BMP00], ([BMP00], [MP05], [X.1035] [X.1035]) has been proven to be as
   secure as the Diffie-Hellman [RFC2631], [DH76] ([RFC2631], [DH76]) in the random oracle
   model [BR93].  That is, PAK retains its security when used with low-entropy low-
   entropy passwords.  Therefore, it can be seamlessly integrated into
   existing applications, requiring secure authentication based on such
   low-entropy shared secrets.

2.  Conventions

   -  A is an identity of Alice Alice.

   -  B is an identity of Bob Bob.

   -  Ra is a secret random exponent selected by A A.

   -  Rb is a secret random exponent selected by B B.

   -  Xab denotes a value (X presumably computed by A) as derived by B B.

   -  Yba denotes a value (Y presumably computed by B) as derived by A A.

   - a  A mod b denotes the least non-negative remainder when a is divided
      by b; b.

   -  Hi(u) denotes an agreed-on function (e.g., based on SHA-1, SHA-256, SHA-
      256, etc.) computed over a string u; The 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; t.

   -  ^ denotes exponentiation; exponentiation.

   - multiplication,  Multiplication, division, and exponentiation are performed over
      (Zp)*; in other words:

      1) a*b always means a*b (mod p) p).

      2) a/b always means a * x (mod p), where x is the multiplicative
         inverse of b modulo p p.

      3) a^b means a^b (mod p).

3.  Password Authenticated  Password-Authenticated Key exchange Exchange

   Diffie-Hellman key agreement requires that both the sender and
   recipient of a message create their own secret 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. 0

   The global Diffie-Hellman publicly-known 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 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 examples of
       selections).

   Initially, Alice (A) selects a secret secret, random exponent Ra and
   computes g^Ra; Bob (B) selects a secret secret, random exponent Rb and
   computes g^Rb.  For efficiency purposes, short exponents could be
   used for Ra and Rb 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); 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;

      - g^Ra
   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 g^Rb,
        and computes S1' = H3(A|B|PW|g^Ra|Yba|(Yba)^Ra);
        authenticates Bob by checking whether S1' equals = the received 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' equals = the received S2;
        if authenticated 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.

4.  Selection of parameters Parameters

   This section provides guidance on selection of the PAK parameters.
   First, it addresses general considerations, then it reports on
   specific implementations.

4.1

4.1.  General considerations Considerations

   In general implementations, the parameters must be selected to meet
   algorithm requirements of [BMP00].

4.2 OTASP

4.2.  Over-the-Air Service Provisioning (OTASP) and WLAN Wireless Local Area
      Network (WLAN) Diffie-Hellman parameters Parameters and key expansion functions Key Expansion
      Functions

   [OTASP], [TIA 683], [TIA683], and [WLAN] 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 values, tricking the legitimate user
   to engage in improper Diffie-Hellman exponentiation and leaking some
   information about the password.

   According to [OTASP], [TIA 683], [TIA683], and [WLAN], g shall be set to
   00001101, and p to the following 1024-bit prime number (Most-significant-bit (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 Ra and Rb, then they should have a minimum size of 384
   bits.  The independent independent, random functions H1 and H2 should each output
   1152 bits 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
   [FIPS180] below to instantiate the random function as done in [WLAN], [WLAN];
   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 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 type, which for H1 is set to 1 and for H2 is
      set to 2;
   b) a 32 bit 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. (e.g., 3 for H3);
   b) a 32 bit 32-bit value for the bit length of the argument z;
   c) the actual argument repeated twice.

   Finally, the 128 least-significant least significant bits of the output are used.

5.  Security Considerations

   Security considerations

    Those 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,
      essential and
    it 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, parameters p and g, g must be carefully selected in order not to
      compromise the shared secret.  Only previously agreed upon 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 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 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) exponents), added
      128 bits to the exponents to ensure the security reductions 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 [WLAN] and [TIA 683]. [TIA683].  For the moment, this is what
         has been implemented; however, a larger prime (i.e., one that
         is 2048-bit long 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, changed too, so this task must be
         approached with extreme care.

      b) An on-line 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 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 [Plan 9]. [Plan9].

6.  IANA considerations

    No IANA considerations at this time

7.  Acknowledgments

   The authors are grateful for the thoughtful comments received from
   Shehryar Qutub, Yaron Sheffer, and Ray Perlner. Perlner, and Yaron Sheffer.  Special thanks go to
   Alfred Hoenes, Tim Polk, and Jim Schaad for the their careful reviews and
   invaluable help in preparing the final version of this document.

8.

7.  References

8.1

7.1.  Normative references References

   [X.1035]    ITU-T Recommendation X.1035 (2007), Password-authenticated    ITU-T, "Password-authenticated key exchange (PAK) protocol

    [TIA 683]   Over-the-Air
               protocol", ITU-T Recommendation X.1035, 2007.

   [TIA683]    TIA, "Over-the-Air Service Provisioning of Mobile
               Stations in Spread Spectrum Systems, TIA TIA-683-D

8.2 Systems", TIA-683-D, May
               2006.

7.2.  Informative references

    [Plan 9]    Plan References

   [Plan9]     Alcatel-Lucent, "Plan 9 ? An open source operating system, which implements PAK
                http://netlib.bell-labs.com/plan9dist/ from Bell Labs",
               http://netlib.bell-labs.com/plan9/.

   [BMP00]     V.     Boyko, P. V., MacKenzie, P., and S. Patel, Provably "Provably secure
               password authentication and key exchange using Diffie-Hellman,
                Proc. Diffie-
               Hellman", Proceedings of Eurocrypt 2000.

   [BR93]      Bellare, M. Bellare and P. Rogaway, Random "Random Oracles are
               Practical: A Paradigm for Designing Efficient Protocols, Proc. Of the
                fifth annual conference Protocols",
               Proceedings of the 5th Annual ACM Conference on computer Computer
               and communications
                security, 1993. Communications Security, 1998.

   [DH76]      Diffie, W. Diffie and M.E. Hellman, New "New directions in cryptography,
               cryptography", IEEE Transactions on Information Theory 22
               (1976), 644-654.

   [FIPS180]   NIST Federal Information Processing Standards,
               Publication FIPS 180-3, 2008

    [IEEE1363]  IEEE P1363.2, April 24, 2002, The PAK suite: Protocols for
                Password-Authentication Key Exchange, P. MacKenzie "Secure Hash Standard", 2008.

   [MP05]      P.      MacKenzie, P. and S. Patel, Hard "Hard Bits of the Discrete
               Log with Applications to Password Authentication, Authentication", CT-RSA
               2005.

   [OTASP]     Over-the-Air     3GPP2, "Over-the-Air Service Provisioning of Mobile
               Stations in Spread Spectrum Systems, Systems", 3GPP2 C.S0016-C v.
               1.0 5, 3GPP2, 10/2004. October 2004.

   [RFC2631]   IETF RFC 2631, E.   Rescorla, Diffie-Hellman E., "Diffie-Hellman Key Agreement
                Method, Standards track,1999 Method", RFC
               2631, June 1999.

   [WLAN]      Wireless      3GPP2, "Wireless Local Area Network (WLAN) Interworking, Interworking",
               3GPP2 X.S0028-0, v.1.0, 3GPP2, 4/2005 April 2005.

Authors' and Contributors' Addresses

   Alec Brusilovsky
   Alcatel-Lucent
   Room 9B-226, 1960 Lucent Lane
   Naperville, IL 60566-7217  U S  USA
   Tel: +1 630 979 5490
    Email:
   EMail: abrusilovsky@alcatel-lucent.com

   Igor Faynberg
   Alcatel-Lucent
   Room 2D-144, 600 Mountain Avenue
   Murray Hill, NJ 07974  USA
   Tel: +1 908 582 2626
    Email:
   EMail: faynberg@alcatel-lucent.com

   Sarvar Patel
   Google, Inc.
   76 Ninth Avenue
   New York, NY 10011  USA
   Tel: +1 212 565 5907
    Email:
   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:
   EMail: zeltsan@alcatel-lucent.com

Intellectual Property

   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.