Eve, who has recently learned the difference between a knight and a rook, claims that she can play two chess grandmasters simultaneously and either win one game or draw both games. The strategy is simple. She waits for the first grandmaster to move, then makes the identical move against the second grandmaster. When the second grandmaster responds, Eve makes that play against the first grandmaster. Continuing in this way, Eve cannot lose both games (unless she runs into time trouble because of the slight delay in transferring the moves).

A similar strategy, called the intruder-in-the-middle attack, can be used against many cryptographic protocols. Many of the technicalities of the algorithms in this chapter are caused by efforts to thwart such an attack.

Let’s see how this attack works against the Diffie-Hellman key exchange from Section 10.4.

Let’s recall the protocol. Alice and Bob want to establish a key for communicating. The Diffie-Hellman scheme for accomplishing this is as follows:

1. Either Alice or Bob selects a large, secure prime number $p$ and a primitive root $\alpha (\text{mod}p)$. Both $p$ and $\alpha$ can be made public.

2. Alice chooses a secret random $x$ with $1\le x\le p-2$, and Bob selects a secret random $y$ with $1\le y\le p-2$.

3. Alice sends ${\alpha }^x(\text{mod}p)$ to Bob, and Bob sends ${\alpha }^y(\text{mod}p)$ to Alice.

4. Using the messages that they each have received, they can each calculate the session key $K$. Alice calculates $K$ by $K\equiv ({\alpha }^y{)}^x(\text{mod}p)$, and Bob calculates $K$ by $K\equiv ({\alpha }^x{)}^y(\text{mod}p)$.

Here is how the intruder-in-the-middle attack works.

1. Eve chooses an exponent $z$.

2. Eve intercepts ${\alpha }^x$ and ${\alpha }^y$.

3. Eve sends ${\alpha }^z$ to Alice and to Bob (Alice believes she is receiving ${\alpha }^y$ and Bob believes he is receiving ${\alpha }^x$).

4. Eve computes $K_{AE}\equiv ({\alpha }^x{)}^z(\text{mod}p)$ and $K_{EB}\equiv ({\alpha }^y{)}^z(\text{mod}p)$. Alice, not realizing that Eve is in the middle, also computes $K_{AE}$, and Bob computes $K_{EB}$.

5. When Alice sends a message to Bob, encrypted with $K_{AE}$, Eve intercepts it, deciphers it, encrypts it with $K_{EB}$, and sends it to Bob. Bob decrypts with $K_{EB}$ and obtains the message. Bob has no reason to believe the communication was insecure. Meanwhile, Eve is reading the juicy gossip that she has obtained.

To avoid the intruder-in-the-middle attack, it is desirable to have a procedure that authenticates Alice’s and Bob’s identities to each other while the key is being formed. A protocol that can do this is known as an authenticated key agreement protocol.

A standard way to stop the intruder-in-the-middle attack is the station-to-station (STS) protocol, which uses digital signatures. Each user $U$ has a digital signature function $si{g}_U$ with verification algorithm $ve{r}_U$. For example, $si{g}_U$ could produce an RSA or ElGamal signature, and $ve{r}_U$ checks that it is a valid signature for $U$. The verification algorithms are compiled and made public by the trusted authority Trent, who certifies that $ve{r}_U$ is actually the verification algorithm for $U$ and not for Eve.

Suppose now that Alice and Bob want to establish a key to use in an encryption function $E_K$. They proceed as in the Diffie-Hellman key exchange, but with the added feature of digital signatures:

1. They choose a large prime $p$ and a primitive root $\alpha$.

2. Alice chooses a random $x$ and Bob chooses a random $y$.

3. Alice computes ${\alpha }^x(\text{mod}p)$, and Bob computes ${\alpha }^y(\text{mod}p)$.

4. Alice sends ${\alpha }^x$ to Bob.

5. Bob computes $K\equiv ({\alpha }^x{)}^y(\text{mod}p)$.

6. Bob sends ${\alpha }^y$ and $E_K(si{g}_B({\alpha }^y\text{,}{\alpha }^x))$ to Alice.

7. Alice computes $K\equiv ({\alpha }^y{)}^x(\text{mod}p)$.

8. Alice decrypts $E_K(si{g}_B({\alpha }^y\text{,}{\alpha }^x))$ to obtain $si{g}_B({\alpha }^y\text{,}{\alpha }^x)$.

9. Alice asks Trent to verify that $ve{r}_B$ is Bob’s verification algorithm.

10. Alice uses $ve{r}_B$ to verify Bob’s signature.

11. Alice sends $E_K(si{g}_A({\alpha }^x\text{,}{\alpha }^y))$ to Bob.

12. Bob decrypts, asks Trent to verify that $ve{r}_A$ is Alice’s verification algorithm, and then uses $ve{r}_A$ to verify Alice’s signature.

This protocol is due to Diffie, van Oorschot, and Wiener. Note that Alice and Bob are also certain that they are using the same key $K$, since it is very unlikely that an incorrect key would give a decryption that is a valid signature.

Note the role that trust plays in the protocol. Alice and Bob must trust Trent’s verification if they are to have confidence that their communications are secure. Throughout this chapter, a trusted authority such as Trent will be an important participant in many protocols.