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  

Previous

Table of Contents

Next

Chapter 8
Key Distribution and Key Agreement

8.1 Introduction

We have observed that public-key systems have the advantage over private-key systems that a secure channel is not needed to exchange a secret key. But, unfortunately, most public-key systems are much slower than private-key systems such as DES, for example. So, in practice, private-key systems are usually used to encrypt “long” messages. But then we come back to the problem of exchanging secret keys.

In this chapter, we discuss several approaches to the problem of establishing secret keys. We will distinguish between key distribution and key agreement. Key distribution is defined to be a mechanism whereby one party chooses a secret key and then transmits it to another party or parties. Key agreement denotes a protocol whereby two (or more) parties jointly establish a secret key by communicating over a public channel. In a key agreement scheme, the value of the key is determined as a function of inputs provided by both parties.

As our setting, we have an insecure network of n users. In some of our schemes, we will have a trusted authority (denoted by TA) that is reponsible for such things as verifying the identities of users, choosing and transmitting keys to users, etc.

Since the network is insecure, we need to protect against potential opponents. Our opponent, Oscar, might be a passive adversary, which means that his actions are restricted to eavesdropping on messages that are transmitted over the channel. On the other hand, we might want to guard against the possibility that Oscar is an active adversary. An active adversary can do various types of nasty things such as the following:

1.  alter messages that he observes being transmitted over the network

2.  save messages for reuse at a later time

3.  attempt to masquerade as various users in the network.

The objective of an active adversary might be one of the following:

1.  to fool U and V into accepting an “invalid” key as valid (an invalid key could be an old key that has expired, or a key chosen by the adversary, to mention two possibilities)

2.  to make U or V believe that they have exchanged a key with other when they have not.

The objective of a key distribution or key agreement protocol is that, at the end of the protocol, the two parties involved both have possession of the same key K, and the value of K is not known to any other party (except possibly the TA). Certainly it is much more difficult to design a protocol providing this type of security in the presence of an active adversary as opposed to a passive one.

We first consider the idea of key predistribution in Section 8.2. For every pair of users {U, V}, the TA chooses a random key K_U,V = K_V,U and transmits it “off-band” to U and V over a secure channel. (That is, the transmission of keys does not take place over the network, since the network is not secure.) This approach is unconditionally secure, but it requires a secure channel between the TA and every user in the network. But, of possibly even more significance is the fact that each user must store n - 1 keys, and the TA needs to transmit a total of keys securely (this is sometimes called the “n² problem”). Even for relatively small networks, this can become prohibitively expensive, and thus it is not really a practical solution.

In Section 8.2.1, we discuss an interesting unconditionally secure key predistribution scheme, due to Blom, that allows a reduction in the amount of secret information to be stored by the users in the network. We also present in Section 8.2.2 a computationally secure key predistribution scheme based on the discrete logarithm problem.

A more practical approach can be described as on-line key distribution by TA. In such a scheme, the TA acts as a key server. The TA shares a secret key K_U with every user U in the network. When U wishes to communicate with V, she requests a session key from the TA. The TA generates a session key K and sends it in encrypted form for U and V to decrypt. The well-known Kerberos system, which we describe in Section 8.3, is based on this approach.

If it is impractical or undesirable to have an on-line TA, then a common approach is to use a key agreement protocol. In a key agreement protocol, U and V jointly choose a key by communicating over a public channel. This remarkable idea is due to Diffie and Hellman, and (independently) to Merkle. We describe a few of the more popular key agreement protocols. A variation of the original protocol of Diffie and Hellman, modified to protect against an active adversary, is presented in Section 8.4.1. Two other interesting protocols are also discussed: the MTI scheme is presented in Section 8.4.2 and the Girault scheme is covered in Section 8.4.3.

8.2 Key Predistribution

In the basic method, the TA generates keys, and gives each key to a unique pair of users in a network of n users. As mentioned above, we require a secure channel between the TA and each user to transmit these keys. This is a significant improvement over each pair of users independently exchanging keys over a secure channel, since the number of secure channels required has been reduced from to n. But if n is large, this solution is not very practical, both in terms of the amount of information to be transmitted securely, and in the amount of information that each user must store securely (namely, the secret keys of the other other n - 1 users).

Thus, it is of interest to try to reduce the amount of information that needs to be transmitted and stored, while still allowing each pair of users U and V to be able to (independently) compute a secret key K_U,V. An elegant scheme to accomplish this, called the Blom Key Predistribution Scheme, is discussed in the next subsection.

Previous

Table of Contents

Next

---

Copyright © CRC Press LLC