quantica/slh_dsa/

fors.rs

//! FORS: Forest of Random Subsets (FIPS 205, Algorithms 14-17).
//!
//! FORS is a few-time signature scheme that signs the message digest by selecting one
//! leaf from each of `k` independent binary trees of height `a`. Each tree has `2^a`
//! leaves; the message digest is split into `k` indices of `a` bits each, and the
//! signature reveals the secret leaf value plus an authentication path for each tree.
//!
//! In the SLH-DSA hierarchy, FORS sits between the message hash and the hypertree:
//! the FORS public key (a compression of the `k` tree roots) becomes the message
//! that the hypertree signs. This two-level structure is what makes SLH-DSA stateless
//! -- FORS absorbs the message entropy, and the hypertree provides many-time security.

use super::SlhDsaError;
use super::address::{Adrs, FORS_PRF, FORS_ROOTS, FORS_TREE};
use super::hash;
use super::params::Params;
use crate::secret::SecretBytes;
use alloc::vec::Vec;

/// Generate a single FORS secret key value at leaf index `idx`.
///
/// Implements Algorithm 14 of FIPS 205. Derives the secret value deterministically
/// from `SK.seed` using the PRF, domain-separated by a FORS_PRF address.
fn fors_sk_gen<P: Params>(sk_seed: &[u8], pk_seed: &[u8], adrs: &mut Adrs, idx: u32) -> Vec<u8> {
    let mut sk_adrs = adrs.clone();
    sk_adrs.set_type_and_clear(FORS_PRF);
    sk_adrs.set_key_pair_address(adrs.get_key_pair_address());
    sk_adrs.set_tree_index(idx);
    hash::prf::<P>(pk_seed, sk_seed, &sk_adrs)
}

/// Compute the root of a FORS subtree of height `z` at leaf index `i`.
///
/// Implements Algorithm 15 of FIPS 205 using an iterative **treehash**
/// (BDS-style) stack traversal: leaves are produced in order, and any
/// time the two nodes on top of the stack have the same height they
/// are combined with `H` and pushed back as a single higher-up node.
/// Peak live memory is `O(z)` nodes (at most `z + 1` stack entries),
/// instead of the `2^z` materialized leaves of the naïve approach.
///
/// For `z = 0` this degenerates to a single `F` evaluation of the
/// secret leaf value. Used during signing to compute authentication
/// path nodes (sibling subtree roots).
///
/// # Side-channel / memory posture
///
/// The iterative treehash is also the SPA-hardening posture for FORS.
/// A recursive implementation would expose a memory-access envelope
/// that matches the tree geometry, indirectly leaking the FORS digit
/// encoded into `i`. The iterative variant instead keeps a BDS stack
/// of `z + 1` nodes and walks the tree with a loop counter that is
/// independent of the secret. See
/// `doc/sca/countermeasures/slh_dsa.rst`, section *Memory / stack-
/// timing — iterative treehash + streaming signature*, for the full
/// threat analysis.
///
/// RAM impact (SLH-DSA-SHAKE-256s, `z = a - 1 = 13`, `n = 32`):
///
/// * naïve: `2^13 * 32 = 256 KiB` leaf buffer, peaking higher with
///   the transient `new_nodes` vector during the climb;
/// * treehash: `14 * 32 ≈ 448 B` on the stack of node bytes.
pub fn fors_node<P: Params>(sk_seed: &[u8], pk_seed: &[u8], i: u32, z: u32, adrs: &mut Adrs) -> Vec<u8> {
    if z == 0 {
        // Leaf: hash the secret key value
        let sk = fors_sk_gen::<P>(sk_seed, pk_seed, adrs, i);
        let kp = adrs.get_key_pair_address();
        adrs.set_type_and_clear(FORS_TREE);
        adrs.set_key_pair_address(kp);
        adrs.set_tree_height(0);
        adrs.set_tree_index(i);
        return hash::f_hash::<P>(pk_seed, adrs, &sk);
    }

    // Iterative treehash: stream the `2^z` leaves, merge equal-height
    // tops into the parent node immediately. Peak depth ≤ z + 1.
    let num_leaves = 1u32 << z;
    let base = i;
    let kp = adrs.get_key_pair_address();

    // (node_bytes, height) — nodes at the "left edge" of what still
    // needs to be merged. Height 0 = leaf.
    let mut stack: Vec<(Vec<u8>, u32)> = Vec::with_capacity((z + 1) as usize);

    for j in 0..num_leaves {
        let leaf_idx = base + j;

        // Produce leaf node.
        let sk = fors_sk_gen::<P>(sk_seed, pk_seed, adrs, leaf_idx);
        adrs.set_type_and_clear(FORS_TREE);
        adrs.set_key_pair_address(kp);
        adrs.set_tree_height(0);
        adrs.set_tree_index(leaf_idx);
        let mut node = hash::f_hash::<P>(pk_seed, adrs, &sk);
        let mut height = 0u32;
        let mut tree_idx = leaf_idx;

        // Merge while the top of stack is at the same height as `node`.
        // Each merge pops the left sibling and produces the parent.
        while let Some(&(_, top_h)) = stack.last() {
            if top_h != height {
                break;
            }
            let (left, _) = stack.pop().expect("stack non-empty in merge loop");
            tree_idx >>= 1;
            height += 1;
            adrs.set_type_and_clear(FORS_TREE);
            adrs.set_key_pair_address(kp);
            adrs.set_tree_height(height);
            adrs.set_tree_index(tree_idx);
            node = hash::hash_h::<P>(pk_seed, adrs, &left, &node);
        }
        stack.push((node, height));
    }

    // With `2^z` leaves processed, the stack holds exactly one entry
    // at height `z`: the subtree root.
    stack.pop().expect("treehash produces exactly one root").0
}

