Needham–Schroeder protocol

The term Needham-Schroeder protocol can refer to one of two communication protocols intended for use over an insecure network, both proposed by Roger Needham and Michael Schroeder in a paper in 1978. These are:

• The Needham-Schroeder Symmetric Key Protocol, which is based on a symmetric encryption algorithm, and forms the basis for the Kerberos protocol. This protocol aims to establish a session key between two parties on a network, typically to protect further communication.
• The Needham-Schroder Public-Key Protocol, based on Public-key cryptography. This is intended to provide mutual authentication between two parties communicating on a network, but in its proposed form it is insecure.

The Symmetric Protocol

Here, Alice (A) initiates the communication to Bob (B). Also,

• S is a server trusted by both parties
• K_AS is a symmetric key known only to A and S
• K_BS is a symmetric key known only to B and S
• N_A, N_B, etc are nonces

The protocol can be specified as follows in security protocol notation:

$A\rightarrow S:A,B,N_{A}$

Alice sends a message to the server identifying herself and Bob, telling the server she wants to communicate with Bob.

$S\rightarrow A:\{N_{A},K_{AB},B,\{K_{AB},A\}_{K_{BS}}\}_{K_{AS}}$

The server generates ${K_{AB}}$ and sends back to Alice a copy encrypted under ${K_{BS}}$ for Alice to forward to Bob and also a copy for Alice. Since Alice may be requesting keys for several different people, the nonce assures Alice that the message is fresh and that the server is replying to that particular message and the inclusion of Bob's name tells Alice who she is to share this key with.

$A\rightarrow B:\{K_{AB},A\}_{K_{BS}}$

Alice forwards the key to Bob who can decrypt it with the key he shares with the server, thus authenticating the data.

$B\rightarrow A:\{N_{B}\}_{K_{AB}}$

Bob sends Alice a nonce encrypted under ${K_{AB}}$ to show that he has the key.

$A\rightarrow B:\{N_{B}-1\}_{K_{AB}}$

Alice performs a simple operation on the nonce, re-encrypts it and sends it back verifying that she is still alive and that she holds the key.

The protocol is vulnerable to a replay attack. If an attacker records one run of this protocol, then subsequently learns the value K_AB used, she can then reply the message $\{K_{AB},A\}_{K_{BS}}$ to Bob, who will accept it, being unable to tell that the key is not fresh. This flaw is fixed in the Kerberos protocol by the inclusion of a timestamp.

See also

• Kerberos
• Otway-Rees
• Wide Mouth Frog protocol

External Links

• http://www.lsv.ens-cachan.fr/spore/nspk.html - description of the Public-key protocol
• http://www.lsv.ens-cachan.fr/spore/nssk.html - the Symmetric-key protocol

References

• Roger Needham and Michael Schroeder. Using encryption for authentification in large networks of computers. Communications of the ACM, 21(12), December 1978.
• Gavin Lowe. An attack on the Needham-Schroeder public key authentication protocol. Information Processing Letters, 56(3):131--136, November 1995.