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 illustrate the algorithm with a small example.

Example 8.2

Suppose p = 25307 and α = 2 are publicly known (p is prime and α is a primitive root modulo p). Suppose U chooses a_U = 3578. Then she computes

which is placed on her certificate. Suppose V chooses a_V = 19956. Then he computes

Figure 8.2 Diffie-Hellman Key Predistribution

which is placed on his certificate.

Now U can compute the key

and V can compute the same key

Let us think about the security of this scheme in the presence of a passive or active adversary. The signature of the TA on users’ certificates effectively prevents W from altering any information on someone else’s certificate. Hence we need only worry about passive attacks. So the pertinent question is: Can a user W compute K_U,V if W ≠ U, V? In other words, given α^au mod p and α^av mod p (but not a_U nor a_V), is it feasible to compute α^aUaV mod p? This problem is called the Diffie-Hellman problem, and it is formally defined (using an equivalent but slightly different presentation) in Figure 8.3. It is clear that Diffie-Hellman Key Predistribution is secure against a passive adversary if and only if the Diffle-Hellman problem is intractible.

Figure 8.3 The Diffie-Hellman problem

If W could determine a_U from b_U, or if he could determine a_V from b_V, then he could compute K_U,V exactly as U (or V) does. But both these computations are instances of the Discrete Log problem. So, provided that the Discrete Log problem in is intractible, Diffie-Hellman Key Predistribution is secure against this particular type of attack. However, it is an unproven conjecture that any algorithm that solves the Diffie-Hellman problem could also be used to solve the Discrete Log problem. (This is very similar to the situation with RSA, where it is conjectured, but not proved, that breaking RSA is polynomially equivalent to factoring.)

By the remarks made above, the Diffie-Hellman problem is no more difficult than the Discrete Log problem. Although we cannot say precisely how difficult this problem is, we can relate its security to that of another cryptosystem we have already studied, namely the ElGamal Cryptosystem.

THEOREM 8.2

Breaking the ElGamal Cryptosystem is equivalent to solving the Diffie-Hellman problem.

PROOF First we recall how ElGamal encryption and decryption work. The key is K = (p, α, a, β), where β = α^a mod p (a is secret and p, α, and β are public). For a (secret) random number ,

where

and

For ,

Suppose we have an algorithm A to solve the Diffie-Hellman problem, and we are given an ElGamal encryption (y₁, y₂). We will apply the algorithm A with inputs p, α, y₁, and β. Then, we obtain the value

Then, the decryption of (y₁, y₂) can easily be computed as

Conversely, suppose we have an algorithm B that performs ElGamal decryption. That is, B takes as inputs p, α, β, y₁, and y₂, and computes the quantity

Now, given inputs p, α, β, and γ for the Diffie-Hellman problem, it is easy to see that

as desired.

8.3 Kerberos

In the key predistribution methods we discussed in the previous section, each pair of users can compute one fixed key. If the same key is used for a long period of time, there is a danger that it might be compromised. Thus it is often preferable to use an on-line method in which a new session key is produced every time a pair of users want to communicate (this property is called key freshness).

If on-line key distribution is used, there is no need for any network user to store keys to communicate with other users (each user will share a key with the TA, however). Session keys will be transmitted on request by the TA. It is the responsibility of the TA to ensure key freshness.

Kerberos is a popular key serving system based on private-key cryptography. In this section, we give an overview of the protocol for issuing session keys in Kerberos. Each user U shares a secret DES key K_U with the TA. In the most recent version of Kerberos (version V), all messages to be transmitted are encrypted using cipher block chaining (CBC) mode, as described in Section 3.4.1.

Figure 8.4 Transmission of a session key using Kerberos

As in Section 8.2.2, ID(U) will denote public identification information for user U. When a request for a session key is sent to the TA, the TA will generate a new random session key K. Also, the TA will record the time at which the request is made as a timestamp, T, and specify the lifetime, L, during which K will be valid. That is, the session key K is to be regarded as a valid key from time T to time T + L. All this information is encrypted and transmitted to U and (eventually) to V. Before going into more details, we will present the protocol in Figure 8.4.

The information transmitted in the protocol is illustrated in the following diagram:

We will now explain what is going on in the various steps of the protocol. Although we have no formal proof that Kerberos is “secure” against an active adversary, we can at least give some informal motivation of the features of the protocol.

Table of Contents