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, and respectively,
which, it is assumed here, are authentically known by the
other. In the following, and are random values
chosen by *A* and *B* respectively, while denotes
encryption of the value *X* with the public key *K* .

- 1.
- 2.
- 3.

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.
- 2.
- 3.

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 , 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 and multiply it
by . 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 .By this process, *A* 's name changes
into *C* , even though the attacker has no knowledge of .
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.
- 1'.
- 2.
- 2'.
- 3.

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 ( or in this case). This leads to the following alternative protocol.

- 1.
- 2.
- 3.

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 or 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.