idnits 2.17.1 draft-jablon-speke-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 981: '... The client MUST abort authenticatio...' RFC 2119 keyword, line 984: '... The host MUST abort the authenticat...' RFC 2119 keyword, line 997: '...ey do not match, the server MUST abort...' RFC 2119 keyword, line 1004: '...ctly, the server MUST respond with its...' Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 1176 has weird spacing: '... robust prima...' == Line 1179 has weird spacing: '...ses the test,...' == Line 1180 has weird spacing: '..., go to step ...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (October 22, 2003) is 7492 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: '0' on line 1164 == Missing Reference: 'N-1' is mentioned on line 362, but not defined -- Looks like a reference, but probably isn't: '1' on line 1164 == Missing Reference: 'RFC2412' is mentioned on line 633, but not defined -- Looks like a reference, but probably isn't: '2' on line 1124 -- Looks like a reference, but probably isn't: '4' on line 1043 -- Looks like a reference, but probably isn't: '3' on line 1044 -- Looks like a reference, but probably isn't: '5' on line 1044 -- Looks like a reference, but probably isn't: '19' on line 1054 == Missing Reference: 'RFC 1321' is mentioned on line 1066, but not defined == Missing Reference: 'RFC 2104' is mentioned on line 1067, but not defined == Missing Reference: 'FIPS186-2' is mentioned on line 1080, but not defined == Missing Reference: 'SEED' is mentioned on line 1139, but not defined == Unused Reference: 'RFC1321' is defined on line 839, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'BM90' -- Possible downref: Non-RFC (?) normative reference: ref. 'BM92' -- Possible downref: Non-RFC (?) normative reference: ref. 'FIPS 186-2' -- Possible downref: Non-RFC (?) normative reference: ref. 'IEEE 1363' -- Possible downref: Non-RFC (?) normative reference: ref. 'Jab96' -- Possible downref: Non-RFC (?) normative reference: ref. 'Jab97' -- Possible downref: Non-RFC (?) normative reference: ref. 'Jas96' ** Obsolete normative reference: RFC 1510 (Obsoleted by RFC 4120, RFC 6649) -- Possible downref: Non-RFC (?) normative reference: ref. 'MacK01b' -- Possible downref: Non-RFC (?) normative reference: ref. 'PK99' ** Downref: Normative reference to an Informational RFC: RFC 1321 ** Downref: Normative reference to an Informational RFC: RFC 1704 ** Downref: Normative reference to an Informational RFC: RFC 1760 ** Obsolete normative reference: RFC 2095 (Obsoleted by RFC 2195) ** Downref: Normative reference to an Informational RFC: RFC 2104 -- Possible downref: Non-RFC (?) normative reference: ref. 'SHA1' -- Possible downref: Non-RFC (?) normative reference: ref. 'Wu98' -- Possible downref: Non-RFC (?) normative reference: ref. 'ZKPPLinks' Summary: 12 errors (**), 0 flaws (~~), 12 warnings (==), 21 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group D. Jablon 2 Internet Draft Phoenix Technologies 3 draft-jablon-speke-02.txt October 22, 2003 5 The SPEKE Password-Based Key Agreement Methods 7 Status of this Memo 9 This document is an Internet-Draft and is subject to all provisions 10 of Section 10 of RFC2026. 12 Internet-Drafts are draft documents valid for a maximum of six months 13 and may be updated, replaced, or obsoleted by other documents at any 14 time. It is inappropriate to use Internet-Drafts as reference 15 material or to cite them other than as "work in progress." 17 The list of current Internet-Drafts can be accessed at 18 http://www.ietf.org/ietf/1id-abstracts.txt 20 The list of Internet-Draft Shadow Directories can be accessed at 21 http://www.ietf.org/shadow.html. 23 Abstract 25 This document describes the SPEKE, B-SPEKE, and W-SPEKE methods 26 for password-based key agreement and authentication. In the same 27 category of techniques as EKE and SRP, these methods provide a zero- 28 knowledge password proof and authenticate session keys over an 29 unprotected channel, with minimal dependency on infrastructure and 30 proper user behavior. These methods are compatible with IEEE 1363 31 and ANSI X9 standards and provide important options for convenient 32 and secure personal authentication. 34 Table of Contents 36 Status of this Memo .............................................. 1 37 Abstract ......................................................... 1 38 1. Introduction .................................................. 3 39 2. Background .................................................... 3 40 2.1 Summary of Features and Benefits ......................... 4 41 2.3 Origin ................................................... 5 42 3. Description ................................................... 6 43 3.1. Notation, Conventions, and Terminology ................... 6 44 3.1.1 Parameters .......................................... 6 45 3.1.2 Notation ............................................ 6 46 3.1.3 Data Formats and Conversion ......................... 7 47 3.1.4 Bits and Bytes ...................................... 7 48 3.2 General Construction ..................................... 7 49 3.2.1 Enrollment .......................................... 8 50 3.2.2 Identification ...................................... 8 51 3.2.3 Key Exchange ........................................ 9 52 3.2.4 Secret Value Derivation ............................. 9 53 3.2.5 Key Derivation ...................................... 10 54 3.2.6 Key Confirmation .................................... 10 55 3.3 Message Ordering ......................................... 11 56 3.4 Compatibility with RFC 2945 .............................. 11 57 4. Method Selection and Application Notes ....................... 11 58 4.1 W-SPEKE, B-SPEKE, and SRP ................................ 12 59 4.2 Balanced vs. Augmented Methods ........................... 12 60 4.3 B-SPEKE vs. W-SPEKE ...................................... 13 61 4.4 Parameter Selection ...................................... 13 62 4.5 Compatibility with Other Standards ....................... 14 63 4.6 Other Key Derivation and Hash Functions .................. 14 64 4.6.1 Security Note ....................................... 15 65 4.7 Key Confirmation Functions ............................... 15 66 4.8 Salt ..................................................... 15 67 4.9 Iterated Hashing ......................................... 16 68 5. Security Considerations ....................................... 16 69 6. Intellectual Property Notice .................................. 16 70 References ....................................................... 17 71 Author's Address ................................................. 19 72 Full Copyright Statement ......................................... 19 73 Acknowledgements ................................................. 19 74 Appendix A: An APKAS-WSPEKE mechanism ............................ 20 75 A.1. Interleaved SHA ......................................... 22 76 A.2. Other Hash Algorithms ................................... 22 77 Appendix B: Extended FIPS 186-2 Prime Generation and Verification..23 78 B.1 Extended Method for Generation of Primes .................. 23 79 B.2 Method for Verification of Primes ......................... 25 80 B.2.1 Fast method .......................................... 25 81 B.2.2 Slow method .......................................... 25 83 1. Introduction 85 This document describes SPEKE, B-SPEKE, and W-SPEKE, three methods 86 that provide cryptographically strong password-based key agreement 87 and network authentication. These methods are in the same category 88 as the earlier EKE [BM92] and later SRP [RFC2945] methods, but use 89 some different techniques. Some advantages of these methods over SRP 90 are slightly increased security and compatibility with IEEE 1363 and 91 ANSI X9 cryptography standards. An appendix highlights changes that 92 can be made to an RFC 2945-compliant application or standard to use 93 these as alternatives. Other documents may adapt these methods for 94 specific applications. 96 Section 2 describes background and rationale for this class of 97 method, where they were developed, what they do, and why. Section 3 98 describes the SPEKE methods in detail, and section 4 discusses method 99 selection, parameter selectio, and other application issues. Two 100 potentially relevant patents are listed in Section 6. 102 2. Background 104 Convenient and secure personal authentication is important for many 105 Internet applications. People want their passwords to be easy to 106 remember and type, and also secure. But most earlier password 107 systems offer insufficient protection against passive and active 108 network attack on passwords. While complex public key based 109 infrastructures have evolved, they often still rely on a password as 110 the human link. 112 Some older systems fail by treating passwords as cryptographic keys, 113 without any real ability to insure appropriate cryptographic quality 114 for these values. As such, they provide the option for either 115 security or convenience, but not both at the same time. Purely hash- 116 based "challenge-response" techniques as described in [RFC2095] and 117 [RFC1760], and various forms of Kerberos initial authentication 118 [RFC1510], were designed to defeat simple sniffing attacks, but 119 unfortunately use the password directly as a message authentication 120 key, and can thus be compromised by exhaustive guessing or dictionary 121 attack by one who obtains protocol messages [BM90]. Passwords often 122 need to be simple, easy-to-remember, and easy-to-type, which means 123 that they cannot safely be used like traditional encryption keys. 125 Still other systems try to protect transmitted passwords by relying 126 on a separate security infrastructure. The password-thru-SSL 127 approach as commonly used in web browsing is vulnerable to spoofing 128 attacks. These are not the result of weak cryptography, but rather, 129 due to the generally weak concept of giving away a password to prove 130 knowledge of it. In so-called "tunnelled" protocols, the password 131 may flow through a authenticated channel in which the sole act of 132 server authentication is ignored or bypassed by a typical user. When 133 people must authenticate the server, but don't, their passwords are 134 at risk. 136 Old methods for proving knowledge of a secret force disclosure of the 137 secret from the prover to the verifier during each act. Such 138 practices should be discouraged where non-disclosing zero-knowledge 139 methods are available. 141 Strong password methods, including SPEKE, were first discovered in 142 the 1990's. They use ephemeral public key techniques to securely 143 bind people to keys, using a small or not-so-random password, and 144 perform a zero-knowledge password proof (ZKPP), where each party 145 proves to the other that it knows the password without revealing it 146 to any party that doesn't already know it. These methods also 147 negotiate a mutually authenticated session key between the parties 148 based on knowledge of the password. This can happen over an 149 unprotected network, without revealing the password or keys to 150 attackers, requiring no certificates, no long-term sensitive data at 151 the client, and minimal demands on the user. 153 These benefits are attractive for providing secure and convenient 154 personal authentication. While these methods work with passwords 155 alone, they are also used to provide secure mobility and credential 156 provisioning in systems that use additional secret key or public key 157 infrastructure. Security is improved by reducing assumptions on 158 proper user behavior and reducing dependencies on security 159 infrastructure. 161 SPEKE and other zero-knowledge password methods have been deployed in 162 both academic and commercial settings. SRP has been described in 163 [RFC2944] and [RFC2945], and referenced in several Internet Drafts. 164 These methods are also described in the proposed IEEE standard for 165 password-based public key cryptography [P1363.2]. 167 2.1 Summary of Features and Benefits 169 SPEKE, B-SPEKE and W-SPEKE all perform mutual authentication and key 170 agreement across an untrusted network while protecting passwords 171 and negotiated authenticated keys. These methods do not send any 172 passwords or password-crackable data over the network; Instead they 173 integrate the password into a standard Diffie-Hellman exchange in a 174 way that negotiates a mutually authenticated key. 176 Even with a password that is too small to serve as a cryptographic 177 key, these methods prevent passive and active network attacks (man- 178 in-the-middle, replay, etc.), as well as password-sniffing and 179 unconstrained brute force attack from the network. These methods 180 surpass the requirements in [RFC1704] for non-disclosing 181 authentication protocols. Because both acts of user and server 182 authentication are based on a common credential, and a step that the 183 user can't forget to do, these methods are superior to tunnelled 184 methods in common applications. ZKPP techniques prevent unnecessary 185 password disclosures whether or not the authentication succeeds, 186 defending against both simple accidents (typing the wrong password) 187 and malicious attacks (interception by a spoofed or compromised 188 server). 190 The methods are as efficient as a Diffie-Hellman key exchange (DH) 191 computation, using any standard groups. The incorporation of DH 192 provides the benefits of forward secrecy and so-called "backward 193 secrecy", which are important for robust password changing protocols 194 [Jas96] and for strong key management in general. 196 These methods include both balanced and augmented password-based key 197 agreement methods. SPEKE is a balanced method, in that both parties 198 share identical password-derived data. B-SPEKE and W-SPEKE are 199 augmented methods, typically used in client/server applications, in 200 which a server stores password verification data derived from a one- 201 way function of the client's password. A thief that steals augmented 202 password verification data from a server cannot use it to pose as the 203 user in the protocol, without first "cracking" the password. W-SPEKE 204 is comparable to SRP, with differences in structure, benefits, and 205 limitations as described in section 4.2 and Appendix A. 207 Two of these methods are compatible with standard Diffie-Hellman as 208 described in [IEEE 1363] and [ANSI X9.42], and are also aligned with 209 the emerging IEEE [P1363.2] standard for password-based cryptography 210 (see section 4.5). Implementation requires little more than a hash 211 function and big integer modular exponentiation. Use of alternative 212 settings, such as elliptic curve groups [ANSI X9.63], is beyond the 213 scope of this document. 215 Methods in this class are particularly valuable for bootstrapping 216 applications, where an initial act of personal authentication 217 authorizes the download, transmission, or remote verification of 218 private keys, certificates, and other sensitive configuration data. 219 Personal key retrieval, so-called roaming applications, and general 220 provisioning of keys are all ideal applications in both wired and 221 wireless settings. Continued proliferation of ad-hoc password systems 222 still remains a large problem on the Internet -- SPEKE and other 223 zero-knowledge password methods provide an appropriate foundation for 224 future consolidation and replacement of such ad-hoc systems. 226 2.2 Origin 228 SPEKE stands for "Simple Password-authenticated Exponential Key 229 Exchange", and was first published in [Jab96]. It has been reviewed, 230 cited, and/or studied in many subsequent papers including [Jab97] and 231 [MacK01b], and has been commercially deployed. SPEKE is a "balanced" 232 method, where two parties share an identical password-derived value 233 that is used to derive and mutually authenticate a Diffie-Hellman 234 key. 236 B-SPEKE, first published in [Jab97], is an augmented method, where 237 the server's password verification data cannot be used directly by 238 the client. 240 W-SPEKE is an augmented method that has similarities to both B-SPEKE 241 and SRP [Wu98]. W-SPEKE was described as "SRP-4" in an earlier 242 Internet draft and a submission to IEEE P1363. 244 A brief comparison of some of these methods is in section 4.3, and 245 lists of research papers are available in [P1363.2] and [ZKPPLinks]. 247 3. Description 249 This section describes the SPEKE, B-SPEKE, and W-SPEKE password- 250 authenticated key agreement methods. It begins with preliminary 251 notation, conventions, and terminology in subsection 3.1, followed by 252 a combined description of all three methods in 3.2. 254 3.1. Notation, Conventions, and Terminology 256 This section describes the system parameters, notation, and data 257 format conversion functions used in these methods. The parameter 258 notation is similar to RFC 2945, and the function names are aligned 259 with IEEE 1363. 261 3.1.1 Parameters 263 The methods described here use multiplicative groups of integers, 264 parameterized with the following values and functions: 266 N field modulus, a suitable 1024-bit prime of the form kq + 1 267 q prime order of the subgroup to be used, larger than 2^159 268 k the "co-factor", k=N-1/q. It is recommended that all 269 divisors of k/2 other than 1 be larger than q. 270 hash SHA-1, or an alternate suitable hash function 271 kdf KDF1-SHA1, as defined in [IEEE 1363], or an alternate 272 suitable key derivation function 274 Selection of suitable values is discussed in section 4.4. 276 3.1.2 Notation 278 In these descriptions, the | symbol denotes concatenation of byte 279 strings. All hash functions operate on and produce byte strings. 281 The * and + operators denote integer multiplication and addition. 282 The ^ and % operators denote integer exponentiation and the integer 283 modular remainder operation. 285 The / operator denotes integer division. 287 The := operator denotes either a definition of a term or the function 288 of assigning a value to a variable. 290 Note also that variables may be bracketed with '<' and '>' in the 291 text for readability, but the brackets are often omitted in 292 equations; Unambiguous uses of x and refer to the same thing. 294 "DH" stands for "Diffie-Hellman". "DL" refers to the so-called 295 discrete logarithm setting that uses a multiplicative group of 296 integers. ("EC" would refer to the elliptic curve setting.) 298 SHA1() refers to the SHA-1 Secure Hash Algorithm, as defined in 299 [SHA1]. is a hash function used to process passwords. is 300 a key derivation function used to derive authenticated keys. 302 SHA1 may be used for both and , although other suitable 303 standard hash and key derivation functions are acceptable. 305 3.1.3 Data Formats and Conversion 307 The functions in this description are defined to operate on either 308 byte strings or on unsigned big integers, with an implied standard 309 conversion between these types of values. The necessary conversion 310 functions are specified in this section. 312 The conversion functions used are OS2IP and FE2OSP as defined in 313 [IEEE 1363]. OS2IP converts a byte string (or "octet string") into a 314 non-negative integer, where the first byte represents the most 315 significant 8 bits, presuming unsigned big-endian format. FE2OSP 316 converts a field element into a big-endian byte string, where high 317 zero bytes are added as needed to make the length equal to the number 318 of significant bytes in the field modulus N. A field element is a 319 big integer in the range [0,N-1], with no sign bit used in the 320 encoding. 322 For example, the computation "hash(x)^k % N" implies that the big 323 integer value x is converted to a byte string before being hashed, 324 and the hash output is converted from a byte string to a big integer 325 prior to the modular exponentiation. Thus, a long way to describe 326 this step is "OS2FEP(hash(FE2OSP(x)))^k % N". 328 3.1.4 Bits and Bytes 330 Bit strings in this document (such as the input and output of hash 331 functions) are always a multiple of 8 bits in length, and are treated 332 as byte strings. The high bit of a bit string is treated as the 333 high-bit of the first byte of the corresponding byte string. Thus, 334 the input to SHA1 is a byte string of arbitrary length less than 2^56 335 bytes, and the 160-bit output is treated as a big-endian 20-byte 336 string. 338 3.2 General Construction 340 This section describes the general construction of SPEKE, B-SPEKE and 341 W-SPEKE. 343 When used in a client/server application, the authentication server 344 must have access to a password repository (database or file) which 345 associates a username or similar identifier with password 346 verification data, and, optionally, a salt value. 348 For SPEKE, password verification data can be any arbitrary byte 349 string (designated as ) that preserves the randomness of the 350 password and is available to both client and server. 352 The parties must agree on which method to use, including domain 353 parameters, hash, key derivation, and key confirmation functions. 354 These values may be fixed in the implementation of the client and 355 server. The parties must also initially agree on a password, and how 356 they do that is beyond the scope of this document. 358 3.2.1 Enrollment 360 During enrollment of the user's credentials with a server, the 361 password value x is hashed and converted to a value that serves 362 as password verification data. is in the range [1,N-1]. For 363 B-SPEKE and W-SPEKE, the server's password verification data is a 364 specially constructed pair of values {,}. 366 SPEKE server stores: { , [, ] } 367 B-SPEKE/W-SPEKE server stores: { , , [, ] } 369 The value is of order . is a standard DH public key 370 corresponding to a base raised to the power of password-derived 371 DH private key . These methods also require that cannot be 372 derivable from , which is enforced using a hash function to 373 compute from . These values are defined as follows: 375 p := the password or other potentially small authenticator string 376 x := any suitable derivation of

