###################################################################
ECDSA / ECDH — countermeasures
###################################################################

:Spec:        FIPS 186-5 :cite:`fips186_5`, RFC 6979
              :cite:`rfc6979`, NIST SP 800-56A :cite:`nist_sp_800_56a`
:Crate path:  ``arcana::ecc::curves`` (``Curve`` trait + 7 unit
              structs), ``arcana::ecc::ecdsa`` (LIMBS-generic
              internals), ``arcana::ecc::curve`` (Jacobian point ops
              + ``scalar_mul_point``), ``arcana::ecc::field``
              (multi-precision modular arithmetic).
:Cargo feature: none — ECDSA / ECDH are unconditionally compiled.

ECDSA / ECDH on the seven short-Weierstrass curves (P-256, P-384,
P-521, secp256k1, brainpoolP256r1, brainpoolP384r1, brainpoolP512r1)
share a single CT scalar-multiplication path,
``ecc::curve::scalar_mul_point``, which has been hardened (commit
``76191c1``, 2026-04-21) and is **the** primary defensive surface
for the family.

This chapter is the most extensive of the per-algorithm chapters
because the published attack literature on ECDSA is the richest of
any classical primitive (LadderLeak, Minerva, OpenSSL CVE-2024-13176
all landed in 2020-2024).

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

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

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

   * - Threat
     - Status
     - Countermeasure(s)
   * - SPA / SEMA on scalar mul
     - **implemented**
     - CT Montgomery ladder ``scalar_mul_point`` with
       ``ct_swap`` between two accumulator points;
       ``point_add_ct`` is branch-free on point coords.
   * - Software / cache-timing on scalar mul
     - **implemented**
     - Same ladder. Release-asm verification:
       ``scalar_mul_point`` = 1 branch (loop), ``point_double`` =
       0, ``point_add_ct`` = 0.
   * - LadderLeak
       (:cite:`aranha2020_ladderleak`)
     - **implemented**
     - The ladder does not branch on bit-length of the scalar
       and uses ``ct_swap`` masked by the bit value.
   * - Minerva (:cite:`jancar2020_minerva`)
     - **partial — audit pending**
     - The ECDSA nonce sampling and ``bits2int`` /
       ``rfc6979_k`` paths must be re-audited specifically for
       bit-length leakage on ``k``. Item ``T1-B``.
   * - DPA / CPA on field operations
     - **vulnerable**
     - Plan ``T2-A``: Z-coordinate randomization
       (:cite:`brier2002weierstrass_sca`,
       :cite:`coron1999dpa_ecc`).
   * - Template attacks on ladder traces
     - **vulnerable**
     - Plan ``T2-A`` (Z-rerand destroys profile alignment) +
       ``T2-B`` (scalar blinding).
   * - Single-fault on RFC 6979 deterministic ECDSA
     - **vulnerable**
     - Plan ``T1-D``: optional hedged mode mirroring
       :cite:`cfrg_hedged_sigs`.
   * - Invalid-curve attack on peer pubkey (ECDH)
     - **implemented**
     - ``parse_and_validate_pubkey`` enforces ``y^2 = x^3 + ax +
       b`` before any scalar mul.
   * - Small-subgroup attack on ECDH output
     - **implemented**
     - ``ecdh_internal`` rejects the point at infinity output.

SPA / cache-timing — CT Montgomery ladder (implemented)
=======================================================

State as of 2026-04-21
----------------------

The scalar multiplication path was hardened in commit ``76191c1``
(2026-04-21). The structure of the loop body is now:

.. code-block:: rust

   for i in (0..total_bits).rev() {
       let bit = (k.limbs[i / 64] >> (i % 64)) & 1;
       ct_swap(&mut r0, &mut r1, bit);
       r1 = point_add_ct(&r0, &r1, params);
       r0 = point_double(&r0, params);
       ct_swap(&mut r0, &mut r1, bit);
   }

Three source-level secret-dependent branches were removed:

1. **point_double's** ``if pt.z.is_zero() { infinity() } else
   { ... }`` — replaced by the observation that the dbl-2007-bl
   formula naturally produces ``Z3 = 0`` when ``Z1 = 0`` (because
   ``Z3 = (Y1+Z1)^2 - YY - ZZ = Y1^2 - Y1^2 - 0``).
