Internet Info 1997 December/Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso/drafts/draft_s_z/draft-wu-srp-auth-00.txt

Text File | 1997-09-11 | 16KB | 360 lines

Internet Draft                                                     T. Wu
draft-wu-srp-auth-00.txt                             Stanford University
Expires 31 March 1998                                     September 1997


            The SRP Authentication and Key Exchange System

Status of this Memo

     This document is an Internet-Draft.  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."

     To view the entire list of current Internet-Drafts, please check
     the "1id-abstracts.txt" listing contained in the Internet-Drafts
     Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net
     (Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East
     Coast), or ftp.isi.edu (US West Coast).

Abstract

   This document describes a cryptographically strong network
   authentication mechanism known as the Secure Remote Password (SRP)
   protocol.  This mechanism is suitable for negotiating secure
   connections using a user-supplied password, while eliminating the
   security problems traditionally associated with reusable passwords.
   This system also performs a secure key exchange in the process of
   authentication, allowing security layers (privacy and/or integrity
   protection) to be enabled during the session.  Trusted key servers
   and certificate infrastructures are not required, and clients are
   not required to store or manage any long-term keys.  SRP offers
   both security and deployment advantages over existing challenge-
   response techniques, making it an ideal drop-in replacement where
   secure password authentication is needed.

1. Introduction

   The lack of a secure authentication mechanism that is also easy
   to use has been a long-standing problem with the vast majority of
   Internet protocols currently in use.  The problem is two-fold:
   Users like to use passwords that they can remember, but most
   password-based authentication systems offer little protection
   against even passive attackers, especially if weak and easily-
   guessed passwords are used.


draft-ietf-wu-srp-auth-00.txt                                   [Page 2]

   Eavesdropping on a TCP/IP network can be carried out very easily
   and very effectively against protocols that transmit passwords in
   the clear.  Even so-called "challenge-response" techniques like
   the one described in [RFC 2095] and [RFC 1760], which are designed
   to defeat simple sniffing attacks, can be compromised by what is
   known as a "dictionary attack".  This occurs when an attacker
   captures the messages exchanged during a legitimate run of the
   protocol and uses that information to verify a series of guessed
   passwords taken from a precompiled "dictionary" of common passwords.
   This works because users often choose simple, easy-to-remember
   passwords, which invariably are also easy to guess.

   Many existing mechanisms also require the password database on the
   host to be kept secret because the password P or some private hash
   h(P) is stored there and would compromise security if revealed.
   That approach often degenerates into "security through obscurity"
   and goes against the UNIX convention of keeping a "public" password
   file whose contents can be revealed without destroying system security.

   SRP meets the strictest requirements laid down in [RFC 1704] for a
   non-disclosing authentication protocol.  It offers complete protection
   against both passive and active attacks, and accomplishes this
   efficiently using a single Diffie-Hellman-style round of computation,
   making it feasible to use in both interactive and non-interactive
   authentication for a wide range of Internet protocols.  Since it
   retains its security when used with low-entropy passwords, it can
   be seamlessly integrated into existing user applications.

2. Conventions and Terminology

   The protocol described by this document is officially known as
   "SRP-3" for the sake of clarity.  This particular protocol is
   described in [SRP] and is believed to have very good logical
   and cryptographic resistance to both eavesdropping and active
   attacks.

   This document does not attempt to describe SRP-3 in the context
   of any particular Internet protocol; instead it describes an
   abstract protocol that can be easily fitted to a particular
   application.  For example, the specific format of messages
   (including padding) is not specified.  Those issues have been
   left to the protocol implementor to decide.

   The one implementation issue worth specifying here is the
   mapping between strings and integers.  Internet protocols are
   byte-oriented, while SRP-3 performs algebraic operations on its
   messages, so it is logical to define at least one method
   by which integers can be converted into a string of bytes and
   vice versa.


