Basic Concepts for the Kerberos Protocol

The Kerberos protocol relies heavily on an authentication technique that makes use of shared secrets. The basic concept is quite simple: If a secret is known by only two people, either person can verify the identity of the other by confirming that the other person knows the secret.

For example, let's suppose that Alice often sends messages to Bob and that Bob needs to be sure that a message from Alice really has come from Alice before he acts on its information. They decide to solve their problem by selecting a password, and they agree not to share this secret with anyone else. If Alice's messages can somehow demonstrate that the sender knows the password, Bob knows that the sender is Alice.

The only question for Alice and Bob to resolve is how Alice can show that she knows the password. She might simply include it somewhere in her messages, perhaps in a signature block at the end — Alice, Our$ecret . This would be simple and efficient and might even work if Alice and Bob can be sure that no one else is reading their mail. Unfortunately, that is not the case. Their messages pass over a network used by people like Carol, who has a network analyzer and a hobby of scanning traffic in hope that one day she might spot a password. So it is out of the question for Alice to prove that she knows the secret simply by saying it. To keep the password secret, she must show that she knows it without revealing it.

The Kerberos protocol solves this problem with secret key cryptography . Rather than sharing a password, communication partners share a cryptographic key. They use knowledge of this key to verify one another's identity. For this method of authentication to work, the shared key must be symmetric — a single key must be capable of both encryption and decryption. One party proves knowledge of the key by encrypting a piece of information, the other by decrypting it.

Authenticators

A simple protocol that uses secret key authentication begins when someone is outside a communications door and wants to go in. To gain entry, this person presents an authenticator in the form of a piece of information encrypted in the secret key. The information in the authenticator must be different each time the protocol is executed, otherwise an old authenticator could be reused by anyone who happens to overhear the communication. Upon receiving an authenticator, the person guarding the door decrypts it and knows from what is inside it whether the decryption was successful. If it was successful, the doorkeeper knows that the person presenting the authenticator has the correct key. Only two people have the key; the doorkeeper is one of them, so the person who presented the authenticator must be the other one.

If the person outside the door wants mutual authentication, the same protocol can be executed in reverse, with a slight difference. The doorkeeper can extract part of the information from the original authenticator, encrypt it in a new authenticator, and then give the new authenticator to the person waiting outside the door. The person outside the door can then decrypt the doorkeeper's authenticator and compare the result with the original. If there is a match, the person outside the door knows that the doorkeeper was able to decrypt the original, so he must have the correct key.

It might help to walk through an example. Suppose Alice and Bob decide that before transferring any information between their computers, each will use knowledge of a shared secret key to verify the identity of the party at the other end of the connection. In situations where Alice is the wary guest and Bob is the suspicious host, they agree to follow this protocol:

1. Alice sends Bob a message containing her name in plaintext and an authenticator encrypted in the secret key she shares with Bob. In this protocol, the authenticator is a data structure with two fields. One field contains information about Alice. For simplicity, let's say this is her name. The second field contains the current time on Alice's workstation.

2. Bob receives the message, sees that it is from someone claiming to be Alice, and uses the key he shares with Alice to decrypt the authenticator. He extracts the field that contains the time on Alice's workstation and evaluates the time.
   Bob's task is easier if his clock is reasonably synchronized with Alice's clock, so let's suppose both Alice and Bob use a network time service to keep their clock times fairly close. Let's say the time skew is never more than five minutes. This way, Bob can compare the time from the authenticator with the current time on his clock. If the difference is greater than five minutes, he can automatically reject the authenticator.
   If the time is within the allowable skew, it's probable that the authenticator came from Alice, but Bob still does not have proof that it actually came from her. Another person might have been watching network traffic and might now be replaying an earlier attempt by Alice to establish a connection with Bob. However, if Bob has recorded the times of the authenticators that were received from Alice during the past five minutes, he can defeat attempts to replay earlier messages by rejecting any message with a time that is the same as or earlier than the time of the last authenticator. If this authenticator yields a time later than the time of the last authenticator from Alice, then this message must be from Alice.

3. Bob uses the key he shares with Alice to encrypt the time shown on Alice's message and sends the result back to her.
   Note that Bob does not send back all of the information taken from Alice's authenticator, just the time. If he sent back everything, Alice would have no way of knowing whether someone posing as Bob had simply copied the authenticator from her original message and sent it back to her unchanged. He sends just a piece of the information in order to demonstrate that he was able to decrypt the authenticator and manipulate the information inside. He chooses the time because that is the one piece of information that is sure to be unique in Alice's message to him.

4. Alice receives Bob's reply, decrypts it, and compares the result with the time in her original authenticator. If the times match, she can be confident that her authenticator reached someone who knows the secret key needed to decrypt it and extract the time. She shares that key only with Bob, so it must be Bob who received her message and replied.

This process is illustrated in Figure 11.1.

Figure 11.1 A Simple Protocol for Mutual Authentication

Key Distribution

