Needham-Schroeder and Kerberos

The five-message Needham-Schroeder protocol for building a KDC, and how Kerberos hardens it into a deployed, ticket-based authentication service with an Authentication Server and a Ticket-Granting Server.

Reproduce all five Needham-Schroeder messages in order, with every field named.
Explain what the ticket-granting ticket solves and why the TGS exists as a separate server from the AS.
Reproduce all six Kerberos exchanges in order, with every field named.
State how Kerberos hardens Needham-Schroeder and what a ticket's lifetime is enforced by.

22 min read

Intuition

The key distribution scenario from earlier this week moved a session key from a KDC to two users. Needham- Schroeder formalises exactly that idea with an Authentication Server, and Kerberos is what that idea looks like once it is hardened and actually deployed: the basis for authentication on Windows, Linux, UNIX, macOS and more.

Mechanism

The Needham-Schroeder protocol’s basic idea is an intermediary Authentication Server (AS) that helps two users establish a session key over an insecure network. Several variants exist; the one covered here uses symmetric keys, and is, in effect, a way of building a KDC.

Formula

Needham-Schroeder message 1: initiate

A \to AS: ID_A \Vert ID_B \Vert N_1

$ID_A, ID_B$: identifiers of A and B
$N_1$: a nonce identifying this session, chosen by A

Mechanism

The nonce $N_1$ identifies this specific session. The AS now generates a fresh session key and replies with two payloads bundled into one message:

Formula

Needham-Schroeder message 2: AS response

AS \to A: E(K_a, [K_s \Vert ID_A \Vert ID_B \Vert N_1]) \Vert E(K_b, [K_s \Vert ID_A])

$K_s$: the fresh session key the AS generates for this exchange
$K_a, K_b$: the long-term master keys A and B each share with the AS

The first block, readable only by A, returns A's own request including N_1, letting A confirm freshness. The second block is the ticket for B, which A cannot read.

Formula

Needham-Schroeder message 3: forward the ticket

A \to B: E(K_b, [K_s \Vert ID_A])

$E(K_b, [K_s \Vert ID_A])$: the ticket A relays to B unopened, exactly as received

Mechanism

A relays this payload without being able to read it, exactly as in the earlier key distribution scenario. B decrypts it with $K_b$ and learns $K_s$ , learns the other party is A (from $ID_A$ ), and knows this came from the AS, because only the AS and B share $K_b$ . That distributes the key. Two further messages add proof of live participation:

Formula

Needham-Schroeder message 4: B's challenge

B \to A: E(K_s, N_2)

$N_2$: a fresh nonce B generates, proving A's reply is current

Formula

Needham-Schroeder message 5: A's response

A \to B: E(K_s, f(N_2))

$f(N_2)$: a generic transformation of N_2, proving A holds K_s and answered this specific challenge

EXTRACTION DEFECT: Figures 19 (the basic idea of Needham-Schroeder) and 20 (the full protocol diagram) did not survive extraction. All five messages are reproduced above from the notes’ own restated text, in full and with every field named.

Exam detail

Needham-Schroeder’s five messages split into two jobs: messages 1–3 distribute the key, messages 4–5 authenticate that A is actually present and holds it. This mirrors the earlier KDC scenario exactly, which is what the slides mean by calling that scenario “also called the Needham-Schroeder Protocol.”

Mechanism

Kerberos is a widely deployed protocol for authentication and access control, built on Needham-Schroeder. Rather than implementing authentication separately on every server, it centralises the job in an Authentication Server. Kerberos hardens Needham-Schroeder with a ticket concept: users authenticate with a password once, then request access to individual servers using tickets, each given a lifetime enforced by timestamps, after which reauthentication is required. It is based on Needham-Schroeder with more advanced features, timestamps and, notably, separating the authentication function from the ticket-granting function, and can federate authentication across several administrative domains.

Mechanism

The problem Kerberos solves beyond plain Needham-Schroeder: a stolen ticket, captured before it expires, should still be useless. The fix is that the Authentication Server securely gives both the client and the Ticket-Granting Server (TGS) a shared piece of secret information, in practice a session key. The client then proves its identity to the TGS by revealing knowledge of that secret, without exposing it directly, using an authenticator. A thief holding only the ticket, without also holding this secret, cannot use it.

