Presentation Slides (.PPT)

The Kerberos Authentication System

The Kerberos design is open-source, originating at MIT in the mid-1980's, and Kerberos is still freely available from MIT and other sources. Kerberos is also available in commercial software supported by vendors and has been incorporated into many widely-used products. For instance, Sun includes basic Kerberos functionality in Solaris, Cisco routers support Kerberos authentication for telnet connections, and Microsoft has announced it will use a version of the Kerberos protocol in Windows 2000. 

This paper will first list the goals and scope of the Kerberos system, followed by a brief review of concepts in private-key cryptography, and a description of the Kerberos "ticket-granting" approach. Appropriate applications, limitations, and competing technologies will be discussed, as well as the future of this technology. This brief overview of Kerberos is intended to highlight its main functionality, and does not exhaustively describe its features. For additional details on Kerberos, see the references listed at the end of this paper. 

Goals and Scope of the Kerberos system

A basic assumption is that network traffic is highly susceptible to interception and is the weak link in system security, rather than direct access to servers, which can be protected by physical means. The more often a specific cryptographic key is reused, the more susceptible it becomes to decoding. For this reason, each session of interactions between a user and a specific service should be encrypted using a short-lived "session key". To make the system usable in practice, however, it must be convenient, and to the greatest extent possible, transparent to the user. 

Starting with those assumptions, the system's key goals can be summarized as follows: 

• Never transmit unencrypted passwords over the network, i.e. "in the clear". 
• Protect against the misuse of intercepted credentials (also called "replay attacks"). 
• Do not require the user to repeatedly enter a password to access routine services.

Implementations of Kerberos are available from various vendors, and it is freely accessible in open-source form. The standard MIT distribution includes a basic set of applications, including telnet, POP email, and the Berkeley UNIX "R-commands" (such as rlogin). Other applications can be "Kerberized" by incorporating calls to Kerberos library functions. 

Encryption algorithms such as those used in Kerberos have long been considered munitions by the US government. The export status of Kerberos under newly liberalized regulations (October 2000) is unclear. For the time being, MIT is distributing its source only to US and Canadian citizens. Versions without encryption have been exported overseas, however. 

Private key cryptography and trusted third parties

The term "private key" cryptography (also called "secret key" or "symmetric key" cryptography) refers to an approach where the pair of entities exchanging messages share a single key used to encode and decode messages. This is in contrast to "public key" (or "asymmetric key") cryptography, where the encoding and decoding keys are separate and difficult to derive from each other, allowing one of the keys to be made publicly available. Private-key cryptography has the advantage of efficiency, but poses the fundamental problem of initially communicating the key to be used. For this reason, the two techniques are often combined. 

In both private-key and public-key cryptography, there is generally a practical need to rely on trusted third parties to certify identity. In Kerberos, a central authentication server certifies the identities of all entities (where an entity may be a user, a client application operating on behalf of a specific user, or a service provided by an application server). The functionality of Kerberos completely relies on the trustworthiness of the authentication server, which must know the password or key of every entity. It is therefore of paramount importance that the authentication server itself be completely secure. 

Kerberos ticket-granting approach

The Kerberos system's approach involves several layers of messages. Although these multiple layers may seem overly elaborate at first glance, they represent a reasonable attempt to address the design trade-offs. 

The following is a simplified description of the Kerberos message scheme (illustrated in Figures 1-3). In this discussion, the term "client" refers to a user or to a client-side application program operating on behalf of a user. As noted above, the term "application" server refers to a remote computer which provides a shared service. The term "password" refers to the user's password or to a cryptographic key derived from it (since the process of deriving the key from the password is transparent to the user). The term "session" key refers to a cryptographic key issued for use in communication between a client and an application server, which is valid for some defined interval of time. 

Two basic elements are used in Kerberos messages: a ticket and an authenticator. A ticket is acquired by a client from the authentication server, and sent to the application server as part of the request for a service. An authenticator is constructed by the client, is sent to the application server along with the ticket, and is used by the application server to verify that the request was sent by the client to whom the ticket was issued. 

As noted above, the goals of the system include 1) avoiding repeated re-entry of passwords and 2) sending unencrypted passwords over the network. To address these goals, the initial exchange with the Kerberos authentication server issues the user a "ticket-granting ticket" (TGT) containing a session key to be used for subsequent ticket requests. 

Each TGT is good for a fixed life span, typically set to 8 hours. The TGT effectively serves as a proxy for the user with the Ticket Granting Service over the life of the TGT. This prevents the user from having to authenticate themselves every time they wish to access a service on the network. 
 
 

Figure 1

The initial message from the client to the authentication server is typically sent automatically at the time of login. The initial message contains the user's name (but not password) and request for a TGT (Figure 1). 

The authentication server replies with a message encrypted with the user's password and containing a TGT (Figure 1). Because the TGT message is encrypted with the user's password, it is protected if intercepted. When received by the client, the TGT message can be decoded to obtain the session key to be used for subsequent ticket requests. This session key for ticket-granting requests is referred to below as the TG key. 
 
 

Figure 2

Once the client has a TG key, the subsequent requests for a specific service will take the form shown in Figure 2. 

