Step 235. DH Key Exchange and an MITM Simulation — Making a Secret on an Eavesdropped Channel, and Its Limits

Level 3 — Real-World CTF & Advanced Offensive Skills | Difficulty ★★★☆☆ | Estimated time: 4 hours

Prerequisites: pow(a, b, n) from Step 227 (Crypto Math Foundations). That one line is this entire chapter.

⚠️ All exercises in this chapter are for your own lab and legal platforms only. Applying them to unauthorized systems is a crime.

• What you need: Python 3 (measured: 3.12.14), paper and pen (for a 3-column Alice·Eve·Bob table).
• Caution: today’s exercises are 100% safe. No network — just roleplay inside your own computer.

Every cipher so far (symmetric-key) had a fatal prerequisite problem — how do you share the key first? Diffie-Hellman (DH) key exchange solves that problem with mathematics: over an eavesdropped channel, exchanging only public values still produces a shared secret only the two parties know. But this magic is missing one condition — authentication: "is the other party really who they claim to be?" Today you implement DH yourself and prove by simulation why the man-in-the-middle (MITM) attack works.

1. Learning Objectives

By the end of this chapter, you will be able to:

• Implement the DH key-exchange procedure (exchange g^a mod p → share g^ab mod p) in code
• Explain that the discrete logarithm problem is DH’s security foundation
• Measure DH breaking via exhaustive search at a small p
• Simulate the structure in which a MITM shares separate keys with each side
• Explain why "key exchange" and "authentication" are separate problems, and how TLS binds them together

2. Background Knowledge — Today’s Tools and Concepts

Today’s Tools at a Glance

2-1. The DH Procedure — Five Lines of Magic

The procedure is all of this. After Alice and Bob agree on the public parameters — a prime p and a generator g:

Alice: picks a secret a → publishes A = g^a mod p
Bob:   picks a secret b → publishes B = g^b mod p
Alice computes B^a mod p, Bob computes A^b mod p
Both results equal g^(ab) mod p → this is the shared secret

An eavesdropper sees p, g, A, and B — all of them. Yet making the shared secret requires a or b, and recovering a from A is the discrete logarithm problem — g^a mod p is fast to compute, but its inverse is practically impossible for large p.

2-2. The Discrete Logarithm Problem — Easy to Go, Hard to Come Back

In Step 227 we saw why pow(a, b, n) is fast. Reverse the direction and the story changes — "given A = g^a mod p with g, A, p known, what is a?" has no general fast algorithm. With a 2048-bit p, exhaustive search wouldn’t finish in the age of the universe.

There’s a premise, though — p must be large enough. At today’s practice p = 23, the discrete log falls to a few lines of exhaustive search. This is also the seed of real-world attacks (Logjam and friends) — attacks that force negotiation of weak parameters actually happened.

2-3. MITM — the Empty Seat of "Who Did I Exchange Keys With?"

DH is strong against eavesdropping but defenseless against relaying. If Eve sits in the middle of the communication, pretending to be Bob to Alice and Alice to Bob:

Alice ⇄ Eve : shared secret s1 (Alice believes she shares it with Bob)
Eve   ⇄ Bob : shared secret s2 (Bob believes he shares it with Alice)

Afterward, the ciphertext Alice sends is encrypted with s1, so Eve reads it, re-encrypts it with s2, and passes it to Bob — both sides perceive a normal conversation. DH itself worked perfectly. What collapsed is the absence of authentication. This is exactly why TLS always bundles certificates and signatures with key exchange.

3. Follow Along

All output in this chapter was measured 2026-09-09 on Python 3.12.14.

3-1. Implementing DH — Do the Shared Secrets Match?

p, g = 23, 5            # small practice parameters (production uses 2048+ bits)
a, b = 6, 15            # Alice's and Bob's secret exponents
A = pow(g, a, p)        # Alice's public value
B = pow(g, b, p)        # Bob's public value
s_alice = pow(B, a, p)  # B^a = g^(ab) mod p
s_bob   = pow(A, b, p)  # A^b = g^(ab) mod p
print(f"Alice: a={a} -> public A = {A}")
print(f"Bob  : b={b} -> public B = {B}")
print(f"Alice's shared secret = {s_alice}")
print(f"Bob  's shared secret = {s_bob}")
print("match:", s_alice == s_bob)

