What follows is a brief guide to Kerberos: what it's for, how it works, how to use it. It is not for system administrators who want to know why they can't make the latest release, nor is it for applications programmers who want to know how to use the interface. It certainly isn't for Kerberos hackers. You know who you are.
Kerberos is an authentication service developed at MIT, under the auspices of Project Athena. Its purpose was and is to allow users and services to authenticate themselves to each other. That is, it allows them to demonstrate their identity to each other.
There are, of course, many ways to establish one's identity to a service. The most familiar is the user password. One "logs in" to a server by typing in a user name and password, which ideally only the user (and the server) know. The server is thus convinced that the person attempting to access it really is that user.
Above and beyond the usual problems with passwords (for instance, that most people pick abysmal passwords that can be guessed within a small number of tries), this approach has an additional problem when it's translated to a network: The password must transit that network in the clear--that is, unencrypted. That means that anyone listening in on the network can intercept the password, and use it to impersonate the legitimate user. Distorting the password (for instance, by running a one-way hash over it) does no good; so long as identity is established solely on the basis of what is sent by the user, that information can be used to impersonate that user.
The key innovation underlying Kerberos (and its predecessors) is the notion that the password can be viewed as a special case of a shared secret--something that the user and the service hold in common, and which (again ideally) only they know. Establishing identity shouldn't require the user to actually reveal that secret; there ought to be a way to prove that you know the secret without sending it over the network.
And indeed there is. In Kerberos and related protocols, that secret is used as an encryption key. In the simplest case, the user takes something freshly created, like a timestamp (it need not be secret), and encrypts it with the shared secret key. This is then sent on to the service, which decrypts it with the shared key, and recovers the timestamp. If the user used the wrong key, the timestamp won't decrypt properly, and the service can reject the user's authentication attempt. More importantly, in no event does the user or the service reveal the shared key in any message passed over the network.
Of course, Kerberos is more complex than that, but broadly speaking, those complexities are there to do one of two things: to patch some of the problems caused even when using shared secrets in this improved way; and to make use of this shared secret more convenient. In this short tutorial, I'll discuss at a high level how Kerberos works, and why it's designed the way it is.
Incidentally, since one of Kerberos's underlying mechanisms is encryption, it pays to be clear about what kind of encryption we're discussing. Kerberos, as defined in RFC 4120, uses only so-called conventional or symmetric cryptography. In this kind of cryptography, there is only one key, which is shared by the two endpoints. The key is used to encrypt a message, and on the other end, the same key is used to decrypt that message (hence the name, symmetric cryptography).
There is another kind of cryptography, called public-key cryptography, in which there are two keys: a public key, and a private key. The public key, as its name implies, is publicly known and can be used, by anybody, to encrypt a message; to decrypt that message, though, one needs the private key, which is only known by one user, the intended recipient. (One could also encrypt with the private key and decrypt with the public key, and we'll see an example of that below.) Because of the two different keys, public-key cryptography is sometimes known as asymmetric cryptography. Kerberos, by default, does not use public-key cryptography, but RFC 4556, which I co-authored, adds public-key cryptography to the initial authentication phase; I'll say more about this in a bit.
Kerberos's fundamental approach is to create a service whose sole purpose is to authenticate. The reason for doing this is that it frees other services from having to maintain their own user account records. The lynchpin to this approach is that both user and service implicitly trust the Kerberos authentication server (AS); the AS thus serves as an introducer for them. In order for this to work, both the user and the service must have a shared secret key registered with the AS; such keys are typically called long-term keys, since they last for weeks or months.
There are three basic steps involved in authenticating a user to an end service. First, the user sends a request to the AS, asking it to authenticate him to the service. Fundamentally, this request consists only of the service's name, although in practice, it contains some other information that we don't have to concern ourselves with here.
In the second step, the AS prepares to introduce the user and the service to each other. It does this by generating a new, random secret key that will be shared only by the user and the service. It sends the user a two-part message. One part contains the random key along with the service's name, encrypted with the user's long-term key; the other part contains that same random key along with the user's name, encrypted with the service's long-term key. In Kerberos parlance, the former message is often called the user's credentials, the latter message is called the ticket, and the random key is called the session key.
At this stage, only the user knows the session key (provided he really is the user and knows the appropriate long-term key). He generates a fresh message, such as a timestamp, and encrypts it with the session key. This message is called the authenticator. He sends the authenticator, along with the ticket, to the service. The service decrypts the ticket with its long-term key, recovers the session key, which is in turn used to decrypt the authenticator. The service trusts the AS, so it knows that only the legitimate user could have created such an authenticator. This completes the authentication of the user to the service.
There is a version of Kerberos called Bones, which is exactly like Kerberos, except that Bones doesn't encrypt any of the messages. So what is it good for? The U.S. restricts export of cryptography; if it's sufficiently advanced, it qualifies as munitions, in fact. At one time, it was extraordinarily difficult to get crypto software out of the U.S. On the other hand, there is a wide variety of legitimate software that is exported (or created outside the U.S. altogether), and expects Kerberos to be there. Such software can be shipped with Bones instead of Kerberos, tricking them into thinking that Kerberos is there.
Doug Rickard wrote to explain how Bones got its name. In 1988, he was working at MIT, with the Project Athena group. He was trying to get permission from the State Department to export Kerberos to Bond University in Australia. The State Department wouldn't allow it--not with DES included. To get it out of the country, they had to not only remove all calls to DES routines, but all comments and textual references to them as well, so that (superficially, at least) it was non-trivial to determine where the calls were originally placed.
To strip out all the DES calls and garbage, John Kohl wrote a program called piranha. At one of their progress meetings, Doug jokingly said, "And we are left with nothing but the Bones." For lack of a better term, he then used the word "Bones" and "boned" in the meeting minutes to distinguish between the DES and non-DES versions of Kerberos. "It somehow stuck," he says, "and I have been ashamed of it ever since."
Back at Bond University, Errol Young then put encryption back into Bones, thus creating Encrypted Bones, or E-Bones.
Sometimes, the user may want the service to be authenticated in return. To do so, the service takes the timestamp from the authenticator, adds the service's own name to it, and encrypts the whole thing with the session key. This is then returned to the user.
One of the inconveniences of using a password is that each time you access a service, you have to type the darned thing in. It can be a tremendous nuisance, if you have to access a variety of different services, and so the temptation is to use the same password for each service, and further to make that password easy to type. Kerberos eliminates the problem of having passwords for each of many different services, but there is still the temptation of making the one password easy to type. This makes it possible for an attacker to guess the password--even if it is used as a shared secret key, rather than as a message passed over the network.
Kerberos resolves this second problem by introducing a new service, called the ticket granting server (TGS). The TGS is logically distinct from the AS, although they may reside on the same physical machine. (They are often referred to collectively as the KDC--the Key Distribution Center, from Needham and Schroeder [1].) The purpose of the TGS is to add an extra layer of indirection so that the user only needs to enter in a password once; the ticket and session key obtained from that password is used for all further tickets.
So, before accessing any regular service, the user requests a ticket from the AS to talk to the TGS. This ticket is called the ticket granting ticket, or TGT; it is also sometimes called the initial ticket. The session key for the TGT is encrypted using the user's long-term key, so the password is needed to decrypt it from the AS's response to the user.
After receiving the TGT, any time that the user wishes to contact a service, he requests a ticket not from the AS, but from the TGS. Furthermore, the reply is encrypted not with the user's secret key, but with the session key that came with the TGT, so the user's password is not needed to obtain the new session key (the one that will be used with the end service). Aside from this wrinkle, the rest of the exchange continues as before.
It's sort of like when you visit some workplaces. You show your regular ID to get a guest ID for the workplace. Now, when you want to enter various rooms in the workplace, instead of showing your regular ID over and over again, which might make it vulnerable to being dropped or stolen, you show your guest ID, which is only valid for a short time anyway. If it were stolen, you could get it invalidated and be issued a new one quickly and easily, something that you couldn't do with your regular ID.
The advantage this provides is that while passwords usually remain valid for months at a time, the TGT is good only for a fairly short period, typically eight or ten hours. Afterwards, the TGT is not usable by anyone, including the user or any attacker. This TGT, as well as any tickets that you obtain using it, are stored in the credentials cache.
The term "credentials" actually refers to both the ticket and the session key in conjunction. However, you will often see the terms "ticket cache" and "credentials cache" used more or less interchangeably.
So far, we've considered the case where there is a single AS and a single TGS, which may or may not reside on the same machine. As long as the number of requests is small, this is not a problem. But as the network grows, the number of requests grows with it, and the AS/TGS becomes a bottleneck in the authentication process. In short, this system doesn't scale. For this reason, it often makes sense to divide the world into distinct realms. These divisions are often made on organizational boundaries, although they need not be. Each realm has its own AS and TGS.
To allow for cross-realm authentication--that is, to allow users in one realm to access services in another--it is necessary first for the user's realm to register a remote TGS (RTGS) in the service's realm. Such an association typically (but not always) goes both ways, so that each realm has an RTGS in the other realm. This now adds a new layer of indirection to the authentication procedure: First the user contacts the AS to access the TGS. Then the TGS is contacted to access the RTGS. Finally, the RTGS is contacted to access the end service.
Actually, it can be worse than that. In some cases, where there are many realms, it is inefficient to register each realm in every other realm. Instead, there is a network of realms, so that in order to contact a service in another realm, it is sometimes necessary to contact the RTGS in one or more intermediate realms. These realms are called the transited realms, and their names are recorded in the ticket. This is so the end service knows all of the intermediate realms that were transited, and can decide whether or not to accept the authentication. (It might not, for instance, if it believes one of the intermediate realms is not trustworthy.)
This feature is new to Kerberos in Version 5. In Version 4, only peer-to-peer cross-realm authentication was permitted. In principle, the Version 5 approach allows for better scaling if an efficient hierarchy of realms is set up; in practice, realms exhibit significant locality, and they mostly use peer-to-peer cross-realm authentication anyway. However, the advent of public-key cryptography for the initial authentication step (for which the certificate chain is recorded in the ticket as transited "realms") may again justify the inclusion of this mechanism.
As I mentioned earlier, Kerberos relies on conventional or symmetric cryptography, in which the keys used for encryption and decryption are the same. As a result, the key must be kept secret between the user and the KDC, since if anyone else knew it, they could impersonate the user to any service. What's more, in order for a user to use Kerberos at all, he or she must already be registered with a KDC.
Such a requirement can be circumvented with the use of public-key cryptography, in which there are two separate keys, a public key and a private key. These two keys are conjugates: Whatever one key encrypts, the other decrypts. As their names suggest, the public key is intended to be known by anyone, whereas the private key is known only by the user; not even the KDC is expected to know the private key.
Public-key cryptography can be integrated into the Kerberos initial authentication phase in a simple way--in principle, at least. When the KDC (that is, the AS) generates its response, encapsulating the session key for the TGT, it does not encrypt it with the user's long-term key (which doesn't exist). Rather, it encrypts it with a randomly generated key, which is in turn encrypted with the user's public key. The only key that can reverse this public-key encryption is the user's private key, which only he or she knows. The user thus obtains the random key, which is in turn used to decrypt the session key, and the rest of the authentication (for instance, any exchanges with the TGS) proceeds as before.
You may well wonder why a randomly generated key must be used. Why not simply encrypt the session key with the user's public key? To begin with, public-key operations are not designed to operate on arbitrary data, which might be any length; they are designed to operate on keys, which are short. Public-key cryptography is a relatively expensive operation. So when you make a call to a library routine to encrypt anything, no matter how long it is, it first encrypts it using symmetric cryptography with a randomly generated key, and then encrypts that random key with the public key.
Even though we've been referring just to the session key, Kerberos actually encapsulates a number of other items along with it. As a result, the performance of public-key cryptography becomes a direct factor.
There's a catch. (Of course, there had to be.) The catch is that even though the user and the KDC don't have to share a long-term key, they do have to share some kind of association. Otherwise, the KDC has no confidence that the public key the user is asking it to use belongs to any given identity. I could easily generate a public and a private key that go together, and assert that they belong to you, and present them to the KDC to impersonate you. To prevent that, public keys have to be certified. Some certification authority, or CA, must digitally sign the public key. In essence, the CA encrypts the user's public key and identity with its private key, which binds the two together. Typically, the CA is someone that is trusted generally to do this very thing. Afterward, anyone can verify that the CA did indeed sign the user's public key and identity by decrypting it with the CA's public key. (See how clever the uses of the two complementary keys can be?)
In reality, the CA doesn't encrypt the user's public key with its private key, for the same reasons that the KDC doesn't encrypt the session key with the user's public key. Nor does it encrypt it first with a random key, since the user's public key and identity don't have to be kept confidential. Instead, it passes the public key and identity through a special function called a one-way hash. The hash (sometimes called a message digest) outputs a random-looking short sequence of bytes, and it's these bytes that are encrypted by the CA's private key. This establishes that only the CA could have bound the public key to the user's identity, since you can't just create any other message that also hashes to those same bytes (that's why the hash is called one-way).
You may see a potential problem: How does the KDC know that the key that signed the user's public key belongs to the CA? Doesn't someone else need to sign the CA's key--a higher-level CA perhaps? This could lead to an infinite recursion. At some point, however, the KDC must, by some other means, establish a CA's identity outside of digitally signing things, and know that a public key definitely belongs to it. This terminates the chain of certificates, starting from the user's public key and ending in the trusted CA's public key, and it is that trusted CA that represents the association shared by the user and the KDC. The advantage over sharing a long-term key is that the various authorities don't actually have to be on-line for consultation while the KDC is authenticating the user.
Incidentally, if you've used PGP (or GPG), which also employs public-key cryptography, you may have noticed that you have to enter a password or passphrase before being able to use your private key. That passphrase does not, however, actually generate the private key, which is instead generated only once, at the same time the public key is created. Rather, the passphrase is used to generate a symmetric key (just as in Kerberos), and that symmetric key is used to encrypt the private key, so that no one can snoop onto your machine and use it. Whenever you do want to use it, you have to enter the same passphrase, which generates the same symmetric key, and your private key is decrypted long enough to use it. (After you're done with it, any program that's correctly written will wipe the decrypted private key out of memory.)
Some time ago, I gave a talk about Kerberos, from a more historical perspective. Here is an essay that is chiefly drawn from that talk.
Last modified 2 January 2007.