Subject: Kerberos 5 anomalies

From: "Aaron D. Jaggard" <[email-masked]>
Date: Wed, 5 Jun 2002 23:15:59 -0400 (EDT)

Dear Colleagues,

	Below are links to a paper (joint work with Fred Butler, Iliano
Cervesato, and Andre Scedrov) which investigates the security of Kerberos
5 and will be presented at this month's IEEE Computer Security Foundations
Workshop.  A summary and some questions follow.  We would appreciate
hearing any comments or suggestions that you might have on this work.

	Best regards,

		Aaron Jaggard

Paper (.ps, .ps.gz, and .pdf versions):
	ftp://ftp.cis.upenn.edu/pub/papers/scedrov/KerbV-public.ps
	ftp://ftp.cis.upenn.edu/pub/papers/scedrov/KerbV-public.ps.gz
	http://www.math.upenn.edu/~adj/Research/KerbV-public.pdf

Summary:

	We formalize Kerberos 5 at two levels of detail and prove
authentication properties of the protocol.  We also note two types of
anomalies which arise (these appear to be undesirable but not full attacks
against keys).  The first uses a modification of the etype field after the
client has lost a long term key; even if she requests an encryption type
corresponding to a different long term key, the intruder can force the
compromised key to be used.  In the second anomaly, the intruder replaces
the ticket being sent to the client with a random message, and then
replaces that message with the ticket in the subsequent request from the
client; the client's request may then be granted on the basis of the
ticket which she has been granted but does not actually posses.

Questions:

	Regarding the etype anomaly: While a lost long-term key would
allow an intruder to masquerade at will as the client C, it may be
possible to ensure that if KAS responds to a request from C using the
nonce sent by C, then it does so using one of the encryption types that C
requested (if these are all uncompromised).  We think that we can do this
by not sending the nonce n in the clear and instead sending a sequence of
ciphertexts, the ith of which is the encryption, using the ith requested
encryption type, of the message ``C,n'' (or something similar).  The
KRB_AS_REQ might also be protected via public key encryption (KAS
publishing a key for use with KRB_AS_REQs), although this may not be
practical.  Do you have any thoughts on this anomaly and guarding against
it?

	We are also interested in analyzing whether a second checksum,
taken over the ticket and enclosed in the authenticator, would guard
against the second anomaly noted above.  Is there any reason why such a
checksum should not be considered?

---

From: Ken Raeburn <[email-masked]>
Date: Thu, 06 Jun 2002 03:32:44 -0400

> hearing any comments or suggestions that you might have on this work.

Thanks for sending the pointers.

I haven't had a chance to look it over closely yet, but I'll try to
read through it in the next few days.  I've got little experience with
this sort of formalized analysis of the protocol, but I'll see how
much I can understand. :-)  I can comment on your email though:

> compromised key to be used.

So by "lost" you mean it's been compromised, and its secrecy is what's
lost?  (As opposed to misplaced so that the client doesn't have it
any more.)

Yes, a man-in-the-middle attack can still cause it to be used, or for
that matter so can a completely fake AS-REQ.  The only right thing to
do when a long-term key has been exposed is to update the database so
it won't be used.  (Set a flag, change a password, update a blacklist,
the mechanism is an implementation detail.)

There are various preauthentication schemes that have been developed
or are in the works that would make this harder for an attacker, but
more standardization work and documentation is needed.  The "timestamp
preauth" scheme requires that the client send, encrypted, the current
time; I'd have to go digging around to see if or how the encryption
type used there relates to the type used by the KDC for the AS
response.

Other proposals, based on SRP and some old DCE ideas, provide
stronger protection by preventing the sending of any data on the wire
protected using only the user's long-term key.

>    In the second anomaly, the intruder replaces

If the replacement is with the same ticket, yes, but does it matter?
In a way, the intruder is cooperating with the client to let the
client access services; the intruder isn't gaining anything, since the
intruder cannot fabricate the correct authenticator without knowledge
of the session key.  In a sense, this cooperation simply makes the
pair into one functioning Kerberos client.

Indeed, I could imagine someone proposing to do just such a thing for
some low-bandwidth embedded application, perhaps with a special etype
value for the ticket that means "the octet string here is a cache
entry handle supplied by the middleware box".  I'd try to talk them
out of it, but I could imagine someone suggesting it. :-)

If the intruder isn't quite so cooperative, though, they can cause
other problems.  The Packet Cable people brought up a similar problem
a while back, wherein the ticket is corrupted by an attacker before
the client receives it, and the client believes it to be valid, and
thus tries to use it.  Whatever server the client talks to refuses to
accept the client's authentication, and the client has no way to
determine that it's not the current exchange that was interfered with,
but the earlier exchange with the KDC.

We've been talking about this in the working group for a year or so,
and are planning on extensions to the protocol to add checksums to new
variants of several of the existing message types.  Unfortunately, we
get bogged down in details like exactly which messages should or
shouldn't have checksums added, *how* they should be added so as to
cause minimal problems for the software vendors, etc, so it's taking
us longer than it should.

> encryption type, of the message ``C,n'' (or something similar).

You mean the client should encrypt the nonce multiple times?
Functionally this sounds a lot like timestamp preauth.

Another approach we've talked about a little, but haven't investigated
in detail, is having the (updated version of the) AS-REP message
include a checksum of the original AS-REQ message.  If the checksum
doesn't match what the client computes, an error is reported.

>    The

We've been talking about public key as a possibility.  For one
version, look for "LEAF" in
ftp://ftp.ietf.org/ietf-mail-archive/krb-wg/2002-03.mail.  For
another, look up the PKINIT draft.  I'd really be interested in how
PKINIT and PKCROSS affect the analyses of the Kerberos protocol....

For some environments, where the KDC may be expected to handle high
loads, reducing the number of expensive PK-type operations required is
a priority, so non-PK solutions are likely to be better received if
they provide sufficient degrees of security.

> checksum should not be considered? 

I think the part we'd want to detect would be the first modification,
of the message the client receives from the KDC.  For that, as I
indicated, we are indeed looking at adding checksums.

If the message sent from the client to some service has its ticket
corrupted (in transit, or because the attacker fed an incorrect ticket
to the client as you describe), the decryption will fail on the server
side.  If the ticket is replaced by another valid ticket, the
contained session key still won't match the original, and the
authentication decryption will fail.

The case where the intruder also "repairs" the damage he's inflicted
on the client's messages doesn't seem interesting to me.  Well,
interesting, maybe, as a curiousity, but not important.  Perhaps from
a theoretical perspective it is, but what's the problem in practical
terms?

Ken

---

From: Martin Rex <[email-masked]>
Date: Thu, 6 Jun 2002 11:32:36 +0200 (MET DST)

> out of it, but I could imagine someone suggesting it. :-)

I may be wrong, but I thought the IAKERB was basically just
doing that, i.e. playing man-in-the-middle without gaining
access to the underlying keys.

-Martin

---

From: Ken Raeburn <[email-masked]>
Date: 06 Jun 2002 15:49:28 -0400

> access to the underlying keys.

If I recall correctly, the IAKERB proxy acts as an intermediary via
GSS to let the client and KDC communicate, but doesn't actually
interfere with the ticket itself.