7.4 Security of Diffie-Hellman key exchange

The security of the Diffie-Hellman protocol relies on the following three assumptions:

• The discrete logarithm problem is hard in the chosen group 𝔾
• The Diffie-Hellman problem is hard in the chosen group 𝔾
• The public keys of Alice and Bob are authentic

We will discuss each of these assumptions in turn.

7.4.1 Discrete logarithm problem

If Eve is passively eavesdropping on the protocol exchange shown in Figure 7.1, she sees the generator g and the public key values A and B coming from Alice and Bob, respectively. This means if Eve could efficiently solve the discrete logarithm problem in group 𝔾, she could recover both private keys α and β. Armed with this knowledge, she could also compute the shared secret of Alice and Bob.

As discussed previously, we must ensure that the discrete logarithm problem is hard in 𝔾, so that an attacker cannot derive the private keys or the shared secret. For 𝔽p∗ this means that p must be a large prime (that is, p ≥ 22048) and p − 1 must not have many small divisors. Ideally, p is a safe prime.

While there is no formal mathematical proof for the discrete logarithm problem’s intractability, mathematicians have strong reason to believe this is the case. Because of its role in cryptography, the discrete logarithm problem has attracted many researchers and has been extensively studied for the past 50 years. Yet, no one has so far been able to come up with an algorithm for solving this problem in polynomial time – at least not on conventional computers.

7.4.2 The Diffie-Hellman problem

There is another way Eve could attack a Diffie-Hellman key exchange. From observing A = gα and B = gβ, she might somehow figure out the shared secret K = gαβ. For this, she would need to solve the generalized Diffie-Hellman problem, which is defined like this:

Generic Diffie-Hellman problem

• Given: A finite cyclic group G, a generator g of 𝔾, and group elements A = gα and B = gβ
• Sought: K = gαβ

If we are working specifically in the familiar group 𝔽p∗ = {1,2,…,p− 1}, where p is a prime number, the Diffie-Hellman problem looks like this:

Specific Diffie-Hellman problem

• Given: A prime p, a generator g, and elements A = gα (mod p) and B = gβ (mod p)
• Sought: K = gαβ (mod p)

The Diffie-Hellman problem closely resembles the discrete logarithm problem, yet their exact relationship is not entirely clear. However, we can say this much: if it were possible to efficiently compute the discrete logarithms in G, then we could use this procedure to determine α from gα (mod p) and subsequently compute Bα = gαβ. Therefore, if the discrete logarithm problem is not hard, then the Diffie-Hellman problem isn’t hard either. By using a logical operation called contraposition, we can deduce that if the Diffie-Hellman problem is hard, then the discrete logarithm problem must be hard as well. Moreover, nobody has yet found a faster way to solve the Diffie-Hellman problem than by solving the discrete logarithm problem. For the time being, the hardness of the two problems is considered equivalent.

In addition to Diffie-Hellman key agreement, computational hardness of the Diffie-Hellman problem is also fundamental for the security of the ElGamal asymmetric encryption scheme. We will cover the ElGamal scheme in more detail later on in this chapter.