###################################################################
EdDSA / Ed25519 — countermeasures
###################################################################

:Spec:        RFC 8032 :cite:`rfc8032`
:Crate path:  ``arcana::ecc::eddsa``
:Cargo feature: none — Ed25519 is unconditionally compiled. Ed448
                is **planned but not yet implemented** (RFC 8032
                Appendix A port pending).

EdDSA is **structurally** more SCA-friendly than ECDSA — the nonce
is HMAC-derived from the secret, the scalar is well-formed by
construction (no rejection sampling), and the scalar
multiplication is on a Twisted-Edwards curve where the unified
addition formulas avoid the special cases of Weierstrass
addition. In return, EdDSA's deterministic nature
(:cite:`rfc8032`) makes it the textbook target of single-fault
key-recovery attacks (:cite:`romailler2017eddsa_fault`).

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

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

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

   * - Threat
     - Status
     - Countermeasure(s)
   * - SPA on Ed25519 scalar mul
     - **partial — audit pending**
     - The Ed25519 scalar multiplication path in
       ``ecc::eddsa::ed25519_sign`` calls into
       ``ecc::eddsa::scalar_mul_*`` which is **separate** from the
       Weierstrass ``scalar_mul_point``; needs its own audit.
       Item ``T1-F``.
   * - DPA on scalar mul
     - **vulnerable**
     - Plan ``T2-A`` is shared with the Weierstrass side
       (Z-rerand on the projective coordinates).
   * - Single-fault on deterministic Ed25519
     - **vulnerable**
     - Plan ``T1-D``: hedged Ed25519 mode (RFC 8032 + 32 bytes
       additional randomness, mirroring
       :cite:`cfrg_hedged_sigs`).
   * - Template attacks on Ed25519
       (:cite:`samwel2018ed25519_wolfssl`)
     - **vulnerable**
     - Plan ``T2-A`` (Z-rerand) + ``T2-B`` (scalar blinding).
   * - Power analysis on intermediate hash digest
       (the SHA-512 of ``sk || M``)
     - **partial**
     - Plan ``T2-D``: SHA-512 itself is not masked; the
       carry-based DPA result of
       :cite:`belenky2023_cdpa_hmac_sha2` extends to plain
       SHA-2, so this is a real surface. Discussion in
       :doc:`hmac` (HMAC chapter, since the same SHA-512
       primitive is used).

Background — Ed25519 signing flow
=================================

Ed25519 derives the per-signature nonce ``r`` deterministically:

.. math::

    H(\mathrm{seed}) &= h \;\|\; \mathrm{prefix} \\
    r &= H(\mathrm{prefix} \;\|\; M) \bmod \ell \\
    R &= r \cdot B \\
    k &= H(R \;\|\; A \;\|\; M) \bmod \ell \\
    s &= r + k \cdot a \bmod \ell

where ``a`` is the secret scalar derived from the seed (= the
truncated, clamped form of the upper half of ``H(seed)``), ``A =
a · B`` is the public key, and ``B`` is the Edwards generator.

The single-fault attack (Romailler-Pelissier
:cite:`romailler2017eddsa_fault`):

* Sign ``M`` once normally → ``(R, s)``.
* Inject a fault during the second signing of ``M`` so ``r``
  changes: e.g. glitch one byte of the SHA-512 state →
  ``r' ≠ r``.
* The fault produces ``(R', s')`` with ``r ≠ r'`` but the **same
  challenge** ``k`` (since ``k = H(R || A || M)`` and ``R``
  changed too — but this is what the attacker observes).

Actually the standard formulation: glitch *one* of the two
signatures so it's effectively non-deterministic. From two
non-equal ``r`` for the same message, the attacker recovers
``a = (s - s') / (k - k') mod ℓ`` (modulo factor adjustments).
**One fault → key recovery.**

Single-fault → key recovery (``T1-D``)
======================================

The countermeasure is the same as the ECDSA side: hedged signing.
The CFRG draft :cite:`cfrg_hedged_sigs` already specifies the
EdDSA variant.

Implementation hooks:

