[Search] [txt|pdfized|bibtex] [Tracker] [Email] [Nits]
Versions: 00                                                            
Internet Engineering Task Force                            Radia Perlman
INTERNET DRAFT                                          Sun Microsystems
26 June 2000                                             Charlie Kaufman
Expires in six months                                    Iris Associates
                                                           Eric Rescorla
                                                              RTFM, Inc.

  Strong Password-Based Credentials Download Using Pseudorandom Moduli
                    draft-perlman-strong-cred-00.txt

Status of This Memo

   This document is an individual contribution to the Internet
   Engineering Task Force (IETF).  Comments should be sent to the
   authors Radia.Perlman@Sun.COM and CKaufman@Iris.COM.

   Distribution of this memo is unlimited.

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.  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.


Abstract

   In a strong password-based protocol, the only thing the client needs
   to know is the user's password, and an eavesdropper, or someone
   impersonating either end, cannot do off-line password-guessing
   attacks.  This sort of protocol can be used for credentials download,
   or for mutual authentication. Although password-based mutual
   authentication protocols can be used for credentials download, they
   are designed with some properties (such as not storing a password-
   equivalent at the server) that are not important in a credentials-
   download protocol. Therefore, a protocol designed specifically for
   credentials download can be fewer messages, higher performance at the
   server, and allow the server to operate in a stateless manner.
   Therefore it is possible, even likely, that different protocols might
   be preferable in one case (credentials download) than another.  This



R. Perlman, et. al.       Expires: 17 May 2001                   [Page 1]Internet Draft    Strong Password-Based Authentication


   document specifies a password-based protocol optimized for
   downloading of a user's credentials, such as a private key. We claim
   the desirable properties of such a protocol are that it be
   unencumbered, high performance at the server, stateless at the
   server, minimal number of messages, and acceptable performance at the
   client.



Table of Contents

     Status of This Memo  . . . . . . . . . . . . . . . . . . . . .  1

     Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . .  1

     Table of Contents  . . . . . . . . . . . . . . . . . . . . . .  1

     1 Introduction . . . . . . . . . . . . . . . . . . . . . . . .  1

     2 The Protocol . . . . . . . . . . . . . . . . . . . . . . . .  3

     3 Generating p . . . . . . . . . . . . . . . . . . . . . . . .  4

     4 Getting down to the bits . . . . . . . . . . . . . . . . . .  6

     4.1 Computing p from username and password . . . . . . . . . .  6

     4.2 Format of first message on the wire  . . . . . . . . . . .  8

     4.3 Format of second message on the wire . . . . . . . . . . .  8

     5. Performance Note  . . . . . . . . . . . . . . . . . . . . .  8

     6. Security Considerations . . . . . . . . . . . . . . . . . .  8

     References . . . . . . . . . . . . . . . . . . . . . . . . . .  9

     Author's Addresses . . . . . . . . . . . . . . . . . . . . . . 10

     Full Copyright Statement . . . . . . . . . . . . . . . . . . . 10


1. Introduction

   Protocols such as EKE [BM92], and SPEKE [Jab96] pioneered the notion
   of using a weak secret such as a password to obfuscate a Diffie-
   Hellman exchange, so that the exchange itself gives no information to
   eavesdroppers, and at most a single on-line password guess to someone
   impersonating either the client or the server. Later the protocols
   were adapted [BM94], [Jab97] to incorporate the feature of not
   storing a password-equivalent at the server, so that someone that



