# An introduction to Kerberos

## 1. Notes to the Reader; A Table of Contents

The current post introduces **Kerberos**, a popular authentication protocol. The intended audience for the current post is those with a rudimentary background in software engineering or computer science. Specifically, we expect the reader to be able to follow technical discussions involving pseudocode, boolean operations, and asymptotic computational complexity.

The current post consists of seventeen sections, intended to be read sequentially:

- Notes to the Reader; A Table of Contents
- One-Way Functions
- Pseudorandom Generators
- Case Study: The One-Time Pad
- Symmetric-Key Cryptography
- Public-Key Cryptography
- Authentication
- Centralized Authentication: the Needham–Schroeder protocol
- An Overview of the Kerberos Protocol
- Replay Attacks
- Authenticators
- A Few Human Problems
- Tickets: The Basics
- Tickets: Special Cases
- Realms and Delegation
- Using Kerberos
- A Brief History

Readers with no background in cryptography should start from the beginning. Readers with prior exposure to elementary cryptography may skip to Section 7. Readers already familiar with the Needham–Schroeder protocol may skip to Section 9.

## 2. One-Way Functions

The fundamental goal of cryptography is to create a secret message: easy to encrypt, difficult to decrypt. At the center of working towards this goal is the concept of **one-way functions**, procedures that are easy to compute but difficult to invert.

The canonical exmaple of a one-way function is integer multiplication. Even the naïve algorthm of long multiplcation incurs no more than $O(n^2)$ time complexity, where $n$ is the number of bits in the larger of the two integers. In practice, standard tools such as the Java BigInteger multiplication rely on algorithms such as the Karatsuba algorithm and the Toom–Cook multiplication, which bring down the time complexity to roughly $O(n^{1.5})$.

On the other hand, prime factorization, the inverse operation of multiplication, is a laborious procedure, requiring us to check many potential candidates. The general number field sieve, the most asymptotically-efficient factirization algorithm to date, still requires subexponential time complexity, i.e., asymptotically slower than algorithms with $O(n^p)$ time complexity for any value of $p$.

While there is no known mathematical proof that efficient factoring is, in fact, impossible, centuries of failed attempts suggest that devising an efficient factoring algorithm is improbable. For this reason, the cryptographic community at large operates with the assumption that multiplication is a one-way function, known as the **hardness of integer factorization assumption**. Other candidates for one-way functions include cryptographic hash functions, modular exponentiation, and the Rabin function.

## 3. Pseudorandom Generators

With one-way functions, we can construct **pseudorandom generators**, procedures that generate a large number of bits from a small number of bits in a *more or less* random fashion.

*More or less* is sufficient in practical scenarios, so long as there is no efficient way to tell whether the generated numbers are truly random or not. To this end, we define a **pseudorandom generator** of a function that takes a bitstring (“seed”) and returns a larger-sized bitstring to be the property that there is no efficient algorithm to tell the output distribution of the function from that of the outputs of the uniform distribution, i.e., the “truly-random” numbers.

Even pseudorandom generators are quite tough to construct. Indeed, it says that *every* algorithm must fail to tell apart the generated numbers from the truly-random numbers! It rules out, for example, the linear congruential generator that Java uses for `java.util.Random`

, or the Mersenne Twister that Python uses for `random`

. This is why the random number generators in programming language standard libraries often carry the warning that they are not cryptographically secure.

In fact, there is no known example of a mathematically-verified pseudorandom generator, just as there is no such example of one-way functions. Fortunately, there is a simpler criterion for computational indistinguishability that lends itself to better practical approximations, called the next-bit test. We use a weaker version of the next-bit test complemented by various experimental cryptographic assessments as a basis for certifying number generation algorithms as **cryptographically secure pseudorandom number generators**. `java.security.SecureRandom`

in Java and `secrets`

in Python are standard-library examples of cryptographically secure pseudorandom number generators.

Specifically, the next-bit test states that if any attacker who knows the first $n$ bits of a generated bitstring cannot efficiently predict what the $n+1$th bit is without knowing the seed bitstring, then the underlying number generator is a pseudorandom generator. In practice, we relax the criterion from *all* $n$-bit bitstrings to a *well-chosen subset* of $n$-bit bitstrings.

