The Needham-Schroeder Protocol and Attacks
Revisit the 1978 NS protocol and Lowe's 1995 man-in-the-middle attack that reshaped how we think about authentication.
Origins and Goals of NS Protocol
The Needham-Schroeder protocol (1978) was one of the first formal attempts to design a cryptographic authentication protocol using a trusted third party (TTP). The goal: allow two parties, Alice and Bob, to authenticate each other and establish a shared session key using a trusted Authentication Server (AS) that shares long-term keys with each principal. The protocol predates public key infrastructure but introduced concepts — nonces for freshness, key distribution via a trusted server — that remain central to modern protocols like Kerberos. Understanding NS and its failures shaped the entire field of protocol analysis.
Needham-Schroeder Symmetric Key Protocol
The NS symmetric key protocol proceeds in five steps. (1) Alice sends {A, B, Na} to the AS, requesting a session key for communication with Bob. (2) The AS responds to Alice with {Na, B, Kab, {Kab, A}_Kb}_Ka — a session key Kab, a ticket for Bob, all encrypted under Alice's long-term key Ka. (3) Alice forwards the ticket {Kab, A}_Kb to Bob. (4) Bob decrypts the ticket, extracts Kab, and sends {Nb}_Kab to Alice (a challenge). (5) Alice responds {Nb-1}_Kab proving she holds Kab. The nonce Nb prevents replay of step 4. This protocol has a known replay attack exploited by Denning and Sacco (1981).
All lessons in this course
- The Needham-Schroeder Protocol and Attacks
- Station-to-Station Protocol (STS)
- The Noise Protocol Framework
- Principles of Secure Protocol Design