Needham-Schroeder Protocol

The Needham-Schroeder protocol is a protocol for secure data exchange in a decentralized network . It combines key exchange and authentication with the aim of establishing secure communication between two parties in a decentralized network. It was developed in 1978 by Roger Needham and Michael D. Schroeder at the Xerox Palo Alto Research Center ( MIT ). The basis for the security of the protocol are secure encryption algorithms with any key , which can neither be broken by cryptanalysis nor by exhaustive search, whereby symmetrical and asymmetrical methods are considered.

The variant of the Needham-Schroeder protocol based on asymmetric cryptography contained a flaw that was only discovered 17 years later (1995) by Gavin Lowe through a computer-guided analysis. Lowe also described how the error found can be corrected by adding additional information in a package.

Symmetrical Needham-Schroeder Protocol

The prerequisite for this protocol variant is that both A and B each have a secret key with the authentication server (AS):

${\ displaystyle K_ {A}}$ - secret key between AS and A
${\ displaystyle K_ {B}}$ - secret key between AS and B

By proving that A and B owns, A and B are authenticated to the other party. ${\ displaystyle K_ {A}}$ ${\ displaystyle K_ {B}}$

The protocol is started from A. In the first step (1), A sends an unencrypted message to the AS, which contains its own identity and that of the desired correspondent (A and B) as well as a nonce . The nonce must never have been used by A at this point. ${\ displaystyle N_ {A}}$

In the next step (2) the AS uses the secret keys of both communication partners. A response is sent to A that is completely encrypted with . It contains the nonce to ensure that the response is not a recorded message from a previous protocol flow that would force the use of an old key. Next it contains the identity of B. This is to prevent that in the message of the first protocol step the identity of B could simply be replaced by another without A noticing. The session key then follows . ${\ displaystyle K_ {A}}$ ${\ displaystyle N_ {A}}$ ${\ displaystyle S_ {K}}$

The last part consists of a block that is also encrypted, which is still within the message to A that is encrypted with . This also contains the session key and A. A's identity is now in possession of the session key. In the third step (3), A sends the part that was also encrypted in the response from the AS to B. Only B can decrypt this message and learns that A would like to communicate with him securely using the session key . At this point, both B and A have the session key to use. ${\ displaystyle K_ {B}}$ ${\ displaystyle K_ {A}}$ ${\ displaystyle K_ {B}}$ ${\ displaystyle S_ {K}}$

In addition, A knows that every message that has been encrypted with can only come from B and that every message that A encrypts with can only be read by B. Both are secure, as the session key was only sent with the secret keys and encrypted. The same applies to B in the opposite direction. A also knows that he has never used the session key before, since the nonce prevents a replay attack in the first two protocol steps . B does not yet have this certainty. ${\ displaystyle S_ {K}}$ ${\ displaystyle S_ {K}}$ ${\ displaystyle S_ {K}}$ ${\ displaystyle K_ {A}}$ ${\ displaystyle K_ {B}}$ ${\ displaystyle S_ {K}}$ ${\ displaystyle N_ {A}}$

The message in protocol step 3 could be a recorded message that would force B to reuse an old session key. There are two additional protocol steps to prevent this. Next, B sends its own nonce to A (4) again , which is encrypted with the session key, and in the last protocol step (5) B expects a response from A related to this nonce, e.g. B. , which is also encrypted with . Since it has never been used before, only A can send a corresponding response, because only A knows the session key . B can now assume that he is not exposed to a replay attack. ${\ displaystyle N_ {B}}$ ${\ displaystyle S_ {K}}$ ${\ displaystyle N_ {B} -1}$ ${\ displaystyle S_ {K}}$ ${\ displaystyle N_ {B}}$ ${\ displaystyle S_ {K}}$