/// Sign a message digest using FORS.
///
/// Implements Algorithm 16 of FIPS 205. The message digest `md` contains `k * a` bits,
/// which are split into `k` indices of `a` bits each. For each of the `k` FORS trees,
/// the signature includes:
/// - The secret leaf value at the selected index (n bytes)
/// - An authentication path of `a` sibling nodes (a * n bytes)
///
/// The total FORS signature is `k * (1 + a) * n` bytes.
///
/// `adrs_template` is read-only — a local clone is taken internally for the
/// scratch state mutated during signing. Returns
/// `Err(SlhDsaError::FaultDetected)` only when `sca-fors-indices-check`
/// (T1-E) is enabled and the integrity check on the FORS index vector
/// fails; otherwise always `Ok`.
pub fn fors_sign<P: Params>(
    md: &[u8],
    sk_seed: &[u8],
    pk_seed: &[u8],
    adrs_template: &Adrs,
) -> Result<Vec<u8>, SlhDsaError> {
    let mut sig_fors = alloc::vec![0u8; P::K * (1 + P::A) * P::N];
    fors_sign_into::<P>(md, sk_seed, pk_seed, adrs_template, &mut sig_fors)?;
    Ok(sig_fors)
}

/// Streaming variant of [`fors_sign`] — writes the `K * (1 + A) * N`
/// byte FORS signature directly into the start of `out` (which must
/// be at least that size).
///
/// Each per-tree block is written as `sk (N) || auth path (A * N)`
/// directly into its slot inside `out`, avoiding the transient
/// per-call `Vec<u8>` heap buffer.
///
/// `adrs_template` is read-only — a local clone is taken internally so the
/// caller's address state is not mutated. The save/restore of
/// `key_pair_address` inside the per-tree loop already guarantees that the
/// function does not depend on its own residual mutation across iterations,
/// so the local clone is semantically equivalent to the previous in-place
/// mutation pattern.
///
/// # Feature: `sca-fors-dummy-siblings` (T1-D)
///
/// When enabled, the inner per-FORS-tree loop is replaced by a single
/// **full-tree BDS streaming traversal**: for each FORS tree `i`, all
/// `2^A` leaves at positions `[base, base + 2^A)` are produced in
/// fixed order (`base = i * 2^A`), regardless of the secret index
/// `idx`. The leaf secret and the `A` auth-path sibling nodes are
/// extracted **branchlessly** during the climb, via `silentops::ct_copy`
/// guarded by `silentops::ct_eq_u32`. The address sequence absorbed by
/// Keccak (`set_tree_index(base + 0..base + 2^A - 1)` and the matching
/// internal-merge addresses) is then a deterministic function of `i`
/// only — the per-bit template oracle of Kannwischer COSADE 2018
/// (ePrint 2018/673) collapses, since no
/// `idx`-dependent address ever reaches the PRF. Cost: roughly 2×
/// the FORS hash count vs the FIPS-205 default path (one full
/// tree vs the auth-path subtrees that sum to ~`2^A - 1` leaves).
/// Output bytes are byte-identical to the default path on every
/// input.
///
/// # Historical correction
///
/// The earlier SCA-annex draft described T1-D as "compute both
/// possible siblings (s=0 and s=1) at fixed positions and select
/// branchlessly". That framing is wrong: FIPS-205 Algorithm 16 has
/// `s = floor(idx / 2^j) XOR 1` (multi-bit, taking values in
/// `[0, 2^(A-j))` at level `j`), so the sibling sits at one of
/// `2^(A-j)` `idx`-dependent positions, not at a fixed pair. The
/// only mechanism that produces an `idx`-independent address
/// sequence at the same asymptotic cost is the full-tree streaming
/// traversal implemented here.
pub fn fors_sign_into<P: Params>(
    md: &[u8],
    sk_seed: &[u8],
    pk_seed: &[u8],
    adrs_template: &Adrs,
    out: &mut [u8],
) -> Result<(), SlhDsaError> {
    let entry_size = (1 + P::A) * P::N;
    debug_assert!(out.len() >= P::K * entry_size);

    let indices = message_to_indices::<P>(md);
    let mut adrs = adrs_template.clone();
    let kp = adrs.get_key_pair_address();

    for i in 0..P::K {
        let idx = indices[i];
        let slot = &mut out[i * entry_size..(i + 1) * entry_size];
        let (leaf_slot, auth_slot) = slot.split_at_mut(P::N);
        let base = (i as u32) * (1u32 << P::A);

        #[cfg(feature = "sca-fors-dummy-siblings")]
        {
            // T1-D — full-tree BDS streaming. Absorbed Keccak address
            // sequence is `set_tree_index(base + k)` for `k ∈ [0, 2^A)`,
            // plus the matching internal-merge addresses, all
            // idx-independent. Leaf secret and auth-path siblings are
            // extracted branchlessly via `ct_copy` + `ct_eq_u32`.
            let mut stack: Vec<(Vec<u8>, u32)> = Vec::with_capacity(P::A + 1);
            let num_leaves = 1u32 << P::A;

            for k in 0..num_leaves {
                let leaf_idx = base + k;

                // Leaf secret value (absorbs FORS_PRF address with tree_index = leaf_idx).
                let sk = fors_sk_gen::<P>(sk_seed, pk_seed, &mut adrs, leaf_idx);
                // Branchlessly save sk to leaf_slot if k == idx.
                silentops::ct_copy(leaf_slot, &sk, silentops::ct_eq_u32(k, idx));

                // f_hash of the leaf at height 0 (absorbs FORS_TREE address).
                adrs.set_type_and_clear(FORS_TREE);
                adrs.set_key_pair_address(kp);
                adrs.set_tree_height(0);
                adrs.set_tree_index(leaf_idx);
                let mut node = hash::f_hash::<P>(pk_seed, &mut adrs, &sk);
                let mut height: u32 = 0;
                let mut local_pos: u32 = k;

                // Save height-0 node to auth_slot[0..N] if it is the
                // sibling-at-level-0 of idx (i.e. local_pos == idx XOR 1).
                silentops::ct_copy(&mut auth_slot[0..P::N], &node, silentops::ct_eq_u32(local_pos, idx ^ 1));

                // BDS merge — combine same-height tops.
                while let Some(&(_, top_h)) = stack.last() {
                    if top_h != height {
                        break;
                    }
                    let (left, _) = stack.pop().expect("non-empty");
                    local_pos >>= 1;
                    height += 1;

                    // Absolute tree_index for the merged node at height h
                    // is `(base + leftmost_leaf_offset) >> h`
                    // = i * 2^(A - h) + local_pos.
                    let absolute_pos = (i as u32) * (1u32 << (P::A - height as usize)) + local_pos;
                    adrs.set_type_and_clear(FORS_TREE);
                    adrs.set_key_pair_address(kp);
                    adrs.set_tree_height(height);
                    adrs.set_tree_index(absolute_pos);
                    node = hash::hash_h::<P>(pk_seed, &mut adrs, &left, &node);

                    // Save to auth_slot[h] if this merged node is the
                    // sibling-at-level-h of idx. The final merge produces
                    // the FORS root at height A — skipped (h == A => no
                    // auth-path slot).
                    if (height as usize) < P::A {
                        let sibling_pos = (idx >> height) ^ 1;
                        let slot_off = (height as usize) * P::N;
                        silentops::ct_copy(
                            &mut auth_slot[slot_off..slot_off + P::N],
                            &node,
                            silentops::ct_eq_u32(local_pos, sibling_pos),
                        );
                    }
                }
                stack.push((node, height));
            }
            // The stack now holds exactly one element — the FORS root at
            // height A. The caller will re-derive the root from the
            // produced signature via `fors_pk_from_sig`, so we drop it.
            drop(stack);
        }

        #[cfg(not(feature = "sca-fors-dummy-siblings"))]
        {
            // FIPS-205 Algorithm 16 — single sibling per level.
            // Leak surface: `set_tree_index((base + ((idx >> j) XOR 1) * 2^j) + k)` for
            // each level j and each leaf k of the sibling subtree, idx-dependent.
            let sk = fors_sk_gen::<P>(sk_seed, pk_seed, &mut adrs, base + idx);
            leaf_slot.copy_from_slice(&sk);

            for j in 0..P::A {
                let s = (idx >> j) ^ 1;
                let node = fors_node::<P>(sk_seed, pk_seed, base + s * (1 << j), j as u32, &mut adrs);
                adrs.set_type_and_clear(FORS_TREE);
                adrs.set_key_pair_address(kp);
                auth_slot[j * P::N..(j + 1) * P::N].copy_from_slice(&node);
            }
        }
    }

    // T1-E — recompute the FORS-index vector from `md` and CT-compare to
    // the one we just consumed. Catches a fault that flips a bit during
    // the original `message_to_indices` call (or anywhere upstream in
    // the digest extraction). Cost: one extra `base_2b` (~K * A / 8
    // bytes of bit-extraction, no hashing).
    #[cfg(feature = "sca-fors-indices-check")]
    fors_indices_consistency_check::<P>(md, &indices)?;

    Ok(())
}

