Kerberos Book Chapter

One-way authenticationSearch on YouTubeBookmarkSaved

Email needs one-way authentication. The recipient is not always online at the same time as the sender. Thus the sender cannot wait for a reply that carries a session key.

The KDC scheme can work for encrypted email. Remove steps 4 and 5 of the interactive scheme. For a message $M$, the sequence is:

1. $A \rightarrow KDC$: $ID_A \Vert ID_B \Vert N_1$
2. $KDC \rightarrow A$: $E(K_a, [K_s \Vert ID_B \Vert N_1 \Vert E(K_b, [K_s \Vert ID_A])])$
3. $A \rightarrow B$: $E(K_b, [K_s \Vert ID_A]) \Vert E(K_s, M)$

Only the intended recipient can read the message. B also gets some proof that A is the sender.

Kerberos overviewSearch on YouTubeBookmarkSaved

Kerberos is an authentication service from Project Athena at MIT. It gives a centralized authentication server. This server authenticates users to servers and servers to users.

Three threatsSearch on YouTubeBookmarkSaved

Users at workstations want to use services on servers across the network. Servers must restrict access to authorized users. A workstation cannot be trusted to identify its users correctly. Three threats exist:

1. A user gets access to a workstation and pretends to be another user of that workstation.
2. A user changes the network address of a workstation. Then the requests appear to come from the impersonated workstation.
3. A user eavesdrops on exchanges and uses a replay attack to get into a server or to disrupt operations.

Kerberos uses only symmetric encryption. It does not use public-key encryption.

VersionsSearch on YouTubeBookmarkSaved

• Versions 1 to 3 were internal development versions.
• Version 4 is the "original" Kerberos. Some version 4 implementations still exist.
• Version 5 corrects some security deficiencies of version 4. It is a proposed Internet Standard (RFC 4120 and RFC 4121).

MotivationSearch on YouTubeBookmarkSaved

Most systems today use dedicated user workstations (clients) and distributed or centralized servers. Three approaches to security are possible:

1. Each client workstation makes sure of the identity of its users. Each server enforces a policy based on the user ID.
2. Client systems authenticate themselves to servers. Servers trust the client system for the identity of its user.
3. The user proves its identity for each service. Servers also prove their identity to clients.

A small, closed environment can use approach 1 or 2. An open environment needs approach 3. Kerberos supports approach 3.

RequirementsSearch on YouTubeBookmarkSaved

The first published report on Kerberos lists four requirements:

Kerberos is a trusted third-party authentication service. Its protocol is based on the Needham-Schroeder protocol. Clients and servers trust Kerberos to mediate their mutual authentication.

Kerberos version 4Search on YouTubeBookmarkSaved

Version 4 uses DES. The chapter builds the full protocol in steps. Each new dialogue removes a weakness of the previous dialogue.

Simple dialogueSearch on YouTubeBookmarkSaved

An opponent can pretend to be another client. Thus servers must confirm the identity of clients. If each server does this work, the load on each server is large.

An authentication server (AS) does this work. The AS knows the passwords of all users. It shares a unique secret key with each server.

1. $C \rightarrow AS$: $ID_C \Vert P_C \Vert ID_V$
2. $AS \rightarrow C$: $Ticket$
3. $C \rightarrow V$: $ID_C \Vert Ticket$

$Ticket = E(K_v,[ID_C \Vert AD_C \Vert ID_V])$

The AS checks the password and the access right of the user. Then it creates the ticket. V decrypts the ticket. V checks that the user ID in the ticket is the same as the user ID in the message.

Each part of message 3 has a purpose:

• The ticket is encrypted. Thus C or an opponent cannot change or forge it.
• $ID_V$ in the ticket lets V confirm that it decrypted the ticket correctly.
• $ID_C$ in the ticket shows that the AS issued the ticket for C.
• $AD_C$ stops a replay from another workstation. Without it, an opponent can capture the ticket and send message 3 from a different workstation.

Adding the TGSSearch on YouTubeBookmarkSaved

Two problems remain:

1. Each new service needs a new ticket. Thus the user must enter the password again for each service.
2. Message 1 sends the password in plaintext. An eavesdropper can capture it.

The solution is a ticket-granting server (TGS) and no plaintext password.

Once per user logon session:

1. $C \rightarrow AS$: $ID_C \Vert ID_{tgs}$
2. $AS \rightarrow C$: $E(K_c, Ticket_{tgs})$

Once per type of service:

3. $C \rightarrow TGS$: $ID_C \Vert ID_V \Vert Ticket_{tgs}$
4. $TGS \rightarrow C$: $Ticket_v$

Once per service session:

5. $C \rightarrow V$: $ID_C \Vert Ticket_v$

$Ticket_{tgs} = E(K_{tgs},[ID_C \Vert AD_C \Vert ID_{tgs} \Vert TS_1 \Vert Lifetime_1])$

$Ticket_v = E(K_v,[ID_C \Vert AD_C \Vert ID_v \Vert TS_2 \Vert Lifetime_2])$

The steps:

1. The client asks the AS for a ticket-granting ticket. It sends the user ID and the TGS ID.
2. The AS encrypts the ticket with $K_c$, a key from the user's password. The client asks for the password and decrypts the reply.
3. The client sends the user ID, the service ID and $Ticket_{tgs}$ to the TGS.
4. The TGS decrypts the ticket with $K_{tgs}$. It checks its own ID, the lifetime, the user ID and the address. Then it issues $Ticket_v$.
5. The client sends the user ID and $Ticket_v$ to the server.

Full V4 dialogueSearch on YouTubeBookmarkSaved

Two more problems remain:

1. Ticket lifetime. A short lifetime makes the user enter the password many times. A long lifetime gives an opponent more time to replay a captured ticket. A service must prove that the person who uses a ticket is the person who received it.
2. Server authentication. Servers must also authenticate themselves to users. If not, a false server can capture user data and deny the true service.

The solution is a session key and an authenticator.

(a) Authentication service exchange:

1. $C \rightarrow AS$: $ID_c \Vert ID_{tgs} \Vert TS_1$
2. $AS \rightarrow C$: $E(K_c, [K_{c,tgs} \Vert ID_{tgs} \Vert TS_2 \Vert Lifetime_2 \Vert Ticket_{tgs}])$

$Ticket_{tgs} = E(K_{tgs},[K_{c,tgs} \Vert ID_C \Vert AD_C \Vert ID_{tgs} \Vert TS_2 \Vert Lifetime_2])$

(b) Ticket-granting service exchange:

3. $C \rightarrow TGS$: $ID_v \Vert Ticket_{tgs} \Vert Authenticator_c$
4. $TGS \rightarrow C$: $E(K_{c,tgs}, [K_{c,v} \Vert ID_v \Vert TS_4 \Vert Ticket_v])$

$Ticket_v = E(K_v,[K_{c,v} \Vert ID_C \Vert AD_C \Vert ID_v \Vert TS_4 \Vert Lifetime_4])$

$Authenticator_c = E(K_{c,tgs},[ID_C \Vert AD_C \Vert TS_3])$

(c) Client/server authentication exchange:

5. $C \rightarrow V$: $Ticket_v \Vert Authenticator_c$
6. $V \rightarrow C$: $E(K_{c,v}, [TS_5 + 1])$, for mutual authentication

Here the authenticator is $E(K_{c,v},[ID_C \Vert AD_C \Vert TS_5])$.

Ticket and authenticatorSearch on YouTubeBookmarkSaved

How the parts work:

• The timestamp in message 1 tells the AS that the message is timely.
• Message 2 gives C a readable copy of some ticket fields. Thus C can confirm that the ticket is for the TGS. C also learns the expiry time.
• $K_{c,tgs}$ is in message 2 (encrypted with $K_c$) and in the ticket (encrypted with $K_{tgs}$). Thus C and the TGS both get it securely.
• The ticket says: "Anyone who uses $K_{c,tgs}$ must be C." The authenticator says: "At time $TS_3$, I use $K_{c,tgs}$."
• The TGS gets $K_{c,tgs}$ from the ticket and decrypts the authenticator. It compares the name and address with the ticket and with the source of the message.
• Message 4 has the same form as message 2. It gives C the session key $K_{c,v}$ for server V.
• In message 6, V returns $TS_5 + 1$ encrypted with $K_{c,v}$. Only V can make this message. The plus-one shows that it is not a replay of an old reply.

At the end, the client and the server share a secret key. They can use it to encrypt messages or to exchange a new session key.

Kerberos realmsSearch on YouTubeBookmarkSaved

Realm and principalSearch on YouTubeBookmarkSaved

A full-service Kerberos environment has these requirements:

1. The Kerberos server has the user IDs and hashed passwords of all users. All users are registered with it.
2. The Kerberos server shares a secret key with each server. All servers are registered with it.

Such an environment is a Kerberos realm:

• A realm is a set of managed nodes that share the same Kerberos database.
• The database is on the Kerberos master system. Keep this system in a physically secure room.
• Other Kerberos systems can have read-only copies. Make all changes on the master system.
• A change to the database needs the Kerberos master password.
• A principal is a user or service that Kerberos knows. A principal name has three parts: user or service name, instance name and realm name.

Different administrative organizations usually make different realms.

