Needham-Schroeder protocol - AbsoluteAstronomy.com

The term Needham–Schroeder protocol can refer to one of two communication protocols

Communications protocol

A communications protocol is a system of digital message formats and rules for exchanging those messages in or between computing systems and in telecommunications...

intended for use over an insecure network, both proposed by Roger Needham

Roger Needham

Roger Michael Needham, CBE, FRS, FREng was a British computer scientist.-Early life:He attended Doncaster Grammar School for Boys in Doncaster ....

and Michael Schroeder

Michael Schroeder

Michael Schroeder is a computer scientist perhaps best-known as the co-inventor of the Needham-Schroeder protocol. He is the assistant managing director of Microsoft Research Silicon Valley, where he has been since its inception in 2001 when he moved from DEC SRC. His areas of research include...

. These are:

The Needham–Schroeder Symmetric Key Protocol is based on a symmetric encryption algorithm
Symmetric-key algorithm
Symmetric-key algorithms are a class of algorithms for cryptography that use trivially related, often identical, cryptographic keys for both encryption of plaintext and decryption of ciphertext. The encryption key is trivially related to the decryption key, in that they may be identical or there is...

. It forms the basis for the Kerberos protocol. This protocol aims to establish a session key
Session key
A session key is a single-use symmetric key used for encrypting all messages in one communication session. A closely related term is traffic encryption key or TEK, which refers to any key used to encrypt messages, as opposed to other uses, like encrypting other keys .Session keys can introduce...

between two parties on a network, typically to protect further communication.
The Needham–Schroeder Public-Key Protocol, based on public-key cryptography
Public-key cryptography
Public-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private...

. This protocol is intended to provide mutual authentication
Authentication
Authentication is the act of confirming the truth of an attribute of a datum or entity...

between two parties communicating on a network, but in its proposed form is insecure.

The symmetric protocol

Here, Alice

Alice and Bob

The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...

(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
Cryptographic nonce
In security engineering, nonce is an arbitrary number used only once to sign a cryptographic communication. It is similar in spirit to a nonce word, hence the name. It is often a random or pseudo-random number issued in an authentication protocol to ensure that old communications cannot be reused...

generated by A and B respectively
K_AB is a symmetric, generated key, which will be the session key
Session key
A session key is a single-use symmetric key used for encrypting all messages in one communication session. A closely related term is traffic encryption key or TEK, which refers to any key used to encrypt messages, as opposed to other uses, like encrypting other keys .Session keys can introduce...

of the session between A and B

The protocol can be specified as follows in security protocol notation

Security protocol notation

In cryptography, security protocol notation is a way of expressing a protocol of correspondence between entities of a dynamic system, such as a computer network...

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

The server generates

and sends back to Alice a copy encrypted under

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.

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

Bob sends Alice a nonce encrypted under

to show that he has the key.

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

Replay attack

A replay attack is a form of network attack in which a valid data transmission is maliciously or fraudulently repeated or delayed. This is carried out either by the originator or by an adversary who intercepts the data and retransmits it, possibly as part of a masquerade attack by IP packet...

(as identified by Denning

Dorothy E. Denning

Dorothy Elizabeth Denning is an American information security researcher and a graduate of the University of Michigan. She has published four books and 140 articles...

and Sacco). If an attacker uses an older, compromised value for K_AB, he can then replay the message

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

Kerberos protocol

Kerberos is a computer network authentication protocol which works on the basis of "tickets" to allow nodes communicating over a non-secure network to prove their identity to one another in a secure manner. Its designers aimed primarily at a client–server model, and it provides mutual...

by the inclusion of a timestamp

Timestamp

A timestamp is a sequence of characters, denoting the date or time at which a certain event occurred. A timestamp is the time at which an event is recorded by a computer, not the time of the event itself...

. It can also be fixed with the use of nonces as described below. At the beginning of the protocol:

Alice sends to Bob a request.

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

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

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

is a different nonce from

.The inclusion of this new nonce prevents the replaying of a compromised version of

since such a message would need to be of the form

which the attacker can't forge since she does not have

The public-key protocol

This assumes the use of a public-key encryption algorithm

Public-key cryptography

Public-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private...

.

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
K_PB and K_SB, similar belonging to B
K_PS and K_SS, similar belonging to S. (Note this has the property that K_SS is used to encrypt and K_PS to decrypt).

The protocol runs as follows:

A requests B's public keys from S

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

A invents N_A and sends it to B.

B requests A's public keys.

Server responds.

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

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

Man-in-the-middle attack

In cryptography, the man-in-the-middle attack , bucket-brigade attack, or sometimes Janus attack, is a form of active eavesdropping in which the attacker makes independent connections with the victims and relays messages between them, making them believe that they are talking directly to each other...

. 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 sends N_A to I, who decrypts the message with K_SI

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

B sends N_B

I relays it to A

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

I re-encrypts N_B, 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 N_A and N_B 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.
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:

with the fixed version:

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

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.