hastads-broadcast-attack.ipynb

Kernel: SageMath 10.0

Break: Hastad's Broadcast Attack

Module 04 | Breaking Weak Parameters

Recover plaintext when the same message is encrypted to $e$ different recipients with small $e$ and no padding.

Why This Matters

Textbook RSA with a small public exponent $e$ and no randomized padding is vulnerable to a devastating attack discovered by Johan Hastad (1985).

The scenario is realistic: a system broadcasts the same message to multiple recipients, each with their own RSA public key but the same small exponent $e = 3$. An eavesdropper who collects just $e$ ciphertexts can recover the plaintext without factoring any modulus.

The attack uses only two tools from Module 04:

• The Chinese Remainder Theorem (Notebook 04d)

• An integer cube root (basic arithmetic)

The Scenario

Alice sends the same plaintext message $m$ to three recipients. Each recipient has their own RSA key pair, but all use the same small public exponent $e = 3$:

Recipient	Public Key	Ciphertext
Bob	$(n_1, 3)$	$c_1 = m^3 \bmod n_1$
Carol	$(n_2, 3)$	$c_2 = m^3 \bmod n_2$
Dave	$(n_3, 3)$	$c_3 = m^3 \bmod n_3$

The attacker intercepts all three ciphertexts. Since $m < n_i$ for each $i$, we know $m^3 < n_1 \cdot n_2 \cdot n_3$. The CRT lets us recover $m^3$ exactly, and then we take the integer cube root.

# === Step 1: Generate three RSA key pairs with e = 3 ===

# We use small primes for demonstration (~ 40-bit moduli)
# Each prime p must satisfy p ≡ 2 mod 3, so that gcd(3, p-1) = 1
# (otherwise e=3 won't be coprime to phi(n))

def generate_rsa_e3(bits=20):
    """Generate an RSA key pair with e = 3."""
    while True:
        p = random_prime(2^bits, lbound=2^(bits-1))
        q = random_prime(2^bits, lbound=2^(bits-1))
        if p == q:
            continue
        phi_n = (p - 1) * (q - 1)
        if gcd(3, phi_n) == 1:
            n = p * q
            d = inverse_mod(3, phi_n)
            return (n, 3, d, p, q)

set_random_seed(42)  # For reproducibility

key1 = generate_rsa_e3()
key2 = generate_rsa_e3()
key3 = generate_rsa_e3()

n1, e, d1, p1, q1 = key1
n2, _, d2, p2, q2 = key2
n3, _, d3, p3, q3 = key3

print('Three RSA key pairs with e = 3:')
print(f'  Bob:   n1 = {n1}  ({n1.nbits()} bits)')
print(f'  Carol: n2 = {n2}  ({n2.nbits()} bits)')
print(f'  Dave:  n3 = {n3}  ({n3.nbits()} bits)')
print()
print(f'All moduli are pairwise coprime: {gcd(n1, n2) == 1 and gcd(n1, n3) == 1 and gcd(n2, n3) == 1}')

# === Alice encrypts the same message to all three recipients ===

m = 123456789  # The secret message
assert m < n1 and m < n2 and m < n3, 'Message must be smaller than all moduli'

c1 = power_mod(m, 3, n1)
c2 = power_mod(m, 3, n2)
c3 = power_mod(m, 3, n3)

print(f'Plaintext message: m = {m}')
print()
print('Ciphertexts (attacker intercepts these):')
print(f'  c1 = m^3 mod n1 = {c1}')
print(f'  c2 = m^3 mod n2 = {c2}')
print(f'  c3 = m^3 mod n3 = {c3}')
print()
print('The attacker knows: c1, c2, c3, n1, n2, n3, and e = 3.')
print('The attacker does NOT know: d1, d2, d3, or the factorizations.')

Step 2: Use CRT to Recover $m^3$

We have the system of congruences:

$$m^3 \equiv c_1 \pmod{n_1}, \quad m^3 \equiv c_2 \pmod{n_2}, \quad m^3 \equiv c_3 \pmod{n_3}$$

Since $n_1, n_2, n_3$ are pairwise coprime, the CRT guarantees a unique solution $x$ modulo $N = n_1 \cdot n_2 \cdot n_3$ such that:

$$x \equiv c_i \pmod{n_i} \quad \text{for } i = 1, 2, 3$$

The key insight: since $m < n_i$ for all $i$, we have $m^3 < n_1 \cdot n_2 \cdot n_3 = N$. So $x = m^3$ exactly as an integer --- no modular reduction happened!

# === CRT to recover m^3 ===

N = n1 * n2 * n3
m_cubed = CRT([c1, c2, c3], [n1, n2, n3])

print(f'N = n1 * n2 * n3 = {N}')
print(f'N has {N.nbits()} bits')
print()
print(f'CRT solution: x = {m_cubed}')
print()

# Verify: this should equal m^3 as an integer
print(f'Actual m^3    = {m^3}')
print(f'CRT result    = {m_cubed}')
print(f'Match: {m_cubed == m^3}')
print()
print(f'Is m^3 < N? {m^3 < N}  (this is WHY the attack works)')