2. **point_add_ct's** ``if h_zero && r_zero / h_zero && !r_zero``
   short-circuits (point doubling on equal points; infinity on
   inverse points). Replaced by the observation that the
   Montgomery ladder invariant ``R1 - R0 = P`` (with ``P ≠ O``)
   guarantees ``R1 ≠ R0`` so ``H = 0`` only happens for ``R1 = -R0``,
   and that case naturally produces ``Z3 = 0`` via the general
   formulas.
3. **point_add_ct's** ``if p_inf / q_inf`` selects — replaced by a
   ``ct_select_point`` cascade.

For the **non-CT** path (``double_scalar_mul`` used by ECDSA
verify on **public** values), the original ``point_add`` is kept
unchanged; it has 6 branches (P=Q, P=-Q, p_inf, q_inf, fall-throughs)
which is acceptable since verify operates on attacker-known
inputs.

The ``ecc::field::field_add`` / ``field_sub`` / ``reduce_wide``
mask selects are wrapped in ``core::hint::black_box`` to keep LLVM
from recovering branches over the secret-derived ``need_sub`` flag.

Verification artefact (release-asm branch counts on x86_64 with
all 4 curve widths inlined):

.. list-table::
   :header-rows: 1

   * - Function
     - Pre 76191c1
     - Post 76191c1
   * - ``scalar_mul_point``
     - 1 (loop)
     - 1 (loop)
   * - ``point_double``
     - 8
     - **0**
   * - ``point_add_ct``
     - n/a (non-existent)
     - **0** (inlined)
   * - ``point_add`` (verify)
     - 12
     - 6 (public values)
   * - ``double_scalar_mul``
     - 2
     - 2 (public values)

Minerva / LadderLeak — bit-length nonce leakage (``T1-B``)
==========================================================

Principle of the attack
-----------------------

Minerva (:cite:`jancar2020_minerva`) exploits a timing leak that
reveals the **bit-length** of the ECDSA nonce ``k`` (e.g. through
a variable-iteration modular inverse, or through ``bits2int``
truncating leading zero bits). LadderLeak
(:cite:`aranha2020_ladderleak`) shows that **less than one bit** of
nonce-bias per signature is enough for full key recovery via a
lattice attack on the Hidden Number Problem.

Live in 2024:

* **CVE-2024-23342** — python-ecdsa Minerva-class via the modular
  inverse implementation.
* **CVE-2024-13176** — OpenSSL P-521: ~300 ns leak when the top
  word of ``k^{-1} mod n`` happens to be zero (P-521 nonce is 521
  bits → 9-limb storage, top 55 bits zero by construction; the
  inverse can also have a zero high word with non-trivial
  probability).

Audit checklist for arcana
--------------------------

The CT scalar multiplication is the obvious audit point but
**not the only one**. The Minerva / LadderLeak class also bites:

1. ``ecc::ecdsa::rfc6979_k`` — the deterministic nonce derivation.
   ``bits2int`` must extract the correct bit window without an
   early exit on leading zeros. Sub-byte right-shift for P-521 is
   already wired (``shr_limbs``); audit confirms it is fixed-cost.
2. ``ecc::ecdsa::sample_random_scalar`` — rejection sampling on
   ``k`` to ensure ``1 ≤ k < n``. The rejection loop iteration
   count is publicly leakable (it is statistical, independent of
   the secret key) — but the *interior* of each iteration must not
   leak bits of the candidate. Currently uses
   ``fill_bytes_masked`` + ``scalar_is_valid``, both branchless;
   re-confirm.
3. ``ecc::field::scalar_inv`` (= ``field_inv`` mod ``n``) — the
   modular inverse via Fermat's little theorem. Variable-time
   extended GCD has been the historical Minerva target; arcana's
   choice of Fermat (``a^(n-2) mod n``) sidesteps the GCD
   structure entirely, **but** the underlying ``field_pow`` must
   be square-always + CT-select. Currently is; re-confirm with
   ``black_box`` shielding (item ``T1-E`` overlap).
4. ``ecc::ecdsa::reduce_mod_n`` — the up-to-2 conditional
   subtractions inside the signing flow. Already CT-masked but
   benefits from the ``black_box`` already applied to
   ``ecc::field::field_add``; the ``reduce_mod_n`` function
   (in ``ecdsa.rs``) is a separate copy of the same pattern and
   must receive the same treatment.

