Network Working Group D. Jablon Internet Draft Phoenix Technologies draft-jablon-speke-02.txt October 22, 2003 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 the SPEKE, B-SPEKE, and W-SPEKE methods for password-based key agreement and authentication. In the same category of techniques as EKE and SRP, these methods provide a zero- knowledge password proof 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 provide important options for convenient and secure personal authentication. Jablon [Page 1] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 Table of Contents Status of this Memo .............................................. 1 Abstract ......................................................... 1 1. Introduction .................................................. 3 2. Background .................................................... 3 2.1 Summary of Features and Benefits ......................... 4 2.3 Origin ................................................... 5 3. Description ................................................... 6 3.1. Notation, Conventions, and Terminology ................... 6 3.1.1 Parameters .......................................... 6 3.1.2 Notation ............................................ 6 3.1.3 Data Formats and Conversion ......................... 7 3.1.4 Bits and Bytes ...................................... 7 3.2 General Construction ..................................... 7 3.2.1 Enrollment .......................................... 8 3.2.2 Identification ...................................... 8 3.2.3 Key Exchange ........................................ 9 3.2.4 Secret Value Derivation ............................. 9 3.2.5 Key Derivation ...................................... 10 3.2.6 Key Confirmation .................................... 10 3.3 Message Ordering ......................................... 11 3.4 Compatibility with RFC 2945 .............................. 11 4. Method Selection and Application Notes ....................... 11 4.1 W-SPEKE, B-SPEKE, and SRP ................................ 12 4.2 Balanced vs. Augmented Methods ........................... 12 4.3 B-SPEKE vs. W-SPEKE ...................................... 13 4.4 Parameter Selection ...................................... 13 4.5 Compatibility with Other Standards ....................... 14 4.6 Other Key Derivation and Hash Functions .................. 14 4.6.1 Security Note ....................................... 15 4.7 Key Confirmation Functions ............................... 15 4.8 Salt ..................................................... 15 4.9 Iterated Hashing ......................................... 16 5. Security Considerations ....................................... 16 6. Intellectual Property Notice .................................. 16 References ....................................................... 17 Author's Address ................................................. 19 Full Copyright Statement ......................................... 19 Acknowledgements ................................................. 19 Appendix A: An APKAS-WSPEKE mechanism ............................ 20 A.1. Interleaved SHA ......................................... 22 A.2. Other Hash Algorithms ................................... 22 Appendix B: Extended FIPS 186-2 Prime Generation and Verification..23 B.1 Extended Method for Generation of Primes .................. 23 B.2 Method for Verification of Primes ......................... 25 B.2.1 Fast method .......................................... 25 B.2.2 Slow method .......................................... 25 Jablon [Page 2] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 1. Introduction This document describes SPEKE, B-SPEKE, and W-SPEKE, three methods that provide cryptographically strong password-based key agreement and network authentication. These methods are in the same category as the earlier EKE [BM92] and later SRP [RFC2945] methods, but use some different techniques. Some advantages of these methods over SRP are slightly increased security and compatibility with IEEE 1363 and ANSI X9 cryptography standards. An appendix highlights changes that can be made to an RFC 2945-compliant application or standard to use these as alternatives. Other documents may adapt these methods for specific applications. Section 2 describes background and rationale for this class of method, where they were developed, what they do, and why. Section 3 describes the SPEKE methods in detail, and section 4 discusses method selection, parameter selectio, and other application issues. Two potentially relevant patents are listed in Section 6. 2. Background Convenient and secure personal authentication is important for many Internet applications. People want their passwords to be easy to remember and type, and also secure. But most earlier password systems offer insufficient protection against passive and active network attack on passwords. While complex public key based infrastructures have evolved, they often still rely on a password as the human link. Some older systems fail by treating passwords as cryptographic keys, without any real 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 [RFC2095] and [RFC1760], and various forms of Kerberos initial authentication [RFC1510], 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 [BM90]. Passwords often need to be simple, easy-to-remember, and easy-to-type, which means that they cannot safely be used like traditional encryption keys. Still other systems try to protect transmitted passwords by relying on a separate security infrastructure. The password-thru-SSL approach as commonly used in web browsing is vulnerable to spoofing attacks. These are not the result of weak cryptography, but rather, due to the generally weak concept of giving away a password to prove knowledge of it. In so-called "tunnelled" protocols, the password may flow through a authenticated channel in which the sole act of server authentication is ignored or bypassed by a typical user. When people must authenticate the server, but don't, their passwords are at risk. Jablon [Page 3] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 Old methods for proving knowledge of a secret force disclosure of the secret from the prover to the verifier during each act. Such practices should be discouraged where non-disclosing zero-knowledge methods are available. Strong password methods, including SPEKE, were first discovered in the 1990's. They use ephemeral public key techniques to securely bind people to keys, using a small or not-so-random password, and perform a zero-knowledge password proof (ZKPP), where each party proves to the other that it knows the password without revealing it to any party that doesn't already know it. These methods also negotiate a mutually authenticated session key between the parties based on knowledge of the password. This can happen over an unprotected network, without revealing the password or keys to attackers, requiring no certificates, no long-term sensitive data at the client, and minimal demands on the user. These benefits are attractive for providing secure and convenient personal authentication. While these methods work with passwords alone, they are also used to provide secure mobility and credential provisioning in systems that use additional secret key or public key infrastructure. Security is improved by reducing assumptions on proper user behavior and reducing dependencies on security infrastructure. SPEKE and other zero-knowledge password methods have been deployed in both academic and commercial settings. SRP has been described in [RFC2944] and [RFC2945], and referenced in several Internet Drafts. These methods are also described in the proposed IEEE standard for password-based public key cryptography [P1363.2]. 2.1 Summary of Features and Benefits SPEKE, B-SPEKE and W-SPEKE all perform mutual authentication and key agreement across an untrusted network while protecting passwords and negotiated authenticated keys. These methods do not send any passwords or password-crackable data over the network; Instead they integrate the password into a standard Diffie-Hellman exchange in a way that negotiates a mutually authenticated key. Even with a password that is too small to serve as a cryptographic key, these methods prevent passive and active network attacks (man- in-the-middle, replay, etc.), as well as password-sniffing and unconstrained brute force attack from the network. These methods surpass the requirements in [RFC1704] for non-disclosing authentication protocols. Because both acts of user and server authentication are based on a common credential, and a step that the user can't forget to do, these methods are superior to tunnelled methods in common applications. ZKPP techniques prevent unnecessary password disclosures whether or not the authentication succeeds, defending against both simple accidents (typing the wrong password) Jablon [Page 4] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 and malicious attacks (interception by a spoofed or compromised server). The methods are as efficient as a Diffie-Hellman key exchange (DH) computation, using any standard groups. The incorporation of DH 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. These methods include both balanced and augmented password-based key agreement methods. SPEKE is a balanced method, in that both parties share identical password-derived data. B-SPEKE and W-SPEKE are augmented methods, 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 password verification data from a server cannot use it to pose as the user in the protocol, without first "cracking" the password. W-SPEKE is comparable to SRP, with differences in structure, benefits, and limitations as described in section 4.2 and Appendix A. Two of these methods are compatible with standard Diffie-Hellman as described in [IEEE 1363] and [ANSI X9.42], and are also aligned with the emerging IEEE [P1363.2] standard for password-based cryptography (see section 4.5). Implementation requires little more than a hash function and big integer modular exponentiation. Use of alternative settings, such as elliptic curve groups [ANSI X9.63], is beyond the scope of this document. Methods in this class are particularly 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 general provisioning of keys are all ideal applications in both wired and wireless settings. Continued proliferation of ad-hoc password systems still remains a large problem on the Internet -- SPEKE and other zero-knowledge password methods provide an appropriate foundation for future consolidation and replacement of such ad-hoc systems. 2.2 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 including [Jab97] and [MacK01b], and has been commercially deployed. SPEKE is a "balanced" method, where two parties share an identical password-derived value that is used to derive and mutually authenticate a Diffie-Hellman key. B-SPEKE, first published in [Jab97], is an augmented method, where the server's password verification data cannot be used directly by the client. Jablon [Page 5] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 W-SPEKE is an augmented method that has similarities to both B-SPEKE and SRP [Wu98]. W-SPEKE was described as "SRP-4" in an earlier Internet draft and a submission to IEEE P1363. A brief comparison of some of these methods is in section 4.3, and lists of research papers are available in [P1363.2] and [ZKPPLinks]. 3. Description This section describes the SPEKE, B-SPEKE, and W-SPEKE 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. 3.1. Notation, Conventions, and Terminology This section describes the system parameters, notation, and data format conversion functions used in these methods. The parameter notation is similar to RFC 2945, and the function names are aligned with IEEE 1363. 3.1.1 Parameters The methods described here use multiplicative groups of integers, parameterized with the following values and functions: N field modulus, a suitable 1024-bit prime of the form kq + 1 q prime order of the subgroup to be used, larger than 2^159 k the "co-factor", k=N-1/q. It is recommended that all divisors of k/2 other than 1 be larger than q. hash SHA-1, or an alternate suitable hash function kdf KDF1-SHA1, as defined in [IEEE 1363], or an alternate suitable key derivation function Selection of suitable values is discussed in section 4.4. 3.1.2 Notation In these descriptions, the | symbol denotes concatenation of byte strings. All hash functions operate on and produce byte strings. The * and + operators denote integer multiplication and addition. The ^ and % operators denote integer exponentiation and the integer modular remainder operation. The / operator denotes integer division. The := operator denotes either a definition of a term or the function of assigning a value to a variable. Jablon [Page 6] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 Note also that variables may be bracketed with '<' and '>' in the text for readability, but the brackets are often omitted in equations; Unambiguous uses of x and refer to the same thing. "DH" stands for "Diffie-Hellman". "DL" refers to the so-called discrete logarithm setting that uses a multiplicative group of integers. ("EC" would refer to the elliptic curve setting.) SHA1() refers to the SHA-1 Secure Hash Algorithm, as defined in [SHA1]. is a hash function used to process passwords. is a key derivation function used to derive authenticated keys. SHA1 may be used for both and , although other suitable standard hash and key derivation functions are acceptable. 3.1.3 Data Formats and 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 a big integer in the range [0,N-1], with no sign bit 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 prior to the modular exponentiation. Thus, a long way to describe this step is "OS2FEP(hash(FE2OSP(x)))^k % N". 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 W-SPEKE. Jablon [Page 7] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 When used in a client/server application, the authentication server must have access to a 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 ) that preserves the randomness of the password and is available to both client and server. The parties must agree on which method to use, including domain parameters, hash, key derivation, and key confirmation functions. These values may be fixed in the implementation of the client and server. The parties must also initially agree on a password, and how they do that is beyond the scope of this document. 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 that serves as password verification data. is in the range [1,N-1]. For B-SPEKE and W-SPEKE, the server's password verification data is a specially constructed pair of values {,}. SPEKE server stores: { , [, ] } B-SPEKE/W-SPEKE server stores: { , , [, ] } The value is of order . is a standard DH public key corresponding to a base raised to the power of password-derived DH private key . These methods also require that cannot be derivable from , which is enforced using a hash function to compute from . These values are defined as follows: p := the password or other potentially small authenticator string x := any suitable derivation of

