5.2 Kerberos: The basic protocol

The following sections explain the basic Kerberos protocol as it is defined in RFC 1510. Those not familiar with Kerberos may be bewildered by the need for numerous diverse keys to be transmitted around the network. In order to break down the complexity of the protocol, we will approach it in five steps:

• Step 1: Kerberos authentication is based on symmetric key cryptography.

• Step 2: The Kerberos KDC provides scalability.

• Step 3: A Kerberos ticket provides secure transport of a session key.

• Step 4: The Kerberos KDC distributes the session key by sending it to the client.

• Step 5: The Kerberos Ticket Granting Ticket limits the use of the entities’ master keys.

Before starting to explore how Kerberos works, we must explain the notations that will be used in the illustrations:

• The u stands for user, s stands for resource server, and k stands for KDC.

• S stands for session key; Sus means the session key shared between the user and the resource server.

• M stands for master key; Mu is the master key of the user.

• Drawing (1) in Figure 5.1 represents the session key shared between the user and resource server.

  
  Figure 5.1: Session keys and encrypted session keys.

• Drawing (2) represents the same session key, but this time encrypted.

• Drawing (3) represents the same session key, encrypted using the master key of the user.

To ease reading we will talk about a “client,” Alice, and a “resource server” that authenticates using Kerberos. The identities used in this Kerberos authentication exchange are Alice’s SID and the SID of the service account that is used by the application or the service responsible for the resource. To be fully correct we should talk about the “service account of the service,” but this would not promote ease of reading. Also, when we talk about Alice, we really mean the LSA on Alice’s machine impersonating Alice and acting on her behalf. From now on, the following words are synonyms: principal and security principal and entity, and domain and realm.

5.2.1 Kerberos design assumptions

Before diving into the nuts and bolts of the protocol, let’s have a quick look at some of the design assumptions the Kerberos designers at MIT took. It is very important to keep these assumptions in mind as we run through the Kerberos internals.

• Kerberos always deals with three entities: users, servers, and a set of security servers that mediate between the users and the servers for authentication.

• Time is trusted. This is because Kerberos uses timestamps to protect against replay attacks.

• The user trusts its workstation completely. This is because Kerberos caches authentication tokens on the client side.

• The security server must be online all the time. Kerberos requires the availability of the security server in order to generate new Kerberos security tokens.

• The servers are stateless. Kerberos wants to limit the amount of security principal–related information that is kept on the server side.

• Users’ password time on user machine must be minimized. Kerberos looks at a user password as a weak secret—it should be protected the best possible. One of the ways to do this is to limit its time on the user workstation. Another way is to create a key hierarchy.

5.2.2 Step 1: Kerberos authentication is based on symmetric key cryptography

To authenticate entities Kerberos uses symmetric key cryptography.^[2] In symmetric key cryptography the communicating entities use the same key for both encryption and decryption. The basic mathematical formula behind this process is the following:

D_K(E_K(M)) = M

If the encryption (E) and decryption (D) processes are both using the same key K, the decryption of the encrypted text (M) results in the readable text (M).

This is what happens when Alice wants to authenticate to a resource server using a symmetric key cipher (illustrated in Figure 5.2):

Figure 5.2: Kerberos authentication is based on symmetric key cryptography.

• Alice encrypts her name and the current timestamp using a symmetric key.

• The encrypted message and Alice’s name are sent to the resource server.

• The resource server decrypts the message.

• The resource server checks Alice’s name and the timestamp (this is the result of the decryption process). If they are okay, Alice is authenticated to the server.

Why does this process authenticate Alice to the resource server? If the resource server can successfully decrypt the message, this means if the decryption process results in Alice’s name and an acceptable timestamp, the resource server knows that only Alice could have encrypted this information, because she is the only one, besides the resource server, who also knows the symmetric key. In this context acceptable means the following: Upon receipt of Alice’s encrypted packet, the resource server will compare the timestamp in Alice’s packet against the local time. If the time skew between these two timestamps is too big, the resource server will reject the authentication attempt, because a hacker could have replayed Alice’s original authentication packet.

In this explanation you may have noticed the differences and similarities with the NTLM authentication protocol. Both Kerberos and NTLM use symmetric cryptography for authentication: “If you can prove you know your secret key, I believe you are who you say you are.” In NTLM the knowledge of the secret key is proven using a challenge-response mechanism. Kerberos uses symmetric encryption of the timestamp and the user’s name to do the same thing.

