Understanding Diffie-Hellman Key Exchange Protocol

Diffie-Hellman (Key Exchange) Protocol Rocky K. C. Chang, 25 February 2011 1

Outline The basic foundation: multiplicative group modulo prime The basic Diffie-Hellman (DH) protocol The discrete logarithm problem The basic protocol is insecure: Spoofing attacks Subgroup attacks Use a safe prime approach to address the second insecurity issue. An enhanced DH protocol 2

Motivation for the DH protocol Using a secret-key cryptosystem, how many secret keys are needed for a group of n people to communicate? C(n, 2) = n(n 1)/2 = O(n2) Managing a large number of keys is another problem. With or without a trusted third party, such as a key server. Whitfield Diffie and Martin Hellman asked Whether this can be done more efficiently by having the encryption and decryption keys different. Came up the Diffie-Hellman (DH) protocol, which is a partial solution. Agree on a secret key over an insecure channel. 3

Multiplicative group modulo prime The DH protocol derives a secret key from Z*p, the multiplicative group modulo p. Z*p={1, 2, 3, , p 1} under modulo multiplication operations. p is a very large prime (e.g., 2000-4000 bits long). Z*p under modulo multiplication operations is a group. Closure, associativity, commutative The element 1 is the identity. Each member has a unique inverse. 4

For example, p = 7 Z*7 = {1, 2, 3, , 6} 1 s inverse is 1 2 s inverse is 4 3 s inverse is 5 4 s inverse is 2 5 s inverse is 3 6 s inverse is 6 Generally, 1 s inverse is 1 p 1 s inverse is p 1 (why?). There are methods to find the inverses for other elements between 1 and p 1. 5

Primitive elements There exists at least a primitive element in Z*p that can generate the entire Z*p by exponentiations. For Z*7, 3 is a primitive, because 30 mod 7 = 1, 31 mod 7 = 3, 32 mod 7 = 2, 33 mod 7 = 6, 34 mod 7 = 4, 35 mod 7 = 5, 36 mod 7 = 1, You can show that 5 is another primitive element. 6

For other elements: 1, 2, 4, 6, 40 mod 7 = 1, 41 mod 7 = 4, 42 mod 7 = 2, 43 mod 7 = 1, ------------------ 60 mod 7 = 1, 61 mod 7 = 6, 62 mod 7 = 1, 10 mod 7 = 1, 11 mod 7 = 1, ------------------ 20 mod 7 = 1, 21 mod 7 = 2, 22 mod 7 = 4, 23 mod 7 = 1, 7

Subgroups and order For any divisor of p 1, say d, there is a single subgroup of size d. For p = 7 again, p 1 = 6 and its divisors are 1, 2, 3, 6. A subgroup of size 1: {1} A subgroup of size 2: {1,6} A subgroup of size 3: {1,2,4} A subgroup of size 6: {1,2,3,4,5,6}. Order of an element Order of 1 is 1, because 11 mod 7 = 1. Order of 6 is 2, because 62 mod 7 = 1. Order of 2 and 4 is 3. Order of 3 and 5 is 6. 8

The basic DH protocol Agree on a large prime p and a primitive element g in Z*p (g is also called a generator). Both p and g are not secrets. Alice (Bob) chooses a random x (y) in Z*p(1, 2, , p 1) and computes gx mod p (gy mod p). Send the result to Bob (Alice), and the result is not a secret. Alice computes the secret key k as (gy mod p)x mod p = gxy mod p. Bob computes the secret key k as (gx mod p)y mod p = gxy mod p. Note that k Z*p. 9

The basic DH protocol Alice Bob Randomly pick x from Z* p gx mod p Randomly pick y from Z* p gy mod p k (gy)x mod p k (gx)y mod p 10

The discrete logarithm problem Given the knowledge of p, g, gx mod p, and gy mod p, how does an attacker find gxy mod p? The best method known is to solve the discrete logarithm problem. Given X = gx mod p, g, and p, find x (x = loggX). Analogous to computing logarithm in real numbers. With x and gy mod p, one can compute gxy mod p. 11

