Add missing ',' between parameters [HEIMDAL-599]
[heimdal.git] / doc / standardisation / draft-ietf-krb-wg-crypto-03.txt
blobb1bee6fa491cfbc3b84c7ed9c6cffd15d87581e9
10 INTERNET DRAFT                                                K. Raeburn
11 Kerberos Working Group                                               MIT
12 Document: draft-ietf-krb-wg-crypto-03.txt              February 24, 2003
13                                                  expires August 24, 2003
15                  Encryption and Checksum Specifications
16                              for Kerberos 5
18 Abstract
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".
31    Comments should be sent to the editor, or to the IETF Kerberos
32    working group (ietf-krb-wg@anl.gov).
34 Status
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."
46    The list of current Internet-Drafts can be accessed at
47    http://www.ietf.org/ietf/1id-abstracts.html.
49    The list of Internet-Draft Shadow Directories can be accessed at
50    http://www.ietf.org/shadow.html.
58 Raeburn                                                         [Page 1]
60 INTERNET DRAFT                                             February 2003
63                            Table of Contents
66 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   1
67 Status . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   1
68 Table of Contents  . . . . . . . . . . . . . . . . . . . . . . . . .   2
69 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .   3
70 1. Concepts  . . . . . . . . . . . . . . . . . . . . . . . . . . . .   3
71 2. Encryption algorithm profile  . . . . . . . . . . . . . . . . . .   4
72 3. Checksum algorithm profile  . . . . . . . . . . . . . . . . . . .   9
73 4. Simplified profile for CBC ciphers with key derivation  . . . . .  10
74 4.1. A key derivation function . . . . . . . . . . . . . . . . . . .  10
75 4.2. Simplified profile parameters . . . . . . . . . . . . . . . . .  12
76 4.3. Cryptosystem profile based on simplified profile  . . . . . . .  14
77 4.4. Checksum profiles based on simplified profile . . . . . . . . .  16
78 5. Profiles for Kerberos encryption and checksum algorithms  . . . .  16
79 5.1. Unkeyed checksums . . . . . . . . . . . . . . . . . . . . . . .  16
80 5.2. DES-based encryption and checksum types . . . . . . . . . . . .  18
81 5.3. Triple-DES based encryption and checksum types  . . . . . . . .  28
82 6. Use of Kerberos encryption outside this specification . . . . . .  30
83 7. Assigned Numbers  . . . . . . . . . . . . . . . . . . . . . . . .  31
84 8. Implementation Notes  . . . . . . . . . . . . . . . . . . . . . .  32
85 9. Security Considerations . . . . . . . . . . . . . . . . . . . . .  33
86 10. IANA Considerations  . . . . . . . . . . . . . . . . . . . . . .  34
87 11. Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . .  35
88 12. Editor's address . . . . . . . . . . . . . . . . . . . . . . . .  35
89 13. Full Copyright Statement . . . . . . . . . . . . . . . . . . . .  36
90 A. Test vectors  . . . . . . . . . . . . . . . . . . . . . . . . . .  36
91 A.1. n-fold  . . . . . . . . . . . . . . . . . . . . . . . . . . . .  36
92 A.2. mit_des_string_to_key . . . . . . . . . . . . . . . . . . . . .  38
93 A.3. DES3 DR and DK  . . . . . . . . . . . . . . . . . . . . . . . .  42
94 A.4. DES3string_to_key . . . . . . . . . . . . . . . . . . . . . . .  43
95 A.5. Modified CRC-32 . . . . . . . . . . . . . . . . . . . . . . . .  44
96 B. Significant Changes from RFC 1510 . . . . . . . . . . . . . . . .  44
97 Notes  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  45
98 Normative References . . . . . . . . . . . . . . . . . . . . . . . .  46
99 Informative References . . . . . . . . . . . . . . . . . . . . . . .  48
114 Raeburn                                                         [Page 2]
116 INTERNET DRAFT                                             February 2003
119 Introduction
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.
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.
135 1. Concepts
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.
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.
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.
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.
170 Raeburn                                                         [Page 3]
172 INTERNET DRAFT                                             February 2003
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.
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.
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.
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.
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.
209 2. Encryption algorithm profile
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.
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.
226 Raeburn                                                         [Page 4]
228 INTERNET DRAFT                                             February 2003
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.
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.
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.
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.
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.
277          The third argument, the octet string, may be used to pass
278          mechanism-specific parameters in to this function.  Since doing
282 Raeburn                                                         [Page 5]
284 INTERNET DRAFT                                             February 2003
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.
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.
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.
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.
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.
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.
328       As mentioned above, this should be considered opaque to most
329       normal applications.
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
338 Raeburn                                                         [Page 6]
340 INTERNET DRAFT                                             February 2003
343       indicated above, this parameter block should be treated as an
344       opaque object in most cases.
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.
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.
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.
367       The contents of the cipher state must be treated as opaque outside
368       of encryption system specifications.
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.
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.
381       This state should be treated as opaque in any uses outside of an
382       encryption algorithm definition.
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
394 Raeburn                                                         [Page 7]
396 INTERNET DRAFT                                             February 2003
399       state can vary between encryption systems, and may not always be a
400       single block of random data.
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.
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.
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]
428       Assuming correctly-produced values for the specific key and cipher
429       state, no input octet string may result in an error indication.
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.
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]
446       As with the encryption function, a correct specification for this
450 Raeburn                                                         [Page 8]
452 INTERNET DRAFT                                             February 2003
455       function must indicate not only the contents of the output octet
456       string, but also the resulting cipher state.
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.
465    These operations and attributes are all that should be required to
466    support Kerberos and various proposed preauthentication schemes.
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.
474 3. Checksum algorithm profile
476    A checksum mechanism profile must define the following attributes and
477    operations:
479    associated encryption algorithm(s)
480       This indicates the types of encryption keys this checksum
481       mechanism can be used with.
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.)
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.
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.
506 Raeburn                                                         [Page 9]
508 INTERNET DRAFT                                             February 2003
511       The output of this function will also dictate the size of the
512       checksum.
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.
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.
524    These operations and attributes are all that should be required to
525    support Kerberos and various proposed preauthentication schemes.
527    As with encryption mechanism definition documents, documents defining
528    new checksum mechanisms should indicate validation processes and
529    known weaknesses.
531 4. Simplified profile for CBC ciphers with key derivation
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]
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.
549 4.1. A key derivation function
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.
562 Raeburn                                                        [Page 10]
564 INTERNET DRAFT                                             February 2003
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.
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].
580       Derived Key = DK(Base Key, Well-Known Constant)
582       DK(Key, Constant) = random-to-key(DR(Key, Constant))
584       DR(Key, Constant) = k-truncate(E(Key, Constant,
585                                        initial-cipher-state))
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.
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.
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):
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 = ...
610       DR(Key, Constant) = k-truncate(K1 | K2 | K3 | K4 ...)
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]:
618 Raeburn                                                        [Page 11]
620 INTERNET DRAFT                                             February 2003
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.
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....
639    Test vectors for n-fold are supplied in Appendix A.  [5]
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.
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.
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.
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.
662 4.2. Simplified profile parameters
664    These are the operations and attributes that must be defined:
674 Raeburn                                                        [Page 12]
676 INTERNET DRAFT                                             February 2003
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.
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).
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.
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.
707       This value must be a multiple of 8 bits (one octet).
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.
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).
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.
730 Raeburn                                                        [Page 13]
732 INTERNET DRAFT                                             February 2003
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.
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.
746    While there are still a number of properties to specify, they are
747    fewer and simpler than in the full profile.
749 4.3. Cryptosystem profile based on simplified profile
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.
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.
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.
767    The substring notation "[1..h]" in the following table should be read
768    as using 1-based indexing; leading substrings are used.
771                    cryptosystem from simplified profile
772 ----------------------------------------------------------------------------
773 protocol key format       As given.
775 specific key structure    Three protocol-format keys: { Kc, Ke, Ki }.
777 key-generation seed       As given.
778 length
780 required checksum         As defined below in section 4.4.
781 mechanism
786 Raeburn                                                        [Page 14]
788 INTERNET DRAFT                                             February 2003
791                    cryptosystem from simplified profile
792 ----------------------------------------------------------------------------
794 cipher state              initial vector (usually of length c)
796 initial cipher state      all bits zero
798 encryption 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
808 decryption 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
814 default string-to-key     As given.
815 params
817 pseudo-random function    tmp1 = H(octet-string)
818                           tmp2 = truncate tmp1 to multiple of m
819                           PRF = E(protocol-key, tmp2, initial-cipher-state)
821 key generation functions:
823 string-to-key function    As given.
825 random-to-key function    As given.
827 key-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.
832                           Kc = DK(base-key, usage | 0x99);
833                           Ke = DK(base-key, usage | 0xAA);
834                           Ki = DK(base-key, usage | 0x55);
842 Raeburn                                                        [Page 15]
844 INTERNET DRAFT                                             February 2003
847 4.4. Checksum profiles based on simplified profile
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:
854                 checksum mechanism from simplified profile
855              --------------------------------------------------
856              associated cryptosystem   as defined above
858              get_mic                   HMAC(Kc, message)[1..h]
860              verify_mic                get_mic and compare
862    The HMAC function and key Kc are as described in section 4.3.
864 5. Profiles for Kerberos encryption and checksum algorithms
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.
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.
877 5.1. Unkeyed checksums
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.
885 5.1.1. The RSA MD5 Checksum
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)
898 Raeburn                                                        [Page 16]
900 INTERNET DRAFT                                             February 2003
903    checksum.  RSA-MD5 is believed to be collision-proof.
905                                   rsa-md5
906                ----------------------------------------------
907                associated cryptosystem   any
909                get_mic                   rsa-md5(msg)
911                verify_mic                get_mic and compare
913    The rsa-md5 checksum algorithm is assigned a checksum type number of
914    seven (7).
916 5.1.2. The RSA MD4 Checksum
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.
924                                   rsa-md4
925                ----------------------------------------------
926                associated cryptosystem   any
928                get_mic                   md4(msg)
930                verify_mic                get_mic and compare
933    The rsa-md4 checksum algorithm is assigned a checksum type number of
934    two (2).
936 5.1.3. CRC-32 Checksum
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.
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
954 Raeburn                                                        [Page 17]
956 INTERNET DRAFT                                             February 2003
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.
966    Test values for this modified CRC function are included in appendix
967    A.5.
970                                    crc32
971                ----------------------------------------------
972                associated cryptosystem   any
974                get_mic                   crc32(msg)
976                verify_mic                get_mic and compare
979    The crc32 checksum algorithm is assigned a checksum type number of
980    one (1).
982 5.2. DES-based encryption and checksum types
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.
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.
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.
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.
1010 Raeburn                                                        [Page 18]
1012 INTERNET DRAFT                                             February 2003
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.
1025    Encryption data format
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.
1032                   +-----------+----------+---------+-----+
1033                   |confounder | checksum | msg-seq | pad |
1034                   +-----------+----------+---------+-----+
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.
1043    String or random-data to key transformation
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.
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
1066 Raeburn                                                        [Page 19]
1068 INTERNET DRAFT                                             February 2003
1071    result which is returned as the key.
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.
1077    Pseudocode follows:
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         }
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         }
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         }
1111         key_correction(key) {
1112              fixparity(key);
1113              if (is_weak_key(key))
1114                   key = key XOR 0xF0;
1115              return(key);
1116         }
1122 Raeburn                                                        [Page 20]
1124 INTERNET DRAFT                                             February 2003
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         }
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         }
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).
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:
1164         des_random_to_key(bitstring) {
1165              return key_correction(add_parity_bits(bitstring));
1166         }
1168 5.2.1. DES with MD5
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.
1178 Raeburn                                                        [Page 21]
1180 INTERNET DRAFT                                             February 2003
1183    The encryption system parameters for des-cbc-md5 are:
1185                                 des-cbc-md5
1186     --------------------------------------------------------------------
1187     protocol key format      8 bytes, parity in low bit of each
1189     specific key structure   copy of original key
1191     required checksum        rsa-md5-des
1192     mechanism
1194     key-generation seed      8 bytes
1195     length
1197     cipher state             8 bytes (CBC initial vector)
1199     initial cipher state     all-zero
1201     encryption function      des-cbc(confounder | checksum | msg | pad,
1202                                      ivec=oldstate)
1203                              where
1204                              checksum = md5(confounder | 0000...
1205                                             | msg | pad)
1207                              newstate = last block of des-cbc output
1209     decryption function      decrypt encrypted text and verify checksum
1211                              newstate = last block of ciphertext
1213     default string-to-key    empty string
1214     params
1216     pseudo-random function   des-cbc(md5(input-string), ivec=0)
1218     key generation functions:
1220     string-to-key            des_string_to_key
1222     random-to-key            des_random_to_key
1224     key-derivation           identity
1226    The des-cbc-md5 encryption type is assigned the etype value three
1227    (3).
1234 Raeburn                                                        [Page 22]
1236 INTERNET DRAFT                                             February 2003
1239 5.2.2. DES with MD4
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.
1245                                 des-cbc-md4
1246     --------------------------------------------------------------------
1247     protocol key format      8 bytes, parity in low bit of each
1249     specific key structure   copy of original key
1251     required checksum        rsa-md4-des
1252     mechanism
1254     key-generation seed      8 bytes
1255     length
1257     cipher state             8 bytes (CBC initial vector)
1259     initial cipher state     all-zero
1261     encryption function      des-cbc(confounder | checksum | msg | pad,
1262                                      ivec=oldstate)
1263                              where
1264                              checksum = md4(confounder | 0000...
1265                                             | msg | pad)
1267                              newstate = last block of des-cbc output
1269     decryption function      decrypt encrypted text and verify checksum
1271                              newstate = last block of ciphertext
1273     default string-to-key    empty string
1274     params
1276     pseudo-random function   des-cbc(md5(input-string), ivec=0)
1278     key generation functions:
1280     string-to-key            des_string_to_key
1282     random-to-key            copy input, then fix parity bits
1284     key-derivation           identity
1290 Raeburn                                                        [Page 23]
1292 INTERNET DRAFT                                             February 2003
1295    Note that des-cbc-md4 uses md5, not md4, in the PRF definition.
1297    The des-cbc-md4 encryption algorithm is assigned the etype value two
1298    (2).
1300 5.2.3. DES with CRC
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.
1308                                 des-cbc-crc
1309     --------------------------------------------------------------------
1310     protocol key format      8 bytes, parity in low bit of each
1312     specific key structure   copy of original key
1314     required checksum        rsa-md5-des
1315     mechanism
1317     key-generation seed      8 bytes
1318     length
1320     cipher state             8 bytes (CBC initial vector)
1322     initial cipher state     copy of original key
1324     encryption function      des-cbc(confounder | checksum | msg | pad,
1325                                      ivec=oldstate)
1326                              where
1327                              checksum = crc(confounder | 00000000
1328                                             | msg | pad)
1330                              newstate = last block of des-cbc output
1332     decryption function      decrypt encrypted text and verify checksum
1334                              newstate = last block of ciphertext
1336     default string-to-key    empty string
1337     params
1339     pseudo-random function   des-cbc(md5(input-string), ivec=0)
1341     key generation functions:
1346 Raeburn                                                        [Page 24]
1348 INTERNET DRAFT                                             February 2003
1351                                 des-cbc-crc
1352     --------------------------------------------------------------------
1354     string-to-key            des_string_to_key
1356     random-to-key            copy input, then fix parity bits
1358     key-derivation           identity
1360    The des-cbc-crc encryption algorithm is assigned the etype value one
1361    (1).
1363 5.2.4. RSA MD5 Cryptographic Checksum Using DES
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.
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.
1380                                 rsa-md5-des
1381       ----------------------------------------------------------------
1382       associated cryptosystem   des-cbc-md5, des-cbc-md4, des-cbc-crc
1384       get_mic                   des-cbc(key XOR 0xF0F0F0F0F0F0F0F0,
1385                                         conf | rsa-md5(conf | msg))
1387       verify_mic                decrypt and verify rsa-md5 checksum
1390    The rsa-md5-des checksum algorithm is assigned a checksum type number
1391    of eight (8).
1393 5.2.5. RSA MD4 Cryptographic Checksum Using DES
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
1402 Raeburn                                                        [Page 25]
1404 INTERNET DRAFT                                             February 2003
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.
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.
1416                                 rsa-md4-des
1417       ----------------------------------------------------------------
1418       associated cryptosystem   des-cbc-md5, des-cbc-md4, des-cbc-crc
1420       get_mic                   des-cbc(key XOR 0xF0F0F0F0F0F0F0F0,
1421                                         conf | rsa-md4(conf | msg),
1422                                         ivec=0)
1424       verify_mic                decrypt and verify rsa-md4 checksum
1426    The rsa-md4-des checksum algorithm is assigned a checksum type number
1427    of three (3).
1429 5.2.6. RSA MD4 Cryptographic Checksum Using DES alternative
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.
1440                                rsa-md4-des-k
1441       ----------------------------------------------------------------
1442       associated cryptosystem   des-cbc-md5, des-cbc-md4, des-cbc-crc
1444       get_mic                   des-cbc(key, md4(msg), ivec=key)
1446       verify_mic                decrypt, compute checksum and compare
1449    The rsa-md4-des-k checksum algorithm is assigned a checksum type
1450    number of six (6).
1458 Raeburn                                                        [Page 26]
1460 INTERNET DRAFT                                             February 2003
1463 5.2.7. DES CBC checksum
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.
1478                                   des-mac
1479    ----------------------------------------------------------------------
1480    associated     des-cbc-md5, des-cbc-md4, des-cbc-crc
1481    cryptosystem
1483    get_mic        des-cbc(key XOR 0xF0F0F0F0F0F0F0F0,
1484                           conf | des-mac(key, conf | msg | pad, ivec=0),
1485                           ivec=0)
1487    verify_mic     decrypt, compute DES MAC using confounder, compare
1490    The des-mac checksum algorithm is assigned a checksum type number of
1491    four (4).
1493 5.2.8. DES CBC checksum alternative
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.
1514 Raeburn                                                        [Page 27]
1516 INTERNET DRAFT                                             February 2003
1519                                  des-mac-k
1520       ----------------------------------------------------------------
1521       associated cryptosystem   des-cbc-md5, des-cbc-md4, des-cbc-crc
1523       get_mic                   des-mac(key, msg | pad, ivec=key)
1525       verify_mic                compute MAC and compare
1528    The des-mac-k checksum algorithm is assigned a checksum type number
1529    of five (5).
1531 5.3. Triple-DES based encryption and checksum types
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.
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.
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).
1548    The simplified profile for Triple DES, with key derivation as defined
1549    in section 4, is as follows:
1551                  des3-cbc-hmac-sha1-kd, hmac-sha1-des3-kd
1552               ------------------------------------------------
1553               protocol key format     24 bytes, parity in low
1554                                       bit of each
1556               key-generation seed     21 bytes
1557               length
1559               hash function           SHA-1
1561               HMAC output size        160 bits
1563               message block size      8 bytes
1570 Raeburn                                                        [Page 28]
1572 INTERNET DRAFT                                             February 2003
1575                  des3-cbc-hmac-sha1-kd, hmac-sha1-des3-kd
1576               ------------------------------------------------
1577               default string-to-key   empty string
1578               params
1580               encryption and          triple-DES encrypt and
1581               decryption functions    decrypt, in outer-CBC
1582                                       mode (cipher block size
1583                                       8 octets)
1585               key generation functions:
1587               random-to-key           DES3random-to-key (see
1588                                       below)
1590               string-to-key           DES3string-to-key (see
1591                                       below)
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).
1597 5.3.1. Triple DES Key Production (random-to-key, string-to-key)
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:
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
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.
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.
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
1626 Raeburn                                                        [Page 29]
1628 INTERNET DRAFT                                             February 2003
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:
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)
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".
1647 6. Use of Kerberos encryption outside this specification
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.
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).
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.
1678    The Kerberos protocol uses only the attributes and operations
1682 Raeburn                                                        [Page 30]
1684 INTERNET DRAFT                                             February 2003
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.
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]
1702 7. Assigned Numbers
1704    The following encryption type numbers are already assigned or
1705    reserved for use in Kerberos and related protocols.
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)
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.)
1738 Raeburn                                                        [Page 31]
1740 INTERNET DRAFT                                             February 2003
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.
1749    The following checksum type numbers are assigned or reserved.  As
1750    with encryption type numbers, some overloading of checksum numbers
1751    has occurred.
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]
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.
1779 8. Implementation Notes
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
1794 Raeburn                                                        [Page 32]
1796 INTERNET DRAFT                                             February 2003
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.)
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.
1811 9. Security Considerations
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.
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.
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.
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.
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
1850 Raeburn                                                        [Page 33]
1852 INTERNET DRAFT                                             February 2003
1855    leading zeros to effectively be ignored, so messages differing only
1856    in leading zero bits will have the same checksum.
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.
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.
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.
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.
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.
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.
1893 10. IANA Considerations
1895    None at present.  The management of encryption and checksum type
1896    number assignments may be transferred to IANA at some future time.
1906 Raeburn                                                        [Page 34]
1908 INTERNET DRAFT                                             February 2003
1911 11. Acknowledgments
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.
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.
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.
1929    Tom Yu provided the text describing the modifications to the standard
1930    CRC algorithm as Kerberos implementations actually use it.
1932    Miroslav Jurisic provided information for one of the UTF-8 test cases
1933    for the string-to-key functions.
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.
1939    Simon Josefsson contributed some clarifications to the DES "CBC
1940    checksum", string-to-key and weak key descriptions, and some test
1941    vectors.
1943    Simon Josefsson, Louis LeVay and others also caught some errors in
1944    earlier drafts.
1946 12. Editor's address
1948    Kenneth Raeburn
1949    Massachusetts Institute of Technology
1950    77 Massachusetts Avenue
1951    Cambridge, MA 02139
1952    raeburn@mit.edu
1962 Raeburn                                                        [Page 35]
1964 INTERNET DRAFT                                             February 2003
1967 13. Full Copyright Statement
1969    Copyright (C) The Internet Society (2003).  All Rights Reserved.
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.
1985    The limited permissions granted above are perpetual and will not be
1986    revoked by the Internet Society or its successors or assigns.
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."
1995 A. Test vectors
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.
2003 A.1. n-fold
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:
2018 Raeburn                                                        [Page 36]
2020 INTERNET DRAFT                                             February 2003
2023       64-fold("012345") =
2024       64-fold(303132333435) = be072631276b1955
2026       56-fold("password") =
2027       56-fold(70617373776f7264) = 78a07b6caf85fa
2029       64-fold("Rough Consensus, and Running Code") =
2030       64-fold(526f75676820436f6e73656e7375732c20616e642052756e
2031               6e696e6720436f6465) = bb6ed30870b7f0e0
2033       168-fold("password") =
2034       168-fold(70617373776f7264) =
2035                59e4a8ca7c0385c3c37b3f6d2000247cb6e6bd5b3e
2037       192-fold("MASSACHVSETTS INSTITVTE OF TECHNOLOGY"
2038       192-fold(4d41535341434856534554545320494e5354495456544520
2039                4f4620544543484e4f4c4f4759) =
2040                db3b0d8f0b061e603282b308a50841229ad798fab9540c1b
2042       168-fold("Q") =
2043       168-fold(51) =
2044                518a54a2 15a8452a 518a54a2 15a8452a
2045                518a54a2 15
2047       168-fold("ba") =
2048       168-fold(6261) =
2049                fb25d531 ae897449 9f52fd92 ea9857c4
2050                ba24cf29 7e
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).
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
2067    Note that the initial octets exactly match the input string when the
2068    output length is a multiple of the input length.
2074 Raeburn                                                        [Page 37]
2076 INTERNET DRAFT                                             February 2003
2079 A.2. mit_des_string_to_key
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.
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
2095    Test vector:
2098    salt:        "ATHENA.MIT.EDUraeburn"
2099                               415448454e412e4d49542e4544557261656275726e
2100    password:    "password"    70617373776f7264
2101    fan-fold result:           c01e38688ac86c2e
2102    intermediate key:          c11f38688ac86d2f
2103    DES key:                   cbc22fae235298e3
2107    salt:       "WHITEHOUSE.GOVdanny"   5748495445484f5553452e474f5664616e6e79
2108    password:   "potatoe"               706f7461746f65
2109    fan-fold result:                    a028944ee63c0416
2110    intermediate key:                   a129944fe63d0416
2111    DES key:                            df3d32a74fd92a01
2115    salt:      "EXAMPLE.COMpianist"  4558414D504C452E434F4D7069616E697374
2116    password:  g-clef                f09d849e
2117    fan-fold result:                 3c4a262c18fab090
2118    intermediate key:                3d4a262c19fbb091
2119    DES key:                         4ffb26bab0cd9413
2130 Raeburn                                                        [Page 38]
2132 INTERNET DRAFT                                             February 2003
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
2144    salt:       "AAAAAAAA"   4141414141414141
2145    password:   "11119999"   3131313139393939
2146    fan-fold result:         e0e0e0e0f0f0f0f0
2147    intermediate key:        e0e0e0e0f1f1f101
2148    DES key:                 984054d0f1a73e31
2152    salt:       "FFFFAAAA"   4646464641414141
2153    password:   "NNNN6666"   4e4e4e4e36363636
2154    fan-fold result:         1e1e1e1e0e0e0e0e
2155    intermediate key:        1f1f1f1f0e0e0efe
2156    DES key:                 c4bf6b25adf7a4f8
2159    This trace provided by Simon Josefsson shows the intermediate
2160    processing stages of one of the test inputs:
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;
2186 Raeburn                                                        [Page 39]
2188 INTERNET DRAFT                                             February 2003
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
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
2242 Raeburn                                                        [Page 40]
2244 INTERNET DRAFT                                             February 2003
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
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
2287      for (8byteblock in s) {
2288      }
2289             ;; for loop terminated
2298 Raeburn                                                        [Page 41]
2300 INTERNET DRAFT                                             February 2003
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
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
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
2322 A.3. DES3 DR and DK
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.
2330    key:                 dce06b1f64c857a11c3db57c51899b2cc1791008ce973b92
2331    usage:               0000000155
2332    DR:                  935079d14490a75c3093c4a6e8c3b049c71e6ee705
2333    DK:                  925179d04591a79b5d3192c4a7e9c289b049c71f6ee604cd
2335    key:                 5e13d31c70ef765746578531cb51c15bf11ca82c97cee9f2
2336    usage:               00000001aa
2337    DR:                  9f58e5a047d894101c469845d67ae3c5249ed812f2
2338    DK:                  9e58e5a146d9942a101c469845d67a20e3c4259ed913f207
2340    key:                 98e6fd8a04a4b6859b75a176540b9752bad3ecd610a252bc
2341    usage:               0000000155
2342    DR:                  12fff90c773f956d13fc2ca0d0840349dbd39908eb
2343    DK:                  13fef80d763e94ec6d13fd2ca1d085070249dad39808eabf
2345    key:                 622aec25a2fe2cad7094680b7c64940280084c1a7cec92b5
2346    usage:               00000001aa
2347    DR:                  f8debf05b097e7dc0603686aca35d91fd9a5516a70
2348    DK:                  f8dfbf04b097e6d9dc0702686bcb3489d91fd9a4516b703e
2354 Raeburn                                                        [Page 42]
2356 INTERNET DRAFT                                             February 2003
2359    key:                 d3f8298ccb166438dcb9b93ee5a7629286a491f838f802fb
2360    usage:               6b65726265726f73 ("kerberos")
2361    DR:                  2270db565d2a3d64cfbfdc5305d4f778a6de42d9da
2362    DK:                  2370da575d2a3da864cebfdc5204d56df779a7df43d9da43
2364    key:                 c1081649ada74362e6a1459d01dfd30d67c2234c940704da
2365    usage:               0000000155
2366    DR:                  348056ec98fcc517171d2b4d7a9493af482d999175
2367    DK:                  348057ec98fdc48016161c2a4c7a943e92ae492c989175f7
2369    key:                 5d154af238f46713155719d55e2f1f790dd661f279a7917c
2370    usage:               00000001aa
2371    DR:                  a8818bc367dadacbe9a6c84627fb60c294b01215e5
2372    DK:                  a8808ac267dada3dcbe9a7c84626fbc761c294b01315e5c1
2374    key:                 798562e049852f57dc8c343ba17f2ca1d97394efc8adc443
2375    usage:               0000000155
2376    DR:                  c813f88b3be2b2f75424ce9175fbc8483b88c8713a
2377    DK:                  c813f88a3be3b334f75425ce9175fbe3c8493b89c8703b49
2379    key:                 26dce334b545292f2feab9a8701a89a4b99eb9942cecd016
2380    usage:               00000001aa
2381    DR:                  f58efc6f83f93e55e695fd252cf8fe59f7d5ba37ec
2382    DK:                  f48ffd6e83f83e7354e694fd252cf83bfe58f7d5ba37ec5d
2385 A.4. DES3string_to_key
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.
2390     salt:   "ATHENA.MIT.EDUraeburn"
2391     passwd: "password"
2392     key:    850bb51358548cd05e86768c313e3bfef7511937dcf72c3e
2394     salt:   "WHITEHOUSE.GOVdanny"
2395     passwd: "potatoe"
2396     key:    dfcd233dd0a43204ea6dc437fb15e061b02979c1f74f377a
2398     salt:   "EXAMPLE.COMbuckaroo"
2399     passwd: "penny"
2400     key:    6d2fcdf2d6fbbc3ddcadb5da5710a23489b0d3b69d5d9d4a
2402     salt:   "ATHENA.MIT.EDUJuri" + s-caron + "i" + c-acute
2403     passwd: eszett
2404     key:    16d5a40e1ce3bacb61b9dce00470324c831973a7b952feb0
2410 Raeburn                                                        [Page 43]
2412 INTERNET DRAFT                                             February 2003
2415     salt:   "EXAMPLE.COMpianist"
2416     passwd: g-clef
2417     key:    85763726585dbc1cce6ec43e1f751f07f1c4cbb098f40b19
2419 A.5. Modified CRC-32
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.)
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
2443 B. Significant Changes from RFC 1510
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:
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.
2466 Raeburn                                                        [Page 44]
2468 INTERNET DRAFT                                             February 2003
2471       The use of key derivation is new.
2473       Several new methods are introduced, including generation of a key
2474       in wire-protocol format from random input data.
2476       The means for influencing the string-to-key algorithm are laid out
2477       more clearly.
2479    Triple-DES support is new.
2481    The pseudo-random function is new.
2483    The des-cbc-crc, DES string-to-key and CRC descriptions have been
2484    updated to align them with existing implementations.
2486    [Kerb1510] had no indication what character set or encoding might be
2487    used for pass phrases and salts.
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.
2497 Notes
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.
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.
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.
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
2522 Raeburn                                                        [Page 45]
2524 INTERNET DRAFT                                             February 2003
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.
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].
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.
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.
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.
2565 Normative References
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.
2578 Raeburn                                                        [Page 46]
2580 INTERNET DRAFT                                             February 2003
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.
2634 Raeburn                                                        [Page 47]
2636 INTERNET DRAFT                                             February 2003
2639 Informative References
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.
2672 Notes to RFC Editor
2674    Before publication of this document as an RFC, the following changes
2675    are needed:
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.
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.
2686    Delete this section.
2690 Raeburn                                                        [Page 48]