RSA Broadcast Attack: CRT-Based Plaintext Recovery Across Multiple Recipients

Why This Matters

Hastad's broadcast attack was first published in 1985 and remains relevant today wherever RSA is used to distribute the same session key or message to multiple recipients — a pattern common in firmware update systems, encrypted broadcast protocols, and key encapsulation mechanisms that pre-date OAEP. In 1999, Bleichenbacher demonstrated that even with padding, related-message attacks (a generalisation of Hastad's work) could break RSA-PKCS#1-v1.5 under certain conditions. More recently, implementations of TLS and S/MIME that reuse RSA key pairs across multiple recipients without per-recipient randomisation have been shown vulnerable in research settings. Any CTF challenge presenting multiple RSA ciphertexts with the same e and different moduli is almost certainly testing this exact attack family.

Core Concept

Hastad's broadcast attack exploits the interaction between the algebraic structure of RSA and the Chinese Remainder Theorem (CRT). Formally: given e recipients each with a distinct modulus n_i and the same public exponent e, each receiving the identical plaintext m encrypted as c_i = m^e mod n_i, the attacker who observes all e ciphertexts can recover m.

The key insight is that by CRT, there exists a unique integer M satisfying the system of congruences M ≡ c_i (mod n_i) for all i, provided the moduli are pairwise coprime (which they are, since each n_i is a distinct product of large primes). The CRT guarantees M < n_1·n_2·...·n_e. Because m < n_i for all i (a standard RSA assumption — the message is smaller than any individual modulus), we have m^e < n_1·n_2·...·n_e, so M = m^e holds as an ordinary integer equation, not merely modular. Taking the integer e-th root of M recovers m exactly.

The generalisation to arbitrary e is straightforward: for e=5, five ciphertexts suffice; for e=17, seventeen are needed. In practice CTF challenges almost universally use e=3. The attack precondition is: (1) the same plaintext m is encrypted under e different public keys all sharing the same e, (2) no per-recipient randomised padding is applied (or the padding is deterministic and identical), and (3) the e moduli are pairwise coprime.

Manger's extension and Franklin-Reiter related-message attack are generalisations that handle cases where plaintexts differ by a known linear relation (e.g., m_1 = a·m_2 + b for known a, b). These require Coppersmith's lattice methods but stem from the same fundamental algebraic weakness.

OAEP (Optimal Asymmetric Encryption Padding) defeats Hastad's attack completely: each encryption draws a fresh random seed r, so the padded message OAEP(m, r_i) differs for each recipient, making the e ciphertexts encrypt distinct values — the CRT combination no longer yields m^e as an integer.

Technical Deep-Dive

# Hastad broadcast attack — generalised to e recipients
# Prerequisites: pip install gmpy2 sympy

import gmpy2
from functools import reduce

def crt_two(r1, m1, r2, m2):
    """CRT for two congruences: x ≡ r1 (mod m1), x ≡ r2 (mod m2)"""
    g, s, _ = gmpy2.gcdext(m1, m2)
    assert g == 1, "Moduli not coprime"
    lcm = m1 * m2
    x = (r1 + m1 * (int(s) * (r2 - r1) % m2)) % lcm
    return x, lcm

def hastad_broadcast(pairs, e):
    """
    pairs: list of (n_i, c_i) tuples — e entries required
    e:     public exponent (same for all)
    Returns recovered plaintext m as integer, or None if root not exact.
    """
    # Iteratively apply CRT to combine all congruences
    M, prod = pairs[0]   # start: M ≡ c_0 (mod n_0), prod = n_0
    # Wait — pairs is (n_i, c_i), flip for CRT: residue=c_i, modulus=n_i
    M, prod = pairs[0][1], pairs[0][0]
    for n_i, c_i in pairs[1:]:
        M, prod = crt_two(M, prod, c_i, n_i)

    # M = m^e as integer; extract e-th root
    m, exact = gmpy2.iroot(M, e)
    if exact:
        return m
    return None

# Example usage (fill in real challenge values):
e = 3
pairs = [
    (n1, c1),
    (n2, c2),
    (n3, c3),
]