draft-ietf-wu-srp-auth-00.txt                                   [Page 3]

   An n-byte string S can be converted to an integer as follows:

   i = S[n-1] + 256 * S[n-2] + 256^2 * S[n-3] + ... + 256^(n-1) * S[0]

   where i is the integer and S[x] is the value of the x'th byte
   of S.  In human terms, the string of bytes is the integer
   expressed in base 256, with the most significant digit first.
   When converting back to a string, S[0] must be non-zero (padding
   is considered to be a separate, independent process).  This
   conversion method is suitable for file storage, in-memory
   representation, and network transmission of large integer
   values.  Unless otherwise specified, this mapping will be
   assumed.

   If implementations require padding a string that represents an
   integer value, it is recommended that they use zero bytes and
   add them to the beginning of the string.  The conversion back to
   integer automatically discards leading zero bytes, making this
   padding scheme less prone to error.

   The SHA hash function, when used in this document, refers to the
   SHA-1 message digest algorithm described in [SHA1].

3. The SRP3-SHA1 mechanism

   This section describes an implementation of the SRP-3 authentication
   and key-exchange protocol that employs the SHA hash function to
   generate session keys and authentication proofs.

   The host stores user passwords as triplets of the form

     { <username>, <password verifier>, <salt> }

   Password entries are generated as follows:

     <salt> = random()
     x = SHA(<salt> | SHA(<username> | ":" | <raw password>))
     <password verifier> = v = g^x % N

   The | symbol indicates string concatenation, the ^ operator is the
   exponentiation operation, and the % operator is the integer remainder
   operation.  Most implementations perform the exponentiation and
   remainder in a single stage to avoid generating unwieldy intermediate
   results.  Note that the 160-bit output of SHA is implicitly converted
   to an integer before it is operated upon.


draft-ietf-wu-srp-auth-00.txt                                   [Page 4]

   Authentication is generally initiated by the client.

        Client                             Host
       --------                           ------
        U = <username>              -->
                                    <--    s = <salt from passwd file>

   Upon identifying himself to the host, the client will receive
   the salt stored on the host under his username.

        a = random()
        A = g^a % N                 -->
                                           v = <stored password verifier>
                                           b = random()
                                    <--    B = (v + g^b) % N

        p = <raw password>
        x = SHA(s | SHA(u | ":" | p))

        S = (B - g^x) ^ (a + u * x) % N    S = (A * v^u) ^ b % N
    K = SHA_Interleave(S)              K = SHA_Interleave(S)
        (this function is described
         in the next section)

   The client generates a random number, raises g to that power modulo
   the field prime, and sends the result to the host.  The host
   does the same thing and also adds the public verifier before
   sending it to the client.  Both sides then construct the shared
   session key based on the respective formulae.

   The parameter u is a 32-bit unsigned integer which takes its
   value from the first 32 bits of the SHA1 hash of B, MSB first.

   The client MUST abort authentication if B % N is zero.

   The host MUST abort the authentication attempt if A % N is
   zero.  The host MUST send B after receiving A from the client,
   never before.

   At this point, the client and server should have a common
   session key that is secure (i.e. not known to an outside party).
   To finish authentication, they must prove to each other that
   their keys are identical.

        M = H(H(N) XOR H(g) | H(U) | s | A | B | K)
                                    -->
                                    <--    H(A | M | K)

   The server will calculate M using its own K and compare
   it against the client's response.  If they do not match, the
   server MUST abort and signal an error before it attempts to
   answer the client's challenge.  Not doing so could compromise the
   security of the user's password.


draft-ietf-wu-srp-auth-00.txt                                   [Page 5]

   If the server receives a correct response, it issues its own proof
   to the client.  The client will compute the expected response using
   its own K to verify the authenticity of the server.  If the client
   responded correctly, the server MUST respond with its hash value.

   The transactions in this protocol description do not necessarily
   have a one-to-one correspondence with actual protocol messages.
   This description is only intended to illustrate the relationships
   between the different parameters and how they are computed.
   It is possible, for example, for an implementation of the SRP3-SHA1
   mechanism to consolidate some of the flows as follows:

        Client                             Host
       --------                           ------
        U, A                        -->
                                    <--    s, B
        H(H(N) XOR H(g) | H(U) | s | A | B | K)
                                    -->
                                    <--    H(A | M | K)

   The values of N and g used in this protocol must be agreed upon
   by the two parties in question.  They can be set in advance, or
   the host can supply them to the client.  In the latter case, the
   host should send the parameters in the first message along with
   the salt.  For maximum security, N should be a safe prime
   (i.e. a number of the form N = 2q + 1, where q is also prime).
   Also, g should be a generator modulo N (see [SRP] for details),
   which means that for any X where 0 < X < N, there exists a value
   x for which g^x % N == X.

