Kerberos

Lecturer: Professor Fred B. Schneider

Lecture notes by Lynette I. Millett

Key Management

Today we discuss key management and Kerberos . Given a computer network with n hosts, for each host to be able to communicate with any other host would seem to require as many as n*(n-1) keys. There are millions of host on the Internet today. An O(n2) approach does not scale very well. Of course, in practice, not every host will need to talk to every other host. The usual solution is to create keys only when necessary. In that case, though, the issue is how to deliver the key once it has been created. The solution is to employ a trusted host that we will refer to as the key distribution center (KDC).

Employing a KDC requires O(n) keys: a shared key K_A between every host A and the KDC. The KDC generates a fresh, shared key for any communicating pair of hosts that request one; the KDC distributes this fresh, shared key to those hosts. The disadvantages of a KDC-based system include: the need for a protocol, the need to trust the KDC, and the fact that KDC itself becomes a performance bottleneck. On other other hand, with a KDC it is now possible to have short-lived keys (e.g. a different key each day.) Such short-lived keys are called session keys and make the job of a cryptoanalyst very difficult.

One simple (and flawed) protocol for key distribution works as diagrammed below. Assume that A and B have keys K_A and K_B respectively that are shared with the KDC. 

A --> KDC:  A,B
KDC:        invent fresh key K_AB
KDC --> A:   { K_AB, B}K_A
KDC --> B:   { K_AB, A}K_B
Note that once the fresh key K_AB is created, the KDC cannot send it in the clear; it must be encrypted. Moreover, A (respectively B) needs to be convinced that the key it receives is for communication with B (respectively A). This is done by encrypting both the key and the name of the host that the receiver can use this key to communicate with.

The above protocol is flawed in several ways. For example, after receiving the key K_AB, A may send a message to B. However, this message could arrive at B before B has received K_AB. B would then need to buffer the message while expecting to eventually receive the appropriate key. This buffering provides an opportunity for denial of service attacks. A solution is to make sure that A can't send an encrypted message to B until B has the shared key. To do this, the KDC will send to A key K_AB encrypted under K_B instead of sending that to B. A will then send this to B before sending any messages to B. 

A --> KDC:  A,B
KDC:        invent fresh key K_AB
KDC --> A:   { K_AB, B, { K_AB, A}K_B }K_A
A --> B:   { K_AB, A}K_B
We are now well on our way to the famed Needham Schroeder protocol that we have seen before.

Kerberos

Kerberos is a key distribution facility designed at MIT to manage networks of workstations and servers. The environment it was developed for included very good hackers. Moreover, there is a tendency for people to leave a workstation 'alone' while they were still logged in. Kerberos is well-suited, therefore, to open facilities with shared workstations and clever (and careless) people. There are two versions, V4 and V5. V4 is for TCP/IP only, while V5 can also handle other protocols. There are other differences as well.

The Kerberos system consists of a KDC that runs on a physically secure node in the network as well as a software library that is linked into workstation operating systems and applications. A user logs into a workstation and provides a username and password. The workstation uses the username and password to obtain information (credentials) that are used by processes to access remote resources on behalf of the user. The unit of certification is a session. A session is the period of time from logon to logoff at a given workstation.

Each principal (user, server, printer, etc) shares a key (called its "master key") with the KDC. A workstation uses a session key instead of a master key or password. Because of this, workstations erase the master key as soon as possible (it's needed only long enough to acquire a session key), and thus programs on the workstation cannot steal the master key as easily. This is not absolutely secure, but works well for the kind of environment Kerberos was designed for.

The KDC maintains a database whose entries are pairs: a principal name, p, and an encrypted version (under a key only the KDS knows) of p's master key.

We present three Kerberos protocols: logging on to the network, acquiring credentials for a resource, and using credentials to access a resource.

Logging on to the network involves the creation of a ticket-granting ticket (TGT) by the KDC. The TGT will take the place of the master key and has an expiration time. The principal A then uses the TGT when contacting the KDC for credentials. Below, A is a person, WkStation_A is a computer owned by A, K_A is the master key for A, and KDC is a server. 

A --> WkStation_A:  A wishes to login.

WkStation_A --> KDC:  A needs TGT

KDC:   invent fresh session key S_A
       lookup K_A in local database
       TGT := {A , S_A , expTime}K_KDC

KDC --> WkStation_A:  { S_A , TGT }K_A

WkStation_A --> A:  Password?

A --> WkStation_A:   Password is: xxxxxx

WkStation_A:  Derive K_A from Password  xxxxxx
              Extract S and TGT from "{ S_A , TGT }K_A" received earlier
              Forget K_A at WkStation_A

Note, in the above protocol, the only period of significant vulnerability occurs while the workstation is storing K_A (after asking for the password). Note also that because WkStation_A has received and will store TGT, the KDC does not need to remember any state (and, in particular, S_A)---all relevant state is encoded in the TGT. (If the KDC had to remember state, then it would need storage and a garbage collection routine. Moreover, supporting multiple KDCs would introduce a consistency problem.)

Suppose that A would like to get credentials for a resource B. To do this, A types the request into the workstation, which sends a the request (with the TGT) to the KDC. The KDC will invent a fresh key and also provide A with a ticket (Tick_B) to B. This ticket will be used when A actually wants to access B. We first diagram the protocol for acquiring credentials. 

A --> WkStation_A:  A wishes to access service B.

WkStation_A --> KDC:  A, B, TGT

KDC:  invent fresh key K_AB
      extract S_A from TGT found in message from WkStation_A
      Tick_B := {A, B, K_AB, expTime}K_B

KDC --> WkStation_A:  {B, K_AB, Tick_B}S_A
Now these credentials can be used by A to access resource B. In particular, WkStation_A will send Tick_B to service B, along with the current time encoded under the shared key (call this the authenticator). B extracts the shared key K_AB from Tick_B and checks the authenticator (to prevent a replay of an earlier request). B will then send back its own authenticator (derived from the one that WkStation_A sent). From this second authenticator, A can determine that whoever sent the massage knows K_AB, thus was able to decrypt Tick_B, thus knew K_B and thus had to have been B. 
WkStation_A --> B:   Tick_B, {timeNow}K_AB

B:  extract A, B, K_AB, and expTime from Tick_B (since B knows K_B)
    abort unless timeNow < expTime

B --> WkStation_A:  {timeNow+1}K_AB
Note that this does not prevent a 'replay' of a current request. To do this, B should keep all the requests for the last 5 minutes, and check that all the requests from a given source are for different times.

Engineering Issues in Kerberos

There are several engineering issues that arise in Kerberos. It is not feasible to have only one KDC due to issues of scaling and fault-tolerance. Instead, there is one master KDC and n slave copies that contain read-only copies of the data. The master updates the slave KDCs periodically. The data can be transferred from the master to slave KDCs without additional encryption (recall that the master keys are already encrypted under kKDC.) However, to prevent a splicing attack, a cryptographic checksum should be also be encrypted and sent.

Another issue is how to manage the KDC in a very large network (e.g. an international network). It is impossible to find a single organization that all participants will trust. A solution is to partition the network (namespace) into realms and have a separate KDC for each realm. Principal names will be of the form: p@realm. A KDC for one realm can be registered as a principal in a KDC for another realm. In this way a KDC for another realm can be accessed like any other resource. In Kerberos V4 every KDC can be a principal in every other realm. However, authentication across realms is not allowed unless the path not longer than 2. In V5, the entire path is passed as a list, and a KDC can decide whether it trusts everyone on the list.