m = hastad_broadcast(pairs, e)
if m:
    plaintext = m.to_bytes((m.bit_length() + 7) // 8, 'big')
    # Strip any padding (e.g. leading 0x00 0x02 bytes for PKCS#1 v1.5)
    if b'x00' in plaintext:
        plaintext = plaintext.split(b'x00', 1)[-1]
    print("[+] Recovered plaintext:", plaintext)
else:
    print("[-] Integer root not exact — check that all ciphertexts use same m")

# SageMath version (run inside sage shell or .sage file)
def hastad_sage(pairs, e):
    from sage.arith.misc import CRT
    ns = [p[0] for p in pairs]
    cs = [p[1] for p in pairs]
    M = CRT(cs, ns)               # returns integer by default in Sage
    m = Integer(M).nth_root(e, truncate_if_no_square=False)
    return m

# RsaCtfTool command-line approach:
# python3 RsaCtfTool.py --publickey k1.pem k2.pem k3.pem 
#     --uncipher c1.bin c2.bin c3.bin --attack hastad

Cryptanalysis Methodology

1. Collect all ciphertext–modulus pairs — Identify whether the challenge provides multiple (n_i, c_i, e) tuples. Confirm e is the same for all pairs and that moduli are distinct.
2. Verify pairwise coprimality of moduli — Compute gmpy2.gcd(n_i, n_j) for each pair. A non-trivial GCD means two moduli share a prime factor — an even stronger vulnerability (direct factorisation). Handle that case first.
3. Apply CRT — Reconstruct M = m^e mod (n_1·...·n_e) using iterative two-modulus CRT or sympy.ntheory.modular.crt. Work with Python arbitrary-precision integers (not floating point).
4. Extract the integer e-th root — Call gmpy2.iroot(M, e). If exact is True, the attack is complete. If False, verify step 1 — ciphertexts may encrypt different plaintexts, or the wrong e was assumed.
5. Handle related-message variants — If plaintexts differ by a known linear relation f(m), apply the Franklin-Reiter related-message attack using Coppersmith's method in SageMath (small_roots() on a bivariate polynomial).
6. Decode the plaintext — Convert the recovered integer to bytes. Strip PKCS#1 v1.5 padding (0x00 0x02 [random non-zero bytes] 0x00 [message]) or custom challenge framing to read the flag.

Secure Implementation Note — Use RSAES-OAEP (PKCS#1 v2.2, RFC 8017) for all RSA encryption. OAEP's randomised hash mask ensures that encrypting identical plaintexts to different recipients produces independent, uniformly distributed ciphertexts. This eliminates the CRT combination that makes Hastad's attack possible. In Python use Crypto.Cipher.PKCS1_OAEP from pycryptodome.

Common Cryptanalysis Errors

• Applying CRT before confirming all e are equal — If recipients use different public exponents, the CRT combination does not yield m^e as an integer and the root will fail. Confirm e is identical for every pair.
• Working modulo n instead of over the integers — CRT must return the integer M in range [0, n_1·n_2·...·n_e). If you accidentally reduce M mod any single n_i, the attack fails silently.
• Floating-point cube root — Never use Python's built-in ** operator or math.pow for the e-th root; they lose precision for large integers. Always use gmpy2.iroot.
• Skipping the GCD check — Two challenges may supply moduli that share a factor; a simple GCD attack is far faster than CRT+root and should always be attempted first.
• Assuming e=3 always requires exactly 3 ciphertexts — Manger and other extensions show that sometimes fewer suffice if the attacker has structural knowledge about the plaintext. Consider Coppersmith if 3 ciphertexts are unavailable.
• Ignoring padding in the result — The recovered integer m may still have PKCS#1 v1.5 or custom framing. Always inspect raw bytes before declaring failure.

NICE Framework Alignment

Further Reading

• Hastad, J. (1988). Solving Simultaneous Modular Equations of Low Degree — SIAM Journal on Computing 17(2)
• Boneh, D. (1999). Twenty Years of Attacks on the RSA Cryptosystem — Notices of the AMS 46(2)
• Franklin, M. and Reiter, M. (1996). A Linear Protocol Failure for RSA with Exponent Three — CRYPTO rump session