Alice: a=6 -> public A = 8
Bob  : b=15 -> public B = 19
Alice's shared secret = 2
Bob  's shared secret = 2
match: True

How to read the output: Alice doesn’t know b, and Bob doesn’t know a. Yet both arrived at 2 — because B^a = (g^b)^a = g^(ab) = (g^a)^b = A^b (mod p). The only things that crossed the channel were 8 and 19.

3-2. The Eavesdropper’s View — and the Tragedy of a Small p

Eve saw p=23, g=5, A=8, B=19. With p this small, exhaustive search works:

for x in range(1, 23):
    if pow(5, x, 23) == 8:
        print("Alice's secret a =", x)   # x satisfying A = g^a mod p
        break
print("Eve's shared secret:", pow(19, x, 23))

Alice's secret a = 6
Eve's shared secret: 2

How to read it: done within 22 tries. One fact — p is small — erases every guarantee DH makes. On the other hand, run the same computation with a 127-bit prime (2**127 - 1) and the public values compute fine, but exhaustive search takes up to about 1.7×10³⁸ tries — even at a billion tries per second, that’s billions of times the age of the universe. This contrast is why production parameters (2048-bit) are needed.

3-3. The MITM Simulation — Eve’s Double Key Exchange

Now Eve sits in the middle. Eve makes her own secret exponent e = 13 and swaps both sides’ public values for her own E = 21.

e = 13
E = pow(g, e, p)          # Eve's public value
s_ae = pow(E, a, p)       # the shared secret Alice believes in (her key with "Bob" = Eve)
s_ea = pow(A, e, p)       # the secret Eve shares with Alice
s_be = pow(E, b, p)       # the shared secret Bob believes in (his key with "Alice" = Eve)
s_eb = pow(B, e, p)       # the secret Eve shares with Bob
print(f"Alice's side: {s_ae} == {s_ea} -> {s_ae == s_ea}")
print(f"Bob  's side: {s_be} == {s_eb} -> {s_be == s_eb}")
print(f"Are Alice's and Bob's keys the same? {s_ae == s_be}")

Alice's side: 18 == 18 -> True
Bob  's side: 7 == 7 -> True
Are Alice's and Bob's keys the same? False

How to read the output: these three lines are the whole scenario. Alice and Bob hold different keys (18 and 7), and each key is shared with Eve. DH succeeded perfectly — twice — with the wrong party.

3-4. Eve Reads and Relays the Conversation

Let’s demo using the shared secrets as keys for a simple XOR cipher:

def xor_msg(msg, key):
    return bytes(c ^ (key % 256) for c in msg)

plain = b"meet at 9pm"
c1 = xor_msg(plain, s_ae)          # ciphertext in the Alice -> Eve direction
read = xor_msg(c1, s_ea)           # Eve decrypts and reads it
c2 = xor_msg(read, s_eb)           # Eve re-encrypts with Bob's key
print("ciphertext Alice sent:", c1.hex())
print("plaintext Eve read:", read)
print("plaintext Bob received:", xor_msg(c2, s_be))

ciphertext Alice sent: 7f777766327366322b627f
plaintext Eve read: b'meet at 9pm'
plaintext Bob received: b'meet at 9pm'

How to read it: Bob received the exact message, so he can’t sense anything wrong. Eve can not only read but relay altered content — "meet at 9pm" becomes "meet at 3am." That the key exchange succeeded guarantees nothing — that’s today’s core data.

3-5. The Defense — Authenticated Key Exchange

What fills the empty seat is the digital signature. If Alice signs her public value A with her private key, Eve can’t produce Alice’s signature on the forged value E, so Bob filters it out at verification. This is exactly why TLS bundles certificates and signatures with DH-family key exchange (ECDHE) — key exchange makes the secret, authentication confirms the party, and only together do they make a safe channel.

4. Missions & Exercises

