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

We will describe an authenticated key agreement protocol which is a modification of Diffie-Hellman Key Exchange. The protocol assumes a publicly known prime p and a primitive element α, and it makes use of certificates. Each user U will have a signature scheme with verification algorithm ver_U and signing algorithm sig_U. The TA also has a signature scheme with public verification algorithm ver_TA. Each user U has a certificate

where ID(U) is identification information for U.

Figure 8.6 Simplified Station-to-station Protocol

The authenticated key agreement known as the Station-to-station Protocol (or STS for short) is due to Diffie, Van Oorschot, and Wiener. The protocol we present in Figure 8.6 is a slight simplification; it can be used in such a way that it is conformant with the ISO 9798-3 protocols.

The information exchanged in the simplified STS protocol (excluding certificates) is illustrated as follows:

Let’s see how this protects against an intruder-in -the-middle attack. As before, W will intercept and replace it with . W then receives from V. He would like to replace with as before. However, this means that he must also replace by . Unfortunately for W, he cannot compute V’s signature on since he doesn’t know V’s signing algorithm sig_V. Similarly, W is unable to replace by because he does not know U’s signing algorithm.

This is illustrated in the following diagram:

It is the use of signatures that thwarts the intruder-in-the-middle attack.

The protocol, as described in Figure 8.6, does not provide key confirmation. However, it is easy to modify so that it does, by defining

in step 4 and defining

in step 6. (As in Kerberos, we obtain key confirmation by encrypting a known quantity using the new session key.) The resulting protocol is known as the Station-to-station Protocol. We leave the remaining details for the interested reader to fill in.

8.4.2 MTI Key Agreement Protocols

Matsumoto, Takashima, and Imai have constructed several interesting key agreement protocols by modifying Diffie-Hellman Key Exchange. These protocols, which we call MTI protocols, do not require that U and V compute any signatures. They are two-pass protocols since there are only two separate transmissions of information performed (one from U to V and one from V to U). In contrast, the STS protocol is a three-pass protocol.

We present one of the MTI protocols. The setting for this protocol is the same as for Diffie-Hellman Key Predistribution. We assume a publicly known prime p and a primitive element α. Each user U has an ID string, ID(U), a secret exponent a_U (0 ≤ a_U ≤ p - 2), and a corresponding public value

The TA has a signature scheme with a (public) verification algorithm ver_TA and a secret signing algorithm sig_TA.

Figure 8.7 Matsumoto-Takashima-Imai Key Agreement Protocol

Each user U will have a certificate

where b_U is formed as described above.

We present the MTI key agreement protocol in Figure 8.7. At the end of the protocol, U and V have both computed the same key

We give an example to illustrate this protocol.

Example 8.3

Suppose p = 27803 and α = 5 are publicly known. Assume U chooses a_U = 21131; then she will compute

which is placed on her certificate. As well, assume V chooses a_V = 17555. Then he will compute

which is placed on his certificate.

Now suppose that U chooses r_U = 169; then she will send the value

to V. Suppose that V chooses r_V = 23456; then he will send the value

to U.

Now U can compute the key

and V can compute the key

Thus U and V have computed the same key.

The information transmitted during the protocol is depicted as follows:

Let’s look at the security of the scheme. It is not too difficult to show that the security of the MTI protocol against a passive adversary is exactly the same as the Diffie-Hellman problem — see the exercises. As with many protocols, proving security in the presence of an active adversary is problematic. We will not attempt to prove anything in this regard, and we limit ourselves to some informal arguments.

Here is one threat we might consider: Without the use of signatures during the protocol, it might appear that there is no protection against an intruder-in-the-middle attack. Indeed, it is possible that W might alter the values that U and V send each other. We depict one typical scenario that might arise, as follows:

In this situation, U and V will compute different keys: U will compute

while V will compute

However, neither of the key computations of U or V can be carried out by W, since they require knowledge of the secret exponents a_U and a_V, respectively. So even though U and V have computed different keys (which will of course be useless to them), neither of these keys can be computed by W (assuming the intractibility of the Discrete Log problem). In other words, both U and V are assured that the other is the only user in the network that could compute the key that they have computed. This property is sometimes called implicit key authentication.

Table of Contents