Kerberos Versus the Leighton- Micali Protocol

The second category of keys is session keys. These are the keys that operate directly on the data to encrypt and authenticate it. In this article, I'll explore the derivation of session keys from long-term keys. Imagine that Alice and Bob share a long-term symmetric key, K_AB. Establishing a session key is straightforward. One of them simply picks a random key and encrypts it with the long-term key and forwards it to the other. Unfortunately, in practice, there may be so many parties wishing to communicate that it is unreasonable to assume that they each share a long-term symmetric key with every other participant. Instead, a central, trusted authority is used to distribute session keys. Each user shares a long-term symmetric key with the trusted authority. The question is: How can Alice and Bob securely establish session keys by using the long-term keys they share with the trusted authority? Here, I'll examine two alternatives. The first is a well-established and widely deployed protocol called "Kerberos." The second is a little-known protocol that offers several advantages over more widely deployed systems.

Kerberos

The Kerberos system (see "Kerberos: An Authentication Service For Open Network Systems," by J.G. Steiner, B.C. Neuman, and J.I. Schiller, Usenix Conference Proceedings, February 1988) was designed for user authentication and the distribution of session keys in an open system with trusted hosts but an untrusted network. The protocol is based on earlier work by Needham and Schroeder (see "Using Encryption For Authentication In Large Networks Of Computers," by R.M. Needham and M.D. Schroeder, Communications of the ACM, December 1978). In Kerberos, principals establish long-term associations with an authentication server. Then, when they wish to establish a secure session with another user or a service, the authentication server generates a random key and assigns it to them. In Kerberos, it is more likely that Bob is a file server than an actual person. The Needham and Schroeder protocol is quite simple; the authentication server generates a random key for the two parties in each session. The interesting aspect of the protocol is the way in which the session keys are revealed to Alice and Bob. Figure 1 illustrates the Needham and Schroeder protocol, which is at the heart of Kerberos. It can be specified as follows:

1. A S : A,B,N_a

2. S A : {N_a,B,K_ab,{K_ab,A}K_bs}K_as

3. A B : {K_ab,A}K_bs

4. B A : {N_b}K_ab

5. A B : {N_b-1}K_ab

In this protocol, Kxy represents the long-term key shared between X and Y. A and B represent Alice and Bob, respectively. In message 1, Alice sends a request to the server, S indicating that she wishes to communicate with Bob. The value N_a is a random number called a "nonce" and is included to link future messages to this request. The nonces in this protocol are not necessary in Kerberos because timestamps are used to prevent replay. This message is sent in the clear because it includes no security-related information.

In message 2, the server S responds with a session key, K_ab. A copy of the key is also encrypted under Bob's long-term key. In addition, N_a is included as a guarantee that this message is not a replay of a previous response. Each party is also told who will be on the other end of the secure channel. This can be seen by the inclusion of A in {K_ab,A}K_bs.

In message 3, Alice forwards {K_ab,A}K_bs to Bob, who can decrypt it and recover K_ab. Bob then issues message 4 as a challenge to Alice to make sure that she possesses K_ab. In reality, Alice should also challenge Bob, but this was accidentally left out of the protocol. In message 5, Alice proves possession of the session key.

The Kerberos adaptation of the Needham and Schroeder protocol is in widespread use. Version IV was the first one to be widely deployed. The latest version is number V. It is part of the Andrew File System, and Kerberos has also been implemented in the Open Software Foundation Distributed Computing Environment (OSF DCE) and Windows NT. For information about the most recent version, instructions for obtaining the code, and many papers about Kerberos, see http://web.mit.edu/kerberos/www/.

Problems with Kerberos

Kerberos has been a great success. It is used in many locations around the world. While Version V corrects many of the problems in Version IV, the older version is still the one in predominant use. As such, it pays to take a look at some of the problems with Kerberos IV. There are also many lessons to be learned from what was done incorrectly. While the tone of this section is negative, it should be remembered that the designers and implementors of Kerberos did a great service to the community, and that their product is probably the most impactful security system in the real world, with the recent exception of SSL.

In 1991, Steve Bellovin and Michael Merritt published "Limitations Of The Kerberos Protocol" (Proceedings of USENIX Winter Conference, 1991). This is an excellent account of what is right and wrong with Kerberos from a security perspective. Many of the changes that were made to Kerberos were direct results of this paper.