Mission — Completing the Three-Party Roleplay

1. Split Alice, Bob, and Eve into separate code blocks and reproduce the full MITM scenario — parameters p=23, g=5, secret exponents of your choice
2. Add a step where Eve alters Alice’s message before passing it to Bob (not just reading — swapping)
3. On paper, draw a 3-column table "what Alice knows / what Eve knows / what Bob knows" and place each public value and shared secret in its column
4. Finally, mark on the table "at which step a signature would have severed the attack"

Exercises

Exercise 1. List the four values an eavesdropper sees in DH (p, g, A, B), and answer what else is needed to compute the shared secret.

Exercise 2. With p=23, g=5, Bob’s public value was B=4. Find b by exhaustive search (code or by hand).

Exercise 3. In the MITM attack, explain why the conversation still works even though Alice’s and Bob’s shared secrets differ (18 vs 7).

Exercise 4. Refute the claim "DH is secure, so it’s fine to use without authentication," citing today’s measurements.

# --- Alice ---
a = 6; A = pow(g, a, p)
# --- Eve (intercepts A in the middle and swaps in E) ---
e = 13; E = pow(g, e, p)
# --- Bob ---
b = 15; B = pow(g, b, p)

s_A = pow(E, a, p)    # Alice: receives E believing it's from Bob
s_E_with_A = pow(A, e, p)
s_B = pow(E, b, p)    # Bob: receives E believing it's from Alice
s_E_with_B = pow(B, e, p)

# tampering demo
read = xor_msg(xor_msg(b"meet at 9pm", s_A), s_E_with_A)
forged = b"meet at 3am"
bob_gets = xor_msg(xor_msg(forged, s_E_with_B), s_B)
print("Eve read:", read, "/ Bob received:", bob_gets)

Eve read: b'meet at 9pm' / Bob received: b'meet at 3am'

6. Common Pitfalls & Fixes

Wall 1. The shared secrets don’t match (plain DH)

Symptom: pow(B, a, p) != pow(A, b, p).
Cause: you dropped the mod in the public-value computation (g**a followed by % p works, but ordering mistakes are common), or you substituted A and B swapped.
Fix: always use the three-argument pow(g, a, p), and check substitutions with the sentence "the other party’s public value ^ my secret."

Wall 2. It’s supposed to be MITM but only one key comes out

Symptom: in the simulation, Alice’s and Bob’s keys are equal.
Cause: you coded Eve to pass A and B through unmodified — that’s eavesdropping, not MITM.
Fix: Eve must send her own public value E to both sides. Check in the code that "what Alice receives is E, not B."

Wall 3. The exhaustive search never finishes

Symptom: the discrete-log recovery code has been running for minutes.
Cause: you set p large and looped range(1, p). With a 127-bit p it will literally never end.
Fix: keep the practice p under 1000. Use a large p only for the demonstration that "computation works but inversion doesn’t."

Wall 4. The XOR cipher key exceeds the byte range

Symptom: ValueError: bytes must be in range(0, 256) (when using the key directly in XOR).
Cause: the shared secret s is a value mod p, so it exceeds 256 when p is large.
Fix: for the demo, fold it with key % 256; in reality the standard is to hash the shared secret (a KDF) to derive the key — that whole procedure is TLS’s "key derivation."

Wall 5. The roles get confused and the code tangles

Symptom: who-knows-what gets mixed up in the code.
Cause: in DH MITM, role management is harder than the math — exactly as the original guide points out.
Fix: before coding, draw the Alice/Eve/Bob 3-column table on paper and write each value into the "who knows it" column as it appears. The code is a copy of that table.

7. Summary

Today’s Concepts

Today’s Commands & Code

An Instinct More Important Than Commands

DH solved "the problem of making a secret" but left "the problem of confirming the other party" behind. Today’s three simulation outputs — both key exchanges succeeding (True, True), the two keys mismatching (False), and the plaintext Eve read — show how fatal that empty seat is. When evaluating any crypto system, after asking "does the key exchange succeed?" always ask next — "but with whom?"

Once every box is checked, Step 235 is complete.