Needham-Schroeder protocol


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.Citation | last1=Needham | first1=Roger | last2=Schroeder | first2=Michael
title=Using encryption for authentication in large networks of computers.
journal=Communications of the ACM
volume=21 | issue=12 | date=December 1978 | pages=993-999
doi=10.1145/359657.359659
] These are:
* The "Needham-Schroeder Symmetric Key Protocol" is 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 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
* KAS is a symmetric key known only to A and S
* KBS is a symmetric key known only to B and S
* NA and NB are nonces

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

A ightarrow 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 ightarrow 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 ightarrow 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 ightarrow A: {N_B}_{K_{AB:Bob sends Alice a nonce encrypted under {K_{AB to show that he has the key.A ightarrow 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 KAB used, 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. This flaw is fixed in the Kerberos protocol by the inclusion of a timestamp.

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:
* KPA and KSA, respectively public and private halves of an encryption key-pair belonging to A
* KPB and KSB, similar belonging to B
* KPS and KSS, similar belonging to S. (Note this has the property that KSS is used to "encrypt" and KPS to "decrypt").

The protocol runs as follows:

A ightarrow S: A, B:A requests B's public keys from SS ightarrow A: {K_{PB}, B}_{K_{SS:S responds. B's identity is placed alongside KPB for confirmation.A ightarrow B: {N_A, A}_{K_{PB:A invents NA and sends it to B.B ightarrow S: B, A:B requests A's public keys.S ightarrow B: {K_{PA}, A}_{K_{SS:Server responds.B ightarrow A: {N_A, N_B}_{K_{PA:B invents NB, and sends it to A along with NA to prove ability to decrypt with KSB.A ightarrow 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.

Attacks on the protocol

Unfortunately, this protocol is vulnerable to a man-in-the-middle attack. If an impostor I 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 ightarrow I: {N_A, A}_{K_{PI:A sends NA to I, who decrypts the message with KSII ightarrow B: {N_A, A}_{K_{PB:I relays the message to B, pretending that A is communicatingB ightarrow I: {N_A, N_B}_{K_{PA:B sends NBI ightarrow A: {N_A, N_B}_{K_{PA:I relays it to AA ightarrow I: {N_B}_{K_{PI:A decrypts NB and confirms it to I, who learns itI ightarrow 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.

The attack was first described in a 1995 paper by Gavin Lowe.Citation | last1=Lowe | first1=Gavin
title=An attack on the Needham-Schroeder public key authentication protocol.
journal=Information Processing Letters
volume=56
issue=3
pages=131-136
date=November 1995
url=http://web.comlab.ox.ac.uk/oucl/work/gavin.lowe/Security/Papers/NSPKP.ps
doi=10.1016/0020-0190(95)00144-2
accessdate=2008-04-17
] 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, that is we replace:

B ightarrow A: {N_A, N_B}_{K_{PA

with the fixed version:

B ightarrow A: {N_A, N_B, B}_{K_{PA

ee 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
* http://www.lsv.ens-cachan.fr/spore/nspkLowe.html - the public-key protocol amended by Lowe

References


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • 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.[1] These are: The Needham–Schroeder Symmetric Key Protocol is… …   Wikipedia

  • Needham-Schroeder Protokoll — Das Needham Schroeder Protokoll ist ein Protokoll für sicheren Datenaustausch in einem dezentralen Netzwerk. Es vereint Schlüsselaustausch und Authentifikation mit dem Ziel, eine sichere Kommunikation zwischen zwei Parteien in einem dezentralen… …   Deutsch Wikipedia

  • Needham-Schroeder-Protokoll — Das Needham Schroeder Protokoll ist ein Protokoll für sicheren Datenaustausch in einem dezentralen Netzwerk. Es vereint Schlüsselaustausch und Authentifikation mit dem Ziel, eine sichere Kommunikation zwischen zwei Parteien in einem dezentralen… …   Deutsch Wikipedia

  • Needham-Schroeder — Protocole de Needham Schroeder Pour les articles homonymes, voir Needham et Schroeder. Needham Schroeder est un protocole d authentification dans les réseaux informatiques conçu pour être utilisé dans des réseaux non sûrs (Internet par exemple),… …   Wikipédia en Français

  • Needham-schroeder — Protocole de Needham Schroeder Pour les articles homonymes, voir Needham et Schroeder. Needham Schroeder est un protocole d authentification dans les réseaux informatiques conçu pour être utilisé dans des réseaux non sûrs (Internet par exemple),… …   Wikipédia en Français

  • Protocole de Needham-Schroeder — Pour les articles homonymes, voir Needham et Schroeder. Needham Schroeder est un protocole d authentification dans les réseaux informatiques conçu pour être utilisé dans des réseaux non sûrs (Internet par exemple), et inventé par Roger Needham et …   Wikipédia en Français

  • Needham — is a surname, and may refer to: Ben Needham, British infant missing since 1991 Col Needham, co founder of the Internet Movie Database David Needham, English football player Ernest Needham (1873–1936), English football player Francis Needham, 3rd… …   Wikipedia

  • Needham, Roger Michael — ▪ 2004       British engineer and computer scientist (b. Feb. 9, 1935, Sheffield, Eng. d. Feb. 28, 2003, Cambridge, Eng.), devised a secure way of protecting computer password files that became the basis for all systems currently used. Needham… …   Universalium

  • Schroeder — an umlaut converted representation of Schröder is a common German surname. It can specifically refer to several people: * Andreas Schroeder, a German born Canadian poet, novelist, and nonfiction writer * Barbet Schroeder, a Swiss movie director… …   Wikipedia

  • Needham-Schroder — Protocole de Needham Schroeder Pour les articles homonymes, voir Needham et Schroeder. Needham Schroeder est un protocole d authentification dans les réseaux informatiques conçu pour être utilisé dans des réseaux non sûrs (Internet par exemple),… …   Wikipédia en Français