with encryption-type numbers, some overloading of checksum numbers
has occurred.
Checksum type sumtype checksum section or
value size reference
---------------------------------------------------------------------
CRC32 1 4 6.1.3
rsa-md4 2 16 6.1.2
rsa-md4-des 3 24 6.2.5
des-mac 4 16 6.2.7
des-mac-k 5 8 6.2.8
rsa-md4-des-k 6 16 6.2.6
rsa-md5 7 16 6.1.1
rsa-md5-des 8 24 6.2.4
rsa-md5-des3 9 24 ??
sha1 (unkeyed) 10 20 ??
hmac-sha1-des3-kd 12 20 6.3
hmac-sha1-des3 13 20 ??
sha1 (unkeyed) 14 20 ??
hmac-sha1-96-aes128 15 20 [KRB5-AES]
hmac-sha1-96-aes256 16 20 [KRB5-AES]
[reserved] 0x8003 ? [GSS-KRB5]
Encryption and checksum-type numbers are signed 32-bit values. Zero
is invalid, and negative numbers are reserved for local use. All
standardized values must be positive.
9. Implementation Notes
The "interface" described here is the minimal information that must
be defined to make a cryptosystem useful within Kerberos in an
interoperable fashion. The use of functional notation used in some
places is not an attempt to define an API for cryptographic
functionality within Kerberos. Actual implementations providing
clean APIs will probably make additional information available, that
could be derived from a specification written to the framework given
here. For example, an application designer may wish to determine the
largest number of bytes that can be encrypted without overflowing a
certain size output buffer or conversely, the maximum number of bytes
that might be obtained by decrypting a ciphertext message of a given
size. (In fact, an implementation of the GSS-API Kerberos mechanism
[GSS-KRB5] will require some of these.)
The presence of a mechanism in this document should not be taken to
indicate that it must be implemented for compliance with any
specification; required mechanisms will be specified elsewhere.
Indeed, some of the mechanisms described here for backward
compatibility are now considered rather weak for protecting critical
data.
10. Security Considerations
Recent years have brought so many advancements in large-scale attacks
capability against DES that it is no longer considered a strong
encryption mechanism. Triple-DES is generally preferred in its
place, despite its poorer performance. See [ESP-DES] for a summary
of some of the potential attacks and [EFF-DES] for a detailed
discussion of the implementation of particular attacks. However,
most Kerberos implementations still have DES as their primary
interoperable encryption type.
DES has four ’weak’ keys and twelve ’semi-weak’ keys, and the use of
single-DES here avoids them. However, DES also has 48 ’possibly-
weak’ keys [Schneier96] (note that the tables in many editions of the
reference contains errors) that are not avoided.
DES weak keys have the property that E1(E1(P)) = P (where E1 denotes
encryption of a single block with key 1). DES semi-weak keys, or
"dual" keys, are pairs of keys with the property that E1(P) = D2(P),
and thus E2(E1(P)) = P. Because of the use of CBC mode and the
leading random confounder, however, these properties are unlikely to
present a security problem.
Many of the choices concerning when to perform weak-key corrections
relate more to compatibility with existing implementations than to
any risk analysis.
Although checks are also done for the component DES keys in a
triple-DES key, the nature of the weak keys make it extremely
unlikely that they will weaken the triple-DES encryption. It is only
slightly more likely than having the middle of the three sub-keys
match one of the other two, which effectively converts the encryption
to single-DES - a case we make no effort to avoid.
The true CRC-32 checksum is not collision-proof; an attacker could
use a probabilistic chosen-plaintext attack to generate a valid
message even if a confounder is used [SG92]. The use of collision-
proof checksums is of course recommended for environments where such
attacks represent a significant threat. The "simplifications" (read:
bugs) introduced when CRC-32 was implemented for Kerberos cause
leading zeros effectively to be ignored, so messages differing only
in leading zero bits will have the same checksum.
[HMAC] and [IPSEC-HMAC] discuss weaknesses of the HMAC algorithm.
Unlike [IPSEC-HMAC], the triple-DES specification here does not use
the suggested truncation of the HMAC output. As pointed out in
[IPSEC-HMAC], SHA-1 was not developed for use as a keyed hash
function, which is a criterion of HMAC. [HMAC-TEST] contains test
vectors for HMAC-SHA-1.
The mit_des_string_to_key function was originally constructed with
the assumption that all input would be ASCII; it ignores the top bit
of each input byte. Folding with XOR is also not an especially good
mixing mechanism for preserving randomness.
The n-fold function used in the string-to-key operation for des3-
cbc-hmac-sha1-kd was designed to cause each bit of input to
contribute equally to the output. It was not designed to maximize or
equally distribute randomness in the input, and conceivably
randomness may be lost in cases of partially structured input. This
should only be an issue for highly structured passwords, however.
[RFC1851] discusses the relative strength of triple-DES encryption.
The relatively slow speed of triple-DES encryption may also be an
issue for some applications.
[Bellovin91] suggests that analyses of encryption schemes include a
model of an attacker capable of submitting known plaintexts to be
encrypted with an unknown key, as well as be able to perform many
types of operations on known protocol messages. Recent experiences
with the chosen-plaintext attacks on Kerberos version 4 bear out the
value of this suggestion.
The use of unkeyed encrypted checksums, such as those used in the
single-DES cryptosystems specified in [Kerb1510], allows for cut-
and-paste attacks, especially if a confounder is not used. In
addition, unkeyed encrypted checksums are vulnerable to chosen-
plaintext attacks: An attacker with access to an encryption oracle
can easily encrypt the required unkeyed checksum along with the
chosen plaintext. [Bellovin99] These weaknesses, combined with a
common implementation design choice described below, allow for a
cross-protocol attack from version 4 to version 5.
The use of a random confounder is an important means to prevent an
attacker from making effective use of protocol exchanges as an
encryption oracle. In Kerberos version 4, the encryption of constant
plaintext to constant ciphertext makes an effective encryption oracle
for an attacker. The use of random confounders in [Kerb1510]
frustrates this sort of chosen-plaintext attack.
Using the same key for multiple purposes can enable or increase the
scope of chosen-plaintext attacks. Some software that implements
both versions 4 and 5 of the Kerberos protocol uses the same keys for
both versions. This enables the encryption oracle of version 4 to be
used to attack version 5. Vulnerabilities to attacks such as this
cross-protocol attack make it unwise to use a key for multiple
purposes.
This document, like the Kerberos protocol, does not address limiting
the amount of data a key may be used with to a quantity based on the
robustness of the algorithm or size of the key. It is assumed that
any defined algorithms and key sizes will be strong enough to support
very large amounts of data, or they will be deprecated once
significant attacks are known.
This document also places no bounds on the amount of data that can be
handled in various operations. To avoid denial of service attacks,
implementations will probably seek to restrict message sizes at some
higher level.
11. IANA Considerations
Two registries for numeric values have been created: Kerberos
Encryption Type Numbers and Kerberos Checksum Type Numbers. These
are signed values ranging from -2147483648 to 2147483647. Positive
values should be assigned only for algorithms specified in accordance
with this specification for use with Kerberos or related protocols.
Negative values are for private use; local and experimental
algorithms should use these values. Zero is reserved and may not be
assigned.
Positive encryption- and checksum-type numbers may be assigned
following either of two policies described in [BCP26].
Standards-track specifications may be assigned values under the
Standards Action policy.
Specifications in non-standards track RFCs may be assigned values
after Expert Review. A non-IETF specification may be assigned values
by publishing an Informational or standards-track RFC referencing the
external specification; that specification must be public and
published in some permanent record, much like the IETF RFCs. It is
highly desirable, though not required, that the full specification be
published as an IETF RFC.
Smaller encryption type values should be used for IETF standards-
track mechanisms, and much higher values (16777216 and above) for
other mechanisms. (Rationale: In the Kerberos ASN.1 encoding,
smaller numbers encode to smaller octet sequences, so this favors
standards-track mechanisms with slightly smaller messages.) Aside
from that guideline, IANA may choose numbers as it sees fit.
Internet-Draft specifications should not include values for
encryption- and checksum-type numbers. Instead, they should indicate
that values would be assigned by IANA when the document is approved
as an RFC. For development and interoperability testing, values in
the private-use range (negative values) may be used but should not be
included in the draft specification.
Each registered value should have an associated unique reference
name. The lists given in section 8 were used to create the initial
registry; they include reservations for specifications in progress in
parallel with this document, and certain other values believed to
already be in use.
12. Acknowledgements
This document is an extension of the encryption specification
included in [Kerb1510] by B. Clifford Neuman and John Kohl, and much
of the text of the background, concepts, and DES specifications is
drawn directly from that document.
The abstract framework presented in this document was put together by
Jeff Altman, Sam Hartman, Jeff Hutzelman, Cliff Neuman, Ken Raeburn,
and Tom Yu, and the details were refined several times based on
comments from John Brezak and others.
Marc Horowitz wrote the original specification of triple-DES and key
derivation in a pair of Internet-Drafts (under the names draft-
horowitz-key-derivation and draft-horowitz-kerb-key-derivation) that
were later folded into a draft revision of [Kerb1510], from which
this document was later split off.
Tom Yu provided the text describing the modifications to the standard
CRC algorithm as Kerberos implementations actually use it, and some
of the text in the Security Considerations section.
Miroslav Jurisic provided information for one of the UTF-8 test cases
for the string-to-key functions.
Marcus Watts noticed some errors in earlier versions and pointed out
that the simplified profile could easily be modified to support
cipher text stealing modes.
Simon Josefsson contributed some clarifications to the DES "CBC
checksum" and string-to-key and weak key descriptions, and some test
vectors.
Simon Josefsson, Louis LeVay, and others also caught some errors in
earlier versions of this document.
A. Test Vectors
This section provides test vectors for various functions defined or
described in this document. For convenience, most inputs are ASCII
strings, though some UTF-8 samples are provided for string-to-key
functions. Keys and other binary data are specified as hexadecimal
strings.
A.1. n-fold
The n-fold function is defined in section 5.1. As noted there, the
sample vector in the original paper defining the algorithm appears to
be incorrect. Here are some test cases provided by Marc Horowitz and
Simon Josefsson:
64-fold("012345") =
64-fold(303132333435) = be072631276b1955
56-fold("password") =
56-fold(70617373776f7264) = 78a07b6caf85fa
64-fold("Rough Consensus, and Running Code") =
64-fold(526f75676820436f6e73656e7375732c20616e642052756e
6e696e6720436f6465) = bb6ed30870b7f0e0
168-fold("password") =
168-fold(70617373776f7264) =
59e4a8ca7c0385c3c37b3f6d2000247cb6e6bd5b3e
192-fold("MASSACHVSETTS INSTITVTE OF TECHNOLOGY")
192-fold(4d41535341434856534554545320494e5354495456544520
4f4620544543484e4f4c4f4759) =
db3b0d8f0b061e603282b308a50841229ad798fab9540c1b
168-fold("Q") =
168-fold(51) =
518a54a2 15a8452a 518a54a2 15a8452a
518a54a2 15
168-fold("ba") =
168-fold(6261) =
fb25d531 ae897449 9f52fd92 ea9857c4
ba24cf29 7e
Here are some additional values corresponding to folded values of the
string "kerberos"; the 64-bit form is used in the des3 string-to-key
(section 6.3.1).
64-fold("kerberos") =
6b657262 65726f73
128-fold("kerberos") =
6b657262 65726f73 7b9b5b2b 93132b93
168-fold("kerberos") =
8372c236 344e5f15 50cd0747 e15d62ca
7a5a3bce a4
256-fold("kerberos") =
6b657262 65726f73 7b9b5b2b 93132b93
5c9bdcda d95c9899 c4cae4de e6d6cae4
Note that the initial octets exactly match the input string when the
output length is a multiple of the input length.
A.2. mit_des_string_to_key
The function mit_des_string_to_key is defined in section 6.2. We
present here several test values, with some of the intermediate
results. The fourth test demonstrates the use of UTF-8 with three
characters. The last two tests are specifically constructed so as to
trigger the weak-key fixups for the intermediate key produced by
fan-folding; we have no test cases that cause such fixups for the
final key.
UTF-8 encodings used in test vector:
eszett U+00DF C3 9F s-caron U+0161 C5 A1
c-acute U+0107 C4 87 g-clef U+1011E F0 9D 84 9E
Test vector:
salt: "ATHENA.MIT.EDUraeburn"
415448454e412e4d49542e4544557261656275726e
password: "password" 70617373776f7264
fan-fold result: c01e38688ac86c2e
intermediate key: c11f38688ac86d2f
DES key: cbc22fae235298e3
salt: "WHITEHOUSE.GOVdanny"
5748495445484f5553452e474f5664616e6e79
password: "potatoe" 706f7461746f65
fan-fold result: a028944ee63c0416
intermediate key: a129944fe63d0416
DES key: df3d32a74fd92a01
salt: "EXAMPLE.COMpianist" 4558414D504C452E434F4D7069616E697374
password: g-clef (U+1011E) f09d849e
fan-fold result: 3c4a262c18fab090
intermediate key: 3d4a262c19fbb091
DES key: 4ffb26bab0cd9413
salt: "ATHENA.MIT.EDUJuri" + s-caron(U+0161) + "i" + c-acute(U+0107)
415448454e412e4d49542e4544554a757269c5a169c487
password: eszett(U+00DF)
c39f
fan-fold result:b8f6c40e305afc9e
intermediate key: b9f7c40e315bfd9e
DES key: 62c81a5232b5e69d
salt: "AAAAAAAA" 4141414141414141
password: "11119999" 3131313139393939
fan-fold result: e0e0e0e0f0f0f0f0
intermediate key: e0e0e0e0f1f1f101
DES key: 984054d0f1a73e31
salt: "FFFFAAAA" 4646464641414141
password: "NNNN6666" 4e4e4e4e36363636
fan-fold result: 1e1e1e1e0e0e0e0e
intermediate key: 1f1f1f1f0e0e0efe
DES key: c4bf6b25adf7a4f8
This trace provided by Simon Josefsson shows the intermediate
processing stages of one of the test inputs:
string_to_key (des-cbc-md5, string, salt)
;; string:
;; `password’ (length 8 bytes)
;; 70 61 73 73 77 6f 72 64
;; salt:
;; `ATHENA.MIT.EDUraeburn’ (length 21 bytes)
;; 41 54 48 45 4e 41 2e 4d 49 54 2e 45 44 55 72 61
;; 65 62 75 72 6e
des_string_to_key (string, salt)
;; String:
;; `password’ (length 8 bytes)
;; 70 61 73 73 77 6f 72 64
;; Salt:
;; `ATHENA.MIT.EDUraeburn’ (length 21 bytes)
;; 41 54 48 45 4e 41 2e 4d 49 54 2e 45 44 55 72 61
;; 65 62 75 72 6e
odd = 1;
s = string | salt;
tempstring = 0; /* 56-bit string */
pad(s); /* with nulls to 8 byte boundary */
;; s = pad(string|salt):
;; `passwordATHENA.MIT.EDUraeburn\x00\x00\x00’
;; (length 32 bytes)
;; 70 61 73 73 77 6f 72 64 41 54 48 45 4e 41 2e 4d
;; 49 54 2e 45 44 55 72 61 65 62 75 72 6e 00 00 00
for (8byteblock in s) {
;; loop iteration 0
;; 8byteblock:
;; `password’ (length 8 bytes)
;; 70 61 73 73 77 6f 72 64
;; 01110000 01100001 01110011 01110011 01110111 01101111
;; 01110010 01100100
56bitstring = removeMSBits(8byteblock);
;; 56bitstring:
;; 1110000 1100001 1110011 1110011 1110111 1101111
;; 1110010 1100100
if (odd == 0) reverse(56bitstring); ;; odd=1
odd = ! odd
tempstring = tempstring XOR 56bitstring;
;; tempstring
;; 1110000 1100001 1110011 1110011 1110111 1101111
;; 1110010 1100100
for (8byteblock in s) {
;; loop iteration 1
;; 8byteblock:
;; `ATHENA.M’ (length 8 bytes)
;; 41 54 48 45 4e 41 2e 4d
;; 01000001 01010100 01001000 01000101 01001110 01000001
;; 00101110 01001101
56bitstring = removeMSBits(8byteblock);
;; 56bitstring:
;; 1000001 1010100 1001000 1000101 1001110 1000001
;; 0101110 1001101
if (odd == 0) reverse(56bitstring); ;; odd=0
reverse(56bitstring)
;; 56bitstring after reverse
;; 1011001 0111010 1000001 0111001 1010001 0001001
;; 0010101 1000001
odd = ! odd
tempstring = tempstring XOR 56bitstring;
;; tempstring
;; 0101001 1011011 0110010 1001010 0100110 1100110
;; 1100111 0100101
for (8byteblock in s) {
;; loop iteration 2
;; 8byteblock:
;; `IT.EDUra’ (length 8 bytes)
;; 49 54 2e 45 44 55 72 61
;; 01001001 01010100 00101110 01000101 01000100 01010101
;; 01110010 01100001
56bitstring = removeMSBits(8byteblock);
;; 56bitstring:
;; 1001001 1010100 0101110 1000101 1000100 1010101
;; 1110010 1100001
if (odd == 0) reverse(56bitstring); ;; odd=1
odd = ! odd
tempstring = tempstring XOR 56bitstring;
;; tempstring
;; 1100000 0001111 0011100 0001111 1100010 0110011
;; 0010101 1000100
for (8byteblock in s) {
;; loop iteration 3
;; 8byteblock:
;; `eburn\x00\x00\x00’ (length 8 bytes)
;; 65 62 75 72 6e 00 00 00
;; 01100101 01100010 01110101 01110010 01101110 00000000
;; 00000000 00000000
56bitstring = removeMSBits(8byteblock);
;; 56bitstring:
;; 1100101 1100010 1110101 1110010 1101110 0000000
;; 0000000 0000000
if (odd == 0) reverse(56bitstring); ;; odd=0
reverse(56bitstring)
;; 56bitstring after reverse
;; 0000000 0000000 0000000 0111011 0100111 1010111
;; 0100011 1010011
odd = ! odd
tempstring = tempstring XOR 56bitstring;
;; tempstring
;; 1100000 0001111 0011100 0110100 1000101 1100100
;; 0110110 0010111