RSA — countermeasures

Spec:: RFC 8017 (PKCS#1 v2.2) [MKJR16], FIPS 186-5 [NationalIoSaTechnology23] (signature scheme rules)
Crate path:: arcana::rsa::* (bigint, rsa, pkcs1, oaep, pss)
Cargo feature:: none — RSA is unconditionally compiled.

The RSA decrypt / sign path on arcana is currently fully unprotected against fault injection. It is also only partially audited for SCA on the bigint layer. Because the Bellcore single-fault attack on RSA-CRT ([BDL97]) is a one-fault total break, this is the highest-priority evaluation gap on the classical side and is item T1-C in the workspace roadmap.

Coverage matrix 

RSA countermeasure / threat matrix
Threat	Status	Countermeasure(s)
Bellcore single-fault on RSA-CRT	vulnerable	Plan `T1-C`: Aumüller’s algorithm ([ABF+02]), formally verified ([RG13], [RGN16]).
SPA on modular exponentiation	partial — square-always pattern present in `rsa::bigint::pow_mod` but not formally audited	Plan `T1-E`: full `rsa::bigint` audit + `black_box` shielding on conditional subtracts.
DPA on Montgomery multiplication	vulnerable	Plan `T2-I`: message blinding (multiply `c` by `r^e mod n` before decrypt, divide by `r` after). [Cor99b] is the reference.
Timing attacks on bigint operations	partial	Same plan `T1-E`. Brumley-Boneh [BB03] is the canonical baseline.
SIFA on the verify-then-output check (when added)	n/a (not present yet)	Will be addressed by infective computation [JT07] rather than test-then-branch.
Padding-oracle attacks (PKCS#1 v1.5, OAEP)	partial — PKCS#1 v1.5 decrypt has a known oracle surface (Bleichenbacher [Ble98])	Plan `T2-J`: integrate the FIPS-recommended PKCS#1 v1.5 constant-time padding-oracle handling. OAEP is more robust by design.

Bellcore single-fault attack — `T1-C`

Principle 

In CRT-RSA decryption / signing, the secret operation is split:

\[S_p = m^{d_p} \bmod p, \quad S_q = m^{d_q} \bmod q, \quad S = \mathrm{CRT}(S_p, S_q) \bmod N\]

Boneh-DeMillo-Lipton ([BDL97]) showed that if the attacker can fault either of the two half-exponentiations to produce S' ≠ S, then:

\[\gcd(N, S - S') \in \{p, q\}\]

— i.e. a single fault factorises N. With p or q known the rest of the secret key (d, dp, dq, qinv) is computed in milliseconds.

Equipment cost: ~1 k€ for a Chipwhisperer voltage glitcher; days of bench time for a skilled operator.

Aumüller’s countermeasure 

[ABF+02] (CHES 2002) introduced the standard defence. Sketch:

Choose a small prime t (e.g. 32 bits) coprime with e.
Compute the half-exponentiations modulo p·t and q·t instead of p and q — call the results S_pt and S_qt.
Reduce S_pt mod t and S_qt mod t and check they match the expected value. A fault on either half-exponentiation will change the result mod t with overwhelming probability.
CRT-combine S_pt mod p and S_qt mod q to produce the final signature.

The recent formal-verification effort [RG13] proves Aumüller’s algorithm resistant to all single-fault attacks in a fault model that includes permanent memory faults and transient faults with or without forcing-to-zero. The follow-up [RGN16] extends the formal framework to most published countermeasures and confirms that most of them are broken in slightly richer fault models — Aumüller is the gold standard for single-fault.

For a stronger fault model (e.g. SIFA, multi-fault), the infective computation approach of Joye-Tunstall [JT07] propagates the error multiplicatively into the final result rather than testing-then-branching, which is considered harder to skip with a control-flow fault. This is item T4-RSA-A in the deferred roadmap.

Implementation route in arcana 

Add a CRT-decrypt API in rsa::rsa::rsa_decrypt_crt taking the existing RsaSecretKey (which already holds p, q, dp, dq, qinv).
Implement the Aumüller skeleton on top:
- Generate t at random (32 bits, coprime with e); cached across calls if needed for performance.
- Precompute dp_t = d mod (p-1)(t-1), dq_t = d mod (q-1)(t-1), e_inv_t = e^{-1} mod t.
- Compute S_pt = m^{dp_t} mod (p·t), S_qt = m^{dq_t} mod (q·t).
- Verify S_pt^e mod t = m mod t and same for S_qt. Use silentops::ct_eq for the equality, not == — the comparison itself must be CT to avoid leaking which half was faulted (relevant for SIFA).
- If both checks pass, CRT-combine S_pt mod p and S_qt mod q. If either fails, return a deterministic error — never a partial / faulted signature, since that IS the Bellcore output.
The PKCS#1 v1.5 / OAEP / PSS layers above rsa_decrypt_raw transparently inherit the protection.
Tests: KAT regression + a fault-injection unit test that patches S_pt mid-flight and asserts the error path fires.

SCA on bigint (`T1-E`)

The rsa::bigint::BigInt arithmetic primitives need a CT audit:

BigInt::mul — schoolbook multiplication: a fixed-iteration outer + inner loop. Should be CT by structure, but the inner carry propagation must not collapse to early-exit on zero carry. Audit checkpoint: cargo asm of the release build must show a fixed-cycle inner loop independent of operand bits.
BigInt::montgomery_mul — the conditional final subtract is the classical leak point [Wal02]. Apply the same black_box shielding as ecc::field::reduce_wide.
BigInt::sub — borrow propagation; same shielding.
BigInt::cmp / cmp_le — must be CT (no early exit). The current code uses a magnitude-compare with return Less on first differing limb — this is a leak and must be rewritten to a borrow-only pattern.
BigInt::mod_inv — extended Euclidean. The standard CT alternative is a^(p-2) mod p for prime moduli (Fermat’s little theorem), reusing the Montgomery ladder.
BigInt::pow_mod — must be square-always with CT-select multiply (already the structure on the ecc::field::field_pow side; copy the pattern over, including black_box).

This audit is the prerequisite for both T1-C (Aumüller) and the later message-blinding T2-I: the CT properties of bigint are load-bearing for any RSA hardening above.

DPA on Montgomery multiplication — message blinding (`T2-I`)

Even with Aumüller, DPA on the per-iteration Montgomery multiplications inside pow_mod extracts d over ~10⁵ – 10⁶ power traces (Hamming-weight CPA on the squared intermediates).

The standard answer is message blinding [Cor99b]:

Draw a fresh random r from the RNG, compute c' = c · r^e mod N (cheap, since e is small).
Decrypt c' instead of c: m' = (c')^d mod N = m · r mod N.
Recover m = m' · r^{-1} mod N.

The DPA attacker now sees a different “blinded” message in every trace, so per-key averaging no longer aligns. A 64-bit r adds exponentiation cost of r^e mod N (negligible for typical e = 65 537) plus one r^{-1} mod N which dominates if not amortised; in practice, r-blinding is paired with exponent blinding d' = d + r' · phi(N) to also hide the bit pattern.

This is layered on top of Aumüller (Aumüller defeats single-fault; blinding defeats DPA) and is item T2-I.

Padding-oracle hardening (`T2-J`)

PKCS#1 v1.5 decrypt is the historical Bleichenbacher target [Ble98]. The mitigation is to always return the same number of bytes regardless of whether the padding parsed correctly, with the data being an internally-derived deterministic dummy in the failure path. RFC 8017 §7.2.2 gives the recipe; arcana’s current pkcs1::decrypt must be re-checked against it.

OAEP is more robust by design but still requires CT comparison of the recovered H(L) against the parameter L; arcana’s oaep::decrypt should already use silentops::ct_eq (audit pending).

Code path summary 

Path	Today (2026-04-21)	Target (post `T1-C` + `T1-E` + `T2-I`)
`rsa::bigint::*`	Mostly CT but unaudited; `cmp` has early-exit	Audited CT, `black_box` shielding throughout
`rsa::rsa::rsa_decrypt_raw`	Plain CRT, no fault check, no blinding	Aumüller + message blinding + exponent blinding
`rsa::pkcs1::decrypt`	Bleichenbacher surface unaudited	RFC 8017 §7.2.2 CT padding-oracle handling
`rsa::oaep::decrypt`	`ct_eq` on `H(L)` audit pending	Confirmed CT, regression-locked
`rsa::pss::sign` / `pss::verify`	CT-clean (no secret-dependent branches in PSS itself)	No change; relies on hardened `rsa_decrypt_raw` underneath

Reading list 

In addition to the cited papers above:

[Cor99b] — original message-blinding paper.
[BB03] — the canonical remote timing attack on OpenSSL RSA, motivating Montgomery’s CT.
[Wal02] — the Walter attack on Montgomery’s final-subtract leakage.
[Ble98] — Bleichenbacher’s PKCS#1 v1.5 oracle.
[Gir06] — RSA safe-error attacks (a fault on the dummy multiply in square-always reveals which multiplies are dummies, leaking d); motivates blinding d on top of message blinding.