that preserves its randomness 377 g := REDP(x), "REDP" is a random element derivation function 378 v := g^x % N (only used in B-SPEKE and W-SPEKE) 380 Two suitable REDP functions [P1363.2] are: 382 REDP-1(x) = hash(x)^k % N 383 REDP-2(x) = (ga * gb^hash(x)) % N 384 ga = REDP-1("Alice") 385 gb = REDP-2("Bob") 387 and are two arbitrary elements of order q that have no 388 known exponential relationship to each other. 390 3.2.2 Identification 392 To start the login process, the client typically sends a user name or 393 identifier to the server, after which the server retrieves the stored 394 value of , and optionally and/or values that have been 395 associated with the user's password. The server sends back any 396 optional . 398 Client Server 400 ---------------> 401 get {g [,v] [,salt]} from storage 402 <------------------- [] 404 3.2.3 Key Exchange 406 The client computes and from the user's password and 407 (optionally) the server-supplied or other parameters. 408 Alternately, in a peer-to-peer application using SPEKE, both parties 409 may compute directly from the shared password. 411 The client generates a secret random number in the range [1,q-1], 412 computes the remainder of raising to the power modulo the 413 field prime , and sends the result to the server. 415 The server generates a secret random number in the range [1,q-1], 416 computes the remainder of raising to the power modulo the 417 field prime , and sends the result to the client. 419 Client Server 421 a := random integer 422 A := g^a % N 423 A ------------------------> 424 b := random integer 425 B := g^b % N 426 <-------------------------- B 428 In the DL setting where equals 2 or 2r and where all divisors of 429 r other than 1 are greater than q, the value of or is defined 430 to be unacceptable if it is not in the range [2,-2] inclusive. 431 When is an unacceptable value, the client must abort before 432 revealing any information derived from . When is an 433 unacceptable value, the server must abort before revealing any 434 information derived from . 436 In general, for any DH group, acceptable values of and are 437 those that generate a suitably large set of possible values for , 438 to preclude enumeration of the possible results by an attacker. 440 3.2.4 Secret Value Derivation 442 When a received value is valid, each party computes a secret byte 443 string based on the appropriate computation as shown here: 445 Client Server 447 For SPEKE: 448 S := B^a % N S := A^b % N 450 For BSPEKE: 451 S := (B^a % N) | (B^x % N) S := (A^b % N) | (v^b % N) 453 For WSPEKE: 454 u := hash(B) / (2^128) u := hash(B) / (2^128) 455 S := B^(a + u*x) % N S := (A * v^u)^b % N 457 If the client has used the password that corresponds to the server's 458 verification data, authentication is successful and both parties will 459 share the same value for . 461 3.2.5 Key Derivation 463 At this point, both parties can derive a set of one or more keys 464 { K_1, K_2, ... } from the (hopefully) shared secret using an 465 appropriate key derivation function. Any set of prefix-free distinct 466 derivation parameters can be used to derive a set of distinct derived 467 keys. (See security note in 4.6.1.) 469 K_i := kdf(S, ) 471 Note that none of these keys can be determined by any third- 472 party observer of and , and no second party can negotiate a 473 matching without using the correct password data. Derived keys 474 are useful for various purposes, such as for proving knowledge of 475 in key confirmation, and for use in generating secure session keys. 477 3.2.6 Key Confirmation 479 To complete the act of explicit mutual authentication, both parties 480 prove to each other that their shared secret values are 481 identical. They can use a key confirmation function (KCF) to derive 482 a unique parameterized key from , send the KCF output key to the 483 other party, after which each party verifies the other's correct 484 computation. 486 One specific construction compatible with [P1363.2] also incorporates 487 other shared secret and public values as shown here. The client and 488 server agree that the client will send KCF(), and the 489 server will send KCF(kcfParam2). 491 Client Server 493 K_1 := kcf() K_1 := kcf() 494 K_1 -----------------------> verify K_1 496 K_2 := kcf() K_2 := kcf() 497 verify K_2 <------------------------ K_2 499 := hex byte 04 500 := hex byte 03 501 := KCF1-SHA1 503 KCF1-SHA1() := SHA1( | A | B | S | g) 505 The server computes its value for K_1 as a hash of its concatentated 506 values for , A, B, S, and g, and then it compares its K_1 507 value to the value of K_1 received from the client. If they are not 508 equal, the server must abort and signal an error. The client 509 performs the analogous procedure for verifying the server's K_2. 511 3.3 Message Ordering 513 The message flows in these key agreement protocols do not necessarily 514 have a one-to-one correspondence with application protocol messages. 515 There are no special security constraints on message flows, so that 516 they may be generally combined and arranged in any order that permits 517 necessary computation and interoperability. 519 3.4 Compatibility with RFC 2945 521 In RFC 2945, is of order (N-1), but here is of order . 523 For close alignment with RFC 2945, one can use the following specific 524 definitions: 526 p := the raw password byte string 527 username := byte string identifying the user 528 salt := a random byte string stored on the server 529 x := SHA1( | SHA1( | ":" |

) ) 531 The value is a 32-bit unsigned integer equal to the high-order 32 532 bits of SHA1(B), and is compatible with RFC 2945. 534 The "Interleaved SHA1" key derivation function in RFC 2945 is not 535 compatible with KDF1-SHA1 or other KDFs defined in [IEEE 1363]. 537 4. Method Selection and Application Notes 539 SPEKE, B-SPEKE, and W-SPEKE are three similar but distinct methods. 540 The general benefits of these and other zero-knowledge password 541 methods over earlier techniques is reviewed in section 2. This 542 section compares these and some other methods in the same category, 543 and discusses issues to consider in choosing a specific method, 544 selecting system parameters and primitive functions, and related 545 application notes. 547 Flexibility may be desirable, as people have different opinions and 548 relative priorities for efficiency, compatibility, security, and 549 licensing concerns in a variety of applications. This section 550 discusses technical criteria for selecting one method over another. 551 Business issues may also be relevant, but are beyond the scope of 552 this document. 554 4.1 W-SPEKE, B-SPEKE, and SRP 556 W-SPEKE may be described as a variant of B-SPEKE that uses an 557 optimized exponential computation from SRP. W-SPEKE may also be seen 558 as a variant of SRP with the following differences: 560 * Derives generator from password, instead of =2. 561 * Removes the +v and -v steps associated with . 562 * is of order , instead of order N-1. 563 * Host stores , along with and . 564 * Modified test for unacceptable A and B. 566 The resulting limitations & benefits are: 568 SRP W-SPEKE, B-SPEKE 569 -------------------------------- -------------------------------- 570 Restrictions on message order No restrictions on message order 571 Not aligned with IEEE/ANSI May use IEEE/ANSI DH primitives 572 Two guesses per run [MacK01b] One guess per run 574 B-SPEKE has somewhat increased computation over W-SPEKE and an added 575 password verification value stored on the server as compared to 576 SRP. 578 See also Appendix A for a description of a form of W-SPEKE in the 579 style of RFC 2945. Other changes between RFC 2945 and this document 580 include additional background material and clarifications in 581 presentation and safety recommendations. 583 SRP and W-SPEKE use an additional security parameter in the 584 construction of , that is not present B-SPEKE (or SPEKE), which 585 may merit additional study for some applications. 587 4.2 Balanced vs. Augmented Methods 589 All of the SPEKE methods provide a strong basic level of protection 590 against network attack for passwords and their authenticated keys. 591 The augmented methods W-SPEKE and B-SPEKE provide the added benefit 592 over SPEKE of permitting the host to store passwords in a form that 593 is not directly useful to an attacker. In an augmented system, even 594 if the host's password database is stolen, the thief still needs to 595 perform a successful guessing attack to determine the password in 596 order to login. In either case, however, servers are still required 597 to maintain secure storage of password verification data. References 598 that discuss relative value of augmented methods are [Wu98], [Jab97], 599 and [PK99], the latter providing reasons why the augmented benefit 600 may not be necessary for key-retrieval applications. 602 SPEKE is the simplest, most efficient, and by some measures the most 603 widely studied of the three. These advantages warrant its use in 604 applications that cannot obtain significant extra benefit from an 605 augmented method. It may also be preferred for client/server 606 applications where the server cannot control the format of password 607 verification data -- for example, where the server has access to 608 clear-text passwords or passwords transformed with a legacy one-way 609 function. 611 4.3 B-SPEKE vs. W-SPEKE 613 W-SPEKE and B-SPEKE are both augmented methods that may provide an 614 added benefit in client/server applications. W-SPEKE combines the 615 benefits of B-SPEKE with the computational efficiency boost of an 616 optimized computation similar to that used in SRP. A factor that 617 might favor B-SPEKE over W-SPEKE is conformance with IEEE 1363 and 618 ANSI DH standards. 620 4.4 Parameter Selection 622 This specification requires that the modulus is, in general, any 623 modulus that is suitable for a Diffie-Hellman key exchange. 624 A suitable is prime, defines a suitably large subgroup of prime 625 order q (for compliance with standard DH in [IEEE 1363] and [ANSI 626 X9.42]), and allows group elements to be checked for membership in a 627 small subgroup. If there are any divisors of /2 other than 1, it 628 is recommended that they be larger than q. 630 The modulus must also be one in which the parties can trust has not 631 been specially crafted to provide advantages for an attacker. 632 Construction methods and examples of verifiable primes suitable for 633 SPEKE are defined in [RFC2412] and in [FIPS 186-2] Appendix 2. 635 The random secret exponents and have length and quality 636 constraints similar to any Diffie-Hellman exchange. A common 637 acceleration trick for DH, that applies here too, is to choose 638 and from a range [1,t], where is much smaller than , but 639 still sufficiently large. The general rule is for t to have enough 640 bits to avoid a brute-force attack of order 2^(t/2). A typical value 641 is t = 2^160 to preclude known attacks using 2^80 operations. Such 642 security issues are discussed in [IEEE 1363]. This document 643 recommends that and each contain at least 160 random bits. 645 For the value in W-SPEKE, implementors may choose to increase the 646 length, as long as both client and server agree, but in general this 647 document recommends that it not be shorter than 32 bits. This value 648 limits a thief who steals and (but hasn't cracked the 649 password) to having no more than a 1 in 2^32 chance of being 650 successful in a single run with a lucky random guess. 652 4.5 Compatibility with Other Standards 654 Compatibility and alignment with other existing standards promotes 655 re-use of implementation components. Even when strict compatibility 656 cannot be achieved, re-use of standard settings, primitives, and 657 related functions may still encourage implementation compatibility 658 and help provide assurance of security. 660 These methods are aligned with the BPKAS-SPEKE, APKAS-BSPEKE, and 661 APKAS-WSPEKE schemes as described in the IEEE proposed standard for 662 password-based public key cryptography [P1363.2]. 664 These methods are also compatible with the settings, schemes, and 665 primitives defined for Diffie-Hellman in [IEEE 1363] and the related 666 [ANSI X9.42] and [ANSI X9.63] equivalents. SPEKE, B-SPEKE and W- 667 SPEKE in the DL and EC settings are compatible with the 1363 668 EC/DLSVDP-DH primitives, and SPEKE and B-SPEKE are furthermore 669 compatible with the EC/DLKAS-DH1 and EC/DLKAS-DH2 schemes. 671 This document further shows where W-SPEKE is aligned with RFC 2945 672 and where such alignment conflicts with other standards. It 673 maximizes consistency with RFC 2945, and the various Internet Drafts 674 and other documents that reference it, to facilitate "drop-in" 675 replacement of these methods for SRP. 677 4.6 Other Key Derivation and Hash Functions 679 Standard DH1 and DH2 key agreement [IEEE 1363] specifies that the 680 negotiated shared-secret field elements be converted to fixed-length 681 byte strings using FE2OSP, and then processed through a standard key 682 derivation function. Examples using KDF1-SHA1 are shown here: 684 SPEKE: K_i = SHA1( FE2OSP(A^b % N) | ) 685 BSPEKE: K_i = SHA1( FE2OSP(A^b % N) | FE2OSP(v^b % N) | 686 ) 688 This document permits the key derivation function to be any suitable 689 standard function, such as KDF1-SHA1, or other non-standard yet 690 suitable functions, such as SHA_Interleave ([RFC2945] and Appendix 691 A). Although SHA Interleave is not the preferred choice, we know of 692 no security concern with it. However, although this function 693 attempts to preserve up to 320 bits of entropy in , we note that 694 the effective entropy in is also limited by the entropy in 695 and . 697 Another well-studied alternative is the HMAC-SHA1 function [RFC2104] 698 which is useful for deriving the keyed message authentication codes 699 used in key confirmation. 701 Any of these methods can be used with suitable alternative hash 702 functions other than SHA-1, such as SHA-256, RIPEMD, and HMAC 703 constructions. 705 4.6.1 Security Note 707 To securely use any standard key derivation function, it is important 708 that key derivation parameters be prefix-free, that is, no string 709 should be a prefix substring of any other (as in "p1", "p2", ... 710 "p10"). Using KDF1 with same-fixed-length strings or a length- 711 containing encoding such as ASN.1 BER or DER is suggested (see [IEEE 712 1363], D.5.1.4). 714 4.7 Key Confirmation Functions 716 Alternate key confirmation functions may be desired in different 717 applications. For example RFC 2945 describes acceptable functions 718 for key confirmation (also shown in Appendix A) that are not 719 compatible with KCF1. 721 Note that the protocol messages prior to key confirmation, such as 722 the user name, are not integrity-protected, and as such parties must 723 not rely on these values for security-sensitive purposes. Including 724 party identifiers in the key derivation parameter of a key 725 confirmation message is one way to prevent identity confusion 726 attacks. 728 Many application security protocols include all previously shared 729 messages as key derivation parameters in a key confirmation messages, 730 just to be sure. 732 4.8 Salt 734 The purpose of salt is to frustrate an attacker who may plan to build 735 a generic dictionary of password verification data that corresponds 736 to a set of likely passwords. Such a dictionary could assist a 737 database thief who steals or in a mass-cracking attack. Salt 738 forces such a dictionary to be built on a case-by-case basis. 739 To be effective, salt must be incorporated into both and in 740 the augmented methods W-SPEKE and B-SPEKE. 742 Note that W-SPEKE incorporates salt in the computation of , 743 whereas in SRP3, salt is incorporated at a later stage. This may 744 affect consolidated forms of a server-salted protocol (see Appendix 745 A). 747 In applications where the client sends before contacting 748 the server, a server-supplied salt cannot be incorporated into . 749 In such applications, one might alternately use a self-salting 750 technique, such as by incorporating the username or servername in 751 . 753 4.9 Iterated Hashing 755 Using an iterated hash function in combination with any of these 756 protocols can increase the required cracking effort for stolen 757 password verification data. For example, one may use: 759