One problem with the simple protocol described in the preceding section is that it does not explain how or where Alice and Bob get a secret key to use in their communications with each other. If they are people, Alice and Bob can meet, perhaps in an alley, and agree on a secret key. But if Alice is a client program that is running on a workstation and Bob is a service that is running on a computer somewhere across the network, that method does not work. There is the further problem that the client, Alice, might want to talk to many services and will need keys for each of them. Likewise, the service, Bob, might talk to many clients and will need keys for each of them. If each client needs a key for every service and each service needs a key for every client, key distribution can quickly become a difficult problem to solve. The need to store and protect so many keys on so many computers presents an enormous security risk.

The name Kerberos suggests how the protocol resolves the problem of key distribution. Kerberos (also known as Cerberus) was a figure in classical Greek mythology, a three-headed dog who kept living intruders from entering the underworld. Like the mythical guard dog, the protocol has three heads, which in this case are a client, a server, and a trusted third party that mediates between the client and server. The trusted intermediary in the protocol is known as the Key Distribution Center (KDC).

The KDC is a service that runs on a physically secure server. It maintains a database with account information for all security principals in its realm — the protocol's equivalent of a Windows 2000 domain. Along with other information about each security principal, the KDC stores a cryptographic key known only to the security principal and the KDC. This key is used in exchanges between the security principal and the KDC and is known as a long-term key . In most implementations of the protocol, the long-term key is derived from a user's logon password.

When a client wants to talk to a server, the client sends a request to the KDC, and the KDC distributes a unique session key for the two parties to use when they authenticate each other, as illustrated in Figure 11.2. The server's copy of the session key is encrypted in the server's long-term key. The client's copy of the session key is encrypted in the client's long-term key.

Figure 11.2 Key Distribution (in Theory)

In theory, the KDC can fulfill its role as a trusted intermediary by sending the session key directly to each of the security principals involved, as illustrated in Figure 11.2. But, in practice, that procedure would be extremely difficult to implement. For one thing, it would mean that the server would have to retain its copy of the session key in memory while it waited for the client to call. Moreover, the server would need to remember a key not just for this client but for every client who might ask for service. Key management would consume considerable resources on the server and would thus limit its scalability. In addition, given the vagaries of network traffic, a client's request for service might reach the server before the KDC's message arrived there with the session key. The server would have to suspend its reply to the client while it waited to hear from the KDC. This would require the server to save state, imposing still another burden on the server's resources. What actually happens in the Kerberos protocol is considerably more efficient.

Session Tickets

The KDC responds to the client's request to talk to a server by sending both copies of the session key to the client, as shown in Figure 11.3. The client's copy of the session key is encrypted with the key that the KDC shares with the client. The server's copy of the session key is embedded, along with authorization data for the client, in a data structure called a session ticket . The entire structure is then encrypted with the key that the KDC shares with the server. The session ticket — with the server's copy of the session key safely inside — becomes the client's responsibility to manage until it contacts the server.

Figure 11.3 Key Distribution (in Practice)

Note that the KDC is simply providing a ticket-granting service. It does not keep track of its messages to make sure they reach the intended address. No harm is done if the KDC's messages fall into the wrong hands. Only someone who knows the client's secret key can decrypt the client's copy of the session key. Only someone who knows the server's secret key can read what is inside the ticket.

When the client receives the KDC's reply, it extracts the ticket and the client's copy of the session key, putting both aside in a secure cache, which is located in volatile memory, not on disk. When the client wants admission to the server, it sends the server a message that consists of the session ticket, which is still encrypted with the server's secret key, and an authenticator, which is encrypted with the session key, as illustrated in Figure 11.4. The session ticket and authenticator together are the client's credentials to the server.

Figure 11.4 Mutual Authentication (Client/Server)

When the server receives credentials from a client, it decrypts the session ticket with its secret key, extracts the session key, and uses the session key to decrypt the client's authenticator. If everything checks out, the server knows that the client's credentials were issued by a trusted authority, the KDC. If the client has asked for mutual authentication, the server responds by using the session key to encrypt the timestamp from the client's authenticator. The server then returns the encrypted timestamp to the client, just as Bob returned the encrypted timestamp to Alice in the communication illustrated in Figure 11.1.

One benefit of using session tickets is that the server does not have to store the session key that it uses with this client. It is the client's responsibility to hold a session ticket for the server in its credentials cache and present the ticket each time it wants access to the server. Whenever the server receives a session ticket from a client, it can use its secret key to decrypt the ticket and extract the session key. When the server no longer needs the session key, it can discard it.

Another benefit of using session tickets is that the client does not have to go back to the KDC each time it wants access to a particular server. Session tickets can be reused. As a precaution against the possibility that someone might steal a copy of a ticket, session tickets have an expiration time that is specified by the KDC in the ticket's data structure. How long a session ticket is valid depends on the Kerberos policy for the domain. Tickets usually are good for no longer than eight hours, about the length of a normal logon session. When the user logs off, the credentials cache is flushed and all session tickets — as well as all session keys — are destroyed.

Ticket-Granting Tickets

A user's long-term key is derived from a password. When Alice logs on, for example, the Kerberos client on her workstation accepts her password and then converts it to a cryptographic key by passing the text of the password through a one-way hashing function.