For example, p = 13 and g = 2 is a primitive element Given gx mod p = 1, x = 0 Given gx mod p = 2, x = 1 Given gx mod p = 3, x = 4 Given gx mod p = 4, x = 2 Solving the discrete logarithm problem Exhaustive search by computing g1, g2, g3, , until gx is found. Precompute all possible values of gi, and then sort the list of ordered pairs (i, gi) with respect to the second component. Perform a binary search for gx. Many other smart algorithms 12

A spoofing attack The basic DH protocol does not protect against the man- in-the-middle attack. Alice cannot authenticate whether the other side is Bob, and vice versa. Instead, Eve establishes secret keys with Alice and Bob. Eve can relay the message so that both sides are not aware of the attack. Need authentication mechanisms. 13

A spoofing attack Alice Eve Bob Randomly pick x from Z* p gx mod p Randomly pick v from Z* p gv mod p Randomly pick y from Z* p gy mod p Randomly pick w from Z* p gw mod p k (gw)x mod p k (gw)x mod p k' (gv)y mod p k' (gv)y mod p 14

Attacks on reducing the set of keys Problem 1: Reducing the order to 1. Eve can intercept gx mod p and gy mod p, and replace them with 1. Therefore, k = 1. Problem 2: Reducing the order to significantly less than p 1. g may not be a primitive element of Z*p, therefore which may have a small order. Eve intercepts gx mod p and replaces it with h where h has a small order. 15

Avoiding small subgroups If p is a large prime, then p 1 is always even. Therefore, There is a subgroup of size 1. There is a subgroup of size p 1. There are possibly other subgroups, some of them may be too small to be secure. Use a safe prime to avoid small subgroups other than the one with size 2, which always present. 16

A safe prime approach A safe prime is a large enough prime p = 2q + 1, where q is also a prime. p 1 s divisors are 1, 2, q, 2q. Reason for having q as a prime? Now, Z*p for such a safe prime has the following subgroups. {1} {1, p 1} A subgroup of size q A subgroup of size 2q (the full group) The first 2 subgroups are easy to avoid. Use either the subgroup of size q or the full group. 17

Why the full group is not secure? Consider the set of numbers in Z*p that can be written as a square of another number in Z*p. For example, p = 7 12 mod 7 = 1 22 mod 7 = 4 32 mod 7 = 2 42 mod 7 = 2 52 mod 7 = 4 62 mod 7 = 1 {1, 2, 4} is a set of squares for p = 7. Note that it is a subgroup. {3, 5, 6} is a set of nonsquares. Exactly half the numbers in 1, , p 1 are squares. Note that any generator of the entire group must be a nonsquare (why?). gn is a square (nonsquare) when n is even (odd). 18

This is the problem: Assume that g is a nonsquare and Alice sends out gx mod p to Bob. That is, use the full group. Assume that Eve can determine whether g and gx mod p are squares or not. In this case, g is a nonsquare. What can Eve know about x from g and gx mod p? If gx mod p is a square, then x is even. If gx mod p is a nonsquare, then x is odd. That is, Eve knows about the last bit of x. 19

Use the subgroup of size q The solution is to use the subgroup of size q, which contains the set of squares. A square will only generate a square. For p = 7, we use the subgroup {1, 2, 4}. To sum up: Choose (p, q) such that p = 2q + 1, and both p and q are prime. Choose a random number in the range [2, p 2] and set g = 2 mod p. Make sure g 1 and g p 1. In other words, Alice and Bob will agree on (p, q, g) at the beginning of the DH protocol. 20

The final DH protocol Alice Bob Exchange and check (p, q, g) Randomly pick x from {1, , q-1}. X = gx mod p Check X. Randomly pick y from {1, , q-1}. Y = gy mod p Check Y. k Xy mod p k Yx mod p 21

Summary The DH protocol is based on the difficulty of solving the discrete logarithm problem. However, with a trapdoor (x or y), the computation of the key becomes very easy. There are other public-key cryptosystems based on the discrete logarithm problem, such as the ElGamal algorithm and Elliptic Curves. We will revisit the DH protocol in the Internet Key Exchange protocol. Cookies for denial-of-service attacks Authentication schemes for the man-in-the-middle attack. 22

Acknowledgments The notes are prepared mostly based on N. Ferguson and B. Schneier, Practical Cryptography, Wiley, 2003. D. Stinson, Cryptography: Theory and Practice, Chapman & Hall/CRC, Second Edition, 2002. 23