Network Working Group                           A. Brusilovsky
Internet-Draft                                  Lucent Technologies
Expires: September, 2006                                                                                                                            March 5, 2006


     Password Authenticated Diffie-Hellman Exchange (PAK)
                   draft-brusilovsky-pak-01.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 August 15, 2006.

Copyright Notice

   Copyright (C) The Internet Society (2006).

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-01.txt         March 2006



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

    When we propose PAK, we adhere to the following set of requirements:
    a. Mutual authentication based on just a pre-shared,
       human-memorizable password.
    b. Fulfillment of the need to guard against a
       man-in-the-middle and against offline dictionary attack.
    c. Simplicity and openness, to promote  widespread adoption
       and to minimize flaws.

    PAK (Password Authenticated Key exchange) satisfies all of the above.
    PAK was presented at the sacred WG meeting at the IETF63 in Paris, where
    it was proposed as a new work item for the sacred WG.

    PAK advantages are listed here:
    -  Provides strong key exchange with weak passwords

    -  Foils the man-in-the-middle attack

    -  Provides explicit mutual authentication

    -  Ensures Forward Secrecy

    The PAK protocol [BMP00, MP05] has been proved to be as secure as the
    Diffie-Hellman [DH76] problem in the random oracle model [BR93]. That is,
    PAK retains its security when used with low-entropy passwords, hence,
    it can be seamlessly integrated into existing applications, which require
    secure authentication.



Brusilovsky                                                       [Page 2]


Internet Draft           draft-brusilovsky-pak-01.txt         March 2006

2.  Password Authendicated 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.  By raising
    the exchanged value with its secret random number both parties can
    compute the same shared secret Diffie-Hellman key.


    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

    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) 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.

    Initially, Alice selects a secret random exponent x and computes g^x mod p;
    Bob selects a secret random exponent y and computes g^y mod p.
    For efficiency purposes, short exponents could be used for x and y provided
    they have a certain minimum size.  Then:

    1.  Alice initiates the exchange by picking a random x and sending
        Za = H1(A|B|PW)*(g^x mod p) to Bob;
    2.  Bob, upon receiving that quantity, verifies that Za is not a zero and then
        divides it by H1(A|B|PW) to  recover  g^x mod p.
        Then Bob picks a random y and computes
        S1 = H3(A|B|PW|Za/H1(A|B|PW)|g^y mod p|(Za/H1(A|B|PW))^y mod p), and Zb== H2(A|B|PW)*(g^y mod p).
        Alice sends Zb and S1 to Bob.
    3.  Upon receiving that message, Alice checks that Zb is not zero. Now Alice
        can authenticate Bob by recovering what should be g^y mod p using
        H2(A|B|PW), and computing S1 itself.
        If the calculated S1 is equal to the received value, Alice computes the
        key:
        K = H5(A|B|PW|g^x mod p|Zb/H2(A|B|PW) mod p|(Zb/H2(A|B|PW))^x mod p)
        To authenticate herself and to complete the exchange, Alice also computes
        the quantity
Brusilovsky                                                       [Page 3]


Internet Draft           draft-brusilovsky-pak-01.txt         March 2006

        S2 = H4(A|B|PW|g^x mod p|Zb/H2(A|B|PW) mod p|(Zb/H2(A|B|PW))^x mod p)
        and sends it to Bob.
    4.  Bob authenticates Alice by computing S2 himself and checking it against
        the value received from Alice. If both are the same, Bob also computes
        the key
        K = H5(A|B|PW|Za/H1(A|B|PW) mod p|g^y mod p|(Za/H1(A|B|PW))^y mod p)

    If any of the above verifications fails, the protocol halts; otherwise,
    both parties have authenticated each other and established the key.
COMMENT TO ALEC: Aren't we repeating what we just described below???

    A --> B: Za = H1(A|B|PW)*(g^x mod p),

             Bob checks that Za does not equal zero and calculates S1 and Zb:
             S1 = H3(A|B|PW|Za/H1(A|B|PW) mod p|g^y mod p|(Za/H1(A|B|PW))^y mod p)
                 Zb = H2(A|B|PW)*(g^y mod p)

    A <-- B: Zb, S1

             Alice checks that Zb does not equal zero,verifies S1 and calculates
             S2 and K:
             S2 = H4(A|B|PW|g^x mod p|Zb/H2(A|B|PW) mod p|(Zb/H2(A|B|PW))^x mod p)
             K = H5(A|B|PW|g^x mod p|Zb/H2(A|B|PW) mod p|(Zb/H2(A|B|PW))^x mod p)

    A --> B: S2
                 Bob verifies S2 calculates K = H5(A|B|PW|Za/H1(A|B|PW) mod p|g^y mod p|(Za/H1(A|B|PW))^y mod p)



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. In addition, if short exponents [MP05]are used for Diffi-Hellman
    parameters x and y, then they should have a minimum size of 384 bits as also
    required in [OTASP] and [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 to instantiate
    the random function as done in [WLAN]:

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(3,len(z),z,z) mod 2^128
H4(z): SHA(4,len(z),z,z) mod 2^128

Brusilovsky                                                       [Page 4]


Internet Draft           draft-brusilovsky-pak-01.txt         March 2006

    H5(z): SHA(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 keys. Protection the shared values and managing
    (limiting) their exposure over time is of outmost importance.



Brusilovsky                                                       [Page 3]


Internet Draft           draft-brusilovsky-pak-01.txt         March 2006


6.  References

    [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.

Brusilovsky                                                       [Page 5]


Internet Draft           draft-brusilovsky-pak-01.txt         March 2006

    [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 Standards, 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


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

    [X.800]     ITU-T Recommendation X.805 (2003), Security Architecture for
                Systems Providing End to end Communications.


Authors' and Contributors' Addresses

    Alec Brusilovsky
    Lucent Technologies
    1960 Lucent Lane,
    Naperville, IL 60564 USA
    Tel: +1 630 979 5490
    Email: abrusilovsky@lucent.com

    Igor Faynberg
    Lucent Technologies
    Tel: +1 732 949 0137
    Email: faynberg@lucent.com

    Sarvar Patel
    Lucent Technologies
    Tel: +1 973 386 6558
    Email: sarvar@lucent.com

    Zachary Zeltsan
    Lucent Technologies
    Tel: +1 732 949 4187
    Email: zeltsan@lucent.com

Brusilovsky                                                       [Page 6]


Internet Draft           draft-brusilovsky-pak-01.txt         March 2006

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.


Copyright Statement

    Copyright (C) The Internet Society (2006).

    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 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 7]


Brusilovsky                                                       [Page 5]