Diffie-Hellman – Secgroup Ca' Foscari

We have seen that sharing secret keys is fundamental for authenticating and running secure sessions. The Diffie-Hellman key agreement protocol allows for ‘magically’ establishing a fresh secret key between Alice and Bob with no need of pre-shared keys or secrets.

The scheme is based on discrete logarithms. We choose a prime number p and a generator a of $\{1, \ldots ,p-1\}$ . A generator a is a number such that $\{ a^1 \mod p, \ldots a^{p-1} \mod p\} = \{ 1, \ldots, p-1 \}$ . In other words, if we rise a to all the powers $1, \ldots ,p-1$ modulo n, we obtain all such numbers. In this sense, a can be used to generate the group. When this happens, we can define the discrete logarithm modulo p of any number $1 \leq b \leq p-1$ as follows: $log_a b$ is the power i such that $a^i \mod p = b$ . It is possible to prove that for any prime p there always exists at least one generator a [1, fact 2.132].

Computing the discrete logarithm modulo p is infeasible for a big prime p such that p-1 has at least a big prime factor (this is to prevent the use of the Pohlig–Hellman algorithm which works well only when prime factors of p-1 are small). Diffie-Hellman protocol for key agreement picks one of such big primes p and a generator a of $\{1, \ldots, p-1 \}$ . The prime p and the generator a are public. Alice and Bob generate two secrets $S_A, S_B$ and run the following protocol:

$\begin{array}{l} A \rightarrow B: a^{S_A} \mod p \\ B \rightarrow A: a^{S_B} \mod p \end{array}$

Alice and Bob compute the new key respectively as $(a^{S_B})^{S_A} \mod p$ and $(a^{S_A})^{S_B} \mod p$ , that clearly give the same value. Computing the secrets $S_A, S_B$ from the exchanged messages amounts to compute the discrete logarithm, that we have assumed to be infeasible. Thus an attacker eavesdropping the exchanged traffic will never be able to compute the new exchanged key.

An example of Diffie-Hellman generation of the parameters using openssl follows:

$ openssl dhparam 1024 -text
Generating DH parameters, 1024 bit long safe prime, generator 2
This is going to take a long time
.........................................................................................................
...................................+.....................................................................
....................+......................+.............................................................
..............+.............................+............+.......+................+.+....................
+.................+....................................................................................+.
........................................................................+.................+..............
.....................................................................................++*++*++*
    PKCS#3 DH Parameters: (1024 bit)
        prime:
            00:c8:f4:59:b0:86:fc:10:e6:ac:72:c5:69:d8:9c:
            4e:66:61:c6:c8:59:aa:ca:26:e5:12:51:7f:89:b8:
            6b:e6:db:3f:b6:28:e7:7c:09:63:ee:44:6a:b0:6d:
            b3:b5:de:0d:11:28:35:44:32:e6:99:bb:a5:bb:66:
            22:49:8c:a0:d0:97:68:be:b9:0b:5f:01:9f:93:39:
            9c:c6:1e:eb:b6:04:35:fc:3a:9a:6f:a0:b4:46:49:
            91:a6:57:2c:fd:51:50:44:b8:66:42:41:72:d1:c6:
            21:54:81:03:d5:8d:04:66:00:87:d1:02:b7:5f:45:
            0a:e2:09:0a:c4:ec:6c:5c:03
        generator: 2 (0x2)
-----BEGIN DH PARAMETERS-----
MIGHAoGBAMj0WbCG/BDmrHLFadicTmZhxshZqsom5RJRf4m4a+bbP7Yo53wJY+5E
arBts7XeDREoNUQy5pm7pbtmIkmMoNCXaL65C18Bn5M5nMYe67YENfw6mm+gtEZJ
kaZXLP1RUES4ZkJBctHGIVSBA9WNBGYAh9ECt19FCuIJCsTsbFwDAgEC
-----END DH PARAMETERS-----
$

Man-in-the-middle

Even if Diffie-Hellman protocol has the nice above property about key confidentiality, the fact it is not based on any pre-shared secret makes it completely vulnerable to active attackers that are able to intercept and introduce messages on the network. In particular, an attacker can mount a man-in-the-middle attack where he is able to impersonate Alice with Bob and Bob with Alice. This is easily achieved by establishing two different keys with them, so that he can be in the middle in the subsequent session. The attack works as follows:

$\begin{array}{cccccl} A & \rightarrow & E(B) & & &: a^{S_A} \mod p \\ A & \leftarrow & E(B) & & &: a^{S_E} \mod p \\ & & E(A) & \rightarrow & B &: a^{S_E} \mod p \\ & & E(A) & \leftarrow & B &: a^{S_B} \mod p \end{array}$

Now Alice and Bob respectively share with the attacker keys $k_s^1 = a^{S_AS_E} \mod p$ and $k_s^2 = a^{S_BS_E} \mod p$ . Next messages, encrypted under such keys, will all ‘pass through’ the attacker as follows:

$\begin{array}{cccccl} A & \rightarrow & E(B) & & &: E_{k_s^1}(M_A) \\ & & E(A) & \rightarrow & B &: E_{k_s^2}(M_A) \\ & & E(A) & \leftarrow & B &: E_{k_s^2}(M_B) \\ A & \leftarrow & E(B) & & &: E_{k_s^1}(M_B) \end{array}$

Alice and Bob believe to communicate in a secure, encrypted way, but the attacker is in fact decrypting and re-encrypting any message they exchange.

Summary. Diffie-Hellman protocol is secure only against passive attackers. The absence of any pre-shared secret makes it impossible to authenticate parties. An attacker can easily pretend to be one party and mount man-in-the-middle attacks, as shown above. This protocol can be made secure using digital signatures (so to provide authentication).

References

[1] A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography, CRC Press