Interrealm authenticationSearch on YouTubeBookmarkSaved

Interrealm authentication adds a third requirement. The Kerberos server in each realm shares a secret key with the server in the other realm. Each realm trusts the other realm to authenticate its users.

1. $C \rightarrow AS$: $ID_c \Vert ID_{tgs} \Vert TS_1$
2. $AS \rightarrow C$: $E(K_c, [K_{c,tgs} \Vert ID_{tgs} \Vert TS_2 \Vert Lifetime_2 \Vert Ticket_{tgs}])$
3. $C \rightarrow TGS$: $ID_{tgsrem} \Vert Ticket_{tgs} \Vert Authenticator_c$
4. $TGS \rightarrow C$: $E(K_{c,tgs}, [K_{c,tgsrem} \Vert ID_{tgsrem} \Vert TS_4 \Vert Ticket_{tgsrem}])$
5. $C \rightarrow TGS_{rem}$: $ID_{vrem} \Vert Ticket_{tgsrem} \Vert Authenticator_c$
6. $TGS_{rem} \rightarrow C$: $E(K_{c,tgsrem}, [K_{c,vrem} \Vert ID_{vrem} \Vert TS_6 \Vert Ticket_{vrem}])$
7. $C \rightarrow V_{rem}$: $Ticket_{vrem} \Vert Authenticator_c$

The ticket for the remote server shows the realm where the user was first authenticated. The remote server decides if it accepts the request.

Kerberos version 5Search on YouTubeBookmarkSaved

Version 5 is in RFC 4120. It corrects environmental shortcomings and technical deficiencies of version 4.

Environmental shortcomingsSearch on YouTubeBookmarkSaved

Technical deficienciesSearch on YouTubeBookmarkSaved

1. Double encryption. V4 encrypts tickets twice: with the server key, then with the client key. The second encryption is not necessary and wastes computation.
2. PCBC encryption. V4 uses propagating cipher block chaining, a nonstandard DES mode. An attack that swaps ciphertext blocks works against it. V5 attaches a checksum or hash, then uses standard CBC.
3. Session keys. A ticket can be used many times with the same session key. An opponent can replay messages from an old session. V5 lets client and server agree a subsession key for one connection only.
4. Password attacks. In both versions, the AS reply is encrypted with a key from the password. An opponent can try many passwords on it. V5 preauthentication makes this harder, but it does not prevent it.

V5 dialogueSearch on YouTubeBookmarkSaved

(a) Authentication service exchange:

1. $C \rightarrow AS$: $Options \Vert ID_c \Vert Realm_c \Vert ID_{tgs} \Vert Times \Vert Nonce_1$
2. $AS \rightarrow C$: $Realm_C \Vert ID_C \Vert Ticket_{tgs} \Vert E(K_c, [K_{c,tgs} \Vert Times \Vert Nonce_1 \Vert Realm_{tgs} \Vert ID_{tgs}])$

$Ticket_{tgs} = E(K_{tgs}, [Flags \Vert K_{c,tgs} \Vert Realm_c \Vert ID_C \Vert AD_C \Vert Times])$

(b) Ticket-granting service exchange:

3. $C \rightarrow TGS$: $Options \Vert ID_v \Vert Times \Vert Nonce_2 \Vert Ticket_{tgs} \Vert Authenticator_c$
4. $TGS \rightarrow C$: $Realm_c \Vert ID_C \Vert Ticket_v \Vert E(K_{c,tgs}, [K_{c,v} \Vert Times \Vert Nonce_2 \Vert Realm_v \Vert ID_v])$

$Ticket_v = E(K_v, [Flags \Vert K_{c,v} \Vert Realm_c \Vert ID_C \Vert AD_C \Vert Times])$

$Authenticator_c = E(K_{c,tgs}, [ID_C \Vert Realm_c \Vert TS_1])$

(c) Client/server authentication exchange:

5. $C \rightarrow V$: $Options \Vert Ticket_v \Vert Authenticator_c$
6. $V \rightarrow C$: $E(K_{c,v}, [TS_2 \Vert Subkey \Vert Seq\#])$

Here the authenticator is $E(K_{c,v}, [ID_C \Vert Realm_c \Vert TS_2 \Vert Subkey \Vert Seq\#])$.

New fields in message 1:

• Realm: the realm of the user.
• Options: requests flags in the returned ticket.
• Times: from (start time), till (expiry time) and rtime (renew-till time).
• Nonce: a random value. Message 2 repeats it, to show that the reply is fresh.

New fields in the authenticator of message 5:

• Subkey: the key that the client selects for this application session. If it is absent, the session key $K_{c,v}$ is used.
• Sequence number: an optional start number for the messages from the server. Sequence numbers help to detect replays.

Message 6 returns the timestamp without the plus-one. An opponent cannot create message 6 without the keys. A subkey in message 6 overrides the subkey in message 5.

Ticket flagsSearch on YouTubeBookmarkSaved

Uses of the flags:

• INITIAL: a password-changing server can know that the client recently gave its password.
• PRE-AUTHENT: the MIT implementation sends a block with a random confounder, a version number and a timestamp. The client encrypts the block with its password key. The AS refuses if the timestamp is outside the allowed time skew.
• HW-AUTHENT: shows that a smart card or a similar device was used.
• RENEWABLE: the ticket has two expiry times. The TGS can renew it up to the latest time. The TGS can refuse to renew a stolen ticket.
• MAY-POSTDATE: helps a long batch job. The client gets many tickets at once. All tickets after the first are INVALID until the client has them validated.
• PROXIABLE: lets a server act as a proxy for the client. The new ticket has the PROXY flag.
• FORWARDABLE: the forwarded ticket can go to a remote TGS. Realms can be a hierarchy. A client goes up the tree to a common node, then down to the target realm. Thus each Kerberos server does not need a key with every other realm.

Public-key remote authenticationSearch on YouTubeBookmarkSaved

The chapter ends with remote user authentication that uses asymmetric encryption.

Timestamp protocolSearch on YouTubeBookmarkSaved

This protocol is from Denning [DENN81]:

1. $A \rightarrow AS$: $ID_A \Vert ID_B$
2. $AS \rightarrow A$: $E(PR_{as}, [ID_A \Vert PU_a \Vert T]) \Vert E(PR_{as}, [ID_B \Vert PU_b \Vert T])$
3. $A \rightarrow B$: $E(PR_{as}, [ID_A \Vert PU_a \Vert T]) \Vert E(PR_{as}, [ID_B \Vert PU_b \Vert T]) \Vert E(PU_b, E(PR_a, [K_s \Vert T]))$

The AS gives only public-key certificates. A selects and encrypts the session key, so the AS cannot expose it. Timestamps protect against replays. The protocol is compact, but it needs synchronized clocks.

Woo-Lam protocolSearch on YouTubeBookmarkSaved

Woo and Lam use nonces in place of timestamps:

1. $A \rightarrow KDC$: $ID_A \Vert ID_B$
2. $KDC \rightarrow A$: $E(PR_{auth}, [ID_B \Vert PU_b])$
3. $A \rightarrow B$: $E(PU_b, [N_a \Vert ID_A])$
4. $B \rightarrow KDC$: $ID_A \Vert ID_B \Vert E(PU_{auth}, N_a)$
5. $KDC \rightarrow B$: $E(PR_{auth}, [ID_A \Vert PU_a]) \Vert E(PU_b, E(PR_{auth}, [N_a \Vert K_s \Vert ID_B]))$

Quick self-testSearch on YouTubeBookmarkSaved

Why does one-way email authentication remove steps 4 and 5 of the KDC scheme?

The recipient is not always online. Thus A cannot wait for a reply. A sends $E(K_b, [K_s \Vert ID_A])$ with the message, and B recovers $K_s$ later.

Give the three threats that Kerberos addresses and its four requirements.

Threats: a false user on a workstation, a changed workstation address, and eavesdropping with replay. Requirements: secure, reliable, transparent and scalable.

Why does the ticket contain $AD_C$?

$AD_C$ stops the use of a captured ticket from another workstation. The ticket is valid only from the workstation that requested it.

What is the difference between the ticket and the authenticator in V4?

The ticket is reusable and distributes the session key securely. The authenticator is encrypted with the session key, is used once and has a very short lifetime. It proves the identity of the client.

How does message 6 of V4 give mutual authentication?

V returns $TS_5 + 1$ encrypted with $K_{c,v}$. Only V can make this message. The plus-one shows that it is not a replay.

What is a Kerberos realm, and what is the V4 cost of interrealm authentication?

A realm is a set of managed nodes that share one Kerberos database. N realms need $N(N-1)/2$ secure key exchanges.

Give the four technical deficiencies of V4 and the V5 solution for each.

Double encryption: removed. PCBC: replaced by CBC with a checksum. Reused session keys: replaced by subsession keys. Password attacks: made harder by preauthentication.

What does the nonce in V5 message 1 do?

Message 2 repeats the nonce. This shows that the reply is fresh and that an opponent did not replay it.

In the Woo-Lam protocol, what does B send to the KDC in step 4?

$ID_A \Vert ID_B \Vert E(PU_{auth}, N_a)$. The nonce is encrypted with the public key of the KDC.