/// T1-E — verify the FORS-index vector used during signing matches the
/// one derivable from the digest. Re-derives `message_to_indices(md)`
/// and compares to `used` under `silentops::ct_eq` on the little-endian
/// serialisation. Returns `Err(SlhDsaError::FaultDetected)` on any
/// mismatch (same error envelope as T1-C's recompute-and-compare).
///
/// `pub(crate)` so the `#[cfg(test)]` module can drive it with
/// synthetic divergent buffers without needing real fault injection.
#[cfg(feature = "sca-fors-indices-check")]
pub(crate) fn fors_indices_consistency_check<P: Params>(md: &[u8], used: &[u32]) -> Result<(), SlhDsaError> {
    let recomputed = message_to_indices::<P>(md);
    if recomputed.len() != used.len() {
        return Err(SlhDsaError::FaultDetected);
    }
    let used_bytes: Vec<u8> = used.iter().flat_map(|x| x.to_le_bytes()).collect();
    let recomputed_bytes: Vec<u8> = recomputed.iter().flat_map(|x| x.to_le_bytes()).collect();
    if silentops::ct_eq(&used_bytes, &recomputed_bytes) != 1 {
        return Err(SlhDsaError::FaultDetected);
    }
    Ok(())
}

/// Compute a FORS public key from a FORS signature — constant-time.
///
/// Implements Algorithm 17 of FIPS 205. For each of the `k` FORS trees,
/// hashes the revealed secret leaf, then walks up the authentication path
/// to recover the tree root. The `k` roots are compressed into a single
/// `n`-byte public key via `T_k`. If the signature is valid, the returned
/// public key matches the one produced by the signer.
///
/// # Side-channel posture
///
/// The secret-dependent argument ordering of `hash_h` along each
/// authentication-path level is resolved by a branchless byte-wise
/// `silentops::ct_select_u8` cswap rather than a Rust `if`. Address bytes
/// and the `tree_index` written into `adrs` are identical in both original
/// branches, so they need no extra masking. The per-iteration scratch is
/// drop-zeroized via `silentops::ct_zeroize` before return.
///
/// In the *verifier* path the FORS-tree digit `idx` is reconstructed from
/// the publicly transmitted message digest, so a timing leak on the digit
/// would be harmless. But the same routine is reused inside the *signer*
/// post-signing redundancy check (item ``T1-C`` of the SLH-DSA roadmap —
/// see [`fors_sign_into_redundant`]). At that point of the signing flow,
/// `idx` is derived from values (the freshly sampled randomizer `R`, the
/// secret `SK.prf`) that have **not yet** been published, so a control-flow
/// leak on the digit would become a secret-key leak. A single CT
/// implementation across both paths removes the foot-gun of a future call
/// site picking a variable-time variant by autocomplete.
///
/// # References
///
/// * Castelnovi-Martinelli-Prest, *Grafting Trees: a Fault Attack against
///   the SPHINCS framework*, ePrint 2018/102 — motivates T1-C, which in
///   turn motivates this CT routine.
/// * Adiletta et al., *SLasH-DSA: Breaking SLH-DSA Using an Extensible
///   End-to-End Rowhammer Framework*, arXiv 2509.13048 (Aug 2025) —
///   software realisation of the same attack class.
/// * Genêt, *On Protecting SPHINCS+ Against Fault Attacks*, TCHES 2023(3)
///   (ePrint 2023/042) — recommends the recompute-and-compare redundancy
///   that consumes this routine.
pub fn fors_pk_from_sig<P: Params>(sig_fors: &[u8], md: &[u8], pk_seed: &[u8], adrs_template: &Adrs) -> Vec<u8> {
    let indices = message_to_indices::<P>(md);
    let mut adrs = adrs_template.clone();
    let kp = adrs.get_key_pair_address();

    let entry_size = (1 + P::A) * P::N;
    let mut roots = Vec::with_capacity(P::K * P::N);

    // Per-iteration scratch for the CT argument-swap.
    let mut left = alloc::vec![0u8; P::N];
    let mut right = alloc::vec![0u8; P::N];

    for i in 0..P::K {
        let idx = indices[i];
        let offset = i * entry_size;
        let sk = &sig_fors[offset..offset + P::N];
        let auth = &sig_fors[offset + P::N..offset + entry_size];

        // Leaf from sk — same as the non-CT path.
        adrs.set_type_and_clear(FORS_TREE);
        adrs.set_key_pair_address(kp);
        adrs.set_tree_height(0);
        adrs.set_tree_index((i as u32) * (1u32 << P::A) + idx);
        let mut node = hash::f_hash::<P>(pk_seed, &mut adrs, sk);

        // Climb the authentication path — argument order to `hash_h` is
        // selected by a branchless `ct_select_u8` cswap.
        for j in 0..P::A {
            let auth_j = &auth[j * P::N..(j + 1) * P::N];

            // bit = 0 → `node` is the left child  → hash_h(node, auth_j)
            // bit = 1 → `node` is the right child → hash_h(auth_j, node)
            let bit = ((idx >> j) & 1) as u8;
            for k in 0..P::N {
                // ct_select_u8(a, b, cond) returns a if cond != 0 else b.
                left[k] = silentops::ct_select_u8(auth_j[k], node[k], bit);
                right[k] = silentops::ct_select_u8(node[k], auth_j[k], bit);
            }

            // tree_index is identical in both original branches.
            adrs.set_type_and_clear(FORS_TREE);
            adrs.set_key_pair_address(kp);
            adrs.set_tree_height((j + 1) as u32);
            adrs.set_tree_index(((i as u32) * (1u32 << P::A) + idx) >> (j + 1));

            node = hash::hash_h::<P>(pk_seed, &mut adrs, &left, &right);
        }

        roots.extend_from_slice(&node);
    }

    // Per-loop scratch is wiped — the cswap copies are derived from
    // publish-ready inputs once the signer commits to the signature, but
    // the contract of this CT routine is that nothing of `idx`-shape
    // leaks. Zeroizing keeps that contract strict.
    silentops::ct_zeroize(&mut left);
    silentops::ct_zeroize(&mut right);

    // Compress k roots into one public key — the roots themselves are not
    // secret-shaped at this stage.
    let mut fors_pk_adrs = adrs.clone();
    fors_pk_adrs.set_type_and_clear(FORS_ROOTS);
    fors_pk_adrs.set_key_pair_address(kp);

    hash::t_l::<P>(pk_seed, &fors_pk_adrs, &roots)
}

