Diffie-Hellman: How Strangers Agree on a Secret

1. Why Should You Care?

Here’s the fundamental problem of cryptography:

Alice wants to send Bob an encrypted message.
They've never met.
Everything they send is public.

How can they agree on a secret key?

Before 1976, the answer was: they can’t. You need a secure channel to exchange keys, but you need keys to create a secure channel. A chicken-and-egg problem.

Diffie-Hellman broke this paradox. Every HTTPS connection you make uses it.

2. Definition

Diffie-Hellman Key Exchange (DH) is a method for two parties to jointly establish a shared secret over an insecure channel, without having any prior shared secret.

The security is based on the Discrete Logarithm Problem: given g and g^a, finding a is computationally hard in certain mathematical groups.

The magic:

Alice knows: a (private)
Bob knows:   b (private)
Both compute: g^(ab)  (shared secret)

Eavesdropper sees: g, g^a, g^b
Cannot compute: g^(ab)

3. The Paint Mixing Analogy

Think of colors that can be mixed but not unmixed:

Public: Yellow paint (everyone knows)

1. Alice picks secret Red
   Mixes Yellow + Red → Orange
   Sends Orange to Bob

2. Bob picks secret Blue
   Mixes Yellow + Blue → Green
   Sends Green to Alice

3. Alice adds her Red to Green:
   Green + Red = Brown

4. Bob adds his Blue to Orange:
   Orange + Blue = Brown

Both have Brown!

Eavesdropper has:
- Yellow (public)
- Orange (Yellow + Red)
- Green (Yellow + Blue)

Cannot figure out Brown without knowing Red or Blue!

4. The Math (Modular Exponentiation)

The Setup

Public parameters (everyone knows):
- p: a large prime number
- g: a generator of the multiplicative group mod p

These can be standardized and reused.

The Exchange

Step 1: Generate private keys
  Alice picks random a (private)
  Bob picks random b (private)

Step 2: Compute public keys
  Alice computes: A = g^a mod p
  Bob computes:   B = g^b mod p

Step 3: Exchange public keys
  Alice sends A to Bob (public)
  Bob sends B to Alice (public)

Step 4: Compute shared secret
  Alice computes: s = B^a mod p = (g^b)^a mod p = g^(ab) mod p
  Bob computes:   s = A^b mod p = (g^a)^b mod p = g^(ab) mod p

Both have the same secret s = g^(ab) mod p!

Why Eavesdropping Fails

Eavesdropper Eve sees:
- p, g (public parameters)
- A = g^a mod p
- B = g^b mod p

To compute s = g^(ab) mod p, Eve needs either a or b.

To find a from A = g^a mod p:
This is the Discrete Logarithm Problem.
For proper parameters, it's computationally infeasible.

5. Numerical Example

# Small numbers for understanding (real DH uses 2048+ bit primes)

# Public parameters
p = 23  # prime
g = 5   # generator

# Alice's private key
a = 6
# Alice's public key
A = pow(g, a, p)  # 5^6 mod 23 = 8

# Bob's private key
b = 15
# Bob's public key
B = pow(g, b, p)  # 5^15 mod 23 = 19

# Exchange public keys (A=8, B=19)

# Alice computes shared secret
s_alice = pow(B, a, p)  # 19^6 mod 23 = 2

# Bob computes shared secret
s_bob = pow(A, b, p)    # 8^15 mod 23 = 2

print(f"Alice's secret: {s_alice}")  # 2
print(f"Bob's secret: {s_bob}")      # 2
assert s_alice == s_bob              # Same!

6. ECDH: Diffie-Hellman with Elliptic Curves

Why Use Curves?

Classic DH:
- Needs 2048+ bit primes for security
- Slower operations

ECDH (Elliptic Curve DH):
- 256-bit curves for equivalent security
- Faster operations
- Smaller key sizes

How ECDH Works

Instead of modular exponentiation:
  A = g^a mod p

We use scalar multiplication on curves:
  A = a × G

Where G is a generator point on the elliptic curve.

The shared secret becomes:
  s = a × B = a × (b × G) = ab × G
  s = b × A = b × (a × G) = ab × G

Same point!

ECDH Code Example

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.kdf.hkdf import HKDF

# Generate key pairs
alice_private = ec.generate_private_key(ec.SECP256R1())
alice_public = alice_private.public_key()

bob_private = ec.generate_private_key(ec.SECP256R1())
bob_public = bob_private.public_key()

# Compute shared secrets
alice_shared = alice_private.exchange(ec.ECDH(), bob_public)
bob_shared = bob_private.exchange(ec.ECDH(), alice_public)

