The Needham–Schroeder protocol lets two parties A and B, who each share a secret key with a trusted Key Distribution Centre (KDC), obtain a fresh session key and confirm that the other holds it.
Symmetric-key version (\(K_a\), \(K_b\): keys A and B share with the KDC; \(K_s\): session key; \(N_1, N_2\): nonces):
- A → KDC: \(ID_A \,\|\, ID_B \,\|\, N_1\)
A asks for a key to talk to B; the nonce \(N_1\) guards against replays. - KDC → A: \(E(K_a, [K_s \| ID_B \| N_1 \| E(K_b, [K_s \| ID_A])])\)
Only A can read it. A checks \(N_1\) and \(ID_B\), learns \(K_s\), and gets a "ticket" for B. - A → B: \(E(K_b, [K_s \| ID_A])\)
B decrypts the ticket and learns \(K_s\) and that it is talking to A. - B → A: \(E(K_s, N_2)\)
B challenges A to prove it has \(K_s\). - A → B: \(E(K_s, f(N_2))\), e.g. \(f(N_2) = N_2 - 1\)
A proves knowledge of \(K_s\); the transformation stops a simple replay of message 4.
Weakness (Denning–Sacco attack). Message 3 contains no freshness information. If an attacker learns an old session key \(K_s\), it can replay the old message 3 to B, then answer B's challenge in steps 4–5 and impersonate A. Fix: add timestamps (Denning's modification: \(E(K_b, [K_s \| ID_A \| T])\)) or nonces from B; Kerberos is based on this improved idea.
Public-key version (briefly): A and B exchange nonces encrypted with each other's public keys: A → B: \(\{N_a, A\}_{PU_b}\); B → A: \(\{N_a, N_b\}_{PU_a}\); A → B: \(\{N_b\}_{PU_b}\). Lowe (1995) showed a man-in-the-middle attack; the fix is to include B's identity in the second message: \(\{N_a, N_b, B\}_{PU_a}\) (the Needham–Schroeder–Lowe protocol).
Uses: it is the foundation of ticket-based authentication systems such as Kerberos.