idnits 2.17.1 draft-newman-sasl-passdss-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-24) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. 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. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. ** The document is more than 15 pages and seems to lack a Table of Contents. == 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. ** There are 3 instances of too long lines in the document, the longest one being 1 character in excess of 72. ** The abstract seems to contain references ([SASL]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 233 has weird spacing: '... mpint p ...' == Line 234 has weird spacing: '... mpint q...' == Line 235 has weird spacing: '... mpint g...' == Line 236 has weird spacing: '... mpint y...' == Line 242 has weird spacing: '... mpint r ...' == (2 more instances...) == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords -- however, there's a paragraph with a matching beginning. Boilerplate error? (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- 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 (March 1998) is 9537 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'MSB' is mentioned on line 77, but not defined == Missing Reference: 'UTF-8' is mentioned on line 709, but not defined == Unused Reference: 'UTF8' is defined on line 800, but no explicit reference was found in the text ** Obsolete normative reference: RFC 2234 (ref. 'ABNF') (Obsoleted by RFC 4234) -- Possible downref: Non-RFC (?) normative reference: ref. 'DIFFIE-HELLMAN' -- Possible downref: Non-RFC (?) normative reference: ref. 'DSS' ** Downref: Normative reference to an Informational RFC: RFC 2104 (ref. 'HMAC') ** Downref: Normative reference to an Informational RFC: RFC 2202 (ref. 'HMAC-TEST') ** Obsolete normative reference: RFC 2060 (ref. 'IMAP4') (Obsoleted by RFC 3501) -- Possible downref: Non-RFC (?) normative reference: ref. 'Orm96' ** Obsolete normative reference: RFC 1750 (ref. 'RANDOM') (Obsoleted by RFC 4086) ** Obsolete normative reference: RFC 2222 (ref. 'SASL') (Obsoleted by RFC 4422, RFC 4752) -- Possible downref: Non-RFC (?) normative reference: ref. 'SCHNEIER' -- Possible downref: Non-RFC (?) normative reference: ref. 'SCRAM' -- Possible downref: Non-RFC (?) normative reference: ref. 'SHA1' -- Possible downref: Non-RFC (?) normative reference: ref. 'SHORT-EXP' -- Possible downref: Non-RFC (?) normative reference: ref. 'SSH-ARCH' -- Possible downref: Non-RFC (?) normative reference: ref. 'SSH-TRANS' -- Possible downref: Non-RFC (?) normative reference: ref. 'TIMING' -- Possible downref: Non-RFC (?) normative reference: ref. 'TLS' ** Obsolete normative reference: RFC 2279 (ref. 'UTF8') (Obsoleted by RFC 3629) Summary: 17 errors (**), 0 flaws (~~), 11 warnings (==), 14 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group C. Newman 3 Internet Draft: PASSDSS-3DES-1 SASL Mechanism Innosoft 4 Document: draft-newman-sasl-passdss-01.txt March 1998 5 Expires in six months 7 DSS Secured Password Authentication Mechanism 9 Status of this memo 11 This document is an Internet-Draft. Internet-Drafts are working 12 documents of the Internet Engineering Task Force (IETF), its areas, 13 and its working groups. Note that other groups may also distribute 14 working documents as Internet-Drafts. 16 Internet-Drafts are draft documents valid for a maximum of six 17 months and may be updated, replaced, or obsoleted by other 18 documents at any time. It is inappropriate to use Internet-Drafts 19 as reference material or to cite them other than as "work in 20 progress." 22 To view the entire list of current Internet-Drafts, please check 23 the "1id-abstracts.txt" listing contained in the Internet-Drafts 24 Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net 25 (Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East 26 Coast), or ftp.isi.edu (US West Coast). 28 Abstract 30 Some system administrators are faced with a choice between 31 deploying a new authentication infrastructure or sending 32 unencrypted passwords in the clear over the Internet. Deploying a 33 new authentication infrastructure often involves modifying 34 operating system services or keeping parallel authentication 35 databases up to date and is thus unacceptable to many 36 administrators. 38 Solutions which encrypt the entire session are often crippled with 39 weak keys (due to government restrictions) which are unsuitable for 40 passwords. In addition, such solutions often reduce performance of 41 the entire session to an unacceptable level. This specification 42 defines a SASL [SASL] mechanism which is compatible with existing 43 password-based authentication databases and does not require a 44 security layer for the remainder of the session. 46 [NOTE: Public discussion of this mechanism may take place on the 47 ietf-sasl@imc.org mailing list with a subscription address of 48 ietf-sasl-request@imc.org. Private comments may be sent to the 49 author]. 51 1. How to Read This Document 53 This document is intended primarily for a programmer. If 54 successful, it should be possible for a competent programmer to 55 write a client implementation using this specification, the SASL 56 [SASL] specification, an understanding of how to generate random 57 numbers [RANDOM], a description or implementation of the DES and 58 SHA1 [SHA1] algorithms and a multi-precision integer math library. 59 A cryptographic library or a copy of "Applied Cryptography" 60 [SCHNEIER] or similar reference is helpful for any implementation 61 and necessary for server DSS key generation. 63 The key words "MUST", "MUST NOT", "SHOULD", "SHOULD NOT", and "MAY" 64 in this document are to be interpreted as defined in "Key words for 65 use in RFCs to Indicate Requirement Levels" [KEYWORDS]. 67 1.1. Data Types Used in this Document 69 A list of data types used in this document follows. Note that the 70 majority of this section is copied from the secure shell 71 specification [SSH-ARCH]. 73 octet A basic 8-bit unit of data. 75 uint32 A 32-bit unsigned integer. Stored as four octets in 76 network byte order (also known as big endian or most 77 significant byte [MSB] first). For example, the decimal 78 value 699921578 (hexadecimal 29b7f4aa) is represented with 79 the hexadecimal octet sequence 29 b7 f4 aa. 81 string A string is a length-prefixed octet string. The length is 82 represented as a uint32 with the data immediately 83 following. A length of 0 indicates an empty string. The 84 string MAY contain NUL or 8-bit octets. When used to 85 represent textual strings, the characters are interpreted 86 in UTF-8 [UTF-8]. Other character encoding schemes MUST 87 NOT be used. 89 mpint Represents multiple precision integers in two's complement 90 format, stored as a string, most significant octet first. 91 Negative numbers have one in the most significant bit of 92 the first octet of the string data. If the most significant 93 bit would be set for a positive number, the number MUST be 94 preceded by a zero byte. Unnecessary leading zero or 255 95 bytes MUST NOT be included. The value zero MUST be stored 96 as a string with zero bytes of data. 98 By convention, a number that is used in modular 99 computations in the field of integers mod n SHOULD be 100 represented in the range 0 <= x < n. 102 Examples: 104 value (hex) representation (hex) 105 ----------------------------------------------------------- 106 0 00 00 00 00 107 9a378f9b2e332a7 00 00 00 08 09 a3 78 f9 b2 e3 32 a7 108 80 00 00 00 02 00 80 109 -1234 00 00 00 02 ed cc 110 -deadbeef 00 00 00 05 ff 21 52 41 11 112 1.2. Glossary 114 This section includes some acronyms used in this document. 116 DES The U.S. Government Data Encryption Standard is a symmetric 117 encryption algorithm introduced in 1975 which uses a 56 bit 118 key. The algorithm is documented in [SCHNEIER]. 120 DSA The U.S. Government Digital Signature Algorithm standard. A 121 public key signature algorithm available for unrestricted use 122 without a license. 124 DSS The U.S. Government Digital Signature Standard [DSS] which 125 employs the DSA algorithm. 127 HMAC A hash-based message authentication code [HMAC] summarized in 128 Appendix A.4. Test cases are available in [HMAC-TEST]. 130 SHA The Secure Hash Algorithm (version 1) which is part of the DSS 131 standard. 133 triple-DES 134 Use of the DES algorithm three times in an encrypt-decrypt- 135 encrypt mode with three independent keys as described in 136 appendix A.3. 138 2. Overview 140 This section includes a brief discussion of design goals, intended 141 use and an overview for this SASL mechanism. An overview of some 142 of the algorithms used is in Appendix A. 144 2.1. Design Goals 146 The ideal authentication mechanism would be simple, fast, fully 147 secure, freely distributable without restrictions and backwards 148 compatible with deployed back-end authentication databases. 149 Unfortunately, it is not possible to achieve all these goals so 150 priorities and tradeoffs are necessary. This mechanism has 151 compatibility with deployed back-end authentication databases and 152 protection from passive and active attacks on the underlying 153 connection as primary design goals. Simplicity and unrestricted 154 binary distribution are secondary design goals. 156 Backwards compatibility is achieved by using plain-text 157 passphrases. Protection from passive and active attacks is 158 achieved by using public and symmetric key technology to encrypt 159 the passphrase and optionally protect the remainder of the session. 160 Some simplicity is achieved by avoiding complicated public key 161 certification issues and formats as well as making the SASL session 162 security layer and certification by the client optional. 163 Unrestricted binary distribution is hopefully achieved by using 164 unencumbered algorithms and making the SASL privacy layer optional. 166 2.2. Intended Use 168 This is intended as a plug-and-play mechanism for services layered 169 on top of deployed passphrase-based back-end authentication 170 databases. When no security layer is implemented it can be added 171 to a SASL-based protocol without modifying or substituting network 172 read and write APIs. When the optional session privacy protection 173 is omitted, the author speculates that it may be possible to make a 174 binary implementation which would be exportable from the United 175 States. 177 For cases where simplicity, speed or unrestricted source code 178 distribution is more desirable than backwards compatibility or 179 security, a mechanism such as CRAM-MD5 [CRAM-MD5] or SCRAM [SCRAM] 180 is preferred. 182 The optional SASL integrity and privacy protection is provided as a 183 simple alternative to full service security layers such as TLS 184 [TLS] or Secure Shell [SSH-ARCH]. However, there are many 185 advantages to full service security layers such as compression, 186 faster symmetric cipher options, and the ability to leverage other 187 public key infrastructures. An implementation which supports TLS 188 may have no incentive to support SASL security layers at all. The 189 complexity verses functionality tradeoff is significant enough that 190 these mechanisms do not compete. 192 2.3. Mechanism Overview 194 The PASSDSS-3DES-1 mechanism uses three components to perform a 195 secure authentication against a legacy passphrase database. 197 In order to protect against active attacks, a DSS public key in a 198 format compatible with Secure Shell [SSH-TRANS] is used to 199 authenticate the server to the client. The client is presumed to 200 have the server's public key or a SHA-1 hash thereof stored locally 201 in a secure database. If the client is willing to risk exposure to 202 active attacks, it may skip the public key certification step 203 altogether or do a one-time initialization of its local database, 204 perhaps with user interaction. 206 In addition to the DSS public key, a Diffie-Hellman key exchange is 207 used to generate a key for encrypting the passphrase. The 208 "PASSDSS-3DES-1" variant of this mechanism uses the same fixed 209 Diffie-Hellman group used by Secure Shell's diffie-hellman-group1- 210 sha1 key exchange [SSH-TRANS]. If more groups are necessary, they 211 will be assigned to mechanism variants "PASSDSS-3DES-2" and so 212 forth. 214 Finally, the triple-DES algorithm is used to encrypt the client's 215 passphrase and send it to the server. 217 2.4. Message Format Overview 219 This section provides a quick overview of the format of the 220 messages. The formal definition of the syntax for these messages 221 is in section 6. A detailed discussion of their implementation on 222 clients and servers is in sections 3 and 4 respectively. 224 First message from client to server: 225 string azname ; the user name to login as, may be empty if 226 same as authentication name 227 string authname ; the authentication name 228 mpint X ; Diffie-Hellman parameter X 230 The challenge from server to client is as follows: 231 uint32 pklength ; length of SSH-style DSA server public key 232 string "ssh-dss" ; constant string "ssh-dss" (lower case) 233 mpint p ; DSA public key parameters 234 mpint q 235 mpint g 236 mpint y 237 mpint Y ; Diffie-Hellman parameter Y 238 OCTET ssecmask ; SASL security layers offered 239 3 OCTET sbuflen ; maximum server security layer block size 240 uint32 siglength ; length of SSH-style dss signature 241 string "ssh-dss" ; constant string "ssh-dss" (lower case) 242 mpint r ; DSA signature parameters 243 mpint s 245 The client then sends the following message encrypted with 246 triple-DES: 247 OCTET csecmask ; SASL security layer selection 248 3 OCTET cbuflen ; maximum client block size 249 string passphrase ; the user's passphrase 250 20 OCTET cli-hmac ; a client HMAC-SHA-1 signature 252 3. Client Implementation of PASSDSS-3DES-1 254 This section includes a step-by-step guide for client implementors. 255 Although section 6 contains the formal definition of the syntax and 256 is the authoritative reference in case of errors here, this section 257 should be sufficient to build a correct implementation. 259 The SASL mechanism name is "PASSDSS-3DES-1". 261 The value of n used for the Diffie-Hellman exchange is as follows 262 (represented as an unsigned hexadecimal integer): 264 FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1 265 29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD 266 EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245 267 E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED 268 EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE65381 269 FFFFFFFF FFFFFFFF. 271 When represented as an "mpint", this would have a prefix of 272 "0000008100." The value of g is 2. This group was taken from the 273 ISAKMP/Oakley specification, and was originally generated by 274 Richard Schroeppel at the University of Arizona. Properties of 275 this prime are described in [Orm96]. 277 The client begins by doing the following: 279 (A) Generate the Diffie-Hellman private value "x". This should be 280 less than (n - 1)/2. The number of bits of entropy to use in "x" 281 is an important decision, as shorter lengths will be less secure 282 and longer lengths will noticeably reduce performance. At the time 283 this was written, 192 bits of entropy [RANDOM] is probably 284 sufficient. For more information on this topic, see [SHORT-EXP]. 286 (B) Compute the Diffie-Hellman public value "X" as follows. If X 287 has a value of 0, repeat step (A). 288 x 289 X = 2 mod n 291 The client then sends the following three pieces of information to 292 the server: 294 (1) An authorization identity represented as a string. When the 295 empty string is used, this defaults to the authentication identity. 296 This is used by system administrators or proxy servers to login 297 with a different user identity. 299 (2) An authentication identity represented as a string. This is 300 the identity whose passphrase will be used. 302 (3) The "X" result from step (B) represented as an mpint. 304 The server responds by sending a message containing the following 305 information: 307 (4) An "ssh-dss" public key compatible with Secure Shell, including 308 the 32-bit length prefix in network byte order, the Secure Shell 309 string "ssh-dss" and mpints for "p", "q", "g" and "y" (see Appendix 310 A.1). 312 (5) The mpint "Y" as defined for the Diffie-Hellman key exchange 313 (see Appendix A.2). 315 (6) A single octet bit mask representing the security layers 316 available in the same format used by the KERBEROS_V4 mechanism 317 [SASL]. Bit 0 (value 1) indicates it is permissible to have no 318 security layer. Bit 1 (value 2) indicates integrity protection is 319 permissible. Bit 2 (value 4) indicates privacy protection for the 320 rest of the session is available. The remaining bits are reserved 321 for future use. 323 (7) A three octet unsigned integer in network byte order 324 representing the maximum cipher-text buffer size the server is able 325 to receive. If this is less than 32, it indicates that a SASL 326 security layer is not supported. 328 (8) A DSA signature, including a 32-bit length, the Secure Shell 329 string "ssh-dss" and mpints for "r" and "s". 331 The client then does the following: 333 (C) Verify that "Y" is between 1 and n - 1 inclusive. If "Y" is 334 outside this range, the client MUST cancel the authentication. 336 (D) Verify that the public key from step (4) belongs to the server. 337 This can be done either with a database of SSH public keys or with 338 a database of SHA1 hashes of such public keys. If the client does 339 not have a matching entry for the server or does not have a public 340 key database, it MAY skip this step although it SHOULD alert the 341 user that the connection is susceptible to active attacks if it 342 does so. It MAY also record the public key (or SHA1 hash thereof) 343 in its database with permission from the user. 345 (E) Compute the Diffie-Hellman key K as follows. It may be 346 necessary to mask timing attacks [TIMING]. 347 x 348 K = Y mod n 350 (F) Create a buffer containing data from steps (1) through (7) in 351 order immediately followed by K represented as an mpint. 353 (G) Compute the SHA1 hash of the buffer from (F). This produces a 354 20 octet result. 356 (H) If the public key from step (4) was not certified, this step 357 MAY be skipped. Otherwise, verify that the DSS signature is a 358 signature of (G). This computation is done as defined in appendix 359 A.1 where the output of step (G) represents the message "m" (note 360 that this results in SHA1 being applied twice). 362 (I) Compute the following 20-octet values. K represents the output 363 of step (E) in mpint format. H represents the output of step (G). 364 The || symbol represents string concatenation. "A" represents a 365 single octet containing the US-ASCII value of capital letter A. 366 cs-encryption-iv = SHA1( K || "A" || H ) 367 sc-encryption-iv = SHA1( K || "B" || H ) 368 cs-encryption-key-1 = SHA1( K || "C" || H ) 369 cs-encryption-key-2 = SHA1( K || cs-encryption-key-1 ) 370 cs-encryption-key = cs-encryption-key-1 || cs-encryption-key-2 371 sc-encryption-key-1 = SHA1( K || "D" || H ) 372 sc-encryption-key-2 = SHA1( K || sc-encryption-key-1 ) 373 sc-encryption-key = sc-encryption-key-1 || sc-encryption-key-2 374 cs-integrity-key = SHA1( K || "E" || H ) 375 sc-integrity-key = SHA1( K || "F" || H ) 377 (J) Create a buffer beginning with a bit mask for the selected 378 security layer (it MUST be one offered in 6) followed by three 379 octets representing the maximum cipher-text buffer size (at least 380 32) the client can accept in network byte order. This is followed 381 by a string containing the passphrase. Note that integrity 382 protection is pointless unless the public key was certified in 383 step (D) and the signature was verified in step (H). 385 (K) Create a buffer containing items (1) through (7) immediately 386 followed by the first four octets of (J). 388 (L) Compute HMAC-SHA-1 with (K) as the data and the cs-integrity- 389 key from step (I) as the key. This produces a 20 octet result. A 390 summary of the HMAC-SHA-1 algorithm [HMAC] is in appendix A.4. 392 (M) Create a buffer containing (J) followed by (L) followed by an 393 arbitrary number of zero octets as necessary to reach the block 394 size of DES and conceal the passphrase length from an eavesdropper. 396 (N) Apply the triple-DES algorithm to (M) with the first 8 octets 397 of cs-encryption-iv from step (I) as the initialization vector and 398 the first 24 octets of cs-encryption-key as the key. If optional 399 privacy protection is negotiated on, the triple-DES state is not 400 reset. 402 The client then sends a message to the server containing the 403 following: 405 (9) The output of step (N). 407 If a SASL security layer is negotiated on, the following steps are 408 used when sending a message: 410 (O) Create a buffer containing a uint32 client packet number 411 (starting from 0) immediately followed by the cs-integrity-key from 412 step (I). 414 (P) Compute HMAC-SHA-1 with (O) as the key and the data to transmit 415 as the data. 417 (Q) Create a buffer containing the data to transmit followed by the 418 20-octet output of (P). If privacy was negotiated on, this is 419 followed by zero to seven padding octets followed by one more octet 420 indicating the number of padding octets. The total size MUST be a 421 multiple of the DES block size. 423 (R) The result of step (Q) is encrypted with triple-DES if privacy 424 was negotiated and is sent prefixed by a uint32 length, as required 425 by SASL. 427 If a SASL security layer was negotiated on, the following steps are 428 taken when receiving a message: 430 (S) If privacy was negotiated on, the message is decrypted using 431 triple-DES with the first 24 octets of sc-encryption-key as the 432 key. The value of the last octet plus one indicates the number of 433 octets to ignore at the end of the output. The sc-encryption-iv is 434 used to initialize triple-DES state the first time this is done. 436 (T) Create a buffer containing a uint32 server packet number 437 (starting from 0) immediately followed by the sc-integrity-key. 439 (U) Compute HMAC-SHA-1 with (T) as the key over the portion of the 440 data excluding the 20 octet signature and any encryption padding. 441 If this is the same as the 20 octet signature, then the data is not 442 corrupted. 444 4. Server Implementation of PASSDSS-3DES-1 446 The section includes a step-by-step guide for server implementors. 447 It is intended to be read in conjunction with section 3. 449 The server MUST have a persistent DSS-SSH public key. Mechanisms 450 for generating such keys are described in [SCHNEIER] and [DSS]. 452 IMPORTANT NOTE: The server MUST be able to process any message from 453 the client, including messages of any size, messages with invalid 454 content and messages with NULs in the middle of strings. When 455 input is illegal, the server MUST gracefully reject authentication 456 or in extreme cases gracefully terminate the connection. 457 Particular care to avoid buffer overruns is important if the user 458 name or passphrase strings are copied. 460 The server performs the following computations prior to or during 461 the connection by the client: 463 (a) Select a random number k less than (p - 1)/2. It is important 464 to generate a good random number [RANDOM]. 466 (b) Compute signature component "r" as follows: 467 k 468 r = (g mod p) mod q 470 (c) Optionally pre-compute the group inverse of k, mod q and the 471 value xr. 473 (d) Select a random Diffie-Hellman private key y less than (n - 474 1)/2. Follow the same guidance as in (A) above. 476 (e) Compute the Diffie-Hellman public value Y as follows. If Y has 477 a value of 0, repeat step (d) above. 478 y 479 Y = 2 mod n 481 (f) Verify that the value X from the client is between 1 and (n - 482 1). If it isn't, fail the authentication. 484 (g) Compute the Diffie-Hellman shared key K as follows. It may be 485 necessary to mask timing attacks [TIMING]. 486 y 487 K = X mod n 489 (h) Create a buffer containing items (1) through (7) above followed 490 by K represented as an mpint. 492 (i) Compute the SHA-1 hash of the buffer from (h). This produces a 493 20 octet result. 495 (j) Generate a DSS signature of (i). The signature is made up of 496 "r" from step (b) and the result following computation (partially 497 completed in step c): 498 -1 499 s = (k (SHA1(h) + xr)) mod q 501 (k) Create a buffer containing items (4) through (8) and send it to 502 the client. 504 (l) Perform the computations as described in step (I) where K is 505 the result of step (g) in mpint format and H is the result of step 506 (i). 508 (m) Decrypt message (9) from the client using triple-DES with cs- 509 encryption-iv as the initialization vector and the first 24 octets 510 of cs-encryption-key as the key. 512 (n) Verify the passphrase from the output of step (m) against the 513 authentication database. Fail the authentication if verification 514 fails. 516 (o) Verify that the selected security layer is permitted and the 517 cipher text buffer size is at least 32. If not, fail the 518 authentication. 520 (p) Create a buffer containing steps (1) through (7) followed by 521 the first four octets of the result from (m). 523 (q) Compute the HMAC-SHA-1 of (p) with cs-integrity-key as the key. 525 This produces a 20-octet result. 527 (r) Compare the output of (q) with the 20 octet signature after the 528 passphrase in the output of (m). If they don't match, fail the 529 authentication. 531 If a SASL security layer is negotiated on, sending and receiving 532 procedures are similar to steps (O)-(U), with client and server 533 roles exchanged (and thus sc-* values and cs-* value exchanged). 534 Note that triple-DES state from step (m) is not reset. 536 5. Example 538 The following is an example of the PASSDSS-3DES-1 mechanism using 539 the IMAP [IMAP4] profile of SASL. Note that base64 encoding and 540 the lack of an initial client response with the first command are 541 characteristics of the IMAP profile of SASL and not characteristics 542 of SASL or this mechanism. 544 In this example, "C:" represents lines sent from the client to the 545 server and "S:" represents lines sent from the server to the 546 client. The wrapped lines are for editorial clarity -- there are 547 no actual newlines in the middle of the messages. 549 C: a001 AUTHENTICATE PASSDSS-3DES-1 550 S: + 551 C: AAAAAAAAAAVjaHJpcwAAAIEAhuVbMxdLxrAQVyUWbAp+X09h6QmZ2Jebz 552 H7YhtcbQyLbB9AGi1eIdojZYtAuVeE+PYkKUANLHI9XzWSFliIGMeUvBc 553 bflHr+s9tZ5/5YZh9blb33km3tUYVKyB5XP530bDn+lY1lAv6tXHKZPrx 554 b0zPhc+JGgpWGlmT5k9vx2Wk= 555 S: + AAAA8gAAAAdzc2gtZHNzAAAAQQDPVlO6nFefrq6fA/dQKIoNj75Jjpp 556 kVv3DkyILABCox2dMql0bnO48rHFuo167y6oukT/ocKupIw6bgKmdofgd 557 AAAAFQDRpB6FrxemUGRuLjY/oiH/Qef14QAAAEEAkVr9rOlB58k5XoqmP 558 NYTrVGZKWbCPcYtaL92ANxgWyjyRo49+m0+fHPNhNibQoLddEZF8lHPKW 559 gb7z7qz0QMdgAAAEARcIEiMz5jTZo8COf2njL3BTWRND5NGAgZY7s1YOm 560 2BfjVyf1/MkOiQMiXeonrsfMc0sWQGgpRYRtJWpe56cc2AAAAgQDoV5Uk 561 bcy3Gjf16MZwPLlJlvmjpSNv2dSSApoddd4+BgZr01zyt7hzb0yRruaN5 562 fG43DbJLkk7mtL1Hw8aYXBMQQzrPpHtx+anpCDoN2jlersCGFY2cnjxTf 563 HqY139ohA8vVXYpapeXxKXR4//Ib/ApTGmwlOeIikKDrBmEGX/JgEAAAA 564 AAAA8AAAAB3NzaC1kc3MAAAAVAI7j3HG8HyjCOxaGFOUTwZqe0xSHAAAA 565 FHSqU41vPHTCRTqmxNFwXqazPlJH 566 C: Obp6vQ83q1O/OnQDifZB1rWOci9LaSck8VxNB4UAFhRI56BAs4XPLqOWI 567 CoB3LYZ 568 S: a001 OK Authentication Completed 570 The following private values were used in this example. These 571 values are all represented as an mpint in hexadecimal (msb first). 573 The client private Diffie-Hellman "x" value: 575 00000018 666E35B4 3BF4BF2B 40E31359 7A5D3AD0 61FD4F6F 736A6114 577 The server private Diffie-Hellman "y" value: 579 00000018 587BDFD6 800D101C 8E82E233 3B5A07AA DB87B8F1 68DC194D 581 The Diffie-Hellman shared secret: 583 00000080 3B46D3A8 D2163930 1C33D9FE EAFA528D F4B881CF DF906A03 584 33249A88 42547FF6 49FDC149 1A5084B1 B425A105 CE571283 AC61D896 585 AF8F7AF7 F95643F3 00A91E57 BCB8CFD7 77A25CBD 35F59A9E 59E98BEA 586 EA866339 7F0F9AA0 2F0F335C 8C6AAFF7 76BDB668 DF4D51AF 5B4FB807 587 81A70901 F478FB86 BF42055C BAF46094 EC72E98A 589 The DSA private key value (the public key is in the exchange): 591 00000014 252BCBFA 5634D706 6ED43128 972E181E 66BF9C30 593 The SHA-1 hash value used to compute the keys: 595 26 75 97 06 EB FE E3 69 C9 03 7D 49 64 19 D5 D2 97 66 E8 CE 597 6. Formal Syntax of PASSDSS-3DES-1 Messages 599 This is the formal syntactic definition of the client and server 600 messages. This uses ABNF [ABNF] notation including the core rules. 601 The first three rules define the formal exchange. The later rules 602 define the elements of the exchange. 604 client-msg-1 = [azname] authname diffie-hellman-X 606 server-msg-1 = dss-public-key diffie-hellman-Y 607 ssecmask sbuflen dss-signature 609 client-msg-2 = client-blob 611 authname = string 612 ;; interpreted as UTF-8 [UTF-8] 614 azname = string 615 ;; interpreted as UTF-8 [UTF-8] 617 cbuflen = 3OCTET 618 ;; Big endian binary unsigned integer 619 ;; max length of client read buffer 621 cli-hmac = 20OCTET 623 client-blob = 8*OCTET 624 ;; encrypted version of client-encrypted 626 client-encrypted = csecmask cbuflen passphrase cli-hmac *NUL 627 ;; MUST be multiple of DES block size 629 csecmask = OCTET 630 ;; client selected protection layer 632 diffie-hellman-X = mpint 634 diffie-hellman-Y = mpint 636 dss-g = mpint 638 dss-p = mpint 640 dss-public-key = length NUL NUL NUL %x07 "ssh-dss" 641 dss-p dss-q dss-g dss-y 642 ;; length is total length of remainder 643 ;; as defined in [SSH-TRANS] 645 dss-q = mpint 647 dss-r = mpint 649 dss-signature = length NUL NUL NUL %x07 "ssh-dss" 650 dss-r dss-s 651 ;; length is total length of remainder 653 dss-s = mpint 655 dss-y = mpint 657 length = 4OCTET 658 ;; binary number, big endian format (MSB first) 660 mpint = length *OCTET 661 ;; length specifies number of octets 662 ;; see section 1 for detailed mpint definition 664 passphrase = string 665 ;; At least 64 octets MUST be supported 667 sbuflen = 3OCTET 668 ;; Big endian binary unsigned integer 669 ;; max length of server read buffer 671 ssecmask = OCTET 672 ;; server protection layer mask 674 string = length *OCTET 675 ;; the length determines the number of octets 676 ;; OCTETs are interpreted as UTF-8 678 NUL = %x00 ;; US-ASCII NUL character 680 7. Security Considerations 682 Security considerations are discussed throughout this memo. 684 This mechanism supplies the server with the plain-text passphrase, 685 so the server gains the ability to masquerade as the user to any 686 other services which share the same passphrase. 688 If the public key certification step is skipped, then an active 689 attacker can gain the client's passphrase and thus the ability to 690 masquerade as the user to any other services which share the same 691 passphrase. Negotiating a security layer will fail to provide 692 protection from an active attacker in this case. 694 If no security layer is negotiated, the rest of the protocol 695 session is subject to active and passive attacks. 697 If an integrity-only layer is negotiated, the rest of the protocol 698 is subject to passive eavesdropping. 700 The quality of this mechanism depends on the quality of the random 701 number generator used. See [RANDOM] for more information. 703 8. Multinational Considerations 705 As remote access is a crucial service, users are encouraged to 706 restrict user names and passphrases to the US-ASCII character set. 707 However, if characters outside the US-ASCII character set are used 708 in user names and passphrases, then they are interpreted according 709 to UTF-8 [UTF-8] and it is a protocol error to include any octet 710 sequences not legal for UTF-8. Servers are encouraged to enforce 711 this restriction to discourage clients from using non-interoperable 712 local character sets in this context. 714 9. Intellectual Property Issues and Acknowledgments 716 David Kravitz holds U.S. Patent #5,231,668 on the DSA algorithm. 717 NIST has made this patent available world-wide on a royalty-free 718 basis. 720 Diffie-Hellman was first published in 1976 [DIFFIE-HELLMAN]. U.S. 721 Patent #4,200,770 granted April 1980 has expired. Canada Patent 722 #1,121,480 was granted April 6, 1982 and may still apply at this 723 time. 725 DES is covered under U.S. Patent #3,962,539 granted June 1978, 726 which has expired. 728 The majority of the constructions in this specification were copied 729 from the Secure Shell specifications [SSH-ARCH, SSH-TRANS]. 730 Additional information is paraphrased from "Applied Cryptography" 731 [SCHNEIER]. 733 10. References 735 [ABNF] Crocker, Overell, "Augmented BNF for Syntax Specifications: 736 ABNF", RFC 2234, Internet Mail Consortium, Demon Internet Ltd, 737 November 1997. 739 [CRAM-MD5] Klensin, Catoe, Krumviede, "IMAP/POP AUTHorize Extension 740 for Simple Challenge/Response", RFC 2195, MCI, September 1997. 742 [DIFFIE-HELLMAN] Diffie, W., Hellman, M.E., "Privacy and 743 Authentication: An introduction to Cryptography," Proceedings of 744 the IEEE, v. 67, n. 3, March 1979, pp. 397-427. 746 [DSS] National Institute of Standards and Technology, "Digital 747 Signature Standard," NIST FIPS PUB 186, U.S. Department of 748 Commerce, May 1994. 750 [HMAC] Krawczyk, Bellare, Canetti, "HMAC: Keyed-Hashing for Message 751 Authentication", RFC 2104, IBM, UCSD, February 1997. 753 [HMAC-TEST] Cheng, Glenn, "Test Cases for HMAC-MD5 and HMAC-SHA-1", 754 RFC 2202, IBM, NIST, September 1997. 756 [IMAP4] Crispin, M., "Internet Message Access Protocol - Version 757 4rev1", RFC 2060, University of Washington, December 1996. 759 [KEYWORDS] Bradner, "Key words for use in RFCs to Indicate 760 Requirement Levels", RFC 2119, Harvard University, March 1997. 762 [Orm96] Orman, H., "The Oakley Key Determination Protocol", version 763 1, TR97-92, Department of Computer Science Technical Report, 764 University of Arizona. 766 [RANDOM] Eastlake, Crocker, Schiller, "Randomness Recommendations 767 for Security", RFC 1750, DEC, Cybercash, MIT, December 1994. 769 [SASL] Myers, "Simple Authentication and Security Layer (SASL)", 770 RFC 2222, Netscape Communications, October 1997. 772 [SCHNEIER] Schneier, B., "Applied Cryptography: Protocols, 773 Algorithms and Source Code in C," John Wiley and Sons, Inc., 1996. 775 [SCRAM] Newman, "Salted Challenge Response Authentication Mechanism 776 (SCRAM)", work in progress, January 1998. 778 [SHA1] NIST FIPS PUB 180-1, "Secure Hash Standard," National 779 Institute of Standards and Technology, U.S. Department of Commerce, 780 April 1995. 782 [SHORT-EXP] van Oorschot, P., Wiener, M., "On Diffie-Hellman Key 783 Agreement with Short Exponents", Advances in Cryptography -- 784 EUROCRYPT Springer-Verlag, ISBN 3-540-61186-X, pp. 332-343. 786 [SSH-ARCH] Ylonen, Kivinen, Saarinen, "SSH Protocol Architecture", 787 Work in progress, SSH, October 1997. 789 [SSH-TRANS] Ylonen, Kivinen, Saarinen, "SSH Transport Layer 790 Protocol", Work in progress, SSH, October 1997. 792 [TIMING] Kocher, P., "Timing Attacks on Implementations of Diffie- 793 Hellman, RSA, DSS and Other Systems", Advances in Cryptography -- 794 CRYPTO '96 Proceedings, Lecture Notes in Computer Science, Vol 795 1109, Springer-Verlag, ISBN 3-540-61512-1, pp. 104-113. 797 [TLS] Dierks, Allen, "The TLS Protocol Version 1.0", Work in 798 progress. 800 [UTF8] Yergeau, "UTF-8, a transformation format of ISO 10646", 801 RFC 2279, Alis Technologies, January 1998. 803 11. Author's Address 805 Chris Newman 806 Innosoft International, Inc. 807 1050 Lakes Drive 808 West Covina, CA 91790 USA 810 Email: chris.newman@innosoft.com 812 Appendix A. Algorithm Overview 814 This section provides a quick overview of the algorithms used. For 815 a full understanding, the reader is encouraged to read "Applied 816 Cryptography" [SCHNEIER]. The follow descriptions are paraphrased 817 from that source. 819 Note that an overview of the DES algorithm is not included as 820 publicly available implementations and descriptions are very 821 common. 823 Appendix A.1. DSA Algorithm 825 The DSA algorithm is a public key algorithm which can be used to 826 sign messages such that the source can be verified using a public 827 key. The algorithm has the following parameters: 829 p is a prime number L bits long. Implementations MUST support L 830 between 512 and 1024 bits. 832 q is a 160-bit prime factor of (p - 1). 834 (p - 1)/q 835 g = h mod p where h is any number less than p - 1 such 837 (p - 1)/q 838 that h is greater than 1. 840 x is a number less than q and represents the private key. 842 x 843 y = g mod p and represents the public key. 845 To sign a message m, the client generates a random number k less 846 than q and computes: 848 k 849 r = (g mod p) mod q 850 -1 851 s = (k (SHA1(m) + xr)) mod q 853 The signature is represented as r and s, and is verified as 854 follows: 856 -1 857 w = s mod q 859 u1 = (SHA1(m) * w) mod q 861 u2 = (rw) mod q 863 u1 u2 864 v = ((g * y ) mod p) mod q 866 If v = r then the signature is verified. 868 Appendix A.2. Diffie-Hellman Algorithm 870 The Diffie-Hellman algorithm is a key-exchange algorithm. It 871 allows two ends of a communications channel to establish a shared 872 secret which a passive eavesdropper can not easily determine. This 873 key can then be used in a symmetric algorithm such as triple-DES. 874 The two ends have a prior agreement on two numbers: 876 n a large prime number 878 g a primitive mod n. 880 The client chooses a random large integer x and computes: 882 x 883 X = g mod n 885 and sends X to the server. The server chooses a random large 886 integer y and computes: 888 y 889 Y = g mod n 891 y 892 K = X mod n 894 The server sends Y to the client. The client computes: 896 x 897 K = Y mod n 899 At this point, the client and server share the same secret K. 901 Appendix A.3. Triple-DES Algorithm in EDE/outer-CBC Mode 903 The DES algorithm uses an 8 octet (64 bit) key of which 56 bits are 904 significant. The triple-DES EDE algorithm uses a 24 octet (192 905 bit) key of which roughly 112 bits are significant see [SCHNEIER] 906 for more details. The "EDE" refers to encrypt-decrypt-encrypt, and 907 the "CBC" refers to cipher-block-chaining where each cipher block 908 affects future cipher blocks. If E() is the DES encryption 909 function, D() is the DES decryption function, C is a cipher text 910 block and P is a plain-text block, then triple-DES EDE in CBC mode 911 with outer chaining is: 913 C = E (D (E (P XOR C ))) 914 i K3 K2 K1 i i-1 916 NOTE: C is the initialization vector 917 0 919 and the decryption function is: 921 P = C XOR D (E (D (C ))) 922 i i-1 K3 K2 K1 i 924 K1 is the first 8 octets of the triple-DES key, K2 is the second 8 925 octets and K3 is the final 8 octets. 927 Appendix A.4. HMAC-SHA-1 Keyed hash function 929 HMAC-SHA-1 uses the SHA-1 hash function to create a keyed hash 930 function suitable for use as an integrity protection function. A 931 more complete description is in [HMAC]. A brief summary of the 932 algorithm follows: 934 (A) If the key is longer than 64 octets, it is run through the 935 SHA-1 function to produce a 20 octet key. 937 (B) The key is exclusive-ored with a 64 octet buffer filled with 938 the octet value 0x36. 940 (C) SHA-1 is computed over (B) followed by the input text. 942 (D) The key is exclusive-ored with a 64 octet buffer filled with 943 the octet value 0x5C. 945 (E) SHA-1 is computed over (D) followed by the output of (C).