/// Recompute-and-compare FORS signing — T1-C redundancy against
/// single-fault grafting-tree forgery.
///
/// Signs the FORS component twice into independent scratch buffers,
/// derives the FORS public key from each signature via the
/// constant-time [`fors_pk_from_sig`], then compares **both
/// signatures and both derived public keys** under
/// `silentops::ct_eq`. On any mismatch the function returns
/// [`SlhDsaError::FaultDetected`] *without* writing anything into
/// `out` — the faulted signature never leaves the device. On a clean
/// run, the validated signature is copied into the caller's `out`
/// buffer and the FORS public key (reusable by the hypertree
/// signing step) is returned.
///
/// # Threat addressed
///
/// Castelnovi-Martinelli-Prest *Grafting Trees* (PQCrypto 2018,
/// ePrint 2018/102) showed that a single random fault during any FORS
/// hash chain produces a valid-looking signature under a different
/// FORS root; after collecting a handful of such signatures an
/// attacker forges arbitrary messages. Genêt *On Protecting SPHINCS+
/// Against Fault Attacks* (TCHES 2023(3), ePrint 2023/042) recommends
/// recompute-and-compare at signing time as the canonical defence.
/// The threat is no longer hypothetical-physical: Adiletta et al.
/// *SLasH-DSA* (arXiv 2509.13048, Aug 2025) realised it on stock
/// OpenSSL with software-only Rowhammer in 1–8 h.
///
/// # Design rationale
///
/// Comparing *both* the signature bytes and the derived public keys
/// is intentional defence-in-depth. A fault that corrupts auth-path
/// bytes might round-trip to the same FORS root under the verifier
/// path; the byte-level `ct_eq` catches that case. Symmetrically, a
/// fault that lands inside the second [`fors_pk_from_sig`]
/// derivation would not be caught by a signature-bytes-only check;
/// the pk `ct_eq` catches that case. Both checks together cost a
/// single extra `ct_eq` and are paid only on the slow path that
/// already runs the FORS signer twice.
///
/// # Abort posture (vs ML-KEM's CT-substitute)
///
/// Unlike ML-KEM's double-decaps + branchless fault-fallback
/// (`quantica::ml_kem::kem::decaps`), this routine **aborts**
/// rather than substituting a fault-derived key. The asymmetry is
/// deliberate: a KEM must always return a shared secret (or the
/// caller cannot proceed at all), while a signer that detects a
/// fault is allowed — required, per Genêt 2023 — to refuse to
/// emit, so the faulted signature does not propagate.
///
/// # Memory
///
/// One [`SecretBytes`] scratch of length `fors_sig_len = K * (1 + A)
/// * N` (≈ 10 KiB for SLH-DSA-SHAKE-256s). Heap-allocated so the
/// stack budget on the M0 baseline stays honest. The scratch is
/// drop-zeroized on both the success and the abort path.
pub fn fors_sign_into_redundant<P: Params>(
    md: &[u8],
    sk_seed: &[u8],
    pk_seed: &[u8],
    adrs_template: &Adrs,
    out: &mut [u8],
) -> Result<Vec<u8>, SlhDsaError> {
    let sig_len = P::K * (1 + P::A) * P::N;
    debug_assert!(out.len() >= sig_len);

    // Two independent signings. `SecretBytes` ensures Drop-zeroize
    // even if we return early via the `?`-less Err path below.
    let mut sig1 = SecretBytes::from_vec(alloc::vec![0u8; sig_len]);
    let mut sig2 = SecretBytes::from_vec(alloc::vec![0u8; sig_len]);

    // Both FORS routines take an immutable address template and clone
    // internally for their own scratch, so `adrs_template` is reused as-is
    // across all four calls — four independent address-state pipelines
    // remain inside the four hashings, with zero caller-side cloning.
    fors_sign_into::<P>(md, sk_seed, pk_seed, adrs_template, &mut sig1)?;
    fors_sign_into::<P>(md, sk_seed, pk_seed, adrs_template, &mut sig2)?;

    let pk1 = fors_pk_from_sig::<P>(sig1.as_bytes(), md, pk_seed, adrs_template);
    let pk2 = fors_pk_from_sig::<P>(sig2.as_bytes(), md, pk_seed, adrs_template);

    // CT-compare both surfaces. Mismatch on either aborts.
    fors_redundancy_compare(sig1.as_bytes(), sig2.as_bytes(), &pk1, &pk2)?;

    // Commit the validated signature.
    out[..sig_len].copy_from_slice(sig1.as_bytes());

    Ok(pk1)
}

