Needham-Schroeder and Kerberos

Needham-Schroeder distributes a key through an Authentication Server

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.

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.

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 messages 1–3: distribute the session key

$$\begin{aligned} A \to AS&: ID_A \Vert ID_B \Vert N_1 \\ 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]) \\ A \to B&: E(K_b, [K_s \Vert ID_A]) \end{aligned}$$

$ID_A, ID_B$

identifiers of A and B

$N_1$

a nonce identifying this session, chosen by 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

$E(K_b, [K_s \Vert ID_A])$

the ticket A relays to B unopened, exactly as received

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.

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:

The final two messages prove live possession of the session key

Formula

Needham-Schroeder messages 4–5: prove possession

$$\begin{aligned} B \to A&: E(K_s, N_2) \\ A \to B&: E(K_s, f(N_2)) \end{aligned}$$

$N_2$

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

$f(N_2)$

a generic transformation of N_2, proving A holds K_s and answered this specific challenge

Kerberos separates authentication from ticket granting

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.

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.

The AS gives the client a ticket-granting ticket

Formula

Kerberos exchanges 1–2: obtain a ticket-granting ticket

$$\begin{aligned} C \to AS&: ID_c \Vert ID_{tgs} \Vert TS_1 \\ AS \to C&: E(K_c, [K_{c,tgs} \Vert ID_{tgs} \Vert TS_2 \Vert \text{Lifetime}_2 \Vert \text{Ticket}_{tgs}]) \end{aligned}$$

$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

$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

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.

The TGS supplies a service ticket without asking for the password

Formula

Kerberos exchanges 3–6: obtain and use a service ticket

$$\begin{aligned} C \to TGS&: ID_v \Vert \text{Ticket}_{tgs} \Vert \text{Authenticator}_c \\ TGS \to C&: E(K_{c,tgs}, [K_{c,v} \Vert ID_v \Vert TS_4 \Vert \text{Ticket}_v]) \\ C \to S_v&: \text{Ticket}_v \Vert \text{Authenticator}_c \\ S_v \to C&: E(K_{c,v}, [TS_5 + 1]) \end{aligned}$$

$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

$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

$\text{Ticket}_v$

assures server V this user was authenticated by the AS

$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

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

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.”

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.

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.