* New ``ed25519_sign_hedged(sk, msg, rng) -> Signature`` API.
* Internally:

  .. math::

      r = H(\mathrm{prefix} \;\|\; \rho \;\|\; M) \bmod \ell

  where ``ρ`` is 32 bytes of fresh randomness; everything else
  unchanged.
* Pure-Ed25519 deterministic stays available for KAT compatibility
  (RFC 8032 §7.1 vectors must keep verifying bit-for-bit).
* Tests: KAT regression for the deterministic path; randomized
  round-trip for the hedged path; fault unit test asserting two
  ``ed25519_sign_hedged`` calls on the same message yield
  different ``R``-components.

This item is the same as the ECDSA-side ``T1-D``; the two share
the ``rng`` plumbing and the API design.

SPA / DPA on the Edwards scalar multiplication (``T1-F``, ``T2-A``)
====================================================================

Audit gap
---------

The Ed25519 scalar multiplication code in
``arcana::ecc::eddsa::scalar_mul_*`` was written before the
Weierstrass-side hardening (commit 76191c1) and has not been
re-audited under the same lens. Specific items to check:

1. **Branch-free ladder**: confirm the loop body uses ``ct_swap``
   between two accumulator points, not a window method that
   conditionally selects from a precomputed table.
2. **No early exit on Z = 0**: the Edwards twisted formula
   :math:`(X : Y : Z : T)` (extended coordinates) does not have
   the "point at infinity" issue of Weierstrass — the neutral
   element ``(0, 1, 1, 0)`` is just a normal point. So this
   particular issue does not arise; confirm anyway.
3. **Constant-time clamping**: the secret scalar is clamped per
   RFC 7748 (clear bits 0/1/2/255, set bit 254). The clamping
   itself uses bitwise ops, no branches; confirm.
4. **``black_box`` shielding** on the Curve25519 field
   ``reduce_p`` — same pattern as the Weierstrass side.

Item ``T1-F``: full audit pass mirroring what was done for
Weierstrass in 76191c1. Estimated effort: 2 days.

Z-coordinate randomization
--------------------------

Edwards curves admit the same Z-rerandomization technique as
Weierstrass:

.. math::

    (X, Y, Z, T) \;\sim\; (\lambda X, \lambda Y, \lambda Z, \lambda T),
    \qquad \lambda \stackrel{\$}{\leftarrow} \mathbb{F}_p^*

Implementation route is identical to ``ecdsa_ecdh.rst`` ``T2-A``:
draw ``λ`` from an internal SCA-RNG before the ladder, scale all
four extended coords. Cost: 4 field multiplications; ~< 1 %
overhead.

Scalar blinding works the same way: ``a' = a + r · ℓ`` for
``ℓ = 2^252 + 27742317777372353535851937790883648493``, the order
of the prime-order subgroup.

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

* :cite:`romailler2017eddsa_fault` — the canonical Ed25519 fault
  attack (FDTC 2017).
* :cite:`cao2020_lattice_fault_det_sig` — generalized lattice-
  based fault attacks across many faulted Ed25519 signatures.
* :cite:`samwel2018ed25519_wolfssl` — first practical SCA breaking
  Ed25519 in WolfSSL via SCA on the SHA-512 step.
* :cite:`cfrg_hedged_sigs` — IETF CFRG draft for hedged
  ECDSA / EdDSA.

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

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

   * - Path
     - Today (2026-04-21)
     - Target (post T1-D + T1-F + T2-A)
   * - ``ed25519_sign``
     - Pure RFC 8032 deterministic
     - Unchanged (kept for KAT determinism)
   * - ``ed25519_sign_hedged`` (new)
     - n/a
     - RFC 8032 + 32-byte fresh randomness
   * - Edwards ``scalar_mul``
     - Audit pending
     - Audited CT + Z-rerand + scalar blinding
   * - SHA-512 used inside Ed25519
     - Audit pending
     - Same as :doc:`hmac` (CDPA mitigation if T2-D applies)

Ed448
=====

Ed448 is **deferred** in arcana (RFC 8032 Appendix A reference
Python port pending). When it lands, the same threat-model
chapter applies (mutatis mutandis on Curve448 / Goldilocks):
hedged mode, Z-rerandomization, scalar blinding. The
implementation route is otherwise identical, since Curve448 also
admits extended Twisted-Edwards coordinates.