Some of the problems in Kerberos IV are due to environmental factors. In Kerberos IV, the keys used by the users for various services are cached locally. However, in diskless environments, the /tmp directory, where the keys are cached, is on a file server, so the keys actually travel across the network. However, the purpose of Kerberos was to design a system that is secure against an adversary who controls the network. Another problem with this is that it means only one user should be on a workstation at a time. While this was a reasonable model for MIT, where Kerberos originated, it does not work in all environments. The reason is that most workstations do not come with local storage and access that can be partitioned among several users.

Another weakness of Kerberos IV is that it is vulnerable to replay attacks. An authenticator, which is a message encrypted by a client to prove knowledge of a key, is valid for about five minutes. In the 1985 unpublished manuscript "A Weakness In The 4.2BSD UNIX TCP/IP Software," Robert Morris showed that this is plenty of time to spoof a TCP connection, if the attacker sets it up in advance. Yet another limitation pointed out by Bellovin and Merritt is that Kerberos relies on clocks that are roughly synchronized, despite the fact that many time services, especially the ones in predominant use, are unauthenticated.

One of the most interesting attacks against Kerberos IV results from the fact that users tend to pick poor passwords (see "Password Security: A Case History," by Robert Morris and Ken Thompson, CACM, November 1979). The third message in the Needham and Schroeder exchange is called a "ticket" in Kerberos. There is a special server called a "Ticket Granting Server" (TGS) that has access to the Kerberos database of long-term keys. It is responsible for issuing tickets for services, such as the file system, to clients. When a client requests a ticket for a service, the ticket is returned from the TGS, encrypted under the long-term password between that client and the TGS. How does the client obtain this key it shares with the TGS? The authentication server sends a ticket for the TGS, in much the same way that tickets are issued for services. There is one exception, however, the client does not have to prove possession of the key. For example, if Bob wishes to obtain a ticket for the TGS, the following conversation takes place between him and the Authentication Server (AS):

1.B AS : B,TGS

2.AS B : {K_B,TGS,TKT_B,TGS,Time}K_B,AS

Bob asks the AS for a ticket to talk to TGS. The ticket, and a session key are returned to Bob, encrypted under K_B,AS, which is the long-term session key between Bob and the AS. This key is derived from Bob's long-term Kerberos password. The problem arises from the fact that the Time, and other information's format that is known in advance is included in the message as well. Now, an attacker, Charlie, can do the following:

1. C AS : B, TGS

2. AS C : {K_B,TGS,TKT_B,TGS,Time}K_B,AS

Charlie pretends to be Bob, and asks the AS for a ticket for TGS. The AS complies, without authenticating Bob, and sends Bob a ticket-granting ticket, encrypted under Bob's long-term key. Charlie can now search for Bob's password offline. The easiest way is to construct a dictionary of all possible passwords that can be generated on a computer. For each password, Charlie uses the string-to-key function of Kerberos to generate a key, and then tries to decrypt message 2. If, after decryption, the location where the Time is supposed to be contains a valid time, Charlie probably found the key.

The reason this attack works is that Kerberos IV is willing to hand a ticket-granting ticket, encrypted under the user's password, to anyone who asks for it. A simple way to prevent this is to require the client to encrypt a random challenge from the server using the long-term key. If the client succeeds, he has proven possession of the key, and the ticket can be sent, encrypted under that key. This is the approach recommended by Bellovin and Merritt and adopted in Kerberos V.

There are other problems with Kerberos as well. The AS must be online most of the time. Anytime users wish to obtain tickets for a service, they must contact the AS. Also, the AS is a central point of attack. All of the user's keys are stored there. While they are stored encrypted under a master key, that master key must always reside in memory, so that user keys can be accessed. Thus, physical security is required for the authentication server.

In addition to these protocol-level attacks, it turns out that all of the existing implementations of Kerberos contain buffer overflow bugs. These can potentially be exploited to circumvent any security offered by the system, and probably introduce additional security threats that did not exist before Kerberos was used.

Another Approach