3.1.  Interleaved SHA

   The SHA_Interleave function used in SRP3-SHA1 is used to generate
   a session key that is twice as long as the 160-bit output of SHA1.
   To compute this function, remove all leading zero bytes from the
   input.  If the length of the resulting string is odd, also remove
   the first byte.  Call the resulting string T.  Extract the
   even-numbered bytes into a string E and the odd-numbered bytes
   into a string F, i.e.

     E = T[0] | T[2] | T[4] | ...
     F = T[1] | T[3] | T[5] | ...

   Both E and F should be exactly half the length of T.  Hash each
   one with regular SHA1, i.e.

     G = SHA(E)
     H = SHA(F)

   Interleave the two hashes back together to form the output, i.e.

     result = G[0] | H[0] | G[1] | H[1] | ... | G[19] | H[19]

   The result will be 40 bytes (320 bits) long.


draft-ietf-wu-srp-auth-00.txt                                   [Page 6]

3.2.  Other Hash Algorithms

   SRP-3 can be used with hash functions other than SHA.
   If the hash function produces an output of a different length
   than SHA (20 bytes), it may change the length of some of the
   messages in the protocol, but the fundamental operation will
   be unaffected.

   Earlier versions of the SRP mechanism used the MD5 hash function,
   described in [RFC 1321].

   Any hash function used with SRP should produce an output of at
   least 16 bytes and have the property that small changes in the
   input cause significant nonlinear changes in the output.  [SRP]
   covers these issues in more depth.

4. Intellectual Property Considerations

   The SRP-3 authentication protocol will be made available worldwide
   on a royalty-free basis for non-commercial uses.  Stanford
   University has filed a patent application for SRP, and it
   is expected that commercial licensing terms will be nominal,
   open, and fair.

5. Security Considerations

   This entire draft discusses an authentication and key-exchange
   system that protects passwords and exchanges keys across an
   untrusted network.  This system improves security by eliminating
   the need to send cleartext passwords over the network and by
   enabling encryption through its secure key-exchange mechanism.

   SRP-3 has been designed not only to counter the threat of casual
   password-sniffing, but also to prevent a determined attacker
   equipped with a dictionary of passwords from guessing at
   passwords using captured network traffic.  The SRP-3 protocol
   itself also resists active network attacks, and implementations
   can use the securely exchanged keys to protect the session against
   hijacking and provide confidentiality.

   SRP-3 also has the added advantage of permitting the host to store
   passwords in a form that is not directly useful to an attacker.
   Even if the host's password database were publicly revealed,
   the attacker would still need an expensive dictionary search to
   obtain any passwords.  The exponential computation required to
   validate a guess in this case is much more time-consuming than
   the hash currently used by most UNIX systems.  Hosts are still
   advised, though, to try their best to keep their password files
   secure.


draft-ietf-wu-srp-auth-00.txt                                   [Page 7]

6. References

   [RFC 1321]  R. L. Rivest, The MD5 Message-Digest Algorithm, "Request
               For Comments (RFC) 1321", MIT and RSA Data Security, Inc.,
               April 1992

   [RFC 1704]  N. Haller and R. Atkinson, On Internet Authentication,
               "Request for Comments (RFC) 1704", NRL, October 1994

   [RFC 1760]  N. Haller, The S/Key One-Time Password System, "Request
               For Comments (RFC) 1760", Bellcore, Feburary 1995

   [RFC 2095]  J. Klensin, R. Catoe, P. Krumviede, IMAP/POP AUTHorize
               Extension for Simple Challenge/Response, "Request For
               Comments (RFC) 2095", MCI, January 1997

   [SHA1]  National Institute of Standards and Technology (NIST),
           "Announcing the Secure Hash Standard", FIPS 180-1, U.S.
           Department of Commerce, April 1995.

   [SRP]  T. Wu, The Secure Remote Password Protocol, work in progress

7. Author's Address

   Thomas Wu
   Stanford University
   Stanford, CA 94305

   Phone: [phone]
   EMail: [e-mail]