Needham-Schroeder Public Key Protocol

The Needham-Schroeder public key protocol [21] is another example that has been widely examined by protocol researchers. Users A and B own public keys, $K_A$ and $K_B$ respectively, which, it is assumed here, are authentically known by the other. In the following, $N_A$ and $N_B$ are random values chosen by A and B respectively, while $\{X\}_K$ denotes encryption of the value X with the public key K .

1.

$A \longrightarrow B: \{N_A,A\}_{K_B}$

2.

$B \longrightarrow A: \{N_A,N_B\}_{K_A}$

3.

$A \longrightarrow B: \{N_B\}_{K_B}$

Although this protocol is nearly 20 years old it has aroused quite some interest recently. An attack of Lowe [16] shows that B cannot be sure that the final message came from A . Gollman [13] points out that the protocol fails, because of this, to achieve his goal Gol2. Notice that A has never explicitly declared her intention to converse with B .

In order to fix the protocol against his attack, Lowe proposed the following variation which simply includes the identifier of B in the second message.

1.

$A \longrightarrow B: \{N_A,A\}_{K_B}$

2.

$B \longrightarrow A: \{N_A,N_B,B\}_{K_A}$

3.

$A \longrightarrow B: \{N_B\}_{K_B}$

Let us consider whether the extensional goals for entity authentication proposed above are satisfied. Consider the point of view of A . When she receives the message 2 she wants to use it to verify that B wishes to communicate with her. Immediately we run into a problem here because it is not clear what she can tell from receiving an encrypted message. What she really requires is an authenticated message, but encryption with her public key may not provide this. Indeed, encryption is a way to provide the confidentiality service to the message sender. It seems that the protocol designers (and most analysers) have assumed that inclusion of the nonce $N_A$, which A sent confidentially to B , is sufficient to provide authentication. Unfortunately this need not be the case, even with the most well known public key encryption algorithms.

To see the point, consider the Blum-Goldwasser public key encryption algorithm [8]. In this algorithm the plaintext is added modulo 2 to a string formed by iterative squaring. Consequently it is trivial for an attacker to change the known parts of the ciphertext, which are the identifiers in message 1 (and message 2 in Lowe's fix). This results in a simple attack on the protocol, or on Lowe's fix.

In practice, use of the Blum-Goldwasser algorithm is not very reasonable, since it is known to be vulnerable to a chosen ciphertext attack which is eminently possible in the protocol. On the other hand, there is a reasonable scenario in which use of the well-known RSA algorithm [23] is insecure. Suppose the attacker knows (or chooses) an identifier C such that C is the same bit string as identifier A shifted left one place. Then the attacker can capture $\{N_A,A\}_{K_B}$ and multiply it by $\{2\}_{K_B}$. The effect of this is to change the encrypted message by shifting it to the left, due to the well-known multiplicative property of RSA, so that it becomes $\{2*(N_A,A)\}_{K_B} = \{2*N_A,C\}_{K_B}$.By this process, A 's name changes into C , even though the attacker has no knowledge of $N_A$. With the collaboration of C (or we may assume the attacker is C ) this allows a run of the protocol, or Lowe's fix, where B only ever wanted to communicate with C , but A believes B wants to communicate with A . An attacking run on Lowe's fix is as follows.

1.

$A \longrightarrow C_B: \{N_A,A\}_{K_B}$

1'.

$C \longrightarrow B: \{2*N_A,C\}_{K_B}$

2.

$B \longrightarrow C: \{2*N_A,N_B,B\}_{K_C}$

2'.

$C_B \longrightarrow A: \{N_A,N_B,B\}_{K_A}$

3.

$A \longrightarrow B: \{N_B\}_{K_B}$

In order to allow the receivers of messages 2 and 3 to authenticate the messages the encryption functions needs to act like a message authentication code (MAC) which guarantees that the message was written with knowledge of a shared secret ($N_A$ or $N_B$ in this case). This leads to the following alternative protocol.

1.

$A \longrightarrow B: \{N_A\}_{K_B},A$

2.

$B \longrightarrow A: \{N_B\}_{K_A}, h(N_A,B)$

3.

$A \longrightarrow B: h(N_B,A,B)$

Here h(K,.) may be a keyed one-way hash function such that need K is needed to calculate it, and it does not give away K . Several constructions for such functions exist in the literature [22]. Further considerations on protocol design for entity authentication are discussed below.

It should be noted that the above attack is probably prevented by including strict formatting in the RSA encrypted messages, such as is recommended by the RSA Encryption Standard PKCS #1 [26] or by Bellare and Rogaway [5]. Such formatting is intended to ensure that the encrypting agent must be aware of the whole plaintext in order to form a valid ciphertext. In other words encryption of a shared secret (such as the nonce $N_A$ or $N_B$ in the Needham-Schroeder protocol) gives the ciphertext the essential property of a MAC. Notice also that the attack is not a `typing' attack, since inclusion of, say, one bit typing tags would still allow the attack to succeed with high probability.