3.2 Kerberos 4

The Kerberos 4 protocol is largely based on the Needham-Schroeder protocol, with two major changes.

The hosts involved in the Kerberos 4 protocol exchanges map directly to the principals involved in the Needham-Schroeder protocol. The authentication client is a Kerberos 4 user workstation, and the authentication server maps to a Kerberos 4 Key Distribution Center.

The first change to the Needham-Schroeder protocol reduced the amount of network messages sent between the client and the authentication server. The original Needham-Schroeder protocol did not have a dependence on a network time source, but the cost was an extra two message exchanges. The last two message exchanges in the Needham-Schroeder protocol establish that there is no man in the middle posing as the authentication server, and that the session key is not a replay. In the Kerberos 4 protocol, replay is thwarted through an authenticator message that is constructed of the local time of the client encrypted with the newly-negotiated session key of the connection. While this requires time synchronization between all hosts involved, it does reduce the number of network messages required per authentication exchange.

The second, more significant, change to the basic protocol creates the concept of a Ticket Granting Ticket, which allows users to authenticate to multiple application servers while entering their authentication secret only once. If the original Needham-Schroeder protocol were implemented as-is, a user would need to enter her password every time that she wishes to log into an application server. One of the major design goals for Kerberos was to create a single-sign-on system in which users only need to enter their credentials once per day, and all future authentication requests are handled transparently, without user intervention.

As a result, the Kerberos 4 protocol is split into two logical components: the Authentication Server and the Ticket Granting Server. Note that there is an unfortunate clash in terminology here. The Kerberos Authentication Server should not be confused with the Needham-Schroeder authentication server; the former performs a subset of the services of the latter, as we'll see in a bit. To keep the distinction clear, references to the Kerberos Authentication Server and Ticket Granting Server will be capitalized or abbreviated as AS or TGS, respectively. While these components are usually implemented as a single program that runs on the KDC, they are logically separate processes.

Still other changes reflect the realities of the security of today's computer networks. The original Needham-Schroeder protocol assumed that all secrets involved, including the user's long term key, the application server's long term key, and the session key that is randomly generated by the KDC, are always kept secret. In reality, machines are compromised and people give away their passwords. In addition, the single-sign-on capability provided in Kerberos 4 means that users' workstations will have cached credentials that, if left unguarded, can be used by an attacker to impersonate the user. Therefore, Kerberos 4 introduces limited lifetimes for credentials, enforced by the Kerberos KDC and Kerberos libraries. Without ticket expiration, a user could log in once, and never have to log in again (provided that their credentials are never removed from the workstation). Lifetimes ensure that users must verify their identity periodically—say, once a day—by entering their password again. They also close the window of vulnerability in the case of stolen credentials.

3.2.1 The Authentication Server and the Ticket Granting Server

The Authentication Server performs one function: receive a request containing the username of the client requesting authentication, and return an encrypted Ticket Granting Ticket for that user. Then, the client can use this Ticket Granting Ticket (the TGT) to request further tickets for other services.

When a client has no Kerberos tickets cached, or tickets that have expired, then the client must communicate with the Authentication Server to get an initial ticket to the Ticket Granting Server. This typically happens at the beginning of each day, as most Kerberos implementations default to 8-10 hour ticket lifetimes.

The first message sent to the Kerberos KDC from the client is the Authentication Server Request message, also known as an AS_REQ message. This message is sent in plain text, containing the identity of the client, the client's local time, and the Ticket Granting Server's principal name. By convention, in Kerberos 4, the Ticket Granting Server's principal name is krbtgt. In addition, the Ticket Granting Server's principal always has an instance component. The instance component is the realm for which the ticket granting server can issue further tickets. Every realm contains at least one Ticket Granting Server, a TGS with an instance of the realm itself. For example, the Ticket Granting Server for the WEDGIE.ORG realm is krbtgt.WEDGIE.ORG@WEDGIE.ORG.