We do not cover how to construct a pseudorandom generator from a one-way function. See “A Pseudorandom Generator From Any One-Way Function” by Håstad, Impagliazzo, Levin, and Luby for the details.

## 4. Case Study: The One-Time Pad

Let us now generate a random $n$-bit string $k$ with our newly-acquired pseudorandom generator. Given an $n$-bit string $x$, we define the **one-time pad ciphertext of $x$ with respect to $k$** to be

$$x \, \textrm{XOR} \, k$$

The bitstring $k$ is called the **key** for the ciphertext $x \, \textrm{XOR} \, k$.

Since

$$\begin{align*} (x \, \textrm{XOR} \, k) \, \textrm{XOR} \, k &= x \, \textrm{XOR} \, (k \, \mathrm{XOR} \, k) \\ &= x \, \textrm{XOR} \, \underbrace{111 \ldots 11}_{n \text{ bits}} \\ &= \textrm{NOT}(x)\end{align*}$$

regardless of the values of $x$ and $k$, knowing the key $k$ allows us to convert the ciphertext back to the original bitstring $x$.

On the other hand, it is quite difficult to recover $x$ from $x \, \mathrm{XOR} \, k$ without the knowledge of key $k$. To see this, recall the $\mathrm{XOR}$ truth table:

$$\begin{array}{ccc} p & q & p \, \mathrm{XOR} \, q \\ 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{array}$$

Observe that the $\mathrm{XOR}$ of two one-bit strings has equal change of being 0 and 1. Since $\mathrm{XOR}$ is a bitwise operation, it follows that the $\mathrm{XOR}$ of two bitstrings of size $n$ has an equal change of being any of the $2^n$ possible $n$-bit bitstrings. In other words, the result of an $\mathrm{XOR}$ operation appears completely random to anyone without the knowledge of key $k$.

It is important tonote that the above security guarantee presumes that $k$ is random and thsu unpredictable. As soon as $k$ is discovered, another $\mathrm{XOR}$ operation decrypts any ciphertext with perfect accuracy.

Worse, a repeated use of the same key can reveal the key, hence the name one-time pad. This was the key insight in decrypting intercepted encrypted Soviet communications in the 1940s, through a counterintelligence program now known as the Venona Project.

## 5. Symmetric-Key Cryptography

The one-time pad is an example of a **symmetric-key cryptographic algorithm**, where the same key can be used to encrypt a message into a ciphertext and decrypt a ciphertext back to the original message.

The term **symmetric** refers to the symmetry of the encryption key and the decryption key. It does not refer to the symmetry of encryption and decryption algorithms, as in the case of the one-time pad. In fact, most modern-day symmetric-key algorithms have different procedures for encryption and decryption. Standard examples of symmetric-key cryptographic algorithms include the 56-bit key Data Encryption Standard (DES) and the 256-bit key Advanced Encryption Standard (AES).

For us, it suffices to note that Kerberos is an extension of a symmetric-key cryptographic algorithm. Such algorithms have the following characteristics:

- The keys must be random and known only to the
**principals**, the two main communicators exchanging encrypted information. - Both principals must have the same key prior to initiating encrypted communication.
- 1 and 2 combined lead to the
**problem of secure key exchange**, the most significant defect of symmetric-key cryptography. - The keys are often small and can be generated with low computational cost.
- Encryption and decryption are computationally inexpensive.

## 6. Public-Key Cryptography

Also known as **asymmetric-key crytography**, public-key cryptography addresses the problem of secure key exchange inherent in symmetric-key cryptography.

A public-key cryptographic algorithm employs two types of keys: a **public key** and a **private key**. Encryption required only the public key, whereas decryption requires both the public key and the private key. This allows the principals to communicate securely without agreeing upon the same secret key, as their public keys can be shared freely. So long as both principals hold onto their private key in secret, each principal can encrypt messages in a manner that can only be decrypted by the other principal.