R. Perlman, et. al.       Expires: 17 May 2001                   [Page 2]Internet Draft    Strong Password-Based Authentication


   stole the server's database could not use the contents to directly
   impersonate the user (though they could do a dictionary attack on the
   contents to discover the user's password). SRP [Wu98] improved on
   those protocols in performance.

   However, for credentials download, there is no advantage of avoiding
   a password-equivalent at the server because the purpose of the
   protocol is to obtain the user's credentials, which are stored at the
   server. So someone that steals the server's database already has the
   credentials. Also in [PK99] tricks were provided for making
   (nonextended) protocols such as EKE and SPEKE (but not the extended
   versions) stateless at the server.  A lot of the work of the mutual
   authentication protocols such as extended EKE, extended SPEKE, and
   SRP, are not relevant for credentials download, and they require
   computation and state at the server that are not necessary for a
   protocol used solely for credentials download. Therefore, the
   preferred protocol for mutual authentication might be different from
   the preferred protocol for credentials download.

   Note that the credentials must be encrypted with a different hash of
   the password than might be stored for use in EKE or SPEKE; otherwise
   the user's credentials can be directly derived from the information
   in the database.

   Although a protocol based on (nonextended) EKE or SPEKE for
   credentials download is technically acceptable, patent issues might
   argue for a new approach, which we provide in this paper.

   We claim the desirable properties of a credentials download protocol
   are that it be unencumbered, secure against dictionary attacks by an
   eavesdropper or someone impersonating either end, high performance at
   the server, stateless at the server, minimal number of messages, and
   acceptable performance at the client.

   We claim the performance at the server is much more important than
   performance at the client, because the server must simultaneously
   serve many clients, perhaps many of whom are unauthorized and
   contacting the server solely to require it to consume resources. We
   claim the performance at the client is not as important because it is
   serving only one user at a time, and the protocol is only executed
   once (per user, per session).  So the only thing that matters at the
   client is whether performance is "good enough", whereas at the
   server, any performance gain is important.

   Our protocol has at least as good performance at the server as any of
   the other schemes (and quite likely better, because the argument can
   be made that our scheme allows for use of smaller p's).

   In EKE g and p in the Diffie-Hellman exchange are fixed, and the
   public number g**X mod p is encrypted with a function of the user's
   password. In SPEKE, the base g is a function of the user's password.



R. Perlman, et. al.       Expires: 17 May 2001                   [Page 3]Internet Draft    Strong Password-Based Authentication


   In this paper we propose making the modulus p a function of the
   user's password.

   This protocol can be used to download a user's private key to a
   workstation with appropriate software but no security information
   configured for that user, from a public place such as a directory.
   This can be thought of as bootstrapping the PKI. It is not possible
   to protect the user's private key with conventional access control
   since the user cannot authenticate until the user obtains the private
   key. And the private key cannot be world-readable, even if encrypted
   with the user's password, because the encrypted private key is
   subject to off-line password-guessing. Once the user's private key is
   recovered, any other information necessary to reconstruct the user's
   environment on that workstation, such as the CAs that user trusts as
   trust anchors for certificate chains, can also be retrieved from the
   directory. Information that needs to be integrity protected is signed
   with the user's private key. Information that needs to be secret
   (other than the user's private key, which must be protected in a
   different way) is encrypted with the user's public key.

   The properties of this protocol are:

     . a user need only know her name and password


     . the protocol allows the server to operate in a stateless manner

     . an eavesdropper on the authentication exchange between Alice and
       Bob will gain no information from the exchange, no matter how
       guessable Alice's password.

     . Someone impersonating Bob or Alice will be able to verify only a
       single password guess per interaction with the other side.


   This protocol is not intended for devices such as PDAs which are
   owned by a specific user and carried by that user. For those devices,
   a high quality secret (such as the user's private key) would be
   configured. This protocol is intended for workstations with
   reasonable computational resources (say 400 MHz processors) that have
   reasonable software, but no user-specific information configured.


2. The Protocol

   The basic idea is to use the user's password as a seed for generating
   a prime modulus, and always use 2 as the base. In order to provide
   for salt, the seed for the pseudorandom number generator which will
   select the prime modulus should be h("Alice", Alice's password).  The
   server Bob will store p for user Alice. Alice's workstation must
   generate p based on Alice's name and her password when she logs in.



R. Perlman, et. al.       Expires: 17 May 2001                   [Page 4]Internet Draft    Strong Password-Based Authentication


   The protocol requires only 2 messages (request/response), so is
   obviously stateless for the server. The client calculates p from the
   user's password, chooses a random A, and sends 2**A mod p to the
   server. The server chooses B, sends 2**B mod p to the client, and
   sends back the credentials encrypted with 2**AB.

   To save the server work, it loses no security to always use the same
   B for the same user (but not for different users). If the server
   stores, for Alice, B and 2**B mod p, then in this protocol there is
   only a single exponentiation required at the server (to raise 2**A to
   the power B).

   So Bob stores, for Alice:

     . name "Alice"

     . p (Sophie Germain prime pseudorandomly generated from seed
       h("Alice", password)

     . Y=Alice's credentials encrypted with her password

     . B

     . 2**B mod p


   The protocol is as follows:


     1) User types name ("Alice") and password to the workstation.

     2) Workstation computes h("Alice",password), and uses that to seed
        a pseudorandom number generator to choose a Sophie Germain prime
        p that has 2 as a generator.

     3) Workstation chooses a random A to serve in the Diffie-Hellman
        exchange.

     4) Workstation sends "Alice", 2**A mod p to Bob.

     5) Bob checks that Alice's name is exactly as stored in the
        database, and if not, sends that version of Alice's name back.
        If it is the same, Bob takes the B stored in the database,
        calculates K=2**AB mod p by raising what he received from Alice
        to the power B, and transmits 2**B mod p, and Y encrypted with K
        to Alice.

     6) Workstation calculates 2**AB mod p and uses it to decrypt Y.






