Network Working Group D. Jablon Internet Draft Phoenix Technologies draft-jablon-speke-00.txt February 13, 2002 Expires August 13, 2002 The SPEKE Password-Based Key Agreement Methods Status of this Memo This document is an Internet-Draft and is subject to all provisions of Section 10 of RFC2026. 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 describes SPEKE, B-SPEKE, and SRP-4, three methods for password-based key agreement and authentication. In the same class of techniques as SRP-3 [RFC 2945], these methods provide a zero- knowledge proof of a password and authenticate session keys over an unprotected channel, with minimal dependency on infrastructure and proper user behavior. These methods are compatible with IEEE 1363 and ANSI X9 standards, and are closely aligned with RFC 2945 from an application perspective. They are also based on different fundamental techniques than earlier patented alternatives, providing an expanded set of choices for convenient and secure personal authentication over the Internet. Jablon Expires August 13, 2002 [Page 1]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 Table of Contents Status of this Memo .............................................. 1 Abstract ......................................................... 1 1. Introduction .................................................. 3 2. Background .................................................... 4 2.1 Features and Benefits .................................... 5 2.3 Origin ................................................... 6 3. Description ................................................... 6 3.1. Notation, Conventions, and Terminology ................... 7 3.1.1 Parameters .......................................... 7 3.1.2 Notation ............................................ 7 3.1.3 Data Format Conversion .............................. 8 3.1.4 Bits and Bytes ...................................... 9 3.2 General Construction ..................................... 9 3.2.1 Enrollment .......................................... 9 3.2.2 Identification ...................................... 10 3.2.3 Key Exchange ........................................ 10 3.2.4 Secret Value Derivation ............................. 11 3.2.5 Key Derivation ...................................... 11 3.2.6 Key Confirmation .................................... 11 3.3 Message Ordering ......................................... 12 3.4 Compatibility with RFC 2945 .............................. 12 4. Application Notes ............................................ 13 4.1 Summary of Benefits ...................................... 13 4.2 Comparison with SRP-3 and RFC 2945 ....................... 13 4.3 Which Method Should I Use? ............................... 14 4.3.1 SPEKE vs. Augmented Methods ......................... 14 4.3.2 B-SPEKE vs. SRP-4 ................................... 14 4.4 Parameter Selection ...................................... 15 4.5 Compatibility with Other Standards ....................... 15 4.6 Other Key Derivation and Hash Functions .................. 16 4.6.1 Security Note ....................................... 16 4.7 Key Confirmation Functions ............................... 16 4.8 Salt ..................................................... 17 4.9 Iterated Hashing ......................................... 17 4.10 Foundation of these methods ............................. 17 5. Security Considerations ....................................... 19 6. Intellectual Property Notice .................................. 19 References ....................................................... 19 Author's Address ................................................. 22 Full Copyright Statement ......................................... 22 Acknowledgements ................................................. 22 Appendix A: An SRP4-SHA1 mechanism ............................... 23 A.1. Interleaved SHA ......................................... 25 A.2. Other Hash Algorithms ................................... 25 Jablon Expires August 13, 2002 [Page 2]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 1. Introduction Convenient and secure personal authentication is important for many Internet applications. If people must use passwords, they demand, at a minimum, that they be easy to remember and type. Yet, there has been a proliferation of password systems that offer little or no protection against passive and active network attack, combined with increasingly complex key-based infrastructures that still ultimately depend on a password as the human-link. This document describes SPEKE, B-SPEKE, and SRP-4, three methods that provide cryptographically strong password-based key agreement and network authentication. In the same general class as SRP-3, these methods can provide a secure binding between people and keys, using a small or not-so-random password to negotiate and mutually authenticate a session key between two parties. These zero-knowledge techniques operate over an unprotected network, without revealing the password or keys to attackers, and require no certificates, no long- term sensitive data at the client, and minimal demands on the user. Both SPEKE and SRP-3 have attracted broad attention from Internet application developers for providing secure and convenient personal authentication, with minimal demands on the user, and minimal dependency on security infrastructure. These methods have been deployed in both academic and commercial settings, and at last count, six Internet Drafts referred to RFC 2945 [Bla02, BN02, CAH01, Far02, Mol01, Tay01]. In general, these methods are seen as important enablers of mobility in infrastructure-based systems [SACRED]. Anticipated commercial deployment has naturally raised questions concerning the status of these methods with regard to patents. This document also explores the technical foundation motivating such potential license requirements. In this regard, the SPEKE, B-SPEKE, and SRP-4 methods have a clearly different pedigree than SRP-3, which makes them attractive as alternatives to SRP-3 and other methods. Section 6 discusses relevant patent considerations for these methods. Other subtle advantages include slightly increased security and compatibility with IEEE 1363 and ANSI X9 cryptography standards. An appendix highlights simple changes that can be made to an RFC 2945- compliant application or standard to use these alternate methods. This document does not describe an application security protocol. Rather, it describes a set of key agreement protocols in a modular form that can be easily fitted to particular applications. Application-specific design issues are left for other documents to define. <<=== Note: Editorial notes herein are bracketed like this. ===>> Jablon Expires August 13, 2002 [Page 3]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 2. Background Many older password systems fail by treating passwords as cryptographic keys, without any realistic ability to insure appropriate cryptographic quality for these values. As such, they provide the option for either security or convenience, but not both at the same time. Purely hash-based "challenge-response" techniques as described in [RFC 2095] and [RFC 1760], and various forms of Kerberos initial authentication [KN93], were designed to defeat simple sniffing attacks, but unfortunately use the password directly as a message authentication key, and can thus be compromised by exhaustive guessing or dictionary attack by one who obtains protocol messages [BM91]. When using password-based systems, people demand to use simple, easy-to-remember, easy-to-type passwords, which typically do not have sufficient entropy to serve directly as cryptographic keys. Other systems have been designed to protect transmitted passwords by relying on additional security infrastructure. The password-thru-SSL approach is widely used on the Internet, but may be vulnerable to a variety of server spoofing attacks. These attacks are typically not the result of any weak cryptography in SSL, but are rather the result of using SSL only half-way, sending vulnerable password data through a server-only authenticated SSL channel. This puts the password at risk when people must authenticate the server, but don't. The methods described in this document provide a simultaneous, mutual, zero-knowledge proof of a password (ZKPP) -- each party proves to the other that it knows the password without revealing the password to any party that doesn't already know it. In a client/server setting, both acts of user and server authentication are based on a single credential and a single step that the user can't forget to do. ZKPP techniques prevent unnecessary password disclosures whether or not the authentication succeeds, defending against both simple accidents (like typing the wrong password) and malicious attacks (interception by a spoofed or compromised server). These methods surpass the strictest requirements in [RFC 1704] for non-disclosing authentication protocols, and provide full security and mutual authentication even when used with low-entropy passwords. They protect against both passive and active attacks, and in the optimal case accomplish this efficiently using a single Diffie- Hellman computation, making them applicable for a wide range of Internet applications. The incorporation of Diffie-Hellman also provides the benefits of forward secrecy and so-called "backward secrecy", which are important for robust password changing protocols [Jas96] and for strong key management in general. Older password verification systems invariably required the complete or partial disclosure of the password from the prover to the verifier in each act of authentication. ZKPPs eliminate these unnecessary disclosures. Jablon Expires August 13, 2002 [Page 4]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 Methods in this class are also valuable for bootstrapping applications, where an initial act of personal authentication authorizes the download, transmission, or remote verification of private keys, certificates, and other sensitive configuration data. Personal key retrieval, so-called roaming applications, and strong personal or device key management to achieve "pairing" of Bluetooth devices or "wired-equivalent" security in 802.11, are all application areas that can benefit from this class of technique. Proliferation of ad-hoc password systems remains a large and growing problem on the Internet. Zero-knowledge password techniques provide an appropriately strong basis for future consolidation and replacement of ad-hoc password systems. 2.1 Features and Benefits SPEKE, B-SPEKE and SRP-4 all perform mutual authentication and key agreement across an untrusted network while protecting passwords and negotiated authenticated keys. These systems provide security by never sending any passwords or password-crackable data over the network and by integrating the acts of authentication with session key negotiation, using a Diffie- Hellman exchange with standard parameter constraints. They prevent passive and active network attacks, as well as against casual password-sniffing, and specifically prevent unconstrained brute force attack from the network on small passwords. In contrast with classical password techniques, the features and benefits of these methods include: * provide a zero-knowledge proof of a password prevent unconstrained guessing from network attackers prevent disclosure of password to wrong or spoofed server prevent disclosure of wrong password (for different purpose) permit safe mutual authentication * authenticate a server with existing required user action the user can't forget to do it * integrated DH key exchange provides "backward" and forward secrecy enables robust password change protocols <<=== need reference, especially for "backward" secrecy ===>> SPEKE is a balanced password protocol, in that both parties share identical password-derived data. B-SPEKE and SRP-4 are augmented protocols, that are typically used in client/server applications, in which a server stores password verification data derived from a one- way function of the client's password. A thief that steals augmented Jablon Expires August 13, 2002 [Page 5]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 password verification data from a server cannot use it to pose as the user in the protocol, without first "cracking" the password. The methods in this document are specifically aligned or compatible with the Diffie-Hellman (DH) methods in IEEE 1363 and ANSI X9, and are also aligned with the emerging IEEE P1363.2, as discussed in section 4.5. Although it is similar to SRP-3, SRP-4 includes technical improvements for flexibility, correction of a known security flaw, standards compatibility, and simplified structure. The differences and relative benefits and limitations are summarized in Section 4.2 and detailed in Appendix A. 2.3 Origin SPEKE stands for "Simple Password-authenticated Exponential Key Exchange", and was first published in [Jab96]. It has been reviewed, cited, and/or studied in many subsequent papers from [Jab97] to [MacK01b], and has been commercially deployed. Research papers in the field are listed in [P1363.2], with many available on the Internet at [ZKPP Links]. B-SPEKE is an augmented form of the protocol, which was first published in [Jab97]. SRP-4 is an augmented method that combines elements of B-SPEKE and SRP-3 [Wu98]. All the methods in this document achieve roughly the same goals as the pioneering discoveries of Encrypted Key Exchange (EKE) and Augmented-EKE by Bellovin & Merritt and other similar efforts by others in the early 1990's. However, despite the similar acronyms, SPEKE, B-SPEKE, and SRP-4 are based on a different foundation and improve in other ways upon this earlier work. As the earliest zero-knowledge password methods were the subject of patents, commercial adopters might naturally want to investigate the relative status of these and other alternative methods in this field. Discussion of technical issues related to determining the relevance of patents is in section 4.10. 3. Description This section describes the SPEKE, B-SPEKE, and SRP-4 password- authenticated key agreement methods. It begins with preliminary notation, conventions, and terminology in subsection 3.1, followed by a combined description of all three methods in 3.2. SPEKE is a balanced method in which two parties share an identical password-derived value that is used to derive and mutually Jablon Expires August 13, 2002 [Page 6]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 authenticate a Diffie-Hellman key. B-SPEKE and SRP-4 are augmented forms of SPEKE, where SRP-4 further incorporates techniques from SRP-3. An implementation of all of these methods requires little more than a SHA-1 hash function and a standard big integer modular exponentiation function. 3.1. Notation, Conventions, and Terminology This section describes the system parameters, notation, and data format conversion functions used in these methods. The notation closely follows RFC 2945, even though the functional alignment leans toward IEEE 1363. 3.1.1 Parameters The methods described here are parameterized with the following values and functions: N field modulus, a suitable 1024-bit prime of the form kq + 1 q order of the multiplicative group, a suitable 1023-bit prime k the "co-factor" 2 hash SHA-1, or an alternate suitable hash function kdf KDF1-SHA1, as defined in [IEEE 1363], or an alternate suitable key derivation function <<=== consider alternate values for k ===>> <<=== consider defining EC settings ===>> A "suitable" modulus N is one that both parties have determined, or can assume has been chosen, in a verifiably random manner, as is current standard practice for implementations of Diffie-Hellman key agreement. Fixed standard values are generally fine, such as: <<=== looking for a few good groups ... or just one for now ===>> (1) <<=== pick an Oakley group ===>> Another approach is to use transmitted values, which generally must include a way for the recipient to validate the suitability of the parameter. Some examples are: 1) Select from, or confirm that N is in, a list of trustworthy values. 2) Use the approach used in DSA: Given N, a <seed> value, and related iteration parameters, confirm that N = a function of hash(<seed>). 3.1.2 Notation In these descriptions, the | symbol denotes concatenation of byte strings. All hash functions operate on and produce byte strings. Jablon Expires August 13, 2002 [Page 7]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 The * and + operators denote integer multiplication and addition. The ^ and % operators denote integer exponentiation and the integer modular remainder operation, which are combined in any actual implementation of big integer modular exponentiation. The / operator denotes integer division. (Note that the only use of / is in SRP-4, where it can be implemented with simple byte shifts.) The := operator denotes either a definition or the function of assigning a value to a variable. Note also that variables may be bracketed with '<' and '>' in the text for readability, but the brackets are often omitted in equations. That is, <x> and x always refer to the same thing. "DH" stands for "Diffie-Hellman". "DL" refers to the Discrete Logarithm setting, IEEE 1363 terminology for the good old-fashioned modular arithmetic versions of DH, in contrast with "EC", which refers to the Elliptic Curve setting. <<=== EC setting needs definition ===>> This document uses both "SHA1()" to refer to the SHA-1 Secure Hash Algorithm, as defined in [SHA1]. It also uses <hash> as the hash function used to process passwords, and <kdf> as the key derivation function used to derive authenticated keys. SHA1 is recommended for use in both <hash> and <kdf>, but other suitable standard hash and key derivation functions are also allowed. 3.1.3 Data Format Conversion The functions in this description are defined to operate on either byte strings or on unsigned big integers, with an implied standard conversion between these types of values. The necessary conversion functions are specified in this section. The conversion functions used are OS2IP and FE2OSP as defined in [IEEE 1363]. OS2IP converts a byte string (or "octet string") into a non-negative integer, where the first byte represents the most significant 8 bits, presuming unsigned big-endian format. FE2OSP converts a field element into a big-endian byte string, where high zero bytes are added as needed to make the length equal to the number of significant bytes in the field modulus N. A field element is just a big integer in the range [0,N-1], and no sign bit is used in the encoding. For example, the computation "hash(x)^k % N" implies that the big integer value <x> is converted to a byte string before being hashed, and the hash output is converted from a byte string to a big integer Jablon Expires August 13, 2002 [Page 8]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 prior to the modular exponentiation. Thus, the long way of writing this step is "OS2FEP(hash(FE2OSP(x)))^k % N". <<=== Note: To accomodate the EC setting, should describe these in terms of group elements, instead of field elements or integers. For key derivation, FE2OSP is used only on the x-coordinate of EC points. We may want to align better with P1363.2 and/or ISO terminology that treats the EC and DL settings in a more unified manner. ===>> 3.1.4 Bits and Bytes Bit strings in this document (such as the input and output of hash functions) are always a multiple of 8 bits in length, and are treated as byte strings. The high bit of a bit string is treated as the high-bit of the first byte of the corresponding byte string. Thus, the input to SHA1 is a byte string of arbitrary length less than 2^56 bytes, and the 160-bit output is treated as a big-endian 20-byte string. 3.2 General Construction This section describes the general construction of SPEKE, B-SPEKE and SRP-4. When used in a client/server application, the authentication server must have access to some kind of password repository (database or file) which associates a username or similar identifier with password verification data, and, optionally, a salt value. For SPEKE, password verification data can be any arbitrary byte string (designated as <x>) that preserves the entropy of the password and is available to both client and server. All these methods operate in a standard Diffie-Hellman group, such as the multiplicative group of integers modulo prime number N, where N = kq+1, and q is a suitable large prime. 3.2.1 Enrollment During enrollment of the user's credentials with a server, the password value <x> is hashed and converted to a value <g> that serves as password verification data. <g> is an integer in the range [1,N] that generates the group of order q. For the augmented methods B-SPEKE and SRP-4, the server's password verification data is a specially constructed pair of values {<g>, <v>}. SPEKE server stores: { <username>, <g> [, <salt>] } B-SPEKE/SRP-4 server stores: { <username>, <g>, <v> [, <salt>] } Jablon Expires August 13, 2002 [Page 9]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 The value <g> is of order q to be compliant with standard Diffie- Hellman defined in [IEEE 1363] and [ANSI X9.42]. <v> is a standard DH public key corresponding to a base <g> and password-derived DH private key <x>. These methods also require that <x> cannot be derivable from <g>, which is enforced using a hash function. These values are defined as follows: p := the password or other potentially small authenticator string x := any suitable entropy-preserving function of <p> g := hash(x)^k % N v := g^x % N (only used in B-SPEKE and SRP-4) 3.2.2 Identification To start the login process, the client generally sends a user name or identifier to to the server, after which the server retrieves the stored value of <g>, and optionally <v> and/or <salt> values that have been associated with the user's password. The server sends back any optional <salt>. Client Server <username> ---------------> get {g [,v] [,salt]} from storage <------------------- [<salt>] 3.2.3 Key Exchange The client computes <x> and <g> from the user's password and (optionally) the server-supplied <salt> or other parameters. Alternately, in a peer-to-peer application using SPEKE, both parties may compute <g> directly from the shared password. The client generates a secret random number <a> in the range [1,q-1], computes the remainder of raising <g> to the power <a> modulo the field prime <N>, and sends the result to the server. The server generates a secret random number <b> in the range [1,q-1], computes the remainder of raising <g> to the power <b> modulo the field prime <N>, and sends the result to the client. Client Server a := random integer A := g^a % N A ------------------------> b := random integer B := g^b % N <-------------------------- B In the (default) DL setting with k = 2, the value of A or B is defined to be invalid if it is less than 2 or greater than N-2. Jablon Expires August 13, 2002 [Page 10]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 The client must abort if B is invalid, and the server must abort if A is invalid. 3.2.4 Secret Value Derivation When a received value is valid, each party computes a secret byte string <S> based on the appropriate formula as shown here: Client Server For SPEKE: S := B^a % N S := A^b % N For BSPEKE: S := (B^a % N) | (B^x % N) S := (A^b % N) | (v^b % N) For SRP4: u := hash(B) / (2^128) u := hash(B) / (2^128) S := B^(a + u*x) % N S := (A * v^u)^b % N If the client has used the password that corresponds to the server's verification data, authentication is successful and both parties will share the same value for S. 3.2.5 Key Derivation At this point, both parties can derive a set of one or more keys { K_1, K_2, ... } from the (hopefully) shared secret <S> using an appropriate key derivation function. Any set of prefix-free distinct derivation parameters can be used to derive a set of distinct derived keys. (See security note in 4.6.1.) K_i := kdf(S, <key derivation parameter i>) Note that none of these keys <K_i> can be determined by any third- party observer of <B> and <A>, and no second party can negotiate a matching <S> without using the correct password data. Derived keys are useful for various purposes, such as for proving knowledge of <S> in key confirmation, and for use in generating secure session keys. 3.2.6 Key Confirmation To complete the act of explicit mutual authentication, both parties must prove to each other that their shared secret <S> values are identical. Each party may simply send one of the derived keys to the other to explicitly prove to the other that they share the same <S> value, and thus prove that they knew the matching password value. <kdfParam1> := "Client" <kdfParam2> := "Server" Jablon Expires August 13, 2002 [Page 11]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 <kdfParam1> and <kdfParam2> are two arbitrary distinct byte strings that the client and server must agree to use to uniquely tag these key confirmation messages. Client Server K_1 := kdf(S, <kdfParam1>) K_1 -----------------------> verify K_1 K_2 = kdf(S, <kdfParam2>) <------------------------ K_2 verify K_2 The server calculates K_1 using its own value for <S> and <kdfParam1>, and compares it against the client's value for K_1. If they do not match, the server must abort and signal an error. The client calculates K_2 using its own value for <S> and <kdfParam2>, and compares it against the server's value for K_2. If they do not match, the client must abort and signal an error. K_1 and K_2 are, of course, used just once. 3.3 Message Ordering The message flows in these key agreement protocols do not necessarily have a one-to-one correspondence with application protocol messages. Message flows may be generally combined and arranged in any order that permits the necessary computation and application interoperability. 3.4 Compatibility with RFC 2945 Note that in RFC 2945, the order of <g> is (N-1), whereas <g> is of order <q> in this document. For close alignment with RFC 2945, one can use the following specific definitions: p := the raw password byte string username := byte string identifying the user salt := a random byte string stored on the server x := SHA1( <salt> | SHA1( <username> | ":" | <p> ) ) The value <u> is a 32-bit unsigned integer equal to the high-order 32 bits of SHA1(B), and is compatible with RFC 2945. Standard key derivation functions such as KDF1 [IEEE 1363] are incompatible with the "Interleaved SHA1" function in RFC 2945. Jablon Expires August 13, 2002 [Page 12]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 4. Application Notes This section discusses issues to be considered when selecting these methods and related parameters. 4.1 Summary of Benefits These systems optimally protect passwords and negotiate authenticated keys across an untrusted network. They improve security by eliminating the need to send cleartext passwords or other crackable data over the network, by mutually authenticating based on a single user action, and by generating high quality authenticated keys. SRP-4 and B-SPEKE have 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 is stolen, the thief still needs to perform a successful guessing attack to determine the password in order to login. In either case, however, servers are still required to maintain secure storage of password verification data. 4.2 Comparison with SRP-3 and RFC 2945 This section summarizes the differences between SRP-3 and SRP-4. The structural changes in SRP-4 are: * Creates <g> from the password, instead of the fixed value 2. * Removes the +v and -v steps that hide the transmitted <B>. * <g> is of order <q>, instead of of order N-1. * Host stores <g>, along with <username> and <v>. * Modified test for invalid A and B. The resulting limitations & benefits are: SRP-3 SPEKE, B-SPEKE, & SRP-4 -------------------------------- -------------------------------- Restrictions on message order No restrictions on message order Uses Encrypted Key Exchange Doesn't use Encrypted Key techniques Exchange techniques Not aligned with IEEE/ANSI Compatible or aligned with standards IEEE & ANSI standard DH Not-so-scalable to EC groups Scalable to EC groups Vulnerable to 2-for-1 guessing No such known vulnerability attack [MacK01b] B-SPEKE provides these benefits at the expense of somewhat increased computation and the added password verification value <g> stored on the server. SPEKE provides these benefits at the expense of omitting the augmented verifier feature. See also Appendix A for a description of a form of SRP-4 in the exact style of RFC 2945. Jablon Expires August 13, 2002 [Page 13]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 Other changes between RFC 2945 and this document include additional background material and clarifications in presentation and safety recommendations. 4.3 Which Method Should I Use? This document describes three similar but distinct methods, SPEKE, B-SPEKE, and SRP-4. Flexibility is desirable, as people may have different opinions and relative priorities for the goals of maximizing efficiency, compatibility, security, and minimizing licensing concerns in a variety of applications. This section discusses criteria for selecting one method over another. 4.3.1 SPEKE vs. Augmented Methods SPEKE is the simplest and most computationally efficient of the three, plus reduced requirements for server storage in a client/server setting. SPEKE is also the oldest and appears to be the most widely studied of the three. These advantages warrant its use in applications that cannot obtain significant extra benefit from an augmented method. It is also useful in client/server applications where the server cannot control the format of password verification data -- for example, where the server has access to clear-text passwords or passwords transformed with a legacy one-way function. Other references for the relative value of augmented methods are [Wu98], [Jab97], and, for a contrasting argument against the need for the augmented benefit in key-retrieval applications, [PK99]. 4.3.2 B-SPEKE vs. SRP-4 SRP-4 and B-SPEKE are both augmented methods, providing an added benefit in some client/server applications. Both are generally the best known augmented methods, such as SRP-3. SRP-4 combines the benefits of B-SPEKE with the computational efficiency boost of the optimized SRP computation. Due to it's specific construction, one might naturally expect SRP-4 to be closely related to Stanford's pending SRP patent (hence, the name). Depending on the application, one may need to consider requirements for complying with Stanford's license terms. Other considerations may be the relative level of confidence in these methods that one gains from evaluating the body of research papers that review or cite these methods. The SRP-4 construction has had less public scrutiny than the others, but it is based upon the earlier work and close scrutiny of SRP-3 and SPEKE. Note also that SRP introduces a further security parameter in the construction of <u>, that is not present in SPEKE or B-SPEKE, which may merit additional study for some applications. Jablon Expires August 13, 2002 [Page 14]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 Criteria that might favor B-SPEKE over SRP-4 include stricter compliance with IEEE 1363 and ANSI standards, and, perhaps, the intangible respectability of a well-aged method. 4.4 Parameter Selection The modulus <N> is, in general, any modulus that is suitable for a Diffie-Hellman key exchange method. This document recommends a randomly chosen prime N equal to kq+1, where k = 2, and q is prime. N should have at least 640 significant bits to resist discrete logarithm attack. The random secret exponents <a> and <b> have similar constraints of length and entropy as do the private values in a Diffie-Hellman exchange. A somewhat standard acceleration trick for DH, that applies here too, is to choose <a> and <b> from a range [1,t], where <t> is much smaller than <q>, but still sufficiently large. The general rule is for t to have enough bits to avoid a brute-force attack of order 2^(t/2). A typical value is t = 2^160 to preclude known attacks using 2^80 operations. Such security issues are discussed in [IEEE 1363]. This standard recommends that <a> and <b> each contain at least 160 random bits. For the value <u> in SRP-4, implementors may choose to increase the length, as long as both client and server agree, but in general it is recommended that it not be shorter than 32 bits. This value limits a thief who steals <g> and <v> (but hasn't cracked the password) to having no more than a 1-in-2^32 chance of being successful in a single run with a lucky random guess. 4.5 Compatibility with Other Standards Compatibility and alignment with other existing standards promotes re-use of implementation components. Even when strict compatibility cannot be achieved, re-use of standard settings, primitives, and related functions may still encourage implementation compatibility and help provide assurance of security. In contrast with earlier methods in this class, these methods are compatible with the settings, schemes, and primitives defined in [IEEE 1363] and the related [ANSI X9.42] and [ANSI X9.63] equivalents. SPEKE, B-SPEKE and SRP-4 in the DL and EC settings are specifically compatible with the 1363 EC/DLSVDP-DH Diffie-Hellman primitives. SPEKE and B-SPEKE are furthermore compatible with the EC/DLKAS-DH1 and EC/DLKAS-DH2 schemes respectively, when used with an appropriate key derivation function. These methods are also aligned with the work-in-progress on the [IEEE P1363.2] standard for password-based cryptography. Jablon Expires August 13, 2002 [Page 15]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 The description in this document (and the SRP-4 method in particular) is further aligned with RFC 2945, and notes where this goal is in conflict with alignment with other standards. This presentation and the notes in Appendix A are designed to assure maximum consistency with RFC 2945 and the various Internet Drafts and other documents that reference it. Alignment with RFC 2945 in particular facilitates "drop-in" replacement of these methods for SRP-3, to obtain added benefits and improvements described in section 4.2. 4.6 Other Key Derivation and Hash Functions Standard DH1 and DH2 key agreement [IEEE 1363] specifies that the negotiated shared-secret field elements be converted to fixed-length byte strings using FE2OSP, and then processed through a standard key derivation function. Examples using KDF1-SHA1 are shown here: SPEKE: K_i = SHA1( FE2OSP(A^b % N) | <key derivation parameter> ) BSPEKE: K_i = SHA1( FE2OSP(A^b % N) | FE2OSP(v^b % N) | <key derivation parameter> ) This document permits the key derivation function to be any suitable standard function, such as KDF1-SHA1, or other non-standard yet suitable functions, such as SHA_Interleave ([RFC 2945] and Appendix A). Although SHA Interleave is not the preferred choice, we know of no security concern with it. However, although this function attempts to preserve up to 320 bits of entropy in <S>, we note that the effective entropy in <S> is also limited by the entropy in <a> and <b>. Another well-studied alternative is the HMAC-SHA1 function [RFC 2104] which is useful for deriving the keyed message authentication codes used in key confirmation. Any of these methods can be used with suitable alternative hash functions other than SHA-1, such as SHA-256, RIPEMD, and HMAC constructions. 4.6.1 Security Note To securely use any standard key derivation function, it is important that key derivation parameters be prefix-free, that is, no string should be a prefix substring of any other (as in "p1", "p2", ... "p10"). Using KDF1 with same-fixed-length strings or a length- containing encoding such as ASN.1 BER or DER is suggested (see [IEEE 1363], D.5.1.4). 4.7 Key Confirmation Functions This document recognizes that alternate key confirmation functions may be desired in different applications. For example RFC 2945 describes acceptable functions for key confirmation (also shown in Appendix A) that are not compatible with KDF1. Jablon Expires August 13, 2002 [Page 16]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 Note that the protocol messages prior to key confirmation, such as the user name, are not integrity-protected, and as such parties must not rely on these values for security-sensitive purposes. Including party identifiers in the key derivation parameter of a key confirmation message is one way to prevent identity confusion attacks. Many application security protocols include all previously shared messages as key derivation parameters in a key confirmation messages, just to be sure. 4.8 Salt The purpose of salt is to frustrate an attacker who may plan to build a generic dictionary of password verification data that corresponds to a set of likely passwords. Such a dictionary could assist a database thief who steals <g> or <v> in a mass-cracking attack. Salt forces such a dictionary to be built on a case-by-case basis. To be effective, salt must be incorporated into both <g> and <v> in the augmented methods SRP-4 and B-SPEKE. Note that SRP-4 incorporates salt in the computation of <A>, whereas in SRP-3, salt is incorporated at a later stage. This may affect consolidated forms of a server-salted protocol(see Appendix A). In applications where the client sends <A> before contacting the server, a server-supplied salt cannot be incorporated into <x>. In such applications, one might alternately use a self-salting technique, such as by incorporating the username or servername in <x>. 4.9 Iterated Hashing Using an iterated hash function in combination with any of these protocols can increase the required cracking effort for stolen password verification data. For example, one may use: <p> := hash(hash(... hash(<password>) ...)) ... for perhaps thousands of iterations However, in any case, security of the server password database remains a primary way to prevent unconstrained attack, whereas salt and iterated hashing are secondary backup defensive measures. 4.10 Foundation of these methods A potential commercial advantage of these methods is the avoidance of certain patented fundamental techniques. In recent years, a number of researchers have invented (and re- invented) various techniques for zero-knowledge password proofs. Jablon Expires August 13, 2002 [Page 17]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 It takes time for a clear picture to emerge of what works and what doesn't, and of who first invented what and when, after careful study of available publications. This section reviews structural differences and similarities of these methods to shed light on relevant technical issues underlying patents in this field. SPEKE, B-SPEKE and SRP-4 achieve roughly the same goals as defined in early efforts, but are based on different fundamental techniques, resulting in both subtle and important advantages. The fundamental techniques in the Encrypted Key Exchange methods (described in US patent 5,241,599) use a password-based key to "symmetrically encrypt" and "symmetrically decrypt" messages during key negotiation, to hide the messages from an attacker. Both DES and XOR were described as suitable encryption functions. The Augmented-EKE techniques (described in US 5,440,635) use either "symmetric encryption" or "public-key decryption" to recover a message during key negotiation. This partly-unfinished work introduced the concept of an "augmented" password protocol. However, these specific Augmented-EKE techniques aren't used in SPEKE, B-SPEKE, or SRP-4. SPEKE ([Jab96] and US 6,226,383) is a balanced protocol where both parties use a password-based generator in a Diffie-Hellman exchange. This is fundamentally different than the "Encrypted" Key Exchange, in that SPEKE is implemented with purely one-way functions. No symmetric encryption, public key decryption, or any other reversible function is used. B-SPEKE is an augmented form of SPEKE based on [Jab97]. B-SPEKE uses a combined form of static-ephemeral dual Diffie-Hellman exchange, where the password is used to form a DH generator and is also used in the exponent of a static DH public key. The DH public key is stored as password verification data. Like SPEKE, B-SPEKE uses purely one- way functions and no symmetric encryption or public-key decryption. SRP-3, the "Secure Remote Password" protocol version 3, is an augmented protocol published in [Wu98] and described in [RFC 2945]. SRP-3 has attracted widespread attention as a valuable protocol for many applications. Along with some sublte limitations (discussed below), a potential problem for commercial adoption of SRP-3 is in its use of fundamental techniques from earlier methods. SRP-3 uses addition and subtraction of password-derived value to hide a message from attackers, for a purpose similar to the symmetric encryption in Encrypted Key Exchange. SRP-4 combines the best of SRP-3 and B-SPEKE. In contrast with SRP- 3, it eliminates any EKE-like steps of hiding and unhiding messages using a password, and instead uses a SPEKE-like password-derived generator. As in SPEKE and B-SPEKE, SRP-4 does not use any symmetric Jablon Expires August 13, 2002 [Page 18]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 encryption/decryption, any public-key decryption, or any other similar techique. People have recognized that zero-knowledge password methods are valuable enough to warrant the effort of inquiring about license requirements for their use. This document presents alternatives to the IETF community that expand licensing choice without sacrificing important design principles of user security and convenience. 5. Security Considerations Security considerations discussed throughout this document include parameter selection, relevant cryptographic research, and comparison of these key agreement protocols to other methods. 6. Intellectual Property Notice Phoenix Technologies Ltd. is assigned a US patent which is relevant to SPEKE, B-SPEKE, and SRP-4. Stanford University has announced filing a US patent application for SRP, which may be relevant to SRP-4. License policy statements regarding these patents and methods are on file with the IEEE and IETF. Section 4.10 further discusses technical foundations that motivate patent license requirements for methods in this field, including a review of differences between the methods described herein and the SRP-3, Encrypted Key Exchange, and Augmented-EKE methods. The latter two methods are described in two other US patents. References [ANSI X9.42] ANSI X9.42-2001, "Public Key Cryptography for the Financial Services Industry: Agreement of Symmetric Keys Using Discrete Logarithm Cryptography", ANSI, 2001. [ANSI X9.63] ANSI X9.63-2001, "Public Key Cryptography for the Financial Services Industry, Key Agreement and Key Transport Using Elliptic Curve Cryptography", ANSI, 2001. [Bla02] Black, D., "iSCSI Security Requirements and SRP-based ESP Keys", IETF draft-black-ips-iscsi-security-01.txt (work in progress), August 2001. Jablon Expires August 13, 2002 [Page 19]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 [BM91] Bellovin S., and M. Merritt, "Limitations of the Kerberos Authentication System", ACM Computer Communications Review, October 1990. [BN02] Burdis, K.R., and R. Naffah , "Secure Remote Password SASL Mechanism", IETF draft-burdis-cat-srp-sasl-06.txt (work in progress), January 12, 2002. [CAH01] Carlson, J., Aboba, B. and, H. Haverinen, "PPP EAP SRP- SHA1 Authentication Protocol", IETF draft-ietf-pppext- eap-srp-03.txt (work in progress), July 2001. [Far02] S. Farrell, editor, "Securely Available Credentials Protocol", January 2002, IETF draft-ietf-sacred- protocol-bss-01.txt (work in progress). [IEEE 1363] IEEE Std 1363-2000, "IEEE Standard Specifications for Public-Key Cryptography 2000", IEEE, 2000. [Jab96] D. Jablon, "Strong Password-Only Authenticated Key Exchange", Computer Communication Review, ACM SIGCOMM, vol. 26, no. 5, pp. 5-26, October 1996. [Jab97] Jablon, D., "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. [Jas96] B. Jaspan, Dual-workfactor Encrypted Key Exchange: Efficiently Preventing Password Chaining and Dictionary Attacks, Proceedings of the Sixth Annual USENIX Security Conference, July 1996, pp. 43-50. [KN93] Kohl, J., and C. Neuman, "The Kerberos Network Authentication Service (V5)", RFC 1510, Digital Equipment Corporation, USC/Information Sciences Institute, September 1993. [MacK01b] MacKenzie, P., "On the Security of the SPEKE Password- Authenticated Key Exchange Protocol", Cryptology ePrint Archive: Report 2001/057, <http://eprint.iacr.org/2001/057/>. [Mol01] N. M”ller, "Using the SRP protocol as a key exchange method in Secure Shell", IETF draft-nisse-secsh-srp- 01.txt (work in progress), March 2001. [P1363.2] IEEE P1363.2, "Standard Specifications for Public-Key Cryptography: Password-Based Techniques", (work in progress), IEEE, <http://grouper.ieee.org/groups/1363/>. Jablon Expires August 13, 2002 [Page 20]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 [PK99] Perlman, R. and C. Kaufman, "Secure Password-Based Protocol for Downloading a Private Key", Proceedings of the 1999 Network and Distributed System Security, February 3-5, 1999. [RFC 1321] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April 1992. [RFC 1704] Haller, N. and R. Atkinson, "On Internet Authentication", RFC 1704, October 1994. [RFC 1760] Haller, N., "The S/Key One-Time Password System", RFC 1760, Feburary 1995. [RFC 2095] Klensin, J., Catoe, R. and P. Krumviede, "IMAP/POP AUTHorize Extension for Simple Challenge/Response", RFC 2095, January 1997. [RFC 2104] Krawczyk, H., Bellare, M. and R. Canetti, "HMAC: Keyed- Hashing for Message Authentication", RFC 2104, February 1997. [RFC 2945] T. Wu, "The SRP Authentication and Key Exchange System", RFC 2945, September 2000. [SACRED] IETF Securely Available Credentials (sacred) working group, Security Area, IETF, <http://www.ietf.org/html.charters/sacred-charter.html> [SHA1] National Institute of Standards and Technology (NIST), "Announcing the Secure Hash Standard", FIPS 180-1, U.S. Department of Commerce, April 1995. [Tay01] D. Taylor, "Using SRP for TLS Authentication", IETF draft-ietf-tls-srp-01.txt (work in progress), June 29, 2001. [Wu98] T. Wu, "The Secure Remote Password Protocol", In Proceedings of the 1998 Internet Society Symposium on Network and Distributed Systems Security, San Diego, CA, pp. 97-111. [ZKPP Links] "Research Papers on Strong Password Authentication", <http://www.integritysciences.com/links.html>. Jablon Expires August 13, 2002 [Page 21]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 Author's Address David Jablon Phoenix Technologies Ltd. 320 Norwood Park South Norwood, MA 02062 EMail: david_jablon@phoenix.com Full Copyright Statement Copyright (C) The Internet Society (2002). 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. Acknowledgements The author thanks Paul Funk, Nora Hanley, and Jim Walker for their review and thoughtful comments on early drafts. This document includes significant material derived from the important work of Tom Wu and RFC 2945. The author is also grateful for the encouragement and advice from Steve Bellovin and Michael Wiener during the initial refinement of these methods. Funding for the RFC Editor function is currently provided by the Internet Society. Jablon Expires August 13, 2002 [Page 22]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 Appendix A: An SRP4-SHA1 mechanism This section describes a form of SRP-4 employing SHA-1 to authenticate users and generate session keys. This text is revised from section 3 of RFC 2945 (SRP-3), and is suitable for "diff"ing. The host stores user passwords as quartets of the form { <username>, <password generator>, <password verifier>, <salt> } Password entries are generated as follows: <salt> = random() x = SHA(<salt> | SHA(<username> | ":" | <raw password>)) <password generator> = g = SHA(x)^2 % N <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. 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() x = SHA(s | SHA(U | ":" | p)) g = SHA(x)^2 % N A = g^a % N --> g = <stored password generator> v = <stored password verifier> b = random() <-- B = g^b % N p = <raw password> S = B ^ (a + u * x) % N S = (A * v^u) ^ b % N K = SHA_Interleave(S) K = SHA_Interleave(S) (this function is described in section A.1) The client generates a random number a, computes x and g from the password, raises g to the power of random number a and reduces it Jablon Expires August 13, 2002 [Page 23]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 modulo the field prime, and sends the result to the host. The host generates a random number b, raises g to the power of random number b and reduces it modulo the field prime, and sends the result 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 is less than 2 or greater than N-2. The host MUST abort the authentication attempt if A is less than 2 or greater than N-2. 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. 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 SRP4-SHA1 mechanism to consolidate some of the flows as follows: Client Host -------- ------ U --> <-- s, B A, H(H(N) XOR H(g) | H(U) | s | A | B | K) --> <-- H(A | M | K) (Note: In RFC 2945, A is sent along with U. This consolidated SRP-4 protocol sends A after receiving s, as A is derived from s.) Jablon Expires August 13, 2002 [Page 24]
Internet-Draft draft-jablon-speke-00.txt February 13, 2002 The value of N used in this protocol must be agreed upon by the two parties in question. It can be set in advance, or the host can supply it to the client. In the latter case, the host should send N 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), chosen in a random manner, and the client must have a means of assuring the suitability of N. Also, note that g is a generator of the group of order q, which means that for any element X in the group of order q, there exists a value x in the range [1,q] for which g^x % N == X. A.1. Interleaved SHA The SHA_Interleave function used in SRP4-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. A.2. Other Hash Algorithms SRP-4 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]. Keyed hash transforms are also recommended for use with SRP; one possible construction uses HMAC [RFC 2104], using K to key the hash in each direction instead of concatenating it with the other parameters. 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. [Wu98] covers these issues in more depth. Jablon Expires August 13, 2002 [Page 25]