The most famous example of a public-key algorithm is the **Rivest–Shamir–Adleman** (RSA) algorithm. The $n$-bit RSA algorithm generates two random prime numbers $p$ and $q$, whose product $r=pq$ is of size $n$ bits. The public key is generated by applying simple computational procedures to $r$, whereas the private key cannot be computed easily without the knowledge of $p$ and $q$. It now follows from the hardness of the integer factorization that the private key cannot be computed with ease from the public key.

RSA then applies cheap computational procedures to the public key and a message to produce a ciphertext. Similarly, the decryption algorithm is a quick procedure involving the private key and the ciphertext corresponding to a message.

The typical size of an RSA public key in use ranges from 1024 bits to 4096 bits. Compare these to the standard size of an AES key, which is 4 to 16 times smaller. Moreover, unconditional random number generation is computationally far cheaper than random prime number generation, adding to the cost of using a public-key cryptographic protocol.

For this reason, contemporary cryptographic protocols typically use a public-key system to exchange the key for a symmetric-key system, and rely on the latter for subsequent communication.

## 7. Authentication

None of the cryptographic protocols discussed thus far provides any guarantee that

- a message remains unmodified during transmission (
**data integrity**), and that - the source of the message is what the message claims it to be (
**authenticity**)

To safeguard against the above issues, we introduce a **message authentication code** (MAC). In a shared-key MAC scheme, the sender generates a **tag** $t$ for the message $m_1$ and offers it alongside their ciphertext. The recipient decrypts the text to obtain message $m_2$ and plugs it into a verification algorithm that accepts the received tag $t$ only if $m_1 = m_2$.

By generating the tags pseudorandomly, we ensure that an attacker without the shared key is unlikely to be able to intercept a ciphertext, tamper it, and then swap out the original tag with a new, correct one corresponding to the new ciphertext. A tag check thus serves as a reliable measure for data integrity and authenticity.

A popular example of a MAC scheme is **HMAC**, which uses a cryptographic hash function for tag generation.

## 8. Centralized Authentication: the Needham–Schroeder protocol

In practice, it is impractical to expect each person to generate and exchange different keys with everyone they communicate with and maintain all those keys in a secure manner. It is more reasonable to involve a **trusted third party** who is aware of both principals’ identities and can provide keys for the principals to communicate securely.

As a case study, we examine the **symmetric-key Needhan–Schroeder protocol**, which allows a centralized **authentication server** (AS) to provide temporary keys for the principals, known as **session keys**.

Consider two principals **Alice** and **Bob**, who wish to communicate within a coporate network, relying on authentication server **Server** to smooth out the process.

We assume that both **Alice** and **Bob** registered their identities to **Server**. We also assume that there is no direct, secure communication channel between **Alice** and **Bob** that can be used to exchange a secret key, rendering the traditional symmetric-key systems unusable.

__ Step 1__.

**Alice**sends a message to

**Server**, declaring her identity alongside the identity of

**Bob**, her desired correspondent. The content of the message is

```
[Alice, Bob, Nonce(1)]
```

where **Nonce(1)** is a cryptographic nonce, a pseudorandom number that is meant to be discarded after one round of communication.

__ Step 2__.

**Server**possesses identifying keys

**AliceKey**and

**BobKey**of

**Alice**and

**Bob**, which we assume are keys for symmetric-key-encrypted exchanges between

**Server**and each principal, respectively.

**Server**also generates a session key

**SessionKey**, which

**Alice**and

**Bob**will use for symmetric-key-encrypted exchanges between each other.

__ Step 3__.

**Server**sends out the following reply to

**Alice**:

```
encrypt(
message=[
Nonce(1),
Bob,
SessionKey,
encrypt(
message=[SessionKey, Alice],
key=BobKey
)
],
key=AliceKey
)
```

Note that the above message as a whole is encrypted with **AliceKey** but contains a part encrypted with **BobKey**.

__ Step 4__.

**Alice**receives the message in Step 3 from

**Server**. Since

**Alice**already possesses

**AliceKey**, she is able to decrypt the outermost layer, obtaining

```
[
Nonce(1),
Bob,
SessionKey,
encrypt(
message=[SessionKey, Alice],
key=BobKey
)
]
```

Recall that only **Alice** and **Server** possesses **AliceKey**. **Alice**, having decrypted the incoming message, concludes **Server** is indeed the sender of the above message.