/// Internal — apply the two `silentops::ct_eq` checks of the T1-C
/// redundancy and produce the verdict.
///
/// Factored out so the test suite can exercise the comparison logic
/// with synthetically divergent inputs without injecting a fault into
/// the FORS signing primitive itself.
#[inline]
fn fors_redundancy_compare(sig1: &[u8], sig2: &[u8], pk1: &[u8], pk2: &[u8]) -> Result<(), SlhDsaError> {
    // `silentops::ct_eq` returns 1 on equality, 0 otherwise.
    let sigs_equal = silentops::ct_eq(sig1, sig2) == 1;
    let pks_equal = silentops::ct_eq(pk1, pk2) == 1;
    if !sigs_equal || !pks_equal {
        return Err(SlhDsaError::FaultDetected);
    }
    Ok(())
}

/// Split a message digest `md` (`k * a` bits) into `k` unsigned integers of `a` bits each.
///
/// Uses [`base_2b`](super::wots::base_2b) to extract the indices. Each index selects
/// one leaf in its corresponding FORS tree.
fn message_to_indices<P: Params>(md: &[u8]) -> Vec<u32> {
    // Use base_2b with b=a to extract k values
    // md contains ceil(k*a / 8) bytes; we extract k values of a bits each.
    super::wots::base_2b(md, P::A, P::K)
}