Buried in the cryptoliterature is a wonderful protocol by Leighton and Micali (see "Secret-key Agreement Without Public-key Cryptography," by Tom Leighton and Silvio Micali, Advances In Cryptology: Proceedings of Crypto '93, 1994) that has several advantages over Kerberos. Perhaps the protocol has not been widely adopted because it is a bit more mathematically complex than Needham and Schroeder's protocol, or perhaps it is due to patent issues. In any case, it is a protocol worth understanding.

There are several advantages to Leighton-Micali. First of all, it does not require that the Trusted Authority (TA) be available at all times. The TA creates a directory that can be made public, and from then on, each party can look up information in the directory and use it to establish a symmetric key with any other party. In addition, the scheme does not require any public-key operations.

The only security assumption made by Leighton-Micali is the existence of one-way functions. In practice, you use pseudorandom functions (see Pseudorandomness and Cryptographic Applications, by Michael Luby, Princeton University Press, 1996) to achieve this. For the purposes of this discussion, consider a pseudorandom function to be a keyed function with certain cryptographic properties. There are two properties that we are interested in:

1. Given the output, it is not feasible to find the input to the function.

2. Without the key, there is no way to compute the function.

It is reasonable to use a MAC function, such as HMAC (see "Keying Hash Functions For Message Authentication," by M. Bellare, R. Canetti, and H. Krawczyk, Crypto '96 Proceedings, 1996) to simulate this function in practice. Basing the entire security of the scheme on the assumptions about HMAC makes it easy to analyze the security of the protocol. It also makes for a clean and easy way to implement system. Leighton-Micali, as you will see, is also very efficient. I refer to the pseudorandom function used here as f and recommend that HMAC be used.

The Scheme

The Leighton-Micali scheme works as follows: The TA generates two master secret keys, K for secrecy, and L for authentication. One advantage of this scheme over Needham and Schroeder is that confidentiality and authentication are explicitly dealt with separately, whereas in Needham and Schroeder, you must employ encryption to attain authentication. The TA computes a key-exchange key to be shared with each participant in the system. These correspond to the K_sx in the Kerberos scheme. Take Alice as an example. The TA computes K_sa by applying the function f to the master key, K, and the string Alice. Using HMAC, you could write this as K_sa= HMAC_K("Alice") and K_sb=HMAC_K("Bob").

In addition to the key exchange key it shares with each user, the TA computes another key called the "individual authentication key." This is simply computed as L_sa=HMAC_L ("Alice") and L_sb= HMAC_L("Bob"). In other words, the long-term keys are computed by applying the pseudorandom function using K and L to the person's name. Only the TA could have generated these values, as K and L are master secrets. Each participant is then given the two keys in a secure manner, out of band.

Now the tricky part. The TA computes some information that will be stored in a public directory. For n participants in the system, the table contains n² values. The directory can be made widely available; it could be stored on a web site, for example. For every two participants, such as Alice (a) and Bob (b), the TA computes P_a,b={K_sb("Alice") f_Ksa("Bob") and A_a,b=f_Lsa (f_Ksb("Alice")).

If storage is not an issue, each party can download and store the values in the table for the participants with whom they expect to communicate. Another option is to download them on demand. The method used to obtain these values is unimportant. After making them available, the TA can disappear and erase the master keys. So, how do Bob and Alice share a common key? Interestingly, the key already exists. It is the output of f_Ksb("Alice"). Similarly, the key shared by Bob and Fred is f_Ksb("Fred"), and the key shared by Alice and Fred is f_Kab("Fred"). In general, the secret key that results from this protocol is f, keyed by the key-exchange key of the first party, applied to the name of the second party. To recover the key between Alice and Bob, Bob can simply apply the function f, using his key-exchange key, to Alice's name. Alice has to do a little more work, but not much. She simply computes f_Ksa("Bob") P_a,b, which is the exclusive OR of her key-exchange key, applied to Bob, with the directory value for her and Bob. The reason this works is that:

f_Ksa("Bob") P_a,b

=f_Ksa("Bob") f_Ksb("Alice") f_Ksa("Bob")

=f_Ksb("Alice")

The two f_Ksa("Bob") cancel out, and the result is the key that Bob computed directly. To be sure that she has the right key, Alice computes f_Lsa(f_Ksb("Alice")) and compares it to A_a,b from the table. The two values should match. If they do, then Alice can be sure that the directory values are legitimate. Any tampering with them would result in an error. The protocol works because nobody can produce P and A values that will match when a session key is tested without possession of the master keys.

As mentioned earlier, in general, it is best to use different keys for each direction. This protocol achieves this very naturally. The key used to receive is always the one that computes directly from the long-term key. For example, when Bob receives from Alice, he uses f_Ksb("Alice"). When Alice receives messages from Bob, she uses the key f_Ksa("Bob"). To compute a sending key, each party must consult the directory. This is nice because the heavier burden is placed on the sender, and the receiver can easily decrypt by performing a simple computation to find the key.

So, what you have is a protocol where Bob and Alice, who share a secret with a TA, can compute a shared symmetric key, with only HMAC and XOR operations. This is pretty efficient, but allows for only one derived key in each direction. This key could be used as a long-term key directly between Alice and Bob, who could use it to encrypt a randomly chosen session key to be used for actual data encryption and authentication.

Leighton-Micali is elegant, efficient, and secure. It is a little complicated, but after staring at it for a while, you should become convinced that it works.

DDJ