Needham–Schroeder protocol

The Needham–Schroeder protocol is one of the two key transport protocols intended for use over an insecure network, both proposed by Roger Needham and Michael Schroeder.[1] These are:

• The Needham–Schroeder Symmetric Key Protocol, based on a symmetric encryption algorithm. It 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–Schroeder Public-Key Protocol, based on public-key cryptography. This protocol is intended to provide mutual authentication between two parties communicating on a network, but in its proposed form is insecure.

Symmetric Needham–Schroeder protocol scheme

The symmetric protocol

Here, Alice (A) initiates the communication to Bob (B). S is a server trusted by both parties. In the communication:

• A and B are identities of Alice and Bob respectively
• 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 and N_B are nonces generated by A and B respectively
• K_AB is a symmetric, generated key, which will be the session key of the session between A and B

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

${\displaystyle A\rightarrow S:\left.A,B,N_{A}\right.}$

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

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

The server generates ${\displaystyle {K_{AB}}}$ and sends back to Alice a copy encrypted under ${\displaystyle {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.

${\displaystyle 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.

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

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

${\displaystyle 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.

Attacks on the protocol

The protocol is vulnerable to a replay attack (as identified by Denning and Sacco[2]). If an attacker uses an older, compromised value for K_AB, he can then replay the message ${\displaystyle \{K_{AB},A\}_{K_{BS}}}$ to Bob, who will accept it, being unable to tell that the key is not fresh.

Fixing the attack

This flaw is fixed in the Kerberos protocol by the inclusion of a timestamp. It can also be fixed with the use of nonces as described below.[3] At the beginning of the protocol:

${\displaystyle A\rightarrow B:A}$

Alice sends to Bob a request.

${\displaystyle B\rightarrow A:\{A,\mathbf {N_{B}'} \}_{K_{BS}}}$

Bob responds with a nonce encrypted under his key with the Server.

${\displaystyle A\rightarrow S:\left.A,B,N_{A},\{A,\mathbf {N_{B}'} \}_{K_{BS}}\right.}$

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

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

Note the inclusion of the nonce.

The protocol then continues as described through the final three steps as described in the original protocol above. Note that ${\displaystyle N_{B}'}$ is a different nonce from ${\displaystyle N_{B}}$.The inclusion of this new nonce prevents the replaying of a compromised version of ${\displaystyle \{K_{AB},A\}_{K_{BS}}}$ since such a message would need to be of the form ${\displaystyle \{K_{AB},A,\mathbf {N_{B}'} \}_{K_{BS}}}$ which the attacker can't forge since she does not have ${\displaystyle K_{BS}}$.

The public-key protocol

This assumes the use of a public-key encryption algorithm.

Here, Alice (A) and Bob (B) use a trusted server (S) to distribute public keys on request. These keys are:

• K_PA and K_SA, respectively public and private halves of an encryption key-pair belonging to A (S stands for "secret key" here)
• K_PB and K_SB, similar belonging to B
• K_PS and K_SS, similar belonging to S. (Note that this key-pair will be used for digital signatures, i.e., K_SS used for signing a message and K_PS used for verification. K_PS must be known to A and B before the protocol starts.)

The protocol runs as follows:

${\displaystyle A\rightarrow S:\left.A,B\right.}$

A requests B's public keys from S

${\displaystyle S\rightarrow A:\{K_{PB},B\}_{K_{SS}}}$

S responds with public key K_PB alongside B's identity, signed by the server for authentication purposes.

${\displaystyle A\rightarrow B:\{N_{A},A\}_{K_{PB}}}$

A chooses a random N_A and sends it to B.

${\displaystyle B\rightarrow S:\left.B,A\right.}$

B now knows A wants to communicate, so B requests A's public keys.

${\displaystyle S\rightarrow B:\{K_{PA},A\}_{K_{SS}}}$

Server responds.

${\displaystyle B\rightarrow A:\{N_{A},N_{B}\}_{K_{PA}}}$

B chooses a random N_B, and sends it to A along with N_A to prove ability to decrypt with K_SB.

${\displaystyle A\rightarrow B:\{N_{B}\}_{K_{PB}}}$

A confirms N_B to B, to prove ability to decrypt with K_SA

At the end of the protocol, A and B know each other's identities, and know both N_A and N_B. These nonces are not known to eavesdroppers.

An attack on the protocol

Unfortunately, this protocol is vulnerable to a man-in-the-middle attack. If an impostor ${\displaystyle I}$ can persuade ${\displaystyle A}$ to initiate a session with them, they can relay the messages to ${\displaystyle B}$ and convince ${\displaystyle B}$ that he is communicating with ${\displaystyle A}$.

Ignoring the traffic to and from S, which is unchanged, the attack runs as follows:

${\displaystyle A\rightarrow I:\{N_{A},A\}_{K_{PI}}}$

A sends N_A to I, who decrypts the message with K_SI

${\displaystyle I\rightarrow B:\{N_{A},A\}_{K_{PB}}}$

I relays the message to B, pretending that A is communicating

${\displaystyle B\rightarrow I:\{N_{A},N_{B}\}_{K_{PA}}}$

B sends N_B

${\displaystyle I\rightarrow A:\{N_{A},N_{B}\}_{K_{PA}}}$

I relays it to A

${\displaystyle A\rightarrow I:\{N_{B}\}_{K_{PI}}}$

A decrypts N_B and confirms it to I, who learns it

${\displaystyle I\rightarrow B:\{N_{B}\}_{K_{PB}}}$

I re-encrypts N_B, and convinces B that she's decrypted it

At the end of the attack, B falsely believes that A is communicating with him, and that N_A and N_B are known only to A and B.

The following example illustrates the attack. Alice (A) would like to contact her bank (B). We assume that an impostor (I) successfully convinces A that they are the bank. As a consequence A uses the public key of I instead of using the public key of B to encrypt the messages she intends to send to her bank. Therefore, A sends I her nonce encrypted with the public key of I. I decrypts the message using their private key and contacts B sending it the nonce of A encrypted with the public key of B. B has no way to know that this message was actually sent by I. B responds with their own nonce and encrypts the message with the public key of A. Since I is not in possession of the private key of A they have to relay the message to A without knowing the content. A decrypts the message with her private key and respond with the nonce of B encrypted with the public key of I. I decrypts the message using their private key and is now in possession of nonce A and B. Therefore they can now impersonate the bank and the client respectively.

Fixing the man-in-the-middle attack

The attack was first described in a 1995 paper by Gavin Lowe.[4] The paper also describes a fixed version of the scheme, referred to as the Needham–Schroeder–Lowe protocol. The fix involves the modification of message six to include the responder's identity, that is we replace:

${\displaystyle B\rightarrow A:\{N_{A},N_{B}\}_{K_{PA}}}$

with the fixed version:

${\displaystyle B\rightarrow A:\{N_{A},N_{B},B\}_{K_{PA}}}$

and the intruder cannot successfully replay the message because A is expecting a message containing the identity of I whereas the message will have identity of B.

See also

• Kerberos
• Otway–Rees protocol
• Yahalom
• Wide Mouth Frog protocol
• Neuman–Stubblebine protocol

References

1. Needham, Roger; Schroeder, Michael (December 1978). "Using encryption for authentication in large networks of computers". Communications of the ACM. 21 (12): 993–999. CiteSeerX 10.1.1.357.4298. doi:10.1145/359657.359659.
2. Denning, Dorothy E.; Sacco, Giovanni Maria (1981). "Timestamps in key distribution protocols". Communications of the ACM. 24 (8): 533–535. doi:10.1145/358722.358740.
3. Needham, R. M.; Schroeder, M. D. (1987). "Authentication revisited". ACM SIGOPS Operating Systems Review. 21 (1): 7. doi:10.1145/24592.24593.
4. Lowe, Gavin (November 1995). "An attack on the Needham-Schroeder public key authentication protocol". Information Processing Letters. 56 (3): 131–136. CiteSeerX 10.1.1.394.6094. doi:10.1016/0020-0190(95)00144-2. Retrieved 2008-04-17.

External links

• Roger Needham and Michael Schroeder (1978). "Needham-Schroeder Public Key". Laboratoire Spécification et Vérification.CS1 maint: uses authors parameter (link)

• Roger Needham and Michael Schroeder (1978). "Needham Schroeder Symmetric Key". Laboratoire Spécification et Vérification.CS1 maint: uses authors parameter (link)

• Gavin Lowe (1995). "Lowe's fixed version of Needham-Schroder Public Key". Laboratoire Spécification et Vérification.CS1 maint: uses authors parameter (link)