#[cfg(test)]
mod tests {
    use super::super::address::{Adrs, FORS_TREE};
    use super::super::params::{Params, Shake128f, Shake128s};
    use super::*;

    /// Sign FORS with deterministic seeds, then re-derive the FORS public
    /// key from the produced signature; assert that two back-to-back
    /// derivations yield byte-identical output and that the output has the
    /// expected `N`-byte width. Smoke test for the sign / pk-from-sig
    /// round trip on every parameter set we exercise.
    fn round_trip<P: Params>(seed_byte: u8, message_byte: u8) {
        let sk_seed = alloc::vec![seed_byte; P::N];
        let pk_seed = alloc::vec![seed_byte.wrapping_add(0x80); P::N];

        // Synthesise a `digest` long enough for `message_to_indices` to
        // extract K * A bits worth of FORS indices.
        let md_bytes = (P::K * P::A + 7) / 8;
        let md: Vec<u8> = (0..md_bytes).map(|i| message_byte.wrapping_add(i as u8)).collect();

        let mut sig_fors = alloc::vec![0u8; P::K * (1 + P::A) * P::N];
        let mut adrs = Adrs::new();
        adrs.set_type_and_clear(FORS_TREE);
        adrs.set_key_pair_address(0);
        // FORS routines take an immutable template; one address suffices
        // for the whole test.
        super::fors_sign_into::<P>(&md, &sk_seed, &pk_seed, &adrs, &mut sig_fors)
            .expect("round-trip — clean signing must succeed");

        let pk_a = super::fors_pk_from_sig::<P>(&sig_fors, &md, &pk_seed, &adrs);
        let pk_b = super::fors_pk_from_sig::<P>(&sig_fors, &md, &pk_seed, &adrs);

        assert_eq!(pk_a.len(), P::N, "FORS pk must be N bytes wide");
        assert_eq!(pk_a, pk_b, "fors_pk_from_sig must be deterministic");
    }

