Key Management

Lecturer: Professor Fred B. Schneider

Lecture notes by Lynette I. Millett

Key Management

Today we discuss key management. 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 between every host and the KDC. The KDC generates a fresh key for any other communicating pair of hosts that request one and distributes it 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.) Short-lived keys make the job of a cryptoanalyst very difficult.

One protocol for key distribution works as diagrammed below. Assume that A and B have keys kA and kB respectively that are shared with the KDC.

Note that once the fresh key kAB 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 kAB, A may send a message to B. However, this message may arrive before B has received kAB. 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 A the key encrypted under kB instead of sending that to B. A will then send this to B before sending any messages to B.

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.

The only 'risky' interval is when the workstation is using the password to derive kA. Because of the TGT, the KDC does not need to remember any state, 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 sends a request to the workstation, which then passes along the request (with the TGT) to the KDC. The KDC will invent a fresh key and also provide A with a ticket to B. This ticket will be used when A actually wants to access B. We first diagram the protocol for acquiring credentials.

Now these credentials can be used to access resource B. The workstation will send TickB to B, along with the current time encoded under the shared key (call this the authenticator). B extracts the shared key from TickB and checks the authenticator (to prevent a replay of an earlier request). B will then send back its own authenticator. From this, A can determine that whoever sent the massage knows kAB, thus was able to decrypt TickB, thus knew kB and thus was B.
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.