Discrete logs and the ways Diffie-Hellman is set up wrong

Diffie-Hellman rests on one assumption: given g, p, and g^a mod p, recovering a is hard. In a well-chosen group it is. CTF challenges are built out of the ways a group can be chosen badly, and there are only about five of them. Reading the parameters tells you which one you are looking at before you write any code.

The parameters are p (the modulus), g (the generator), and implicitly the *order* of the subgroup g generates. That last one is the number almost every attack turns on, and it is the one challenges quietly get wrong.

The parameter triage

Baby-step giant-step: the meet in the middle

To solve g^x = h mod p for x < n, write x = i*m + j with m = ceil(sqrt(n)). Then h * g^(-i*m) = g^j. Build a table of g^j for all j < m, then walk i and look each value up. Time and memory are both O(sqrt(n)), which turns a 2^60 search into 2^30 - comfortable - and leaves 2^256 exactly as hopeless as it was.

def bsgs(g, h, p, n=None):
    n = n or p - 1
    m = int(n ** 0.5) + 1
    table = {}
    e = 1
    for j in range(m):                 # baby steps: g^j
        table[e] = j
        e = e * g % p
    factor = pow(g, -m, p)             # giant stride: g^(-m)
    e = h
    for i in range(m):
        if e in table:
            return i * m + table[e]
        e = e * factor % p
    return None

Pohlig-Hellman: smooth orders collapse

This is the attack most "weak DH" challenges are actually about. If the group order n factors as a product of small prime powers, the discrete log problem splits into one small problem per factor. Solve x mod p_i^e_i in each - each is a BSGS over a tiny group - and reassemble with the Chinese remainder theorem.

The cost is governed by the *largest* prime factor, not by the size of p. A 2048-bit prime whose p - 1 factors into primes below 2^20 is completely broken, and it looks perfectly respectable in a config file.

from sympy import factorint
from sympy.ntheory.modular import crt

def pohlig_hellman(g, h, p, n=None):
    n = n or p - 1
    residues, moduli = [], []
    for q, e in factorint(n).items():
        qe = q ** e
        # Project into the subgroup of order q^e and solve there.
        gi = pow(g, n // qe, p)
        hi = pow(h, n // qe, p)
        residues.append(bsgs(gi, hi, p, qe))
        moduli.append(qe)
    return int(crt(moduli, residues)[0])

This is why safe primes exist. A safe prime has p = 2q + 1 with q prime, so p - 1 has exactly one large factor and Pohlig-Hellman buys you a single bit. If a challenge hands you a prime that is not a safe prime, factoring p - 1 is the first thing to try - the same instinct as looking at the shape of n in the RSA decision tree.

Small subgroup confinement

The generator matters as much as the modulus. If g generates a subgroup of order k rather than the full group, then g^a takes only k distinct values no matter how large a is. The shared secret has k possibilities, and you enumerate them.

The active version is better. In an interactive exchange where the server does not validate what you send, transmit a value of small order instead of a legitimate public key:

• Send 1. Then shared = 1^b = 1 for every possible server secret. You know the shared secret exactly.
• Send p - 1. It has order 2, so shared is 1 or p - 1 depending on the parity of the server's exponent. Two candidates, and you have leaked one bit of their key.
• Send 0. Then shared = 0. Some implementations reject this; many do not.
• Send an element of order k for a small k dividing p - 1. Now shared has k candidates - and which one it is reveals the server's secret modulo k. Repeat across several small k and CRT them together to recover the whole secret.

That last variant is the full small-subgroup key-recovery attack, and it is the reason a real implementation validates that a received public value has the expected order before using it. A challenge that omits the check is inviting you to run it.

The exchange with nobody authenticating

Textbook Diffie-Hellman provides confidentiality against a passive eavesdropper and nothing at all against an active one. If a challenge puts you between two parties - a proxy, a relay, a chat server you control - you do not need any discrete log. Run two independent exchanges, one with each side, and decrypt-then-re-encrypt in the middle.

Alice --g^a--> [you] --g^m--> Bob
Alice <--g^m-- [you] <--g^b-- Bob

You hold g^(am) with Alice and g^(bm) with Bob.
Neither of them holds a secret you do not.

The tell that this is the intended path: the challenge gives you a network position rather than just a transcript. If you are handed a pcap you are a passive observer and you need the maths; if you are handed a socket in the middle, you do not.

Related shapes worth recognising

• ElGamal is Diffie-Hellman with a message multiplied in, so every attack above applies unchanged. It also inherits a malleability property: multiplying the ciphertext by m' multiplies the plaintext by m', which is a signature-forgery route when the same key signs.
• DSA and its elliptic-curve sibling are signature schemes over the same hard problem, and they fail on the *nonce* rather than the group - covered in elliptic curve attacks.
• Elliptic-curve Diffie-Hellman is this post with multiplication written as addition. Pohlig-Hellman applies to a curve whose order is smooth, and invalid-curve attacks are the small-subgroup attack wearing a different hat.
• Knapsack and subset-sum systems turn up in the same challenge slot and are not discrete-log problems at all; they fall to lattice reduction instead.

The order of attack

1. Print p, g, and every public value. Check the obvious degenerate cases first: g in {0, 1, p-1}, a public value in {0, 1, p-1}.
2. Confirm p is prime. If it is not, factor it - a composite modulus is a different and easier problem.
3. Factor p - 1. Smooth means Pohlig-Hellman; a safe prime means look elsewhere.
4. Compute the order of g. If it is small, the shared secret is enumerable.
5. If p is small enough that sqrt(p) is reachable, just run BSGS and stop thinking.
6. If you are interactive and nothing is validated, send a small-order element and recover the peer's secret modulo its order, repeatedly.
7. If the maths is sound, the bug is in the key derivation or the cipher wrapped around it.