Moreover, the inclusion of the same nonce that **Alice** sent to **Server** allows **Alice** to reason that the message she received from **Server** has not been tampered.

__ Step 5__.

**Alice**stores

**SessionKey**in a secure location and sends the undecrypted portion

```
encrypt(
message=[SessionKey, Alice],
key=BobKey
)
```

to **Bob**.

__ Step 6__.

**Bob**receives the message in Step 5 from

**Alice**. Since

**Bob**already possesses

**BobKey**, he can decrypt the above message and obtain

```
[SessionKey, Bob]
```

Sine both **AliceKey** and **BobKey** were required to obtain this message, **Bob** knows that **Server** guarantees:

**Alice**to be the sender of the message, thus establishing authenticity, and**SessionKey**to be the symmetric-key session key between**Alice**and**Bob**, which can be used to establish data integrity in subsequent message exchanges.

__ Step 7__. To confirm the receipt of

**SessionKey**,

**Bob**sends the following message to

**Alice**:

```
encrypt(
message=[Nonce(2)],
key=SessionKey
)
```

__ Step 8__.

**Alice**confirms to

**Bob**that she has received the message and is capable of decrypting it by sending the following message to

**Bob**:

```
encrypt(
message=[Nonce(2), "hi!"],
key=SessionKey
)
```

__ Step 9__.

**Alice**and

**Bob**have confirmed that they have a shared

**SessionKey**and can now communicate securely through traditional symmetric-key schemes.

With a minor modification of the above scheme, we can obtain a public-key version of the Needham–Schroeder protocol as well. See “Using Encryption for Authentication in Large Networks of Computers” by Roger M. Needham and Michael D. Schroeder for details.

## 9. An Overview of the Kerberos Protocol

We are now ready to study the **Kerberos** authentication protocol, which provides a secure way to perform trusted third-party authentication over a potentially unsecure network. In this section, we describe the protocol as specified in IETF RFC 4120 and surveyed in “Kerberos: an authentication service for computer networks” by B. Clifford Neuman and Theodore Ts’o.

The basic Kerberos authentication protocol is a version of the symmetric-key Needham–Schroeder protocol. In what follows, all keys are assumed to be secret keys as in symmetric-key cryptography.

We consider three actors: a client `Client`

, an application server `Server`

, and an authentication server `Auth`

. We assume that `Auth`

possesses key `ClientKey`

shared by `Client`

. This happens when, for example, `Client`

registers a password with `Auth`

. Similarly, we assume that `Auth`

possesses key `ServerKey`

shared by `Server`

.

The goal is for `Auth`

to ensure `Server`

, who has no knowledge of `ClientKey`

, that `Client`

does know `ClientKey`

, thus authenticating `Client`

. This is done in the following manner:

__ Step 1__.

`Client`

sends a request to `Auth`

for a proof of its identity that it can send over to `Server`

. The message `ClientToAuth`

consists of:`ClientId`

, identifying information about`Client`

;`AuthId`

, identifying information about`Auth`

;`Nonce(1)`

a cryptographic nonce.

__ Step 2__. Upon receipt of

`ClientToAuth`

, `Auth`

checks `AuthId`

to determine whether the request was meant for `Auth`

. It then checks `ClientId`

and retrieves corresponding `ClientKey`

from its database of keys.__ Step 3__.

`Auth`

collects the following:`AuthId`

, identifying information about`Auth`

;`Nonce(1)`

, the same cryptographic nonce`Auth`

received from`Client`

;- a newly-generated random key
`SessionKey`

, - a ticket
`ServerTicket`

consisting of`AuthId`

, identifying information`ServerId`

about`Server`

, and`SessionKey`

.

__ Step 4__.

`Auth`

encrypts `ServerTicket`

with `ServerKey`

, generating```
EncryptedServerTicket = encrypt(message=ServerTicket, key=ServerKey)
```

__ Step 5__.

`Auth`

collects `AuthId`

, `Nonce(1)`

, `SessionKey`

, and `EncryptedServerTicket`

into one message `AuthToClient`

.__ Step 6__.

`Auth`

encrypts `AuthToClient`

with `ClientKey`

