Diffie-Hellman key exchange protocol (800 words)

Diffie-Hellman key exchange protocol

For this Assignment, you will review the Diffie-Hellman key exchange protocol and describe how to address common attacks on that protocol. You will also perform some basic calculations.

To complete this Assignment:

For this Assignment, submit a single document with your answers to the following:

Review the Diffie-Hellman key exchange protocol discussed in the lecture and list some of the attacks on Diffie-Hellman.

Explain your solutions for avoiding such attacks.

Calculate the value of the symmetric key and the values of RA and RB in the Diffie-Helman Protocol for the set of given values. (see Notes1)

Note: The Individual Hand-In and the Individual Paper will be graded as a single assessment.

NOTES 1

Diffie-Hellman key agreement

The security of many cryptographic techniques depends on a challenging mathematical concept-the discrete log problem (Section 5.7.2 in the textbook): Compute the value x given g and (gx modulo p) where p is a large prime and g is number called the generator (see page 107 in the textbook). For example, let p = 97 and g = 5. Compute an x such that 5x = 35 (mod 97). The most obvious way to compute such an x is an exhaustive search. That is, try all values from 1 to 96. Since 532 = 35 (mod 97), you know that x = 32. However, for large values of p, an exhaustive search is almost impossible. There are, however, other methods, which are better than the exhaustive search, e.g. the famous index-calculus algorithm and the baby-step-giant-ste' algorithm. For a large prime p of 1024 bits in length, the currently known best algorithms for discrete logarithm problems still need to search a space of approximately 280. Thus it is still a tough problem using current technologies.

We can illustrate the Diffie-Hellman key exchange protocol (Section 5.7.2.2 Key Establishment on page 175 of the textbook) with an example. Suppose that p = 25307 and g = 2 are publicly known values. Alice and Bob establish an agreed secret key as follows:

1. Alice chooses a random integer RA= 3578 and sends Bob the value: (23578 mod 25307) = 6113. Note that this value 6113 can be computed very quickly from 2 and 3578 in approximately 1000 steps.

2. Bob chooses a random integer RB= 19956 and sends Alice the value: (219956 mod 25307) = 7984.

3. Alice computes the secret key K = (79843578 mod 25307) = 3694.

4. Bob computes K = (611319956 mod 25307) = 3694.

Thus Alice and Bob can easily compute the shared secret 3694. However, in order for Eve (the adversary) to compute the shared key 3694 (who knows p = 25307 and g = 2 and observed these communicated values 6113 and 7984), she has to compute RAfrom 6113 or RBfrom 7984. As you have seen, there are no efficient ways for Eve to do this. For the most part, she has to try all values between 1 and 25307 to get either RA or RB.