EXTRACTION DEFECT: Figure 21 (a Kerberos overview) and Figure 22 (the diagram of the Kerberos exchanges among the parties) did not survive extraction. The notes restate every message in full text, reproduced in order below.

Formula

Kerberos exchange 1: client requests a ticket-granting ticket

C \to AS: ID_c \Vert ID_{tgs} \Vert TS_1

$ID_c$: the client's identity
$ID_{tgs}$: tells the AS the user requests access to the TGS
$TS_1$: lets the AS verify the client's clock is synchronised with its own

Formula

Kerberos exchange 2: AS returns the ticket-granting ticket

AS \to C: E(K_c, [K_{c,tgs} \Vert ID_{tgs} \Vert TS_2 \Vert \text{Lifetime}_2 \Vert \text{Ticket}_{tgs}])

$K_c$: a key derived from the user's password, letting the AS and client verify the password and protecting the message
$K_{c,tgs}$: a session key the AS creates so the client and TGS can talk without a permanent shared key
$ID_{tgs}$: confirms this ticket is for the TGS
$TS_2, \text{Lifetime}_2$: when this ticket was issued, and how long it remains valid
$\text{Ticket}_{tgs}$: the ticket-granting ticket itself

Mechanism

The client now holds a ticket-granting ticket, valid for its stated lifetime, and never has to touch the password again until it expires. Every further service request goes through the TGS instead.

Formula

Kerberos exchange 3: client requests a service-granting ticket

C \to TGS: ID_v \Vert \text{Ticket}_{tgs} \Vert \text{Authenticator}_c

$ID_v$: tells the TGS the user requests access to server V
$\text{Ticket}_{tgs}$: assures the TGS this user was already authenticated by the AS
$\text{Authenticator}_c$: generated by the client to let the TGS validate the ticket

Formula

Kerberos exchange 4: TGS returns the service-granting ticket

TGS \to C: E(K_{c,tgs}, [K_{c,v} \Vert ID_v \Vert TS_4 \Vert \text{Ticket}_v])

$K_{c,tgs}$: the key shared only by client and TGS, protecting this message
$K_{c,v}$: the session key for the client and server V
$ID_v$: confirms this ticket is for server V
$\text{Ticket}_v$: the ticket used to access server V

TS_4 is not separately glossed in the notes; by the pattern TS_2 sets, it records when this ticket was issued.

Formula

Kerberos exchange 5: client requests service

C \to S_v: \text{Ticket}_v \Vert \text{Authenticator}_c

$\text{Ticket}_v$: assures server V this user was authenticated by the AS

Formula

Kerberos exchange 6: optional server authentication

S_v \to C: E(K_{c,v}, [TS_5 + 1])

$K_{c,v}$: assures the client this reply genuinely came from V
$TS_5 + 1$: assures the client this is not a replay of an earlier reply

Exam detail

Six numbered exchanges, but they answer three separate questions: exchanges 1–2 authenticate the client to the AS and hand back a ticket-granting ticket; exchanges 3–4 use that ticket to get a service-granting ticket for one specific server, without the password; exchanges 5–6 use the service-granting ticket to actually reach that server, with exchange 6 as an optional step proving the server itself is genuine. State which pair of exchanges a question is asking about before answering what each field does.

Aside

Every ticket ( $\text{Ticket}_{tgs}$ , $\text{Ticket}_v$ ) is itself built the same way as the Needham-Schroeder ticket earlier on this page: a session key and an identity, encrypted under a key the requester cannot read, to be carried unopened to whoever can. Kerberos layers timestamps, lifetimes and a second server (the TGS) on top of that same core idea, rather than replacing it.

Recall

Needham-Schroeder: messages 1–3 distribute a session key via the AS; messages 4–5 prove A is actively present.
Kerberos centralises authentication in an AS, adds ticket lifetimes enforced by timestamps, and separates authentication (AS) from ticket-granting (TGS).
A ticket alone is not enough to impersonate its owner: the accompanying session key and authenticator are what actually prove the presenter is who the ticket says.
The six Kerberos exchanges: 1–2 get a ticket-granting ticket, 3–4 exchange it for a service-granting ticket, 5–6 use that ticket to reach and, optionally, verify the target server.

Source

Week 7 Notes PDF