Item ``T1-B`` is the audit + ``black_box`` patch on the four
points above. Estimated effort: 1 day audit + 1 day fix.

DPA / CPA — Z-coordinate randomization (``T2-A``)
=================================================

Principle of the countermeasure
-------------------------------

A Jacobian point ``(X, Y, Z)`` represents the same affine point as
``(λ²X, λ³Y, λZ)`` for any ``λ ≠ 0`` mod ``p``. Drawing a fresh
random ``λ`` at the start of each scalar multiplication
randomizes the per-iteration intermediate values, so DPA
correlation across multiple signatures becomes uncorrelated:

* The ``s_1, s_2, …, s_t`` traces of the per-iteration
  intermediates depend on ``λ``, which is fresh per trace.
* Hamming-weight prediction across traces no longer aligns; the
  CPA peak averages out.

Reference: :cite:`brier2002weierstrass_sca` (CHES 2002),
:cite:`coron1999dpa_ecc` (CHES 1999).

Implementation route in arcana
------------------------------

In ``ecc::curve::scalar_mul_point``, before the loop:

.. code-block:: rust

   // λ ← random non-zero in F_p, e.g. via a per-call SCA-RNG seed
   let lambda = sample_random_field_element_nonzero(rng, p);
   let lambda_sq = field_sqr(&lambda, p);
   let lambda_cu = field_mul(&lambda_sq, &lambda, p);
   let p_rerand = JacobianPoint {
       x: field_mul(&point.x, &lambda_sq, p),
       y: field_mul(&point.y, &lambda_cu, p),
       z: field_mul(&point.z, &lambda, p),
   };
   // ... ladder uses p_rerand instead of point ...

Cost: 3 field multiplications + 2 squarings before the ladder, i.e.
< 1 % overhead. Requires a ``CryptoRng`` callback at the
``scalar_mul_point`` boundary — the API change is the bigger
work item than the math.

Note: the **ECDH** path (``ecdh_internal``) and the **ECDSA**
random-nonce signing path (``sign_random_internal``) already have
an RNG plumbed through; the **RFC 6979 deterministic** signing
path (``sign_rfc6979_internal``) does not. To avoid breaking the
RFC 6979 KAT determinism, Z-rerand on that path needs an internal
SCA-RNG seeded from the per-signature data
(``sk.bytes ‖ digest ‖ "z-rerand"``), à la
:cite:`coron2024_masked_rejection_dilithium` for ML-DSA.

Scalar blinding (``T2-B``)
==========================

In addition to Z-rerand, the textbook DPA defence on ECDSA is
**scalar blinding**:

.. math::

    k' \;=\; k + r \cdot n,
    \qquad r \stackrel{\$}{\leftarrow} \{0, 1\}^{64}

so that ``k' \cdot G = k \cdot G`` (since ``n \cdot G = O``) but the
ladder iterates over the bit-pattern of ``k'``, not ``k``. The
attacker observing per-iteration leakage now sees a different
sequence each call. Reference: :cite:`coron1999dpa_ecc`.

64 random bits is the typical width quoted in CHES papers; it
implies ~64 extra iterations of the ladder per call (~25 % cost
hit on a 256-bit curve). For a level-1 evaluation threat, 32 bits
may suffice, but 64 is the safer default.

Implementation route: take ``k``, compute ``k' = k + r·n`` in the
scalar field, run the ladder on ``k'`` over ``ceil(log2(n)) + 64``
bits. ``T2-B`` lands together with ``T2-A`` since both share the
RNG plumbing of the previous section.

DFA on RFC 6979 deterministic signatures (``T1-D``)
====================================================

Principle of the attack
-----------------------

RFC 6979 derives ``k`` deterministically from ``(sk, hash(msg))``
via HMAC-DRBG. Two signatures of the same message reuse the same
``k`` — which is fine cryptographically, but **fragile under
fault**. :cite:`romailler2017eddsa_fault` demonstrates the attack
on Ed25519 (same principle applies to deterministic ECDSA): sign
the same message twice; fault one of the two signatures so it
uses a slightly different ``k`` (e.g. by glitching the HMAC
state); the two resulting signatures share enough algebraic
structure that ``k`` and ``sk`` fall out of a small linear system.
:cite:`cao2020_lattice_fault_det_sig` generalises to a lattice
attack across many faulted signatures.