A special case occurs when two or more realms trust each other's users and services. This relationship, known as a cross-realm trust, requires special TGS principals to be set up in all participating realms, with different instance components representing the different realms. We won't talk more about cross-realm here; instead, we'll come back and explore the implementation of cross-realm authentication in Chapter 8.

Once the KDC receives the AS_REQ message, it verifies that the requesting principal exists, and that the client's timestamp is close to the KDC's local time (usually this means within five minutes). This check is made not to detect replay; after all, the AS_REQ message is sent entirely in clear text. Instead, it performs the timestamp check so that clients can provide users a message early in the authentication process in the event of a time mismatch between the client and the KDC. If either of these checks fails, an error message is sent back to the client and the client is not authenticated.

Next, the Authentication Server generates a random session key. This session key will be shared between the client and the Ticket Granting Server. This key secures the ticket requests that the client makes to the Ticket Granting Server later on for specific Kerberized services. The KDC makes two copies of this session key: one for the client, and one for the Ticket Granting Server.

The KDC responds with an Authentication Server Reply message, or AS_REP message. This message includes the information above—most importantly, a copy of the session key and verified identity of the client encrypted with the Ticket Granting Server's key, and another copy of the session key encrypted with the user's long-term key. As long as the client has knowledge of the user's long-term key, then the client can decrypt the message encrypted with the user's key, and acquire the session key now shared between the client and the Ticket Granting Server. The knowledge of this session key and the possession of the Ticket Granting Ticket (the other copy of the session key, encrypted with the Ticket Granting Server's key) allow the client to obtain tickets for further Kerberos services without requiring the user to re-enter their password.

This implies that the security of your Kerberos system is highly dependent on the passwords your users choose. Since the Authentication Server will happily return an encrypted Ticket Granting Ticket valid for any principal to any client, the only line of defense against attackers is a strong password. A further discussion of this issue can be found in Chapter 6. The AS_REQ and AS_REP exchange is summarized in Figure 3-6.

Figure 3-6. Authentication Server request-and-reply exchange

Once the Authentication Server transaction has completed, the client possesses a session key, encrypted with the user's long-term key, as well as a Ticket Granting Ticket, encrypted first with the Ticket Granting Server's key. The client attempts to decrypt the message with the user's long-term key (password). If this decryption is successful, then the password is correct and the client stores the Ticket Granting Ticket as well as its copy of the session key in a credential cache. Remember that even though the client has removed the outer layer of encryption of the Ticket Granting Ticket, it is still encrypted with the Ticket Granting Server's key. Therefore, the client cannot read the contents of the Ticket Granting Ticket; instead, it simply stores the encrypted contents in the credential cache.

When the user wishes to authenticate to a Kerberized service later, there is a separate protocol exchange with the Ticket Granting Server. The client prepares a message to the Ticket Granting Server consisting of three parts: a TGS request, a copy of the Ticket Granting Ticket acquired earlier, and an authenticator that serves to thwart replay.

The authenticator consists of a timestamp, encrypted with the session key acquired from the Authentication Server exchange. The authenticator ensures that every ticket request packet is unique, and also proves that the client has knowledge of the shared session key established during the Authentication Server exchange. Without the authenticator, an attacker could simply listen on the network for a ticket sent by the KDC to a legitimate client, make a copy of the ticket, and replay that ticket to either the KDC (in the case of a Ticket Granting Ticket) or an application server (in the case of a service ticket).

Upon receipt of the ticket request from the client, the KDC formulates a reply message that includes a new set of session keys, shared between the client and the application server. The client's copy of the new session key is encrypted with the older session key, established during the Authentication Server exchange. This ensures that only the valid client can read the new session key for use with the application server. The service's copy of the new session key is embedded inside of a service ticket, encrypted with the service's long-term key. The client appends this service ticket and the new session key to its credential cache for later retrieval. When the client contacts the application server, the knowledge of this service ticket and the session key will prove to the service that the client is authentic. Figure 3-7 depicts the protocol messages involved in the Ticket Granting Server exchange.

Figure 3-7. Ticket Granting Server message exchange

The three major cryptographic messages that are passed back and forth in both the Authentication Server and Ticket Granting Server exchange are the service ticket, the Ticket Granting Ticket, and the authenticator. Figure 3-8 depicts the contents of these cryptographic messages.

Figure 3-8. Service ticket, Ticket Granting Ticket, and authenticator

Note that in the Kerberos system, the KDC does not specify policy on what principals are authorized to access a given service. The KDC will, after ensuring the validity of the Ticket Granting Ticket sent by the client, happily issue a ticket for any service that it knows about. Kerberos leaves the authorization decisions to the individual application servers. The possession of a valid service ticket for a given service does not imply that the user should be granted access to that service; instead, it assures the end service of the authenticity of the end user's credentials. Figure 3-9 summarizes the network exchanges between the Authentication Server and the Ticket Granting Server.

Figure 3-9. Authentication Server and Ticket Granting Server protocol exchanges

The details of the final step in authentication—how the client sends the service ticket to an application server—are different for every application server. Kerberos does not define a standard for doing this; instead, it is up to each application to define a method for the client to send its service ticket and an authenticator for authentication. While Kerberos provides function libraries that can formulate and read messages to perform these tasks, the actual transmission and reception of the messages is wholly application-dependent.

3.2.2 String-to-Key Transformation

Kerberos 4 requires a transformation between the textual passwords that people remember and the 56-bit DES key that is actually used for encryption and decryption of the messages passed back and forth between client, KDC, and application server. This transformation is referred to as a string-to-key function, usually shortened to simply string2key. The transformation is very similar to the functions used to "encrypt" passwords in the standard Unix /etc/passwd file. It is a one-way hash function that, in the case of Kerberos 4, uses the principal's password as input, and outputs a 56-bit hexadecimal DES key. Since the function is one way, it is mathematically very hard (read as impossible) to reverse the algorithm to deduce the password from the generated DES key. However, since this algorithm is public (and, indeed, must be widely known in order for different Kerberos implementations to interoperate), a brute-force or dictionary attack can be used to try passwords to find a matching DES key for a particular message.

The details of the string2key function are not particularly important to this discussion. If you're interested in exactly how the transformation is performed, the string2key function is included in both the MIT and kth-krb Kerberos 4 distributions. In addition, kth-krb includes a kstring2key program that, given a password as input, outputs the hexadecimal DES key resulting from the string2key transformation.

3.2.3 The Key Version Number

The key version number, commonly abbreviated as kvno, distinguishes between different encryption keys that are stored for a given principal. For example, if a user changes his password, then his principal has a new encryption key associated with it. When the Kerberos KDC stores his new encryption key in the Kerberos database, it increments the key version number. Similarly, if a service's long-term key is changed, the key version number also changes.

Key version numbers are not important when dealing with user principals. However, they do become important when working with Kerberized services. In order for Kerberized services to be able to read the ticket contents sent by clients for authentication, both the encryption key and the key version number that is stored in the service's keytab must match the encryption key and key version number that is stored in the Kerberos database. A mismatch in either the encryption key or key version number will cause the decryption process to fail.

3.2.4 Password Changing

The original Kerberos specifications had no provisions to allow users to change their own passwords. However, the ability for users to change their passwords is a requirement for any practical authentication scheme, so Kerberos 4 implementations grafted on password-changing protocols. As a result, most Kerberos 4 packages implement password changing through a separate administrative protocol, the same protocol that is used to remotely administer the Kerberos database.

Both MIT and kth-krb run the password through the string2key function on the client side to avoid sending even the encrypted text password over the network. This has the advantage of not exposing a plain text password over the network, but has the down side that all password quality checks must be implemented on the client side, so a rogue password-changing client could bypass all quality checks.

The administrative protocols for MIT and kth-krb differ, so there is no interoperability between the password-changing services in either. The kpasswd program from one will not connect to the password-changing service provided by the other.