Introduction to Diffie-Hellman Key Exchange

Diffie-Hellman is a key exchange protocol that allows two parties with no prior knowledge of each other to establish a shared secret key over an insecure network jointly. This shared secret can then be used to encrypt subsequent communications using a faster symmetric encryption algorithm, like AES. The security of Diffie-Hellman relies on the mathematical difficulty of calculating discrete logarithms.

To give you a simple example, imagine you and a friend want to create a secret color of paint, but you can only communicate by sending paint cans back and forth in public, where anyone can see them. Diffie-Hellman lets you both arrive at the same secret color without an eavesdropper being able to figure it out, even though they see the paint you exchange.

• It’s a key exchange algorithm, not an encryption algorithm. Its only job is to create a shared secret.
• It solves the problem of getting a symmetric key to both sides without anyone else seeing it.
• It does not provide authentication. It doesn’t prove who you are talking to.
• Its security is based on the Discrete Logarithm Problem, a mathematical function that is easy to perform in one direction but extremely difficult to reverse.

The Key Exchange Problem

To understand why we need Diffie-Hellman, we first need to understand the two main types of encryption.

• Symmetric Encryption: Uses a single, shared key for both encryption and decryption. It’s very fast and efficient. AES is a perfect example.
• Asymmetric Encryption: Uses a key pair: a public key to encrypt and a private key to decrypt. It’s much slower than symmetric encryption. RSA is a common example.

Symmetric encryption is ideal for encrypting large amounts of data, like in an IPsec VPN tunnel. The challenge, however, is a classic chicken-and-egg problem: how do we securely get that single, shared key to both devices in the first place? We can’t just send it in clear text across the Internet, as an attacker could intercept it.

This is the problem Diffie-Hellman (DH) was created to solve. It provides a way for two devices to agree upon a shared secret, even if an attacker is listening to their entire conversation.

How Diffie-Hellman Works

The magic of Diffie-Hellman is that the two sides exchange public information but can independently create an identical secret that an eavesdropper cannot.

Let’s use the classic paint mixing analogy.

The Paint Mixing Analogy

Imagine Alice wants to create a secret color with Bob. An eavesdropper, Eve, is watching everything they send to each other.

• Agree on Public Paint: Alice and Bob first agree on a common, public color that everyone knows about. Let’s say it’s yellow. This color is not a secret.
• Choose Secret Colors: Alice secretly chooses a private color (e.g., red). Bob secretly chooses his own private color (e.g., blue). They never share these secret colors.
• Mix and Exchange:
  • Alice mixes her secret red with the public yellow, creating an orange mixture. She sends this orange mixture to Bob.
  • Bob mixes his secret blue with the public yellow, creating a green mixture. He sends this green mixture to Alice.
• Eve’s View: Eve intercepts and sees the public yellow paint, the orange mixture, and the green mixture. However, it’s computationally very difficult to “un-mix” paint. Eve can’t easily determine Alice’s secret red from the orange mixture or Bob’s secret blue from the green mixture.
• Create the Shared Secret:
  • Alice takes the green mixture she received from Bob and adds her own secret color (red).
  • Bob takes the orange mixture he received from Alice and adds his own secret color (blue).

Both Alice and Bob now have the exact same final color: a mix of yellow, red, and blue. Eve, who only has the public and intermediate mixtures, cannot create this final color.

The Math Behind the Magic

Now, let’s map the analogy to the actual math. The process relies on modular arithmetic.

1. Public Parameters: Alice and Bob agree on two public numbers:

• A large prime number, p
• A generator, g
• (These are the “public yellow paint”.)

2. Private Keys: Alice and Bob each choose a secret private integer.

• Alice’s private key: a
• Bob’s private key: b
• (These are their “secret colors”.)

3. Public Key Generation and Exchange: They use their private keys to generate public keys and send them to each other.

• Alice calculates A = g^a mod p and sends A to Bob. (Her “orange mixture”.)
• Bob calculates B = g^b mod p and sends B to Alice. (His “green mixture”.)

4. Shared Secret Calculation: Each side uses the public key they received and their own private key to calculate the final shared secret s.

• Alice calculates s = B^a mod p
• Bob calculates s = A^b mod p

Both Alice and Bob arrive at the exact same value for the shared secret s.

Why does this work? Because (g^b)^a mod p is the same as (g^a)^b mod p. The attacker, Eve, knows p, g, A, and B, but to find the secret s, she would need to find either a or b. This requires solving the Discrete Logarithm Problem, which is finding a given g^a mod p. For large numbers, this is computationally infeasible.

Diffie-Hellman Groups

When you configure IPsec or other security protocols, you’ll often see options for Diffie-Hellman (DH) Groups, like Group 14, 19, or 21.

A DH Group is simply a pre-defined, standardized set of a prime number p and a generator g. Using standardized groups ensures interoperability between different vendors’ equipment.

The group number is important because it corresponds to the strength of the key exchange. A higher group number uses a larger prime, which makes it more resistant to attacks.

• Low-numbered groups (1, 2, 5): These are considered weak and legacy. They use smaller key sizes (e.g., 768-bit or 1536-bit) and should not be used.
• Stronger groups (14, 15, 16): These use larger key sizes (e.g., 2048-bit) and are considered a good baseline for security.
• Elliptic Curve groups (19, 20, 21): These use Elliptic Curve Diffie-Hellman (ECDH), a more modern and efficient variant. ECDH can provide the same level of security as traditional DH but with much smaller key sizes, reducing CPU overhead. For example, ECDH Group 19 (256-bit curve) is considered stronger than DH Group 14 (2048-bit prime).

As a best practice, always use the strongest DH group that both devices support in a negotiation.

Security Considerations

The most significant weakness of the basic Diffie-Hellman algorithm is its vulnerability to a Man-in-the-Middle (MITM) attack.

Because DH does not authenticate either party, an attacker can position themselves between Alice and Bob. The attacker can then perform one DH exchange with Alice and a separate DH exchange with Bob.

• Alice thinks she’s establishing a key with Bob, but she’s actually establishing one with the attacker.
• Bob thinks he’s establishing a key with Alice, but he’s also establishing a key with the attacker.

The attacker now sits in the middle, decrypting traffic from Alice with one key, reading or modifying it, and then re-encrypting it with the other key to send to Bob. To fix this, DH must be combined with an authentication method. This is why protocols like IKE (for IPsec) and TLS use digital signatures (like RSA) or Pre-Shared Keys (PSKs) to authenticate the peers before the shared key from the DH exchange is trusted.

Conclusion

Diffie-Hellman is a cornerstone of modern network security. It solves the problem of how to establish a secret key over a public network.