(1) A AS ${\ displaystyle \ rightarrow}$ ${\ displaystyle \ {A, B, N_ {A} \}}$
(2) AS A ${\ displaystyle \ rightarrow}$ ${\ displaystyle \ {N_ {A}, B, S_ {K}, \ {S_ {K}, A \} _ {K_ {B}} \} _ {K_ {A}}}$
(3) A B ${\ displaystyle \ rightarrow}$ ${\ displaystyle \ {S_ {K}, A \} _ {K_ {B}}}$
(4) B A ${\ displaystyle \ rightarrow}$ ${\ displaystyle \ {N_ {B} \} _ {S_ {K}}}$
(5) A B ${\ displaystyle \ rightarrow}$ ${\ displaystyle \ {N_ {B} -1 \} _ {S_ {K}}}$

Problems and possible solutions

There is no guarantee that the session key cannot be cracked. Authentication is then no longer ensured because an attacker can undermine the authenticity by replaying the third message, which contains the session key known to him. This can be circumvented by integrating time stamps into the messages, which can then be used to decide whether it is a replay or not. This procedure requires synchronized clocks. It is used, for example, in the Kerberos network authentication protocol .

Needham-Schroeder protocol for asymmetric encryption

The Needham-Schroeder protocol can also be modified so that it works with asymmetric encryption methods . A trustworthy entity T is again required for this. It is assumed that Alice , Bob and any number of other partners know T's public key . T also knows the public keys of everyone involved (here: Alice and Bob). ${\ displaystyle P_ {T}}$ ${\ displaystyle P_ {A}}$ ${\ displaystyle P_ {B}}$

Alice wants to establish secure communication with Bob. To do this, she needs Bob's public key to encrypt messages to him. Since this could be replaced by a man-in-the-middle attack , the trustworthy entity T, which already knows the key, must be involved.

In the first step (1) Alice sends T an unencrypted message that she wants to speak to Bob.

T replies (2) with B's public key and his identity, and signs it with his private key . This message can be checked with T's public key , i.e. by all partners who know T. The message is not secret, it is just supposed to ensure that the answer really comes from T and that no attacker is trying to slip a forged key into Alice. ${\ displaystyle C_ {T}}$ ${\ displaystyle P_ {T}}$

Now (3) Alice can send a message to Bob that is encrypted with his public key and contains both a nonce and Alice as the sender. However, Bob cannot know whether the message really came from Alice, and Bob may not yet know Alice's public key. ${\ displaystyle P_ {B}}$ ${\ displaystyle N_ {A}}$

Bob uses the same procedure as Alice in steps (1) and (2) to get Alice's public key. (Steps (4) and (5))

Now Bob answers Alice by sending her nonce back and adding his own nonce (6), this message is encrypted with Alice's public key. Alice replies with Bob's nonce , encrypted with Bob's public key (7). These last two steps ensure that the news is up to date. Since only A could decipher the nonce and only B could decipher the nonce , both parties can be sure who they are communicating with. ${\ displaystyle N_ {A}}$ ${\ displaystyle N_ {B}}$ ${\ displaystyle N_ {B}}$ ${\ displaystyle N_ {B}}$ ${\ displaystyle N_ {A}}$

Should an attacker gain access to one of the private keys of Alice, Bob or the trustworthy entity T, the procedure is no longer secure, as he can take on one of the roles, depending on the stolen key.

(1) A T ${\ displaystyle \ rightarrow}$ ${\ displaystyle A, B}$
(2) T A ${\ displaystyle \ rightarrow}$ ${\ displaystyle \ {B, P_ {B} \} _ {C_ {T}}}$
(3) A B ${\ displaystyle \ rightarrow}$ ${\ displaystyle \ {A, N_ {A} \} _ {P_ {B}}}$
(4) B T ${\ displaystyle \ rightarrow}$ ${\ displaystyle B, A}$
(5) T B ${\ displaystyle \ rightarrow}$ ${\ displaystyle \ {A, P_ {A} \} _ {C_ {T}}}$
(6) B A ${\ displaystyle \ rightarrow}$ ${\ displaystyle \ {N_ {A}, N_ {B} \} _ {P_ {A}}}$
(7) A B ${\ displaystyle \ rightarrow}$ ${\ displaystyle \ {N_ {B} \} _ {P_ {B}}}$