R. Perlman, et. al.       Expires: 17 May 2001                   [Page 5]Internet Draft    Strong Password-Based Authentication


3. Generating p

   We want 2 to be a generator (with high probability). By the law of
   quadratic reciprocity, this calls for p being 3 mod 8. So our
   algorithm for generating p's will only test numbers that are 3 mod 8.

   We estimate 10 seconds as a reasonable maximum amount of time for the
   workstation to compute p. Diffie-Hellman moduli of 1000 bits are
   considered safe. But on today's desktops, it would take too much time
   (we estimate minutes) to generate a 1000-bit Sophie Germain prime. (A
   "Sophie Germain prime" p is one in which (p-1)/2 is also prime.)

   What corners can be cut to make performance tolerable at the client
   machine? Suppose we used a smaller p, say 512 bits. It is estimated
   that it would take 8000 MIP-years to break 512-bit Diffie-Hellman. An
   eavesdropper on this exchange would have information sufficient to
   test passwords, but it would require breaking 512-bit Diffie Hellman
   for every guessed password. Another threat from using breakable
   Diffie-Hellman is that if Bob's database were stolen, or someone
   learned the user's password, then we would lose perfect forward
   secrecy for the attacker's price of breaking 512-bit Diffie-Hellman.
   If this were really considered a problem, then this entire exchange
   could take place inside an anonymous Diffie-Hellman exchange with
   fixed, large p. But for credentials download, (unlike mutual
   authentication) perfect forward secrecy is not a concern.

   Another way to make performance better for the client is not to use a
   Sophie Germain prime, but instead use one where p-1 has at least one
   large (160 bit) prime factor. Selection becomes more complicated
   because determining whether 2 is a generator is probabilistic if the
   factorization of p-1 is not known. This is probably a reasonable
   approach; however, using a trick suggested by Jeff Schiller of having
   the user optionally supply a hint, we think performance with Sophie
   Germain primes can be tolerable, and the size of the Sophie Germain
   prime generated can be increased as desktops get faster, and it is a
   simpler solution. It is always best to start with a simple solution.

   The way to look for a Sophie Germain prime is to start with a number
   n, and then look for the smallest number p of the form 3 mod 8 larger
   than n where both p and (p-1)/2 are (probably) prime. The most
   efficient method is to first sieve to avoid numbers where either p or
   (p-1)/2 have a small (say less than 10000) prime factor, and then
   discard numbers unless both 2**(p-1)/2 mod p=p-1, and 2**(p-3)/2 mod
   (p-1)/2=1. If p passes this test, there is an overwhelming
   probability that p is a Sophie Germain prime and that 2 is a
   generator. As a performance enhancement, we propose that for purposes
   of interoperability that exactly those tests take place as opposed to
   some less efficient test that determines primality with higher
   certainty but which could introduce interoperability problems if not
   all implementations used the same tests.