    #[test]
    fn fors_pk_from_sig_round_trip_shake128s() {
        // Several seed/message combinations to exercise the per-tree
        // bit-by-bit cswap (idx bits vary across runs).
        round_trip::<Shake128s>(0x00, 0x00);
        round_trip::<Shake128s>(0x55, 0xAA);
        round_trip::<Shake128s>(0xFF, 0xFF);
        round_trip::<Shake128s>(0x42, 0x13);
    }

    #[test]
    fn fors_pk_from_sig_round_trip_shake128f() {
        round_trip::<Shake128f>(0x00, 0x00);
        round_trip::<Shake128f>(0x55, 0xAA);
        round_trip::<Shake128f>(0xFF, 0xFF);
    }

    // ===========================================================
    // T1-C — fors_sign_into_redundant equivalence + negative tests
    // ===========================================================

    /// Drive `fors_sign_into_redundant` on the same inputs as the
    /// classic `fors_sign_into`, and check that:
    ///   1. the validated signature is byte-equal to the non-redundant
    ///      signature (clean-run equivalence — no fault, no divergence);
    ///   2. the returned FORS pk matches the standalone `fors_pk_from_sig`
    ///      derivation from the produced signature.
    fn redundancy_equivalence<P: Params>(seed_byte: u8, message_byte: u8) {
        let sk_seed = alloc::vec![seed_byte; P::N];
        let pk_seed = alloc::vec![seed_byte.wrapping_add(0x80); P::N];

        let md_bytes = (P::K * P::A + 7) / 8;
        let md: Vec<u8> = (0..md_bytes).map(|i| message_byte.wrapping_add(i as u8)).collect();

        let sig_len = P::K * (1 + P::A) * P::N;

        // Reference: classic non-redundant path.
        let mut sig_ref = alloc::vec![0u8; sig_len];
        // FORS routines take an immutable template; one address suffices
        // for both the reference and the redundant paths plus the pk-check.
        let mut adrs = Adrs::new();
        adrs.set_type_and_clear(FORS_TREE);
        adrs.set_key_pair_address(0);

        super::fors_sign_into::<P>(&md, &sk_seed, &pk_seed, &adrs, &mut sig_ref)
            .expect("redundancy_equivalence — clean reference sign must succeed");

        // Redundant path — must succeed and produce the same bytes.
        let mut sig_red = alloc::vec![0u8; sig_len];
        let pk_red = super::fors_sign_into_redundant::<P>(&md, &sk_seed, &pk_seed, &adrs, &mut sig_red)
            .expect("clean run must succeed");

        assert_eq!(
            sig_red, sig_ref,
            "redundant signature must equal the non-redundant signature on a clean run"
        );

        // pk returned by the redundant path must equal the standalone
        // derivation from the produced signature.
        let pk_classic = super::fors_pk_from_sig::<P>(&sig_red, &md, &pk_seed, &adrs);

        assert_eq!(pk_red, pk_classic, "redundant-returned pk must match fors_pk_from_sig");
    }

    #[test]
    fn fors_sign_into_redundant_matches_reference_shake128s() {
        redundancy_equivalence::<Shake128s>(0x00, 0x00);
        redundancy_equivalence::<Shake128s>(0x55, 0xAA);
        redundancy_equivalence::<Shake128s>(0xFF, 0xFF);
    }

