9.2. Key Exchange

Classical cryptosystems and public key cryptosystems use different protocols.

9.2.1. 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 [796].

Bob now deciphers the message and uses k_session 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 k_session. If Eve records the second message in the exchange above, and the message enciphered under k_session, she can send Bob the message { k_session }k_Bob followed by the message enciphered under k_session. 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 [682].

In this protocol, rand₁ and rand₂ 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 rand₁ 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 k_Bob with anyone else, the message must have been enciphered by Cathy. This means that Cathy is vouching that she generated k_session 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 k_session 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 k_session), 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 rand₁ are present. This tells her that Cathy sent the second message (because it was enciphered with k_Alice, which only she and Cathy know) and that it was a response to the first message (because rand₁ 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 k_session, 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 [250] 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. Gong [368] adds that a party with a fast clock is also vulnerable, and simply resetting the clock does not eliminate the vulnerability.

The Otway-Rees protocol [706] corrects these problems^[1] by avoiding the use of timestamps.

^[1] Needham and Schroeder also supply a modification [683]; see Exercise 5.

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 k_Alice, and the random number rand₁ 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 rand₂ 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 k_session 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.

9.2.2. Kerberos

Kerberos [526, 872] uses the Needham-Schroeder protocol as modified by Denning and Sacco. A client, Alice, wants to use a server S. Kerberos requires her to use two servers to obtain a credential that will authenticate her to S. First, Alice must authenticate herself to the Kerberos system; then she must obtain a ticket to use S (see next paragraph). (This separates authentication of the user to the issuer of tickets and the vouching of identity to S.)

The basis of Kerberos is a credential known as the ticket. It contains^[2]

^[2] See Kohl and Neuman [526], Section 5.3.1, for a complete description of a ticket. We include only the parts that are relevant to our discussion.

T_Alice,Barnum = Barnum || {Alice || Alice address || valid time || k_Alice,Barnum}k_Barnum

In this ticket, k_Barnum is the key that Barnum shares with the authentication server, and k_Alice,Barnum is the session key that Alice and Barnum will share. The valid time is the time interval during which the ticket is valid, which is typically several hours. The ticket is the issuer's voucher for the identity of the requester of the service.

The authenticator contains the identity of the sender of a ticket and is used when Alice wants to show Barnum that the party sending the ticket is the same as the party to whom the ticket was issued. It contains^[3]

^[3] See Kohl and Neuman [526], Section 5.3.2, for a complete description of an authenticator. We include only the parts that are relevant to our discussion.

A_Alice,Barnum = {Alice || generation time || kt}k_Alice,Barnum

where k_Alice,Barnum is the session key that Alice and Barnum share, kt is an alternative session key, and the authenticator was created at generation time. Alice generates an authenticator whenever she sends a ticket. She sends both the ticket and the authenticator in the same message.

Alice's goal is to print a file using the service Guttenberg. The authentication server is Cerberus and the ticket-granting server is Barnum. The Kerberos (Version 5) protocol proceeds as follows.

At this point, Alice deciphers the first part of the message to obtain the key she will use to communicate with Barnum. Kerberos uses the user's password as the key, so if Alice enters her password incorrectly, the decipherment of the session key will fail. These steps occur only at login; once Alice has the ticket for the ticket-granting server Barnum, she caches it and uses it:

In these steps, Alice first constructs an authenticator and sends it, with the ticket and the name of the server, to Barnum. Barnum validates the request by comparing the data in the authenticator with the data in the ticket. Because the ticket is enciphered using the key Barnum shares with Cerberus, he knows that it came from a trusted source. He then generates an appropriate session key and sends Alice a ticket to pass on to Guttenberg. Step 5 repeats step 3, except that the name of the service is not given (because Guttenberg is the desired service). Step 6 is optional; Alice may ask that Guttenberg send it to confirm the request. If it is sent, t is the timestamp.

Bellovin and Merritt [72] discuss several potential problems with the Kerberos protocol. In particular, Kerberos relies on clocks being synchronized to prevent replay attacks. If the clocks are not synchronized, and if old tickets and authenticators are not cached, replay is possible. In Kerberos 5, authenticators are valid for 5 minutes, so tickets and authenticators can be replayed within that interval. Also, because the tickets have some fixed fields, a dictionary attack can be used to determine keys shared by services or users and the ticket-granting service or the authentication service, much as the WordPerfect cipher was broken (see the end of Section 8.2.2.1). Researchers at Purdue University used this technique to show that the session keys generated by Kerberos 4 were weak; they reported deciphering tickets, and finding session keys, within minutes [277].

9.2.3. Public Key Cryptographic Key Exchange and Authentication

Conceptually, public key cryptography makes exchanging keys very easy.

where e_Bob is Bob's public key. Bob deciphers the message and obtains the session key k_session. Now he and Alice can communicate securely, using a classical cryptosystem.

As attractive as this protocol is, it has a similar flaw to our original classical key exchange protocol. Eve can forge such a message. Bob does not know who the message comes from.

One obvious fix is to sign the session key.

where d_Alice is Alice's private key. When Bob gets the message, uses his private key to decipher the message. He sees the key is from Alice. Alice uses her public key to obtain the session key. Schneier [796] points out that Alice could also include a message enciphered with k_session.

These protocols assume that Alice has Bob's public key e_Bob. If not, she must get it from a public server, Peter. With a bit of ingenuity, Eve can arrange to read Bob's messages to Alice, and vice versa.

Eve now has the session key and can read any traffic between Alice and Bob. This is called a man-in-the-middle attack and illustrates the importance of identification and authentication in key exchange protocols. The man-in-the-middle attack works because there is no binding of identity to a public key. When presented with a public key purportedly belonging to Bob, Alice has no way to verify that the public key in fact belongs to Bob. This issue extends beyond key exchange and authentication. To resolve it, we need to look at the management of cryptographic keys.