, obtaining```
EncryptedAuthToClient = encrypt(message=AuthToClient, key=ClientKey)
```

__ Step 7__.

`Auth`

sends `EncryptedAuthToClient`

over to `Client`

.__ Step 8__. Upon receipt of

`EncryptedAuthToClient`

, `Client`

decrypts it to obtain `AuthId`

, `Nonce(1)`

, `SessionKey`

, and `EncryptedServerTicket`

.__ Step 9__.

`Nonce(1)`

assures `Client`

that `AuthToClient`

is sent in response to `ClientToAuth`

.__ Step 10__.

`AuthId`

assures `Client`

that `AuthToClient`

originated from the intended authentication server.__ Step 11__.

`Client`

is unable to decrypt `EncryptedServerTicket`

, and so it sends it over to `Server`

.__ Step 12__. Upon receipt of

`EncryptedServerTicket`

, `Server`

decrypts it to obtain `ServerTicket`

, which contains `AuthId`

, `SessionKey`

, and `ServerId`

.__ Step 13__.

`AuthId`

assures `Server`

that the authentication of `Client`

was provided by `Auth`

, an authentication server `Sever`

trusts.__ Step 14__.

`ServerId`

assures `Server`

that `SessionKey`

was generated for `Server`

.__ Step 15__. Now, both

`Client`

and `Server`

possesses `SessionKey`

. `Server`

can now securely authenticate `Client`

using `SessionKey`

.__ Step 16__. Just to be sure,

`Server`

sends the following message to `Client`

, thereby performing a **handshake request**:

```
HandshakeServerToClient = encrypt(message=Nonce(2), key=SessionKey)
```

__ Step 17__.

`Client`

decrypts `HandshakeServerToClient`

and obtains `Nonce(2)`

.__ Step 18__. To prove that

`Client`

was able to decrypt the received message, `Client`

adds a little something to `Nonce(2)`

, say, `Nonce(2)-1`

.__ Step 19__.

`Client`

sends the following message to `Server`

:```
HandshakeClientToServer = encrypt(message=(Nonce(2)-1), key=SessionKey)
```

__ Step 20__. Upon receiving

`HandshakeClientToServer`

, `Server`

decrypts it to confirm that `Client`

received `Nonce(2)`

and was able to successfully decrypt it.__ Step 21__.

`Server`

is now confident that `Client`

is what it claims to be, and that `SessionKey`

is the key to be used to communicate with `Client`

.## 10. Replay Attacks

For simplicity, we have presented in Section 9 an incomplete description of Kerberos, which we shall call the **naïve Kerberos protocol**. We now discuss the main vulnerability of the naïve protocol and what full-blown Kerberos does to mitigate the vulnerability.

Consider three actors: Alice, Bob, and Eve. Alice and Bob are two principals sharing classified information. Eve is an eavesdropper attempting to trick Alice and Bob into revealing classified information to her.

Suppose Alice requests a piece of information from Bob, and Bob, in turn, requests Alice for a proof of her identity. Unfortunately, neither Alice nor Bob is up-to-date on the progress of modern cryptography, and Bob simply requires a hash of Alice’s password for authentication. Alice hashes her password and sends it over to Bob, who then offers the requested information to Alice.

What Alice and Bob do not know, however, is that Eve hijacked Alice’s password hash. At first, Eve simply copies the message containing the hash and sends it over to Bob. Upon verifying that Bob releases substantial information to Alice in response to the hash, Eve sends the copied hash to Bob, requesting more information. Since Bob has no way of knowing whether the hash was sent by Alice or Eve, Bob releases the requested information, unintentionally leaking classified information to Eve.

This scenario is known as a **replay attack**.

Suppose now that Alice and Bob adopts the naïve Kerberos protocol. At first glance, the new protocola ppears far stronger than a simple check-the-hash protocol. Nevertheless, it is vulnerable to replay attacks as well.

To see how, let us assume that Eve records all the messages exchanged between Alice and Bob. We also assume that a momentary carelessness allows Eve to gain temporary access to either Alice’s computer or Bob’s computer and steal `SessionKey`

. Now, a replay attack can be carried out as follows:

__ Step 1__. Eve sends a copy of