The encrypted packet containing Alice’s name and the timestamp is known in Kerberos as the authenticator, and the symmetric key is called a session key. A session key exists between all Kerberos principals that want to authenticate to each other.

A critical element in this exchange is the timestamp: It provides “authenticator uniqueness” and protects against replay attacks. Without the authenticator, a hacker could grab a ticket off the network and use it to impersonate Alice to a resource server. The timestamp explains the time sensitivity of the Kerberos protocol and of Windows 2000 and Windows Server 2003.

Remember from the introduction that Kerberos can provide “mutual” authentication: To provide this the Kerberos protocol includes an additional exchange that authenticates the server to the client. In this example, it means that, in turn, the server will encrypt its name and the current timestamp and send it to Alice.

A big problem when using a symmetric protocol is the secure distribution of the secret key. The secret key is generated at one side of the communication channel and should be sent to the other side of the communication channel in a secure way. Secure means that the confidentiality and integrity of the key should be protected. If anybody could read the secret key when it is sent across the network, the whole authentication system becomes worthless: The secrecy of the secret key is a vital part of a symmetric cipher.

Steps 2, 3, and 4 explain how the Kerberos developers have resolved the problem of secure session key distribution.

5.2.3 Step 2: The Kerberos KDC provides scalability

The Kerberos protocol always deals with three entities: two entities that want to authenticate to one another and one entity that mediates between these two entities for authentication: the key distribution center (KDC). Why do we need a KDC?

Suppose that Alice is part of a workgroup consisting of five entities that all want to authenticate to one another using symmetric key cryptography. Because every entity needs to share a secret key with every other entity, we will need 10 keys. The mathematical formula behind this is n (n – 1)/2. In a 50,000-employee company we would need about 1.5 billion keys. Not only would we have to deal with an enormous amount of keys, but there would also be an enormous amount of small authentication databases: On every client there would be one, containing all the secret keys of the entities with which the client wants to authenticate. This solution is clearly not scalable to the level of a big environment. Imagine having to use such a solution on the Internet.

To make Kerberos more scalable, the Kerberos developers included the concept of a KDC. KDC is a trusted third party with which every entity shares a secret key: This key is called the entity’s master key. All entities trust the KDC to mediate in their mutual authentication. The KDC also maintains a centralized authentication database containing a copy of every user’s master key.

Figure 5.3: A KDC provides scalability.

In Windows Server 2003 the KDC is a service that is installed on every domain controller as part of the dcpromo Active Directory installation process. Every Windows Server 2003 domain controller runs a KDC service^[3] and hosts an Active Directory (AD) instance, the central authentication database.^{[4 ]}As a consequence, a domain with multiple domain controllers provides fault tolerance for the authentication process and the authentication database. If one DC is down, another one can automatically take over. Also, the AD authentication database is replicated between domain controllers.

The concept of a master key is not new to Windows 2000, Windows Server 2003, and Kerberos: It already existed in NT4 and earlier Windows versions. In Windows the master key is derived from a security principal’s password.

The password is a secret key that is shared between each individual security principal and the central authentication authority (in the Kerberos case the KDC). Both the entity and the KDC must know the master key before the actual Kerberos authentication process can take place. For obvious security reasons, the AD never stores the plain password but a hashed version (the hash algorithm used is MD4).

An entity’s master key is generated as part of the domain enrollment process (e.g, when the administrator enrolls the user and enters a password). A machine’s master key is derived from the machine password that is automatically created when an administrator joins the machine into a domain.

5.2.4 Step 3: The ticket provides secure transport of the session key

Figure 5.4 shows the three basic entities with which the Kerberos protocol deals: a client (Alice), a resource server, and a KDC. Figure 5.4 also shows the master keys that are shared between the entities participating in the authentication process and the KDC.

Remember that in the first step we talked about the problem of distributing the secret key (the session key) when dealing with symmetric key ciphers. This section explains how Kerberos resolves this problem. It makes the link between the session key and the master key (introduced in step 2) and explains why we really need a master key in the Kerberos protocol.

Figure 5.4: Kerberos entities and master key concept.

In Section 5.2.3, we explained that every entity shares a master key with the KDC. We also said that all entities trust the KDC to mediate in their mutual authentication. Trust in this context also means that every entity trusts the KDC to generate session keys. In the scenario shown in Figure5.4, the resource server would never trust Alice to generate session keys, because Alice has not authenticated yet to the resource server (the other way around would not work either).

