###################################################################
RSA — countermeasures
###################################################################

:Spec:        RFC 8017 (PKCS#1 v2.2) :cite:`rfc8017`,
              FIPS 186-5 :cite:`fips186_5` (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 (:cite:`boneh1997dfa`) 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.

.. contents::
   :local:
   :depth: 2

Coverage matrix
===============

.. list-table:: RSA countermeasure / threat matrix
   :header-rows: 1
   :widths: 25 18 57

   * - Threat
     - Status
     - Countermeasure(s)
   * - Bellcore single-fault on RSA-CRT
     - **vulnerable**
     - Plan ``T1-C``: Aumüller's algorithm
       (:cite:`aumuller2002rsa_crt`), formally verified
       (:cite:`rauzy2013_formal_crt_rsa`,
       :cite:`rauzy2016_algorithmic_crt_rsa`).
   * - 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).
       :cite:`coron1999rsa_blinding` is the reference.
   * - Timing attacks on bigint operations
     - **partial**
     - Same plan ``T1-E``. Brumley-Boneh
       :cite:`brumley2003remote_timing` is the canonical baseline.
   * - SIFA on the verify-then-output check (when added)
     - n/a (not present yet)
     - Will be addressed by infective computation
       :cite:`joye2007rsa_infective` 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 :cite:`bleichenbacher1998rsa`)
     - 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:

.. math::

    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 (:cite:`boneh1997dfa`) showed that if the
attacker can fault either of the two half-exponentiations to
produce ``S' ≠ S``, then:

.. math::

    \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
-------------------------

:cite:`aumuller2002rsa_crt` (CHES 2002) introduced the standard
defence. Sketch:

1. Choose a small prime ``t`` (e.g. 32 bits) coprime with ``e``.
2. Compute the half-exponentiations modulo ``p·t`` and ``q·t``
   instead of ``p`` and ``q`` — call the results ``S_pt`` and
   ``S_qt``.
3. 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.
4. CRT-combine ``S_pt mod p`` and ``S_qt mod q`` to produce the
   final signature.

The recent formal-verification effort
:cite:`rauzy2013_formal_crt_rsa` 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
:cite:`rauzy2016_algorithmic_crt_rsa` 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
:cite:`joye2007rsa_infective` 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
------------------------------

1. Add a CRT-decrypt API in ``rsa::rsa::rsa_decrypt_crt`` taking
   the existing ``RsaSecretKey`` (which already holds ``p``, ``q``,
   ``dp``, ``dq``, ``qinv``).
2. 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.
3. The PKCS#1 v1.5 / OAEP / PSS layers above ``rsa_decrypt_raw``
   transparently inherit the protection.
4. 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 :cite:`walter2002montgomery_leak`. 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**
:cite:`coron1999rsa_blinding`:

1. Draw a fresh random ``r`` from the RNG, compute
   ``c' = c · r^e mod N`` (cheap, since ``e`` is small).
2. Decrypt ``c'`` instead of ``c``: ``m' = (c')^d mod N = m · r mod N``.
3. 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
:cite:`bleichenbacher1998rsa`. 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
=================

.. list-table::
   :header-rows: 1
   :widths: 30 35 35

   * - 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:

* :cite:`coron1999rsa_blinding` — original message-blinding paper.
* :cite:`brumley2003remote_timing` — the canonical remote timing
  attack on OpenSSL RSA, motivating Montgomery's CT.
* :cite:`walter2002montgomery_leak` — the Walter attack on
  Montgomery's final-subtract leakage.
* :cite:`bleichenbacher1998rsa` — Bleichenbacher's PKCS#1 v1.5
  oracle.
* :cite:`giraud2006rsa_safe_error` — 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.