Kerberos Working Group K. Raeburn Document: draft-ietf-krb-wg-crypto-00.txt MIT January 5, 2002 expires July 5, 2002 Encryption and Checksum Specifications for Kerberos 5 Abstract The Kerberos protocol [Kerb] uses cryptography to protect messages of various sizes, using stream encryption ciphers, or more commonly, block encryption ciphers with block chaining. This document describes a framework for defining encryption and checksum mechanisms, defining an abstraction layer between the Kerberos protocol and related protocols, and the actual mechanism specifications. This should allow either side to be extended more cleanly without requiring changes to the other. Several mechanisms are also defined in this document. Some are taken from RFC 1510, modified in form to fit this new framework, and occasionally modified in content when the old specification was incorrect. Some new mechanisms are presented here as well. No requirements for implementation of specific mechanisms are made here. Status This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026 [RFC2026]. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.html. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Raeburn [Page 1] INTERNET DRAFT January 2002 Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Status . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . 2 Work Still Needed . . . . . . . . . . . . . . . . . . . . . . . . . 3 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Encryption mechanism attributes . . . . . . . . . . . . . . . . . 5 3. Checksum mechanism attributes . . . . . . . . . . . . . . . . . . 8 4. Simplified profile for CBC-mode ciphers with key derivation . . . 9 4.1. A key derivation function [Horowitz] . . . . . . . . . . . . . 10 4.2. Simplified profile parameters . . . . . . . . . . . . . . . . . 12 4.3. Cryptosystem profile based on simplified profile . . . . . . . 13 4.4. Checksum profiles based on simplified profile . . . . . . . . . 15 5. Profiles for Kerberos encryption systems . . . . . . . . . . . . 15 5.1. null . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.2. DES-based encryption systems . . . . . . . . . . . . . . . . . 17 5.3. Triple-DES Encryption with Key Derivation . . . . . . . . . . . 23 6. Profiles for Kerberos checksums . . . . . . . . . . . . . . . . . 25 6.1. RSA MD4 Cryptographic Checksum Using DES . . . . . . . . . . . 25 6.2. The RSA MD5 Checksum . . . . . . . . . . . . . . . . . . . . . 26 6.3. RSA MD5 Cryptographic Checksum Using DES . . . . . . . . . . . 26 6.4. The CRC-32 Checksum . . . . . . . . . . . . . . . . . . . . . . 27 6.5. The RSA MD4 Checksum . . . . . . . . . . . . . . . . . . . . . 28 6.6. DES CBC checksum . . . . . . . . . . . . . . . . . . . . . . . 28 6.7. RSA MD4 Cryptographic Checksum Using DES alternative . . . . . 29 6.8. DES CBC checksum alternative . . . . . . . . . . . . . . . . . 30 6.9. The HMAC-SHA1-DES3-KD Checksum . . . . . . . . . . . . . . . . 30 7. Use of Kerberos encryption outside this specification . . . . . . 30 8. Assigned Numbers . . . . . . . . . . . . . . . . . . . . . . . . 31 9. Notes to Implementors . . . . . . . . . . . . . . . . . . . . . . 33 10. Security Considerations . . . . . . . . . . . . . . . . . . . . 33 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . 33 12. Editor's address . . . . . . . . . . . . . . . . . . . . . . . . 34 13. Full Copyright Statement . . . . . . . . . . . . . . . . . . . . 34 A. Test vectors . . . . . . . . . . . . . . . . . . . . . . . . . . 35 A.1. n-fold . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 A.2. mit_des_string_to_key . . . . . . . . . . . . . . . . . . . . . 35 A.3. DES3 DR and DK . . . . . . . . . . . . . . . . . . . . . . . . 37 A.4. DES3string_to_key . . . . . . . . . . . . . . . . . . . . . . . 38 A.5. DES3 combine-keys . . . . . . . . . . . . . . . . . . . . . . . 39 A.6. Modified CRC-32 . . . . . . . . . . . . . . . . . . . . . . . . 39 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Normative References . . . . . . . . . . . . . . . . . . . . . . . . 40 Informative References . . . . . . . . . . . . . . . . . . . . . . . 41 Raeburn [Page 2] INTERNET DRAFT January 2002 Work Still Needed More talking with cryptographers about the "combine-keys" function in the simplified profile. I've been talking a little with Uri Blumenthal, but he hasn't had a lot of time for this. More detailed list of differences from RFC 1510, to update the "Significant changes" appendix. Are sections 2 and 3 what we want to recommend for external use in section 7, or just a subset? Look up reference to Bellovin paper on CBC mode use of key as IV being a bad idea. Fix anything marked with "@@". Fix up references section. Encoding of strings? Someone remind me, why does get_mic have to produce a fixed-size output? Guidelines for mechanism designers for what to document -- something akin to section 4 of RFC 2411 would make sense. Introduction @@ needs update for separation from kerberos-revisions The Kerberos protocols are designed to encrypt blocks of arbitrary sizes, using stream encryption ciphers, or more commonly, block encryption ciphers such as the Data Encryption Standard [DES77] in conjunction with block chaining and checksum methods [DESM80]. Encryption is used to prove the identities of the network entities participating in message exchanges. The Key Distribution Center for each realm is trusted by all principals registered in that realm to store a secret key in confidence. Proof of knowledge of this secret key is used to verify the authenticity of a principal. The Kerberos protocols generally assume that the encryption used is secure from cryptanalysis; however, in some cases, the order of fields in the encrypted portions of messages as defined in this section is chosen to mitigate somewhat the effects of poorly chosen keys under certain types of cryptographic attacks. It is still important to choose good keys. If keys are derived from user-typed passwords, those passwords need to be well chosen to make brute force Raeburn [Page 3] INTERNET DRAFT January 2002 attacks more difficult. Poorly chosen keys still make easy targets for intruders. The following sections specify the encryption and checksum mechanisms currently defined for Kerberos, as well as a framework for defining future mechanisms. The encodings, chaining, padding and other requirements for each are described. Test vectors for several functions are given in appendix A. 1. Concepts Both encryption and checksum mechanisms are defined in terms of profiles, detailed in later sections. Each specifies a collection of operations and attributes that must be defined for a mechanism. A Kerberos encryption or checksum mechanism specification is not complete if it does not define all of these operations and attributes. An encryption mechanism must provide for confidentiality and integrity of the original plaintext. (Integrity checking may be achieved by incorporating a checksum, if the encryption mode does not provide an integrity check itself.) It must also provide non- malleability [Bellare98, Dolev91]. Use of a random confounder prepended to the plaintext is recommended. It should not be possible to determine if two ciphertexts correspond to the same plaintext, without knowledge of the key. A checksum mechanism [1] must provide proof of the integrity of the associated message, and must preserve the confidentiality of the message in case it is not sent in the clear. It should be infeasible to find two plaintexts which have the same checksum. It is NOT required that an eavesdropper be unable to determine if two checksums are for the same message; it is assumed that the messages themselves will be visible to any such eavesdropper. Due to advances in cryptography, it is considered unwise by some cryptographers to use the same key for multiple purposes [@@reference??]. Since keys are used in performing a number of different functions in Kerberos, it is desirable to use different keys for each of these purposes, even though we start with a single long-term or session key. We do this by enumerating the different uses of keys within Kerberos, and making the "usage number" an input to the encryption or checksum mechanisms; this enumeration is outside the scope of this document. Later sections of this document define simplified profile templates for encryption and checksum mechanisms that use a key derivation Raeburn [Page 4] INTERNET DRAFT January 2002 function applied to a CBC mode (or similar) cipher and a checksum or hash algorithm. We distinguish the "base key" specified by other documents from the "specific key" to be used for a particular instance of encryption or checksum operations. It is expected but not required that the specific key will be one or more separate keys derived from the original protocol key and the key usage number. The specific key should not be explicitly referenced outside of this document. The typical language used in other documents should be something like, "encrypt this octet string using this key and this usage number"; generation of the specific key and cipher state (described in the next section) are implicit. (The creation of a new cipher-state object, or the re-use of one from a previous encryption operation, may also be explicit.) New protocols defined in terms of the Kerberos encryption and checksum types should use their own key usage values. Key usages are unsigned 32 bit integers; zero is not permitted. 2. Encryption mechanism attributes An encryption mechanism profile must define the following attributes and operations. The operations must be defined as functions in the mathematical sense: no additional or implicit inputs (such as Kerberos principal names or message sequence numbers) are permitted. protocol key format This describes what octet string values represent valid keys. For encryption mechanisms that don't have perfectly dense key spaces, this will describe the representation used for encoding keys. It need not describe specific values that are not valid or desirable for use; such values should be avoid by all key generation routines. specific key structure This is not a protocol format at all, but a description of the keying material derived from the chosen key and used to encrypt or decrypt data or compute or verify a checksum. It may, for example, be a single key, a set of keys, or a combination of the original key with additional data. The authors recommend using one or more keys derived from the original key via one-way functions. required checksum mechanism This indicates a checksum mechanism that must be available when this encryption mechanism is used. Since Kerberos has no built in mechanism for negotiating checksum mechanisms, once an encryption Raeburn [Page 5] INTERNET DRAFT January 2002 mechanism has been decided upon, the corresponding checksum mechanism can simply be used. key-generation seed length, K This is the length of the random bitstring needed to generate a key with the encryption scheme's random-to-key function (described below). This must be a fixed value so that various techniques for producing a random bitstring of a given length may be used with key generation functions. key generation functions Keys must be generated in a number of cases, from different types of inputs. All function specifications must indicate how to generate keys in the proper wire format, and must avoid generation of "weak" keys if the cryptosystem has such. Entropy from each source should be preserved as much as possible. Many of the inputs, while unknown, may be at least partly predictable (e.g., a password string is likely to be entirely in the ASCII subset and of fairly short length in many environments; a semi-random string may include timestamps); the benefit of such predictability to an attacker must be minimized. string-to-key (UTF8String, UTF8String, params)->(protocol-key) This function generates a key from two UTF-8 strings and an integer. One of the strings is normally the principal's password, but is in general merely a secret string. The other string is a "salt" string intended to produce different keys from the same password for different users or realms. The third argument, "params", may be used to pass mechanism- specific parameters in to this function. Since doing so implies knowledge of the specific encryption system, it is intended that this be an uncommon operation done only through special administrative interfaces, and that normal Kerberos applications be able to treat this parameter block as an opaque object. This should be a one-way function, so that compromising a user's key in one realm does not compromise the user's key in another realm, even if the same password (but a different salt string) is used. random-to-key (bitstring[K])->(protocol-key) This function generates a key from a random bit string of a specific size. It may be assumed that all the bits of the input string are equally random, even though the entropy present in the random source may be limited. Raeburn [Page 6] INTERNET DRAFT January 2002 combine-keys (protocol-key, protocol-key)->(protocol-key) This function takes two input keys and produces a new key. This function is not used in the basic Kerberos protocol, but may be used by preauthentication methods or other applications to be defined later. This operation must be commutative; this requirement lets us specify "combine keys A and B" in other documents without worrying about ordering. key-derivation (protocol-key, integer)->(specific-key) In this function, the integer input is the key usage value as described above; the usage values must be assumed to be known to an attacker. For cryptosystems with dense key spaces, this function should be something like the key derivation function outlined in section 1. default string-to-key parameters (octet string) This default value for the "params" argument to the string-to-key function is to be used when the application protocol (Kerberos or otherwise) does not explicitly set the parameter value. As indicated above, this parameter block should be treated as an opaque object in most cases. cipher state initial cipher state (specific-key)->(state) This describes any initial state setup needed before encrypting arbitrary amounts of data with a given specific key; the specific key must be the only input needed for this initialization. For example, a block cipher used in CBC mode must specify an initial vector. (For security reasons, the key itself should not be used as the IVEC.) This data may be carried over from one encryption or decryption operation to another. Unless otherwise specified, however, each encryption or decryption operation in this RFC uses a freshly initialized state and is thus independent of all other encryptions and decryptions. This state should be treated as opaque in any uses outside of an encryption algorithm definition. encrypt (specific-key, state, bytestring)->(state, bytestring) This function takes the specific key, cipher state, and plaintext as input, and generates ciphertext and a new cipher state as outputs. If the basic encryption algorithm itself does not provide for integrity protection (as DES in CBC mode does not do), then some form of MAC or checksum must be included that can be verified by the receiver. Some random factor such as a confounder should be included so that an observer cannot know if two messages contain the same plaintext, even if the cipher state and specific keys are the same. The exact length of the plaintext need not be Raeburn [Page 7] INTERNET DRAFT January 2002 encoded, but if it is not and if padding is required, the padding must be added at the end of the string so that the decrypted version may be parsed from the beginning. The specification of the encryption function must not only indicate the precise contents of the output bytestring, but also the output cipher state, if that state is not empty. The application protocol may carry forward the output cipher state from one encryption with a given specific key to another; the effect of this "chaining" must be defined, even if only to say that it has no effect. Assuming correctly-produced values for the specific key and cipher state, no input byte string may result in an error indication. decrypt (specific-key, state, bytestring)->(state, bytestring) This function takes the specific key, cipher state, and ciphertext as inputs, and verifies the integrity of the supplied ciphertext. If the ciphertext's integrity is intact, this function produces the plaintext and a new cipher state as outputs; otherwise, an error indication must be returned, and the data discarded. The result of the decryption may be longer than the original plaintext, if the encryption mode requires padding to a multiple of a block size. If this is the case, any extra padding will be after the decoded plaintext. An application protocol which needs to know the exact length of the message must encode a length or recognizable "end of message" marker within the plaintext. [2] As with the encryption function, a correct specification for this function must indicate not only the contents of the output byte string, but also the resulting cipher state. These operations and attributes are all that should be required to support Kerberos and various proposed preauthentication schemes. 3. Checksum mechanism attributes A checksum mechanism profile must define the following attributes and operations: associated encryption algorithm(s) This essentially indicates the type of encryption key this checksum mechanism can be used with. A single checksum mechanism may have more than one associated encryption algorithm if they share the same wire key format, string-to-key function, and key derivation function. (This combination means that, for example, a checksum type and password are adequate to get the specific key Raeburn [Page 8] INTERNET DRAFT January 2002 used to compute a checksum.) get_mic function This function generates a MIC token for a given specific key (see section 2), and message (represented as an octet string), that may be used to verify the integrity of the associated message. This function is not required to return the same deterministic result on every use; it need only generate a token that the verify_mic routine can check. The output of this function will also dictate the size of the checksum. It must be a fixed size. verify_mic function Given a specific key, message, and MIC token, this function ascertains whether the message integrity has been compromised. For a deterministic get_mic routine, the corresponding verify_mic may simply generate another checksum and compare them. The get_mic and verify_mic operations must be able to handle inputs of arbitrary length; if any padding is needed, the padding scheme must be specified as part of these functions. These operations and attributes are all that should be required to support Kerberos and various proposed preauthentication schemes. 4. Simplified profile for CBC-mode ciphers with key derivation The profile outlines in sections 2 and 3 describes a large number of operations that must be defined for encryption and checksum algorithms to be used with Kerberos. We describe here a simpler profile from which both encryption and checksum mechanism definitions can be generated, filling in uses of key derivation in appropriate places, providing integrity protection, and defining multiple operations for the cryptosystem profile based on a smaller set of operations given in the simplified profile. Not all of the existing cryptosystems for Kerberos fit into this simplified profile, but we recommend that future cryptosystems use it or something based on it. [3] Not all of the operations in the complete profiles are defined through this mechanism; several must still be defined for each new algorithm pair. Raeburn [Page 9] INTERNET DRAFT January 2002 4.1. A key derivation function [Horowitz] Rather than define some scheme by which a "protocol key" is composed of a large number of encryption keys, we use keys derived from a base key to perform cryptographic operations. The base key must be used only for generating the derived keys, and this derivation must be non-invertible and entropy-preserving. Given these restrictions, compromise of one derived key does not compromise the other subkeys. Attack of the base key is limited, since it is only used for derivation, and is not exposed to any user data. Since the derived key has as much entropy as the base keys (if the cryptosystem is good), password-derived keys have the full benefit of all the entropy in the password. To generate a derived key from a base key, we generate a pseudorandom byte string, using an algorithm DR described below, and generate a key from that byte string using a function dependent on the encryption algorithm; the input length needed for that function, which is also dependent on the encryption algorithm, dictates the length of the string to be generated by the DR algorithm (the value "k" below). Derived Key = DK(Base Key, Well-Known Constant) DK(Key, Constant) = random-to-key(DR(Key, Constant)) DR(Key, Constant) = k-truncate(E(Key, Constant)) Here DR is the random-byte generation function described below, and DK is the key-derivation function produced from it. In this construction, E(Key, Plaintext) is a block cipher, Constant is a well-known constant determined by the specific usage of this function, and k-truncate truncates its argument by taking the first k bits. Here, k is the key generation seed length needed for the encryption system. The output of the DR function is a string of bits; the actual key is produced by applying the cryptosystem's random-to-key operation on this bitstring. If the output of E is shorter than k bits, then some entropy in the key will be lost. If the Constant is smaller than the block size of E, then it must be padded so it may be encrypted. In either of these situations, a variation of the above construction is used, where the folded Constant is encrypted, and the resulting output is fed back into the encryption as necessary (the | indicates Raeburn [Page 10] INTERNET DRAFT January 2002 concatentation): K1 = E(Key, n-fold(Constant)) K2 = E(Key, K1) K3 = E(Key, K2) K4 = ... DR(Key, Constant) = k-truncate(K1 | K2 | K3 | K4 ...) n-fold is an algorithm which takes m input bits and ``stretches'' them to form n output bits with equal contribution from each input bit to the output, as described in [Blumenthal96]: We first define a primitive called n-folding, which takes a variable-length input block and produces a fixed-length output sequence. The intent is to give each input bit approximately equal weight in determining the value of each output bit. Note that whenever we need to treat a string of bytes as a number, the assumed representation is Big-Endian -- Most Significant Byte first. To n-fold a number X, replicate the input value to a length that is the least common multiple of n and the length of X. Before each repetition, the input is rotated to the right by 13 bit positions. The successive n-bit chunks are added together using 1's-complement addition (that is, with end-around carry) to yield a n-bit result.... Test vectors for n-fold are supplied in Appendix A. [4] In this document, n-fold is always used to produce n bits of output, where n is the block size of E. The size of the Constant must not be larger than the block size of E, because reducing the length of the Constant by n-folding can cause collisions. If the size of the Constant is smaller than the block size of E, then the Constant must be n-folded to the block size of E. This string is used as input to E. If the block size of E is less than the key size, then the output from E is taken as input to a second invocation of E. This process is repeated until the number of bits accumulated is greater than or equal to the key size of E. When enough bits have been computed, the first k are taken as the derived key. Since the derived key is the result of one or more encryptions in the base key, deriving the base key from the derived key is equivalent to Raeburn [Page 11] INTERNET DRAFT January 2002 determining the key from a very small number of plaintext/ciphertext pairs. Thus, this construction is as strong as the cryptosystem itself. 4.2. Simplified profile parameters These are the operations and attributes that must be defined: protocol key format string-to-key function default string-to-key parameters key-generation seed length, k random-to-key function As above for the normal encryption mechanism profile. unkeyed hash algorithm, H This should be a collision-resistant hash algorithm such as SHA-1, suitable for use in an HMAC. It must support inputs of arbitrary length. encryption block size, n encryption/decryption functions, E and D These are basic encryption and decryption functions for messages of sizes that are multiples of the block size. No integrity checking or confounder should be included here. They take as input the IV or similar data, a protocol-format key, and a byte string, returning a new IV and byte string. The encryption function is not required to use CBC mode, but is assumed to be using something with similar properties. In particular, prepending a one-block confounder to the plaintext should alter the entire ciphertext (comparable to choosing and including a random initial vector for CBC mode). While there are still a number of properties to specify, they are fewer and simpler than in the full profile. Raeburn [Page 12] INTERNET DRAFT January 2002 4.3. Cryptosystem profile based on simplified profile cryptosystem from simplified profile ---------------------------------------------------------------------- protocol key format As given. specific key structure Three protocol-format keys: { Kc, Ke, Ki }. key-generation seed As given. length required checksum The checksum mechanism defined by the mechanism simplified checksum profile given later. cipher state CBC initial vector (one block), initialized to all zero. encryption function The ciphertext output is the concatenation of the output of the basic encryption function E and an HMAC using the specified hash function H, both applied to the padded plaintext with a confounder: C1 = E(Ke, conf | plaintext | pad) H1 = HMAC(Ki, conf | plaintext | pad) ciphertext = C1 | H1 newstate.ivec = last block of C1 One block of random confounder data is prepended to the plaintext, and padding added to the end to bring the length to a multiple of the encryption algorithm's block size. The initial vector for encryption is supplied by the cipher state, and the last block of the output of E is the new IVEC for the new cipher state. Raeburn [Page 13] INTERNET DRAFT January 2002 cryptosystem from simplified profile ---------------------------------------------------------------------- decryption function Decryption is performed by extracting the encrypted portion of the ciphertext, decrypting using key Ke from the specific key, and verifying the HMAC. If the HMAC is incorrect, an error must be reported. Otherwise, the confounder and padding are discarded and the remaining plaintext returned. As with encryption, the cipher state input indicates the IVEC to use, and the last block of the encrypted portion of the ciphertext is put into the new cipher state to be used as the next IVEC. default string-to-key As given. params key generation functions: string-to-key function As given. random-to-key function As given. combine-keys function @@ Needs to be specified. How about: combine-keys(K1,K2) /* First, protect original keys against exposure with DR. */ R1 = DR(K1, n-fold(K2)) /* length k */ R2 = DR(K2, n-fold(K1)) /* length k */ /* Using k-fold on length 2k means just add with wrap-around carry. */ rnd = k-fold(R1 | R2) tkey = random-to-key(rnd) key = DK(tkey, CombineConstant) Here CombineConstant is the byte string {0x63 0x6f 0x6d 0x62 0x69 0x6e 0x65} corresponding to the ASCII encoding of the string "combine". @@ Need a cryptographer to review this. Asked Uri Blumenthal, he said he'd look it over when he has time. Have some suggestions from him, not incorporated yet. Raeburn [Page 14] INTERNET DRAFT January 2002 cryptosystem from simplified profile ---------------------------------------------------------------------- key-derivation function Three keys are generated, using the DK function described above, and the key usage number, represented as a 32-bit integer in big-endian byte order. One is used for generating checksums only; the other two are used for encrypting and integrity protection for ciphertext. These keys are generated as follows: Kc = DK(base-key, usage | 0x99); Ke = DK(base-key, usage | 0xAA); Ki = DK(base-key, usage | 0x55); 4.4. Checksum profiles based on simplified profile When an encryption system is defined using the simplified profile given in section 4.2, a checksum algorithm may be defined for it as follows: checksum mechanism from simplified profile ---------------------------------------------- associated cryptosystem as defined above get_mic HMAC(Kc, message) verify_mic get_mic and compare The HMAC function and key Kc are as described in section 4.3. 5. Profiles for Kerberos encryption systems These are the currently defined encryption systems for Kerberos. The astute reader will notice that some of them do not fulfill all of the requirements outlined above. These weaker encryption systems are defined for backwards compatibility; newer implementations should attempt to make use of the stronger encryption systems when possible. The full list of current encryption type number assignments is given in section 8. Raeburn [Page 15] INTERNET DRAFT January 2002 5.1. null If no encryption is in use, the encryption system is said to be the NULL encryption system. In the NULL encryption system there is no checksum, confounder or padding. The ciphertext is simply the plaintext. The null Key is used by the null encryption system and is zero octets in length. This encryption system should not be used for protection of data. It exists primarily to associate with the rsa-md5 checksum type, but may also be useful for testing protocol implementations. null ------------------------------------------------ protocol key format zero-length bit string specific key structure empty required checksum rsa-md5 mechanism key-generation seed 0 length cipher state none initial cipher state none encryption function identity decryption function identity, no integrity check default string-to-key none params key generation functions: string-to-key empty string random-to-key empty string combine-keys empty string key-derivation empty string The null encryption algorithm is assigned the etype value zero (0). Raeburn [Page 16] INTERNET DRAFT January 2002 5.2. DES-based encryption systems These encryption systems encrypt information under the Data Encryption Standard [DES77] using the cipher block chaining mode [DESM80]. A checksum is computed as described below and placed in the cksum field. DES blocks are 8 bytes. As a result, the data to be encrypted (the concatenation of confounder, checksum, and message) must be padded to an 8 byte boundary before encryption. The values of the padding bytes are unspecified. Plaintext and DES ciphtertext are encoded as blocks of 8 octets which are concatenated to make the 64-bit inputs for the DES algorithms. The first octet supplies the 8 most significant bits (with the octet's MSbit used as the DES input block's MSbit, etc.), the second octet the next 8 bits, ..., and the eighth octet supplies the 8 least significant bits. Encryption under DES using cipher block chaining requires an additional input in the form of an initialization vector; this vector is specified for each encryption system, below. The DES specifications identify some 'weak' and 'semi-weak' keys; those keys shall not be used for encrypting messages for use in Kerberos. Additionally, because of the way that keys are derived for the encryption of checksums, keys shall not be used that yield 'weak' or 'semi-weak' keys when eXclusive-ORed with the hexadecimal constant 0xF0F0F0F0F0F0F0F0. A DES key is 8 octets of data. This consists of 56 bits of actual key data, and 8 parity bits, one per octet. The key is encoded as a series of 8 octets written in MSB-first order. The bits within the key are also encoded in MSB order. For example, if the encryption key is (B1,B2,...,B7,P1,B8,...,B14,P2,B15,...,B49,P7,B50,...,B56,P8) where B1,B2,...,B56 are the key bits in MSB order, and P1,P2,...,P8 are the parity bits, the first octet of the key would be B1,B2,...,B7,P1 (with B1 as the MSbit). See the [DESM80] introduction for reference. Encryption data format The format for the data to be encrypted includes a one-block confounder, a checksum, the encoded plaintext, and any necessary padding, as described in the following diagram. The msg-seq field contains the part of the protocol message described in section 5 which is to be encrypted. Raeburn [Page 17] INTERNET DRAFT January 2002 +-----------+----------+---------+-----+ |confounder | checksum | msg-seq | pad | +-----------+----------+---------+-----+ One generates a random confounder of one block, placing it in confounder; zeroes out the checksum field (of length appropriate to exactly hold the checksum to be computed); calculates the appropriate checksum over confounder, check, and msg-seq, placing the result in check; adds the necessary padding; then encrypts using the specified encryption type and the appropriate key. String to key transformation To generate a DES key from a UTF-8 text string (password), a "salt" is concatenated to the text string, and then padded with ASCII nulls to an 8 byte boundary. This string is then fan-folded and eXclusive-ORed with itself to form an 8 byte DES key. Before eXclusive-ORing a block, every byte is shifted one bit to the left to leave the lowest bit zero. The key is the "corrected" by correcting the parity on the key, and if the key matches a 'weak' or 'semi-weak' key as described in the DES specification, it is eXclusive-ORed with the constant 0x00000000000000F0. This key is then used to generate a DES CBC checksum on the initial string (with the salt appended). The result of the CBC checksum is the "corrected" as described above to form the result which is return as the key. Pseudocode follows: key_correction(key) { fixparity(key); if (is_weak_key_key(key)) key = key XOR 0xF0; return(key); } Raeburn [Page 18] INTERNET DRAFT January 2002 mit_des_string_to_key(string,salt) { odd = 1; s = string | salt; tempkey = NULL; pad(s); /* with nulls to 8 byte boundary */ for (8byteblock in s) { if (odd == 0) { odd = 1; reverse(8byteblock) } else odd = 0; left shift every byte in 8byteblock one bit; tempkey = tempkey XOR 8byteblock; } tempkey = key_correction(tempkey); key = key_correction(DES-CBC-check(s,tempkey)); return(key); } des_string_to_key(string,salt,params) { if (length(params) == 0) type = 0; else if (length(params) == 1) type = params[0]; else error("invalid params"); if (type == 0) mit_des_string_to_key(string,salt); else if (type == 1) afs_des_string_to_key(string,salt); else error("invalid params"); } The AFS string-to-key algorithm is not defined here, but a parameter block containing a byte value of one (1) is reserved for its use. 5.2.1. DES with MD5 The des-cbc-md5 encryption mode encrypts information under DES in CBC mode with an all-zero initial vector, with an MD5 checksum (described in [MD5-92]) computed and placed in the checksum field. Raeburn [Page 19] INTERNET DRAFT January 2002 The encryption system parameters for des-cbc-md5 are: des-cbc-md5 -------------------------------------------------------------------- protocol key format 8 bytes, parity in low bit of each specific key structure copy of original key required checksum rsa-md5-des mechanism key-generation seed 8 bytes length cipher state 8 bytes (CBC initial vector) initial cipher state all-zero encryption function des-cbc(confounder | checksum | msg | pad, ivec=oldstate) where checksum = md5(confounder | 0000... | msg) newstate = last block of des-cbc output decryption function decrypt encrypted text and verify checksum newstate = last block of ciphertext default string-to-key empty string params key generation functions: string-to-key des_string_to_key random-to-key copy input, then fix parity bits (discards low bit of each input byte) combine-keys bitwise XOR, then fix parity bits key-derivation identity The des-cbc-md5 encryption type is assigned the etype value three (3). Raeburn [Page 20] INTERNET DRAFT January 2002 5.2.2. DES with MD4 The des-cbc-md4 encryption mode also encrypts information under DES in CBC mode, with an all-zero initial vector. An MD4 checksum (described in [MD4-92]) is computed and placed in the checksum field. des-cbc-md4 -------------------------------------------------------------------- protocol key format 8 bytes, parity in low bit of each specific key structure copy of original key required checksum rsa-md4-des mechanism key-generation seed 8 bytes length cipher state 8 bytes (CBC initial vector) initial cipher state all-zero encryption function des-cbc(confounder | checksum | msg | pad, ivec=oldstate) where checksum = md4(confounder | 0000... | msg) newstate = last block of des-cbc output decryption function decrypt encrypted text and verify checksum newstate = last block of ciphertext default string-to-key empty string params key generation functions: string-to-key des_string_to_key random-to-key copy input, then fix parity bits combine-keys bitwise XOR, then fix parity bits key-derivation identity Raeburn [Page 21] INTERNET DRAFT January 2002 The des-cbc-md4 encryption algorithm is assigned the etype value two (2). 5.2.3. DES with CRC The des-cbc-crc encryption type uses DES in CBC mode, with a 4-octet CRC-based checksum computed as described in section 6.4. (Note that this is not a standard CRC-32 checksum, but a slightly modified one.) Unless otherwise specified, the key should be used as the initialization vector, unlike for the other Kerberos DES encryption schemes. The other details of the encryption of this data are identical to those for the des-cbc-md5 encryption mode. Note that, since the CRC-32 checksum is not collision-proof, an attacker could use a probabilistic chosen-plaintext attack to generate a valid message even if a confounder is used [SG92]. The use of collision-proof checksums is recommended for environments where such attacks represent a significant threat. des-cbc-crc -------------------------------------------------------------------- protocol key format 8 bytes, parity in low bit of each specific key structure copy of original key required checksum rsa-md5-des mechanism key-generation seed 8 bytes length cipher state 8 bytes (CBC initial vector) initial cipher state copy of original key encryption function des-cbc(confounder | checksum | msg | pad, ivec=oldstate) where checksum = crc(confounder | 00000000 | msg) newstate = last block of des-cbc output decryption function decrypt encrypted text and verify checksum newstate = last block of ciphertext Raeburn [Page 22] INTERNET DRAFT January 2002 des-cbc-crc -------------------------------------------------------------------- default string-to-key empty string params key generation functions: string-to-key des_string_to_key random-to-key copy input, then fix parity bits combine-keys bitwise XOR, then fix parity bits key-derivation identity The des-cbc-crc encryption algorithm is assigned the etype value one (1). 5.3. Triple-DES Encryption with Key Derivation This encryption type is based on the Triple DES cryptosystem in Outer-CBC mode, and the HMAC-SHA1 [Krawczyk96] message authentication algorithm. A Triple DES key is the concatenation of three DES keys as described above for des-cbc-md5. A Triple DES key is generated from random data by creating three DES keys from separate sequences of random data. EncryptedData using this type must be generated as described in section 4.3. If the length of the input data is not a multiple of the block size, zero octets must be used to pad the plaintext to the next eight-octet boundary. The counfounder must be eight random octets (one block). The simplified profile for Triple DES, with key derivation as defined in section 4, is as follows: des3-cbc-hmac-sha1-kd ------------------------------------------------ protocol key format 24 bytes, parity in low bit of each key-generation seed 21 bytes length Raeburn [Page 23] INTERNET DRAFT January 2002 des3-cbc-hmac-sha1-kd ------------------------------------------------ hash function SHA-1 block size 8 bytes default string-to-key none params encryption decryption functions key generation functions: random-to-key see below string-to-key DES3string-to-key (see below) The des3-cbc-hmac-sha1-kd encryption type is assigned the value sixteen (16). 5.3.1. Triple DES Key Production (random-to-key, string-to-key) The 168 bits of random key data are converted to a protocol key value as follows. First, the 168 bits are divided into three groups of 56 bits, which are expanded individually into 64 bits as follows: 1 2 3 4 5 6 7 p 9 10 11 12 13 14 15 p 17 18 19 20 21 22 23 p 25 26 27 28 29 30 31 p 33 34 35 36 37 38 39 p 41 42 43 44 45 46 47 p 49 50 51 52 53 54 55 p 56 48 40 32 24 16 8 p The "p" bits are parity bits computed over the data bits. The output of the three expansions are concatenated to form the protocol key value. When the HMAC-SHA1 of a string is computed, the key is used in the protocol key form. The string-to-key function is used to tranform UTF-8 passwords into DES3 keys. The DES3 string-to-key function relies on the "N-fold" algorithm and DK function, described in section 4. Raeburn [Page 24] INTERNET DRAFT January 2002 The n-fold algorithm is applied to the password string concatenated with a salt value. For 3-key triple DES, the operation will involve a 168-fold of the input password string, to generate an intermediate key, from which the user's long-term key will be derived with the DK function. The DES3 string-to-key function is shown here in pseudocode: DES3string-to-key(passwordString, salt, params) if (params != emptyString) error("invalid params"); s = passwordString + salt tmpKey = random-to-key(168-fold(s)) key = DK (tmpKey, KerberosConstant) No weak-key checking is performed. The KerberosConstant value is the byte string {0x6b 0x65 0x72 0x62 0x65 0x72 0x6f 0x73}. These values correspond to the ASCII encoding for the string "kerberos". 6. Profiles for Kerberos checksums These are the checksum types currently defined for Kerberos. The full list of current checksum type number assignments is given in section 8. 6.1. RSA MD4 Cryptographic Checksum Using DES The RSA-MD4-DES checksum calculates a keyed collision-proof checksum by prepending an 8 octet confounder before the text, applying the RSA MD4 checksum algorithm [MD4-92], and encrypting the confounder and the checksum using DES in cipher-block-chaining (CBC) mode using a variant of the key, where the variant is computed by eXclusive-ORing the key with the constant 0xF0F0F0F0F0F0F0F0 [@@REF 39]. The initialization vector should be zero. The resulting checksum is 24 octets long. This checksum is tamper-proof and believed to be collision-proof. The DES specifications identify some weak keys' and 'semi-weak keys'; those keys shall not be used for generating RSA-MD4 checksums for use in Kerberos. rsa-md4-des ---------------------------------------------------------------- associated cryptosystem des-cbc-md5, des-cbc-md4, des-cbc-crc get_mic des-cbc(key XOR 0xF0F0F0F0F0F0F0F0, conf | rsa-md4(conf | msg), ivec=0) Raeburn [Page 25] INTERNET DRAFT January 2002 rsa-md4-des ---------------------------------------------------------------- verify_mic decrypt and verify rsa-md4 checksum The rsa-md4-des checksum algorithm is assigned a checksum type number of three (3). 6.2. The RSA MD5 Checksum The RSA-MD5 checksum calculates a checksum using the RSA MD5 algorithm [MD5-92]. The algorithm takes as input an input message of arbitrary length and produces as output a 128-bit (16 octet) checksum. RSA-MD5 is believed to be collision-proof. However, since it is unkeyed, it must be used with caution. Currently it is used by some implementations in places where the checksum itself is part of a larger message that will be encrypted. Its use is not recommended. rsa-md5 ---------------------------------------------- associated cryptosystem null get_mic rsa-md5(msg) verify_mic get_mic and compare The rsa-md5 checksum algorithm is assigned a checksum type number of seven (7). 6.3. RSA MD5 Cryptographic Checksum Using DES The RSA-MD5-DES checksum calculates a keyed collision-proof checksum by prepending an 8 octet confounder before the text, applying the RSA MD5 checksum algorithm, and encrypting the confounder and the checksum using DES in cipher-block-chaining (CBC) mode using a variant of the key, where the variant is computed by eXclusive-ORing the key with the hexadecimal constant 0xF0F0F0F0F0F0F0F0. The initialization vector should be zero. The resulting checksum is 24 octets long. This checksum is tamper-proof and believed to be collision-proof. The DES specifications identify some 'weak keys' and 'semi-weak keys'; those keys shall not be used for encrypting RSA-MD5 checksums for use in Kerberos. Raeburn [Page 26] INTERNET DRAFT January 2002 The format for the checksum is described in the following diagram: +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | des-cbc(confounder+rsa-md5(confounder+msg), key=var(key), iv=0) | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ rsa-md5-des ---------------------------------------------------------------- associated cryptosystem des-cbc-md5, des-cbc-md4, des-cbc-crc get_mic des-cbc(key XOR 0xF0F0F0F0F0F0F0F0, conf | rsa-md5(conf | msg)) verify_mic decrypt and verify rsa-md5 checksum The rsa-md5-des checksum algorithm is assigned a checksum type number of eight (8). 6.4. The CRC-32 Checksum This CRC-32 checksum calculates a checksum based on a cyclic redundancy check as described in ISO 3309 [ISO3309], modified as described below. The resulting checksum is four (4) octets in length. The CRC-32 is neither keyed nor collision-proof; thus, the use of this checksum is not recommended. An attacker using a probabilistic chosen-plaintext attack as described in [@@REF 13??] might be able to generate an alternative message that satisfies the checksum. The use of collision-proof checksums is recommended for environments where such attacks represent a significant threat. The CRC-32 checksum used in the des-cbc-crc encryption mode is identical to the 32-bit FCS described in ISO 3309 with two exceptions: the sum with the all-ones polynomial times x**k is omitted, and the final remainder is not ones-complemented. ISO 3309 describes the FCS in terms of bits, while this document describes the Kerberos protocol in terms of octets. To disambiguate the ISO 3309 definition for the purpose of computing the CRC-32 in the des-cbc-crc encryption mode, the ordering of bits in each octet shall be assumed to be LSB-first. Given this assumed ordering of bits within an octet, the mapping of bits to polynomial coefficients shall be identical to that specified in ISO 3309. Raeburn [Page 27] INTERNET DRAFT January 2002 crc32 ------------------------------------------------ associated cryptosystem des-cbc-md5, des-cbc- md4, des-cbc-crc get_mic crc32(msg) verify_mic compute checksum and compare The crc32 checksum algorithm is assigned a checksum type number of one (1). 6.5. The RSA MD4 Checksum The RSA-MD4 checksum calculates a checksum using the RSA MD4 algorithm [MD4-92]. The algorithm takes as input an input message of arbitrary length and produces as output a 128-bit (16 octet) checksum. RSA-MD4 is believed to be collision-proof. rsa-md4 ------------------------------------------------ associated cryptosystem des-cbc-md5, des-cbc- md4, des-cbc-crc get_mic md4(msg) verify_mic compute checksum and compare The rsa-md4 checksum algorithm is assigned a checksum type number of two (2). 6.6. DES CBC checksum The DES-MAC checksum is computed by prepending an 8 octet confounder to the plaintext, performing a DES CBC-mode encryption on the result using the key and an initialization vector of zero, taking the last block of the ciphertext, prepending the same confounder and encrypting the pair using DES in cipher-block-chaining (CBC) mode using a a variant of the key, where the variant is computed by eXclusive-ORing the key with the constant 0xF0F0F0F0F0F0F0F0. The initialization vector should be zero. The resulting checksum is 128 Raeburn [Page 28] INTERNET DRAFT January 2002 bits (16 octets) long, 64 bits of which are redundant. This checksum is tamper-proof and collision-proof. The DES specifications identify some "weak" and "semiweak" keys; those keys shall not be used for generating DES-MAC checksums for use in Kerberos, nor shall a key be used whose variant is "weak" or "semi-weak". des-mac ---------------------------------------------------------------- associated des-cbc-md5, des-cbc-md4, des-cbc-crc cryptosystem get_mic des-cbc(key XOR 0xF0F0F0F0F0F0F0F0, conf | des-mac(key, conf | msg, ivec=0), ivec=0) verify_mic decrypt, compute DES MAC using confounder, compare The des-mac checksum algorithm is assigned a checksum type number of four (4). 6.7. RSA MD4 Cryptographic Checksum Using DES alternative The RSA-MD4-DES-K checksum calculates a keyed collision-proof checksum by applying the RSA MD4 checksum algorithm and encrypting the results using DES in cipherblock-chaining (CBC) mode using a DES key as both key and initialization vector. The resulting checksum is 16 octets long. This checksum is tamper-proof and believed to be collision-proof. Note that this checksum type is the old method for encoding the RSA-MD4-DES checksum and it is no longer recommended. rsa-md4-des-k ---------------------------------------------------------------- associated cryptosystem des-cbc-md5, des-cbc-md4, des-cbc-crc get_mic des-cbc(key, md4(msg), ivec=key) verify_mic compute CRC-32 and compare Raeburn [Page 29] INTERNET DRAFT January 2002 The rsa-md4-des-k checksum algorithm is assigned a checksum type number of six (6). 6.8. DES CBC checksum alternative The DES-MAC-K checksum is computed by performing a DES CBC-mode encryption of the plaintext, and using the last block of the ciphertext as the checksum value. It is keyed with an encryption key and an initialization vector; any uses which do not specify an additional initialization vector will use the key as both key and initialization vector. The resulting checksum is 64 bits (8 octets) long. This checksum is tamper-proof and collision-proof. Note that this checksum type is the old method for encoding the DESMAC checksum and it is no longer recommended. The DES specifications identify some "weak keys"; those keys shall not be used for generating DES-MAC checksums for use in Kerberos. des-mac-k ---------------------------------------------------------------- associated cryptosystem des-cbc-md5, des-cbc-md4, des-cbc-crc get_mic des-mac(key, msg, ivec=key or given) verify_mic compute MAC and compare The des-mac-k checksum algorithm is assigned a checksum type number of five (5). 6.9. The HMAC-SHA1-DES3-KD Checksum This checksum type is defined as outlined in section 3 above, using the des3-hmac-sha1-kd encryption algorithm parameters from section 5.3. The checksum is thus a SHA-1 HMAC using the computed key Kc over the message to be protected. The hmac-sha1-des3-kd checksum algorithm is assigned a checksum type number of twelve (12). 7. Use of Kerberos encryption outside this specification Several Kerberos-based application protocols and preauthentication systems have been designed and deployed that perform encryption and message integrity checks in various ways. While in some cases there may be good reason for specifying these protocols in terms of Raeburn [Page 30] INTERNET DRAFT January 2002 specific encryption or checksum algorithms, we anticipate that in many cases this will not be true, and more generic approaches independent of particular algorithms will be desirable. Rather than having each protocol designer reinvent schemes for protecting data, using multiple keys, etc, we have attempted to present in this section a general framework that should be sufficient not only for the Kerberos protocol itself but also for many preauthentication systems and application protocols, while trying to avoid some of the assumptions that can work their way into such protocol designs. Some problematic assumptions we've seen, and sometimes made, include: that a random bitstring is always valid as a key (not true for DES keys with parity); that the basic block encryption chaining mode provides no integrity checking, or can easily be separated from such checking (not true for many modes in development that do both simultaneously); that a checksum for a message always results in the same value (not true if a confounder is incorporated); that an initial vector is used (may not be true if a block cipher in CBC mode is not in use); that the key is a clever thing to use as the initial vector for CBC mode encryption (not true @@REF Bellovin paper). Such assumptions, while they may hold for any given set of encryption and checksum algorithms, may not be true of the next algorithms to be defined, leaving the application protocol unable to make use of those algorithms without updates to its specification. The Kerberos protocol uses only the attributes and operations described in sections 2 and 3. Preauthentication systems and application protocols making use of Kerberos are encouraged to use them as well. The specific key and string-to-key parameters should generally be treated as opaque. While the string-to-key parameters are manipulated as an octet string, the representation for the specific key structure is implementation-defined; it may not even be a single object. While we don't recommend it, some application protocols will undoubtedly continue to use the key data directly, even if only in some of the currently existing protocol specifications. An implementation intended to support general Kerberos applications may therefore need to make the key data available, as well as the attributes and operations described in sections 2 and 3. [5] 8. Assigned Numbers The following encryption type numbers are already assigned or reserved for use in Kerberos and related protocols. Raeburn [Page 31] INTERNET DRAFT January 2002 Encryption type etype block minimum confounder section value size pad size size ---------------------------------------------------------------------- NULL 0 1 0 0 5.1 des-cbc-crc 1 8 4 8 5.2.3 des-cbc-md4 2 8 0 8 5.2.2 des-cbc-md5 3 8 0 8 5.2.1 des3-cbc-sha1-kd 16 8 0 8 5.3 Other numbers have been reserved for use in encryption systems not defined here. Encryption type numbers are unfortunately overloaded on occasion in Kerberos-related protocols, so some of the reserved numbers do not and will not correspond to encryption systems fitting the profile presented here. Encryption type etype value comment ---------------------------------------------------------------------- [reserved] 4 des3-cbc-md5 5 [reserved] 6 des3-cbc-sha1 7 dsaWithSHA1-CmsOID 9 (pkinit) md5WithRSAEncryption-CmsOID 10 (pkinit) sha1WithRSAEncryption-CmsOID 11 (pkinit) rc2CBC-EnvOID 12 (pkinit) rsaEncryption-EnvOID 13 (pkinit from PKCS#1 v1.5) rsaES-OAEP-ENV-OID 14 (pkinit from PKCS#1 v2.0) des-ede3-cbc-Env-OID 15 (pkinit) rc4-hmac 23 (swift) rc4-hmac-exp 24 (swift) subkey-keynaterial 65 (opaque mhur) The following checksum type numbers are assigned or reserved. As with encryption type numbers, some overloading of checksum numbers has occurred. Checksum type sumtype checksum section value size ---------------------------------------------------------------------- CRC32 1 4 6.4 rsa-md4 2 16 6.5 rsa-md4-des 3 24 6.1 des-mac 4 16 6.6 Raeburn [Page 32] INTERNET DRAFT January 2002 des-mac-k 5 8 6.8 rsa-md4-des-k 6 16 6.7 rsa-md5 7 16 6.2 rsa-md5-des 8 24 6.3 rsa-md5-des3 9 24 hmac-sha1-des3-kd 12 20 6.9 hmac-sha1-des3 13 20 sha1 (unkeyed) 14 20 [reserved] 0x8003 ? [GSS-KRB5] 9. Notes to Implementors The "interface" described here is the minimal information that must be defined to make a cryptosystem useful within Kerberos in an interoperable fashion. It is not an attempt to define a complete API for cryptographic functionality within Kerberos. Actual implementations providing clean APIs will probably find it useful to make additional information available, which should be possible to derive from a specification written to the framework given here. For example, an application designer may wish to determine the largest number of bytes that can be encrypted without overflowing a certain size output buffer, or conversely, the maximum number of bytes that might be obtained by decrypting a given ciphertext message. The presence of a mechanism in this document should not be taken as an indication that it must be implemented for compliance with any specification; required mechanisms will be specified elsewhere. Indeed, some of the mechanisms described here for backwards compatibility are now considered rather weak for protecting critical data. 10. Security Considerations Well, sure... weak encryption or checksum algorithms. Warnings made in the various sections. Reference EFF book on DES cracking, RFC on DES for IPsec. 11. Acknowledgements This document is an extension of the encryption specification included in RFC 1510 by B. Clifford Neuman and John Kohl, and much of the text of the background, concepts, and DES specifications are drawn directly from that document. Marc Horowitz wrote the original specification of triple-DES and key derivation in a pair of Internet Drafts (under the names draft- horowitz-key-derivation and draft-horowitz-kerb-key-derivation) which Raeburn [Page 33] INTERNET DRAFT January 2002 were later folded into a draft revision of RFC 1510, from which this document was later split off. The abstract framework presented in this document was put together by Jeff Altman, Sam Hartman, Jeff Hutzelman, Cliff Neuman, Ken Raeburn, and Tom Yu, and the details were refined several times based on comments from John Brezak and others. Miroslav Jurisic provided one of the UTF-8 test cases for the string- to-key functions. Uri Blumenthal provided comments on the "combine-keys" function proposed for use with triple-DES. 12. Editor's address Kenneth Raeburn Massachusetts Institute of Technology 77 Massachusetts Avenue Cambridge, MA 02139 raeburn@mit.edu 13. Full Copyright Statement Copyright (C) The Internet Society (2002). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION Raeburn [Page 34] INTERNET DRAFT January 2002 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE." A. Test vectors This section provides test vectors for various functions defined or described in section 6. For convenience, most inputs are ASCII strings, though some UTF-8 samples should be provided for string-to- key functions. Keys and other binary data are specified as hexadecimal strings. A.1. n-fold The n-fold function is defined in section 6.4. As noted there, the sample vector in the original paper defining the algorithm appears to be incorrect. Here are values provided by Marc Horowitz: 64-fold("012345") = 64-fold(303132333435) = be072631276b1955 56-fold("password") = 56-fold(70617373776f7264) = 78a07b6caf85fa 64-fold("Rough Consensus, and Running Code") = 64-fold(526f75676820436f6e73656e7375732c20616e642052756e 6e696e6720436f6465) = bb6ed30870b7f0e0 168-fold("password") = 168-fold(70617373776f7264) = 59e4a8ca7c0385c3c37b3f6d2000247cb6e6bd5b3e 192-fold("MASSACHVSETTS INSTITVTE OF TECHNOLOGY" 192-fold(4d41535341434856534554545320494e5354495456544520 4f4620544543484e4f4c4f4759) = db3b0d8f0b061e603282b308a50841229ad798fab9540c1b A.2. mit_des_string_to_key The function mit_des_string_to_key is defined in section 6.5.2. We present here several test values, with some of the intermediate results. The fourth test demonstrates the use of UTF-8 with three characters. The last two tests are specifically constructed so as to trigger the weak-key fixups for the intermediate key produced by fan- folding; we have no test cases that cause such fixups for the final key. Raeburn [Page 35] INTERNET DRAFT January 2002 UTF-8 encodings used in test vector: eszett C3 9F s-caron C5 A1 c-acute C4 87 Test vector: salt: "ATHENA.MIT.EDUraeburn" 415448454e412e4d49542e4544557261656275726e password: "password" 70617373776f7264 fan-fold result: c01e38688ac86c2e intermediate key: c11f38688ac86d2f DES key: cbc22fae235298e3 salt: "WHITEHOUSE.GOVdanny" 5748495445484f5553452e474f5664616e6e79 password: "potatoe" 706f7461746f65 fan-fold result: a028944ee63c0416 intermediate key: a129944fe63d0416 DES key: df3d32a74fd92a01 salt: "EXAMPLE.COMbuckaroo" 4558414d504c452e434f4d6275636b61726f6f password: "penny" 70656e6e79 fan-fold result: 96d2d87e925c64ee intermediate key: 97d3d97f925d64ef DES key: 9443a2e532fdc4f1 salt: "ATHENA.MIT.EDUJuri" + s-caron + "i" + c-acute 415448454e412e4d49542e4544554a757269c5a169c487 password: eszett c39f fan-fold result: b8f6c40e305afc9e intermediate key: b9f7c40e315bfd9e DES key: 62c81a5232b5e69d salt: "AAAAAAAA" 4141414141414141 password: "11119999" 3131313139393939 fan-fold result: e0e0e0e0f0f0f0f0 intermediate key: e0e0e0e0f1f1f101 DES key: 984054d0f1a73e31 Raeburn [Page 36] INTERNET DRAFT January 2002 salt: "FFFFAAAA" 4646464641414141 password: "NNNN6666" 4e4e4e4e36363636 fan-fold result: 1e1e1e1e0e0e0e0e intermediate key: 1f1f1f1f0e0e0efe DES key: c4bf6b25adf7a4f8 A.3. DES3 DR and DK These tests show the derived-random and derived-key values for the des3-hmac-sha1-kd encryption scheme, using the DR and DK functions defined in section 6.5.5. The input keys were randomly generated; the usage values are from this specification. key: dce06b1f64c857a11c3db57c51899b2cc1791008ce973b92 usage: 0000000155 DR: 935079d14490a75c3093c4a6e8c3b049c71e6ee705 DK: 925179d04591a79b5d3192c4a7e9c289b049c71f6ee604cd key: 5e13d31c70ef765746578531cb51c15bf11ca82c97cee9f2 usage: 00000001aa DR: 9f58e5a047d894101c469845d67ae3c5249ed812f2 DK: 9e58e5a146d9942a101c469845d67a20e3c4259ed913f207 key: 98e6fd8a04a4b6859b75a176540b9752bad3ecd610a252bc usage: 0000000155 DR: 12fff90c773f956d13fc2ca0d0840349dbd39908eb DK: 13fef80d763e94ec6d13fd2ca1d085070249dad39808eabf key: 622aec25a2fe2cad7094680b7c64940280084c1a7cec92b5 usage: 00000001aa DR: f8debf05b097e7dc0603686aca35d91fd9a5516a70 DK: f8dfbf04b097e6d9dc0702686bcb3489d91fd9a4516b703e key: d3f8298ccb166438dcb9b93ee5a7629286a491f838f802fb usage: 6b65726265726f73 DR: 2270db565d2a3d64cfbfdc5305d4f778a6de42d9da DK: 2370da575d2a3da864cebfdc5204d56df779a7df43d9da43 Raeburn [Page 37] INTERNET DRAFT January 2002 key: b55e983467e551b3e5d0e5b6c80d45769423a873dc62b30e usage: 636f6d62696e65 DR: 0127398bacc81a2a62bc45f8d4c151bbcdd5cb788a DK: 0126388aadc81a1f2a62bc45f8d5c19151bacdd5cb798a3e key: c1081649ada74362e6a1459d01dfd30d67c2234c940704da usage: 0000000155 DR: 348056ec98fcc517171d2b4d7a9493af482d999175 DK: 348057ec98fdc48016161c2a4c7a943e92ae492c989175f7 key: 5d154af238f46713155719d55e2f1f790dd661f279a7917c usage: 00000001aa DR: a8818bc367dadacbe9a6c84627fb60c294b01215e5 DK: a8808ac267dada3dcbe9a7c84626fbc761c294b01315e5c1 key: 798562e049852f57dc8c343ba17f2ca1d97394efc8adc443 usage: 0000000155 DR: c813f88b3be2b2f75424ce9175fbc8483b88c8713a DK: c813f88a3be3b334f75425ce9175fbe3c8493b89c8703b49 key: 26dce334b545292f2feab9a8701a89a4b99eb9942cecd016 usage: 00000001aa DR: f58efc6f83f93e55e695fd252cf8fe59f7d5ba37ec DK: f48ffd6e83f83e7354e694fd252cf83bfe58f7d5ba37ec5d A.4. DES3string_to_key These are the keys generated for some of the above input strings for triple-DES with key derivation as defined in section 5.3.1. salt: "ATHENA.MIT.EDUraeburn" passwd: "password" key: 850bb51358548cd05e86768c313e3bfef7511937dcf72c3e salt: "WHITEHOUSE.GOVdanny" passwd: "potatoe" key: dfcd233dd0a43204ea6dc437fb15e061b02979c1f74f377a Raeburn [Page 38] INTERNET DRAFT January 2002 salt: "EXAMPLE.COMbuckaroo" passwd: "penny" key: 6d2fcdf2d6fbbc3ddcadb5da5710a23489b0d3b69d5d9d4a salt: "ATHENA.MIT.EDUJuri" + s-caron + "i" + c-acute passwd: eszett key: 16d5a40e1ce3bacb61b9dce00470324c831973a7b952feb0 A.5. DES3 combine-keys PLACEHOLDER, FILL IN BEFORE PUBLICATION A.6. Modified CRC-32 PLACEHOLDER, GET DATA FROM TOM Notes [1] While Message Authentication Code (MAC) or Message Integrity Check (MIC) would be more appropriate terms for many of the uses in this section, we continue to use the term "checksum" for historical reasons. [2] In the case of Kerberos, the encrypted objects will generally be ASN.1 DER encodings, which contain indications of their length in the first few octets. [3] As of the time of this writing, some new modes of operation have been proposed, some of which may permit encryption and integrity protection simultaneously. After some of these proposals have been subjected to adequate analysis, we may wish to formulate a new simplified profile based on one of them. [4] It should be noted that the sample vector in Appendix B.2 of the original paper appears to be incorrect. Two independent implementations from the specification (one in C by Marc Horowitz, and another in Scheme by Bill Sommerfeld) agree on a value different from that in [Blumenthal96]. [5] Perhaps one of the more common reasons for directly performing encryption is direct control over the negotiation and to select a "sufficiently strong" encryption algorithm (whatever that means in the context of a given application). While Kerberos directly provides no facility for negotiating encryption types between the application client and server, there are other means for accomplishing similar goals. For example, requesting only "strong" session key types from the Raeburn [Page 39] INTERNET DRAFT January 2002 KDC, and assuming that the type actually returned by the KDC will be understood and supported by the application server. Normative References This section copied from kerberos-revisions draft. Drop the ones we don't need, add anything new that we do need. Move informational- only references to the next section. Update old I-D references to RFCs, or find other sources. [Blumenthal96] Blumenthal, U., "A Better Key Schedule for DES-Like Ciphers", Proceedings of PRAGOCRYPT '96, 1996. [Bellare98] Bellare, M., Desai, A., Pointcheval, D., Rogaway, P., "Relations Among Notions of Security for Public-Key Encryption Schemes". Extended abstract published in Advances in Cryptology- Crypto 98 Proceedings, Lecture Notes in Computer Science Vol. 1462, H. Krawcyzk ed., Springer-Verlag, 1998. [DES77] National Bureau of Standards, U.S. Department of Commerce, "Data Encryption Standard," Federal Information Processing Standards Publication 46, Washington, DC (1977). [DESM80] National Bureau of Standards, U.S. Department of Commerce, "DES Modes of Operation," Federal Information Processing Standards Publication 81, Springfield, VA (December 1980). [Dolev91] Dolev, D., Dwork, C., Naor, M., "Non-malleable cryptography", Proceedings of the 23rd Annual Symposium on Theory of Computing, ACM, 1991. [ISO3309] International Organization for Standardization, "ISO Information Processing Systems - Data Communication - High-Level Data Link Control Procedure - Frame Structure," IS 3309 (October 1984). 3rd Edition. [Krawczyk96] Krawczyk, H., Bellare, and M., Canetti, R., "HMAC: Keyed-Hashing for Message Authentication", draft-ietf-ipsec-hmac-md5-01.txt, August, 1996. @@ Now RFC 2202. [MD4-92] R. Rivest, "The MD4 Message Digest Algorithm," RFC 1320, MIT Laboratory for Computer Science (April 1992). [MD5-92] R. Rivest, "The MD5 Message Digest Algorithm," RFC 1321, MIT Laboratory for Computer Science (April 1992). Raeburn [Page 40] INTERNET DRAFT January 2002 [MNSS87] S. P. Miller, B. C. Neuman, J. I. Schiller, and J. H. Saltzer, Section E.2.1: Kerberos Authentication and Authorization System, M.I.T. Project Athena, Cambridge, Massachusetts (December 21, 1987). [SG92] Stuart G. Stubblebine and Virgil D. Gligor, "On Message Integrity in Cryptographic Protocols," in Proceedings of the IEEE Symposium on Research in Security and Privacy, Oakland, California (May 1992). Informative References [GSS-KRB5] @@ blah blah blah, RFC 1964 ... EFF DES-cracking book ... Raeburn [Page 41]