Initial release, version 0.0.0.
[gsasl.git] / doc / specification / rfc2945.txt
blob983c441c3508cef660c51c007629f33182a88ee2
7 Network Working Group                                              T. Wu
8 Request for Comments: 2945                           Stanford University
9 Category: Standards Track                                 September 2000
12              The SRP Authentication and Key Exchange System
14 Status of this Memo
16    This document specifies an Internet standards track protocol for the
17    Internet community, and requests discussion and suggestions for
18    improvements.  Please refer to the current edition of the "Internet
19    Official Protocol Standards" (STD 1) for the standardization state
20    and status of this protocol.  Distribution of this memo is unlimited.
22 Copyright Notice
24    Copyright (C) The Internet Society (2000).  All Rights Reserved.
26 Abstract
28    This document describes a cryptographically strong network
29    authentication mechanism known as the Secure Remote Password (SRP)
30    protocol.  This mechanism is suitable for negotiating secure
31    connections using a user-supplied password, while eliminating the
32    security problems traditionally associated with reusable passwords.
33    This system also performs a secure key exchange in the process of
34    authentication, allowing security layers (privacy and/or integrity
35    protection) to be enabled during the session.  Trusted key servers
36    and certificate infrastructures are not required, and clients are not
37    required to store or manage any long-term keys.  SRP offers both
38    security and deployment advantages over existing challenge-response
39    techniques, making it an ideal drop-in replacement where secure
40    password authentication is needed.
42 1. Introduction
44    The lack of a secure authentication mechanism that is also easy to
45    use has been a long-standing problem with the vast majority of
46    Internet protocols currently in use.  The problem is two-fold: Users
47    like to use passwords that they can remember, but most password-based
48    authentication systems offer little protection against even passive
49    attackers, especially if weak and easily-guessed passwords are used.
51    Eavesdropping on a TCP/IP network can be carried out very easily and
52    very effectively against protocols that transmit passwords in the
53    clear.  Even so-called "challenge-response" techniques like the one
54    described in [RFC 2095] and [RFC 1760], which are designed to defeat
58 Wu                          Standards Track                     [Page 1]
60 RFC 2945        SRP Authentication & Key Exchange System  September 2000
63    simple sniffing attacks, can be compromised by what is known as a
64    "dictionary attack".  This occurs when an attacker captures the
65    messages exchanged during a legitimate run of the protocol and uses
66    that information to verify a series of guessed passwords taken from a
67    precompiled "dictionary" of common passwords.  This works because
68    users often choose simple, easy-to-remember passwords, which
69    invariably are also easy to guess.
71    Many existing mechanisms also require the password database on the
72    host to be kept secret because the password P or some private hash
73    h(P) is stored there and would compromise security if revealed.  That
74    approach often degenerates into "security through obscurity" and goes
75    against the UNIX convention of keeping a "public" password file whose
76    contents can be revealed without destroying system security.
78    SRP meets the strictest requirements laid down in [RFC 1704] for a
79    non-disclosing authentication protocol.  It offers complete
80    protection against both passive and active attacks, and accomplishes
81    this efficiently using a single Diffie-Hellman-style round of
82    computation, making it feasible to use in both interactive and non-
83    interactive authentication for a wide range of Internet protocols.
84    Since it retains its security when used with low-entropy passwords,
85    it can be seamlessly integrated into existing user applications.
87 2. Conventions and Terminology
89    The protocol described by this document is sometimes referred to as
90    "SRP-3" for historical purposes.  This particular protocol is
91    described in [SRP] and is believed to have very good logical and
92    cryptographic resistance to both eavesdropping and active attacks.
94    This document does not attempt to describe SRP in the context of any
95    particular Internet protocol; instead it describes an abstract
96    protocol that can be easily fitted to a particular application.  For
97    example, the specific format of messages (including padding) is not
98    specified.  Those issues have been left to the protocol implementor
99    to decide.
101    The one implementation issue worth specifying here is the mapping
102    between strings and integers.  Internet protocols are byte-oriented,
103    while SRP performs algebraic operations on its messages, so it is
104    logical to define at least one method by which integers can be
105    converted into a string of bytes and vice versa.
107    An n-byte string S can be converted to an integer as follows:
109    i = S[n-1] + 256 * S[n-2] + 256^2 * S[n-3] + ... + 256^(n-1) * S[0]
114 Wu                          Standards Track                     [Page 2]
116 RFC 2945        SRP Authentication & Key Exchange System  September 2000
119    where i is the integer and S[x] is the value of the x'th byte of S.
120    In human terms, the string of bytes is the integer expressed in base
121    256, with the most significant digit first.  When converting back to
122    a string, S[0] must be non-zero (padding is considered to be a
123    separate, independent process).  This conversion method is suitable
124    for file storage, in-memory representation, and network transmission
125    of large integer values.  Unless otherwise specified, this mapping
126    will be assumed.
128    If implementations require padding a string that represents an
129    integer value, it is recommended that they use zero bytes and add
130    them to the beginning of the string.  The conversion back to integer
131    automatically discards leading zero bytes, making this padding scheme
132    less prone to error.
134    The SHA hash function, when used in this document, refers to the
135    SHA-1 message digest algorithm described in [SHA1].
137 3. The SRP-SHA1 mechanism
139    This section describes an implementation of the SRP authentication
140    and key-exchange protocol that employs the SHA hash function to
141    generate session keys and authentication proofs.
143    The host stores user passwords as triplets of the form
145         { <username>, <password verifier>, <salt> }
147    Password entries are generated as follows:
149         <salt> = random()
150         x = SHA(<salt> | SHA(<username> | ":" | <raw password>))
151         <password verifier> = v = g^x % N
153    The | symbol indicates string concatenation, the ^ operator is the
154    exponentiation operation, and the % operator is the integer remainder
155    operation.  Most implementations perform the exponentiation and
156    remainder in a single stage to avoid generating unwieldy intermediate
157    results.  Note that the 160-bit output of SHA is implicitly converted
158    to an integer before it is operated upon.
160    Authentication is generally initiated by the client.
162       Client                             Host
163      --------                           ------
164       U = <username>              -->
165                                      <--    s = <salt from passwd file>
170 Wu                          Standards Track                     [Page 3]
172 RFC 2945        SRP Authentication & Key Exchange System  September 2000
175    Upon identifying himself to the host, the client will receive the
176    salt stored on the host under his username.
178       a = random()
179       A = g^a % N                 -->
180                                          v = <stored password verifier>
181                                          b = random()
182                                   <--    B = (v + g^b) % N
184       p = <raw password>
185       x = SHA(s | SHA(U | ":" | p))
187       S = (B - g^x) ^ (a + u * x) % N    S = (A * v^u) ^ b % N
188       K = SHA_Interleave(S)              K = SHA_Interleave(S)
189       (this function is described
190        in the next section)
192    The client generates a random number, raises g to that power modulo
193    the field prime, and sends the result to the host.  The host does the
194    same thing and also adds the public verifier before sending it to the
195    client.  Both sides then construct the shared session key based on
196    the respective formulae.
198    The parameter u is a 32-bit unsigned integer which takes its value
199    from the first 32 bits of the SHA1 hash of B, MSB first.
201    The client MUST abort authentication if B % N is zero.
203    The host MUST abort the authentication attempt if A % N is zero.  The
204    host MUST send B after receiving A from the client, never before.
206    At this point, the client and server should have a common session key
207    that is secure (i.e. not known to an outside party).  To finish
208    authentication, they must prove to each other that their keys are
209    identical.
211         M = H(H(N) XOR H(g) | H(U) | s | A | B | K)
212                                     -->
213                                     <--    H(A | M | K)
215    The server will calculate M using its own K and compare it against
216    the client's response.  If they do not match, the server MUST abort
217    and signal an error before it attempts to answer the client's
218    challenge.  Not doing so could compromise the security of the user's
219    password.
226 Wu                          Standards Track                     [Page 4]
228 RFC 2945        SRP Authentication & Key Exchange System  September 2000
231    If the server receives a correct response, it issues its own proof to
232    the client.  The client will compute the expected response using its
233    own K to verify the authenticity of the server.  If the client
234    responded correctly, the server MUST respond with its hash value.
236    The transactions in this protocol description do not necessarily have
237    a one-to-one correspondence with actual protocol messages.  This
238    description is only intended to illustrate the relationships between
239    the different parameters and how they are computed.  It is possible,
240    for example, for an implementation of the SRP-SHA1 mechanism to
241    consolidate some of the flows as follows:
243         Client                             Host
244        --------                           ------
245         U, A                        -->
246                                     <--    s, B
247         H(H(N) XOR H(g) | H(U) | s | A | B | K)
248                                     -->
249                                     <--    H(A | M | K)
251    The values of N and g used in this protocol must be agreed upon by
252    the two parties in question.  They can be set in advance, or the host
253    can supply them to the client.  In the latter case, the host should
254    send the parameters in the first message along with the salt.  For
255    maximum security, N should be a safe prime (i.e. a number of the form
256    N = 2q + 1, where q is also prime).  Also, g should be a generator
257    modulo N (see [SRP] for details), which means that for any X where 0
258    < X < N, there exists a value x for which g^x % N == X.
260 3.1.  Interleaved SHA
262    The SHA_Interleave function used in SRP-SHA1 is used to generate a
263    session key that is twice as long as the 160-bit output of SHA1.  To
264    compute this function, remove all leading zero bytes from the input.
265    If the length of the resulting string is odd, also remove the first
266    byte.  Call the resulting string T.  Extract the even-numbered bytes
267    into a string E and the odd-numbered bytes into a string F, i.e.
269      E = T[0] | T[2] | T[4] | ...
270      F = T[1] | T[3] | T[5] | ...
272    Both E and F should be exactly half the length of T.  Hash each one
273    with regular SHA1, i.e.
275      G = SHA(E)
276      H = SHA(F)
282 Wu                          Standards Track                     [Page 5]
284 RFC 2945        SRP Authentication & Key Exchange System  September 2000
287    Interleave the two hashes back together to form the output, i.e.
289      result = G[0] | H[0] | G[1] | H[1] | ... | G[19] | H[19]
291    The result will be 40 bytes (320 bits) long.
293 3.2.  Other Hash Algorithms
295    SRP can be used with hash functions other than SHA.  If the hash
296    function produces an output of a different length than SHA (20
297    bytes), it may change the length of some of the messages in the
298    protocol, but the fundamental operation will be unaffected.
300    Earlier versions of the SRP mechanism used the MD5 hash function,
301    described in [RFC 1321].  Keyed hash transforms are also recommended
302    for use with SRP; one possible construction uses HMAC [RFC 2104],
303    using K to key the hash in each direction instead of concatenating it
304    with the other parameters.
306    Any hash function used with SRP should produce an output of at least
307    16 bytes and have the property that small changes in the input cause
308    significant nonlinear changes in the output.  [SRP] covers these
309    issues in more depth.
311 4. Security Considerations
313    This entire memo discusses an authentication and key-exchange system
314    that protects passwords and exchanges keys across an untrusted
315    network.  This system improves security by eliminating the need to
316    send cleartext passwords over the network and by enabling encryption
317    through its secure key-exchange mechanism.
319    The private values for a and b correspond roughly to the private
320    values in a Diffie-Hellman exchange and have similar constraints of
321    length and entropy.  Implementations may choose to increase the
322    length of the parameter u, as long as both client and server agree,
323    but it is not recommended that it be shorter than 32 bits.
325    SRP has been designed not only to counter the threat of casual
326    password-sniffing, but also to prevent a determined attacker equipped
327    with a dictionary of passwords from guessing at passwords using
328    captured network traffic.  The SRP protocol itself also resists
329    active network attacks, and implementations can use the securely
330    exchanged keys to protect the session against hijacking and provide
331    confidentiality.
338 Wu                          Standards Track                     [Page 6]
340 RFC 2945        SRP Authentication & Key Exchange System  September 2000
343    SRP also has the added advantage of permitting the host to store
344    passwords in a form that is not directly useful to an attacker.  Even
345    if the host's password database were publicly revealed, the attacker
346    would still need an expensive dictionary search to obtain any
347    passwords.  The exponential computation required to validate a guess
348    in this case is much more time-consuming than the hash currently used
349    by most UNIX systems.  Hosts are still advised, though, to try their
350    best to keep their password files secure.
352 5. References
354    [RFC 1321]  Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321,
355                April 1992.
357    [RFC 1704]  Haller, N. and R. Atkinson, "On Internet Authentication",
358                RFC 1704, October 1994.
360    [RFC 1760]  Haller, N., "The S/Key One-Time Password System", RFC
361                1760, Feburary 1995.
363    [RFC 2095]  Klensin, J., Catoe, R. and P. Krumviede, "IMAP/POP
364                AUTHorize Extension for Simple Challenge/Response", RFC
365                2095, January 1997.
367    [RFC 2104]  Krawczyk, H., Bellare, M. and  R. Canetti, "HMAC: Keyed-
368                Hashing for Message Authentication", RFC 2104, February
369                1997.
371    [SHA1]      National Institute of Standards and Technology (NIST),
372                "Announcing the Secure Hash Standard", FIPS 180-1, U.S.
373                Department of Commerce, April 1995.
375    [SRP]       T. Wu, "The Secure Remote Password Protocol", In
376                Proceedings of the 1998 Internet Society Symposium on
377                Network and Distributed Systems Security, San Diego, CA,
378                pp. 97-111.
380 6. Author's Address
382    Thomas Wu
383    Stanford University
384    Stanford, CA 94305
386    EMail: tjw@cs.Stanford.EDU
394 Wu                          Standards Track                     [Page 7]
396 RFC 2945        SRP Authentication & Key Exchange System  September 2000
399 7.  Full Copyright Statement
401    Copyright (C) The Internet Society (2000).  All Rights Reserved.
403    This document and translations of it may be copied and furnished to
404    others, and derivative works that comment on or otherwise explain it
405    or assist in its implementation may be prepared, copied, published
406    and distributed, in whole or in part, without restriction of any
407    kind, provided that the above copyright notice and this paragraph are
408    included on all such copies and derivative works.  However, this
409    document itself may not be modified in any way, such as by removing
410    the copyright notice or references to the Internet Society or other
411    Internet organizations, except as needed for the purpose of
412    developing Internet standards in which case the procedures for
413    copyrights defined in the Internet Standards process must be
414    followed, or as required to translate it into languages other than
415    English.
417    The limited permissions granted above are perpetual and will not be
418    revoked by the Internet Society or its successors or assigns.
420    This document and the information contained herein is provided on an
421    "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
422    TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
423    BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
424    HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
425    MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
427 Acknowledgement
429    Funding for the RFC Editor function is currently provided by the
430    Internet Society.
450 Wu                          Standards Track                     [Page 8]