small-subgroup-attack.ipynb

Kernel: SageMath 10.0

Break: Small Subgroup Attack on Diffie-Hellman

Module 05 | Breaking Weak Parameters

If we don't validate public keys, an attacker can confine the shared secret to a tiny subgroup.

Why This Matters

Diffie-Hellman key exchange assumes both parties send legitimate public keys of the form $A = g^a \bmod p$. But what if an attacker sends a malicious value instead?

If $p$ is not a safe prime, then $p - 1$ has small factors, and the group $\mathbb{Z}/p\mathbb{Z}^*$ contains small subgroups. An attacker can:

1. Find an element $h$ of small order $r$ (where $r \mid p - 1$)

2. Send $h$ as their "public key" instead of $g^a$

3. The victim computes $h^b \bmod p$ as the shared secret --- but this value is confined to only $r$ possibilities

4. The attacker brute-forces all $r$ values to find the shared secret

This attack requires no knowledge of the victim's secret exponent $b$. The attacker only needs to search a space of size $r$ instead of size $p - 1$.

The Scenario

Alice and Bob agree on DH parameters $(p, g)$ where $p$ is a prime but not a safe prime. This means $p - 1$ has small factors. Eve (the attacker) intercepts and replaces one of the public keys with an element of small order.

Let's pick $p = 433$. Check the factorization of $p - 1$:

# === Step 1: Pick a prime p where p-1 has small factors ===

p = 433
print(f'p = {p}')
print(f'Is p prime? {is_prime(p)}')
print(f'p - 1 = {p - 1}')
print(f'p - 1 = {factor(p - 1)}')
print()

# p - 1 = 432 = 2^4 * 3^3
# The small prime power factors are: 2, 3, 4, 8, 9, 16, 27
# This gives us subgroups of orders: 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, ...

divs = divisors(p - 1)
print(f'Possible subgroup orders (divisors of p-1): {divs}')
print(f'Number of subgroup orders: {len(divs)}')
print()
print('Small subgroups are the danger!')
print(f'Smallest nontrivial subgroup orders: {[d for d in divs if 1 < d <= 27]}')

# === Step 2: Set up a legitimate DH exchange ===

g = primitive_root(p)
print(f'Generator g = {g}')
print(f'Order of g = {Mod(g, p).multiplicative_order()} (should be {p-1})')
print()

# Bob's secret exponent
b = 317  # Bob's secret (unknown to Eve)
B = power_mod(g, b, p)
print(f"Bob's secret:     b = {b}")
print(f"Bob's public key: B = g^b mod p = {B}")
print()
print('Eve intercepts B and replaces it with a malicious value...')

Step 3: Eve Constructs a Malicious Public Key

Eve picks a small factor $r$ of $p - 1$ and finds an element $h$ of order $r$.

To find an element of order $r$: take any generator $g$ and compute $h = g^{(p-1)/r} \bmod p$. By Lagrange's theorem, $h$ has order $r$.

Eve sends $h$ to Alice as if it were Bob's public key.

# === Step 3: Eve constructs an element of small order ===

# Pick a small factor of p - 1
r = 3  # subgroup of order 3
print(f'Target subgroup order: r = {r}')
print(f'Does r divide p-1? {(p - 1) % r == 0}')
print()

