Needham–Schroeder protocol

The term Needham–Schroeder protocol can refer to 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 symmetric protocol

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

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

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.

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.

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 KAB, he can then replay the message \{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:

A \rightarrow B: A
Alice sends to Bob a request.
B \rightarrow A: \{A,\mathbf{N_B'}\}_{K_{BS}}
Bob responds with a nonce encrypted under his key with the Server.
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.
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  N_B' is a different nonce from  N_B.The inclusion of this new nonce prevents the replaying of a compromised version of \{K_{AB}, A\}_{K_{BS}} since such a message would need to be of the form \{K_{AB}, A,\mathbf{N_B'}\}_{K_{BS}} which the attacker can't forge since she does not have 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:

The protocol runs as follows:

A \rightarrow S: \left . A, B \right .

A requests B's public keys from S

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

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

A \rightarrow B: \{N_A, A\}_{K_{PB}}

A chooses a random NA and sends it to B.

B \rightarrow S: \left. B, A \right .

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

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

Server responds.

B \rightarrow A: \{N_A, N_B\}_{K_{PA}}

B chooses a random NB, and sends it to A along with NA to prove ability to decrypt with KSB.

A \rightarrow B: \{N_B\}_{K_{PB}}

A confirms NB to B, to prove ability to decrypt with KSA

At the end of the protocol, A and B know each other's identities, and know both NA and NB. 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 can persuade A to initiate a session with him, he can relay the messages to B and convince B that he is communicating with A.

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

A \rightarrow I: \{N_A, A\}_{K_{PI}}

A sends NA to I, who decrypts the message with KSI

I \rightarrow B: \{N_A, A\}_{K_{PB}}

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

B \rightarrow I: \{N_A, N_B\}_{K_{PA}}

B sends NB

I \rightarrow A: \{N_A, N_B\}_{K_{PA}}

I relays it to A

A \rightarrow I: \{N_B\}_{K_{PI}}

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

I \rightarrow B: \{N_B\}_{K_{PB}}

I re-encrypts NB, and convinces B that he's decrypted it

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

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:

B \rightarrow A: \{N_A, N_B\}_{K_{PA}}

with the fixed version:

B \rightarrow A: \{N_A, N_B, B\}_{K_{PA}}

See also

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. doi:10.1145/359657.359659.
  2. Denning, Dorothy E.; Sacco, Giovanni Maria (1981). "Timestamps in key distributed protocols". Communication 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. doi:10.1016/0020-0190(95)00144-2. Retrieved 2008-04-17.

External links

This article is issued from Wikipedia - version of the Thursday, September 17, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.