Diffie-Hellman (DH) Key Exchange is one of the earliest Public Key Cryptosystem. The protocol uses a public key to securely exchange the private key.
Although it is a Public Key Cryptosystem, the main goal of this protocol is to exchange a key (a.k.a. shared secret), so the two users can then encrypt the information using symmetric encryption.
Diffie-Hellman Key Exchange Algorithm
Find below the algorithm for the keys exchange.
Example with values
Find below an example of the algorithms using q=11, a=2, Xa=7, and Xb=5.
We are using these numbers for simplicity. But remember the length of the key has an impact on the strength of the protocol.
To show the impact of the key size on this protocol, let’s try a brute force attack.
In this case, a brute force attack will try to find any of the two private keys Xa or Xb. Ya=7, YB=10, q=11, and a=2 are known as they are transmitted in plain text in an insecure network.
The attack will consist in finding a certain number s such that 2^e mod 11 = 7 (or 10).
See the code below (in Python).
a= 2
q= 11
Ya=7
Yb=10
for i in range(11):
if a**i % q == Ya or a**i % q == Yb:
print('key=', i)
From the example above, you can see it is very easy to break this protocol when the prime number chosen is small.
However, if you choose a big enough key size, it is computationally infeasible to carry out a brute force attack.
The recommended key size for Diffie-Helman Key Exchange is 2048 bit for the public key and 224 for the private key.
Limitation
The main problem with this protocol is that it is vulnerable to a Man-in-the-Middle (MITM) Attack. The reason for this is that the protocol does not authenticate the users. Therefore, it is easy for an attacker to pretend that is one of the two users that want to establish secure communication.
A solution to this limitation is to add the use of Digital Signature or Public Key Certificate to the key exchange algorithm.
Versions
The Anonymous Diffie-Hellman is the original algorithm. It was explained in the above sections.
The Fixed Diffie-Hellman uses a digital certificate (signed by a CA) to authenticate both users in the communication. In this way, it avoids the MITM attack. The public key in this certificate is fixed. Therefore, if the private key is compromised, all the communication done using the certificate will also be compromised.
The case of Ephemeral Diffie-Hellman uses temporary public keys. The temporary key is signed using the digital certificate private key. Because the public keys are created on each connection, if it is compromised only the communication session of that specific key will be compromised and, the previous sessions won’t be compromised. This is known as Perfect Forward Secrecy.
Summary
The classic (anonymous) Diffie-Hellman Key Exchange is vulnerable to a Man-in-the-Middle attack because it does not authenticate the users.
Fixed DH uses digital certificates to authenticate users. Therefore, it provides a higher level of secrecy.
Ephemeral Diffie-Hellman provides Perfect Forward Secrecy, being the recommended version of the algorithm to use.
Related posts