quantica/ml_kem/
shuffle.rs

1//! Fisher-Yates shuffle for NTT butterfly index randomization
2//! (**countermeasure: SPA / SEMA on secret-polynomial NTT**).
3//!
4//! ## Principle
5//!
6//! Butterflies at the same NTT level are mutually independent: permuting
7//! their execution order does not change the output polynomial, only the
8//! pattern of memory accesses and instantaneous power consumption. By
9//! drawing a fresh permutation on every invocation from a CSPRNG seeded
10//! with per-signature entropy, two successive NTTs on the same input
11//! produce different power / EM traces, defeating trace-alignment-based
12//! SPA and template attacks.
13//!
14//! The permutation is drawn with rejection sampling on a 16-bit RNG
15//! output so the sampled indices are unbiased.
16//!
17//! ## References
18//!
19//! * J. Aycock et al., *Hardware NTT shuffling as a lightweight
20//!   countermeasure for ML-KEM* (arXiv, 2024) — baseline hardware
21//!   construction we re-implement in software.
22//! * M.-J. O. Saarinen, *Practical side-channel evaluation of post-
23//!   quantum primitives* (NIST, 2023) — independent evaluation of the
24//!   shuffling benefit on ML-KEM / ML-DSA.
25//!
26//! ## Where to look next
27//!
28//! * Countermeasure description and threat analysis:
29//!   `doc/sca/countermeasures/ml_kem.rst`, section
30//!   *SPA / SEMA — NTT butterfly shuffling*.
31//! * Call sites: `quantica/src/ml_kem/kem.rs`, functions
32//!   `keygen_internal_sca` and `decaps_internal_sca`.
33//! * Companion primitive reference: `doc/sca/primitives.rst`.
34
35use super::MlKemError;
36use super::rng::CryptoRng;
37
38/// Generate a uniform random permutation of `0..n` using Fisher-Yates.
39///
40/// Iterates from the last index down to 1, swapping each element with a
41/// uniformly chosen earlier (or equal) element. Uses rejection sampling
42/// on 16-bit random values to avoid modular bias.
43///
44/// # Arguments
45///
46/// * `perm` - Output slice of length `n`, initialized to `[0, 1, ..., n-1]`
47///   then shuffled in place.
48/// * `rng` - A cryptographic RNG for generating swap indices.
49///
50/// # Errors
51///
52/// Returns [`MlKemError::RngFailure`] if the RNG fails.
53pub fn generate_permutation(perm: &mut [u16], rng: &mut impl CryptoRng) -> Result<(), MlKemError> {
54    let n = perm.len();
55    for i in 0..n {
56        perm[i] = i as u16;
57    }
58    // Fisher-Yates: for i from n-1 downto 1, swap perm[i] with perm[rand(0..=i)]
59    let mut rand_buf = [0u8; 2];
60    for i in (1..n).rev() {
61        let bound = (i + 1) as u16;
62        // Rejection sampling to avoid modular bias
63        let limit = u16::MAX - (u16::MAX % bound);
64        loop {
65            rng.fill_bytes(&mut rand_buf)?;
66            let r = u16::from_le_bytes(rand_buf);
67            if r < limit {
68                let j = (r % bound) as usize;
69                perm.swap(i, j);
70                break;
71            }
72        }
73    }
74    Ok(())
75}
76
77/// Forward NTT with randomized butterfly ordering (SPA countermeasure).
78///
79/// Functionally equivalent to [`super::ntt::ntt`] but randomizes the
80/// execution order of butterfly operations at each NTT level. Both the
81/// group order (which butterfly group runs first) and the intra-group
82/// order (which pair within a group runs first) are independently
83/// shuffled using fresh [`generate_permutation`] calls.
84///
85/// A new random permutation is generated for every level and every group,
86/// so successive invocations produce different power traces even for
87/// identical inputs.
88///
89/// # Arguments
90///
91/// * `f` - A mutable reference to a 256-coefficient polynomial. Modified in place.
92/// * `rng` - A cryptographic RNG for generating shuffle permutations.
93///
94/// # Errors
95///
96/// Returns [`MlKemError::RngFailure`] if the RNG fails during permutation generation.
97pub fn ntt_shuffled(f: &mut [i16; 256], rng: &mut impl CryptoRng) -> Result<(), MlKemError> {
98    use super::ntt::Q;
99    const ZETAS: [i16; 128] = [
100        1, 1729, 2580, 3289, 2642, 630, 1897, 848, 1062, 1919, 193, 797, 2786, 3260, 569, 1746, 296, 2447, 1339, 1476,
101        3046, 56, 2240, 1333, 1426, 2094, 535, 2882, 2393, 2879, 1974, 821, 289, 331, 3253, 1756, 1197, 2304, 2277,
102        2055, 650, 1977, 2513, 632, 2865, 33, 1320, 1915, 2319, 1435, 807, 452, 1438, 2868, 1534, 2402, 2647, 2617,
103        1481, 648, 2474, 3110, 1227, 910, 17, 2761, 583, 2649, 1637, 723, 2288, 1100, 1409, 2662, 3281, 233, 756, 2156,
104        3015, 3050, 1703, 1651, 2789, 1789, 1847, 952, 1461, 2687, 939, 2308, 2437, 2388, 733, 2337, 268, 641, 1584,
105        2298, 2037, 3220, 375, 2549, 2090, 1645, 1063, 319, 2773, 757, 2099, 561, 2466, 2594, 2804, 1092, 403, 1026,
106        1143, 2150, 2775, 886, 1722, 1212, 1874, 1029, 2110, 2935, 885, 2154,
107    ];
108
109    fn mod_q(a: i32) -> i16 {
110        let mut r = a % (Q as i32);
111        r += (Q as i32) & (r >> 31);
112        r as i16
113    }
114    fn mul_mod(a: i16, b: i16) -> i16 {
115        mod_q(a as i32 * b as i32)
116    }
117
118    let mut k = 1usize;
119    let mut len = 128;
120    while len >= 2 {
121        let num_groups = 256 / (2 * len);
122        // Generate random permutation of group indices
123        let mut perm = vec![0u16; num_groups];
124        generate_permutation(&mut perm, rng)?;
125
126        for &gi in perm.iter() {
127            let start = gi as usize * 2 * len;
128            let zeta = ZETAS[k + gi as usize];
129            // Also shuffle butterfly indices within each group
130            let mut inner_perm = vec![0u16; len];
131            generate_permutation(&mut inner_perm, rng)?;
132            for &ji in inner_perm.iter() {
133                let j = start + ji as usize;
134                let t = mul_mod(zeta, f[j + len]);
135                f[j + len] = mod_q(f[j] as i32 - t as i32);
136                f[j] = mod_q(f[j] as i32 + t as i32);
137            }
138        }
139        k += num_groups;
140        len >>= 1;
141    }
142    Ok(())
143}
quantica/ml_kem/shuffle.rs

quantica/ml_kem/
shuffle.rs