So far, so good. Alice needs to authenticate to the resource server and requests a session key from the KDC. The KDC will generate the session key^[5] and distribute it to both entities. After the KDC has generated the session key, it must communicate it to both Alice and the resource server. To secure the transport of the session key to a particular entity, Kerberos encrypts it with the master key of that entity.

Because there are two entities, Alice and the resource server, two encrypted versions of the session key must be generated:

• One encrypted with Alice’s master key

• One encrypted with the master key of the resource server

In Kerberos terminology, the session key encrypted with the resource server’s master key is known as a “ticket.” A Kerberos ticket provides a way to transport a Kerberos session key securely across the network. Only the destination resource server and a Windows Server 2003 domain controller can decrypt it.

By securing the transport of the session key using the master key, Kerberos creates what is known as a key hierarchy. Figure 5.5 shows the Windows Server 2003 key hierarchy, which consists of:

Figure 5.5: Windows Server 2003 key hierarchy.

• The session key (or short-term key): A session key is a secret key that is shared between two entities for authentication purposes. The session key is generated by the KDC. Because it is a critical part of the Kerberos authentication protocol, it is never sent in the clear over a communication channel: It is encrypted using the master key.

• The master key (or long-term key): The master key is a secret key that is shared between each entity and the KDC. It must be known to both the entity and the KDC before the actual Kerberos protocol communication can take place. The master key is generated as part of the domain enrollment process and is derived from a user, a machine, or a service’s password. The transport of the master key over a communication channel is secured using a secure channel.

• The secure channel: When Windows is using a secure channel, it is using a master key to secure the transport of another master key. The following example illustrates the secure channel concept. When you create a new user, the user’s password will be sent to the domain controller using a secure channel. The secure channel is in this case made up of the master key shared between the workstation you’re working on and the domain controller. In other words, the master key is derived from the workstation’s machine account password. The concept of a secure channel was also explained in Chapter 2.

In this key hierarchy the following are also true:

• Higher-level keys protect lower-level keys.

• Higher-level keying material has a longer lifetime than lower-level keying material.

• Lower-level keying material is used more frequently for sending encrypted packets across the network. As a consequence, there is a higher risk for brute-force attacks on these packets. In other words, the associated keys should be changed more often.

5.2.5 Step 4: The KDC distributes the session key by sending it to the client

The KDC can distribute the encrypted session keys to Alice and the resource server in two ways:

• Method 1: The KDC could send it directly to both Alice and the resource server (as shown in Figure 5.6).

• Method 2: The KDC could send the two encrypted session keys to

Alice. Alice could then send out the resource server’s encrypted copy of the session key later on in the Kerberos authentication sequence (as shown in Figure 5.7).

The first method has the following disadvantages:

• The resource server has to cache all the session keys: one session key for each client that wants to access a resource on the server. This would impose a huge security risk on the server side.

• Synchronization problems could occur: The client could already be using the session key, while the resource server has not even received its copy yet.

  
  Figure 5.6: Kerberos ticket distribution Method 1.

Because of the disadvantages associated with Method 1, Kerberos uses the alternative explained next as Method 2 (see Figure 5.7):

Figure 5.7: Kerberos ticket distribution Method 2.

• Both the encrypted session keys (the one for Alice, encrypted with Alice’s master key, and the one for the resource server, encrypted with the resource server’s master key) are sent to Alice.

• Alice can decrypt the packet encrypted with her master key and get out the session key. Alice’s system can now cache both Alice’s copy of the session key and the server’s copy of the session key (contained in the ticket).

• When Alice needs to authenticate to the resource server, the client will send out the server’s copy of the session key.

The key advantage of Method 2 lies in its unique caching architecture: Alice’s machine can cache tickets and reuse them. Also, it takes away the need for the server to cache the tickets: It receives them from the clients as needed. This architecture makes the Kerberos protocol stateless on the server side. This has obvious advantages if you want to implement a load balancing or redundancy solution on the server side: There is no need to bother about keeping the session keys synchronized between the different domain controllers.

On the client side, tickets are kept in a special system memory area, which is never paged to disk. The reuse of the cached tickets is limited because of a ticket’s limited lifetime and renewal time. Windows 2000, XP, and Windows Server 2003 maintain a ticket cache for every security principal logon session. The ticket cache is purged when the logon session ends. The cache is preserved and written to disk when a system goes into hibernation mode.

5.2.6 Step 5: The Ticket Granting Ticket limits the use of the master keys

