Diffie Hellman Key Exchange

When two persons want to exchange a secret message over an insecure medium, they could meet once and decide on a secret encryption method and a secret key they want to use.

However, keeping an algorithm secret isn’t secure at all and applying the principle of meeting eachother to modern client-server communication is inpractical.

The Diffie-Hellman Key Exchange is a clever way of getting rid of this problem. It is more an algorithm to generate a key than actually exchange the key, but it serves the purpose of letting each communication partner know how to encrypt or decrypt a message without letting a man in the middle know the key.

Algorithm

1. The client and the server publicly exchange a prime number \(p\) and a basis \(b\). Every attacker would know these numbers too.

2. The client now chooses a secret exponent \(c\) and nobody but the client itself will know this key. \(c\) must satisfy \(gcd(c, b)=1\).

3. The server now chooses a secret exponent \(s\) and nobody but the server itself will know this key. \(s\) must satisfy \(gcd(s, b)=1\).

4. The client now calculates \(i=b^c\pmod{p}\) and sends it to the server. The server calculates \(j=b^s\pmod{p}\) and sends it to the client. An attacker would also have \(i\) and \(j\).

5. The client now takes \(j\) from the server and calculates \(j^c\pmod{p}\) and the server takes \(i\) from the client and calculates \(i^s\pmod{p}\). The result of both calculations is the same and can now be used as the secret key for the message.

In practice, the prime \(p\) and the base \(b\) are chosen to be quite large and using exponentiation by squaring, the complexity of the algorithm is logarithmic in the exponent.

The algorithm works, since \(i=b^c\pmod{p}\) and \(j=b^s\pmod{p}\) and the client therefore calculates \(j^c\equiv(b^s)^c\equiv b^{sc}\pmod{p}\) and the server calculates equivalently \(i^s\equiv(b^c)^s\equiv b^{cs}\pmod{p}\).

This is quite interesting. An attacker knows \(b, p\) and also \(i\) and \(j\) but since \(c\) and \(s\) is unknown, \(b^{sc}\) can’t be figured out. This is because \(i=b^c\pmod{p}\) would require the logarithm under the modular congruence. This open problem is called discrete logarithm problem and only an iterative algorithm is known today, which is not practically with reasonable large primes \(p\).

Diffie Hellman Atacks

Even if the principle behind the Diffie Hellman key-exchange is pretty secure, there have been numerous attempts to break the method.

Man in the middle Attack

If an attacker can interfere into the connection and act as the server to the client and vice versa, the participants of the communication wouldn’t recognize this intruder. That is, an attacker would establish a secret communication with both ends and since the attacker knows \(b\) and \(p\), the attacker can choose its own exponent \(a\) and follow the protocol. The complete algorithm is:

1. The client tries to send its \(i=b^c\pmod{p}\) to the server and the server its \(j=b^s\pmod{p}\) to the client. Both messages are intercepted by the attacker.

2. The attacker calculates \(k=b^a\pmod{p}\) using its own exponent and sends it to both, the client and the server instead of \(j\) and \(i\).

3. Both ends use \(k\) mistakenly and the client proceeds by calculating \(k^c\equiv (b^a)^c\pmod{p}\) and the server proceeds by calculating \(k^s\equiv(b^a)^s\pmod{p}\).

This is a serious problem and the only real solution is, that the opponent must be trustworthy by authenticating against a certificate authority.

Weak Diffie-Hellman and the Logjam Attack