this mechanism; several must still be defined for each new algorithm
pair.
5.1. A Key Derivation Function
Rather than define some scheme by which a "protocol key" is composed
of a large number of encryption keys, we use keys derived from a base
key to perform cryptographic operations. The base key must be used
only for generating the derived keys, and this derivation must be
non-invertible and entropy preserving. Given these restrictions,
compromise of one derived key does not compromise others. Attack of
the base key is limited, as it is only used for derivation and is not
exposed to any user data.
To generate a derived key from a base key, we generate a pseudorandom
octet string by using an algorithm DR, described below, and generate
a key from that octet string by using a function dependent on the
encryption algorithm. The input length needed for that function,
which is also dependent on the encryption algorithm, dictates the
length of the string to be generated by the DR algorithm (the value
"k" below). These procedures are based on the key derivation in
[Blumenthal96].
Derived Key = DK(Base Key, Well-Known Constant)
DK(Key, Constant) = random-to-key(DR(Key, Constant))
DR(Key, Constant) = k-truncate(E(Key, Constant,
initial-cipher-state))
Here DR is the random-octet generation function described below, and
DK is the key-derivation function produced from it. In this
construction, E(Key, Plaintext, CipherState) is a cipher, Constant is
a well-known constant determined by the specific usage of this
function, and k-truncate truncates its argument by taking the first k
bits. Here, k is the key generation seed length needed for the
encryption system.
The output of the DR function is a string of bits; the actual key is
produced by applying the cryptosystem’s random-to-key operation on
this bitstring.
If the Constant is smaller than the cipher block size of E, then it
must be expanded with n-fold() so it can be encrypted. If the output
of E is shorter than k bits, it is fed back into the encryption as
many times as necessary. The construct is as follows (where |
indicates concatentation):
K1 = E(Key, n-fold(Constant), initial-cipher-state)
K2 = E(Key, K1, initial-cipher-state)
K3 = E(Key, K2, initial-cipher-state)
K4 = ...
DR(Key, Constant) = k-truncate(K1 | K2 | K3 | K4 ...)
n-fold is an algorithm that takes m input bits and "stretches" them
to form n output bits with equal contribution from each input bit to
the output, as described in [Blumenthal96]:
We first define a primitive called n-folding, which takes a
variable-length input block and produces a fixed-length output
sequence. The intent is to give each input bit approximately
equal weight in determining the value of each output bit. Note
that whenever we need to treat a string of octets as a number, the
assumed representation is Big-Endian -- Most Significant Byte
first.
To n-fold a number X, replicate the input value to a length that
is the least common multiple of n and the length of X. Before
each repetition, the input is rotated to the right by 13 bit
positions. The successive n-bit chunks are added together using
1’s-complement addition (that is, with end-around carry) to yield
a n-bit result....
Test vectors for n-fold are supplied in appendix A [5].
In this section, n-fold is always used to produce c bits of output,
where c is the cipher block size of E.
The size of the Constant must not be larger than c, because reducing
the length of the Constant by n-folding can cause collisions.
If the size of the Constant is smaller than c, then the Constant must
be n-folded to length c. This string is used as input to E. If the
block size of E is less than the random-to-key input size, then the
output from E is taken as input to a second invocation of E. This
process is repeated until the number of bits accumulated is greater
than or equal to the random-to-key input size. When enough bits have
been computed, the first k are taken as the random data used to
create the key with the algorithm-dependent random-to-key function.
As the derived key is the result of one or more encryptions in the
base key, deriving the base key from the derived key is equivalent to
determining the key from a very small number of plaintext/ciphertext
pairs. Thus, this construction is as strong as the cryptosystem
itself.
5.2. Simplified Profile Parameters
These are the operations and attributes that must be defined:
protocol key format
string-to-key function
default string-to-key parameters
key-generation seed length, k
random-to-key function
As above for the normal encryption mechanism profile.
unkeyed hash algorithm, H
This should be a collision-resistant hash algorithm with fixed-
size output, suitable for use in an HMAC [HMAC]. It must support
inputs of arbitrary length. Its output must be at least the
message block size (below).
HMAC output size, h
This indicates the size of the leading substring output by the
HMAC function that should be used in transmitted messages. It
should be at least half the output size of the hash function H,
and at least 80 bits; it need not match the output size.
message block size, m
This is the size of the smallest units the cipher can handle in
the mode in which it is being used. Messages will be padded to a
multiple of this size. If a block cipher is used in a mode that
can handle messages that are not multiples of the cipher block
size, such as CBC mode with cipher text stealing (CTS, see [RC5]),
this value would be one octet. For traditional CBC mode with
padding, it would be the underlying cipher’s block size.
This value must be a multiple of eight bits (one octet).
encryption/decryption functions, E and D
These are basic encryption and decryption functions for messages
of sizes that are multiples of the message block size. No
integrity checking or confounder should be included here. For
inputs these functions take the IV or similar data, a protocol-
format key, and an octet string, returning a new IV and octet
string.
The encryption function is not required to use CBC mode but is
assumed to be using something with similar properties. In
particular, prepending a cipher block-size confounder to the
plaintext should alter the entire ciphertext (comparable to
choosing and including a random initial vector for CBC mode).
The result of encrypting one cipher block (of size c, above) must
be deterministic for the random octet generation function DR in
the previous section to work. For best security, it should also
be no larger than c.
cipher block size, c
This is the block size of the block cipher underlying the
encryption and decryption functions indicated above, used for key
derivation and for the size of the message confounder and initial
vector. (If a block cipher is not in use, some comparable
parameter should be determined.) It must be at least 5 octets.
This is not actually an independent parameter; rather, it is a
property of the functions E and D. It is listed here to clarify
the distinction between it and the message block size, m.
Although there are still a number of properties to specify, they are
fewer and simpler than in the full profile.
5.3. Cryptosystem Profile Based on Simplified Profile
The above key derivation function is used to produce three
intermediate keys. One is used for computing checksums of
unencrypted data. The other two are used for encrypting and
checksumming plaintext to be sent encrypted.
The ciphertext output is the concatenation of the output of the basic
encryption function E and a (possibly truncated) HMAC using the
specified hash function H, both applied to the plaintext with a
random confounder prefix and sufficient padding to bring it to a
multiple of the message block size. When the HMAC is computed, the
key is used in the protocol key form.
Decryption is performed by removing the (partial) HMAC, decrypting
the remainder, and verifying the HMAC. The cipher state is an
initial vector, initialized to zero.
The substring notation "[1..h]" in the following table should be read
as using 1-based indexing; leading substrings are used.
Cryptosystem from Simplified Profile
------------------------------------------------------------------------
protocol key format As given.
specific key structure Three protocol-format keys: { Kc, Ke, Ki }.
key-generation seed As given.
length
required checksum As defined below in section 5.4.
mechanism
cipher state Initial vector (usually of length c)
initial cipher state All bits zero
encryption function conf = Random string of length c
pad = Shortest string to bring confounder
and plaintext to a length that’s a
multiple of m.
(C1, newIV) = E(Ke, conf | plaintext | pad,
oldstate.ivec)
H1 = HMAC(Ki, conf | plaintext | pad)
ciphertext = C1 | H1[1..h]
newstate.ivec = newIV
decryption function (C1,H1) = ciphertext
(P1, newIV) = D(Ke, C1, oldstate.ivec)
if (H1 != HMAC(Ki, P1)[1..h])
report error
newstate.ivec = newIV
default string-to-key As given.
params
pseudo-random function tmp1 = H(octet-string)
tmp2 = truncate tmp1 to multiple of m
PRF = E(DK(protocol-key, prfconstant),
tmp2, initial-cipher-state)
The "prfconstant" used in the PRF operation is the three-octet string
"prf".
Cryptosystem from Simplified Profile
------------------------------------------------------------------------
key generation functions:
string-to-key function As given.
random-to-key function As given.
key-derivation function The "well-known constant" used for the DK
function is the key usage number, expressed as
four octets in big-endian order, followed by
one octet indicated below.
Kc = DK(base-key, usage | 0x99);
Ke = DK(base-key, usage | 0xAA);
Ki = DK(base-key, usage | 0x55);
5.4. Checksum Profiles Based on Simplified Profile
When an encryption system is defined with the simplified profile
given in section 5.2, a checksum algorithm may be defined for it as
follows:
Checksum Mechanism from Simplified Profile
--------------------------------------------------
associated cryptosystem As defined above.
get_mic HMAC(Kc, message)[1..h]
verify_mic get_mic and compare
The HMAC function and key Kc are as described in section 5.3.
6. Profiles for Kerberos Encryption and Checksum Algorithms
These profiles describe the encryption and checksum systems defined
for Kerberos. The astute reader will notice that some of them do not
fulfill all the requirements outlined in previous sections. These
systems are defined for backward compatibility; newer implementations
should (whenever possible) attempt to utilize encryption systems that
satisfy all the profile requirements.
The full list of current encryption and checksum type number
assignments, including values currently reserved but not defined in
this document, is given in section 8.
6.1. Unkeyed Checksums
These checksum types use no encryption keys and thus can be used in
combination with any encryption type, but they may only be used with
caution, in limited circumstances where the lack of a key does not
provide a window for an attack, preferably as part of an encrypted
message [6]. Keyed checksum algorithms are recommended.
6.1.1. The RSA MD5 Checksum
The RSA-MD5 checksum calculates a checksum by using the RSA MD5
algorithm [MD5-92]. The algorithm takes as input an input message of
arbitrary length and produces as output a 128-bit (sixteen octet)
checksum.
rsa-md5
----------------------------------------------
associated cryptosystem any
get_mic rsa-md5(msg)
verify_mic get_mic and compare
The rsa-md5 checksum algorithm is assigned a checksum type number of
seven (7).
6.1.2. The RSA MD4 Checksum
The RSA-MD4 checksum calculates a checksum using the RSA MD4
algorithm [MD4-92]. The algorithm takes as input an input message of
arbitrary length and produces as output a 128-bit (sixteen octet)
checksum.
rsa-md4
----------------------------------------------
associated cryptosystem any
get_mic md4(msg)
verify_mic get_mic and compare
The rsa-md4 checksum algorithm is assigned a checksum type number of
two (2).
6.1.3. CRC-32 Checksum
This CRC-32 checksum calculates a checksum based on a cyclic
redundancy check as described in ISO 3309 [CRC] but modified as
described below. The resulting checksum is four (4) octets in
length. The CRC-32 is neither keyed nor collision-proof; thus, the
use of this checksum is not recommended. An attacker using a
probabilistic chosen-plaintext attack as described in [SG92] might be
able to generate an alternative message that satisfies the checksum.
The CRC-32 checksum used in the des-cbc-crc encryption mode is
identical to the 32-bit FCS described in ISO 3309 with two
exceptions: The sum with the all-ones polynomial times x**k is
omitted, and the final remainder is not ones-complemented. ISO 3309
describes the FCS in terms of bits, whereas this document describes
the Kerberos protocol in terms of octets. To clarify the ISO 3309
definition for the purpose of computing the CRC-32 in the des-cbc-crc
encryption mode, the ordering of bits in each octet shall be assumed
to be LSB first. Given this assumed ordering of bits within an
octet, the mapping of bits to polynomial coefficients shall be
identical to that specified in ISO 3309.
Test values for this modified CRC function are included in appendix
A.5.
crc32
----------------------------------------------
associated cryptosystem any
get_mic crc32(msg)
verify_mic get_mic and compare
The crc32 checksum algorithm is assigned a checksum type number of
one (1).
6.2. DES-Based Encryption and Checksum Types
These encryption systems encrypt information under the Data
Encryption Standard [DES77] by using the cipher block chaining mode
[DESM80]. A checksum is computed as described below and placed in
the cksum field. DES blocks are eight bytes. As a result, the data
to be encrypted (the concatenation of confounder, checksum, and
message) must be padded to an eight byte boundary before encryption.
The values of the padding bytes are unspecified.
Plaintext and DES ciphertext are encoded as blocks of eight octets,
which are concatenated to make the 64-bit inputs for the DES
algorithms. The first octet supplies the eight most significant bits
(with the octet’s MSB used as the DES input block’s MSB, etc.), the
second octet the next eight bits, and so on. The eighth octet
supplies the 8 least significant bits.
Encryption under DES using cipher block chaining requires an
additional input in the form of an initialization vector; this vector
is specified below for each encryption system.
The DES specifications [DESI81] identify four ’weak’ and twelve
’semi-weak’ keys; these keys SHALL NOT be used for encrypting
messages for use in Kerberos. The "variant keys" generated for the
RSA-MD5-DES, RSA-MD4-DES, and DES-MAC checksum types by an
eXclusive-OR of a DES key with a constant are not checked for this
property.
A DES key is eight octets of data. This consists of 56 bits of
actual key data, and eight parity bits, one per octet. The key is
encoded as a series of eight octets written in MSB-first order. The
bits within the key are also encoded in MSB order. For example, if
the encryption key is
(B1,B2,...,B7,P1,B8,...,B14,P2,B15,...,B49,P7,B50,...,B56,P8), where
B1,B2,...,B56 are the key bits in MSB order, and P1,P2,...,P8 are the
parity bits, the first octet of the key would be B1,B2,...,B7,P1
(with B1 as the most significant bit). See the [DESM80] introduction
for reference.
Encryption Data Format
The format for the data to be encrypted includes a one-block
confounder, a checksum, the encoded plaintext, and any necessary
padding, as described in the following diagram. The msg-seq field
contains the part of the protocol message to be encrypted.
+-----------+----------+---------+-----+
|confounder | checksum | msg-seq | pad |
+-----------+----------+---------+-----+
One generates a random confounder of one block, placing it in
’confounder’; zeros out the ’checksum’ field (of length appropriate
to exactly hold the checksum to be computed); adds the necessary
padding; calculates the appropriate checksum over the whole sequence,
placing the result in ’checksum’; and then encrypts using the
specified encryption type and the appropriate key.
String or Random-Data to Key Transformation
To generate a DES key from two UTF-8 text strings (password and
salt), the two strings are concatenated, password first, and the
result is then padded with zero-valued octets to a multiple of eight
octets.
The top bit of each octet (always zero if the password is plain
ASCII, as was assumed when the original specification was written) is
discarded, and the remaining seven bits of each octet form a
bitstring. This is then fan-folded and eXclusive-ORed with itself to
produce a 56-bit string. An eight-octet key is formed from this
string, each octet using seven bits from the bitstring, leaving the
least significant bit unassigned. The key is then "corrected" by
correcting the parity on the key, and if the key matches a ’weak’ or
’semi-weak’ key as described in the DES specification, it is
eXclusive-ORed with the constant 0x00000000000000F0. This key is
then used to generate a DES CBC checksum on the initial string with
the salt appended. The result of the CBC checksum is then
"corrected" as described above to form the result, which is returned
as the key.
For purposes of the string-to-key function, the DES CBC checksum is
calculated by CBC encrypting a string using the key as IV and the
final eight byte block as the checksum.
Pseudocode follows:
removeMSBits(8byteblock) {
/* Treats a 64 bit block as 8 octets and removes the MSB in
each octet (in big endian mode) and concatenates the
result. E.g., the input octet string:
01110000 01100001 11110011 01110011 11110111 01101111
11110010 01100100
results in the output bitstring:
1110000 1100001 1110011 1110011 1110111 1101111
1110010 1100100 */
}
reverse(56bitblock) {
/* Treats a 56-bit block as a binary string and reverses it.
E.g., the input string:
1000001 1010100 1001000 1000101 1001110 1000001
0101110 1001101
results in the output string:
1011001 0111010 1000001 0111001 1010001 0001001
0010101 1000001 */
}
add_parity_bits(56bitblock) {
/* Copies a 56-bit block into a 64-bit block, left shifts
content in each octet, and add DES parity bit.
E.g., the input string:
1100000 0001111 0011100 0110100 1000101 1100100
0110110 0010111
results in the output string:
11000001 00011111 00111000 01101000 10001010 11001000
01101101 00101111 */
}
key_correction(key) {
fixparity(key);
if (is_weak_key(key))
key = key XOR 0xF0;
return(key);
}
mit_des_string_to_key(string,salt) {
odd = 1;
s = string | salt;
tempstring = 0; /* 56-bit string */
pad(s); /* with nulls to 8 byte boundary */
for (8byteblock in s) {
56bitstring = removeMSBits(8byteblock);
if (odd == 0) reverse(56bitstring);
odd = ! odd;
tempstring = tempstring XOR 56bitstring;