There is yet another important weakness in the protocol that we have not addressed so far: The session key that is sent back from the KDC to Alice is encrypted using Alice’s master key (as shown in Figure 5.8). This encrypted packet is sent over the network every time Alice needs a session key to authenticate to a resource server. This means that every time there is an opportunity for hackers to intercept the encrypted packet and to perform— possibly offline—a brute-force attack on the encrypted packet and derive the user’s master key.

Figure 5.8: The use of the master key.

In a brute-force attack, a hacker tries to guess the key that was used to encrypt a packet by trying out all the possible keys and looking at the result. Such attacks are not unrealistic: Remember some of the tools that were mentioned in Chapter 2 (L0phtcrack, John the Ripper…) to do brute-force attacks on the SAM or AD database or on the authentication packets sent across the network?

There is clearly a need here for a strong^[6] secret to replace Alice’s master key: This will be the role of the session key that is shared between each entity and the KDC. This session key will replace Alice’s password, and it will be used to authenticate Alice to the KDC after the initial authentication.^[7]

Although it has an identical function (authentication), the session key introduced in this step is not the same as the one used in the previous sections. This session key is shared between Alice and the KDC, and the other session key is shared between Alice and the resource server.

Just like Alice’s master key, both Alice and the KDC must know this session key. To securely transport this session key, we will use the same mechanism as the one described in steps 3 and 4:

• Step 3: Kerberos uses a ticket to provide secure transport of the session key. The special ticket used here is known as the Ticket Granting Ticket (TGT).

• Step 4: Kerberos distributes the tickets by sending them out via Alice. The KDC sends the TGT to Alice; Alice caches the TGT and can send it to the KDC when needed. Again, there is no need for the KDC to cache the TGTs of every client, and once more this makes the Kerberos protocol stateless on the server side. If you do not consider these arguments, it may sound silly that the KDC generates the session key and sends it out to the client to get it back from the client at a moment later in time.

Figure 5.9 shows how this new session key (S_ku) and the associated TGT are used in the basic Kerberos protocol exchange:

• Alice sends a logon message to the domain controller. This message is secured using Alice’s master key, derived from Alice’s password.^[8]

• The KDC will then send out a secured copy of the session key to be used for authentication between Alice and the KDC for the rest of the logon session (this session key will replace the user’s master key). The copy of the session key encrypted with the KDC’s master key is called the TGT.

• The session key and the TGT will be cached in Alice’s local Kerberos ticket cache.

• Later on, when Alice wants to access a resource on the resource server, the security process acting on Alice’s behalf will send out a request for a ticket to the KDC using the locally cached TGT. The request for the resource will be secured using the session key S_ku.

• Finally, the KDC will send back a ticket and a new session key to Alice, which she can use later on to authenticate to the resource server. Notice that in Figure 5.9 the new session key is not encrypted using Alice’s master key, but using the newly created session key S_ku.

  
  Figure 5.9: The role of the Kerberos TGT.

This sequence shows how in the basic Kerberos exchange:

• The TGT is reused to request tickets for other application or resource servers. The reuse of the TGT is limited by its lifetime. The lifetime of the TGT not only limits the usage of the TGT itself but of all the tickets that were obtained using a particular TGT. For example, if I have a TGT that is about to expire in a half-hour, every new ticket I get will also expire at the same point in time (even though the default lifetime of a ticket may be one hour).

• Ticket requests do not require further use of the client’s master key.^[9] During the logon session, a weak secret (the master key derived from a client’s password) is exchanged for a strong secret (the session key contained within the TGT). In other words, at logon time and at each TGT renewal the user will authenticate to the KDC with his master key; in subsequent ticket requests he will authenticate using the session key, which is contained in the TGT.

• The newly created session key (S_ku) doesn’t need to be cached on the KDC: The KDC gets it from the client each time the client requests a new service ticket. S_ku is encrypted using the KDC’s master key (remember: this is what they call the TGT). This feature makes Kerberos stateless on the KDC side, which has, as for resource servers, obvious advantages if some load balancing or redundancy technology has to be implemented on the KDC side.

5.2.7 Bringing it all together

In this section we will bring together all the elements that were brought up in the previous five steps. Figure 5.10 shows the complete Kerberos protocol: It consists of three subprotocols (or phases), each one made up of two steps. In the following list, the cryptic names between parentheses are the names of the Kerberos protocol messages as they are called in the Kerberos standard documents.

Figure 5.10: The complete Kerberos protocol. Request Ticket + Auth

