Cybersecurity Chunks: Diffie-Hellman Key Exchange

The Diffie-Hellman (DH) Key Exchange is a method for deriving a shared symmetric-key cipher over an unsecure communication channel such as the internet. It is used in many areas of cybersecurity including in tunnelling (VPNs) and establishing secure web sessions. In this article we look at the DH process, its uses, and the mathematics behind it.

DH helps to setup secure, encrypted communications between two or more parties and serves as a basis for further security mechanisms such as end-to-end encryption, authentication, and integrity. In the realm of cryptographic communication, techniques and mechanisms are often layered on top of each other to achieve robust protection against eavesdropping and unauthorized access to data.

DH key exchange isn’t typically used to provide data encryption or digital signing by itself; rather, it is an underlying mechanism used in many modern security technologies which facilitates creating a secure link by which more specialized mechanisms such as RSA or TLS can operate.

The strength of the DH mechanism lies in the computational complexity of factoring immense prime numbers and outside parties not having access to all the information needed to recreate the key exchange process.

The DH Key Exchange Process, Simplified

Assume we have two devices looking to begin a secure link, Device A and Device B.

1: Both ends of the communication agree on a Prime Number P and Primitive Root R, let’s say P = 11 and R = 7 for example.

Tidbit: The primitive root is also known as a generator as it is used to generate another value.

2: Device A picks an exponent to use as its Private Key PrivK and uses this to create a Public Key PubK using the following calculation:

The shared primitive root to the power of device A’s private key, modulo the shared prime number

PubK = (R^PrivK) % P

Let’s say 4 is chosen as device A’s Private Key, so we would have:

P = 11, R = 7, PrivK = 4

Plugging this into the calculation we get:

A’s PubK = (7^4) % 11

A’s PubK = 2,401 % 11

A’s PubK = 3

3: Device B derives its own Public Key by mirroring this process with its own Private Key, let’s say it uses 8:

P = 11, R = 7, PrivK = 8

B’s PubK = (7^8) % 11

B’s PubK = 5,764,801 % 11

B’s PubK = 9

4: Device A and Device B share their public keys with each other.

5: Each device combines their own Private Key with the other’s Public Key to derive a Shared Secret Key:

A’s Shared Secret Key = B’s Public Key ^ A’s Private Key % Shared Prime

A’s Shared Secret Key = (9^4) % 11 = 5

B’s Shared Secret Key = A’s Public Key ^ B’s Private Key % Shared Prime

B’s Shared Secret Key = (3^8) % 11 = 5

And voila, both devices have now securely derived a shared secret key of 5.

Vulnerabilities & Mitigations of Diffie-Hellman Key Exchange

In the real world, much larger primes, generators, and private keys are used in DH key exchange to provide stronger security; in fact, we should use a minimum 2048-bit prime (617 digits) or elliptic-curve DH – see Logjam and RFC-8270.

If someone put enough compute power together to derive the numbers and keys used in a DH exchange, they would have access to all communications sent/received. For this reason, new DH session keys are generated for every message sent in the communication (see Forward Secrecy) and additional cryptographic mechanisms like digital signatures are used in conjunction with DH to provide various other security functions.

As the shared secret in DH is derived independently by each device in the communication, anyone who eavesdrops on the conversation (known as a Man-in-the-Middle type of attack) won’t be able to capture it in real-time as it isn’t actually transmitted between devices; however, DH doesn’t have any authentication method, meaning there is no guarantee that a device on the other end of the communication is genuine. If an attacker placed themselves in the middle of the DH exchange, they could potentially intercept the request and substitute their own DH information to set up a fraudulent connection masquerading as the intended receiver. They could also send bogus numbers instead of public keys to trigger expensive calculations on the receiver’s device, potentially launching a denial-of-service attack, see CVE-2002-20001.

Often, the digital signing and public key encryption aspect of RSA or similar is used to provide authentication and asymmetric encryption for DH exchanges.

Key Terms Used

We lightly touched on some mathematics and encryption terms in this article, here’s a quick reference to get you up to speed:

Prime Number: Any number that can only be divided by itself and 1 without remainders, e.g. 2, 3, 5, 7, 11, etc.

Tidbit: 1 used to be considered as a prime number; however, modern definitions state that for a number to be prime, it should have exactly two factors, 1 has only one factor: itself, and is therefore not a prime number.

Primitive Root: Specifically, primitive root modulo n. A number is a primitive root modulo n if every number coprime to n is congruent to a power of the number modulo n – in simple terms, a magic number with a special relationship to a modulo operation. This relates to a concept in mathematics known as the Discrete Logarithm Problem (DLP) which makes it computationally difficult to discover constituent parts knowing only a result, or generate that specific result by guessing its constituent parts. Due to the exponential nature of the DLP, encryption algorithms mostly derive their strength from longer key sizes (bits used).

*Coprime Numbers: Pairs of numbers that don’t have any common factor (‘divided by’ number) other than 1. E.g.:

4 can be rationally divided by 1, 2, and 4

7 can be rationally divided by 1, and 7

Therefore 4 and 7 are coprime

*Congruent: Another way of saying identical/equivalent to in math and logic, often using the ≡ symbol.

Exponent: The number to the right of ^ or “To the power of”, e.g. in 2³, also written 2^3, 3 is the exponent which tells us to multiply 2 by itself 3 times: 2x2x2.

Modulo: Math operator % which returns the remainder after division.

Modulus: With the above, the number divided by, so 4 % 2 = 0, 2 is the modulus, 5 % 3 = 2, 3 is the modulus, etc.

Cryptographic Keys: In cryptography, a key is simply a number derived from some type of mathematical function(s). A Private Key is a number which is kept secret, and a Public Key is a number which doesn’t have to be kept secret. Some encryption methods, such as Advanced Encryption Standard (AES) and Twofish, only rely on a shared private key (known as symmetric encryption), while other methods, such as Rivest-Shamir-Adleman (RSA), use both private and public keys (known as public-key or asymmetric encryption).

Digital Signature: Is a way to ensure that who you’re communicating with is authentic and not an impersonator. Think of it as a unique stamp produceable only by a specific entity.

Cipher: Whereas a key in cryptography is a number, a cipher is the instructions or algorithm used to encrypt/decrypt information using the key.

~ G.G. July 2024