Classical Cryptographic Key Exchange and Authentication

Suppose Alice and Bob wish to communicate. If they share a common key, they can use a classical cryptosystem. But how do they agree on a common key? If Alice sends one to Bob, Eve the eavesdropper will see it and be able to read the traffic between them.

To avoid this bootstrapping problem, classical protocols rely on a trusted third party, Cathy. Alice and Cathy share a secret key, and Bob and Cathy share a (different) secret key. The goal is to provide a secret key that Alice and Bob share. The following simple protocol provides a starting point.

Bob now deciphers the message and uses ksession to communicate with Alice.

This particular protocol is the basis for many more sophisticated protocols. However, Bob does not know to whom he is talking. Assume that Alice sends Bob a message (such as "Deposit $500 in Dan's bank account today") enciphered under ksession. If Eve records the second message in the exchange above, and the message enciphered under ksession, she can send Bob the message { ksession }kBob followed by the message enciphered under ksession. Bob will not know who is sending it.

Avoiding problems such as this replay attack adds considerable complexity. Key exchange protocols typically add, at a minimum, some sort of authentication and defense against replay attack. One of the best-known such protocols is the Needham-Schroeder protocol.

In this protocol, rand1 and rand2 are two numbers generated at random, except that they cannot repeat between different protocol exchanges. These numbers are called nonces. (If Alice begins the protocol anew, her rand1 in the first exchange will not have been used there before.) The basis for the security of this protocol is that both Alice and Bob trust Cathy.

When Bob receives the third message and deciphers it, he sees that the message names Alice. Since he could decipher the message, the message was enciphered using a key he shares only with Cathy. Because he trusts Cathy not to have shared the key kBob with anyone else, the message must have been enciphered by Cathy. This means that Cathy is vouching that she generated ksession so Bob could communicate with Alice. So Bob trusts that Cathy sent the message to Alice, and that Alice forwarded it to him.

However, if Eve recorded the message, she could have replayed it to Bob. In that case, Eve would not have known the session key, so Bob sets out to verify that his unknown recipient does know it. He sends a random message enciphered by ksession to Alice. If Eve intercepts the message, she will not know what to return; should she send anything, the odds of her randomly selecting a message that is correct is very low and Bob will detect the attempted replay. But if Alice is indeed initiating the communication, when she gets the message she can decipher it (because she knows ksession), apply some fixed function to the random data (here, decrement it by 1), and encipher the result and return it to Bob. Then Bob will be sure he is talking to Alice.

Alice needs to convince herself that she is talking to Bob, also. When she receives the second message from Cathy, she deciphers it and checks that Alice, Bob, and rand1 are present. This tells her that Cathy sent the second message (because it was enciphered with kAlice, which only she and Cathy know) and that it was a response to the first message (because rand1 is in both the first and second messages). She obtains the session key and forwards the rest to Bob. She knows that only Bob has ksession, because only she and Bob can read the messages containing that key. So when she receives messages enciphered with that key, she will be sure that she is talking to Bob.

The Needham-Schroeder protocol assumes that all cryptographic keys are secure. In practice, session keys will be generated pseudorandomly. Depending on the algorithm used, it may be possible to predict such keys. Denning and Sacco assumed that Eve could obtain a session key and subverted the protocol. Assume that the protocol above took place. Then:

Now Bob thinks he is talking to Alice. He is really talking to Eve.

Denning and Sacco suggest using timestamps to enable Bob to detect this replay. Applying their method to the Needham-Schroeder protocol yields

where T is a timestamp. When Bob gets the message in step 3, he rejects it if the timestamp is too old (too old being determined from the system in use). This modification requires synchronized clocks. Denning and Sacco note that a principal with a slow clock is vulnerable to a replay attack. A party with a fast clock is also vulnerable, and simply resetting the clock does not eliminate the vulnerability.

The Otway-Rees protocol corrects these problems by avoiding the use of timestamps.

The purpose of the integer num is to associate all messages with a particular exchange. Again, consider the elements of the protocol.

When Alice receives the fourth message from Bob, she checks that the num agrees with the num in the first message that she sent to Bob. If so, she knows that this is part of the exchange. She also trusts that Cathy generated the session key because only Cathy and Alice know kAlice, and the random number rand1 agrees with what Alice put in the enciphered portion of the message. Combining these factors, Alice is now convinced that she is talking to Bob.

When Bob receives the message from Cathy, he determines that the num corresponds to the one he received from Alice and sent to Cathy. He deciphers that portion of the message enciphered with his key, and checks that rand2 is what he sent. He then knows that Cathy sent the reply, and that it applies to the exchange with Alice.

Because no timestamps are used, the synchronization of the system clocks is irrelevant. Now suppose that Eve acquired an old session key and the message in 3.

She forwards that message to Alice. Alice immediately rejects it if she has no ongoing key exchanges with Bob. If she does, and num does not match, she rejects Eve's message. The only way Eve could impersonate Bob is if she acquired ksession for an ongoing exchange, recorded the third message, and resent the relevant portion to Alice before Bob could do so. In that case, however, Eve could simply listen to the traffic, and no replay would be involved.