Break weak Diffie-Hellman key exchanges in CTF crypto challenges - small subgroup, logjam, and discrete log.

Diffie-Hellman Attacks

The Diffie-Hellman key exchange relies on the hardness of the discrete logarithm problem (DLP). CTF challenges exploit weak parameter choices, small subgroups, or implementation errors.

DH Quick Review

Public parameters: prime $p$ , generator $g \in \mathbb{Z}_p^*$ .

Alice picks secret $a$ , sends $A \equiv g^a \pmod{p}$ .
Bob picks secret $b$ , sends $B \equiv g^b \pmod{p}$ .

Shared secret (same in both directions):

K \equiv B^a \equiv A^b \equiv g^{ab} \pmod{p}

Attack: Small Prime / Weak Parameters

If p is small or has small factors in p-1, the DLP is easy.

Check with SageMath:

from sage.all import *

p = ...  # given prime
g = ...
A = ...  # Alice's public key

# Factor p-1
print(factor(p - 1))

# If p-1 has small factors → use Pohlig-Hellman
# discrete_log computes a from g^a = A mod p
a = discrete_log(Mod(A, p), Mod(g, p))
print(f"Private key a = {a}")

Attack: Pohlig-Hellman (Smooth Order)

If p-1 = q1^e1 * q2^e2 * ... with small qi, the DLP decomposes via CRT:

from sage.all import *

p = ...   # prime
g = ...   # generator
A = ...   # public key

F = GF(p)
g_F = F(g)
A_F = F(A)

# Pohlig-Hellman is built into Sage's discrete_log:
a = discrete_log(A_F, g_F)
print(f"Private key: {a}")

# If the group order is not p-1 but a specific order n:
a = discrete_log(A_F, g_F, ord=n)

If the attacker can send B = h where h is an element of a small subgroup (order q where q | p-1 and q is small), the server computes K = h^a mod p which only has q possible values. Brute-force a mod q.

# Example: if p = 2*q + 1 (safe prime) and a subgroup of order q exists
# An element of order 2: h = p-1
# Then K = (p-1)^a mod p = (-1)^a mod p = 1 or p-1
# → reveals parity of a

# Systematic: send elements of each small subgroup order
# and observe K to recover bits of a via CRT

Attack: Logjam / Export-Grade DH (512-bit)

If p is only 512 bits (export-grade), the DLP can be computed with the Number Field Sieve.

Check:

p = int(given_p)
print(f"p bit length: {p.bit_length()}")
# < 1024 bits → weak
# 512 bits → LOGJAM-style (solvable with enough compute)

For CTF purposes, p < 1024 bits often means:

Use factor(p-1) first - might factor directly
Try SageMath's discrete_log directly - might solve if smooth

Attack: g = 1 or g = p-1

Trivially weak generators:

g = 1
# A = 1^a mod p = 1 for all a
# Shared key K = 1^b mod p = 1 always
# → Key is always 1

g = p - 1  # i.e. g ≡ -1 (mod p); only two possible public values
# A = (-1)^a mod p = 1 (even a) or p-1 (odd a)
# Only 2 possible keys!

Attack: Parameter Reuse Across Sessions

If the same nonce $k$ is reused in ElGamal encryption (related to DH), with public key $y \equiv g^x \pmod{p}$ :

\mathrm{Enc}(m_1) = (g^k,\; m_1 \cdot y^k), \qquad \mathrm{Enc}(m_2) = (g^k,\; m_2 \cdot y^k)

(same $k$ in both). Then dividing the second components, $m_1 \cdot y^k$ and $m_2 \cdot y^k$ , gives $m_1 / m_2 \pmod{p}$ (ratio of plaintexts leaks).

Solving DLP Directly with Baby-Step Giant-Step (BSGS)

For small group orders or small discrete logs:

from sage.all import *

def bsgs(g, h, p, n=None):
    """Solve g^x = h mod p using Baby-Step Giant-Step."""
    if n is None:
        n = p - 1

    m = int(ceil(sqrt(n)))

    # Baby steps: compute g^j for j = 0..m
    baby = {pow(g, j, p): j for j in range(m)}

    # Giant steps: compute h * g^(-im) for i = 0..m
    gm_inv = pow(pow(g, m, p), p - 2, p)  # g^(-m) mod p
    gamma = h
    for i in range(m):
        if gamma in baby:
            return i * m + baby[gamma]
        gamma = (gamma * gm_inv) % p

    return None

x = bsgs(g, h, p)
print(f"Discrete log: {x}")

Checklist

What is the bit length of $p$ ? ( $p \lt 512$ bits: often trivially breakable)
Factor p-1 → is it smooth (small factors)?
Use SageMath discrete_log for automated solving
Check g value: g=1, g=0, g=p-1 → trivial keys
Are parameters reused across sessions? → nonce reuse
Small subgroup: can you send a non-generator point?
Use Pohlig-Hellman if p-1 factors into small primes

Last updated on Aug 1, 2025

Diffie-Hellman Attacks

Diffie-Hellman Attacks

DH Quick Review

Attack: Small Prime / Weak Parameters

Attack: Pohlig-Hellman (Smooth Order)

Attack: Small Subgroup Attack

Attack: Logjam / Export-Grade DH (512-bit)

Attack: g = 1 or g = p-1

Attack: Parameter Reuse Across Sessions

Solving DLP Directly with Baby-Step Giant-Step (BSGS)

Checklist

On this page