R. Perlman, et. al.       Expires: 17 May 2001                   [Page 6]Internet Draft    Strong Password-Based Authentication


   The user-supplied hint trick involves having the workstation give the
   user a small value (say a single character, giving 6 bits of
   information) that will speed up the search. For instance, it can
   specify 6 of the bits of the p that will be chosen from the password.
   If the user remembers the hint, then it saves computation time. If
   the user does not furnish the hint, then authentication takes longer.
   If the user furnishes the wrong hint, it is possible for
   authentication to fail.

   It is also important, in protocols of this sort, to avoid leaking
   information that would enable an eavesdropper to eliminate passwords.
   For instance, in the most straightforward implementation of EKE, one
   might encrypt g**A mod p with a hash of the password. An eavesdropper
   that observed an encrypted g**A mod p could do trial decryptions with
   various passwords, and eliminate any passwords in which the result
   was larger than p.

   To avoid leaking information, we specify that candidate p's be chosen
   from a very narrow range. So we fix the top 64 bits to be a constant.
   For maximum performance given the size of the numbers, p should be
   close to a power of 2. Therefore we recommend fixing the top 64 bits
   to be 111...1. That means that the smallest possible p chosen would
   be 64 bits of 1 followed by 0's, and the larger would be all 1's. We
   recommend discarding A's and B's for which 2**A mod p or 2**B mod p
   wind up larger than the maximum possible p that could be generated.
   The probability of needing to discard an A is 1/2**64.

   Another way in which information might be leaked is observing the
   amount of time required to generate p. But an eavesdropper will have
   no way of knowing how long it took to compute p, since the only thing
   the eavesdropper sees is the client's request (which occurs after
   computation of p).

   Another way information could be leaked is if Alice chooses an A so
   small that 2**A does not need to be reduced by p. In that case, she
   has not committed to a password, and can do a dictionary attack based
   on {Y}2**AB mod p (since she knows A), for any p.  Using 2 as the
   base has the nice property that Bob can recognize this form of
   cheating, since 2**A mod p will have only a single "1" in the binary
   representation. Bob must reject such values from Alice.

   To support smooth migration to variations on this protocol in the
   future, to allow some negotiation of parameter sizes, we specify a
   minor version number and an alternate form of the second message in
   which the server can specify alternate parameter sizes and/or a
   "cookie".








R. Perlman, et. al.       Expires: 17 May 2001                   [Page 7]Internet Draft    Strong Password-Based Authentication


4. Getting down to the bits


