If you receive an email asking you to go to a website and update your account information, how can you be sure that the website is legitimate? An impostor can easily set up a web page that looks like the correct one but simply records sensitive information and forwards it to Eve. This is an important authentication problem that must be addressed in real-world implementations of cryptographic protocols. One standard solution uses certificates and a trusted authority and will be discussed in Section 15.5. Authentication will also play an important role in the protocols in many other sections of this chapter.
Another major consideration that must be addressed in communications over public channels is the intruder-in-the-middle attack, which we’ll discuss shortly. It is another cause for several of the steps in the protocols we discuss.
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:
Either Alice or Bob selects a large, secure prime number and a primitive root . Both and can be made public.
Alice chooses a secret random with , and Bob selects a secret random with .
Alice sends to Bob, and Bob sends to Alice.
Using the messages that they each have received, they can each calculate the session key . Alice calculates by , and Bob calculates by .
Here is how the intruder-in-the-middle attack works.
Eve chooses an exponent .
Eve intercepts and .
Eve sends to Alice and to Bob (Alice believes she is receiving and Bob believes he is receiving ).
Eve computes and . Alice, not realizing that Eve is in the middle, also computes , and Bob computes .
When Alice sends a message to Bob, encrypted with , Eve intercepts it, deciphers it, encrypts it with , and sends it to Bob. Bob decrypts with 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 has a digital signature function with verification algorithm . For example, could produce an RSA or ElGamal signature, and checks that it is a valid signature for . The verification algorithms are compiled and made public by the trusted authority Trent, who certifies that is actually the verification algorithm for and not for Eve.
Suppose now that Alice and Bob want to establish a key to use in an encryption function . They proceed as in the Diffie-Hellman key exchange, but with the added feature of digital signatures:
They choose a large prime and a primitive root .
Alice chooses a random and Bob chooses a random .
Alice computes , and Bob computes .
Alice sends to Bob.
Bob computes .
Bob sends and to Alice.
Alice computes .
Alice decrypts to obtain .
Alice asks Trent to verify that is Bob’s verification algorithm.
Alice uses to verify Bob’s signature.
Alice sends to Bob.
Bob decrypts, asks Trent to verify that is Alice’s verification algorithm, and then uses 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 , 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.