Hedged signatures
-----------------

The CFRG draft :cite:`cfrg_hedged_sigs` standardises the
countermeasure: keep RFC 6979 deterministic derivation but mix in
32 bytes of fresh randomness:

.. math::

    k = \mathrm{HMAC\_DRBG}(sk \;\|\; H(msg) \;\|\; r),
    \qquad r \stackrel{\$}{\leftarrow} \{0, 1\}^{256}

Properties:

* If ``r`` is fresh entropy, hedged is as strong as fully
  randomized signing against fault.
* If ``r`` is zero, the scheme degrades to standard RFC 6979 —
  preserving determinism for ACVP / KAT purposes when needed.
* If ``r`` is bad (predictable), the scheme is no worse than
  RFC 6979 — there is no nonce-reuse oracle.

Implementation route in arcana
------------------------------

* New ``Curve::sign_hedged<H>(sk, digest, rng)`` API alongside the
  existing ``sign_rfc6979`` and ``sign_random``.
* The internal nonce derivation feeds ``r`` into ``rfc6979_k`` as
  an extra HMAC-DRBG personalization byte string.
* Tests: KAT regression for ``sign_rfc6979`` (still deterministic
  with ``r = 0^{32}``); randomized round-trip for ``sign_hedged``;
  fault-injection unit test that asserts two ``sign_hedged`` of
  the same message produce different ``r``-component signatures.

Out-of-scope: the EdDSA side has its own chapter
(:doc:`eddsa`); the hedged-signing implementation will share the
``rng`` plumbing with this ECDSA path.

Invalid-curve and small-subgroup defences (implemented)
=======================================================

ECDH is the canonical target of invalid-curve attacks: an attacker
sends a peer pubkey on a *different* curve whose order has small
prime factors; the shared secret leaks ``sk mod p_i`` for each small
``p_i``. ``ecc::ecdsa::parse_and_validate_pubkey`` enforces the
on-curve check ``y^2 = x^3 + ax + b mod p`` on every externally-
provided pk; the same entry point is used by ECDSA verify, ECDH
derive, and SEC1 compress / decompress, so the validation cannot
drift between code paths.

The output of ``ecdh_internal`` is rejected if it lands on the
point at infinity (small-subgroup defence-in-depth on cofactor-1
curves).

These two defences are **already in place**, validated by the
Wycheproof corpus (``arcana/tests/wycheproof.rs`` exercises the
full set of off-curve and infinity-encoding negative vectors).

Reading list
============

Beyond the cited items above:

* :cite:`bauer2014ecdsa` — synthesis of SCA on ECC in smartcards.
* :cite:`goudarzi2020_double_add_ladders` — modern formulas for
  Joye double-add ladder (alternative to Montgomery, no special
  case at bit 0; performance-comparable).
* :cite:`pessl2017drama` — DRAM-based cross-CPU attacks on ECDSA
  in mbedTLS (relevant for shared hosts; outside the embedded
  evaluation scope).
* :cite:`moghimi2020tpm_fail` — TPM-Fail: ECDSA + RSA timing on
  certified TPMs.
* :cite:`brumley2003remote_timing` — historical baseline for
  remote timing.

Code path summary
=================

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

   * - Path
     - Today (2026-04-21)
     - Target (post T1-B + T1-D + T2-A + T2-B)
   * - ``ecc::curve::scalar_mul_point``
     - CT Montgomery ladder (76191c1)
     - + Z-coordinate randomization, scalar blinding
   * - ``ecc::ecdsa::rfc6979_k`` /
       ``sample_random_scalar``
     - CT structure, ``black_box`` audit pending
     - Audited, ``black_box`` shielding throughout
   * - ``ecc::field::scalar_inv``
     - Fermat ladder via ``field_pow`` (CT)
     - Audited; same ``black_box`` shielding
   * - ``Curve::sign_hedged`` (new)
     - n/a
     - RFC 6979 + 32-byte additional randomness
   * - ``ecdh_internal`` / ``parse_and_validate_pubkey``
     - On-curve check, infinity reject
     - Unchanged