Cryptography: Theory and Practice:Key Distribution and Key Agreement

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

As mentioned above, the TA generates K, T, and L in step 2. In step 3, this information, along with ID(V), is encrypted using the key K_U shared by U and the TA to form m₁. Also, K, T, L, and ID(U) are encrypted using the key K_v shared by V and the TA to form m₂. Both these encrypted messages are sent to U.

U can use her key to decrypt m₁, and thus obtain K, T, and L. She will verify that the current time is in the interval from T to T + L. She can also check that the session key K has been issued for her desired communicant V by verifying the information ID(V) decrypted from m₁.

Next, U will relay m₂ to V. As well, U will use the new session key K to encrypt T and ID (U) and send the resulting message m₃ to V.

When V receives m₂ and m₃ from U, he decrypts m₂ to obtain T, K, L and ID(U). Then he uses the new session key K to decrypt m₃ and he verifies that T and ID(U), as decrypted from m₂ and m₃, are the same. This ensures V that the session key encrypted within m₂ is the same key that was used to encrypt m₃. Then V uses K to encrypt T + 1, and sends the result back to U as message m₄.

When U receives m₄, she decrypts it using K and verifies that the result is T + 1. This ensures U that the session key K has been successfully transmitted to V, since K was needed in order to produce the message m₄.

It is important to note the different functions of the messages transmitted in this protocol. The messages m₁ and m₂ are used to provide secrecy in the transmission of the session key K. On the other hand, m₃ and m₄ are used to provide key confirmation, that is, to enable U and V to convince each other that they possess the same session key K. In most key distribution schemes, (session) key confirmation can be included as a feature if it is not already present. Usually this is done in a similar fashion as it is done in Kerberos, namely by using the new session key K to encrypt known quantities. In Kerberos, U uses K to encrypt ID (U) and T, which are already encrypted in m₂. Similarly, V uses K to encrypt T + 1.

The purpose of the timestamp T and lifetime L is to prevent an active adversary from storing “old” messages for retransmission at a later time (this is called a replay attack). This method works because keys are not accepted as valid once they have expired.

Figure 8.5 Diffie-Hellman Key Exchange

One of the drawbacks of Kerberos is that all the users in the network should have synchronized clocks, since the current time is used to determine if a given session key K is valid. In practice, it is very difficult to provide perfect synchronization, so some amount of variation in times must be allowed.

8.4 Diffie-Hellman Key Exchange

If we do not want to use an on-line key server, then we are forced to use a key agreement protocol to exchange secret keys. The first and best known key agreement protocol is Diffie-Hellman Key Exchange. We will assume that p is prime, α is a primitive element of , and that the values p and α are publicly known. (Alternatively, they could be chosen by U and communicated to V in the first step of the protocol.) Diffie-Hellman Key Exchange is presented in Figure 8.5.

At the end of the protocol, U and V have computed the same key

This protocol is very similar to Diffie-Hellman Key Predistribution described earlier. The difference is that the exponents a_U and a_V of users U and V (respectively) are chosen anew each time the protocol is run, instead of being fixed. Also, in this protocol, both U and V are assured of key freshness, since the session key depends on both random exponents a_U and a_V.

8.4.1 The Station-to-station Protocol

Diffie-Hellman Key Exchange is supposed to look like this:

Unfortunately, the protocol is vulnerable to an active adversary who uses an intruder-in-the-middle attack. There is an episode of The Lucy Show in which Vivian Vance is having dinner in a restaurant with a date, and Lucille Ball is hiding under the table. Vivian and her date decide to hold hands under the table. Lucy, trying to avoid detection, holds hands with each of them and they think they are holding hands with each other.

An intruder-in-the-middle attack on the Diffie-Hellman Key Exchange protocol works in the same way. W will intercept messages between U and V and substitute his own messages, as indicated in the following diagram:

At the end of the protocol, U has actually established the secret key with W, and V has established a secret key with W. When U tries to encrypt a message to send to V, W will be able to decrypt it but V will not. (A similar situation holds if V sends a message to U.)

Clearly, it is essential for U and V to make sure that they are exchanging messages with each other and not with W. Before exchanging keys, U and V might carry out a separate protocol to establish each other’s identity, for example by using one of the identification schemes that we will describe in Chapter 9. But this offers no protection against an intruder-in-the-middle attack if W simply remains inactive until after U and V have proved their identities to each other. Hence, the key agreement protocol should itself authenticate the participants’ identities at the same time as the key is being established. Such a protocol will be called authenticated key agreement.

Table of Contents