173
performing one iteration of the attack with the chosenP
0
to acquireC
0
.
If a particularP
1
in an iteration of the attack needs to
contain one NUL character, the value ofP
1
will be split be-
tween thepname andpinstance fields of the ticket, rather
than being completely contained within thepname field.
This does not pose a problem. However, if two or more
NUL characters
3
need to appear in n P
1
, the target KDC
will probably not create a useful ticket, so the attacker
must change the previously fixed string appearing in n P
0
in
order to obtain a value ofF
1
which does not require more
than one NUL character to appear inP
1
. Similarly, the
attacker may also permuteP
0
such that the complete client
principal name will not need to contain any “suspicious”
characters,e.g., non-alphanumeric characters, though this
practice will increase the number of iterations needed to
complete the attack.
Almost none of this attack is specific to the particular
cipher mode (CBC or PCBC), provided that the mode is
of the general block-feedback form. The scenario of a
compromised realm sharing a key with the target realm is
not farfetched; it is not uncommon for a realm to set up a
shared key with a less-secure realm for testing purposes.
As mentioned earlier, this practice would not constitute
asecurity exposure if it were not for this cryptographic
attack.
The attacker need not control a cross-realm key shared
with the target realm; knowledge of a sufficient number
of keys in the target realm enables the use of the AS
exchange, instead of the TGS exchange, as an oracle.
This is particularly easy if the attacker has privileges to
adaptivelycreate principals in the target realm’s database,
in which case the required number is not large at all.
For example, the MIT implementation provides a facil-
ity for allowing a less-privileged administrator (typically
one responsible for deploying server hosts) to create or
change a key associated with a host-based service. Typi-
cally, site policy limits the principal names to forms such
as “ “ rcmd.hostname@realm ”; the rcmd keys are used for
authenticating remote logins to a host. If the e hostname
portion of these principals is not restricted to the set of
characters typically valid for use as hostnames, this at-
tack may require the creation of as few as n principals
to forge a ticket that isn ciphertext blocks long. Tighter
constraints, e.g., character set restrictions, on the form
of the principal names that the administrator is permitted
to create will cause the required number of principals to
increase. Regardless, this approach is not useful in a ver-
sion 4-only environment, as the interesting client principal
names to impersonate rarely begin with “ “ rcmd”; the at-
tacker must somehow obtain (possibly by packet-sniffing)
3
Actually, if the second NUL character appears at the end of the
first block, it is not a problem.
an initial ciphertext block of a ticket issued to the target
client principal. This limitation can be circumvented by
the cross-protocol attack, which we describe later.
Controlling a cross-realm key is merely one of the
most efficient methods of attack, and it is the only attack
variant that we have implemented so far. Our implemen-
tation of the attack only requires about one oracle query
per forged ciphertext block, needing slightly more queries
when too many NUL characters would have to appear in
the relevant plaintext block.
4
This sort of attack might
go completely unnoticed by all but the most vigilant ad-
ministrators, allowing the attacker to surreptitiously com-
promise the realm. As noted above, but not implemented
by us, the attacker can utilize a larger number of queries
to avoid using principal names containing “suspicious”
characters, making the attack even less detectable.
8. Forging arbitrary tickets
Given the encryption oracle, an attacker may construct
an arbitrary Kerberos version 4 ticket, subject to certain
conditions. The attacker must usually obtain the cipher-
text of the counterfeit ticket one block at a time, since the
feedback block corresponding to a particular ciphertext
block is generally not known in advance. Optimizations
may exist which permit multiple ciphertext blocks to be
produced and spliced together at once, but the length con-
straints inherent in version 4 principal names, as well as
the use of NUL-terminated strings in the tickets, limit
these optimizations somewhat.
To forge a ticket ciphertext
{
X
i
:X
i
=
k
(
M
i
⊕
F
i
)}
that
decrypts to the plaintext
{
M
i
}
,the attackeriterates through
eachM
i
, determining the corresponding F
i
, and submit-
tingM
i
⊕
F
i
to the encryption oracle to receiveX
i
. The
use of the key as the IV in Kerberos version 4 introduces
a slight difficulty in forging the initial ciphertext block,
X
0
;the attacker must cause the TGS to encryptM
0
as the
first block of a ticket. The attacker cannot use the oracle
to directly produceX
0
because the feedback block F
0
is
secret.
This property of X
0
places some constraints on the
set of client principal names that an attacker may forge.
In particular, if the target client principal’sprimaryname
andinstance components total less than 7 bytes, including
terminating NUL characters, the target realm must share
an initial substring with the attacking realm. This initial
substring requirement arises from the TGS’s checking for
amatch between the client realm and the realm issuing
the cross-realm ticket. The length limitation on the target
principal name may be circumvented by copying the first
ciphertext block of a legitimate ticket issued to the target
4
This complication occurs with probability
∼
2
−
11
, assuming that
all possible feedback block contents are equally likely.
119
principal, e.g., by sniffing the network while the target
principal is using the ticket to authenticate to a service.
9. Implementation flaws
The MIT implementations of Kerberos version 4 have
afew design flaws which enable more widespread dam-
age than would be possible if the implementation were
better designed. We emphasize that these additional flaws
are not flaws in the protocol, but rather are flaws in the
implementation. Even the most secure protocol is use-
less if the implementation is insecure, and we encourage
specifiers of cryptographic protocols to identify particular
pitfalls that implementors may encounter.
In the MIT implementation of version 4, a poorly de-
signed lineage check forcross-realm authentication allows
an attacker to compromise realms other than the initial
target realm. Also, the MIT implementation of version 5
uses identical keys for encrypting version 4 and version 5
tickets for the same service principal, enabling a cross-
protocol attack against version 5. These flaws are believed
to exist in non-MIT implementations of the Kerberos pro-
tocols as well.
9.1. Realm hopping
The MIT implementation of the Kerberos version 4
KDC attempts to prevent client principals from transiting
or “hopping” between realms, , i.e., a client principal ac-
cessing a service in a foreign realm must have its local
realm directly share a key with the foreign realm. The
KDC implementation does not enforce this policy by pre-
venting the issuance of a cross-realm ticket to a foreign
principal; it instead relies on the receiving KDC to deny
further tickets based on that cross-realm ticket. For ex-
ample, if a client principal clienta@A obtains a ticket
for krbtgt.B@A, it may subsequently obtain a ticket for
krbtgt.C@B. The KDC for the C realm is responsible
for denying the client principal clienta@A further tick-
ets in the C realm. For similar reasons, it is also possible
for that client to obtain a ticket for krbtgt.B@B. While
the client from A may obtain the ticket krbtgt.B@B,
it will normally be unable to obtain further tickets in B
using that ticket.
Unfortunately, these restrictions are not sufficient to
prevent an attacker from using the chosen-plaintext attack
to attack the TGS principal in B, or, for that matter, any
cross-realm TGS principals in B. This flaw permits an at-
tacker to recursively compromise an entire authentication
network comprising numerous realms, even though tran-
siting through multiple realms is normally not permitted
in Kerberos version 4. Hopping through realms is expen-
sive:O
(
c
n
)
tickets must be forged to compromise a realm
nhopsaway.
9.2. Cross-protocol attack
The reuse of a key for multiple cryptographic purposes
can also lead to a vulnerability. The MIT implementation
of version 5 has a backwards compatibility mode that al-
lows the KDC to issue version 4 tickets. A single database
is used for handling both version 4 and version 5 requests,
and the KDC uses the same key to encrypt both version 4
and version 5 tickets for a given service principal. An
attacker can use the version 4 encryption oracle to attack
the version 5 protocol. This enables a wider attack than
would be possible against version 4 alone.
Tickets in Kerberos version 5 also consist of a string of
encrypted data, although, unlike version 4, the version 5
encryption scheme performs some encoding on the data
prior to encryption. The format of the encoded plaintext
in version 5 immediately prior to encryption is
{
confounder
,
checksum
,
data
,
pad
}.
The confounder is one block of random bytes. The Ker-
beros version 5 specification [23] chooses the block ci-
pher as DES, which is used in CBC mode, and allows
the checksum to be CRC-32, MD4, or MD5. None of
these checksums is keyed. This lack of keying enables
the cross-protocol attack from version 4 to version 5.
For DES with MD4 (des-cbc-md4) and DES with MD5
(des-cbc-md5), the IVofthe encryptionis a block of zeros.
For DES with CRC-32 (des-cbc-crc), the IV is the key.
The checksum is computed over the entire concatenated
plaintext, with the checksum field zeroed out. This frus-
trates ciphertext generation via chosen-plaintext manipula-
tion ifthe attacker has no knowledge ofthe confounder; an
adversary will find it difficult, if not impossible, to create
an encryption oracle by manipulating version 5 tickets.
Fordes-cbc-md4 and des-cbc-md5,an attacker cansim-
ply fabricate any desired confounder using the version 4
encryption oracle, since the IV is known and constant. For
des-cbc-crc, the attack is somewhat more difficult, since
the IV is the key and not known to the attacker. For this
particular attack, it is necessary to obtain the ciphertext
blockC
0
corresponding to the desired confounder, possi-
bly by the same method that can be used for theC
0
attack
on PCBC in version 4, i.e., by forcing the KDC to en-
crypt an initialP
0
with the attacked key (which generally
requires control of a realm sharing a key with the target
realm).
10. The evolution of Kerberos encryption
The original specification of Kerberos version 5, while
it makes significant improvements on version 4, still con-
tains some flaws. In particular, it attempts to provide
authenticated encryption, but remains vulnerable to at-
tacks based on encryption oracles. Work continues on
130
Kerberos encryption schemes; the proposed changes rem-
edy the cryptographic vulnerabilities in both version 4
and RFC 1510, and eliminate the oracle-based attacks we
describe.
10.1. Kerberos version 5
Kerberos version 5 adds checksums to the encoded
plaintext. This provides some protection against simple
attacks, but it is not sufficient to prevent the chosen-
plaintext attacks we describe. Given an encryption oracle,
an attacker can simply fabricate a valid checksum as part
of the desired plaintext. An unforgeable signature,e.g., a
keyed hash whose creation requires knowledge of a secret,
will thwart an attacker equipped with an encryption ora-
cle, assuming that the attacker does not have a signature
oracle.
Version 5 alone would prevent an encryption oracle
by its use of random confounders. An attacker cannot
predict the ciphertext corresponding to a chosen plaintext
block, and is therefore unable to create an oracle. The
MIT implementation’s sharing of version 4 and version 5
keys enables the cross-protocol attack against version 5,
by allowing an attacker to use the encryption oracle of
version 4 to forge ciphertexts for version 5.
The confounder in version 5 also prevents a cut-and-
paste attack against the TGS exchange. The version 5
TGS exchange permits a client to submit arbitrary plain-
text for the KDC to encrypt in a ticket, in the form of
the AuthorizationData field. If it were not for the con-
founder, an attacker could submit the plaintext of a de-
sired forged ticket as AuthorizationData in a legitimate
TGS request and obtain the desired ticket’s ciphertext as
asubstring of the actual ticket returned by the TGS [11].
Others [9, 38] have previously noted the weaknesses of
encrypted checksums against cut-and-paste attacks. The
presence of a checksummed confounder in the ticket pre-
vents an attacker from predicting the feedback block for
the initial ciphertext block of the forged ticket. If the con-
founder were not checksummed with the plaintext, the at-
tack would still be possible, as the receiving service would
discard the confounder without verifying its integrity.
10.2. Upcoming revisions to Kerberos
The upcoming revision [34] to the Kerberos ver-
sion 5 protocol specification repairs many of the flaws
in RFC 1510. This revision moves the encryption speci-
fication [36] to a distinct document, which increases the
separation between encryption and protocol recommended
byBellovin and Merritt [12]. Ciphers stronger than single-
DES, e.g., triple-DES or the Advanced Encryption Stan-
dard (AES) [32, 35], may now be used. The revised en-
cryption specification recommends that a ciphertext output
format of
{
encrypt
(
k
e
,
plaintext
),
HMAC
(
k
c
,
plaintext
)},
whereencryptis the encryption function,e.g., triple-DES
in CBC mode, or AES in CTS mode;HMAC is a keyed
hash [26]; andplaintextis
{
confounder
,
data
,
pad
}.
k
e
is a key used only for performing encryption, andk
c
is a key only used for creating keyed hashes. Both keys
are derived from the underlying key exchanged in the
protocol.
The use of HMAC prevents an attacker from construct-
ing a valid ciphertext without access to the signature key
k
c
, thus precluding many chosen-plaintext attacks. This
feature of HMAC improves upon the weak scheme used
in the original version 5 protocol, where an attacker could
easily construct a valid ciphertext using an encryption ora-
cle. The updated protocol derives the keysk
e
andk
c
from
the actual shared key via a one-waykeyderivation func-
tion. The new encryption specification also recommends
using key derivation to produce separate keys for each
possible use of a shared key, thus restricting the actual
quantity and type of plaintext encrypted with each key.
This practice makes chosen-plaintext attacks even more
difficult.
Bellare and Namprempre [7], as well as Krawczyk [25],
analyze the composition of encryption and authentication
primitives. Krawczyk determines that the “Encrypt-and-
Authenticate” scheme (called “Encrypt-and-MAC plain-
text”by Bellare and Namprempre) is insecure in the gen-
eral case. The independent encryption and HMAC of the
revised Kerberos version 5 encryption scheme appears to
fall into this category, but could be better identified as an
“Encode-then-E&M”scheme, into which Bellare e etal.[6]
classify the SSH encryption scheme.
Bellare et al. [6] recall that the SSH protocol’s pre-
dictable chained IVs make it insecure against a chosen-
plaintext attack. One of their proposed fixes adds random
padding as part of an encoding step prior to encrypting
and MACing the plaintext, and uses randomized IVs for
each separate ciphertext packet. Kerberos version 5 uses
a similar strategy, though Kerberos doesn’t specify the
use of a keyed hash until the recent revision of the en-
cryption specification. Bellovin and Merritt [12] note that
version 5’s random confounder is equivalent to a random
IV, though they criticize the use of the former.
The work of Bellare e et al. on the SSH encryption
scheme shows that the unmodified “Encode-then-E&M”
scheme is not sufficient if it has predictable IVs. While
Kerberos version 4 effectively has predictable (and con-
stant!) IVs, version 5’s use of random confounders pre-
vents an attacker frompredictingthe relationships between
107
plaintext and ciphertext. The revisions to the version 5 en-
cryption scheme [36] add a MAC, which further prevents
various attacks.
11. Conclusions
The lack of authenticated encryption in Kerberos ver-
sion4 leads to a very serious attack. This deficiency is one
of several errors in version 4. Though the existing ver-
sion 5 specification (RFC 1510) is an improvement over
version 4, it too has vulnerabilities. Ongoing revisions to
version 5 remedy the existing flaws in RFC 1510.
Protocol designers should clearly identify the role of
encryption in their protocols. If the protocol requires non-
malleable encryption, clearly state so in the specification,
and ensure that the encryption scheme actually achieves
this requirement. The use of unauthenticated encryption
in version 4 violates the implicit requirement of nonmal-
leability, with dramatic results.
Designers should abstract the use of encryption away
from the layout of the protocol messages. The design-
ers of version 4 erroneously assumed that the message
layout itself would enhance the security properties of the
encryption scheme. Such cross-dependencies complicate
analysis of the protocol, leading to security vulnerabilities.
CBC and related cipher modes have weaknesses when
used with deterministic IVs. In particular, if a fixed plain-
text encrypts to a fixed ciphertext, an attacker can build
an encryption oracle. Even if a protocol does not allow an
encryption oracle, message authentication schemes should
be robust against encryption oracles. As we have shown,
encrypted plaintext checksums are insufficient protection.
Using a single key for multiple purposes allows weak-
nesses in one system to compromise another, as illustrated
by the cross-protocol attack. The revisions to version 5
specify using key derivation to produce different keys for
different cryptographic purposes.
Protocols have a longer life than their designers might
anticipate. Despite its age, and weaknesses related to its
age, e.g., its use of single-DES, Kerberos version 4 re-
mains in widespread use. Even published criticisms about
the security of version 4 have not significantly diminished
its use. It has taken the revelation of a cryptographic
flaw of this magnitude to encourage users to finally begin
moving away from the protocol.
Acknowledgments
We thank Steve Bellovin, Mark Eichin, Radia Perl-
man, Amy Yu, and the anonymous referees for reading
and providing useful commentary on earlier versions of
this paper. We also thank Steve Bellovin, Matt Blaze,
Love H¨ornquist-
˚
Astrand, Jeff Hutzelman, Perry Metzger,
Jeff Schiller, and Ted Ts’o for useful discussions and ad-
vice. Steve Dorner brought to our attention a ciphertext-
corrupting application bug that inspired us to discover the
attack. We thank Marshall Vale and the rest of the MIT
Kerberos Development Team for their ongoing support.
References
[1] M. Abadi and R. Needham. Prudent engineering practice
for cryptographic protocols. . IEEETransactions on
Software Engineering,22(1):6–15,January1996.
[2] G. Bella and L. C. Paulson. Kerberos version IV:
Inductive analysis of the secrecy goals. InProceedings
of the 5th European Symposium on Research in
Computer Security,pages361–375.LNCS 1485,
Springer-Verlag, 1998.
[3] G. Bella and E. Riccobene. Formal analysis of the
Kerberos authentication system. . JournalofUniversal
Computer Science,3(12):1337–1381,1997.
[4] M. Bellare, A. Desai, E. Jokipii, and P. Rogaway. A
concrete security treatment of symmetric encryption. In
Proceedings of the 38th Symposium on Foundations of
Computer Science,pages394–403.IEEE,1997.
[5] M. Bellare, A. Desai, E. Jokipii, and P. Rogaway. A
concrete security treatment of symmetric encryption.
Available from http://www.cs.ucsd.edu/
users/mihir/papers/sym-enc.html, 2000.
[6] M. Bellare, T. Kohno, and C. Namprempre.
Authenticated encryption in SSH: Provably fixing the
SSH binary packet protocol. InProceedingsof9thACM
Conference on Computer and Communications Security.
ACM, November 2002.
[7] M. Bellare and C. Namprempre. Authenticated
encryption: Relations among notions and analysis of the
generic composition paradigm. InAdvancesin
Cryptology –ASIACRYPT 2000,pages 531–545.
LNCS 1976, Springer-Verlag, 2000.
[8] M. Bellare and C. Namprempre. Authenticated
encryption: Relations among notions and analysis of the
generic composition paradigm. Available from
http://www.cs.ucsd.edu/users/mihir/
papers/oem.html, 2000.
[9] S. M. Bellovin. Problem areas for the IP security
protocols. InProceedingsoftheSixthUSENIXUNIX
Security Symposium.USENIX,July1996.
[10] S. M. Bellovin. Cryptography and the internet. In
Advances in Cryptology –CRYPTO ’98 8 ,pages46–55.
LNCS 1462, Springer-Verlag, 1998.
[11] S. M. Bellovin and D. Atkins. Private communications,
1999.
[12] S. M. Bellovin and M. Merritt. Limitations of the
Kerberos authentication system. InUSENIXConference
Proceedings,pages253–267,Dallas,TX,Winter1991.
USENIX.
[13] J. Black and H. Urtubia. Side-channel attacks on
symmetric encryption schemes: The case for
authenticated encryption. InProceedingsofthe11th
USENIX Security Symposium.USENIX,August2002.
85
[14] M. Burrows, M. Abadi, and R. Needham. A logic of
authentication.ProceedingsoftheRoyalSocietyof
London, Series A, Mathematical and Physical Sciences,
426(1871):233–271, 1989.
[15] cr_ciph.c. Source code of Kerberos version 4 library,
MIT, 1986.
[16] cr_tkt.c. Source code of Kerberos version 4 library,
MIT, 1985.
[17] R. DeMillo and M. Merritt. Protocols for data security.
Computer,16(2):39–50,February1983.
[18] D. E. Denning and G. M. Sacco. Timestamps in key
distribution protocols.CommunicationsoftheACM,
24(8):533–536, August 1981.
[19] D. Dolev, C. Dwork, and M. Naor. Nonmalleable
cryptography.SIAMJournalonComputing,
30(2):391–437, 2000.
[20] N. Ferguson and B. Schneier. . PracticalCryptography.
Wiley, 2003.
[21] A. M. Iley. Kerberos ivec attack. Web page, now
defunct.
[22] A. Joux, G. Martinet, and F. Valette. Blockwise-adaptive
attackers. InAdvancesinCryptology–CRYPTO2002 ,
pages 17–30. LNCS 2442, Springer-Verlag, 2002.
[23] J. Kohl and C. Neuman. The Kerberos network
authentication service (v5). Internet Request for
Comments 1510, Internet Engineering Task Force, 1993.
[24] Messages exchanged on the
krb-protocol@athena.mit.edu email list, April
1989.
[25] H. Krawczyk. The order of encryption and authentication
for protecting communications (or: How secure is SSL?).
InAdvancesinCryptology–CRYPTO2001 , pages
310–331. LNCS 2139, Springer-Verlag, 2001.
[26] H. Krawczyk, M. Bellare, and R. Canetti. HMAC:
Keyed-hashing for message authentication. Internet
Request for Comments 2104, Internet Engineering Task
Force, 1997.
[27] G. Lowe. Some new attacks upon security protocols. In
Proceedings of the 9th Computer Security Foundations
Workshop.IEEE,1996.
[28] S. P. Miller, B. C. Neuman, J. I. Schiller, and J. H.
Saltzer. Kerberos authentication and authorization
system. Project Athena technical plan, section E.2.1,
Massachusetts Institute of Technology, 1987.
[29] J. H. Moore. Protocol failures in cryptosystems.
Proceedings of the IEEE,76(5):594–602,May1988.
[30] National Institute of Standards and Technology. DES
modes of operation. FIPS publication 81, U.S.
Department of Commerce, December 1980.
[31] National Institute of Standards and Technology. Data
encryption standard. FIPS publication 46-3, U.S.
Department of Commerce, October 1999.
[32] National Institute of Standards and Technology.
Advanced encryption standard. FIPS publication 197,
U.S. Department of Commerce, November 2001.
[33] R. M. Needham and M. D. Schroeder. Using encryption
for authentication in large networks of computers.
Communications of the ACM,21(12):993–999,December
1978.
[34] C. Neuman, T. Yu, S. Hartman, and K. Raeburn. The
Kerberos network authentication service (v5). Internet
Draft draft-ietf-krb-wg-kerberos-
clarifications-04.txt, 2003.
[35] K. Raeburn. AES encryption for Kerberos 5. Internet
Draft
draft-raeburn-krb-rijndael-krb-05.txt,
2003.
[36] K. Raeburn. Encryption and checksum specifications for
Kerberos 5. Internet Draft
draft-ietf-krb-wg-crypto-06.txt, 2003.
[37] J. G. Steiner, C. Neuman, and J. I. Schiller. Kerberos:
An authentication service for open network systems. In
Proceedings of the USENIX Winter Conference,pages
191–202, February 1988.
[38] S. G. Stubblebine and V. D. Gligor. On message integrity
in cryptographic protocols. InProceedingsofthe1992
IEEE Computer Society Symposium on Research in
Security and Privacy,pages85–104.IEEE,May1992.
[39] S. Vaudenay. Security flaws induced by CBC padding –
Applications to SSL, IPSEC, WTLS .... InAdvancesin
Cryptology –EUROCRYPT 2002 2 ,pages534–545.
LNCS 2332, Springer-Verlag, 2002.
[40] V. L. Voydock and S. T. Kent. Security mechanisms in
high-level network protocols. . ComputingSurveys,
15(2):135–171, June 1983.
Documents you may be interested
Documents you may be interested
