The Needham–Schroeder protocol is one of the two key transport protocols intended for use over an insecure network, both proposed by
Roger Needham
Roger Michael Needham (9 February 1935 – 1 March 2003) was a British computer scientist.
Early life and education
Needham was born in Birmingham, England, the only child of Phyllis Mary, ''née'' Baker (''c''.1904–1976) and Leonard Wi ...
and
Michael Schroeder.
[
] 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
A session key is a single-use symmetric key used for encrypting all messages in one communication session. A closely related term is content encryption key (CEK), traffic encryption key (TEK), or multicast key which refers to any key used for enc ...
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, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
. This protocol is intended to provide mutual
authentication
Authentication (from ''authentikos'', "real, genuine", from αὐθέντης ''authentes'', "author") is the act of proving an assertion, such as the identity of a computer system user. In contrast with identification, the act of indicati ...
between two parties communicating on a network, but in its proposed form is insecure.
The symmetric protocol
Here,
Alice initiates the communication to Bob
.
is a server trusted by both parties. In the communication:
*
and
are identities of Alice and Bob respectively
*
is a symmetric key known only to
and
*
is a symmetric key known only to
and
*
and
are
nonces generated by
and
respectively
*
is a symmetric, generated key, which will be the
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 content encryption key (CEK), traffic encryption key (TEK), or multicast key which refers to any key used for enc ...
of the session between
and
The protocol can be specified as follows in
security protocol notation
In cryptography, security (engineering) protocol notation, also known as protocol narrations and Alice & Bob notation, is a way of expressing a protocol of correspondence between entities of a dynamic system, such as a computer network. In the cont ...
:
: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
A replay attack (also known as a repeat attack or playback attack) is a form of network attack in which valid data transmission is maliciously or fraudulently repeated or delayed. This is carried out either by the originator or by an adversary wh ...
(as identified by
Denning and Sacco). If an attacker uses an older, compromised value for
, 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 () is a computer-network authentication protocol that 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 it primarily ...
by the inclusion of a
timestamp
A timestamp is a sequence of characters or encoded information identifying when a certain event occurred, usually giving date and time of day, sometimes accurate to a small fraction of a second. Timestamps do not have to be based on some absolut ...
. 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.
Here, Alice
and Bob
use a trusted server
to distribute public keys on request. These keys are:
*
and
, respectively public and private halves of an encryption key-pair belonging to
(
stands for "secret key" here)
*
and
, similar belonging to
*
and
, similar belonging to
. (Note that this key-pair will be used for
digital signature
A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature, where the prerequisites are satisfied, gives a recipient very high confidence that the message was created b ...
s, i.e.,
used for signing a message and
used for verification.
must be known to
and
before the protocol starts.)
The protocol runs as follows:
:
requests
's public keys from
:
responds with public key
alongside
's identity, signed by the server for authentication purposes.
:
chooses a random
and sends it to
.
:
now knows A wants to communicate, so
requests
's public keys.
: Server responds.
:
chooses a random
, and sends it to
along with
to prove ability to decrypt with
.
:
confirms
to
, to prove ability to decrypt with
At the end of the protocol,
and
know each other's identities, and know both
and
. These nonces are not known to eavesdroppers.
An attack on the protocol
This protocol is vulnerable to a
man-in-the-middle attack
In cryptography and computer security, a man-in-the-middle, monster-in-the-middle, machine-in-the-middle, monkey-in-the-middle, meddler-in-the-middle, manipulator-in-the-middle (MITM), person-in-the-middle (PITM) or adversary-in-the-middle (AiTM) ...
. If an impostor
can persuade
to initiate a session with them, they can relay the messages to
and convince
that he is communicating with
.
Ignoring the traffic to and from
, which is unchanged, the attack runs as follows:
:
sends
to
, who decrypts the message with
:
relays the message to
, pretending that
is communicating
:
sends
:
relays it to
:
decrypts
and confirms it to
, who learns it
:
re-encrypts
, and convinces
that she's decrypted it
At the end of the attack,
falsely believes that
is communicating with him, and that
and
are known only to
and
.
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
Gavin Lowe (born 1 March 1995 in Carluke) is a Scottish international 7s rugby union player at the Full Back position.
Rugby union career
Amateur career
Lowe first played his rugby for Ayr Rugby but moved on to the Glasgow Hawks. He was ...
.
[
]
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:
with the fixed version:
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
The Otway–Rees protocol is a computer network authentication protocol designed for use on insecure networks (e.g. the Internet). It allows individuals communicating over such a network to prove their identity to each other while also preventing ...
*
Yahalom
*
Wide Mouth Frog protocol The Wide-Mouth Frog protocol is a computer network authentication protocol designed for use on insecure networks (the Internet for example). It allows individuals communicating over a network to prove their identity to each other while also preventi ...
*
Neuman–Stubblebine protocol
The Neuman–Stubblebine protocol is a computer network authentication protocol designed for use on insecure networks (e.g., the Internet). It allows individuals communicating over such a network to prove their identity to each other. This protoc ...
*
Diffie-Hellman key exchange
References
External links
*
*
*
Explanation of man-in-the-middle attackby
Computerphile.
{{DEFAULTSORT:Needham-Schroeder Protocol
Authentication protocols
Key transport protocols
Symmetric-key cryptography
Computer access control protocols
Telecommunication protocols