Diffie-Hellman

Introduction

#

In secure communication and cryptography, the Diffie-Hellman¹ (DH) key exchange is a method of securely exchanging cryptographic keys over a public channel. It is named after Whitfield Diffie and Martin Hellman. The protocol allows two parties to share a secret key over an insecure channel, without sending the secret key directly. Instead messages are exchanged in such a way that the secret key can be derived.

Background

#

Let’s begin with explaining some fundamental concepts used when calculating keys in the protocol.

Modular Arithmetic

#

Initially we need to understand the basics of modular arithmetic². It is a system of arithmetic for integers, where numbers “wrap around” upon reaching a certain value (the modulus) and start over from zero. This is often taught in discrete mathematics and number theory courses. It is a fundamental concept in cryptography.

Thus all values in a modular system are bound to lie within the range $0$ to $p-1$ for a modulus $p$. This range is denoted as $\mathbb{Z}_p = \{ 0, 1, \cdots, p-1 \}$ and called the residue class modulo $p$.³ However the multiplicative group of integers modulo⁴ $p$, $\mathbb{Z}_p^* = \{ 1, 2, \cdots, p-1 \}$, is the one most relevant in the DH protocol. $0$ is excluded from $\mathbb{Z}_p^*$ because does not have a multiplicative inverse.

Note
$\mathbb{Z}_p^*$ has an order (aka, total number of elements) of $|\mathbb{Z}_p^*| = p - 1$.

Modular Exponentiation

#

The algorithm in the DH protocol uses modular exponentiation⁵ to compute its keys. It is a type of exponentiation performed over a modulus of $p$ with values in $\mathbb{Z}_p$. Exponentiation in modular arithmetic involves computing the remainder when a number is raised to a power and divided by a modulus:

$$ \begin{align*} a^n \mod p = & \newline a \times \cdots \times a \mod p = & \newline (a \mod p) \times \cdots \times (a \mod p) \mod p = & \newline \end{align*} $$

We can try to “optimize” the multiplications by taking the remainder after each repeated multiplication to keep the numbers small during the entire calculation. This results in faster and more memory-efficient computation. However, due to $O(n^2)$ time complexity of multiplication⁶ and the fact that the number of iterations will still be $O(n)$, which for large numbers of roughly $2048$ bits, is a lot of multiplications and is computationally expensive.
But there is a way to solve this!

Square-and-multiply

#

This optimized algorithm computes the modular exponentiation by squaring⁷, in logarithmic time complexity of $O(\log n)$, where $n$ is the size of the exponent. It takes advantage of the binary representation of the exponent and moves from the least significant bit (LSB) to the most significant bit (MSB), also known as the Right-to-Left Binary Method⁵⁷.

def mod_exp(b, e, m):
    result = 1
    x = b % m
    while e > 0:
        if e % 2 == 1:
            result = (result * x) % m
        x = (x * x) % m
        e = e >> 1
    return result

Example

#

We can easily calculate,  $5^{23} \mod 97 \equiv 82$,  using the SaM RTL method above, where $e = 23_{10} = 10111_2$.

If I were to ask you which power $e$ I started with to get to $82$, only knowing $b=5$, $p=97$. You would have to brute-force it by trying different exponents until you find the correct one ($b = 23$).

This is the essence of the discrete logarithm problem.

Discrete Logarithm Problem

#

The discrete logarithm problem⁸ (DLP) is the basis for the security of the DH key exchange. Finding the exponent $x$ in the equation  $g^x = A \mod p$  is computationally infeasible for large numbers. No efficient classical algorithm is known for computing discrete logarithms in general. In fact, it is an exponential-time algorithm.⁸ Given this, the set of all integers $a$ satisfying $A \equiv g^a \mod p$ can be expressed using the discrete logarithm:

$$ a \equiv \log_g A \mod \text{ord}_p(g) $$

The multiplicative order of $g$ modulo $p$, denoted as $\text{ord}_p(g)$, is the smallest positive integer $n$ such that $g^n \mod p \equiv 1$. The order of $g$ is a divisor of $p - 1$, meaning that $\text{ord}_p(g) \mid |\mathbb{Z}_p^*|$.

Note
The order of the generator $g$, denoted as $\text{ord}_p(g)$, is a divisor of $p - 1$ but not necessarily equal. This means that $\text{ord}_p(g) \mid |\mathbb{Z}_p^*| \iff \text{ord}_p(g) \mid p - 1$ for all $g \in \mathbb{Z}_p^*$.

Further analysis why the discrete logarithm problem is hard to solve can be found in the Wikipedia article.

Algorithm

#

The algorithm is based on DLP. As it is very hard to solve for large numbers, the algorithm is considered cryptographically secure if the parameters are chosen correctly.

Short explanation of the steps above:

1. Setup: Alice and Bob agree on a prime number $p$ and a generator $g$.
2. Alice: Alice randomly chooses a secret number $a$ and computes  $A = g^a \mod p$.
3. Bob: Bob randomly chooses a secret number $b$ and computes  $B = g^b \mod p$.
4. Exchange: Alice sends $A$ to Bob and Bob sends $B$ to Alice.
5. Key: Alice computes  $K = B^a \mod p$  and Bob computes  $K = A^b \mod p$.

Naming
$p$ and $g$ are public parameters. Both $a$ and $b$ are kept secret, and are therefore called private keys. The numbers $A$ and $B$ are called public keys, as they get sent over the public channel Internet.

Alice and Bob now share the same secret key $K$ without anyone eavesdropping knowing it! The initial numbers $p$ and $g$, and the generated $A$ and $B$ are public and can be shared over an insecure channel without compromising the key $K$.

Multi-party

#

It is possible to extend this protocol to more than two parties where each agrees on the same $p$ and $g$ and each party chooses a secret key and computes a public key. Similar steps are followed as in the two-party case, but the shared secret key is computed with everyone’s public keys using $ K = g^{a b c} \mod p $¹, where $a$, $b$, and $c$ are the private keys of the parties.

Drawbacks

#

As to any technology, there are drawbacks and vulnerabilities to recognize.

Man-in-the-Middle Attack

#

Everything is fine until Charles comes into the picture. He is not only eavesdropping but also actively manipulating the messages. This is called a Man-in-the-Middle⁹ (MitM) attack. The DH protocol is vulnerable to this because Charles can generate his own keys, and forward the messages to each of the other parties separately, without them knowing. By doing so, he can decrypt and read the messages, alter them, and re-encrypt them before sending them on to the intended recipient, thereby compromising the encryption and the security of the communication.

Solution
The fundamental issue is that the parties cannot verify the authenticity of the public keys they receive. That is, Bob cannot be 100% sure that the public key he receives is actually from Alice.

Both Alice and Bob need to agree to trust some third party to verify the authenticity of the public keys. This is done via a digital signature¹⁰ provided by a certificate authority¹¹ (CA). Before Alice and Bob exchange their public keys, they send them to the CA to be signed by the CA’s private key. After receiving the signed public keys, both Alice and Bob can verify their authenticity by checking the signature using the CA’s public key which everyone has access to. Only then will they trust each other’s public keys, and proceed with the key exchange.

Pohlig-Hellman Algorithm

#

The Pohlig-Hellman algorithm¹² is a discrete logarithm algorithm that can be used to efficiently solve DLP $\iff$ (if and only if) either the order of the group $|\mathbb{Z}_p^*| = p - 1$ or the order of the generator $\text{ord}_p(g)$ factors into small prime numbers. Thus the private keys and the shared secret can be computed, breaking the security of the DH key exchange. The algorithm split the problem into smaller subgroups of order $q_i$.

$$ n = \prod_{i=1}^k q_i^{e_i} = q_1^{e_1} \times q_2^{e_2} \times \cdots \times q_k^{e_k} $$

Where, $n = \text{ord}_p(g)$  or  $n = p - 1$, and all $q_i$ are the prime factors of $n$. This algorithm can be used to break the DH key exchange if the prime number $p$ is not chosen carefully.

Solution
Because of Pohlig-Hellman algorithm working efficiently when $p-1$ or $\text{ord}_p(g)$ factors into small primes, we can choose a large prime number $p$ such that $p - 1$ has at least one large prime factor to make the DLP harder to solve. This is why it is recommended to use 2048-bit or 4096-bit prime numbers in practice.

To select a sufficiently large prime number $p$, we can use safe primes¹³ on the form $p = 2q + 1$, where both $p$ and $q$ are prime. Additionally, selecting a generator $g$ with a large order $q = \text{ord}_p(g)$ ensures computations are performed within this large prime-order subgroup, further enhancing security. Safe primes ensure that $n$ has a large prime factor, rendering the Pohlig-Hellman algorithm ineffective!

Security

#

Before summing up this post about Diffie-Hellman, let’s talk about the security aspects and what to think about when choosing the parameters or using the protocol in general.

The security of the DH protocol relies on good choices of the prime number $p$ and the generator $g$ to make DLP hard to solve, which is crucial for maintaining the confidentiality of the shared secret. Below is a list of best practices to keep in mind when using the DH protocol to ensure secure communications:

Careful selection of $p$ and $g$ significantly enhances the security of the DH protocol by maintaining the difficulty of the DLP, thereby safeguarding secure communications in cryptographic systems.

Conclusion

#

Diffie-Hellman (DH) is vastly used in many cryptographic protocols such as TLS/SSL, SSH, IPsec, and PGP. The main benefit comes from the forward secrecy provided by the protocol, as new keys get generated for each unique session. This makes it more difficult for an attacker to decrypt past sessions if the current key is compromised. With the right parameters and good practices, the Diffie-Hellman key exchange is a secure and efficient way to establish a shared secret key over an insecure channel.