`EncryptedServerTicket`

to Bob, obtained from Step 11 of the naïve Kerberos protocol.__ Step 2__. Bob, assuming Alice has initiated a new conversation, retireves

`SessionKey`

from `EncryptedServerTicket`

.__ Step 3__. Bob does not keep an exhaustive record of all the temporary keys he has used, and so he does not know whether

`SessionKey`

is new or not.__ Step 4__. Just to be sure, Bob sends the following message to Alice:

```
encrypt(message=Nonce(3), key=SessionKey)
```

__ Step 5__. Eve hijacks Bob’s message.

__ Step 6__. From

`HandshakeServerToClient`

in Step 16 of the naïve Kerberos protocol and `HandshakeClientToServer`

in Step 19 of the naïve Kerberos protocol, Eve knows `Nonce(3)-1`

is what Bob expects.__ Step 7__. Eve sends the following message to Bob:

```
encrypt(message=(Nonce(3)-1), key=SessionKey)
```

__ Step 8__. Bob is now convinced that he is communicating securely with Alice, when he is, in fact, giving away classified information to Eve.

__ Step 9__. Meanwhile, Alice is not aware of this incident, as Eve does not allow any of Bob’s message through.

The full Kerberos protocol mitigates the reply attack problem by including a **timestamp** to each ticket and having Bob reject stale tickets.

For more details on the timestamp approach, see “Timestamps in Key Distribution Protocols” by Denning and Sacco, and “A note on the use of timestamps as nonces” by Neuman and Stubblebine.

## 11. Authenticators

Generalizing the method of guarding against replay attacks with timestamps, we introduce the following definition, as per IETF RFC 4120 Section 1.7:

Authenticator

A record containing information that can be shown to have been recently generated using the session key known only by the client and server.

In other words, an authenticator exists to prevent replay attacks. Per IETF RFC 4120 Section 3.2:

The authenticator is used to prevent invalid replay of tickets by proving to the server that the client knows the session key of the ticket and thus is entitled to use the ticket. … Authenticators MUST NOT be re-used and SHOULD be rejected if replayed to a server. Note that this can make applications based on unreliable transports difficult to code correctly. If the transport might deliver duplicated messages, either a new authenticator MUST be generated for each retry, or the application server MUST match requests and replies and replay the first reply in response to a detected duplicate.

To this end, a server often keeps a **replay cache** of recently-seen authenticators to properly reject replayed authenticators. Moreover, a server may also carry a **keytab**, a list of secret keys that a server can tap into for evaluating authentications from clients.

## 12. A Few Human Problems

Even after the addition of timestamps, there are several defects of the Kerberos protocol, largely related to human errors.

First off, Kerberos cannot guard against the principals being careless about their keys. While stolen session keys can be made obsolete by the timestamp trick, stolen keys (as in the symmetric-key cryptography) cannot be reined in until new keys are issued and registered with the authentication server. Similarly, Kerberos is vulnerable to password guessing, as a principal’s key is its only identifier as far as the authentication server is concerned.

Secondly, the clocks of the two principals must not be too unsynchronized. Big gaps render the timestamp trick useless. (See, however, “Kerberos With Clocks Adrift: History, Protocols, and Implementation” by Davis, Geer, and Ts’o.)

Finally, Kerberos has no way of dealing with non-cryptographic matters, such as a denial-of-service attack sabotaging the authentication steps.

Please thank your local sysadmin for dealing with our human frailty.

## 13. Tickets: The Basics

Let us now return to the central object of interest in Kerberos: the **tickets**.

A ticket is issued by an authentication server to vouch for the client’s identity. Recall, for example, that we have considered the scenario with one ticket passed around in the naïve Kerberos protocol outlined in Section 9. In contrast, real-life implementations of Kerberos uses multiple tickets.

Let us first examine the official IETF RFC 4120 definition of a ticket:

Ticket

A record that helps a client authenticate itself to a server; it contains the client’s identity, a session key, a timestamp, and other information, all sealed using the server’s secret key. It only serves to authenticate a client when presented along with a fresh Authenticator.

The word to pay attention to is **help**:

A record that

helpsa client authenticate itself to a server …

This means that *all* messages that play a direct role in the authentication are tickets, beyond the final one sent to the server for verification.

Recall from our outline of the naïve Kerberos protocol in Section 9 that requesting a ticket containing a session key requires the client to prove its knowledge of the secret key by, say, entering a password. Since we prevent replay attacks by expiring tickets, having the client communicate with the authentication every time it needs new ticket amounts to entering the password every few minutes. This is, of course, unreasonable.

To circumvent the issue, we introduce another server **Ticket-Granting Server** (TGS) and another ticket **Ticket-Granting Ticket** (TGT).

The role of TGS is to provide the client with new tickets with session keys without asking for the client’s password. Instead, TGS merely asks the client to show its TGT, which has a longer lifespan than a ticket containing a session key.

Where, then, does the client obtain a TGT from? We know from our outline of the naïve Kerberos protocol in Section 9 that the authentication server, upon receiving the initial ticket request from the client, sends back a ticket containing a session key.

See the below diagram for a summary of the process:

**Key Distribution Center** (KDC) is the term encompassing both servers. Per IETF RFC 4120 Section 1.7:

KDC

Key Distribution Center. A network service that supplies tickets and temporary session keys; or an instance of that service or the host on which it runs. The KDC services both initial ticket and ticket-granting ticket requests. The initial ticket portion is sometimes referred to as the Authentication Server (or service). The ticket-granting ticket portion is sometimes referred to as the ticket-granting server (or service).

While TGTs can reduce the number of password checks, they do require the client to contact KDC every time authorization is required. We can complement them with **credentials caches**, which stores authentication information and thus eliminating the need for repeated queries to KDC. Credentials caches only contain tickets; no secret keys are included in a credentials cache.

## 14. Tickets: Special Cases

We now discuss a few special-case tickets. See IETF RFC 4120 Section 5.3 for the full list.

### 14.1. Renewable Tickets

The most straightforward application of TGTs is to add a renewal feature to tickets. A **renewable ticket** carries two expiration timestamps:

- The time at which the current instance of the ticket expires;
- The time after which no instance of the ticket is valid.

A client in possession of a renewable ticket must check in with KDC periodically to retrieve a new instance of the ticket with a later expiration date. This check-in process involves a TGT and thus does not require re-entering the client password.

Should the renewable ticket be stolen, KDC will refuse to honor it after the current instance’s expiration, minimizing the effects of theft.

### 14.2. Postdated Tickets

To schedule a job in the future that requires authentication, a client can request a **postdated ticket**. Such a ticket is considered invalid until the starting time listed on the ticket. At this point, the ticket can be presented to KDC for validation, after which KDC will issue valid tickets.

Should a postdated ticket be stolen, KDC will refuse to honor it, keeping the ticket at the invalid state forever.

### 14.3. Forwardable Tickets

KDC can issue new, valid tickets based on a **forwardable ticket**, which can be passed around without requiring the client’s secret key again. The TGTs we have discussed in Section 13, for example, are forwardable.

### 14.4. Proxiable and Proxy Tickets

A **proxiable ticket** allows a service to take on the identity of the client to whom the proxiable ticket was issued. Proxiable tickets are tied to specific services and cannot be forwarded to unauthorized services for the purpose of assuming the client’s identity.

Note that every forwardable ticket is proxiable, but not vice versa. In particular, TGTs cannot be issued based on a proxiable, but not forwardable, ticket.

Any ticket that is issued based on a proxiable ticket is called a **proxy ticket**.

## 15. Realms and Delegation

So far, we have operated under the assumption that one authentication server holds the authoritative information on all clients and servers. This, of course, is an unreasonable assumption for all but the smallest organizations.

To discuss matters of distributed authentication, we introduce the notion of a **realm**, the subset of the principals (clients and servers) registered with one authentication server. Typically, a principal belongs to multiple, but not all, realms.

Suppose a client `Client`

belongs to `RealmOne`

but not `RealmTwo`

. In order for `Client`

to be authenticated in `RealmTwo`

, `Client`

must obtain a TGT that is valid within `RealmTwo`

from `RealmOne`

. FOr this to be possible, the authentication servers in `RealmOne`

and `RealmTwo`

must be able to communicate with each other.

A brute-force solution would be to simply register each authentication server with all the other authentication servers. This can become untenable, as establishing $n$ requires $n(n-1) = \Omega(n^2)$ registrations.

Instead, Kerberos supports **multi-hop authentication**, which allows traversing nodes of authentication servers until we reach the correct realm. Afterwards, the authentication information is transferred back to the realm in question.

For the sake of concreteness, we suppose that the following sequence of hops is necessary for `Client`

to be authenticated in `RealmTwo`

:

$\mathrm{Client} \Rightarrow \mathrm{RealmTwo} \Rightarrow \mathrm{RealmThree} \Rightarrow \mathrm{RealmOne}$

In order for the `RealmTwo`

authentication server to contact the `RealmThree`

authentication server on behalf of `Client`

, a **delegation** must happen using `Client`

’s credentials.

Most real-world implementations of Kerberos disables delegation by default. System administrators must enable and configure it manually, as it should be allowed only on trustworthy servers.

Take a look at the Google search results for “double hop problem” to witness pure agony.

## 16. Using Kerberos

To wrap up, let us take a quick look at the reference MIT implementation of Kerberos version 5.

Command-line tool `kinit`

sends an authentication request to the key distribution center. As end users, we often use `kinit -f`

to request forwardable tickets to reduce the frequency of authentication requests needed.

Command-line tool `klist`

lists the tickets currently on the machine. `klist -f`

shows the flags of each ticket.

Here is an example `klist -f`

output, immediately following `kinit -f`

:

```
Ticket cache: FILE:/tmp/krb5cc_IDENTIFIER_STRING
Default principal: markkm@DOMAIN.NAME
Valid starting Expires Service principal
05/13/2019 23:59:42 05/14/2019 09:59:42
krbtgt/DOMAIN.NAME@DOMAIN.NAME
renew until 05/14/2019 23:59:40, Flags: FRIA
```

Flag `I`

indicates that the above ticket is the initial ticket. Indeed, the name `krbtgt`

indicates that the ticket is a ticket-granting ticket (TGT).

After visiting an endpoint that requires authentication, `klist -f`

now shows tickets issues by the said endpoint:

```
Ticket cache: FILE:/tmp/krb5cc_IDENTIFIER_STRING
Default principal: markkm@DOMAIN.NAME
Valid starting Expires Service principal
05/13/2019 23:59:42 05/14/2019 09:59:42
krbtgt/DOMAIN.NAME@DOMAIN.NAME
renew until 05/14/2019 23:59:40, Flags: FRIA
05/14/2019 00:01:09 05/14/2019 09:59:42 HTTP/ANOTHER.DOMAIN.NAME@
renew until 05/14/2019 23:59:40, Flags: FRA
05/14/2019 00:01:09 05/14/2019 09:59:42 HTTP/ANOTHER.DOMAIN.NAME@DOMAIN.NAME
renew until 05/14/2019 23:59:40, Flags: FRA
```

`kdestroy`

deletes all tickets on the machine. See the output of `klist -f`

after `kdestroy`

:

```
klist: No credentials cache found (filename: /tmp/krb5cc_IDENTIFIER_STRING)
```

The Kerberos configurations are stored in `krb5.conf`

, which lists the default realm, the default encryption schemes, and so on. On a POSIX system, the configuration file is typically located at `/etc/krb5.conf`

.

The keytab is stored in `krb5.keytab`

, a binary file. On a POSIX system, the keytab binary is typically located at `/etc/krb5.keytab`

.

Credentials caches are stored as binary in a temporary directory. On a POSIX system, the binary file is typically located at `/tmp/krb5cc_IDENTIFIER_STRING`

.

On a typical terminal on a POSIX system, environment variable `KRB5CCNAME`

contains the full path for the credential caches binary.

## 17. A Brief History

Kerberos was developed as part of Project Athena for building a campus-wide networking environment for educational use at MIT. Versions 1 through 3 were used internally at MIT. Version 4 was developed in 1985 - 1986 and was released to the public as IETF RFC 1510 in 1993. Version 5, the current version in use, was released in 2005 as IEFT RFC 4120.