Recovering RSA Private Keys from Malformed Signatures via Fault Injection

Why This Matters

The Bellcore attack on CRT-RSA signatures was published in 1996 by Boneh, DeMillo, and Lipton, fundamentally changing the security requirements for any hardware or software that performs RSA signing. The core finding was devastating: a single computational error in the signing process — whether caused by cosmic-ray bit-flip, voltage glitching, laser fault injection, or a software bug — immediately reveals the private key factorisation. CVE-2017-15361 (ROCA) and numerous smart-card vulnerabilities demonstrate that fault attacks against RSA signing remain an active threat. In software CTF challenges, fault injection is simulated by giving the solver a "faulty" signature alongside a "correct" one, or by simulating a signing oracle that occasionally returns erroneous values. The mathematical technique is pure algebra — no hardware access required to exploit it once the faulty output is in hand.

Core Concept

CRT-RSA (Chinese Remainder Theorem RSA) is a standard optimisation for RSA signing that computes two partial signatures and recombines them, making signing approximately four times faster than naive modular exponentiation. The computation is:

s_p = m^(d mod p-1) mod p (via Fermat's little theorem) s_q = m^(d mod q-1) mod q s = CRT(s_p, s_q) = s_q + q · (q^(-1) mod p) · (s_p - s_q) mod n

(Garner's formula).

Now suppose a single-byte fault corrupts s_p, producing s_p' ≠ s_p while s_q remains correct. Garner's formula then produces a faulty signature s':

s' ≡ s_q (mod q) [correct — s_q was unaffected] s' ≢ s_p (mod p) [wrong — s_p was faulted]

Meanwhile, the correct signature s satisfies s^e ≡ m (mod n). The faulty signature satisfies:

(s')^e ≡ m (mod q) [because s' is correct mod q] (s')^e ≢ m (mod p) [because s' is wrong mod p]

Therefore, (s')^e - m ≡ 0 (mod q) but ≢ 0 (mod p), which means:

gcd((s')^e - m, n) = q

This immediately factors n, giving p = n/q and full private-key recovery. The attack requires: one correct signature s (or the original message m plus the ability to verify), one faulty signature s', the public key (n, e), and knowledge of the signed message m (or its hash). No knowledge of the private key is needed beyond what the signatures reveal.

Software-level countermeasure: after computing s via CRT, verify that s^e ≡ m (mod n) before returning s. If the check fails, discard the result and either retry or raise an error. This single verification step eliminates the Bellcore attack entirely at negligible cost relative to the signing operation.

Technical Deep-Dive

# Bellcore fault attack on CRT-RSA
# Prerequisites: pip install gmpy2 pycryptodome
import gmpy2

def bellcore_attack(n, e, m, s_faulty):
    """
    n:        RSA modulus (integer)
    e:        public exponent (integer)
    m:        signed message or its hash as integer
    s_faulty: faulty signature (integer) — one of s_p or s_q was wrong

    Returns (p, q) if attack succeeds, else None.
    """
    # Compute s_faulty^e mod n
    s_e = pow(s_faulty, e, n)

    # If fault was in s_p:  gcd(s_faulty^e - m, n) = q
    # If fault was in s_q:  gcd(s_faulty^e - m, n) = p
    diff = (s_e - m) % n
    g = int(gmpy2.gcd(diff, n))

    if g > 1 and g < n:
        p, q = g, n // g
        assert p * q == n, "Factorisation check failed"
        print(f"[+] Factored n!
  p = {p}
  q = {q}")
        return p, q
    else:
        print("[-] GCD attack failed — check inputs or try (s_faulty^e + m) % n")
        # Try additive variant (sometimes message is negated in signing)
        diff2 = (s_e + m) % n
        g2 = int(gmpy2.gcd(diff2, n))
        if g2 > 1 and g2 < n:
            p, q = g2, n // g2
            print(f"[+] Factored n (additive variant)!
  p={p}
  q={q}")
            return p, q
    return None

def recover_private_key(p, q, e):
    """Recover d from p, q, e."""
    phi = (p - 1) * (q - 1)
    d = int(gmpy2.invert(e, phi))
    return d

# Simulation: what a CRT-RSA implementation looks like (for reference)
def crt_rsa_sign_correct(m, d, p, q):
    """Correct CRT-RSA signing with post-computation verification."""
    n = p * q
    dp = d % (p - 1)
    dq = d % (q - 1)
    s_p = pow(m, dp, p)
    s_q = pow(m, dq, q)
    q_inv = int(gmpy2.invert(q, p))
    h = (q_inv * (s_p - s_q)) % p
    s = s_q + q * h           # Garner recombination
    # COUNTERMEASURE: verify before returning
    assert pow(s, e, n) == m % n, "Fault detected — discarding signature"
    return s

# In a CTF challenge context:
# 1. You are given: n, e, message (or hash), correct_sig, faulty_sig
# 2. Run bellcore_attack(n, e, message, faulty_sig)
# 3. Use recovered (p, q) to compute d = gmpy2.invert(e, (p-1)*(q-1))
# 4. Decrypt ciphertext or forge signatures as required

# Tools: pure Python/gmpy2 is sufficient; no specialised tool needed
# SageMath: factor(gcd(pow(s_faulty,e,n) - m, n)) achieves the same result

Cryptanalysis Methodology

1. Identify the fault injection scenario — Determine whether the challenge supplies two signatures (one correct, one faulty) or simulates a signing oracle that intermittently returns faulty values. Note whether m is provided as a raw integer or a hash.
2. Extract public parameters — Parse (n, e) from the challenge. If m is a hash, ensure you are using the integer representation of the hash, not the raw message string.
3. Compute s_faulty^e mod n — This recovers the "decrypted" faulty signature. The distance from m (mod n) factors the modulus.
4. Run GCD — gcd((s_faulty^e - m) % n, n). A result g in (1, n) is a prime factor. Also try gcd((s_faulty^e + m) % n, n) for sign-variant challenges.
5. Recover private key — Compute phi(n) = (p-1)(q-1), then d = gmpy2.invert(e, phi). Verify d works: pow(pow(m, e, n), d, n) == m.
6. Complete the challenge objective — Use d to decrypt a target ciphertext or produce a forged signature as required.

Secure Implementation Note — Always verify the signature output before returning it from a CRT-RSA implementation: assert pow(s, e, n) == m_hash (mod n). This single check — costing one additional modular exponentiation — completely neutralises the Bellcore fault attack. Hardware implementations should additionally use error-correcting storage for intermediate values and avoid predictable fault injection windows by randomising computation timing.

Common Cryptanalysis Errors

• Using the correct signature instead of the faulty one — The attack requires the faulty output. Using the correct signature gives GCD = 1 or GCD = n (trivial). Carefully identify which is which.
• Applying the hash function after the fact — If the signing scheme signs H(message), the m in the GCD formula is the integer value of H(message), not the message itself. Using the wrong m gives a trivial GCD.
• Off-by-one in phi computation — Some implementations use Carmichael's lambda instead of Euler's phi. If gmpy2.invert(e, phi) fails (not coprime), try lambda(n) = lcm(p-1, q-1).
• Assuming two faulty signatures are needed — Unlike some other fault attacks, the Bellcore attack requires only one faulty signature plus the public key and the signed value. A second correct signature is useful for confirming d but not required.
• Ignoring EMSA-PKCS1-v1_5 encoding — If the signing scheme uses PKCS#1 v1.5 signature encoding, m in the GCD formula is the EMSA-encoded message integer, not the raw hash. Always check the signing specification.
• Not testing the additive variant — Some challenge implementations negate the message in the CRT computation. If the standard GCD fails, try gcd(s_faulty^e + m, n).

NICE Framework Alignment

Further Reading

• Boneh, D., DeMillo, R., and Lipton, R. (1997). On the Importance of Checking Cryptographic Protocols for Faults — EUROCRYPT 1997
• Aumuller et al. (2002). Fault Attacks on RSA with CRT: Concrete Results and Practical Countermeasures — CHES 2002
• Bar-El et al. (2006). The Sorcerer's Apprentice Guide to Fault Attacks — Proceedings of the IEEE 94(2)