    #[test]
    fn fors_sign_into_redundant_matches_reference_shake128f() {
        redundancy_equivalence::<Shake128f>(0x00, 0x00);
        redundancy_equivalence::<Shake128f>(0x55, 0xAA);
    }

    /// Negative test — drive `fors_redundancy_compare` (the internal
    /// helper that produces the abort verdict) with synthetically
    /// divergent buffers and check that each kind of mismatch
    /// (signature only, pk only, both) surfaces as `FaultDetected`.
    /// We do not need to inject a real fault into the FORS signer
    /// for this — exercising the comparison logic in isolation is
    /// what catches a regression in the abort path.
    #[test]
    fn fors_redundancy_compare_detects_divergence() {
        let sig_a = alloc::vec![0x42u8; 32];
        let sig_b_eq = sig_a.clone();
        let mut sig_b_diff = sig_a.clone();
        sig_b_diff[5] ^= 0x01;

        let pk_a = alloc::vec![0xAAu8; 16];
        let pk_b_eq = pk_a.clone();
        let mut pk_b_diff = pk_a.clone();
        pk_b_diff[3] ^= 0x80;

        // 1. all four buffers agree → Ok.
        assert!(super::fors_redundancy_compare(&sig_a, &sig_b_eq, &pk_a, &pk_b_eq).is_ok());

        // 2. signature bytes diverge → FaultDetected.
        assert!(matches!(
            super::fors_redundancy_compare(&sig_a, &sig_b_diff, &pk_a, &pk_b_eq),
            Err(SlhDsaError::FaultDetected)
        ));

        // 3. pk diverges → FaultDetected.
        assert!(matches!(
            super::fors_redundancy_compare(&sig_a, &sig_b_eq, &pk_a, &pk_b_diff),
            Err(SlhDsaError::FaultDetected)
        ));

        // 4. both diverge → FaultDetected (same observable, but the
        //    short-circuit must not change the verdict).
        assert!(matches!(
            super::fors_redundancy_compare(&sig_a, &sig_b_diff, &pk_a, &pk_b_diff),
            Err(SlhDsaError::FaultDetected)
        ));
    }

    // ===========================================================
    // T1-E — fors_indices_consistency_check (positive + negative)
    // ===========================================================

    /// Positive — feed the helper the indices that `message_to_indices`
    /// produces from the same `md`, expect `Ok`. Exercised across the
    /// `Shake128s` and `Shake128f` parameter sets so the K * A bit
    /// extraction is non-trivial on both.
    #[cfg(feature = "sca-fors-indices-check")]
    fn indices_check_accepts<P: Params>(seed_byte: u8) {
        let md_bytes = (P::K * P::A + 7) / 8;
        let md: Vec<u8> = (0..md_bytes).map(|i| seed_byte.wrapping_add(i as u8)).collect();
        let indices = super::message_to_indices::<P>(&md);
        assert!(super::fors_indices_consistency_check::<P>(&md, &indices).is_ok());
    }

    #[test]
    #[cfg(feature = "sca-fors-indices-check")]
    fn fors_indices_check_accepts_correct_shake128s() {
        indices_check_accepts::<Shake128s>(0x00);
        indices_check_accepts::<Shake128s>(0x42);
        indices_check_accepts::<Shake128s>(0xFF);
    }

    #[test]
    #[cfg(feature = "sca-fors-indices-check")]
    fn fors_indices_check_accepts_correct_shake128f() {
        indices_check_accepts::<Shake128f>(0x00);
        indices_check_accepts::<Shake128f>(0x55);
    }

    /// Negative — flip one bit of one index and expect `FaultDetected`.
    /// We do not need to inject a fault into `message_to_indices`
    /// itself; passing a deliberately corrupted `used` vector
    /// exercises the same CT-compare path the integrity check runs.
    #[test]
    #[cfg(feature = "sca-fors-indices-check")]
    fn fors_indices_check_rejects_flipped_index() {
        type P = Shake128s;
        let md_bytes = (P::K * P::A + 7) / 8;
        let md: Vec<u8> = (0..md_bytes).map(|i| i as u8).collect();
        let mut indices = super::message_to_indices::<P>(&md);

        // Corrupt one index — flip its lowest bit.
        indices[0] ^= 1;

        assert!(matches!(
            super::fors_indices_consistency_check::<P>(&md, &indices),
            Err(SlhDsaError::FaultDetected)
        ));

        // Corrupt by changing length — expect FaultDetected too.
        let mut short = super::message_to_indices::<P>(&md);
        short.pop();
        assert!(matches!(
            super::fors_indices_consistency_check::<P>(&md, &short),
            Err(SlhDsaError::FaultDetected)
        ));
    }
}