that preserves its randomness g := REDP(x), "REDP" is a random element derivation function v := g^x % N (only used in B-SPEKE and W-SPEKE) Two suitable REDP functions [P1363.2] are: REDP-1(x) = hash(x)^k % N REDP-2(x) = (ga * gb^hash(x)) % N ga = REDP-1("Alice") gb = REDP-2("Bob") and are two arbitrary elements of order q that have no known exponential relationship to each other. 3.2.2 Identification To start the login process, the client typically sends a user name or identifier to the server, after which the server retrieves the stored Jablon [Page 8] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 value of , and optionally and/or values that have been associated with the user's password. The server sends back any optional . Client Server ---------------> get {g [,v] [,salt]} from storage <------------------- [] 3.2.3 Key Exchange The client computes and from the user's password and (optionally) the server-supplied or other parameters. Alternately, in a peer-to-peer application using SPEKE, both parties may compute directly from the shared password. The client generates a secret random number in the range [1,q-1], computes the remainder of raising to the power modulo the field prime , and sends the result to the server. The server generates a secret random number in the range [1,q-1], computes the remainder of raising to the power modulo the field prime , 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 DL setting where equals 2 or 2r and where all divisors of r other than 1 are greater than q, the value of or is defined to be unacceptable if it is not in the range [2,-2] inclusive. When is an unacceptable value, the client must abort before revealing any information derived from . When is an unacceptable value, the server must abort before revealing any information derived from . In general, for any DH group, acceptable values of and are those that generate a suitably large set of possible values for , to preclude enumeration of the possible results by an attacker. 3.2.4 Secret Value Derivation When a received value is valid, each party computes a secret byte string based on the appropriate computation as shown here: Client Server Jablon [Page 9] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 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 WSPEKE: 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 . 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 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, ) Note that none of these keys can be determined by any third- party observer of and , and no second party can negotiate a matching without using the correct password data. Derived keys are useful for various purposes, such as for proving knowledge of 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 prove to each other that their shared secret values are identical. They can use a key confirmation function (KCF) to derive a unique parameterized key from , send the KCF output key to the other party, after which each party verifies the other's correct computation. One specific construction compatible with [P1363.2] also incorporates other shared secret and public values as shown here. The client and server agree that the client will send KCF(), and the server will send KCF(kcfParam2). Client Server K_1 := kcf() K_1 := kcf() K_1 -----------------------> verify K_1 K_2 := kcf() K_2 := kcf() verify K_2 <------------------------ K_2 Jablon [Page 10] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 := hex byte 04 := hex byte 03 := KCF1-SHA1 KCF1-SHA1() := SHA1( | A | B | S | g) The server computes its value for K_1 as a hash of its concatentated values for , A, B, S, and g, and then it compares its K_1 value to the value of K_1 received from the client. If they are not equal, the server must abort and signal an error. The client performs the analogous procedure for verifying the server's K_2. 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. There are no special security constraints on message flows, so that they may be generally combined and arranged in any order that permits necessary computation and interoperability. 3.4 Compatibility with RFC 2945 In RFC 2945, is of order (N-1), but here is of order . 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( | SHA1( | ":" |

) ) The value is a 32-bit unsigned integer equal to the high-order 32 bits of SHA1(B), and is compatible with RFC 2945. The "Interleaved SHA1" key derivation function in RFC 2945 is not compatible with KDF1-SHA1 or other KDFs defined in [IEEE 1363]. 4. Method Selection and Application Notes SPEKE, B-SPEKE, and W-SPEKE are three similar but distinct methods. The general benefits of these and other zero-knowledge password methods over earlier techniques is reviewed in section 2. This section compares these and some other methods in the same category, and discusses issues to consider in choosing a specific method, selecting system parameters and primitive functions, and related application notes. Flexibility may be desirable, as people have different opinions and relative priorities for efficiency, compatibility, security, and Jablon [Page 11] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 licensing concerns in a variety of applications. This section discusses technical criteria for selecting one method over another. Business issues may also be relevant, but are beyond the scope of this document. 4.1 W-SPEKE, B-SPEKE, and SRP W-SPEKE may be described as a variant of B-SPEKE that uses an optimized exponential computation from SRP. W-SPEKE may also be seen as a variant of SRP with the following differences: * Derives generator from password, instead of =2. * Removes the +v and -v steps associated with . * is of order , instead of order N-1. * Host stores , along with and . * Modified test for unacceptable A and B. The resulting limitations & benefits are: SRP W-SPEKE, B-SPEKE -------------------------------- -------------------------------- Restrictions on message order No restrictions on message order Not aligned with IEEE/ANSI May use IEEE/ANSI DH primitives Two guesses per run [MacK01b] One guess per run B-SPEKE has somewhat increased computation over W-SPEKE and an added password verification value stored on the server as compared to SRP. See also Appendix A for a description of a form of W-SPEKE in the style of RFC 2945. Other changes between RFC 2945 and this document include additional background material and clarifications in presentation and safety recommendations. SRP and W-SPEKE use an additional security parameter in the construction of , that is not present B-SPEKE (or SPEKE), which may merit additional study for some applications. 4.2 Balanced vs. Augmented Methods All of the SPEKE methods provide a strong basic level of protection against network attack for passwords and their authenticated keys. The augmented methods W-SPEKE and B-SPEKE provide the added benefit over SPEKE of permitting the host to store passwords in a form that is not directly useful to an attacker. In an augmented system, 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. References that discuss relative value of augmented methods are [Wu98], [Jab97], and [PK99], the latter providing reasons why the augmented benefit may not be necessary for key-retrieval applications. Jablon [Page 12] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 SPEKE is the simplest, most efficient, and by some measures 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 may also be preferred for 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. 4.3 B-SPEKE vs. W-SPEKE W-SPEKE and B-SPEKE are both augmented methods that may provide an added benefit in client/server applications. W-SPEKE combines the benefits of B-SPEKE with the computational efficiency boost of an optimized computation similar to that used in SRP. A factor that might favor B-SPEKE over W-SPEKE is conformance with IEEE 1363 and ANSI DH standards. 4.4 Parameter Selection This specification requires that the modulus is, in general, any modulus that is suitable for a Diffie-Hellman key exchange. A suitable is prime, defines a suitably large subgroup of prime order q (for compliance with standard DH in [IEEE 1363] and [ANSI X9.42]), and allows group elements to be checked for membership in a small subgroup. If there are any divisors of /2 other than 1, it is recommended that they be larger than q. The modulus must also be one in which the parties can trust has not been specially crafted to provide advantages for an attacker. Construction methods and examples of verifiable primes suitable for SPEKE are defined in [RFC2412] and in [FIPS 186-2] Appendix 2. The random secret exponents and have length and quality constraints similar to any Diffie-Hellman exchange. A common acceleration trick for DH, that applies here too, is to choose and from a range [1,t], where is much smaller than , 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 document recommends that and each contain at least 160 random bits. For the value in W-SPEKE, implementors may choose to increase the length, as long as both client and server agree, but in general this document recommends that it not be shorter than 32 bits. This value limits a thief who steals and (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. Jablon [Page 13] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 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. These methods are aligned with the BPKAS-SPEKE, APKAS-BSPEKE, and APKAS-WSPEKE schemes as described in the IEEE proposed standard for password-based public key cryptography [P1363.2]. These methods are also compatible with the settings, schemes, and primitives defined for Diffie-Hellman in [IEEE 1363] and the related [ANSI X9.42] and [ANSI X9.63] equivalents. SPEKE, B-SPEKE and W- SPEKE in the DL and EC settings are compatible with the 1363 EC/DLSVDP-DH primitives, and SPEKE and B-SPEKE are furthermore compatible with the EC/DLKAS-DH1 and EC/DLKAS-DH2 schemes. This document further shows where W-SPEKE is aligned with RFC 2945 and where such alignment conflicts with other standards. It maximizes consistency with RFC 2945, and the various Internet Drafts and other documents that reference it, to facilitate "drop-in" replacement of these methods for SRP. 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) | ) BSPEKE: K_i = SHA1( FE2OSP(A^b % N) | FE2OSP(v^b % N) | ) 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 ([RFC2945] 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 , we note that the effective entropy in is also limited by the entropy in and . Another well-studied alternative is the HMAC-SHA1 function [RFC2104] 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. Jablon [Page 14] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 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 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 KCF1. 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 or 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 and in the augmented methods W-SPEKE and B-SPEKE. Note that W-SPEKE incorporates salt in the computation of , whereas in SRP3, 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 before contacting the server, a server-supplied salt cannot be incorporated into . In such applications, one might alternately use a self-salting technique, such as by incorporating the username or servername in . Jablon [Page 15] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 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:

:= hash(hash(... hash() ...)) ... 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. 5. Security Considerations Security considerations are discussed throughout this document, including parameter selection, relevant cryptographic research, and comparison of these to other methods. 6. Intellectual Property Notice Phoenix Technologies Ltd. and Stanford University own patents that describe the SPEKE and SRP methods respectively. For more information, including contact information for resolving questions, readers are referred to the IPR statements available at http://www.ietf.org/ipr.html. Jablon [Page 16] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 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. [BM90] Bellovin, S., and M. Merritt, "Limitations of the Kerberos Authentication System", ACM Computer Communications Review, October 1990. [BM92] Bellovin, S., and M. Merritt, "Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attacks", Proceedings of the I.E.E.E. Symposium on Research in Security and Privacy, Oakland, May 1992. [FIPS 186-2] FIPS 186-2, Digital Signature Standard, NIST. [IEEE 1363] IEEE Std 1363-2000, "IEEE Standard Specifications for Public-Key Cryptography 2000", IEEE, 2000. [Jab96] Jablon, D., "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. [RFC1510] 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, . Jablon [Page 17] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 [P1363.2] IEEE P1363.2, "Standard Specifications for Public-Key Cryptography: Password-Based Techniques", (work in progress), IEEE, . [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. [RFC1321] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April 1992. [RFC1704] Haller, N. and R. Atkinson, "On Internet Authentication", RFC 1704, October 1994. [RFC1760] Haller, N., "The S/Key One-Time Password System", RFC 1760, Feburary 1995. [RFC2095] Klensin, J., Catoe, R. and P. Krumviede, "IMAP/POP AUTHorize Extension for Simple Challenge/Response", RFC 2095, January 1997. [RFC2104] Krawczyk, H., Bellare, M. and R. Canetti, "HMAC: Keyed- Hashing for Message Authentication", RFC 2104, February 1997. [RFC2944] T. Wu, "Telnet Authentication: SRP", RFC 2944, September 2000. [RFC2945] T. Wu, "The SRP Authentication and Key Exchange System", RFC 2945, September 2000. [SHA1] National Institute of Standards and Technology (NIST), "Announcing the Secure Hash Standard", FIPS 180-1, U.S. Department of Commerce, April 1995. [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. [ZKPPLinks] "Research Papers on Strong Password Authentication", . Jablon [Page 18] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 Author's Address David Jablon Phoenix Technologies Ltd. 320 Norwood Park South Norwood, MA 02062 EMail: david_jablon at 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, Jim Walker, and Tom Wu for their review and thoughtful comments on earlier drafts. This document includes significant material derived from 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. Jablon [Page 19] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 Appendix A: An APKAS-WSPEKE mechanism ------------------------------------- This section describes a form of APKAS-WSPEKE employing SHA-1 to authenticate users and generate session keys. This text is revised from section 3 of RFC 2945 (SRP), and is suitable for "diff"ing. The host stores user passwords as quartets of the form { , , , } Password entries are generated as follows: = random() x = SHA( | SHA( | ":" | )) = g = SHA(x)^2 % N = 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 = --> <-- s = 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 = v = b = random() <-- B = g^b % N p = 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 [Page 20] Internet-Draft draft-jablon-speke-02.txt October 22, 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 APKAS-WSPEKE-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 W-SPEKE protocol sends A after receiving s, as A is derived from s.) Jablon [Page 21] Internet-Draft draft-jablon-speke-02.txt October 22, 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 WSPEKE-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 W-SPEKE 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 [Page 22] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 Appendix B: Extended FIPS 186-2 Prime Generation and Verification ----------------------------------------------------------------- This section describes an extension of the method to generate "kosherized" primes for DSA, as described in [FIPS186-2]. The FIPS method could be used to generate primes of the form p=2qr+1, but it was limited to 1024 bit p with 160 bit subgroup order q. This extended method can generate larger p's and q's, and supports explicit options for requiring that r be prime, or r = 1, which are all useful for Diffie-Hellman, SPEKE, and related methods. The option for prime r is fully compatible with the standard in that all primes p,q of suitable size generated by this method can be verified by any compliant implementation of FIPS 186-2. B.1 Extended Method for Generation of Primes This method generates primes, p and q, satisfying the following three or four conditions: a. 2^(M-1) < q < 2^M for a specified M (e.g. M = 224) b. 2^(L-1) < p < 2^L for a specified L (e.g. L = 2048) c. q divides p - 1. d. (optionally) r is prime, where r = (p-1)/(2q). This method is a compatible extension of the DSA prime generation method specified in FIPS 186-2 Appendix 2.2. It is extended to generate values for q that are larger than 160 bits, to generate primes where p = 2q+1, and with the option to require that r is prime. This prime generation scheme starts by using the SHA-1 and a user supplied SEED to construct a prime, q, in the range 2^(M-1) < q< 2^M. Once this is accomplished, the same SEED value is used to construct an X in the range 2^(L-1) < X < 2^L. The prime, p, is then formed by rounding X to a number congruent to 1 mod 2q as described below. An integer x in the range 0 <= x < 2g may be converted to a g-long sequence of bits by using its binary expansion as shown below: x = x[1]*2^(g-1) + x[2]*2^(g-2) + ... + x[g-1]*2 + x[g] -> { x[1],...,x[g] }. Conversely, a g-long sequence of bits { x1,...,xg } is converted to an integer by the rule { x[1],...,x[g] } -> x[1]*2^(g-1) + x[2]*2^(g-2) + ... + x[g-1]*2 + x[g]. Jablon [Page 23] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 Note that the first bit of a sequence corresponds to the most significant bit of the corresponding integer and the last bit to the least significant bit. Let L - 1 = n*M + b, where both b and n are integers and 0 <= b < M. Step 1. Choose an arbitrary sequence of at least 160 bits and call it SEED. Let g be the length of SEED in bits. Step 2. Let z = (M+159) DIV 160. DIV is defined as integer division. For i = 0,...,z-1 compute U[i] = SHA-1[SEED] XOR SHA-1[(SEED+1+i) mod 2^g ]. Step 3. Let U be the integer U = (U[0] + U[1]*2^160 + ... + U[z-1]*(z-1)2^160) mod 2^M. Form q from U by setting the most significant bit(the 2^(M-1) bit) and the least significant bit to 1. In terms of boolean operations, q = U OR 2^(M-1) OR 1. Note that 2^(M-1) < q < 2^M. Step 4. Use a robust primality testing algorithm to test whether q is prime [footnote 1]. If M = L-1, let p = 2q+1 and test whether p is prime. Step 5. If q is not prime, go to step 1. If M = L-1, go to step 1 if p is not prime and go to step 15 if p is prime. Step 6. Let counter = 0. Let offset = 1 + z. Step 7. For k = 0,...,n let V[k] = SHA-1[(SEED + offset + k) mod 2^g ]. Step 8. Let W be the integer W = V[0] + V[1]*2^160 + ... + V[n-1]*2^((n-1)*160) + (V[n] mod 2^b ) * 2^(n*160) and let X = W + 2^(L-1). Note that 0 <= W < 2^(L-1) and hence 2^(L-1) <= X < 2^L. Step 9. Let c = X mod 2q and set p = X - (c - 1) and, if r must be prime, let r = X DIV 2q. Note that p is congruent to 1 mod 2q. Step 10. If p < 2^(L-1), then go to step 13. Step 11. Perform a robust primality test on p, and if r must be prime, perform a robust primality test on r. Step 12. If p passes the test performed in step 11, and if r must Jablon [Page 24] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 be prime and r passes the test, go to step 15. If p passes the test and r must be prime, but r fails the test, go to step 1. Step 13. Let counter = counter + 1 and offset = offset + n + 1. Step 14. If counter <= 2^12 = 4096 go to step 1, otherwise (i.e. if counter < 4096) go to step 7. Step 15. Save the value of SEED and the value of counter for use in certifying the proper generation of p and q. B.2 Method for Verification of Primes FIPS 186-2 does not explicitly describe specific steps for verify that p and q have been generated properly. There are two somewhat obvious ways this might be done, with one being faster than the other. Both methods are described here, and both may be used to verify primes generated with either FIPS 186-2 or the extended method. B.2.1 Fast method Input: SEED, counter, p, q, and, if r must be prime, r. Perform the generation method described in FIPS 186-2 Appendix 2.2 or the extended method in A.1 above as appropriate with the following inputs and changes: Set L = the size of p, and (if extended) set M = the size of q and specify whether r must be prime. In Step 1, set the "arbitrary sequence" to the SEED value to be verified. Instead of Step 6, set counter equal to the counter value to be verified, and set offset = 1+z + counter*(n+1). (Let z = 1 when not using the extended method.) After Step 11, stop. If the Step 11 tests for the values of p, q, and (optionally) r have all passed, and these values are the same as their corresponding input values, the values are verified. Otherwise verification has failed. B.2.2 Slow method Note: This method may be very slow, by performing a lot of unnecessary searching and testing of irrelevant values, particularly in case of failure. It is described primarily to show how to perform verification using an implementation of the generation method that does not allow one to specify an initial counter. Jablon [Page 25] Internet-Draft draft-jablon-speke-02.txt October 22, 2002 Input: SEED, counter, p, q, and, if r must be prime, r Perform the generation method described in FIPS 186-2 Appendix 2.2 or the extended method in A.1 above as appropriate with the following inputs: Set L = the size of p, and (if extended) set M = the size of q and specify whether r must be prime. In Step 1, set the "arbitrary sequence" to the SEED value to be verified. Compare the resulting values of SEED, counter, p, q, and (optionally) r to the input values. If these values are the same, the values are verified. Otherwise verification has failed. Jablon [Page 26]