IS 250
Project 1

Presentation Slides (.PPT)

Jean-Anne Fitzpatrick
Jennifer English
 

The Kerberos Authentication System

Kerberos is an authentication system based on private-key cryptography. In the Kerberos system, a trusted third-party issues session keys for interactions between users and services. It is mature technology which has been widely used, although it has known limitations. 

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

Kerberos is designed to provide authentication of user identity in a networked computing environment consisting of workstations (used directly by one or more users) and servers (providing services such as email and shared file systems). It is, in part, a response to the current standard approach to network security, authentication by assertion, wherein a client gains access to services simply by asserting that it is who it says it is (or is acting on behalf of the user that it claims it is). 

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.
The Kerberos system attempts to address design tradeoffs between the level of protection provided and the user's convenience, while also considering the complexity of system administration and application development. 

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 crypographic algorithm typically employed in Kerberos is Data Encryption Standard (DES), although the modular design of Kerberos allows alternative encryption libraries to be used. DES is a standard algorithm for "private-key" cryptography. 

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

An essential conflict exists between the need to communicate the encryption key, and the need to keep the key secret. There is also a trade-off between using a unique key for every message and re-using a single key for an extended session of interactions (this trade-off potentially impacts both efficiency and convenience, vs. the level of protection provided). 

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

Kerberos is suitable for supporting authentication, authorization, and confidentiality within a network or small set of networks. However, it is not as well suited to some other functions, such as digital signatures (which provide both certification of identity and non-repudiation), for which public-key cryptography is often used. 

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' main competition is SSL, an authentication technology developed by Netscape which uses certificates issued by Verisign to vouch for the client's identity. The two are really suited for different purposes. It is a worthwhile exercise, however, to compare the two. 
 
SSL Kerberos
Uses public key encryption Uses private key encryption
Is certificate based (asynchronous)  Relies on a trusted third party (synchronous) 
Ideal for secure communications with a large, variable user base that is not known in advance, such as the WWW, because it can be used when one side of the communication does not know a password.  Ideal for networked environments where all services and users are known in advance. However, authentication and ticket granting services become a bottleneck as network requests increase. Version 5 will make Kerberos more scalable with the ability to hierarchically arrange realms of the network, each of which has its own AS and TGS, and which trust each other based on explicit instructions from the system administrator. (This is known as cross realm authentication.) 
Key revocation must be accomplished either by sending revocation certificates to all relevant servers or by having a centralized, available "Revocation Server" against which all certificates would be compared. This removes one of the key benefits of SSL - its independence from trusted third parties.  Key revocation can be accomplished by disabling a user at the Key Distribution Center. Once again, the extent of an attack is limited to the remaining time on any outstanding tickets. 
Certificates sit on a users hard drive (even if they are encrypted) where they are subject to being cracked.  Passwords reside in users' minds where they are usually not subject to secret attack. (This assumes that users do not write their passwords down.) 
Uses patented material, so the service is not free. Netscape has a profit motive in wide acceptance of the standard.  Kerberos has always been open source and freely available. Kerberos is open source and platform independent, It can be used on Unix, Windows, Macintosh, and AFS.

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 on the MIT distribution of Kerberos can be found at: http://web.mit.edu/kerberos/www/

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.