3.3 Authentication and Key Exchange

These protocols combine authentication with key exchange to solve a general computer problem: Alice and Bob are on opposite ends of a network and want to talk securely. How can Alice and Bob exchange a secret key and at the same time each be sure that he or she is talking to the other and not to Mallory? Most of the protocols assume that Trent shares a different secret key with each participant, and that all of these keys are in place before the protocol begins.

The symbols used in these protocols are summarized in Table 3.1.

Wide-Mouth Frog

The Wide-Mouth Frog protocol [283,284] is probably the simplest symmetric key-management protocol that uses a trusted server. Both Alice and Bob share a secret key with Trent. The keys are just used for key distribution and not to encrypt any actual messages between users. Just by using two messages, Alice transfers a session key to Bob:

(1)  Alice concatenates a timestamp, Bob’s name, and a random session key and encrypts the whole message with the key she shares with Trent. She sends this to Trent, along with her name.

A,E_A(T_A,B,K)

(2)  Trent decrypts the message from Alice. Then he concatenates a new timestamp, Alice’s name, and the random session key; he encrypts the whole message with the key he shares with Bob. Trent sends to Bob:

E_B(T_B,A,K)

The biggest assumption made in this protocol is that Alice is competent enough to generate good session keys. Remember that random numbers aren’t easy to generate; it might be more than Alice can be trusted to do properly.

Yahalom

In this protocol, both Alice and Bob share a secret key with Trent [283,284].

(1)  Alice concatenates her name and a random number, and sends it to Bob.

A,R_A

(2)  Bob concatenates Alice’s name, Alice’s random number, his own random number, and encrypts it with the key he shares with Trent. He sends this to Trent, along with his name.

B,E_B(A,R_A,R_B)

(3)  Trent generates two messages. The first consists of Bob’s name, a random session key, Alice’s random number, and Bob’s random number, all encrypted with the key he shares with Alice. The second consists of Alice’s Zname and the random session key, encrypted with the key he shares with Bob. He sends both messages to Alice.

E_A(B,K,R_A,R_B),E_B(A,K)

(4)  Alice decrypts the first message, extracts K, and confirms that R_A has the same value as it did in step (1). Alice sends Bob two messages. The first is the message received from Trent, encrypted with Bob’s key. The second is R_B, encrypted with the session key.

E_B(A,K),E_K(R_B)

(5)  Bob decrypts the message encrypted with his key, extracts K, and confirms that R_B has the same value as it did in step (2).

At the end, Alice and Bob are each convinced that they are talking to the other and not to a third party. The novelty here is that Bob is the first one to contact Trent, who only sends one message to Alice.

Needham-Schroeder

This protocol, invented by Roger Needham and Michael Schroeder [1159], also uses symmetric cryptography and Trent.

(1)  Alice sends a message to Trent consisting of her name, Bob’s name, and a random number.

A,B,R_A

(2)  Trent generates a random session key. He encrypts a message consisting of a random session key and Alice’s name with the secret key he shares with Bob. Then he encrypts Alice’s random value, Bob’s name, the key, and the encrypted message with the secret key he shares with Alice. Finally, he sends her the encrypted message:

E_A(R_A,B,K,E_B(K,A))

(3)  Alice decrypts the message and extracts K. She confirms that RA is the same value that she sent Trent in step (1). Then she sends Bob the message that Trent encrypted in his key.

E_B(K,A)

(4)  Bob decrypts the message and extracts K. He then generates another random value, R_B. He encrypts the message with K and sends it to Alice.

E_K(R_B)

(5)  Alice decrypts the message with K. She generates R_B - 1 and encrypts it with K. Then she sends the message back to Bob.

E_K(R_B - 1)

(6)  Bob decrypts the message with K and verifies that it is R_B - 1.

All of this fussing around with R_A and R_B and R_B - 1 is to prevent replay attacks. In this attack, Mallory can record old messages and then use them later in an attempt to subvert the protocol. The presence of R_A in step (2) assures Alice that Trent’s message is legitimate and not a replay of a response from a previous execution of the protocol. When Alice successfully decrypts R_B and sends Bob R_B - 1 in step (5), Bob is ensured that Alice’s messages are not replays from an earlier execution of the protocol.