assert alice_shared == bob_shared

# Derive actual encryption key
key = HKDF(
    algorithm=hashes.SHA256(),
    length=32,
    salt=None,
    info=b'encryption key'
).derive(alice_shared)

print(f"Shared secret length: {len(alice_shared)} bytes")
print(f"Derived key length: {len(key)} bytes")

X25519: The Modern Choice

from cryptography.hazmat.primitives.asymmetric import x25519

# Much simpler API
alice_private = x25519.X25519PrivateKey.generate()
alice_public = alice_private.public_key()

bob_private = x25519.X25519PrivateKey.generate()
bob_public = bob_private.public_key()

# Exchange
shared_secret = alice_private.exchange(bob_public)

# Same result for Bob
assert shared_secret == bob_private.exchange(alice_public)

7. Ephemeral vs Static DH

Static DH (Deprecated)

Alice and Bob have long-term DH key pairs.
They use the same keys for all sessions.

Problem: No forward secrecy!
If Alice's private key is later compromised,
all past sessions can be decrypted.

Ephemeral DH (DHE/ECDHE)

For each session:
1. Generate fresh, temporary key pairs
2. Perform DH exchange
3. Derive session keys
4. Discard ephemeral private keys

Benefits:
- Forward secrecy: past sessions stay secure
- Even if long-term keys compromised later
- TLS 1.3 requires this

TLS 1.3 Key Exchange

Client                              Server
  │                                    │
  │─── ClientHello ───────────────────>│
  │    supported_groups: x25519, p256  │
  │    key_share: x25519 public key    │
  │                                    │
  │<─── ServerHello ───────────────────│
  │     key_share: x25519 public key   │
  │                                    │
  │   [Both compute shared secret]     │
  │   [Derive handshake keys]          │
  │                                    │
  │<═══ Encrypted with AEAD ══════════>│

The key_share values are ephemeral.
New key pair for every connection.

8. Common Attacks and Defenses

Man-in-the-Middle Attack

The fundamental vulnerability of basic DH:

Alice                Mallory               Bob
  │                    │                    │
  │── g^a ────────────>│                    │
  │                    │── g^m ────────────>│
  │                    │                    │
  │<───────────── g^m ─│<───────────── g^b ─│
  │                    │                    │

Alice thinks she's talking to Bob: shares g^(am)
Bob thinks he's talking to Alice: shares g^(bm)
Mallory can decrypt, read, re-encrypt everything!

Solution: Authentication
- Digital signatures on public keys
- Certificates (PKI)
- This is why HTTPS needs TLS certificates!

Small Subgroup Attack

Attack on poorly implemented DH:

Attacker sends B' from a small subgroup.
Shared secret has limited possibilities.
Can brute-force the secret.

Defense:
- Validate received public keys
- Check that B^q = 1 (where q is group order)
- Use safe primes: p = 2q + 1
- Use well-designed curves (X25519 handles this)

Logjam Attack (2015)

Researchers found:
- Many servers used same 512-bit DH params
- Precomputation makes these weak
- Could break 512-bit DH in minutes

Lessons:
- Use at least 2048-bit DH groups
- Don't share DH parameters across servers
- Better: Use ECDH (X25519)

9. DH in Real Protocols

TLS (HTTPS)

TLS 1.2:
- DHE_RSA, ECDHE_RSA, ECDHE_ECDSA cipher suites
- Static RSA was an option (no forward secrecy)

TLS 1.3:
- Only ECDHE (x25519 or P-256)
- RSA key exchange removed entirely
- Forward secrecy required

Signal Protocol

Double Ratchet Algorithm:
1. ECDH with long-term identity keys (authentication)
2. ECDH with ephemeral keys (forward secrecy)
3. Ratchet: new DH keys periodically

Result:
- Forward secrecy
- Post-compromise security
- Each message has unique key

SSH

Initial key exchange:
- curve25519-sha256 (preferred)
- ecdh-sha2-nistp256
- diffie-hellman-group-exchange-sha256

After DH:
- Derive session keys
- Authenticate server (host key)
- Authenticate client (password or key)

WireGuard VPN

Uses Noise Protocol Framework:
1. Static DH: Client and server long-term keys
2. Ephemeral DH: Fresh keys per handshake

Combining static + ephemeral:
- Mutual authentication
- Forward secrecy
- Minimal round trips

10. Implementation Checklist

For secure DH implementation:

□ Use ephemeral keys (ECDHE)
  - Generate new keys per session
  - Delete private keys after use