# Construct element of order r
h = power_mod(g, (p - 1) // r, p)
print(f'Malicious public key: h = g^((p-1)/{r}) mod p = {h}')
print(f'Order of h: {Mod(h, p).multiplicative_order()} (should be {r})')
print()

# List all elements in this subgroup
subgroup = sorted(set(power_mod(h, i, p) for i in range(r)))
print(f'The entire subgroup of order {r}: {subgroup}')
print(f'Only {r} possible values for the shared secret!')

# === Step 4: Alice computes the "shared secret" using the malicious key ===

# Alice has her own secret exponent
a = 251  # Alice's secret
A = power_mod(g, a, p)

# Alice receives h (thinking it's Bob's public key B)
# Alice computes: shared_secret = h^a mod p
compromised_secret = power_mod(h, a, p)

print(f"Alice's secret:    a = {a}")
print(f"Alice computes:    h^a mod p = {h}^{a} mod {p} = {compromised_secret}")
print()
print(f'Is the compromised secret in the small subgroup? {compromised_secret in subgroup}')
print(f'The shared secret is one of only {r} values: {subgroup}')

Step 5: Eve Brute-Forces the Shared Secret

Eve doesn't know Alice's secret $a$, but she knows the shared secret $h^a \bmod p$ must be one of only $r$ values. She simply tries all of them.

In a real protocol, the shared secret is used to derive a symmetric key. Eve can test each candidate by trying to decrypt the first message.

# === Step 5: Eve brute-forces the small subgroup ===

print(f'Eve tries all {r} possible shared secrets:')
print()

for i in range(r):
    candidate = power_mod(h, i, p)
    match = '  <-- FOUND IT!' if candidate == compromised_secret else ''
    print(f'  h^{i} mod p = {candidate}{match}')

print()
print(f'Eve needed at most {r} attempts instead of {p-1}.')
print(f'Speedup: {(p-1) / r:.0f}x')

# === Try larger small subgroups ===

print('=== Varying the subgroup order ===')
print(f'p - 1 = {p - 1} = {factor(p - 1)}')
print()

for r in [2, 3, 4, 6, 8, 9, 12, 16, 27]:
    if (p - 1) % r != 0:
        continue
    h_r = power_mod(g, (p - 1) // r, p)
    compromised = power_mod(h_r, a, p)
    # Verify it's in the subgroup
    assert power_mod(compromised, r, p) == 1
    print(f'  r = {r:3d}: search space = {r:3d}, '
          f'speedup = {(p-1)//r:5d}x, '
          f'compromised secret = {compromised}')

print()
print('Smaller r = less work for Eve. r = 2 means a coin flip!')

The Fix: Public Key Validation

There are two complementary defenses:

1. Use safe primes: If $p = 2q + 1$ with $q$ prime, the only subgroup orders are $1, 2, q, 2q$. The only "small" subgroup has order 2 (elements $\{1, p-1\}$), which is trivially checkable.

2. Validate received public keys: Check that the received value $A$ satisfies:

   • $2 \leq A \leq p - 2$ (not 0, 1, or $p-1$)

   • $A^q \equiv 1 \pmod{p}$ (for safe prime $p = 2q + 1$, this confirms $A$ is in the subgroup of order $q$)

# === The fix: validate public keys ===

def validate_public_key(A, p):
    """Validate a DH public key against small subgroup attacks."""
    # Basic range check
    if A < 2 or A > p - 2:
        return False, 'Out of range [2, p-2]'
    
    # For safe prime p = 2q+1: check A has order q or 2q
    q = (p - 1) // 2
    if is_prime(q):
        # A^q must be 1 (order q) or p-1 (order 2q = p-1)
        check = power_mod(A, q, p)
        if check != 1 and check != p - 1:
            return False, f'A^q mod p = {check}, not 1 or p-1'
        return True, 'Valid (safe prime check passed)'
    
    # For non-safe prime: check A^(p-1) = 1 and A has large order
    order = Mod(A, p).multiplicative_order()
    if order < 100:  # Reject small-order elements
        return False, f'Order too small: {order}'
    return True, f'Order = {order}'

# Test with safe prime
p_safe = 2267  # safe prime: (2267-1)/2 = 1133 is prime
g_safe = primitive_root(p_safe)

print(f'Safe prime p = {p_safe}, p-1 = {factor(p_safe - 1)}')
print()

# Legitimate key
legit = power_mod(g_safe, 42, p_safe)
ok, msg = validate_public_key(legit, p_safe)
print(f'Legitimate key {legit}: {msg}')

# Malicious keys
for bad in [0, 1, p_safe - 1, p_safe]:
    ok, msg = validate_public_key(bad, p_safe)
    print(f'Malicious key {bad}: {msg}')

Exercises

1. Larger prime: Try $p = 15121$ where $p - 1 = 15120 = 2^4 \cdot 3^3 \cdot 5 \cdot 7$. Find elements of order 5 and 7. How many attempts does Eve need for each?

2. Combined attack: Use the subgroup of order $2 \cdot 3 = 6$ to learn $a \bmod 6$. Then use order 16 to learn $a \bmod 16$. Can you combine these with CRT to narrow down $a$ even further?

3. Active vs. passive: In this attack, Eve must be an active (man-in-the-middle) attacker. Why can't she mount this attack by just eavesdropping?

Summary

Concept	Detail
Attack	Send an element of small order $r$ as a public key
Effect	Shared secret is confined to $r$ possible values
Cost to attacker	$O(r)$ brute-force attempts
Prerequisite	$p - 1$ has small factors (not a safe prime)
Fix	Use safe primes + validate public keys

Key takeaways:

• The small subgroup attack is an active attack: Eve replaces a public key in transit.

• The victim's computation $h^b \bmod p$ is "trapped" in a subgroup of size $r$.

• Safe primes eliminate all dangerous small subgroups.

• Even with safe primes, public key validation is essential defense-in-depth.

---

Back to Module 05: Discrete Log and Diffie-Hellman