Fault Injection Attacks — one faulty RSA-CRT signature factors the modulus outright

Inducing a computational error in a signing/decryption device — a glitched voltage or clock edge, a bit-flip, a corrupted intermediate value — so that it produces a *wrong* output on a request it would normally answer correctly; the flagship payoff is that one such wrong RSA-CRT signature factors the modulus outright, and a fault targeting a signature nonce degrades ECDSA to an easier nonce-leak problem.

The signal that gives it away

- **The oracle produces both a correct and a faulty output for the *same* message/request. This is the core precondition — a single faulty output is often not enough; the exploit typically needs to compare a faulty result against either a known message or a known-good result for that message. - Explicit fault framing in the challenge: a parameter like `?glitch=1`, flavor text mentioning "glitch," "fault," "hardware error," "Bellcore," or a signing service that "sometimes" returns a wrong signature. - RSA signing implemented via CRT (mentions `s_p`/`s_q`, `dmp1`/`dmq1`/`iqmp`, or any performance-optimized RSA-CRT scheme) — this is the specific structural precondition the Bellcore attack needs; plain (non-CRT) modular exponentiation is not vulnerable to this exact trick. - A check you can apparently skip under fault conditions — an `if password_ok` / `if signature_valid` branch that a glitch can jump over, or a counter that can be corrupted mid-loop. For non-RSA targets, this is often the whole attack: a skipped verification just hands you the result directly, no algebra required. - ECDSA/DSA framed the same way** — a signing service that occasionally returns a signature under stated "fault" conditions. Here the signal to look for is different: not modulus factoring, but a nonce k that the fault has zeroed, halved, or otherwise corrupted in a structured way, which routes to the nonce-leak family instead (see below).

How it's exploited

RSA-CRT (Bellcore attack). CRT-optimized RSA signing computes s_p = m^d mod p and s_q = m^d mod q separately, then recombines them via CRT into the full signature s. If a fault corrupts *exactly one* of the two branches (say s_q), the resulting faulty signature s' is still correct modulo p but wrong modulo q. That single-branch corruption is what the Chinese Remainder Theorem — recombining residues across coprime moduli recombination turns into an exploitable factor: s' ≡ s mod p but s' ≢ s mod q, so gcd(s' - s, N) (or an equivalent gcd built from s' alone) lands exactly on p.

Two field-tested variants, depending on what you actually have:

```python from math import gcd

# Variant 1: message m is known, only the faulty signature s' is needed p = gcd(pow(s_faulty, e, N) - m, N) # s_faulty^e == m mod p, != m mod q q = N // p

# Variant 2: a correct signature s AND a faulty s' of the SAME message, # message itself not required p = gcd(s - s_faulty, N) q = N // p ```

Always validate 1 < p < N before trusting the result — see "What does NOT work" below for when this check fails. Once p, q are recovered, deriving the private key is the same mechanical step as any other factoring route (see RSA Fundamentals — the routing hub: which artifact points to which attack):

```python from sympy import mod_inverse

phi = (p - 1) * (q - 1) d = mod_inverse(e, phi) ```

With d recovered, decrypt or forge anything under that key. Reference: Boneh, DeMillo & Lipton, 1997 — the original description of this class of RSA-CRT fault attack, still the standard citation for it.

ECDSA/DSA nonce faults. A fault that perturbs the ephemeral nonce k during signing — zeroing it, halving it, or otherwise biasing a known subset of its bits — does not directly factor anything, but it turns the signature into exactly the kind of partial-information leak the nonce-recovery family is built for. If the fault fully zeroes or otherwise makes k fully known or repeated, treat it as ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra / known-nonce recovery; if it only biases some bits, it is a Hidden-Number-Problem instance for DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery. Public research on this exact angle documents recovering deterministic ECDSA/EdDSA keys from signatures with a large fraction of the nonce's bits corrupted by fault injection, well beyond what classical (non-lattice) differential fault attacks could use.

Non-RSA, non-signature targets. Where there's no CRT or nonce structure to exploit algebraically, a fault that skips a verification branch (if password_ok:, a signature-check before returning a secret, a loop-bound check) is often the entire attack: the glitch just makes the device do the thing it was gatekeeping. No gcd, no lattice — the fault *is* the exploit.

What does NOT work

- Faulting both CRT branches at once (or an unpredictable number of them). The gcd trick requires *exactly one* branch to be wrong. If both s_p and s_q are corrupted, s' is wrong modulo both primes and gcd(s' - s, N) (or the single-signature variant) typically returns 1 or N — no factor, no signal. If a fault campaign produces a mix of single- and double-branch corruptions, filter for the useful faulty signatures rather than assuming every glitched output is exploitable; check 1 < p < N on every candidate before trusting it. - Expecting this against non-CRT RSA. Plain modular exponentiation with the private exponent d (no CRT speedup) has no p-branch/q-branch split to desynchronize — a fault there just gives you a wrong number with no algebraic structure to recover a factor from. Confirm the target actually uses CRT before reaching for this attack. - Assuming a single faulty output alone is enough. Variant 1 above still needs the message m; variant 2 needs a *correct* signature of the same message alongside the faulty one. A lone faulty signature with neither of those is (on its own, without further tooling) not directly exploitable by this technique. - Ignoring sign-then-verify defenses. A well-implemented CRT-RSA signer verifies its own output (recomputes and checks s^e ≡ m mod N) before releasing it, and simply withholds the response if the check fails. Where that defense is present, the fault has to beat *both* the CRT computation *and* the self-check to ever reach the attacker — a much narrower fault window than an implementation with no post-check. If every response you observe verifies cleanly, this technique's precondition (a released, wrong signature) may simply not be reachable, and the intended path is elsewhere. - Confusing this with passive side-channel attacks. Fault injection *actively tampers* with the computation to force a wrong output; Power Analysis (SPA/DPA/CPA) — reading a key off a device's power draw, Cache-Timing Attack — recovering key bytes from which cache line a table lookup touched, and Timing Attack — recovering a secret from how long a secret-dependent operation takes are *passive* — they observe (traces, cache lines, response time) without altering the result. A challenge that only gives you consistent, always-correct outputs with variable timing/power is a different page, not this one. - Treating a recovered faulty ECDSA nonce leak as automatic key recovery. A single fully-known or fully-repeated nonce collapses to closed-form algebra (ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra); a partially-biased one needs enough independent faulty signatures to make the lattice problem well-determined (DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery) — one biased sample alone is rarely sufficient.

Related

RSA Fundamentals — the routing hub: which artifact points to which attack Chinese Remainder Theorem — recombining residues across coprime moduli Integer Factorization Methodology — which factoring attack to try, in what order ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra DSA/ECDSA Biased-Nonce Lattice Attack — turning partial nonce leaks into a private-key recovery ECDSA Fundamentals — the s*k = h + d*r identity that routes every nonce attack RSA Signature Forgery — homomorphic combination and lax padding checks forge signatures without the private key Power Analysis (SPA/DPA/CPA) — reading a key off a device's power draw Error / Boolean Oracle Attack — turn any distinguishable valid/invalid response into a key or plaintext