□ Use strong curves
  - X25519 (preferred)
  - P-256 (fallback)
  - Avoid custom or exotic curves

□ Validate public keys
  - Check point is on curve
  - Check point is not identity
  - Libraries usually handle this

□ Authenticate the exchange
  - Use signed certificates
  - Verify signatures before computing secrets
  - This prevents MITM attacks

□ Use proper key derivation
  - Don't use raw DH output as key
  - Use HKDF or similar
  - Include context in derivation

11. Code: Complete TLS-like Exchange

from cryptography.hazmat.primitives.asymmetric import x25519, ed25519
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes, serialization

class SecureKeyExchange:
    def __init__(self):
        # Long-term identity key for signing
        self.identity_key = ed25519.Ed25519PrivateKey.generate()
        self.identity_public = self.identity_key.public_key()

    def initiate(self):
        """Client side: create ephemeral key and sign it"""
        ephemeral_private = x25519.X25519PrivateKey.generate()
        ephemeral_public = ephemeral_private.public_key()

        # Sign the ephemeral public key
        public_bytes = ephemeral_public.public_bytes(
            encoding=serialization.Encoding.Raw,
            format=serialization.PublicFormat.Raw
        )
        signature = self.identity_key.sign(public_bytes)

        return ephemeral_private, ephemeral_public, signature

    def respond(self, peer_ephemeral_public, peer_signature, peer_identity_public):
        """Server side: verify, create ephemeral, compute secret"""
        # Verify peer's signature
        public_bytes = peer_ephemeral_public.public_bytes(
            encoding=serialization.Encoding.Raw,
            format=serialization.PublicFormat.Raw
        )
        peer_identity_public.verify(peer_signature, public_bytes)

        # Create our ephemeral key
        ephemeral_private = x25519.X25519PrivateKey.generate()
        ephemeral_public = ephemeral_private.public_key()

        # Sign our ephemeral public key
        our_public_bytes = ephemeral_public.public_bytes(
            encoding=serialization.Encoding.Raw,
            format=serialization.PublicFormat.Raw
        )
        signature = self.identity_key.sign(our_public_bytes)

        # Compute shared secret
        shared_secret = ephemeral_private.exchange(peer_ephemeral_public)

        return ephemeral_public, signature, shared_secret

    def complete(self, our_ephemeral_private, peer_ephemeral_public,
                 peer_signature, peer_identity_public):
        """Client side: verify and compute secret"""
        # Verify peer's signature
        public_bytes = peer_ephemeral_public.public_bytes(
            encoding=serialization.Encoding.Raw,
            format=serialization.PublicFormat.Raw
        )
        peer_identity_public.verify(peer_signature, public_bytes)

        # Compute shared secret
        shared_secret = our_ephemeral_private.exchange(peer_ephemeral_public)

        return shared_secret

def derive_keys(shared_secret, context):
    """Derive encryption and MAC keys from shared secret"""
    return HKDF(
        algorithm=hashes.SHA256(),
        length=64,  # 32 for encryption + 32 for MAC
        salt=None,
        info=context
    ).derive(shared_secret)

# Usage
alice = SecureKeyExchange()
bob = SecureKeyExchange()

# Alice initiates
alice_eph_priv, alice_eph_pub, alice_sig = alice.initiate()

# Bob responds (verifies Alice, creates ephemeral, computes secret)
bob_eph_pub, bob_sig, bob_secret = bob.respond(
    alice_eph_pub, alice_sig, alice.identity_public
)

# Alice completes (verifies Bob, computes secret)
alice_secret = alice.complete(
    alice_eph_priv, bob_eph_pub, bob_sig, bob.identity_public
)

assert alice_secret == bob_secret
print("Secure key exchange successful!")

# Derive actual keys
keys = derive_keys(alice_secret, b"my protocol v1")
encryption_key = keys[:32]
mac_key = keys[32:]

12. Common Misconceptions

13. Summary

Three things to remember:

1. Diffie-Hellman lets strangers create shared secrets. Two parties can agree on a secret over a public channel, which seems impossible but works thanks to the discrete log problem.

2. Always use ephemeral DH (ECDHE) for forward secrecy. New keys per session mean past sessions stay safe even if keys are later compromised.

3. DH needs authentication. Without signatures/certificates, MITM attacks are trivial. This is why HTTPS needs TLS certificates.

14. What’s Next

We’ve covered asymmetric cryptography: RSA, ECC, and Diffie-Hellman. But there’s one crucial piece missing: how do we know we’re talking to who we think we are?

In the next section, we’ll explore: Digital Signatures and Certificates—how we prove identity and build trust on the internet.