Internet Engineering Task Force Radia Perlman INTERNET DRAFT Sun Microsystems 26 June 2000 Charlie Kaufman Expires in six months Iris Associates Strong Password-Based Authentication Using Pseudorandom Moduli draft-perlman-strong-pass-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 This document specifies a new password-based protocol that can be used as the basis of mutual authentication, or downloading of a private key. The only thing the client needs to know is the user's password. The protocol is constructed such that an eavesdropper cannot do off-line password-guessing attacks. Someone stealing the server's database cannot directly impersonate the user, although they can do an off-line password-guessing attack on the contents. The protocol presented in this paper is similar in functionality, higher in performance at the server, but lower in performance at the client, to the extended EKE and SPEKE, and SRP schemes. Additional properties of this scheme are salt, no password-equivalent stored at the server, and prevention of servers on which the user has the same password from impersonating each other to the user. This document gives an overview of the approach, but not wire-formats, which are R. Perlman, C. Kaufman Expires: 6 December 2000 [Page 1] Internet Draft Strong Password-Based Authentication June 2000 premature at this stage. The purpose of this document is to advertise this new scheme to various groups that might be interested (CAT, for a GSS-API mechanism, LDAP, for download of a private key). Table of Contents Status of This Memo . . . . . . . . . . . . . . . . . . . . . 1 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Table of Contents . . . . . . . . . . . . . . . . . . . . . . 2 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 2 The Protocol . . . . . . . . . . . . . . . . . . . . . . . . 4 3 Generating p . . . . . . . . . . . . . . . . . . . . . . . . 5 4 Getting down to the bits . . . . . . . . . . . . . . . . . . 7 4.1 Computing p from username and password . . . . . . . . . . 7 4.2 Format of first message on the wire . . . . . . . . . . . 8 4.3 Format of second message on the wire . . . . . . . . . . . 8 4.4 Format of third message on the wire . . . . . . . . . . . 9 5. Security Considerations . . . . . . . . . . . . . . . . . . 9 References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Author's Addresses . . . . . . . . . . . . . . . . . . . . . . 12 Full Copyright Statement . . . . . . . . . . . . . . . . . . . 12 1. Introduction Protocols such as EKE [BM92], and SPEKE [Jab96] pioneered the notion of using a weak secret such as a password to disguise 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. Our protocol gives the same functionality as EKE, SPEKE, or SRP, with a few additional features that could easily be incorporated into any of the other protocols. Our protocol has the disadvantage of lower, but tolerable performance at the client, and higher performance for the server. EKE, SPEKE, and SRP [WU99] involve a Diffie-Hellman exchange, but R. Perlman, C. Kaufman Expires: 6 December 2000 [Page 2] Internet Draft Strong Password-Based Authentication June 2000 modified somehow with the user's password. In EKE and SRP, g and p in the Diffie-Hellman exchange are fixed, and the public number g**X mod p is modified with a function of the user's password (encryption in the case of EKE, subtraction in the case of SRP). In SPEKE, the base g is a function of the user's password. In this paper we propose making the modulus p a function of the user's password. Using such an exchange a user Alice can use any workstation which has the appropriate software but no security information configured for that user, type her password, and the workstation can do mutual authentication with the server Bob. One purpose of this protocol is for downloading a user's private key 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. Such protocols are studied in [PK99]. The other purpose for this protocol is to do mutual authentication between the user and the server. The properties of this protocol are: . a user need only know her name and password . the protocol provides mutual authentication between the user and a server . 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 a single password guess per interaction with the other side. . Someone stealing Bob's database will not be able to directly impersonate Alice, though they can do an off-line dictionary attack, and obtain all of Alice's security information if Alice's password is guessable. Two servers on which the user has the same password will not be able to impersonate each other to the user. R. Perlman, C. Kaufman Expires: 6 December 2000 [Page 3] Internet Draft Strong Password-Based Authentication June 2000 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. In order to prevent different servers on which Alice uses the same password from having the same security information, and therefore being able to impersonate each other to Alice, each server Bob will be configured with a secret which is a function of Alice's name, password, and Bob's name. We'll call that secret X. X can be hierarchically administered by giving the configurator node Z=h("Alice", pwd) and having that node calculate, for Bob, X=h(Z,"Bob"). It is easy for Alice to compute the X for Bob using her name, password, and Bob's name. In order to have the information at server Bob not be a password- equivalent, and to also download an RSA private key as a side effect, the server additionally stores the user's public key, and her private key encrypted with her password. We'll call that quantity Y. So Bob stores, for Alice,: . name "Alice" . p (safe prime pseudorandomly generated from seed h("Alice", password) . Alice's public RSA key . Y=Alice's private RSA key encrypted with her password . X=h("Alice", "Bob", Alice's password) In order to prevent someone who is impersonating the server from sending 2**B with sufficiently small B that the result is less than p (i.e., they would not need to know the value of p) from doing a dictionary attack based on the result, Alice must reject a 2**B if it is of the form 1000...000 (a power of 2, not reduced by p). R. Perlman, C. Kaufman Expires: 6 December 2000 [Page 4] Internet Draft Strong Password-Based Authentication June 2000 The protocol is as follows: 1) Server Bob stores for Alice: "Alice", p, Alice's public RSA key, Y, X 2) User types name ("Alice") and password to the workstation. 3) Workstation computes h("Alice",password), and uses that to seed a pseudorandom number generator to choose a safe prime p that has 2 as a generator. 4) User types the name of the server to which she wishes to attach ("Bob") 5) Workstation chooses a random A to serve in the Diffie-Hellman exchange. 6) Workstation sends "Alice", 2**A mod p to Bob. Workstation calculates X. 7) Bob chooses random B, calculates 2**B mod p, calculates 2**AB mod p, calculates K=h(X, 2**AB mod p). Transmits "Bob", 2**B mod p, and Y encrypted with K to Alice. 8) Workstation calculates 2**AB and verifies Bob's response. Workstation sends h(K) signed with Alice's private key, to Bob. 9) Bob verifies Alice's response. 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 safe prime. (A "safe 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. R. Perlman, C. Kaufman Expires: 6 December 2000 [Page 5] Internet Draft Strong Password-Based Authentication June 2000 If this were really considered a problem, then this entire exchange could take place inside an anonymous Diffie-Hellman exchange with fixed, large p. Another way to make performance better for the client is not to use a safe 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 safe primes can be tolerable, and the size of the safe 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 safe 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=-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 safe 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. The user-supplied hint trick (suggested by Jeff Schiller) 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 which of the first 64 test numbers to start with. 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 R. Perlman, C. Kaufman Expires: 6 December 2000 [Page 6] Internet Draft Strong Password-Based Authentication June 2000 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. Assuming the user interface consists of first supplying the user's name and password, the workstation can be computing p while the user is typing the server name. If the exchange does not start until the workstation has finished computing p, then there will be no timing information available to the eavesdropper. To support smooth migration to variations on this protocol in the future, to allow some negotiation of parameter sizes, and to 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". 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 61 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.0 dated 26JUN2000") 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"), ... If there is no HINT, 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. A useful HINT is then computed as (p-3)/8 mod 62, and R. Perlman, C. Kaufman Expires: 6 December 2000 [Page 7] Internet Draft Strong Password-Based Authentication June 2000 the user is told that future logins will run faster if ".x" is appended to his password in the future (where x is replaced with the character corresponding to the discovered HINT). If there is a HINT, only candidates of the form p = 3 + HINT*8 mod 8*62 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 byte of password will get in a lot faster. 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 || ` ' || 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 h(X, 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. From that database, he then reads p, Y, X, and AP, where: p = the 512 bit safe prime derived from Alice's name and password S = SHA1(Servername) X = SHA1(Pseed || S) K1 = SHA1(Pseed || "0") - First 128 bits only used as a two key triple-DES key Y* = 2048 bit quantity: 1024 bit RSA modulus; 1024 bit RSA private R. Perlman, C. Kaufman Expires: 6 December 2000 [Page 8] Internet Draft Strong Password-Based Authentication June 2000 exponent (big endian) Y = ({Y*} 3DES encrypted with K1) || SHA1(Y* || K1) AP = 1024 bit RSA modulus (same as in Y*) - public exponent is fixed at 3 Bob checks to make sure that 2**A mod p contains more than a single 1-bit (i.e. that it is not a small power of 2). Bob then computes: B = 160 bit random integer Kseed = SHA1(X || 2**AB mod p) - Numeric result fixed at 512 bits in big endian order K2 = SHA1(Kseed || "1") - First 128 bits only used as two key triple-DES key ENCY = {Y} 3DES encrypted with K2 (IV=0; CBC mode) 2**B mod p has fixed length 512 bits, send in "big endian" order. Msg2 = V || 2**B mod p || ENCY || Servername 4.4 Format of third message on the wire: [h(K)] signed with RSA private key) Alice parses the second message and verifies that the final 160 bits of Y are consistent with the rest of Y when decrypted. She also checks that 2**B mod p contains more than 1 1-bit (i.e. that it is not a small power of 2). This assures that she is actually talking to Bob. She then computes: K3 = SHA1(Kseed || "2") Message is 512 bit RSA signature of K3 padded using PKCS #1 formatting. 5. Security Considerations This protocol is intended to replace a number of other authentication protocols with the intention of improving their security. The ideal authentication protocol would be built atop a public key infrastructure and implemented using smart cards. But deploying such a system requires agreement on issues like a universal naming scheme and a sufficiently flexible trust policy to cover a wide range of environments; and deploying of the trusted third parties necessary to R. Perlman, C. Kaufman Expires: 6 December 2000 [Page 9] Internet Draft Strong Password-Based Authentication June 2000 support actual use of the protocols. This proposal offers a low infrastructure alternative. It does not constrain the form of names for users or servers, it does not require any trusted third party intermediaries, and it matches the commonly deployed "form factor" of a user who knows a name and a password, and a server that has a table of user names and for each user a quantity that can be used to verify a password. Within those constraints, this scheme offers a number of advantages not present in the currently deployed schemes: neither an eavesdropper, nor a user impersonator, nor a server impersonator, nor a reader of the server's database gains the information needed to impersonate the user to the server. Authentication is mutual (the user knows she is talking to the genuine server). And if the user chooses to use the same password with multiple systems, those systems can still be individually authenticated. R. Perlman, C. Kaufman Expires: 6 December 2000 [Page 10] Internet Draft Strong Password-Based Authentication June 2000 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", ACM Computer Communications Review, October 1996. [JAB97] D. Jablon, "Extended Password Protocols Immune to Dictionary Attack", Proceedings of the WETICE `97 Enterprise Security Workshop, June 1997. [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, C. Kaufman Expires: 6 December 2000 [Page 11] Internet Draft Strong Password-Based Authentication June 2000 Author's Address Radia Perlman Sun Microsystems Phone: Email: radia.perlman@sun.com Charlie Kaufman Iris Associates Phone: Email: ckaufman@iris.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 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE." R. Perlman, C. Kaufman Expires: 6 December 2000 [Page 12]