:= hash(hash(... hash() ...)) 760 ... for perhaps thousands of iterations 762 However, in any case, security of the server password database 763 remains a primary way to prevent unconstrained attack, whereas salt 764 and iterated hashing are secondary backup defensive measures. 766 5. Security Considerations 768 Security considerations are discussed throughout this document, 769 including parameter selection, relevant cryptographic research, and 770 comparison of these to other methods. 772 6. Intellectual Property Notice 774 Phoenix Technologies Ltd. and Stanford University own patents that 775 describe the SPEKE and SRP methods respectively. For more 776 information, including contact information for resolving questions, 777 readers are referred to the IPR statements available at 778 http://www.ietf.org/ipr.html. 780 References 782 [ANSI X9.42] ANSI X9.42-2001, "Public Key Cryptography for the 783 Financial Services Industry: Agreement of Symmetric Keys 784 Using Discrete Logarithm Cryptography", ANSI, 2001. 786 [ANSI X9.63] ANSI X9.63-2001, "Public Key Cryptography for the 787 Financial Services Industry, Key Agreement and Key 788 Transport Using Elliptic Curve Cryptography", ANSI, 789 2001. 791 [BM90] Bellovin, S., and M. Merritt, "Limitations of the 792 Kerberos Authentication System", ACM Computer 793 Communications Review, October 1990. 795 [BM92] Bellovin, S., and M. Merritt, "Encrypted Key Exchange: 796 Password-Based Protocols Secure Against Dictionary 797 Attacks", Proceedings of the I.E.E.E. Symposium on 798 Research in Security and Privacy, Oakland, May 1992. 800 [FIPS 186-2] FIPS 186-2, Digital Signature Standard, NIST. 802 [IEEE 1363] IEEE Std 1363-2000, "IEEE Standard Specifications for 803 Public-Key Cryptography 2000", IEEE, 2000. 805 [Jab96] Jablon, D., "Strong Password-Only Authenticated Key 806 Exchange", Computer Communication Review, ACM SIGCOMM, 807 vol. 26, no. 5, pp. 5-26, October 1996. 809 [Jab97] Jablon, D., "Extended Password Key Exchange Protocols 810 Immune to Dictionary Attacks", Proceedings of the Sixth 811 Workshops on Enabling Technologies: Infrastructure for 812 Collaborative Enterprises (WET-ICE '97), IEEE Computer 813 Society, June 18-20, 1997, Cambridge, MA, pp. 248-255. 815 [Jas96] B. Jaspan, Dual-workfactor Encrypted Key Exchange: 816 Efficiently Preventing Password Chaining and Dictionary 817 Attacks, Proceedings of the Sixth Annual USENIX Security 818 Conference, July 1996, pp. 43-50. 820 [RFC1510] Kohl, J., and C. Neuman, "The Kerberos Network 821 Authentication Service (V5)", RFC 1510, Digital 822 Equipment Corporation, USC/Information Sciences 823 Institute, September 1993. 825 [MacK01b] MacKenzie, P., "On the Security of the SPEKE Password- 826 Authenticated Key Exchange Protocol", Cryptology ePrint 827 Archive: Report 2001/057, 828 . 830 [P1363.2] IEEE P1363.2, "Standard Specifications for Public-Key 831 Cryptography: Password-Based Techniques", (work in 832 progress), IEEE, . 834 [PK99] Perlman, R. and C. Kaufman, "Secure Password-Based 835 Protocol for Downloading a Private Key", Proceedings of 836 the 1999 Network and Distributed System Security, 837 February 3-5, 1999. 839 [RFC1321] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 840 1321, April 1992. 842 [RFC1704] Haller, N. and R. Atkinson, "On Internet 843 Authentication", RFC 1704, October 1994. 845 [RFC1760] Haller, N., "The S/Key One-Time Password System", RFC 846 1760, Feburary 1995. 848 [RFC2095] Klensin, J., Catoe, R. and P. Krumviede, "IMAP/POP 849 AUTHorize Extension for Simple Challenge/Response", RFC 850 2095, January 1997. 852 [RFC2104] Krawczyk, H., Bellare, M. and R. Canetti, "HMAC: Keyed- 853 Hashing for Message Authentication", RFC 2104, February 854 1997. 856 [RFC2944] T. Wu, "Telnet Authentication: SRP", RFC 2944, September 857 2000. 859 [RFC2945] T. Wu, "The SRP Authentication and Key Exchange System", 860 RFC 2945, September 2000. 862 [SHA1] National Institute of Standards and Technology (NIST), 863 "Announcing the Secure Hash Standard", FIPS 180-1, U.S. 864 Department of Commerce, April 1995. 866 [Wu98] T. Wu, "The Secure Remote Password Protocol", In 867 Proceedings of the 1998 Internet Society Symposium on 868 Network and Distributed Systems Security, San Diego, CA, 869 pp. 97-111. 871 [ZKPPLinks] "Research Papers on Strong Password Authentication", 872 . 874 Author's Address 876 David Jablon 877 Phoenix Technologies Ltd. 878 320 Norwood Park South 879 Norwood, MA 02062 881 EMail: david_jablon at phoenix.com 883 Full Copyright Statement 885 Copyright (C) The Internet Society (2002). All Rights Reserved. 887 This document and translations of it may be copied and furnished to 888 others, and derivative works that comment on or otherwise explain it 889 or assist in its implementation may be prepared, copied, published 890 and distributed, in whole or in part, without restriction of any 891 kind, provided that the above copyright notice and this paragraph are 892 included on all such copies and derivative works. However, this 893 document itself may not be modified in any way, such as by removing 894 the copyright notice or references to the Internet Society or other 895 Internet organizations, except as needed for the purpose of 896 developing Internet standards in which case the procedures for 897 copyrights defined in the Internet Standards process must be 898 followed, or as required to translate it into languages other than 899 English. 901 The limited permissions granted above are perpetual and will not be 902 revoked by the Internet Society or its successors or assigns. 904 This document and the information contained herein is provided on an 905 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 906 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 907 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 908 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 909 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 911 Acknowledgements 913 The author thanks Paul Funk, Nora Hanley, Jim Walker, and Tom Wu for 914 their review and thoughtful comments on earlier drafts. This 915 document includes significant material derived from RFC 2945. The 916 author is also grateful for the encouragement and advice from Steve 917 Bellovin and Michael Wiener during the initial refinement of these 918 methods. 920 Appendix A: An APKAS-WSPEKE mechanism 921 ------------------------------------- 923 This section describes a form of APKAS-WSPEKE employing SHA-1 to 924 authenticate users and generate session keys. This text is revised 925 from section 3 of RFC 2945 (SRP), and is suitable for "diff"ing. 927 The host stores user passwords as quartets of the form 929 { , , , } 931 Password entries are generated as follows: 933 = random() 934 x = SHA( | SHA( | ":" | )) 935 = g = SHA(x)^2 % N 936 = v = g^x % N 938 The | symbol indicates string concatenation, the ^ operator is the 939 exponentiation operation, and the % operator is the integer remainder 940 operation. Most implementations perform the exponentiation and 941 remainder in a single stage to avoid generating unwieldy intermediate 942 results. Note that the 160-bit output of SHA is implicitly converted 943 to an integer before it is operated upon. 945 Authentication is generally initiated by the client. 947 Client Host 948 -------- ------ 949 U = --> 950 <-- s = 952 Upon identifying himself to the host, the client will receive the 953 salt stored on the host under his username. 955 a = random() 956 x = SHA(s | SHA(U | ":" | p)) 957 g = SHA(x)^2 % N 958 A = g^a % N --> 959 g = 960 v = 961 b = random() 962 <-- B = g^b % N 963 p = 965 S = B ^ (a + u * x) % N S = (A * v^u) ^ b % N 966 K = SHA_Interleave(S) K = SHA_Interleave(S) 967 (this function is described 968 in section A.1) 970 The client generates a random number a, computes x and g from the 971 password, raises g to the power of random number a and reduces it 972 modulo the field prime, and sends the result to the host. The host 973 generates a random number b, raises g to the power of random number 974 b and reduces it modulo the field prime, and sends the result to the 975 client. Both sides then construct the shared session key based on 976 the respective formulae. 978 The parameter u is a 32-bit unsigned integer which takes its value 979 from the first 32 bits of the SHA1 hash of B, MSB first. 981 The client MUST abort authentication if B is less than 2 or greater 982 than N-2. 984 The host MUST abort the authentication attempt if A is less than 2 985 or greater than N-2. 987 At this point, the client and server should have a common session key 988 that is secure (i.e. not known to an outside party). To finish 989 authentication, they must prove to each other that their keys are 990 identical. 992 M = H(H(N) XOR H(g) | H(U) | s | A | B | K) 993 --> 994 <-- H(A | M | K) 996 The server will calculate M using its own K and compare it against 997 the client's response. If they do not match, the server MUST abort 998 and signal an error before it attempts to answer the client's 999 challenge. 1001 If the server receives a correct response, it issues its own proof to 1002 the client. The client will compute the expected response using its 1003 own K to verify the authenticity of the server. If the client 1004 responded correctly, the server MUST respond with its hash value. 1006 The transactions in this protocol description do not necessarily have 1007 a one-to-one correspondence with actual protocol messages. This 1008 description is only intended to illustrate the relationships between 1009 the different parameters and how they are computed. It is possible, 1010 for example, for an implementation of the APKAS-WSPEKE-SHA1 mechanism 1011 to consolidate some of the flows as follows: 1013 Client Host 1014 -------- ------ 1015 U --> 1016 <-- s, B 1017 A, H(H(N) XOR H(g) | H(U) | s | A | B | K) 1018 --> 1019 <-- H(A | M | K) 1021 (Note: In RFC 2945, A is sent along with U. This consolidated 1022 W-SPEKE protocol sends A after receiving s, as A is derived from s.) 1023 The value of N used in this protocol must be agreed upon by the 1024 two parties in question. It can be set in advance, or the host 1025 can supply it to the client. In the latter case, the host should 1026 send N in the first message along with the salt. For 1027 maximum security, N should be a safe prime (i.e. a number of the form 1028 N = 2q + 1, where q is also prime), chosen in a random manner, and 1029 the client must have a means of assuring the suitability of N. 1030 Also, note that g is a generator of the group of order q, 1031 which means that for any element X in the group of order q, 1032 there exists a value x in the range [1,q] for which g^x % N == X. 1034 A.1. Interleaved SHA 1036 The SHA_Interleave function used in WSPEKE-SHA1 is used to generate a 1037 session key that is twice as long as the 160-bit output of SHA1. To 1038 compute this function, remove all leading zero bytes from the input. 1039 If the length of the resulting string is odd, also remove the first 1040 byte. Call the resulting string T. Extract the even-numbered bytes 1041 into a string E and the odd-numbered bytes into a string F, i.e. 1043 E = T[0] | T[2] | T[4] | ... 1044 F = T[1] | T[3] | T[5] | ... 1046 Both E and F should be exactly half the length of T. Hash each one 1047 with regular SHA1, i.e. 1049 G = SHA(E) 1050 H = SHA(F) 1052 Interleave the two hashes back together to form the output, i.e. 1054 result = G[0] | H[0] | G[1] | H[1] | ... | G[19] | H[19] 1056 The result will be 40 bytes (320 bits) long. 1058 A.2. Other Hash Algorithms 1060 W-SPEKE can be used with hash functions other than SHA. If the hash 1061 function produces an output of a different length than SHA (20 1062 bytes), it may change the length of some of the messages in the 1063 protocol, but the fundamental operation will be unaffected. 1065 Earlier versions of the SRP mechanism used the MD5 hash function, 1066 described in [RFC 1321]. Keyed hash transforms are also recommended 1067 for use with SRP; one possible construction uses HMAC [RFC 2104], 1068 using K to key the hash in each direction instead of concatenating it 1069 with the other parameters. 1071 Any hash function used with SRP should produce an output of at least 1072 16 bytes and have the property that small changes in the input cause 1073 significant nonlinear changes in the output. [Wu98] covers these 1074 issues in more depth. 1076 Appendix B: Extended FIPS 186-2 Prime Generation and Verification 1077 ----------------------------------------------------------------- 1079 This section describes an extension of the method to generate 1080 "kosherized" primes for DSA, as described in [FIPS186-2]. The FIPS 1081 method could be used to generate primes of the form p=2qr+1, but it 1082 was limited to 1024 bit p with 160 bit subgroup order q. This 1083 extended method can generate larger p's and q's, and supports 1084 explicit options for requiring that r be prime, or r = 1, which are 1085 all useful for Diffie-Hellman, SPEKE, and related methods. The 1086 option for prime r is fully compatible with the standard in that all 1087 primes p,q of suitable size generated by this method can be verified 1088 by any compliant implementation of FIPS 186-2. 1090 B.1 Extended Method for Generation of Primes 1092 This method generates primes, p and q, satisfying the following three 1093 or four conditions: 1095 a. 2^(M-1) < q < 2^M for a specified M (e.g. M = 224) 1097 b. 2^(L-1) < p < 2^L for a specified L (e.g. L = 2048) 1099 c. q divides p - 1. 1101 d. (optionally) r is prime, where r = (p-1)/(2q). 1103 This method is a compatible extension of the DSA prime generation 1104 method specified in FIPS 186-2 Appendix 2.2. It is extended to 1105 generate values for q that are larger than 160 bits, to generate 1106 primes where p = 2q+1, and with the option to require that r is 1107 prime. 1109 This prime generation scheme starts by using the SHA-1 and a user 1110 supplied SEED to construct a prime, q, in the range 2^(M-1) < q< 2^M. 1111 Once this is accomplished, the same SEED value is used to construct 1112 an X in the range 2^(L-1) < X < 2^L. The prime, p, is then formed by 1113 rounding X to a number congruent to 1 mod 2q as described below. 1115 An integer x in the range 0 <= x < 2g may be converted to a g-long 1116 sequence of bits by using its binary expansion as shown below: 1118 x = x[1]*2^(g-1) + x[2]*2^(g-2) + ... + x[g-1]*2 + x[g] 1119 -> { x[1],...,x[g] }. 1121 Conversely, a g-long sequence of bits { x1,...,xg } is converted to 1122 an integer by the rule 1124 { x[1],...,x[g] } -> x[1]*2^(g-1) + x[2]*2^(g-2) + ... + 1125 x[g-1]*2 + x[g]. 1127 Note that the first bit of a sequence corresponds to the most 1128 significant bit of the corresponding integer and the last bit to the 1129 least significant bit. 1131 Let L - 1 = n*M + b, where both b and n are integers and 0 <= b < M. 1133 Step 1. Choose an arbitrary sequence of at least 160 bits and call 1134 it SEED. Let g be the length of SEED in bits. 1136 Step 2. Let z = (M+159) DIV 160. DIV is defined as integer 1137 division. For i = 0,...,z-1 compute 1139 U[i] = SHA-1[SEED] XOR SHA-1[(SEED+1+i) mod 2^g ]. 1141 Step 3. Let U be the integer 1143 U = (U[0] + U[1]*2^160 + ... + U[z-1]*(z-1)2^160) mod 2^M. 1145 Form q from U by setting the most significant bit(the 2^(M-1) 1146 bit) and the least significant bit to 1. In terms of boolean 1147 operations, q = U OR 2^(M-1) OR 1. Note that 2^(M-1) < q < 2^M. 1149 Step 4. Use a robust primality testing algorithm to test whether q 1150 is prime [footnote 1]. If M = L-1, let p = 2q+1 and test 1151 whether p is prime. 1153 Step 5. If q is not prime, go to step 1. If M = L-1, go to step 1 1154 if p is not prime and go to step 15 if p is prime. 1156 Step 6. Let counter = 0. Let offset = 1 + z. 1158 Step 7. For k = 0,...,n let 1160 V[k] = SHA-1[(SEED + offset + k) mod 2^g ]. 1162 Step 8. Let W be the integer 1164 W = V[0] + V[1]*2^160 + ... + V[n-1]*2^((n-1)*160) + 1165 (V[n] mod 2^b ) * 2^(n*160) 1167 and let X = W + 2^(L-1). Note that 0 <= W < 2^(L-1) and hence 1168 2^(L-1) <= X < 2^L. 1170 Step 9. Let c = X mod 2q and set p = X - (c - 1) and, if r must be 1171 prime, let r = X DIV 2q. Note that p is congruent to 1 mod 2q. 1173 Step 10. If p < 2^(L-1), then go to step 13. 1175 Step 11. Perform a robust primality test on p, and if r must be 1176 prime, perform a robust primality test on r. 1178 Step 12. If p passes the test performed in step 11, and if r must 1179 be prime and r passes the test, go to step 15. If p passes the 1180 test and r must be prime, but r fails the test, go to step 1. 1182 Step 13. Let counter = counter + 1 and offset = offset + n + 1. 1184 Step 14. If counter <= 2^12 = 4096 go to step 1, otherwise 1185 (i.e. if counter < 4096) go to step 7. 1187 Step 15. Save the value of SEED and the value of counter for use 1188 in certifying the proper generation of p and q. 1190 B.2 Method for Verification of Primes 1192 FIPS 186-2 does not explicitly describe specific steps for verify 1193 that p and q have been generated properly. There are two somewhat 1194 obvious ways this might be done, with one being faster than the 1195 other. Both methods are described here, and both may be used to 1196 verify primes generated with either FIPS 186-2 or the extended 1197 method. 1199 B.2.1 Fast method 1201 Input: SEED, counter, p, q, and, if r must be prime, r. 1203 Perform the generation method described in FIPS 186-2 Appendix 2.2 or 1204 the extended method in A.1 above as appropriate with the following 1205 inputs and changes: 1207 Set L = the size of p, and (if extended) set M = the size of q and 1208 specify whether r must be prime. 1210 In Step 1, set the "arbitrary sequence" to the SEED value to be 1211 verified. 1213 Instead of Step 6, set counter equal to the counter value to be 1214 verified, and set offset = 1+z + counter*(n+1). (Let z = 1 when 1215 not using the extended method.) 1217 After Step 11, stop. 1219 If the Step 11 tests for the values of p, q, and (optionally) r have 1220 all passed, and these values are the same as their corresponding 1221 input values, the values are verified. Otherwise verification has 1222 failed. 1224 B.2.2 Slow method 1226 Note: This method may be very slow, by performing a lot of 1227 unnecessary searching and testing of irrelevant values, particularly 1228 in case of failure. It is described primarily to show how to perform 1229 verification using an implementation of the generation method that 1230 does not allow one to specify an initial counter. 1232 Input: SEED, counter, p, q, and, if r must be prime, r 1234 Perform the generation method described in FIPS 186-2 Appendix 2.2 or 1235 the extended method in A.1 above as appropriate with the following 1236 inputs: 1238 Set L = the size of p, and (if extended) set M = the size of q and 1239 specify whether r must be prime. 1241 In Step 1, set the "arbitrary sequence" to the SEED value to be 1242 verified. 1244 Compare the resulting values of SEED, counter, p, q, and (optionally) 1245 r to the input values. If these values are the same, the values are 1246 verified. Otherwise verification has failed.