Step 3: Take the Integer Cube Root

We now have the exact value $m^3$ (not reduced modulo anything). Taking the integer cube root recovers $m$ directly:

$$m = \sqrt[3]{x}$$

No factoring. No private keys. Just CRT and a cube root.

# === Take the integer cube root ===

# SageMath's integer nth root
m_recovered = Integer(m_cubed).nth_root(3)

print(f'Integer cube root of CRT result:')
print(f'  m_recovered = {m_cubed}^(1/3) = {m_recovered}')
print()
print(f'Original message: {m}')
print(f'Recovered message: {m_recovered}')
print(f'Attack successful: {m_recovered == m}')
print()
print('The entire attack required:')
print('  1. Three intercepted ciphertexts (public channel)')
print('  2. One CRT computation')
print('  3. One integer cube root')
print('  Total cost: essentially FREE')

Cost Analysis

Let's compare the cost of this attack vs. the "honest" approach of factoring.

# === Cost comparison ===

print('=== Hastad\'s Attack Cost ===')
print(f'CRT computation: O(e) = O(3) multiplications of {n1.nbits()}-bit numbers')
print(f'Cube root:       O(log(m^3)) = O({(m^3).nbits()}) bit operations')
print(f'Total:           TRIVIAL')
print()
print('=== Factoring n1 (for comparison) ===')
print(f'n1 = {n1} ({n1.nbits()} bits)')

t0 = walltime()
factors = factor(n1)
t1 = walltime()

print(f'n1 = {factors}')
print(f'Factoring took: {(t1-t0)*1000:.2f} ms')
print()
print('For our toy example, factoring is also fast.')
print('But for 2048-bit RSA, factoring is infeasible,')
print('while Hastad\'s attack remains instant given e ciphertexts.')

The Fix: Randomized Padding (OAEP)

The attack works because the same plaintext $m$ is encrypted each time. If we add random padding before encryption, each recipient sees a different padded message:

$$c_i = \text{pad}(m, r_i)^e \bmod n_i$$

where $r_i$ is fresh randomness for each encryption. Now the CRT recovers $\text{pad}(m, r_1)^e$ combined with $\text{pad}(m, r_2)^e$ and $\text{pad}(m, r_3)^e$, which are three different values --- the system of congruences yields garbage.

RSA-OAEP (see the Connect notebook on OAEP) is the standard way to add this padding. It ensures that even identical messages produce different ciphertexts.

# === Demonstration: padding defeats the attack ===

import hashlib

def simple_pad(m, randomness, modulus_bits):
    """Toy padding: concatenate message with random bytes."""
    # In real OAEP, this is a Feistel-like construction
    m_bytes = int(m).to_bytes(16, 'big')
    r_bytes = int(randomness).to_bytes(16, 'big')
    padded = int.from_bytes(m_bytes + r_bytes, 'big')
    return padded

# Same message, different random padding each time
r1, r2, r3 = ZZ.random_element(2^64), ZZ.random_element(2^64), ZZ.random_element(2^64)
m_padded1 = simple_pad(m, r1, n1.nbits())
m_padded2 = simple_pad(m, r2, n2.nbits())
m_padded3 = simple_pad(m, r3, n3.nbits())

print('With randomized padding, each encryption sees a DIFFERENT input:')
print(f'  pad(m, r1) = {m_padded1}')
print(f'  pad(m, r2) = {m_padded2}')
print(f'  pad(m, r3) = {m_padded3}')
print()
print('These are three different values, so the CRT trick fails.')
print('The attacker would need to factor n_i to decrypt any single ciphertext.')

Exercises

1. $e = 5$ with 5 recipients: Modify the attack for $e = 5$. Generate 5 RSA key pairs with $e = 5$, encrypt the same message, and recover it using CRT + 5th root.

2. What if $m$ is large? What happens if $m^e > n_1 \cdot n_2 \cdot \ldots \cdot n_e$? Try with a message close to $n_i$ in size. Does the attack still work? Why or why not?

3. Partial information: If you only have 2 ciphertexts (not 3) with $e = 3$, can you still recover $m$? What additional information would you need?

Summary

Component	Role in the Attack
Small $e$	Means $m^e$ is "small" relative to the product of moduli
No padding	Same $m$ encrypted each time, enabling CRT combination
CRT (Notebook 04d)	Recovers $m^e$ exactly from $e$ congruences
Integer $e$-th root	Extracts $m$ from $m^e$ (works because $m^e < N$)

Key takeaways:

• Textbook RSA with small $e$ and no padding is completely broken when the same message is sent to $e$ or more recipients.

• The attack costs essentially nothing: one CRT computation and one $e$-th root.

• Randomized padding (OAEP) is the fix: it makes each ciphertext depend on fresh randomness, so the CRT combination produces garbage.

• This is why every RSA standard mandates padding. Textbook RSA is a teaching tool, not a cryptosystem.

---

Back to Module 04: Number Theory and RSA