1 2 3 4 5 6 7 8 9 10INTERNET DRAFT K. Raeburn 11Kerberos Working Group MIT 12Document: draft-ietf-krb-wg-crypto-03.txt February 24, 2003 13 expires August 24, 2003 14 15 Encryption and Checksum Specifications 16 for Kerberos 5 17 18Abstract 19 20 This document describes a framework for defining encryption and 21 checksum mechanisms for use with the Kerberos protocol [Kerb], 22 defining an abstraction layer between the Kerberos protocol and 23 related protocols, and the actual mechanisms themselves. Several 24 mechanisms are also defined in this document. Some are taken from 25 RFC 1510, modified in form to fit this new framework, and 26 occasionally modified in content when the old specification was 27 incorrect. New mechanisms are presented here as well. This document 28 does NOT indicate which mechanisms may be considered "required to 29 implement". 30 31 Comments should be sent to the editor, or to the IETF Kerberos 32 working group (ietf-krb-wg@anl.gov). 33 34Status 35 36 This document is an Internet-Draft and is in full conformance with 37 all provisions of Section 10 of RFC2026 [RFC2026]. Internet-Drafts 38 are working documents of the Internet Engineering Task Force (IETF), 39 its areas, and its working groups. Note that other groups may also 40 distribute working documents as Internet-Drafts. Internet-Drafts are 41 draft documents valid for a maximum of six months and may be updated, 42 replaced, or obsoleted by other documents at any time. It is 43 inappropriate to use Internet-Drafts as reference material or to cite 44 them other than as "work in progress." 45 46 The list of current Internet-Drafts can be accessed at 47 http://www.ietf.org/ietf/1id-abstracts.html. 48 49 The list of Internet-Draft Shadow Directories can be accessed at 50 http://www.ietf.org/shadow.html. 51 52 53 54 55 56 57 58Raeburn [Page 1] 59 60INTERNET DRAFT February 2003 61 62 63 Table of Contents 64 65 66Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 67Status . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 68Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . 2 69Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 701. Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 712. Encryption algorithm profile . . . . . . . . . . . . . . . . . . 4 723. Checksum algorithm profile . . . . . . . . . . . . . . . . . . . 9 734. Simplified profile for CBC ciphers with key derivation . . . . . 10 744.1. A key derivation function . . . . . . . . . . . . . . . . . . . 10 754.2. Simplified profile parameters . . . . . . . . . . . . . . . . . 12 764.3. Cryptosystem profile based on simplified profile . . . . . . . 14 774.4. Checksum profiles based on simplified profile . . . . . . . . . 16 785. Profiles for Kerberos encryption and checksum algorithms . . . . 16 795.1. Unkeyed checksums . . . . . . . . . . . . . . . . . . . . . . . 16 805.2. DES-based encryption and checksum types . . . . . . . . . . . . 18 815.3. Triple-DES based encryption and checksum types . . . . . . . . 28 826. Use of Kerberos encryption outside this specification . . . . . . 30 837. Assigned Numbers . . . . . . . . . . . . . . . . . . . . . . . . 31 848. Implementation Notes . . . . . . . . . . . . . . . . . . . . . . 32 859. Security Considerations . . . . . . . . . . . . . . . . . . . . . 33 8610. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 34 8711. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . 35 8812. Editor's address . . . . . . . . . . . . . . . . . . . . . . . . 35 8913. Full Copyright Statement . . . . . . . . . . . . . . . . . . . . 36 90A. Test vectors . . . . . . . . . . . . . . . . . . . . . . . . . . 36 91A.1. n-fold . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 92A.2. mit_des_string_to_key . . . . . . . . . . . . . . . . . . . . . 38 93A.3. DES3 DR and DK . . . . . . . . . . . . . . . . . . . . . . . . 42 94A.4. DES3string_to_key . . . . . . . . . . . . . . . . . . . . . . . 43 95A.5. Modified CRC-32 . . . . . . . . . . . . . . . . . . . . . . . . 44 96B. Significant Changes from RFC 1510 . . . . . . . . . . . . . . . . 44 97Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 98Normative References . . . . . . . . . . . . . . . . . . . . . . . . 46 99Informative References . . . . . . . . . . . . . . . . . . . . . . . 48 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114Raeburn [Page 2] 115 116INTERNET DRAFT February 2003 117 118 119Introduction 120 121 The Kerberos protocols are designed to encrypt messages of arbitrary 122 sizes, using block encryption ciphers, or less commonly, stream 123 encryption ciphers. Encryption is used to prove the identities of 124 the network entities participating in message exchanges. However, 125 nothing in the Kerberos protocol requires any specific encryption 126 algorithm be used, as long as certain operations are available in the 127 algorithm that is used. 128 129 The following sections specify the encryption and checksum mechanisms 130 currently defined for Kerberos, as well as a framework for defining 131 future mechanisms. The encoding, chaining, padding and other 132 requirements for each are described. Test vectors for several 133 functions are given in appendix A. 134 1351. Concepts 136 137 Both encryption and checksum mechanisms are defined in terms of 138 profiles, detailed in later sections. Each specifies a collection of 139 operations and attributes that must be defined for a mechanism. A 140 Kerberos encryption or checksum mechanism specification is not 141 complete if it does not define all of these operations and 142 attributes. 143 144 An encryption mechanism must provide for confidentiality and 145 integrity of the original plaintext. (Integrity checking may be 146 achieved by incorporating a checksum, if the encryption mode does not 147 provide an integrity check itself.) It must also provide non- 148 malleability [Bellare98, Dolev91]. Use of a random confounder 149 prepended to the plaintext is recommended. It should not be possible 150 to determine if two ciphertexts correspond to the same plaintext, 151 without knowledge of the key. 152 153 A checksum mechanism [1] must provide proof of the integrity of the 154 associated message, and must preserve the confidentiality of the 155 message in case it is not sent in the clear. It should be infeasible 156 to find two plaintexts which have the same checksum. It is NOT 157 required that an eavesdropper be unable to determine if two checksums 158 are for the same message; it is assumed that the messages themselves 159 will be visible to any such eavesdropper. 160 161 Due to advances in cryptography, it is considered unwise by some 162 cryptographers to use the same key for multiple purposes. Since keys 163 are used in performing a number of different functions in Kerberos, 164 it is desirable to use different keys for each of these purposes, 165 even though we start with a single long-term or session key. 166 167 168 169 170Raeburn [Page 3] 171 172INTERNET DRAFT February 2003 173 174 175 We do this by enumerating the different uses of keys within Kerberos, 176 and making the "usage number" an input to the encryption or checksum 177 mechanisms; this enumeration is outside the scope of this document. 178 Later sections of this document define simplified profile templates 179 for encryption and checksum mechanisms that use a key derivation 180 function applied to a CBC mode (or similar) cipher and a checksum or 181 hash algorithm. 182 183 We distinguish the "base key" specified by other documents from the 184 "specific key" to be used for a particular instance of encryption or 185 checksum operations. It is expected but not required that the 186 specific key will be one or more separate keys derived from the 187 original protocol key and the key usage number. The specific key 188 should not be explicitly referenced outside of this document. The 189 typical language used in other documents should be something like, 190 "encrypt this octet string using this key and this usage number"; 191 generation of the specific key and cipher state (described in the 192 next section) are implicit. The creation of a new cipher-state 193 object, or the re-use of one from a previous encryption operation, 194 may also be explicit. 195 196 New protocols defined in terms of the Kerberos encryption and 197 checksum types should use their own key usage values. Key usages are 198 unsigned 32 bit integers; zero is not permitted. 199 200 All data is assumed to be in the form of strings of octets or 8-bit 201 bytes. Environments with other byte sizes will have to emulate this 202 behavior in order to get correct results. 203 204 Each algorithm is assigned an encryption type (or "etype") or 205 checksum type number, for algorithm identification within the 206 Kerberos protocol. The full list of current type number assignments 207 is given in section 7. 208 2092. Encryption algorithm profile 210 211 An encryption mechanism profile must define the following attributes 212 and operations. The operations must be defined as functions in the 213 mathematical sense: no additional or implicit inputs (such as 214 Kerberos principal names or message sequence numbers) are permitted. 215 216 protocol key format 217 This describes what octet string values represent valid keys. For 218 encryption mechanisms that don't have perfectly dense key spaces, 219 this will describe the representation used for encoding keys. It 220 need not describe specific values that are not valid or desirable 221 for use; such values should be avoid by all key generation 222 routines. 223 224 225 226Raeburn [Page 4] 227 228INTERNET DRAFT February 2003 229 230 231 specific key structure 232 This is not a protocol format at all, but a description of the 233 keying material derived from the chosen key and used to encrypt or 234 decrypt data or compute or verify a checksum. It may, for 235 example, be a single key, a set of keys, or a combination of the 236 original key with additional data. The authors recommend using 237 one or more keys derived from the original key via one-way 238 functions. 239 240 required checksum mechanism 241 This indicates a checksum mechanism that must be available when 242 this encryption mechanism is used. Since Kerberos has no built in 243 mechanism for negotiating checksum mechanisms, once an encryption 244 mechanism has been decided upon, the corresponding checksum 245 mechanism can simply be used. 246 247 key-generation seed length, K 248 This is the length of the random bitstring needed to generate a 249 key with the encryption scheme's random-to-key function (described 250 below). This must be a fixed value so that various techniques for 251 producing a random bitstring of a given length may be used with 252 key generation functions. 253 254 key generation functions 255 Keys must be generated in a number of cases, from different types 256 of inputs. All function specifications must indicate how to 257 generate keys in the proper wire format, and must avoid generation 258 of keys that significantly compromise the confidentiality of 259 encrypted data, if the cryptosystem has such. Entropy from each 260 source should be preserved as much as possible. Many of the 261 inputs, while unknown, may be at least partly predictable (e.g., a 262 password string is likely to be entirely in the ASCII subset and 263 of fairly short length in many environments; a semi-random string 264 may include timestamps); the benefit of such predictability to an 265 attacker must be minimized. 266 267 string-to-key (UTF-8 string, UTF-8 string, opaque)->(protocol-key) 268 This function generates a key from two UTF-8 strings and an 269 opaque octet string. One of the strings is normally the 270 principal's pass phrase, but is in general merely a secret 271 string. The other string is a "salt" string intended to 272 produce different keys from the same password for different 273 users or realms. While the strings provided will use UTF-8 274 encoding, no specific version of Unicode should be assumed; all 275 valid UTF-8 strings should be allowed. 276 277 The third argument, the octet string, may be used to pass 278 mechanism-specific parameters in to this function. Since doing 279 280 281 282Raeburn [Page 5] 283 284INTERNET DRAFT February 2003 285 286 287 so implies knowledge of the specific encryption system, it is 288 intended that generating non-default parameter values be an 289 uncommon operation, and that normal Kerberos applications be 290 able to treat this parameter block as an opaque object supplied 291 by the KDC or defaulted to some mechanism-specific constant 292 value. 293 294 This should be a one-way function, so that compromising a 295 user's key in one realm does not compromise the user's key in 296 another realm, even if the same password (but a different salt) 297 is used. 298 299 random-to-key (bitstring[K])->(protocol-key) 300 This function generates a key from a random bit string of a 301 specific size. It may be assumed that all the bits of the 302 input string are equally random, even though the entropy 303 present in the random source may be limited. 304 305 key-derivation (protocol-key, integer)->(specific-key) 306 In this function, the integer input is the key usage value as 307 described above; the usage values must be assumed to be known 308 to an attacker. The specific-key output value was described in 309 section 1. 310 311 string-to-key parameter format 312 This describes the format of the block of data that can be passed 313 to the string-to-key function above to configure additional 314 parameters for that function. Along with the mechanism of 315 encoding parameter values, bounds on the allowed parameters should 316 also be described to avoid allowing a spoofed KDC to compromise 317 the user's password. It may be desirable to construct the 318 encoding such that values weakening the resulting key unacceptably 319 cannot be encoded, if practical. 320 321 Tighter bounds might be permitted by local security policy, or to 322 avoid excess resource consumption; if so, recommended defaults for 323 those bounds should be given in the specification. The 324 description should also outline possible weaknesses that may be 325 caused by not applying bounds checks or other validation to a 326 parameter string received from the network. 327 328 As mentioned above, this should be considered opaque to most 329 normal applications. 330 331 default string-to-key parameters (octet string) 332 This default value for the "params" argument to the string-to-key 333 function is to be used when the application protocol (Kerberos or 334 otherwise) does not explicitly set the parameter value. As 335 336 337 338Raeburn [Page 6] 339 340INTERNET DRAFT February 2003 341 342 343 indicated above, this parameter block should be treated as an 344 opaque object in most cases. 345 346 cipher state 347 This describes any information that can be carried over from one 348 encryption or decryption operation to the next, for use in 349 conjunction with a given specific key. For example, a block 350 cipher used in CBC mode may put an initial vector of one block in 351 the cipher state. Other encryption modes may track nonces or 352 other data. 353 354 This state must be non-empty, and must influence encryption so as 355 to require that messages be decrypted in the same order they were 356 encrypted, if the cipher state is carried over from one encryption 357 to the next. Distinguishing out-of-order or missing messages from 358 corrupted messages is not required; if desired, this can be done 359 at a higher level by including sequence numbers and not "chaining" 360 the cipher state between encryption operations. 361 362 The cipher state may not be reused in multiple encryption or 363 decryption operations; these operations all generate a new cipher 364 state that may be used for following operations using the same key 365 and operation. 366 367 The contents of the cipher state must be treated as opaque outside 368 of encryption system specifications. 369 370 initial cipher state (specific-key, direction)->(state) 371 This describes the generation of the initial value for the cipher 372 state if it is not being carried over from a previous encryption 373 or decryption operation. 374 375 This describes any initial state setup needed before encrypting 376 arbitrary amounts of data with a given specific key; the specific 377 key and the direction of operations to be performed (encrypt 378 versus decrypt) must be the only input needed for this 379 initialization. 380 381 This state should be treated as opaque in any uses outside of an 382 encryption algorithm definition. 383 384 IMPLEMENTATION NOTE: [Kerb1510] was vague on whether and to what 385 degree an application protocol could exercise control over the 386 initial vector used in DES CBC operations. Some existing 387 implementations permit the setting of the initial vector. This 388 new specification does not permit application control of the 389 cipher state (beyond "initialize" and "carry over from previous 390 encryption"), since the form and content of the initial cipher 391 392 393 394Raeburn [Page 7] 395 396INTERNET DRAFT February 2003 397 398 399 state can vary between encryption systems, and may not always be a 400 single block of random data. 401 402 New Kerberos application protocols should not assume that they can 403 control the initial vector, or that one even exists. However, a 404 general-purpose implementation may wish to provide the capability, 405 in case applications explicitly setting it are encountered. 406 407 encrypt (specific-key, state, octet string)->(state, octet string) 408 This function takes the specific key, cipher state, and a non- 409 empty plaintext string as input, and generates ciphertext and a 410 new cipher state as outputs. If the basic encryption algorithm 411 itself does not provide for integrity protection (as DES in CBC 412 mode does not do), then some form of MAC or checksum must be 413 included that can be verified by the receiver. Some random factor 414 such as a confounder should be included so that an observer cannot 415 know if two messages contain the same plaintext, even if the 416 cipher state and specific keys are the same. The exact length of 417 the plaintext need not be encoded, but if it is not and if padding 418 is required, the padding must be added at the end of the string so 419 that the decrypted version may be parsed from the beginning. 420 421 The specification of the encryption function must not only 422 indicate the precise contents of the output octet string, but also 423 the output cipher state. The application protocol may carry 424 forward the output cipher state from one encryption with a given 425 specific key to another; the effect of this "chaining" must be 426 defined. [2] 427 428 Assuming correctly-produced values for the specific key and cipher 429 state, no input octet string may result in an error indication. 430 431 decrypt (specific-key, state, octet string)->(state, octet string) 432 This function takes the specific key, cipher state, and ciphertext 433 as inputs, and verifies the integrity of the supplied ciphertext. 434 If the ciphertext's integrity is intact, this function produces 435 the plaintext and a new cipher state as outputs; otherwise, an 436 error indication must be returned, and the data discarded. 437 438 The result of the decryption may be longer than the original 439 plaintext, for example if the encryption mode adds padding to 440 reach a multiple of a block size. If this is the case, any extra 441 octets must be after the decoded plaintext. An application 442 protocol which needs to know the exact length of the message must 443 encode a length or recognizable "end of message" marker within the 444 plaintext. [3] 445 446 As with the encryption function, a correct specification for this 447 448 449 450Raeburn [Page 8] 451 452INTERNET DRAFT February 2003 453 454 455 function must indicate not only the contents of the output octet 456 string, but also the resulting cipher state. 457 458 pseudo-random (protocol-key, octet-string)->(octet-string) 459 This pseudo-random function should generate an octet string of 460 some size that independent of the octet string input. The PRF 461 output string should be suitable for use in key generation, even 462 if the octet string input is public. It should not reveal the 463 input key, even if the output is made public. 464 465 These operations and attributes are all that should be required to 466 support Kerberos and various proposed preauthentication schemes. 467 468 A document defining a new encryption type should also describe known 469 weaknesses or attacks, so that its security may be fairly assessed, 470 and should include test vectors or other validation procedures for 471 the operations defined. Specific references to information readily 472 available elsewhere are sufficient. 473 4743. Checksum algorithm profile 475 476 A checksum mechanism profile must define the following attributes and 477 operations: 478 479 associated encryption algorithm(s) 480 This indicates the types of encryption keys this checksum 481 mechanism can be used with. 482 483 A keyed checksum mechanism may have more than one associated 484 encryption algorithm if they share the same wire key format, 485 string-to-key function, and key derivation function. (This 486 combination means that, for example, a checksum type, key usage 487 value and password are adequate to get the specific key used to 488 compute a checksum.) 489 490 An unkeyed checksum mechanism can be used in conjunction with any 491 encryption type, since the key is ignored, but its use must be 492 limited to cases where the checksum itself is protected, to avoid 493 trivial attacks. 494 495 get_mic function 496 This function generates a MIC token for a given specific key (see 497 section 2), and message (represented as an octet string), that may 498 be used to verify the integrity of the associated message. This 499 function is not required to return the same deterministic result 500 on every use; it need only generate a token that the verify_mic 501 routine can check. 502 503 504 505 506Raeburn [Page 9] 507 508INTERNET DRAFT February 2003 509 510 511 The output of this function will also dictate the size of the 512 checksum. 513 514 verify_mic function 515 Given a specific key, message, and MIC token, this function 516 ascertains whether the message integrity has been compromised. 517 For a deterministic get_mic routine, the corresponding verify_mic 518 may simply generate another checksum and compare them. 519 520 The get_mic and verify_mic operations must be able to handle inputs 521 of arbitrary length; if any padding is needed, the padding scheme 522 must be specified as part of these functions. 523 524 These operations and attributes are all that should be required to 525 support Kerberos and various proposed preauthentication schemes. 526 527 As with encryption mechanism definition documents, documents defining 528 new checksum mechanisms should indicate validation processes and 529 known weaknesses. 530 5314. Simplified profile for CBC ciphers with key derivation 532 533 The profile outlines in sections 2 and 3 describes a large number of 534 operations that must be defined for encryption and checksum 535 algorithms to be used with Kerberos. We describe here a simpler 536 profile from which both encryption and checksum mechanism definitions 537 can be generated, filling in uses of key derivation in appropriate 538 places, providing integrity protection, and defining multiple 539 operations for the cryptosystem profile based on a smaller set of 540 operations given in the simplified profile. Not all of the existing 541 cryptosystems for Kerberos fit into this simplified profile, but we 542 recommend that future cryptosystems use it or something based on it. 543 [4] 544 545 Not all of the operations in the complete profiles are defined 546 through this mechanism; several must still be defined for each new 547 algorithm pair. 548 5494.1. A key derivation function 550 551 Rather than define some scheme by which a "protocol key" is composed 552 of a large number of encryption keys, we use keys derived from a base 553 key to perform cryptographic operations. The base key must be used 554 only for generating the derived keys, and this derivation must be 555 non-invertible and entropy-preserving. Given these restrictions, 556 compromise of one derived key does not compromise the other subkeys. 557 Attack of the base key is limited, since it is only used for 558 derivation, and is not exposed to any user data. 559 560 561 562Raeburn [Page 10] 563 564INTERNET DRAFT February 2003 565 566 567 Since the derived key has as much entropy as the base keys (if the 568 cryptosystem is good), password-derived keys have the full benefit of 569 all the entropy in the password. 570 571 To generate a derived key from a base key, we generate a pseudorandom 572 octet string, using an algorithm DR described below, and generate a 573 key from that octet string using a function dependent on the 574 encryption algorithm; the input length needed for that function, 575 which is also dependent on the encryption algorithm, dictates the 576 length of the string to be generated by the DR algorithm (the value 577 "k" below). These procedures are based on the key derivation in 578 [Blumenthal96]. 579 580 Derived Key = DK(Base Key, Well-Known Constant) 581 582 DK(Key, Constant) = random-to-key(DR(Key, Constant)) 583 584 DR(Key, Constant) = k-truncate(E(Key, Constant, 585 initial-cipher-state)) 586 587 Here DR is the random-octet generation function described below, and 588 DK is the key-derivation function produced from it. In this 589 construction, E(Key, Plaintext, CipherState) is a cipher, Constant is 590 a well-known constant determined by the specific usage of this 591 function, and k-truncate truncates its argument by taking the first k 592 bits. Here, k is the key generation seed length needed for the 593 encryption system. 594 595 The output of the DR function is a string of bits; the actual key is 596 produced by applying the cryptosystem's random-to-key operation on 597 this bitstring. 598 599 If the Constant is smaller than the cipher block size of E, then it 600 must be expanded with n-fold() so it can be encrypted. If the output 601 of E is shorter than k bits it is fed back into the encryption as 602 many times as necessary. The construct is as follows (where | 603 indicates concatentation): 604 605 K1 = E(Key, n-fold(Constant), initial-cipher-state) 606 K2 = E(Key, K1, initial-cipher-state) 607 K3 = E(Key, K2, initial-cipher-state) 608 K4 = ... 609 610 DR(Key, Constant) = k-truncate(K1 | K2 | K3 | K4 ...) 611 612 n-fold is an algorithm which takes m input bits and ``stretches'' 613 them to form n output bits with equal contribution from each input 614 bit to the output, as described in [Blumenthal96]: 615 616 617 618Raeburn [Page 11] 619 620INTERNET DRAFT February 2003 621 622 623 We first define a primitive called n-folding, which takes a 624 variable-length input block and produces a fixed-length output 625 sequence. The intent is to give each input bit approximately 626 equal weight in determining the value of each output bit. Note 627 that whenever we need to treat a string of octets as a number, the 628 assumed representation is Big-Endian -- Most Significant Byte 629 first. 630 631 To n-fold a number X, replicate the input value to a length that 632 is the least common multiple of n and the length of X. Before 633 each repetition, the input is rotated to the right by 13 bit 634 positions. The successive n-bit chunks are added together using 635 1's-complement addition (that is, with end-around carry) to yield 636 a n-bit result.... 637 638 639 Test vectors for n-fold are supplied in Appendix A. [5] 640 641 In this section, n-fold is always used to produce c bits of output, 642 where c is the cipher block size of E. 643 644 The size of the Constant must not be larger than c, because reducing 645 the length of the Constant by n-folding can cause collisions. 646 647 If the size of the Constant is smaller than c, then the Constant must 648 be n-folded to length c. This string is used as input to E. If the 649 block size of E is less than the random-to-key input size, then the 650 output from E is taken as input to a second invocation of E. This 651 process is repeated until the number of bits accumulated is greater 652 than or equal to the random-to-key input size. When enough bits have 653 been computed, the first k are taken as the random data used to 654 create the key with the algorithm-dependent random-to-key function. 655 656 Since the derived key is the result of one or more encryptions in the 657 base key, deriving the base key from the derived key is equivalent to 658 determining the key from a very small number of plaintext/ciphertext 659 pairs. Thus, this construction is as strong as the cryptosystem 660 itself. 661 6624.2. Simplified profile parameters 663 664 These are the operations and attributes that must be defined: 665 666 667 668 669 670 671 672 673 674Raeburn [Page 12] 675 676INTERNET DRAFT February 2003 677 678 679 protocol key format 680 string-to-key function 681 default string-to-key parameters 682 key-generation seed length, k 683 random-to-key function 684 As above for the normal encryption mechanism profile. 685 686 unkeyed hash algorithm, H 687 This should be a collision-resistant hash algorithm with fixed- 688 size output, suitable for use in an HMAC [HMAC]. It must support 689 inputs of arbitrary length. Its output must be at least the 690 message block size (below). 691 692 HMAC output size, h 693 This indicates the size of the leading substring output by the 694 HMAC function that should be used in transmitted messages. It 695 should be at least half the output size of the hash function H, 696 and at least 80 bits; it need not match the output size. 697 698 message block size, m 699 This is the size of the smallest units the cipher can handle in 700 the mode in which it is being used. Messages will be padded to a 701 multiple of this size. If a block cipher is used in a mode that 702 can handle messages that are not multiples of the cipher block 703 size, such as CBC mode with cipher text stealing (CTS, see [RC5]), 704 this value would be one octet. For traditional CBC mode with 705 padding, it will be the underlying cipher's block size. 706 707 This value must be a multiple of 8 bits (one octet). 708 709 encryption/decryption functions, E and D 710 These are basic encryption and decryption functions for messages 711 of sizes that are multiples of the message block size. No 712 integrity checking or confounder should be included here. These 713 functions take as input the IV or similar data, a protocol-format 714 key, and a octet string, returning a new IV and octet string. 715 716 The encryption function is not required to use CBC mode, but is 717 assumed to be using something with similar properties. In 718 particular, prepending a cipher-block-size confounder to the 719 plaintext should alter the entire ciphertext (comparable to 720 choosing and including a random initial vector for CBC mode). 721 722 The result of encrypting one cipher block (of size c, above) must 723 be deterministic, for the random octet generation function DR in 724 the previous section to work. For best security, it should also 725 be no larger than c. 726 727 728 729 730Raeburn [Page 13] 731 732INTERNET DRAFT February 2003 733 734 735 cipher block size, c 736 This is the block size of the block cipher underlying the 737 encryption and decryption functions indicated above, used for key 738 derivation and for the size of the message confounder and initial 739 vector. (If a block cipher is not in use, some comparable 740 parameter should be determined.) It must be at least 5 octets. 741 742 This is not actually an independent parameter; rather, it is a 743 property of the functions E and D. It is listed here to clarify 744 the distinction between it and the message block size, m. 745 746 While there are still a number of properties to specify, they are 747 fewer and simpler than in the full profile. 748 7494.3. Cryptosystem profile based on simplified profile 750 751 The above key derivation function is used to produce three 752 intermediate keys. One is used for computing checksums of 753 unencrypted data. The other two are used for encrypting and 754 checksumming plaintext to be sent encrypted. 755 756 The ciphertext output is the concatenation of the output of the basic 757 encryption function E and a (possibly truncated) HMAC using the 758 specified hash function H, both applied to the plaintext with a 759 random confounder prefix and sufficient padding to bring it to a 760 multiple of the message block size. When the HMAC is computed, the 761 key is used in the protocol key form. 762 763 Decryption is performed by removing the (partial) HMAC, decrypting 764 the remainder, and verifying the HMAC. The cipher state is an 765 initial vector, initialized to zero. 766 767 The substring notation "[1..h]" in the following table should be read 768 as using 1-based indexing; leading substrings are used. 769 770 771 cryptosystem from simplified profile 772---------------------------------------------------------------------------- 773protocol key format As given. 774 775specific key structure Three protocol-format keys: { Kc, Ke, Ki }. 776 777key-generation seed As given. 778length 779 780required checksum As defined below in section 4.4. 781mechanism 782 783 784 785 786Raeburn [Page 14] 787 788INTERNET DRAFT February 2003 789 790 791 cryptosystem from simplified profile 792---------------------------------------------------------------------------- 793 794cipher state initial vector (usually of length c) 795 796initial cipher state all bits zero 797 798encryption function conf = random string of length c 799 pad = shortest string to bring confounder 800 and plaintext to a length that's a 801 multiple of m 802 C1 = E(Ke, conf | plaintext | pad, 803 oldstate.ivec) 804 H1 = HMAC(Ki, conf | plaintext | pad) 805 ciphertext = C1 | H1[1..h] 806 newstate.ivec = last c of C1 807 808decryption function (C1,H1) = ciphertext 809 P1 = D(Ke, C1, oldstate.ivec) 810 if (H1 != HMAC(Ki, P1)[1..h]) 811 report error 812 newstate.ivec = last c of C1 813 814default string-to-key As given. 815params 816 817pseudo-random function tmp1 = H(octet-string) 818 tmp2 = truncate tmp1 to multiple of m 819 PRF = E(protocol-key, tmp2, initial-cipher-state) 820 821key generation functions: 822 823string-to-key function As given. 824 825random-to-key function As given. 826 827key-derivation function The "well-known constant" used for the DK 828 function is the key usage number, expressed as 829 four octets in big-endian order, followed by one 830 octet indicated below. 831 832 Kc = DK(base-key, usage | 0x99); 833 Ke = DK(base-key, usage | 0xAA); 834 Ki = DK(base-key, usage | 0x55); 835 836 837 838 839 840 841 842Raeburn [Page 15] 843 844INTERNET DRAFT February 2003 845 846 8474.4. Checksum profiles based on simplified profile 848 849 When an encryption system is defined using the simplified profile 850 given in section 4.2, a checksum algorithm may be defined for it as 851 follows: 852 853 854 checksum mechanism from simplified profile 855 -------------------------------------------------- 856 associated cryptosystem as defined above 857 858 get_mic HMAC(Kc, message)[1..h] 859 860 verify_mic get_mic and compare 861 862 The HMAC function and key Kc are as described in section 4.3. 863 8645. Profiles for Kerberos encryption and checksum algorithms 865 866 These profiles describe the encryption and checksum systems defined 867 for Kerberos. The astute reader will notice that some of them do not 868 fulfull all of the requirements outlined in previous sections. These 869 systems are defined for backward compatibility; newer implementations 870 should (whenever possible) attempt to make use of encryption systems 871 which satisfy all of the profile requirements. 872 873 The full list of current encryption and checksum type number 874 assignments, including values currently reserved but not defined in 875 this document, is given in section 7. 876 8775.1. Unkeyed checksums 878 879 These checksum types use no encryption keys, and thus can be used in 880 combination with any encryption type, but may only be used with 881 caution, in limited circumstances where the lack of a key does not 882 provide a window for an attack, preferably as part of an encrypted 883 message. [6] Keyed checksum algorithms are recommended. 884 8855.1.1. The RSA MD5 Checksum 886 887 The RSA-MD5 checksum calculates a checksum using the RSA MD5 888 algorithm [MD5-92]. The algorithm takes as input an input message of 889 arbitrary length and produces as output a 128-bit (16 octet) 890 891 892 893 894 895 896 897 898Raeburn [Page 16] 899 900INTERNET DRAFT February 2003 901 902 903 checksum. RSA-MD5 is believed to be collision-proof. 904 905 rsa-md5 906 ---------------------------------------------- 907 associated cryptosystem any 908 909 get_mic rsa-md5(msg) 910 911 verify_mic get_mic and compare 912 913 The rsa-md5 checksum algorithm is assigned a checksum type number of 914 seven (7). 915 9165.1.2. The RSA MD4 Checksum 917 918 The RSA-MD4 checksum calculates a checksum using the RSA MD4 919 algorithm [MD4-92]. The algorithm takes as input an input message of 920 arbitrary length and produces as output a 128-bit (16 octet) 921 checksum. RSA-MD4 is believed to be collision-proof. 922 923 924 rsa-md4 925 ---------------------------------------------- 926 associated cryptosystem any 927 928 get_mic md4(msg) 929 930 verify_mic get_mic and compare 931 932 933 The rsa-md4 checksum algorithm is assigned a checksum type number of 934 two (2). 935 9365.1.3. CRC-32 Checksum 937 938 This CRC-32 checksum calculates a checksum based on a cyclic 939 redundancy check as described in ISO 3309 [CRC], modified as 940 described below. The resulting checksum is four (4) octets in 941 length. The CRC-32 is neither keyed nor collision-proof; thus, the 942 use of this checksum is not recommended. An attacker using a 943 probabilistic chosen-plaintext attack as described in [SG92] might be 944 able to generate an alternative message that satisfies the checksum. 945 946 The CRC-32 checksum used in the des-cbc-crc encryption mode is 947 identical to the 32-bit FCS described in ISO 3309 with two 948 exceptions: the sum with the all-ones polynomial times x**k is 949 omitted, and the final remainder is not ones-complemented. ISO 3309 950 describes the FCS in terms of bits, while this document describes the 951 952 953 954Raeburn [Page 17] 955 956INTERNET DRAFT February 2003 957 958 959 Kerberos protocol in terms of octets. To disambiguate the ISO 3309 960 definition for the purpose of computing the CRC-32 in the des-cbc-crc 961 encryption mode, the ordering of bits in each octet shall be assumed 962 to be LSB-first. Given this assumed ordering of bits within an 963 octet, the mapping of bits to polynomial coefficients shall be 964 identical to that specified in ISO 3309. 965 966 Test values for this modified CRC function are included in appendix 967 A.5. 968 969 970 crc32 971 ---------------------------------------------- 972 associated cryptosystem any 973 974 get_mic crc32(msg) 975 976 verify_mic get_mic and compare 977 978 979 The crc32 checksum algorithm is assigned a checksum type number of 980 one (1). 981 9825.2. DES-based encryption and checksum types 983 984 These encryption systems encrypt information under the Data 985 Encryption Standard [DES77] using the cipher block chaining mode 986 [DESM80]. A checksum is computed as described below and placed in 987 the cksum field. DES blocks are 8 bytes. As a result, the data to 988 be encrypted (the concatenation of confounder, checksum, and message) 989 must be padded to an 8 byte boundary before encryption. The values 990 of the padding bytes are unspecified. 991 992 Plaintext and DES ciphertext are encoded as blocks of 8 octets which 993 are concatenated to make the 64-bit inputs for the DES algorithms. 994 The first octet supplies the 8 most significant bits (with the 995 octet's MSB used as the DES input block's MSB, etc.), the second 996 octet the next 8 bits, ..., and the eighth octet supplies the 8 least 997 significant bits. 998 999 Encryption under DES using cipher block chaining requires an 1000 additional input in the form of an initialization vector; this vector 1001 is specified for each encryption system, below. 1002 1003 The DES specifications [DESI81] identify four 'weak' and twelve 1004 'semi-weak' keys; those keys shall not be used for encrypting 1005 messages for use in Kerberos. 1006 1007 1008 1009 1010Raeburn [Page 18] 1011 1012INTERNET DRAFT February 2003 1013 1014 1015 A DES key is 8 octets of data. This consists of 56 bits of actual 1016 key data, and 8 parity bits, one per octet. The key is encoded as a 1017 series of 8 octets written in MSB-first order. The bits within the 1018 key are also encoded in MSB order. For example, if the encryption 1019 key is (B1,B2,...,B7,P1,B8,...,B14,P2,B15,...,B49,P7,B50,...,B56,P8) 1020 where B1,B2,...,B56 are the key bits in MSB order, and P1,P2,...,P8 1021 are the parity bits, the first octet of the key would be 1022 B1,B2,...,B7,P1 (with B1 as the most significant bit). See the 1023 [DESM80] introduction for reference. 1024 1025 Encryption data format 1026 1027 The format for the data to be encrypted includes a one-block 1028 confounder, a checksum, the encoded plaintext, and any necessary 1029 padding, as described in the following diagram. The msg-seq field 1030 contains the part of the protocol message which is to be encrypted. 1031 1032 +-----------+----------+---------+-----+ 1033 |confounder | checksum | msg-seq | pad | 1034 +-----------+----------+---------+-----+ 1035 1036 One generates a random confounder of one block, placing it in 1037 'confounder'; zeroes out the 'checksum' field (of length appropriate 1038 to exactly hold the checksum to be computed); calculates the 1039 appropriate checksum over the whole sequence, placing the result in 1040 'checksum'; adds the necessary padding; then encrypts using the 1041 specified encryption type and the appropriate key. 1042 1043 String or random-data to key transformation 1044 1045 To generate a DES key from two UTF-8 text strings (password and 1046 salt), the two strings are concatenated, password first, and the 1047 result is then padded with zero-valued octets to a multiple of 8 1048 octets. 1049 1050 The top bit of each octet (always zero if the password is plain 1051 ASCII, as was assumed when the original specification was written) is 1052 discarded, and a bitstring is formed of the remaining seven bits of 1053 each octet. This bitstring is then fan-folded and eXclusive-ORed 1054 with itself to produce a 56-bit string. An eight-octet key is formed 1055 from this string, each octet using seven bits from the bit string, 1056 leaving the least significant bit unassigned. The key is then 1057 "corrected" by correcting the parity on the key, and if the key 1058 matches a 'weak' or 'semi-weak' key as described in the DES 1059 specification, it is eXclusive-ORed with the constant 1060 0x00000000000000F0. This key is then used to generate a DES CBC 1061 checksum on the initial string with the salt appended. The result of 1062 the CBC checksum is then "corrected" as described above to form the 1063 1064 1065 1066Raeburn [Page 19] 1067 1068INTERNET DRAFT February 2003 1069 1070 1071 result which is returned as the key. 1072 1073 For purposes of the string-to-key function, the DES CBC checksum is 1074 calculated by CBC encrypting a string using the key as IV and using 1075 the final 8 byte block as the checksum. 1076 1077 Pseudocode follows: 1078 1079 removeMSBits(8byteblock) { 1080 /* Treats a 64 bit block as 8 octets and remove the MSB in 1081 each octect (in big endian mode) and concatenates the 1082 result. E.g., input octet string: 1083 01110000 01100001 11110011 01110011 11110111 01101111 1084 11110010 01100100 1085 results in output bit string: 1086 1110000 1100001 1110011 1110011 1110111 1101111 1087 1110010 1100100 */ 1088 } 1089 1090 reverse(56bitblock) { 1091 /* Treats a 56-bit block as a binary string and reverse it. 1092 E.g., input string: 1093 1000001 1010100 1001000 1000101 1001110 1000001 1094 0101110 1001101 1095 results in output string: 1096 1011001 0111010 1000001 0111001 1010001 0001001 1097 0010101 1000001 */ 1098 } 1099 1100 add_parity_bits(56bitblock) { 1101 /* Copies a 56-bit block into a 64-bit block, left shift 1102 content in each octet and add DES parity bit. 1103 E.g., input string: 1104 1100000 0001111 0011100 0110100 1000101 1100100 1105 0110110 0010111 1106 results in output string: 1107 11000001 00011111 00111000 01101000 10001010 11001000 1108 01101101 00101111 */ 1109 } 1110 1111 key_correction(key) { 1112 fixparity(key); 1113 if (is_weak_key(key)) 1114 key = key XOR 0xF0; 1115 return(key); 1116 } 1117 1118 1119 1120 1121 1122Raeburn [Page 20] 1123 1124INTERNET DRAFT February 2003 1125 1126 1127 mit_des_string_to_key(string,salt) { 1128 odd = 1; 1129 s = string | salt; 1130 tempstring = 0; /* 56-bit string */ 1131 pad(s); /* with nulls to 8 byte boundary */ 1132 for (8byteblock in s) { 1133 56bitstring = removeMSBits(8byteblock); 1134 if (odd == 0) reverse(56bitstring); 1135 odd = ! odd; 1136 tempstring = tempstring XOR 56bitstring; 1137 } 1138 tempkey = key_correction(add_parity_bits(tempstring)); 1139 key = key_correction(DES-CBC-check(s,tempkey)); 1140 return(key); 1141 } 1142 1143 des_string_to_key(string,salt,params) { 1144 if (length(params) == 0) 1145 type = 0; 1146 else if (length(params) == 1) 1147 type = params[0]; 1148 else 1149 error("invalid params"); 1150 if (type == 0) 1151 mit_des_string_to_key(string,salt); 1152 else 1153 error("invalid params"); 1154 } 1155 1156 One common extension is to support the "AFS string-to-key" algorithm, 1157 which is not defined here, if the type value above is one (1). 1158 1159 For generation of a key from a random bit-string, we start with a 1160 56-bit string, and as with the string-to-key operation above, insert 1161 parity bits, and if the result is a weak or semi-weak key, modify it 1162 by exclusive-OR with the constart 0x00000000000000F0: 1163 1164 des_random_to_key(bitstring) { 1165 return key_correction(add_parity_bits(bitstring)); 1166 } 1167 11685.2.1. DES with MD5 1169 1170 The des-cbc-md5 encryption mode encrypts information under DES in CBC 1171 mode with an all-zero initial vector, with an MD5 checksum (described 1172 in [MD5-92]) computed and placed in the checksum field. 1173 1174 1175 1176 1177 1178Raeburn [Page 21] 1179 1180INTERNET DRAFT February 2003 1181 1182 1183 The encryption system parameters for des-cbc-md5 are: 1184 1185 des-cbc-md5 1186 -------------------------------------------------------------------- 1187 protocol key format 8 bytes, parity in low bit of each 1188 1189 specific key structure copy of original key 1190 1191 required checksum rsa-md5-des 1192 mechanism 1193 1194 key-generation seed 8 bytes 1195 length 1196 1197 cipher state 8 bytes (CBC initial vector) 1198 1199 initial cipher state all-zero 1200 1201 encryption function des-cbc(confounder | checksum | msg | pad, 1202 ivec=oldstate) 1203 where 1204 checksum = md5(confounder | 0000... 1205 | msg | pad) 1206 1207 newstate = last block of des-cbc output 1208 1209 decryption function decrypt encrypted text and verify checksum 1210 1211 newstate = last block of ciphertext 1212 1213 default string-to-key empty string 1214 params 1215 1216 pseudo-random function des-cbc(md5(input-string), ivec=0) 1217 1218 key generation functions: 1219 1220 string-to-key des_string_to_key 1221 1222 random-to-key des_random_to_key 1223 1224 key-derivation identity 1225 1226 The des-cbc-md5 encryption type is assigned the etype value three 1227 (3). 1228 1229 1230 1231 1232 1233 1234Raeburn [Page 22] 1235 1236INTERNET DRAFT February 2003 1237 1238 12395.2.2. DES with MD4 1240 1241 The des-cbc-md4 encryption mode also encrypts information under DES 1242 in CBC mode, with an all-zero initial vector. An MD4 checksum 1243 (described in [MD4-92]) is computed and placed in the checksum field. 1244 1245 des-cbc-md4 1246 -------------------------------------------------------------------- 1247 protocol key format 8 bytes, parity in low bit of each 1248 1249 specific key structure copy of original key 1250 1251 required checksum rsa-md4-des 1252 mechanism 1253 1254 key-generation seed 8 bytes 1255 length 1256 1257 cipher state 8 bytes (CBC initial vector) 1258 1259 initial cipher state all-zero 1260 1261 encryption function des-cbc(confounder | checksum | msg | pad, 1262 ivec=oldstate) 1263 where 1264 checksum = md4(confounder | 0000... 1265 | msg | pad) 1266 1267 newstate = last block of des-cbc output 1268 1269 decryption function decrypt encrypted text and verify checksum 1270 1271 newstate = last block of ciphertext 1272 1273 default string-to-key empty string 1274 params 1275 1276 pseudo-random function des-cbc(md5(input-string), ivec=0) 1277 1278 key generation functions: 1279 1280 string-to-key des_string_to_key 1281 1282 random-to-key copy input, then fix parity bits 1283 1284 key-derivation identity 1285 1286 1287 1288 1289 1290Raeburn [Page 23] 1291 1292INTERNET DRAFT February 2003 1293 1294 1295 Note that des-cbc-md4 uses md5, not md4, in the PRF definition. 1296 1297 The des-cbc-md4 encryption algorithm is assigned the etype value two 1298 (2). 1299 13005.2.3. DES with CRC 1301 1302 The des-cbc-crc encryption type uses DES in CBC mode with the key 1303 used as the initialization vector, with a 4-octet CRC-based checksum 1304 computed as described in section 5.1.3. Note that this is not a 1305 standard CRC-32 checksum, but a slightly modified one. 1306 1307 1308 des-cbc-crc 1309 -------------------------------------------------------------------- 1310 protocol key format 8 bytes, parity in low bit of each 1311 1312 specific key structure copy of original key 1313 1314 required checksum rsa-md5-des 1315 mechanism 1316 1317 key-generation seed 8 bytes 1318 length 1319 1320 cipher state 8 bytes (CBC initial vector) 1321 1322 initial cipher state copy of original key 1323 1324 encryption function des-cbc(confounder | checksum | msg | pad, 1325 ivec=oldstate) 1326 where 1327 checksum = crc(confounder | 00000000 1328 | msg | pad) 1329 1330 newstate = last block of des-cbc output 1331 1332 decryption function decrypt encrypted text and verify checksum 1333 1334 newstate = last block of ciphertext 1335 1336 default string-to-key empty string 1337 params 1338 1339 pseudo-random function des-cbc(md5(input-string), ivec=0) 1340 1341 key generation functions: 1342 1343 1344 1345 1346Raeburn [Page 24] 1347 1348INTERNET DRAFT February 2003 1349 1350 1351 des-cbc-crc 1352 -------------------------------------------------------------------- 1353 1354 string-to-key des_string_to_key 1355 1356 random-to-key copy input, then fix parity bits 1357 1358 key-derivation identity 1359 1360 The des-cbc-crc encryption algorithm is assigned the etype value one 1361 (1). 1362 13635.2.4. RSA MD5 Cryptographic Checksum Using DES 1364 1365 The RSA-MD5-DES checksum calculates a keyed collision-proof checksum 1366 by prepending an 8 octet confounder before the text, applying the RSA 1367 MD5 checksum algorithm, and encrypting the confounder and the 1368 checksum using DES in cipher-block-chaining (CBC) mode using a 1369 variant of the key, where the variant is computed by eXclusive-ORing 1370 the key with the hexadecimal constant 0xF0F0F0F0F0F0F0F0. The 1371 initialization vector should be zero. The resulting checksum is 24 1372 octets long. This checksum is tamper-proof and believed to be 1373 collision-proof. 1374 1375 The DES specifications identify some 'weak keys' and 'semi-weak 1376 keys'; those keys shall not be used for encrypting RSA-MD5 checksums 1377 for use in Kerberos. 1378 1379 1380 rsa-md5-des 1381 ---------------------------------------------------------------- 1382 associated cryptosystem des-cbc-md5, des-cbc-md4, des-cbc-crc 1383 1384 get_mic des-cbc(key XOR 0xF0F0F0F0F0F0F0F0, 1385 conf | rsa-md5(conf | msg)) 1386 1387 verify_mic decrypt and verify rsa-md5 checksum 1388 1389 1390 The rsa-md5-des checksum algorithm is assigned a checksum type number 1391 of eight (8). 1392 13935.2.5. RSA MD4 Cryptographic Checksum Using DES 1394 1395 The RSA-MD4-DES checksum calculates a keyed collision-proof checksum 1396 by prepending an 8 octet confounder before the text, applying the RSA 1397 MD4 checksum algorithm [MD4-92], and encrypting the confounder and 1398 the checksum using DES in cipher-block-chaining (CBC) mode using a 1399 1400 1401 1402Raeburn [Page 25] 1403 1404INTERNET DRAFT February 2003 1405 1406 1407 variant of the key, where the variant is computed by eXclusive-ORing 1408 the key with the constant 0xF0F0F0F0F0F0F0F0. [7] The initialization 1409 vector should be zero. The resulting checksum is 24 octets long. 1410 This checksum is tamper-proof and believed to be collision-proof. 1411 1412 The DES specifications identify some "weak keys" and "semi-weak 1413 keys"; those keys shall not be used for generating RSA-MD4 checksums 1414 for use in Kerberos. 1415 1416 rsa-md4-des 1417 ---------------------------------------------------------------- 1418 associated cryptosystem des-cbc-md5, des-cbc-md4, des-cbc-crc 1419 1420 get_mic des-cbc(key XOR 0xF0F0F0F0F0F0F0F0, 1421 conf | rsa-md4(conf | msg), 1422 ivec=0) 1423 1424 verify_mic decrypt and verify rsa-md4 checksum 1425 1426 The rsa-md4-des checksum algorithm is assigned a checksum type number 1427 of three (3). 1428 14295.2.6. RSA MD4 Cryptographic Checksum Using DES alternative 1430 1431 The RSA-MD4-DES-K checksum calculates a keyed collision-proof 1432 checksum by applying the RSA MD4 checksum algorithm and encrypting 1433 the results using DES in cipher block chaining (CBC) mode using a DES 1434 key as both key and initialization vector. The resulting checksum is 1435 16 octets long. This checksum is tamper-proof and believed to be 1436 collision-proof. Note that this checksum type is the old method for 1437 encoding the RSA-MD4-DES checksum and it is no longer recommended. 1438 1439 1440 rsa-md4-des-k 1441 ---------------------------------------------------------------- 1442 associated cryptosystem des-cbc-md5, des-cbc-md4, des-cbc-crc 1443 1444 get_mic des-cbc(key, md4(msg), ivec=key) 1445 1446 verify_mic decrypt, compute checksum and compare 1447 1448 1449 The rsa-md4-des-k checksum algorithm is assigned a checksum type 1450 number of six (6). 1451 1452 1453 1454 1455 1456 1457 1458Raeburn [Page 26] 1459 1460INTERNET DRAFT February 2003 1461 1462 14635.2.7. DES CBC checksum 1464 1465 The DES-MAC checksum is computed by prepending an 8 octet confounder 1466 to the plaintext, padding with zero-valued octets if necessary to 1467 bring the length to a multiple of 8 octets, performing a DES CBC-mode 1468 encryption on the result using the key and an initialization vector 1469 of zero, taking the last block of the ciphertext, prepending the same 1470 confounder and encrypting the pair using DES in cipher-block-chaining 1471 (CBC) mode using a variant of the key, where the variant is computed 1472 by eXclusive-ORing the key with the constant 0xF0F0F0F0F0F0F0F0. The 1473 initialization vector should be zero. The resulting checksum is 128 1474 bits (16 octets) long, 64 bits of which are redundant. This checksum 1475 is tamper-proof and collision-proof. 1476 1477 1478 des-mac 1479 ---------------------------------------------------------------------- 1480 associated des-cbc-md5, des-cbc-md4, des-cbc-crc 1481 cryptosystem 1482 1483 get_mic des-cbc(key XOR 0xF0F0F0F0F0F0F0F0, 1484 conf | des-mac(key, conf | msg | pad, ivec=0), 1485 ivec=0) 1486 1487 verify_mic decrypt, compute DES MAC using confounder, compare 1488 1489 1490 The des-mac checksum algorithm is assigned a checksum type number of 1491 four (4). 1492 14935.2.8. DES CBC checksum alternative 1494 1495 The DES-MAC-K checksum is computed by performing a DES CBC-mode 1496 encryption of the plaintext, with zero-valued padding bytes if 1497 necessary to bring the length to a multiple of 8 octets, and using 1498 the last block of the ciphertext as the checksum value. It is keyed 1499 with an encryption key which is also used as the initialization 1500 vector. The resulting checksum is 64 bits (8 octets) long. This 1501 checksum is tamper-proof and collision-proof. Note that this 1502 checksum type is the old method for encoding the DESMAC checksum and 1503 it is no longer recommended. 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514Raeburn [Page 27] 1515 1516INTERNET DRAFT February 2003 1517 1518 1519 des-mac-k 1520 ---------------------------------------------------------------- 1521 associated cryptosystem des-cbc-md5, des-cbc-md4, des-cbc-crc 1522 1523 get_mic des-mac(key, msg | pad, ivec=key) 1524 1525 verify_mic compute MAC and compare 1526 1527 1528 The des-mac-k checksum algorithm is assigned a checksum type number 1529 of five (5). 1530 15315.3. Triple-DES based encryption and checksum types 1532 1533 This encryption and checksum type pair is based on the Triple DES 1534 cryptosystem in Outer-CBC mode, and the HMAC-SHA1 message 1535 authentication algorithm. 1536 1537 A Triple DES key is the concatenation of three DES keys as described 1538 above for des-cbc-md5. A Triple DES key is generated from random 1539 data by creating three DES keys from separate sequences of random 1540 data. 1541 1542 Encrypted data using this type must be generated as described in 1543 section 4.3. If the length of the input data is not a multiple of 1544 the block size, zero-valued octets must be used to pad the plaintext 1545 to the next eight-octet boundary. The confounder must be eight 1546 random octets (one block). 1547 1548 The simplified profile for Triple DES, with key derivation as defined 1549 in section 4, is as follows: 1550 1551 des3-cbc-hmac-sha1-kd, hmac-sha1-des3-kd 1552 ------------------------------------------------ 1553 protocol key format 24 bytes, parity in low 1554 bit of each 1555 1556 key-generation seed 21 bytes 1557 length 1558 1559 hash function SHA-1 1560 1561 HMAC output size 160 bits 1562 1563 message block size 8 bytes 1564 1565 1566 1567 1568 1569 1570Raeburn [Page 28] 1571 1572INTERNET DRAFT February 2003 1573 1574 1575 des3-cbc-hmac-sha1-kd, hmac-sha1-des3-kd 1576 ------------------------------------------------ 1577 default string-to-key empty string 1578 params 1579 1580 encryption and triple-DES encrypt and 1581 decryption functions decrypt, in outer-CBC 1582 mode (cipher block size 1583 8 octets) 1584 1585 key generation functions: 1586 1587 random-to-key DES3random-to-key (see 1588 below) 1589 1590 string-to-key DES3string-to-key (see 1591 below) 1592 1593 The des3-cbc-hmac-sha1-kd encryption type is assigned the value 1594 sixteen (16). The hmac-sha1-des3-kd checksum algorithm is assigned a 1595 checksum type number of twelve (12). 1596 15975.3.1. Triple DES Key Production (random-to-key, string-to-key) 1598 1599 The 168 bits of random key data are converted to a protocol key value 1600 as follows. First, the 168 bits are divided into three groups of 56 1601 bits, which are expanded individually into 64 bits as follows: 1602 1603 DES3random-to-key: 1604 1 2 3 4 5 6 7 p 1605 9 10 11 12 13 14 15 p 1606 17 18 19 20 21 22 23 p 1607 25 26 27 28 29 30 31 p 1608 33 34 35 36 37 38 39 p 1609 41 42 43 44 45 46 47 p 1610 49 50 51 52 53 54 55 p 1611 56 48 40 32 24 16 8 p 1612 1613 The "p" bits are parity bits computed over the data bits. The output 1614 of the three expansions are concatenated to form the protocol key 1615 value. 1616 1617 The string-to-key function is used to transform UTF-8 passwords into 1618 DES3 keys. The DES3 string-to-key function relies on the "N-fold" 1619 algorithm and DK function, described in section 4. 1620 1621 The n-fold algorithm is applied to the password string concatenated 1622 with a salt value. For 3-key triple DES, the operation will involve 1623 1624 1625 1626Raeburn [Page 29] 1627 1628INTERNET DRAFT February 2003 1629 1630 1631 a 168-fold of the input password string, to generate an intermediate 1632 key, from which the user's long-term key will be derived with the DK 1633 function. The DES3 string-to-key function is shown here in 1634 pseudocode: 1635 1636 DES3string-to-key(passwordString, salt, params) 1637 if (params != emptyString) 1638 error("invalid params"); 1639 s = passwordString + salt 1640 tmpKey = random-to-key(168-fold(s)) 1641 key = DK (tmpKey, KerberosConstant) 1642 1643 No weak-key checking is performed. The KerberosConstant value is the 1644 byte string {0x6b 0x65 0x72 0x62 0x65 0x72 0x6f 0x73}. These values 1645 correspond to the ASCII encoding for the string "kerberos". 1646 16476. Use of Kerberos encryption outside this specification 1648 1649 Several Kerberos-based application protocols and preauthentication 1650 systems have been designed and deployed that perform encryption and 1651 message integrity checks in various ways. While in some cases there 1652 may be good reason for specifying these protocols in terms of 1653 specific encryption or checksum algorithms, we anticipate that in 1654 many cases this will not be true, and more generic approaches 1655 independent of particular algorithms will be desirable. Rather than 1656 having each protocol designer reinvent schemes for protecting data, 1657 using multiple keys, etc, we have attempted to present in this 1658 section a general framework that should be sufficient not only for 1659 the Kerberos protocol itself but also for many preauthentication 1660 systems and application protocols, while trying to avoid some of the 1661 assumptions that can work their way into such protocol designs. 1662 1663 Some problematic assumptions we've seen (and sometimes made) include: 1664 that a random bitstring is always valid as a key (not true for DES 1665 keys with parity); that the basic block encryption chaining mode 1666 provides no integrity checking, or can easily be separated from such 1667 checking (not true for many modes in development that do both 1668 simultaneously); that a checksum for a message always results in the 1669 same value (not true if a confounder is incorporated); that an 1670 initial vector is used (may not be true if a block cipher in CBC mode 1671 is not in use). 1672 1673 Such assumptions, while they may hold for any given set of encryption 1674 and checksum algorithms, may not be true of the next algorithms to be 1675 defined, leaving the application protocol unable to make use of those 1676 algorithms without updates to its specification. 1677 1678 The Kerberos protocol uses only the attributes and operations 1679 1680 1681 1682Raeburn [Page 30] 1683 1684INTERNET DRAFT February 2003 1685 1686 1687 described in sections 2 and 3. Preauthentication systems and 1688 application protocols making use of Kerberos are encouraged to use 1689 them as well. The specific key and string-to-key parameters should 1690 generally be treated as opaque. While the string-to-key parameters 1691 are manipulated as an octet string, the representation for the 1692 specific key structure is implementation-defined; it may not even be 1693 a single object. 1694 1695 While we don't recommend it, some application protocols will 1696 undoubtedly continue to use the key data directly, even if only in 1697 some of the currently existing protocol specifications. An 1698 implementation intended to support general Kerberos applications may 1699 therefore need to make the key data available, as well as the 1700 attributes and operations described in sections 2 and 3. [8] 1701 17027. Assigned Numbers 1703 1704 The following encryption type numbers are already assigned or 1705 reserved for use in Kerberos and related protocols. 1706 1707 1708 encryption type etype section or comment 1709 ----------------------------------------------------------------- 1710 des-cbc-crc 1 5.2.3 1711 des-cbc-md4 2 5.2.2 1712 des-cbc-md5 3 5.2.1 1713 [reserved] 4 1714 des3-cbc-md5 5 1715 [reserved] 6 1716 des3-cbc-sha1 7 1717 dsaWithSHA1-CmsOID 9 (pkinit) 1718 md5WithRSAEncryption-CmsOID 10 (pkinit) 1719 sha1WithRSAEncryption-CmsOID 11 (pkinit) 1720 rc2CBC-EnvOID 12 (pkinit) 1721 rsaEncryption-EnvOID 13 (pkinit from PKCS#1 v1.5) 1722 rsaES-OAEP-ENV-OID 14 (pkinit from PKCS#1 v2.0) 1723 des-ede3-cbc-Env-OID 15 (pkinit) 1724 des3-cbc-sha1-kd 16 5.3 1725 aes128-cts-hmac-sha1-96 17 [KRB5-AES] 1726 aes256-cts-hmac-sha1-96 18 [KRB5-AES] 1727 rc4-hmac 23 (Microsoft) 1728 rc4-hmac-exp 24 (Microsoft) 1729 subkey-keymaterial 65 (opaque; PacketCable) 1730 1731 1732 (The "des3-cbc-sha1" assignment is a deprecated version using no key 1733 derivation. It should not be confused with des3-cbc-sha1-kd.) 1734 1735 1736 1737 1738Raeburn [Page 31] 1739 1740INTERNET DRAFT February 2003 1741 1742 1743 Several numbers have been reserved for use in encryption systems not 1744 defined here. Encryption type numbers have unfortunately been 1745 overloaded on occasion in Kerberos-related protocols, so some of the 1746 reserved numbers do not and will not correspond to encryption systems 1747 fitting the profile presented here. 1748 1749 The following checksum type numbers are assigned or reserved. As 1750 with encryption type numbers, some overloading of checksum numbers 1751 has occurred. 1752 1753 1754 Checksum type sumtype checksum section or 1755 value size reference 1756 ---------------------------------------------------------------------- 1757 CRC32 1 4 5.1.3 1758 rsa-md4 2 16 5.1.2 1759 rsa-md4-des 3 24 5.2.5 1760 des-mac 4 16 5.2.7 1761 des-mac-k 5 8 5.2.8 1762 rsa-md4-des-k 6 16 5.2.6 1763 rsa-md5 7 16 5.1.1 1764 rsa-md5-des 8 24 5.2.4 1765 rsa-md5-des3 9 24 ?? 1766 sha1 (unkeyed) 10 20 ?? 1767 hmac-sha1-des3-kd 12 20 5.3 1768 hmac-sha1-des3 13 20 ?? 1769 sha1 (unkeyed) 14 20 ?? 1770 hmac-sha1-96-aes128 15 20 [KRB5-AES] 1771 hmac-sha1-96-aes256 16 20 [KRB5-AES] 1772 [reserved] 0x8003 ? [GSS-KRB5] 1773 1774 1775 Encryption and checksum type numbers are signed 32-bit values. Zero 1776 is invalid, and negative numbers are reserved for local use. All 1777 standardized values must be positive. 1778 17798. Implementation Notes 1780 1781 The "interface" described here is the minimal information that must 1782 be defined to make a cryptosystem useful within Kerberos in an 1783 interoperable fashion. Despite the functional notation used in some 1784 places, it is not an attempt to define an API for cryptographic 1785 functionality within Kerberos. Actual implementations providing 1786 clean APIs will probably find it useful to make additional 1787 information available, which should be possible to derive from a 1788 specification written to the framework given here. For example, an 1789 application designer may wish to determine the largest number of 1790 bytes that can be encrypted without overflowing a certain size output 1791 1792 1793 1794Raeburn [Page 32] 1795 1796INTERNET DRAFT February 2003 1797 1798 1799 buffer, or conversely, the maximum number of bytes that might be 1800 obtained by decrypting a ciphertext message of a given size. (In 1801 fact, an implementation of the GSS-API Kerberos mechanism [GSS-KRB5] 1802 will require some of these.) 1803 1804 The presence of a mechanism in this document should not be taken as 1805 an indication that it must be implemented for compliance with any 1806 specification; required mechanisms will be specified elsewhere. 1807 Indeed, some of the mechanisms described here for backwards 1808 compatibility are now considered rather weak for protecting critical 1809 data. 1810 18119. Security Considerations 1812 1813 Recent years have brought advancements in the ability to perform 1814 large-scale attacks against DES, to such a degree that it is not 1815 considered a strong encryption mechanism any longer; triple-DES is 1816 generally preferred in its place, despite the poorer performance. 1817 See [ESP-DES] for a summary of some of the potential attacks, and 1818 [EFF-DES] for a detailed discussion of the implementation of 1819 particular attack. However, most Kerberos implementations still have 1820 DES as their primary interoperable encryption type. 1821 1822 DES has four 'weak' keys and twelve 'semi-weak' keys, and the use of 1823 single-DES here avoids them. However, DES also has 48 'possibly-weak' 1824 keys [Schneier96] (note that the tables in many editions of the 1825 reference contains errors) which are not avoided. 1826 1827 DES weak keys are keys with the property that E1(E1(P)) = P (where E1 1828 denotes encryption of a single block with key 1). DES semi-weak keys 1829 or "dual" keys are pairs of keys with the property that E1(P) = 1830 D2(P), and thus E2(E1(P)) = P. Because of the use of CBC mode and 1831 leading random confounder, however, these properties are unlikely to 1832 present a security problem. 1833 1834 The use of triple-DES in Kerberos makes no effort to avoid these 1835 keys. The nature of the weak keys is such that it is extremely 1836 unlikely that they will weaken the triple-DES encryption -- only 1837 slightly more likely than having the middle of the three sub-keys 1838 match one of the other two, which effectively converts the encryption 1839 to single-DES, which is another case we make no effort to avoid. 1840 1841 The true CRC-32 checksum is not collision-proof; an attacker could 1842 use a probabilistic chosen-plaintext attack to generate a valid 1843 message even if a confounder is used [SG92]. The use of collision- 1844 proof checksums is of course recommended for environments where such 1845 attacks represent a significant threat. The "simplifications" (read: 1846 bugs) introduced when CRC-32 was implemented for Kerberos cause 1847 1848 1849 1850Raeburn [Page 33] 1851 1852INTERNET DRAFT February 2003 1853 1854 1855 leading zeros to effectively be ignored, so messages differing only 1856 in leading zero bits will have the same checksum. 1857 1858 [HMAC] and [IPSEC-HMAC] discuss weaknesses of the HMAC algorithm. 1859 Unlike [IPSEC-HMAC], the triple-DES specification here does not use 1860 the suggested truncation of the HMAC output. As pointed out in 1861 [IPSEC-HMAC], SHA-1 was not developed to be used as a keyed hash 1862 function, which is a criterion of HMAC. [HMAC-TEST] contains test 1863 vectors for HMAC-SHA-1. 1864 1865 The mit_des_string_to_key function was originally constructed with 1866 the assumption that all input would be ASCII; it ignores the top bit 1867 of each input byte. Folding with XOR is also not an especially good 1868 mixing mechanism in terms of preserving randomness. 1869 1870 The n-fold function used in the string-to-key operation for des3-cbc- 1871 hmac-sha1-kd was designed to cause each bit of input to contribute 1872 equally to the output; it was not designed to maximize or equally 1873 distribute randomness in the input, and there are conceivable cases 1874 of partially structured input where randomness may be lost. This 1875 should only be an issue for highly structured passwords, however. 1876 1877 [RFC1851] discusses the relative strength of triple-DES encryption. 1878 The relative slow speed of triple-DES encryption may also be an issue 1879 for some applications. 1880 1881 This document, like the Kerberos protocol, completely ignores the 1882 notion of limiting the amount of data a key may be used with to a 1883 quantity based on the robustness of the algorithm or size of the key. 1884 It is assumed that any defined algorithms and key sizes will be 1885 strong enough to support very large amounts of data, or they will be 1886 deprecated once significant attacks are known. 1887 1888 This document also places no bounds on the amount of data that can be 1889 handled in various operations. In order to avoid denial of service 1890 attacks, implementations will probably want to restrict message sizes 1891 at some higher level. 1892 189310. IANA Considerations 1894 1895 None at present. The management of encryption and checksum type 1896 number assignments may be transferred to IANA at some future time. 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906Raeburn [Page 34] 1907 1908INTERNET DRAFT February 2003 1909 1910 191111. Acknowledgments 1912 1913 This document is an extension of the encryption specification 1914 included in [Kerb1510] by B. Clifford Neuman and John Kohl, and much 1915 of the text of the background, concepts, and DES specifications are 1916 drawn directly from that document. 1917 1918 The abstract framework presented in this document was put together by 1919 Jeff Altman, Sam Hartman, Jeff Hutzelman, Cliff Neuman, Ken Raeburn, 1920 and Tom Yu, and the details were refined several times based on 1921 comments from John Brezak and others. 1922 1923 Marc Horowitz wrote the original specification of triple-DES and key 1924 derivation in a pair of Internet Drafts (under the names draft- 1925 horowitz-key-derivation and draft-horowitz-kerb-key-derivation) which 1926 were later folded into a draft revision of [Kerb1510], from which 1927 this document was later split off. 1928 1929 Tom Yu provided the text describing the modifications to the standard 1930 CRC algorithm as Kerberos implementations actually use it. 1931 1932 Miroslav Jurisic provided information for one of the UTF-8 test cases 1933 for the string-to-key functions. 1934 1935 Marcus Watts noticed some errors in earlier drafts, and pointed out 1936 that the simplified profile could easily be modified to support 1937 cipher text stealing modes. 1938 1939 Simon Josefsson contributed some clarifications to the DES "CBC 1940 checksum", string-to-key and weak key descriptions, and some test 1941 vectors. 1942 1943 Simon Josefsson, Louis LeVay and others also caught some errors in 1944 earlier drafts. 1945 194612. Editor's address 1947 1948 Kenneth Raeburn 1949 Massachusetts Institute of Technology 1950 77 Massachusetts Avenue 1951 Cambridge, MA 02139 1952 raeburn@mit.edu 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962Raeburn [Page 35] 1963 1964INTERNET DRAFT February 2003 1965 1966 196713. Full Copyright Statement 1968 1969 Copyright (C) The Internet Society (2003). All Rights Reserved. 1970 1971 This document and translations of it may be copied and furnished to 1972 others, and derivative works that comment on or otherwise explain it 1973 or assist in its implementation may be prepared, copied, published 1974 and distributed, in whole or in part, without restriction of any 1975 kind, provided that the above copyright notice and this paragraph are 1976 included on all such copies and derivative works. However, this 1977 document itself may not be modified in any way, such as by removing 1978 the copyright notice or references to the Internet Society or other 1979 Internet organizations, except as needed for the purpose of 1980 developing Internet standards in which case the procedures for 1981 copyrights defined in the Internet Standards process must be 1982 followed, or as required to translate it into languages other than 1983 English. 1984 1985 The limited permissions granted above are perpetual and will not be 1986 revoked by the Internet Society or its successors or assigns. 1987 1988 This document and the information contained herein is provided on an 1989 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 1990 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 1991 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 1992 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 1993 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE." 1994 1995A. Test vectors 1996 1997 This section provides test vectors for various functions defined or 1998 described in this document. For convenience, most inputs are ASCII 1999 strings, though some UTF-8 samples are be provided for string-to-key 2000 functions. Keys and other binary data are specified as hexadecimal 2001 strings. 2002 2003A.1. n-fold 2004 2005 The n-fold function is defined in section 4.1. As noted there, the 2006 sample vector in the original paper defining the algorithm appears to 2007 be incorrect. Here are some test cases provided by Marc Horowitz and 2008 Simon Josefsson: 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018Raeburn [Page 36] 2019 2020INTERNET DRAFT February 2003 2021 2022 2023 64-fold("012345") = 2024 64-fold(303132333435) = be072631276b1955 2025 2026 56-fold("password") = 2027 56-fold(70617373776f7264) = 78a07b6caf85fa 2028 2029 64-fold("Rough Consensus, and Running Code") = 2030 64-fold(526f75676820436f6e73656e7375732c20616e642052756e 2031 6e696e6720436f6465) = bb6ed30870b7f0e0 2032 2033 168-fold("password") = 2034 168-fold(70617373776f7264) = 2035 59e4a8ca7c0385c3c37b3f6d2000247cb6e6bd5b3e 2036 2037 192-fold("MASSACHVSETTS INSTITVTE OF TECHNOLOGY" 2038 192-fold(4d41535341434856534554545320494e5354495456544520 2039 4f4620544543484e4f4c4f4759) = 2040 db3b0d8f0b061e603282b308a50841229ad798fab9540c1b 2041 2042 168-fold("Q") = 2043 168-fold(51) = 2044 518a54a2 15a8452a 518a54a2 15a8452a 2045 518a54a2 15 2046 2047 168-fold("ba") = 2048 168-fold(6261) = 2049 fb25d531 ae897449 9f52fd92 ea9857c4 2050 ba24cf29 7e 2051 2052 Here are some additional values corresponding to folded values of the 2053 string "kerberos"; the 64-bit form is used in the des3 string-to-key 2054 (section 5.3.1). 2055 2056 64-fold("kerberos") = 2057 6b657262 65726f73 2058 128-fold("kerberos") = 2059 6b657262 65726f73 7b9b5b2b 93132b93 2060 168-fold("kerberos") = 2061 8372c236 344e5f15 50cd0747 e15d62ca 2062 7a5a3bce a4 2063 256-fold("kerberos") = 2064 6b657262 65726f73 7b9b5b2b 93132b93 2065 5c9bdcda d95c9899 c4cae4de e6d6cae4 2066 2067 Note that the initial octets exactly match the input string when the 2068 output length is a multiple of the input length. 2069 2070 2071 2072 2073 2074Raeburn [Page 37] 2075 2076INTERNET DRAFT February 2003 2077 2078 2079A.2. mit_des_string_to_key 2080 2081 The function mit_des_string_to_key is defined in section 5.2. We 2082 present here several test values, with some of the intermediate 2083 results. The fourth test demonstrates the use of UTF-8 with three 2084 characters. The last two tests are specifically constructed so as to 2085 trigger the weak-key fixups for the intermediate key produced by fan- 2086 folding; we have no test cases that cause such fixups for the final 2087 key. 2088 2089 2090 UTF-8 encodings used in test vector: 2091 eszett C3 9F s-caron C5 A1 c-acute C4 87 2092 g-clef F0 9D 84 9E 2093 2094 2095 Test vector: 2096 2097 2098 salt: "ATHENA.MIT.EDUraeburn" 2099 415448454e412e4d49542e4544557261656275726e 2100 password: "password" 70617373776f7264 2101 fan-fold result: c01e38688ac86c2e 2102 intermediate key: c11f38688ac86d2f 2103 DES key: cbc22fae235298e3 2104 2105 2106 2107 salt: "WHITEHOUSE.GOVdanny" 5748495445484f5553452e474f5664616e6e79 2108 password: "potatoe" 706f7461746f65 2109 fan-fold result: a028944ee63c0416 2110 intermediate key: a129944fe63d0416 2111 DES key: df3d32a74fd92a01 2112 2113 2114 2115 salt: "EXAMPLE.COMpianist" 4558414D504C452E434F4D7069616E697374 2116 password: g-clef f09d849e 2117 fan-fold result: 3c4a262c18fab090 2118 intermediate key: 3d4a262c19fbb091 2119 DES key: 4ffb26bab0cd9413 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130Raeburn [Page 38] 2131 2132INTERNET DRAFT February 2003 2133 2134 2135 salt: "ATHENA.MIT.EDUJuri" + s-caron + "i" + c-acute 2136 415448454e412e4d49542e4544554a757269c5a169c487 2137 password: eszett c39f 2138 fan-fold result: b8f6c40e305afc9e 2139 intermediate key: b9f7c40e315bfd9e 2140 DES key: 62c81a5232b5e69d 2141 2142 2143 2144 salt: "AAAAAAAA" 4141414141414141 2145 password: "11119999" 3131313139393939 2146 fan-fold result: e0e0e0e0f0f0f0f0 2147 intermediate key: e0e0e0e0f1f1f101 2148 DES key: 984054d0f1a73e31 2149 2150 2151 2152 salt: "FFFFAAAA" 4646464641414141 2153 password: "NNNN6666" 4e4e4e4e36363636 2154 fan-fold result: 1e1e1e1e0e0e0e0e 2155 intermediate key: 1f1f1f1f0e0e0efe 2156 DES key: c4bf6b25adf7a4f8 2157 2158 2159 This trace provided by Simon Josefsson shows the intermediate 2160 processing stages of one of the test inputs: 2161 2162 string_to_key (des-cbc-md5, string, salt) 2163 ;; string: 2164 ;; `password' (length 8 bytes) 2165 ;; 70 61 73 73 77 6f 72 64 2166 ;; salt: 2167 ;; `ATHENA.MIT.EDUraeburn' (length 21 bytes) 2168 ;; 41 54 48 45 4e 41 2e 4d 49 54 2e 45 44 55 72 61 2169 ;; 65 62 75 72 6e 2170 des_string_to_key (string, salt) 2171 ;; String: 2172 ;; `password' (length 8 bytes) 2173 ;; 70 61 73 73 77 6f 72 64 2174 ;; Salt: 2175 ;; `ATHENA.MIT.EDUraeburn' (length 21 bytes) 2176 ;; 41 54 48 45 4e 41 2e 4d 49 54 2e 45 44 55 72 61 2177 ;; 65 62 75 72 6e 2178 odd = 1; 2179 s = string | salt; 2180 2181 2182 2183 2184 2185 2186Raeburn [Page 39] 2187 2188INTERNET DRAFT February 2003 2189 2190 2191 tempstring = 0; /* 56-bit string */ 2192 pad(s); /* with nulls to 8 byte boundary */ 2193 ;; s = pad(string|salt): 2194 ;; `passwordATHENA.MIT.EDUraeburn\x00\x00\x00' 2195 ;; (length 32 bytes) 2196 ;; 70 61 73 73 77 6f 72 64 41 54 48 45 4e 41 2e 4d 2197 ;; 49 54 2e 45 44 55 72 61 65 62 75 72 6e 00 00 00 2198 for (8byteblock in s) { 2199 ;; loop iteration 0 2200 ;; 8byteblock: 2201 ;; `password' (length 8 bytes) 2202 ;; 70 61 73 73 77 6f 72 64 2203 ;; 01110000 01100001 01110011 01110011 01110111 01101111 2204 ;; 01110010 01100100 2205 56bitstring = removeMSBits(8byteblock); 2206 ;; 56bitstring: 2207 ;; 1110000 1100001 1110011 1110011 1110111 1101111 2208 ;; 1110010 1100100 2209 if (odd == 0) reverse(56bitstring); ;; odd=1 2210 odd = ! odd 2211 tempstring = tempstring XOR 56bitstring; 2212 ;; tempstring 2213 ;; 1110000 1100001 1110011 1110011 1110111 1101111 2214 ;; 1110010 1100100 2215 2216 for (8byteblock in s) { 2217 ;; loop iteration 1 2218 ;; 8byteblock: 2219 ;; `ATHENA.M' (length 8 bytes) 2220 ;; 41 54 48 45 4e 41 2e 4d 2221 ;; 01000001 01010100 01001000 01000101 01001110 01000001 2222 ;; 00101110 01001101 2223 56bitstring = removeMSBits(8byteblock); 2224 ;; 56bitstring: 2225 ;; 1000001 1010100 1001000 1000101 1001110 1000001 2226 ;; 0101110 1001101 2227 if (odd == 0) reverse(56bitstring); ;; odd=0 2228 reverse(56bitstring) 2229 ;; 56bitstring after reverse 2230 ;; 1011001 0111010 1000001 0111001 1010001 0001001 2231 ;; 0010101 1000001 2232 odd = ! odd 2233 tempstring = tempstring XOR 56bitstring; 2234 ;; tempstring 2235 ;; 0101001 1011011 0110010 1001010 0100110 1100110 2236 ;; 1100111 0100101 2237 2238 2239 2240 2241 2242Raeburn [Page 40] 2243 2244INTERNET DRAFT February 2003 2245 2246 2247 for (8byteblock in s) { 2248 ;; loop iteration 2 2249 ;; 8byteblock: 2250 ;; `IT.EDUra' (length 8 bytes) 2251 ;; 49 54 2e 45 44 55 72 61 2252 ;; 01001001 01010100 00101110 01000101 01000100 01010101 2253 ;; 01110010 01100001 2254 56bitstring = removeMSBits(8byteblock); 2255 ;; 56bitstring: 2256 ;; 1001001 1010100 0101110 1000101 1000100 1010101 2257 ;; 1110010 1100001 2258 if (odd == 0) reverse(56bitstring); ;; odd=1 2259 odd = ! odd 2260 tempstring = tempstring XOR 56bitstring; 2261 ;; tempstring 2262 ;; 1100000 0001111 0011100 0001111 1100010 0110011 2263 ;; 0010101 1000100 2264 2265 for (8byteblock in s) { 2266 ;; loop iteration 3 2267 ;; 8byteblock: 2268 ;; `eburn\x00\x00\x00' (length 8 bytes) 2269 ;; 65 62 75 72 6e 00 00 00 2270 ;; 01100101 01100010 01110101 01110010 01101110 00000000 2271 ;; 00000000 00000000 2272 56bitstring = removeMSBits(8byteblock); 2273 ;; 56bitstring: 2274 ;; 1100101 1100010 1110101 1110010 1101110 0000000 2275 ;; 0000000 0000000 2276 if (odd == 0) reverse(56bitstring); ;; odd=0 2277 reverse(56bitstring) 2278 ;; 56bitstring after reverse 2279 ;; 0000000 0000000 0000000 0111011 0100111 1010111 2280 ;; 0100011 1010011 2281 odd = ! odd 2282 tempstring = tempstring XOR 56bitstring; 2283 ;; tempstring 2284 ;; 1100000 0001111 0011100 0110100 1000101 1100100 2285 ;; 0110110 0010111 2286 2287 for (8byteblock in s) { 2288 } 2289 ;; for loop terminated 2290 2291 2292 2293 2294 2295 2296 2297 2298Raeburn [Page 41] 2299 2300INTERNET DRAFT February 2003 2301 2302 2303 tempkey = key_correction(add_parity_bits(tempstring)); 2304 ;; tempkey 2305 ;; `\xc1\x1f8h\x8a\xc8m\x2f' (length 8 bytes) 2306 ;; c1 1f 38 68 8a c8 6d 2f 2307 ;; 11000001 00011111 00111000 01101000 10001010 11001000 2308 ;; 01101101 00101111 2309 2310 key = key_correction(DES-CBC-check(s,tempkey)); 2311 ;; key 2312 ;; `\xcb\xc2\x2f\xae\x23R\x98\xe3' (length 8 bytes) 2313 ;; cb c2 2f ae 23 52 98 e3 2314 ;; 11001011 11000010 00101111 10101110 00100011 01010010 2315 ;; 10011000 11100011 2316 2317 ;; string_to_key key: 2318 ;; `\xcb\xc2\x2f\xae\x23R\x98\xe3' (length 8 bytes) 2319 ;; cb c2 2f ae 23 52 98 e3 2320 2321 2322A.3. DES3 DR and DK 2323 2324 These tests show the derived-random and derived-key values for the 2325 des3-hmac-sha1-kd encryption scheme, using the DR and DK functions 2326 defined in section 5.3.1. The input keys were randomly generated; 2327 the usage values are from this specification. 2328 2329 2330 key: dce06b1f64c857a11c3db57c51899b2cc1791008ce973b92 2331 usage: 0000000155 2332 DR: 935079d14490a75c3093c4a6e8c3b049c71e6ee705 2333 DK: 925179d04591a79b5d3192c4a7e9c289b049c71f6ee604cd 2334 2335 key: 5e13d31c70ef765746578531cb51c15bf11ca82c97cee9f2 2336 usage: 00000001aa 2337 DR: 9f58e5a047d894101c469845d67ae3c5249ed812f2 2338 DK: 9e58e5a146d9942a101c469845d67a20e3c4259ed913f207 2339 2340 key: 98e6fd8a04a4b6859b75a176540b9752bad3ecd610a252bc 2341 usage: 0000000155 2342 DR: 12fff90c773f956d13fc2ca0d0840349dbd39908eb 2343 DK: 13fef80d763e94ec6d13fd2ca1d085070249dad39808eabf 2344 2345 key: 622aec25a2fe2cad7094680b7c64940280084c1a7cec92b5 2346 usage: 00000001aa 2347 DR: f8debf05b097e7dc0603686aca35d91fd9a5516a70 2348 DK: f8dfbf04b097e6d9dc0702686bcb3489d91fd9a4516b703e 2349 2350 2351 2352 2353 2354Raeburn [Page 42] 2355 2356INTERNET DRAFT February 2003 2357 2358 2359 key: d3f8298ccb166438dcb9b93ee5a7629286a491f838f802fb 2360 usage: 6b65726265726f73 ("kerberos") 2361 DR: 2270db565d2a3d64cfbfdc5305d4f778a6de42d9da 2362 DK: 2370da575d2a3da864cebfdc5204d56df779a7df43d9da43 2363 2364 key: c1081649ada74362e6a1459d01dfd30d67c2234c940704da 2365 usage: 0000000155 2366 DR: 348056ec98fcc517171d2b4d7a9493af482d999175 2367 DK: 348057ec98fdc48016161c2a4c7a943e92ae492c989175f7 2368 2369 key: 5d154af238f46713155719d55e2f1f790dd661f279a7917c 2370 usage: 00000001aa 2371 DR: a8818bc367dadacbe9a6c84627fb60c294b01215e5 2372 DK: a8808ac267dada3dcbe9a7c84626fbc761c294b01315e5c1 2373 2374 key: 798562e049852f57dc8c343ba17f2ca1d97394efc8adc443 2375 usage: 0000000155 2376 DR: c813f88b3be2b2f75424ce9175fbc8483b88c8713a 2377 DK: c813f88a3be3b334f75425ce9175fbe3c8493b89c8703b49 2378 2379 key: 26dce334b545292f2feab9a8701a89a4b99eb9942cecd016 2380 usage: 00000001aa 2381 DR: f58efc6f83f93e55e695fd252cf8fe59f7d5ba37ec 2382 DK: f48ffd6e83f83e7354e694fd252cf83bfe58f7d5ba37ec5d 2383 2384 2385A.4. DES3string_to_key 2386 2387 These are the keys generated for some of the above input strings for 2388 triple-DES with key derivation as defined in section 5.3.1. 2389 2390 salt: "ATHENA.MIT.EDUraeburn" 2391 passwd: "password" 2392 key: 850bb51358548cd05e86768c313e3bfef7511937dcf72c3e 2393 2394 salt: "WHITEHOUSE.GOVdanny" 2395 passwd: "potatoe" 2396 key: dfcd233dd0a43204ea6dc437fb15e061b02979c1f74f377a 2397 2398 salt: "EXAMPLE.COMbuckaroo" 2399 passwd: "penny" 2400 key: 6d2fcdf2d6fbbc3ddcadb5da5710a23489b0d3b69d5d9d4a 2401 2402 salt: "ATHENA.MIT.EDUJuri" + s-caron + "i" + c-acute 2403 passwd: eszett 2404 key: 16d5a40e1ce3bacb61b9dce00470324c831973a7b952feb0 2405 2406 2407 2408 2409 2410Raeburn [Page 43] 2411 2412INTERNET DRAFT February 2003 2413 2414 2415 salt: "EXAMPLE.COMpianist" 2416 passwd: g-clef 2417 key: 85763726585dbc1cce6ec43e1f751f07f1c4cbb098f40b19 2418 2419A.5. Modified CRC-32 2420 2421 Below are modified-CRC32 values for various ASCII and octet strings. 2422 Only the printable ASCII characters are checksummed, no C-style 2423 trailing zero-valued octet. The 32-bit modified CRC and the sequence 2424 of output bytes as used in Kerberos are shown. (The octet values are 2425 separated here to emphasize that they are octet values and not 32-bit 2426 numbers, which will be the most convenient form for manipulation in 2427 some implementations. The bit and byte order used internally for 2428 such a number is irrelevant; the octet sequence generated is what is 2429 important.) 2430 2431 2432 mod-crc-32("foo") = 33 bc 32 73 2433 mod-crc-32("test0123456789") = d6 88 3e b8 2434 mod-crc-32("MASSACHVSETTS INSTITVTE OF TECHNOLOGY") = f7 80 41 e3 2435 mod-crc-32(8000) = 4b 98 83 3b 2436 mod-crc-32(0008) = 32 88 db 0e 2437 mod-crc-32(0080) = 20 83 b8 ed 2438 mod-crc-32(80) = 20 83 b8 ed 2439 mod-crc-32(80000000) = 3b b6 59 ed 2440 mod-crc-32(00000001) = 96 30 07 77 2441 2442 2443B. Significant Changes from RFC 1510 2444 2445 The encryption and checksum mechanism profiles are new. The old 2446 specification defined a few operations for various mechanisms, but 2447 didn't outline what should be required of new mechanisms in terms of 2448 abstract properties, nor how to ensure that a mechanism specification 2449 is complete enough for interoperability between implementations. The 2450 new profiles do differ from the old specification in a few ways: 2451 2452 Some message definitions in [Kerb1510] could be read as permitting 2453 the initial vector to be specified by the application; the text 2454 was too vague. It is specifically not permitted in this 2455 specification. Some encryption algorithms may not use 2456 initialization vectors, so relying on chosen, secret 2457 initialization vectors for security is unwise. Also, the 2458 prepended confounder in the existing algorithms is roughly 2459 equivalent to a per-message initialization vector that is revealed 2460 in encrypted form. However, carrying state across from one 2461 encryption to another is explicitly permitted through the opaque 2462 "cipher state" object. 2463 2464 2465 2466Raeburn [Page 44] 2467 2468INTERNET DRAFT February 2003 2469 2470 2471 The use of key derivation is new. 2472 2473 Several new methods are introduced, including generation of a key 2474 in wire-protocol format from random input data. 2475 2476 The means for influencing the string-to-key algorithm are laid out 2477 more clearly. 2478 2479 Triple-DES support is new. 2480 2481 The pseudo-random function is new. 2482 2483 The des-cbc-crc, DES string-to-key and CRC descriptions have been 2484 updated to align them with existing implementations. 2485 2486 [Kerb1510] had no indication what character set or encoding might be 2487 used for pass phrases and salts. 2488 2489 In [Kerb1510], key types, encryption algorithms and checksum 2490 algorithms were only loosely associated, and the association was not 2491 well described. In this specification, key types and encryption 2492 algorithms have a one-to-one correspondence, and associations between 2493 encryption and checksum algorithms are described so that checksums 2494 can be computed given negotiated keys, without requiring further 2495 negotiation for checksum types. 2496 2497Notes 2498 2499 [1] While Message Authentication Code (MAC) or Message Integrity 2500 Check (MIC) would be more appropriate terms for many of the 2501 uses in this document, we continue to use the term "checksum" 2502 for historical reasons. 2503 2504 [2] Extending CBC mode across messages would be one obvious 2505 example of this chaining. Another might be the use of 2506 counter mode, with a counter randomly initialized and 2507 attached to the ciphertext; a second message could continue 2508 incrementing the counter when chaining the cipher state, thus 2509 avoiding having to transmit another counter value. However, 2510 this chaining is only useful for uninterrupted, ordered 2511 sequences of messages. 2512 2513 [3] In the case of Kerberos, the encrypted objects will generally 2514 be ASN.1 DER encodings, which contain indications of their 2515 length in the first few octets. 2516 2517 [4] As of the time of this writing, some new modes of operation 2518 have been proposed, some of which may permit encryption and 2519 2520 2521 2522Raeburn [Page 45] 2523 2524INTERNET DRAFT February 2003 2525 2526 2527 integrity protection simultaneously. After some of these 2528 proposals have been subjected to adequate analysis, we may 2529 wish to formulate a new simplified profile based on one of 2530 them. 2531 2532 [5] It should be noted that the sample vector in Appendix B.2 of 2533 the original paper appears to be incorrect. Two independent 2534 implementations from the specification (one in C by Marc 2535 Horowitz, and another in Scheme by Bill Sommerfeld) agree on 2536 a value different from that in [Blumenthal96]. 2537 2538 [6] For example, in MIT's implementation of [Kerb1510], the rsa- 2539 md5 unkeyed checksum of application data may be included in 2540 an authenticator encrypted in a service's key; since rsa-md5 2541 is believed to be collision-proof, even if the application 2542 data is exposed to an attacker, it cannot be modified without 2543 causing the checksum verification to fail. 2544 2545 [7] A variant of the key is used to limit the use of a key to a 2546 particular function, separating the functions of generating a 2547 checksum from other encryption performed using the session 2548 key. The constant 0xF0F0F0F0F0F0F0F0 was chosen because it 2549 maintains key parity. The properties of DES precluded the 2550 use of the complement. The same constant is used for similar 2551 purpose in the Message Integrity Check in the Privacy 2552 Enhanced Mail standard. 2553 2554 [8] Perhaps one of the more common reasons for directly 2555 performing encryption is direct control over the negotiation 2556 and to select a "sufficiently strong" encryption algorithm 2557 (whatever that means in the context of a given application). 2558 While Kerberos directly provides no facility for negotiating 2559 encryption types between the application client and server, 2560 there are other means for accomplishing similar goals. For 2561 example, requesting only "strong" session key types from the 2562 KDC, and assuming that the type actually returned by the KDC 2563 will be understood and supported by the application server. 2564 2565Normative References 2566 2567 [Bellare98] 2568 Bellare, M., Desai, A., Pointcheval, D., and P. Rogaway, 2569 "Relations Among Notions of Security for Public-Key Encryption 2570 Schemes". Extended abstract published in Advances in Cryptology- 2571 Crypto 98 Proceedings, Lecture Notes in Computer Science Vol. 2572 1462, H. Krawcyzk ed., Springer-Verlag, 1998. 2573 2574 2575 2576 2577 2578Raeburn [Page 46] 2579 2580INTERNET DRAFT February 2003 2581 2582 2583 [Blumenthal96] 2584 Blumenthal, U., and S. Bellovin, "A Better Key Schedule for DES- 2585 Like Ciphers", Proceedings of PRAGOCRYPT '96, 1996. 2586 [CRC] 2587 International Organization for Standardization, "ISO Information 2588 Processing Systems - Data Communication - High-Level Data Link 2589 Control Procedure - Frame Structure," IS 3309, 3rd Edition, 2590 October 1984. 2591 [DES77] 2592 National Bureau of Standards, U.S. Department of Commerce, "Data 2593 Encryption Standard," Federal Information Processing Standards 2594 Publication 46, Washington, DC, 1977. 2595 [DESI81] 2596 National Bureau of Standards, U.S. Department of Commerce, 2597 "Guidelines for implementing and using NBS Data Encryption 2598 Standard," Federal Information Processing Standards Publication 2599 74, Washington, DC, 1981. 2600 [DESM80] 2601 National Bureau of Standards, U.S. Department of Commerce, "DES 2602 Modes of Operation," Federal Information Processing Standards 2603 Publication 81, Springfield, VA, December 1980. 2604 [Dolev91] 2605 Dolev, D., Dwork, C., Naor, M., "Non-malleable cryptography", 2606 Proceedings of the 23rd Annual Symposium on Theory of Computing, 2607 ACM, 1991. 2608 [HMAC] 2609 Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed-Hashing 2610 for Message Authentication", RFC 2104, February 1997. 2611 [KRB5-AES] 2612 Raeburn, K., "AES Encyrption for Kerberos 5", RFC XXXX, Xxxxxxxx 2613 2003. 2614 [MD4-92] 2615 Rivest, R., "The MD4 Message Digest Algorithm," RFC 1320, MIT 2616 Laboratory for Computer Science, April 1992. 2617 [MD5-92] 2618 Rivest, R., "The MD5 Message Digest Algorithm," RFC 1321, MIT 2619 Laboratory for Computer Science, April 1992. 2620 [RFC2026] 2621 Bradner, S., "The Internet Standards Process -- Revisions 3," RFC 2622 2026, October 1996. 2623 [SG92] 2624 Stubblebine, S., and V. D. Gligor, "On Message Integrity in 2625 Cryptographic Protocols," in Proceedings of the IEEE Symposium on 2626 Research in Security and Privacy, Oakland, California, May 1992. 2627 2628 2629 2630 2631 2632 2633 2634Raeburn [Page 47] 2635 2636INTERNET DRAFT February 2003 2637 2638 2639Informative References 2640 2641 [EFF-DES] 2642 Electronic Frontier Foundation, "Cracking DES: Secrets of 2643 Encryption Research, Wiretap Politics, and Chip Design", O'Reilly 2644 & Associates, Inc., May 1998. 2645 [ESP-DES] 2646 Madson, C., and N. Doraswamy, "The ESP DES-CBC Cipher Algorithm 2647 With Explicit IV", RFC 2405, November 1998. 2648 [GSS-KRB5] 2649 Linn, J., "The Kerberos Version 5 GSS-API Mechanism," RFC 1964, 2650 June 1996. 2651 [HMAC-TEST] 2652 Cheng, P., and R. Glenn, "Test Cases for HMAC-MD5 and HMAC-SHA-1", 2653 RFC 2202, September 1997. 2654 [IPSEC-HMAC] 2655 Madson, C., and R. Glenn, "The Use of HMAC-SHA-1-96 within ESP and 2656 AH", RFC 2404, November 1998. 2657 [Kerb] 2658 Neuman, C., Kohl, J., Ts'o, T., Yu, T., Hartman, S., and K. 2659 Raeburn, "The Kerberos Network Authentication Service (V5)", 2660 draft-ietf-krb-wg-kerberos-clarifications-00.txt, February 22, 2661 2002. Work in progress. 2662 [Kerb1510] 2663 Kohl, J., and C. Neuman, "The Kerberos Network Authentication 2664 Service (V5)", RFC 1510, September 1993. 2665 [RC5] 2666 Baldwin, R, and R. Rivest, "The RC5, RC5-CBC, RC5-CBC-Pad, and 2667 RC5-CTS Algorithms", RFC 2040, October 1996. 2668 [Schneier96] 2669 Schneier, B., "Applied Cryptography Second Edition", John Wiley & 2670 Sons, New York, NY, 1996. ISBN 0-471-12845-7. 2671 2672Notes to RFC Editor 2673 2674 Before publication of this document as an RFC, the following changes 2675 are needed: 2676 2677 Change the reference "[KRB5-AES]" in Normative References to indicate 2678 the AES draft (draft-raeburn-krb-rijndael-krb-XX) that should be 2679 advancing to RFC at the same time. The RFC number and publication 2680 date are needed. 2681 2682 If draft-ietf-krb-wg-kerberos-clarifications advances to RFC at the 2683 same time as this document, change the information for [Kerb] in the 2684 Informative References section as well. 2685 2686 Delete this section. 2687 2688 2689 2690Raeburn [Page 48] 2691