• Phase 1: Authentication Service Exchange (occurs once for every logon session)

  • Step 1: Authentication Server Request (KRB_AS_REQ). Alice logs on the domain from her local machine. A TGT request is sent to a Windows KDC. Ntsecurity.nu makes available two tools (kerbsniff and kerbcrack) to retrieve a user’s password from the KRB_AS_REQ network exchange. To capture the KRB_AS_REQ packets, use kerbsniff. Then use kerbcrack to perform a brute-force or dictionary attack on the captured packets. The tools can be downloaded from http://www.ntsecurity.nu/ toolbox/kerbcrack/.

  • Step 2: Authentication Server Reply (KRB_AS_REP). The Windows KDC returns a TGT and a session key to Alice.

• Phase 2: Ticket-Granting Service Exchange (occurs once for every resource server)

  • Step 3: TGS Request (KRB_TGS_REQ). Alice wants to access an application on a server. A ticket request for the application server is sent to the Windows KDC. This request consists of Alice’s TGT and an authenticator.

  • Step 4: TGS Reply (KRB_TGS_REP). The Windows KDC returns a ticket and a session key to Alice.

• Phase 3: Client-Server Authentication Exchange (occurs once for every server session)

  • Step 5: Application Server Request (KRB_AP_REQ). The ticket is sent to the application server. Upon receiving the ticket and the authenticator, the server can authenticate Alice.

  • Step 6: Application Server Reply (KRB_AP_REP). The server replies to Alice with another authenticator. On receiving this authenticator, Alice can authenticate the server.

During these exchanges the following keys and tickets are cached on Alice’s computer: the TGT, the ticket used to authenticate to the resource server, and two session keys—one to authenticate to the KDC and one to authenticate to the resource server.

5.2.8 Kerberos data confidentiality, authentication, and integrity services

Windows 2000, XP, and Windows Server 2003 all include the Kerberos extensions that can be used to provide data confidentiality, authentication, and integrity for messages that are sent after the initial Kerberos exchange outlined in the previous sections. These extensions are known as the KRB_PRIV (providing data confidentiality) and the KRB_SAFE (providing data authentication and integrity) Kerberos extensions. They are based on the existence of a session key between two entities at the end of a Kerberos authentication protocol exchange:

• The session key can be used to sign a message. A hash, which is the result of applying a hash function to a message, can be encrypted using the session key. A hash encrypted with a session key is also referred to as a message authentication code (MAC).

• The session key can be used to seal a message by encrypting the message using the session key.

^[2]When the Kerberos design was started, public key cryptography was still patented (by RSA). This explains why the default Kerberos protocol (as defined in RFC 1510) relies on symmetric key cryptography.

^[3]The KDC itself is made of two subservices: the Authentication Service (AS) and the Ticket Granting Service (TGS); in other Kerberos implementations these two subservices can run on different machines, but this is not possible in Windows 2000 and Windows Server 2003.

^{[4 ]}On an interesting note, a standard Kerberos domain is made up of a master KDC and one or more slave KDCs. The master KDC is collocated with a read-write copy of the authentication database (single-master model). In Windows 2000 and Windows Server 2003 every KDC server hosts a read-write copy of the domain portion of the Active Directory (multimaster model).

^[5]The security quality of the session key depends on the quality of the random number generator used to generate the session key.

^[6]Strong means less susceptible to brute-force attacks. To resist these attacks there are two possibilities: (1) Use longer keys—longer keys create bigger key spaces and make it more difficult to guess the right key; (2) change the keys more often—this limits the chance for brute-force attacks. In other words, limit the lifetime of the keys; this principle is often referred to as perfect forward secrecy (PFS). The Kerberos developers have chosen the latter solution.

^[7]There are also other reasons why the concept of a session key shared between every Kerberos entity and the KDC is important: it allows for the KDC’s AS and TGS services to be hosted on different machines (this cannot be done in Windows, but is often done in UNIX Kerberos implementations), and it enables cross-domain authentication referrals (explained later).

^[8]The encryption of this request is not a part of the basic Kerberos protocol as defined in RFC 1510; it is based on a Kerberos extension known as Kerberos preauthentication. It will be explained later on in this chapter.

^[9]This also means that once you have a session key, in a standard Kerberos implementation there’s no more need to cache the master key on the client, which is very good from a security point of view. Microsoft Windows 2000, XP, and Windows Server 2003 still cache the master key because they need it to perform NTLM authentication to downlevel clients.