Alice and Bob can communicate over an insecure channel. By insecure, we mean that there are eavesdroppers who can read the messages exchanged on this channel. How can Alice and Bob agree on a secret key in such a setting? One way would be to use the Diffie-Hellman key exchange.
Diffie-Hellman is an asymmetric encryption algorithm. It allows the exchange of a secret over a public channel. We will skip the modular arithmetic background and provide a simple numeric example. We will need two mathematical operations: power and modulus. x__p, i.e., x raised to the power p, is x multiplied by itself p times. Furthermore, x mod m, i.e., x modulus m, is the remainder of the division of x by m.
- Alice and Bob agree on q and g. For this to work, q should be a prime number, and g is a number smaller than q that satisfies certain conditions. (In modular arithmetic, g is a generator.) In this example, we take q = 29 and g = 3.
- Alice chooses a random number a smaller than q. She calculates A = (g__a) mod q. The number a must be kept a secret; however, A is sent to Bob. Let’s say that Alice picks the number a = 13 and calculates A = 313%29 = 19 and sends it to Bob.
- Bob picks a random number b smaller than q. He calculates B = (g__b) mod q. Bob must keep b a secret; however, he sends B to Alice. Let’s consider the case where Bob chooses the number b = 15 and calculates B = 315%29 = 26. He proceeds to send it to Alice.
- Alice receives B and calculates k__e__y = B__a mod q. Numeric example k__e__y = 2613 mod 29 = 10.
- Bob receives A and calculates k__e__y = A__b mod q. Numeric example k__e__y = 1915 mod 29 = 10.
We can see that Alice and Bob reached the same key.
Although an eavesdropper has learned the values of q, g, A, and B, they won’t be able to calculate the secret k__e__y that Alice and Bob have exchanged. The above steps are summarized in the figure below.
Although the numbers we have chosen make it easy to find a and b, even without using a computer, real-world examples would select a q of 256 bits in length. In decimal numbers, that’s 115 with 75 zeroes to its right (I don’t know how to read that either, but I was told it is read as 115 quattuorvigintillion). Such a large q will make it infeasible to find a or b despite knowledge of q, g, A, and B.
Let’s take a look at actual Diffie-Hellman parameters. We can use openssl to generate them; we need to specify the option dhparam to indicate that we want to generate Diffie-Hellman parameters along with the specified size in bits, such as 2048 or 4096.
In the console output below, we can view the prime number P and the generator G using the command openssl dhparam -in dhparams.pem -text -noout. (This is similar to what we did with the RSA private key.)
Terminal
`user@TryHackMe$ openssl dhparam -out dhparams.pem 2048 Generating DH parameters, 2048 bit long safe prime [...] $ openssl dhparam -in dhparams.pem -text -noout DH Parameters: (2048 bit) P: 00:82:3b:9d:b5:29:31:f8:12:fe:21:e1:90:30:37: ac:d2:48:41:f7:d7:55:e5:d2:5d:dd:87:67:9e:bd: b3:97:df:05:a9:d2:d9:56:4f:66:b5:d9:d8:65:06: 58:c3:8f:b3:0e:30:d2:9a:0b:c3:0a:56:8d:fc:0f: f2:e2:9e:4f:16:16:93:4e:b9:a4:c3:9c:09:2d:48: a2:ec:b6:97:92:63:a3:b4:75:36:3f:51:77:ca:ac: 44:6d:99:eb:4d:4a:97:d5:4b:52:c8:07:f8:16:30: 37:d3:b2:47:30:e6:4e:bc:6a:53:d1:9b:6a:4d:91: 7a:4b:4f:af:3b:f0:ce:b9:ed:91:4d:8b:52:5a:3f: bb:6b:06:ae:32:95:7d:53:da:9b:ce:b0:ec:7d:81: 25:05:d8:ce:ca:76:e7:d1:5a:31:13:d2:9f:62:b4: d5:ad:7d:cd:c9:ab:3d:28:e3:92:27:9f:f3:66:a0: be:61:49:cc:47:21:d8:e0:2c:e8:c6:35:4b:2f:ba: 35:36:8f:bb:41:c6:89:b2:60:3c:62:bb:fe:bf:59: d3:7f:05:69:55:dc:61:1b:b4:bb:68:fa:65:1e:2e: 46:2f:2d:21:62:d1:9f:a0:2b:aa:81:df:3a:f9:7d: 0b:9d:0e:47:68:01:4f:6e:81:cc:4c:2a:91:fc:8c: f4:6f G: 2 (0x2)`
Diffie-Hellman key exchange algorithm allows two parties to agree on a secret over an insecure channel. However, the discussed key exchange is prone to a Man-in-the-Middle (MitM) attack; an attacker might reply to Alice pretending to be Bob and reply to Bob pretending to be Alice.