The KDC gets its copy of Alice's long-term key from her record in its account database. When it receives a request from the Kerberos client on Alice's workstation, the KDC searches its database for Alice, pulls up her account record, and takes her long-term key from a field in the record.

This process of computing one copy of the key from a password and fetching another copy of the key from a database actually takes place only once, when a user initially logs on to the network. Immediately after accepting the user's password and deriving the user's long-term key, the Kerberos client on the user's workstation asks the KDC for a session ticket and session key that it can use in subsequent transactions with the KDC during this logon session.

The KDC responds to the client's request by returning a session ticket for itself. This special session ticket is called a ticket-granting ticket (TGT) . Like an ordinary session ticket, a TGT contains a copy of the session key that the service (in this case the KDC) uses in communicating with the client. The message that returns the TGT to the client also includes a copy of the session key that the client can use in communicating with the KDC. The TGT is encrypted in the KDC's long-term key. The client's copy of the session key is encrypted in the user's long-term key.

When the client receives the KDC's reply to its initial request, it uses its cached copy of the user's long-term key to decrypt its copy of the session key. It can then discard the long-term key derived from the user's password, for it is no longer needed. In all subsequent exchanges with the KDC, the client uses the session key. Like any other session key, this key is temporary, valid only until the TGT expires or the user logs off. For that reason, it is called a logon session key .

From the client's point of view, a TGT is just another ticket. Before it attempts to connect to a service, the client first checks its credentials cache for a session ticket to that service. If it does not have one, it checks the cache again for a TGT. If it finds a TGT, the client fetches the corresponding logon session key from the cache, uses this key to prepare an authenticator, and sends both the authenticator and the TGT to the KDC, along with a request for a session ticket for the service. In other words, gaining admission to the KDC is no different from gaining admission to any other service in the domain — it requires a session key, an authenticator, and a ticket (in this case, a TGT).

From the KDC's point of view, TGTs allow it to shave a few nanoseconds off the turnaround time for ticket requests. The KDC looks up the user's long-term key only once, when it grants an initial TGT. For all other exchanges with this client, the KDC can decrypt the TGT with its own long-term key, extract the logon session key, and use that to validate the client's authenticator.

Authentication Across Domain Boundaries

The functions of the KDC are divided into two distinct services: an authentication service, whose job is to issue TGTs, and a ticket-granting service, whose job is to issue session tickets. This division of labor allows the Kerberos protocol to operate across domain boundaries. A client can get a TGT from the authentication service of one domain and use it to get session tickets from the ticket-granting service of another domain.

The easiest way to grasp how cross-domain authentication works is to consider the simplest case — a network that has only two domains. For our example, let's say one domain is East and the other domain is West. If the administrators for these domains are members of the same organization (or if for some other reason they are willing to treat each other's domain users as their own), they can enable authentication across domain boundaries by sharing interdomain keys. (In Windows 2000 this happens automatically when two domains establish a trust relationship.) After this is accomplished, the ticket-granting service in each domain is registered as a security principal with the other domain's KDC. This means the ticket-granting service in each domain can treat the ticket-granting service in the other domain as just another service, something for which properly authenticated clients can request and receive session tickets.

When a user with an account in East wants access to a server with an account in West, the Kerberos client on the user's workstation sends a request for a session ticket to the ticket-granting service in the user's account domain, East. The ticket-granting service in East sees that the desired server is not a security principal in its own domain, so it replies by sending the client a referral ticket . This is simply a TGT that is encrypted with the interdomain key shared by the KDC in East and the KDC in West. The client uses the referral ticket to prepare a second request for a session ticket, and this time sends the request to the ticket-granting service in the server's account domain, West. The ticket-granting service in West uses its copy of the interdomain key to decrypt the referral ticket. If decryption is successful, it sends the client a session ticket to the desired server in its domain.

The referral process is more complicated on networks with more than two domains. In theory, the KDC in each domain could establish a direct link to the KDC in every other domain on the network, in each case sharing a different inter-domain key. In practice, the number and complexity of these relationships can easily become unmanageable, especially on a large network. The Kerberos protocol solves the problem by making direct links unnecessary. A client in one domain can get a ticket to a server in another domain by traveling a referral path through one or more intermediate domains.

For example, consider a network with three domains, East, West, and CorpHQ. The KDC in East does not share an inter-domain key with the KDC in West, but both East and West do share inter-domain keys with CorpHQ. In this case, when a user with an account in East wants access to a server with an account in West, the referral path begins at the KDC for the user's account domain, East, passes through an intermediate domain, CorpHQ, and ends at the KDC for the server's account domain, West. The client must send its request for a session ticket three times, to three different KDCs.

1. The client asks the KDC for East to give it a ticket to the server in West.
   The KDC for East sends the client a referral ticket to the KDC for CorpHQ. This ticket is encrypted in the interdomain key East shares with CorpHQ.

2. The client asks the KDC for CorpHQ to give it a ticket to the server in West.
   The KDC for CorpHQ sends the client a referral ticket to the KDC for West. This ticket is encrypted in the interdomain key CorpHQ shares with West.

3. The client asks the KDC for West to give it a ticket to the server in West.
   The KDC in West replies by sending a ticket for the server in West.