4.1 Computing p from username and password

   If the password is at least three characters long, the next to last
   character is ".", and the final character is from the set (0-9, a-z,
   A-Z, +, =), then the final two characters of the password are left
   out of the calculation of P below and the final character is
   translated into an integer HINT between 0 and 63 depending on its
   position in that set of legal characters. This will be used as a
   performance enhancement (see below).

     U     = SHA1(Username)

     P     = SHA1(Password)

     V     = SHA1 ("Strong Password Authentication - Version 1.1 dated
             16NOV2000")

     Pseed = SHA1(U || P || V)

     A     = Randomly chosen 160 bit integer

   Starting point for search for prime p is a 512 bit number with high
   order bits 0-63 all 1's, and the remaining bits from SHA1(Pseed ||
   "1"), SHA1(Pseed || "2"), ... The chosen p will be the smallest
   number greater than or equal to the starting point for which p = 3
   mod 8, neither p nor (p-1)/2 has prime factors less than 10,000, and
   for which 2**((p-1)/2 mod p = -1 and 2**((p-3)/2 mod ((p-1)/2) = 1.
   The HINT is 6 bits of the chosen p. Since the bottom 3 bits must be
   011 (to be 3 mod 8), the hint can be the representation of bits
   503-508. (i.e., the low order bit of the penultimate byte and the
   high order 5 bits of the last byte).

   If the user does not supply a hint, the user is told that future
   logins will run faster if the hint "x" is supplied in the future
   (where x is replaced with the character corresponding to the
   discovered HINT). The hint could be supplied with a separate user
   prompt, or by appending to the password a character (such as space)
   that would be otherwise be disallowed in the password, followed by x.

   If there is a HINT, only candidate p's with bits 4-10 equal to the
   hint are considered. The effect of this is that if the user provides
   the HINT when entering the password, the computation of p will be
   much faster but ultimately will produce the same result as the
   calculation without the HINT. If the user specifies an incorrect
   HINT, a different p will be calculated and it will probably take a
   long time. The end result is that no passwords are disallowed (any
   value entered will result in a 512 bit p), but users willing to
   remember one more character of password will get in a lot faster.



R. Perlman, et. al.       Expires: 17 May 2001                   [Page 8]Internet Draft    Strong Password-Based Authentication


   Note that this is not equivalent to simply having a longer password,
   since the hint is not user-supplied, and has no logical (from a human
   point of view) connection with the rest of the password.

   It would also be reasonable to allow multiple characters for the
   hint, further speeding up processing at the client. In this case the
   first character supplied by the user would equal bits 4-9, the next
   10-15, etc.

   Above, we specified that the user interface for entering the hint
   would be that ".x" would be appended to the password. If "." is a
   legal character in a password, and the user happened to specify a
   password with "." as the penultimate character, then the final
   character would be interpreted as a hint, and a prime would be found,
   but it would be slow.


4.2 Format of first message on the wire: "Alice", 2**A mod p

   The encapsulating protocol is assumed to provide the total length of
   the message. Message is V || `\0' || 2**A mod p || Username, where V
   has fixed length 160 bits, a single zero byte follows, 2**A mod p has
   fixed length 512 bits, and username is variable length. 2**A mod p is
   sent in "big endian" order. The recipient of this message MUST verify
   that V is the expected value or terminate the protocol. The zero byte
   is a "minor version" number. It MUST be zero for clients implementing
   this version of the protocol. It MAY be non-zero for future clients,
   indicating that those clients are willing to negotiate some variation
   on this protocol. The recipient of this message implementing this
   version of the protocol MUST ignore the value of that byte. Future
   versions of the protocol may specify optional alternate responses if
   the value is non-zero.


4.3 Format of second message on the wire: "Bob", 2**B mod p, and (Y)
   encrypted with 2**AB

   Bob parses the first message. He uses the user name to look up
   account information for Alice, and checks to make sure the case,
   accents, and punctuation of Alice's name as provided matches the
   version in his account database. If not, or if the version is not
   acceptable, or if 2**A mod p has only a single "1" bit in its binary
   representation, or if Bob wants a stateless cookie before he does any
   exponentiation, then Bob replies, with the cookie, corrected form of
   Alice's name, required size of p (if the client sent the wrong size),
   complaint about the format of 2**A mod p, etc.  If the version,
   Alice's name, and the prime size is acceptable, Bob then reads p, B,
   2**B mod p, and Y from the database, raises the received 2**A mod p
   to the power B, encrypts Y with 2**AB mod p to get ENCY, and sends V
   || 2**B mod p || ENCY.




R. Perlman, et. al.       Expires: 17 May 2001                   [Page 9]Internet Draft    Strong Password-Based Authentication


5. Performance Note

   By far the most time consuming part of this protocol is the client's
   generation of p from the username and password.  The performance of
   this operation is especially important because it must be performed
   every time the client wishes to download his credentials.

   Table 1 contains performance numbers for this operation. These
   numbers are the mean of 20 trials with different passwords. The
   passwords were chosen using words 20001-20020 in FreeBSD 3.4's
   /usr/share/dict/words. The username was "Alice". All numbers are in
   seconds. For reference, we have included numbers at a variety of key
   sizes.


        Key Size       Normal   w/ Hint
        384               6.6       .13    (not recommended)
        512               8.7       .15
        768              34         .57
        1024 *          120        2.0
                 Figure 1: Performance of prime generation

   * Only 5 trials were run for 1024 bits due to needing to submit this
   I-D.

   These numbers were collected on a fairly unoptimized implementation
   of the algorithm of Section 4.1 on a Pentium II/400 running FreeBSD
   3.4. The bignum implementation was OpenSSL 0.9.6.

   Note that although performance with a 1024 bit prime is quite bad,
   with a hint it's quite acceptable.

6. Security Considerations

   This protocol is intended to be a method of downloading credentials
   which is somewhat less secure than having smart cards for each user.
   It can bootstrap deployment of a PKI, allowing deployment before
   users have smart cards. It is perfectly feasible for some users to
   obtain credentials through this protocol and others to have smart
   cards, and a user that subsequently obtains a smart card can simply
   have their credentials information removed from the directory.  This
   protocol assumes trusted software at the client machine.












R. Perlman, et. al.       Expires: 17 May 2001                  [Page 10]Internet Draft    Strong Password-Based Authentication


References

   [BM92]  S. Bellovin and M. Merritt, "Encrypted Key Exchange:
           Password-based protocols secure against dictionary attacks",
           Proceedings of the IEEE Symposium on Research in Security and
           Privacy, May 1992.

   [BM94]  S. Bellovin and M. Merritt, "Augmented Encrypted Key
           Exchange: a Password-Based Protocol Secure Against Dictionary
           Attacks and Password File Compromise, ATT Labs Technical
           Report, 1994.

   [DH76]  W. Diffie and M. Hellman, "New Directions in Cryptography",
           IEEE Transactions on Information Theory, November 1976.

   [Jab96] D. Jablon, "Strong Password-Only Authenticated Key Exchange",
           Computer Communication Review, ACM SIGCOMM, vol. 26, no. 5,
           pp. 5-26, October 1996.

   [JAB97] D. Jablon, ""Extended Password Key Exchange Protocols Immune
           to Dictionary Attacks", Proceedings of the Sixth Workshops on
           Enabling Technologies: Infrastructure for Collaborative
           Enterprises (WET-ICE '97), IEEE Computer Society, June 18-20,
           1997, Cambridge, MA, pp. 248-255.

   [KPS95] C. Kaufman, R. Perlman, and M. Speciner, "Network Security:
           Private Communication in a Public World", Prentice Hall,
           1995.

   [Pat97] S. Patel, "Number Theoretic Attacks On Secure Password
           Schemes", Proceedings of the IEEE Symposium on Security and
           Privacy, May 1997.

   [PK99]  R. Perlman and C. Kaufman, "Secure Password-Based Protoocol
           for Downloading a Private Key", ISOC NDSS Symposium, 1999.

   [WU98]  T. WU, "The Secure Remote Password Protocol", ISOC NDSS
           Symposium, 1998.
















R. Perlman, et. al.       Expires: 17 May 2001                  [Page 11]Internet Draft    Strong Password-Based Authentication


Author's Address


                Radia Perlman
                Sun Microsystems

      Phone:
      Email:    radia.perlman@sun.com

                Charlie Kaufman
                Iris Associates

      Phone:
      Email:    ckaufman@iris.com

                Eric Rescorla
                RTFM, Inc.

      Phone:
      Email:    ekr@rtfm.com



Full Copyright Statement

   Copyright (C) The Internet Society (1999).  All Rights Reserved.

   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain it
   or assist in its implementation may be prepared, copied, published
   and distributed, in whole or in part, without restriction of any
   kind, provided that the above copyright notice and this paragraph
   are included on all such copies and derivative works.  However,
   this document itself may not be modified in any way, such as by
   removing the copyright notice or references to the Internet Society
   or other Internet organizations, except as needed for the purpose
   of developing Internet standards in which case the procedures
   for copyrights defined in the Internet Standards process must be
   followed, or as required to translate it into languages other than
   English.

   The limited permissions granted above are perpetual and will not be
   revoked by the Internet Society or its successors or assigns.

   This document and the information contained herein is provided on an
   "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
   TASK FORCE DISCLAIMS 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 WARRAN<TIES OF
   MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE."