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:

  1. Notes to the Reader; A Table of Contents
  2. One-Way Functions
  3. Pseudorandom Generators
  4. Case Study: The One-Time Pad
  5. Symmetric-Key Cryptography
  6. Public-Key Cryptography
  7. Authentication
  8. Centralized Authentication: the Needham–Schroeder protocol
  9. An Overview of the Kerberos Protocol
  10. Replay Attacks
  11. Authenticators
  12. A Few Human Problems
  13. Tickets: The Basics
  14. Tickets: Special Cases
  15. Realms and Delegation
  16. Using Kerberos
  17. 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:

  1. The keys must be random and known only to the principals, the two main communicators exchanging encrypted information.
  2. Both principals must have the same key prior to initiating encrypted communication.
  3. 1 and 2 combined lead to the problem of secure key exchange, the most significant defect of symmetric-key cryptography.
  4. The keys are often small and can be generated with low computational cost.
  5. 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

  1. a message remains unmodified during transmission (data integrity), and that
  2. 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:

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:

a sketch of the kerberos protocol

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:

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:

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 helps a 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:

a sketch of the kerberos ticket exchange

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:

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.