The client sends a request to the Ticket Granting Service (TGS) to obtain a ticket for the service. The Ticket Granting Service can compare the client identification information embedded in the message with its record of issuing the TG key. The timestamp helps to protect against any attempt to re-use an intercepted message; typically, a request will be considered invalid if received more than 5 minutes after the embedded timestamp. This prevents messages from being intercepted, cracked offline, and then used at a later time. 

After confirming the client's identity, the Ticket Granting Service responds with a message containing a new session key. 

The ticket itself contains information identifying the client and the newly generated session key. Note that the client cannot decode or alter the ticket, only forward it to the application server. 
 
 

Figure 3

The client then sends a message to the application server containing the ticket and an authenticator (Figure 3). 

As noted above, the authenticator is constructed by the client, and contains identifying information and a timestamp. When this message is received by the application server, it can decode the ticket, because it is encrypted with the server's own key (known only to itself and the authentication server). The ticket contains the session key which is used to decode the authenticator. For the request to be considered valid, the data embedded in the authenticator must match that in the ticket. 

Subsequent messages between the client and the application server may be encrypted using the session key. 

Applications and Limitations of Kerberos

A fundamental issue is whether the Kerberos approach is scalable to the Internet. Features added in the current version of Kerberos are designed to allow inter-network authentication (in Kerberos terminology, referred to as "cross-realm" authentication). Recent proposals have included using public-key cryptography for both initial authentication of clients (TGT) and for cross-realm authentication. Such changes will make it more feasible for Kerberos to scale to larger sets of networks, but the question is far from resolved. 

One of the primary assumptions of the Kerberos protocol is that the hosts on the network can be trusted. Luckily, the extent of attacks that can occur if a host is compromised is limited. Tickets which remain in the hosts' cache can be used, but only until they expire. 

If users choose easily guessable passwords, the system is subject to a dictionary attack, where attackers simply try different passwords until the correct one is chosen. This can be overcome by administrative rules requiring passwords that are not easily guessed by a dictionary algorithm. Timestamps also help to protect against this type of attack by limiting the amount of time an attacker has to guess a password. 

Since the system relies entirely on passwords for user authentication, if the passwords themselves are stolen, the possibility of system attack is unlimited. This points to the requirement that the Key Distribution Center be protected. If it is compromised, the entire system is unsafe. 

For long processes, limited duration tickets can present problems. Kerberos Version 5 addresses this problem with renewable tickets. 

Competition to Kerberos

Kerberos Past and Future

As a mature product, Kerberos has undergone significant revision. The last major revision, Kerberos Version 5, addressed many previously identified limitations:

• Version 5 added support for forwardable, renewable, and postdatable tickets. These accommodate long running processes and processes which need to run automatically in the future, in addition to allowing users to use their credentials on a machine other than the one they logged in on. 
• Kerberos tickets can now contain multiple IP addresses and addresses for different types of networking protocols. This allows the use of multi-homed machines. 
• Replay caches keep track of recently issued tickets and do not allow the same ticket to be used twice in a row. This cuts down on the ability of attackers to hijack cached tickets before they expire. 
• There is now support for transitive cross-realm authentication which removes the requirement that each pair of realms that wish to allow authentication must share a secret. In large networks consisting of many realms, the number of secrets can become quite large and is not scalable. Instead, transitive cross-realm authentication allows a path between secret-sharing realms to be specified so that credentials from the desired realm can be earned by following this path.

Modifications to Kerberos and research on extending Kerberos are still active. For instance, as noted previously, recent work has explored using public-key cryptography for cross-realm authentication, which has the potential to improve the scalability of Kerberos. 

Kerberos' many strengths are attested to by it's wide adoption as an industry standard. It seems certain to continue to play a role in small networks with strict authentication requirements. In the broader Internet context, however, SSL seems already to have achieved de facto standard status. Even with technical improvements in its scalability, Kerberos may remain restricted to the small network context. 

References

Information about other freely available distributions of Kerberos can be found at Frequently Asked Questions About Kerberos, which also contains a great deal of other useful information (last modified August 2000). 

A list of commercial vendors providing supported versions of Kerberos or Kerberos-aware products can be found at: Commercial Implementations of Kerberos

More detailed information on the Kerberos system can be found in the following: 

Kerberos: An Authentication Service for Open Network Systems (Postscript document), Jennifer C. Steiner, Clifford Neuman, and Jeffrey I. Schiller (March 1988). 

Kerberos: An Authentication Service for Computer Networks, B. Clifford Neuman and Theodore Ts'o (September 1994). 

Limitations of the Kerberos Authentication System (Postscript document), Steven M. Bellovin and Michael Merritt (1991). 

Designing an Authentication System: A Dialogue in Four Scenes, Bill Bryant (February 1988), HTML version by Theodore Ts'o (February 1997) 

The Moron's Guide to Kerberos, Brian Tung (last modified December 1996). 

Public Key Cryptography for Initial Authentication in Kerberos, Brian Tung et al. (Draft expires August 2001) 

For additional information on DES, refer to DES Encryption and Data Encryption Standard Fact Sheet.