GHSA-hcp2-x6j4-29j7

fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) { // ... let mut r1 = r_plus - r0; r1.0 /= TwoGamma2::U32; // Variable-time division on secret-derived data (r1, r0) }

diff --git a/ml-dsa/src/algebra.rs b/ml-dsa/src/algebra.rs index 559b68a..bb126ce 100644 --- a/ml-dsa/src/algebra.rs +++ b/ml-dsa/src/algebra.rs @@ -54,8 +54,50 @@ pub(crate) trait Decompose { fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem); } +/// Constant-time division by a compile-time constant divisor. +/// +/// This trait provides a constant-time alternative to the hardware division +/// instruction, which has variable timing based on operand values. +/// Uses Barrett reduction to compute `x / M` where M is a compile-time constant. +pub(crate) trait ConstantTimeDiv: Unsigned { + /// Bit shift for Barrett reduction, chosen to provide sufficient precision + const CT_DIV_SHIFT: usize; + /// Precomputed multiplier: ceil(2^SHIFT / M) + const CT_DIV_MULTIPLIER: u64; + + /// Perform constant-time division of x by Self::U32 + /// Requires: x < Q (the field modulus, ~2^23) + #[inline(always)] + fn ct_div(x: u32) -> u32 { + // Barrett reduction: q = (x * MULTIPLIER) >> SHIFT + // This gives us floor(x / M) for x < 2^SHIFT / MULTIPLIER * M + let x64 = u64::from(x); + let quotient = (x64 * Self::CT_DIV_MULTIPLIER) >> Self::CT_DIV_SHIFT; + quotient as u32 + } +} + +impl<M> ConstantTimeDiv for M +where + M: Unsigned, +{ + // Use a shift that provides enough precision for the ML-DSA field (Q ~ 2^23) + // We need SHIFT > log2(Q) + log2(M) to ensure accuracy + // With Q < 2^24 and M < 2^20, SHIFT = 48 is sufficient + const CT_DIV_SHIFT: usize = 48; + + // Precompute the multiplier at compile time + // We add (M-1) before dividing to get ceiling division, ensuring we never underestimate + #[allow(clippy::integer_division_remainder_used)] + const CT_DIV_MULTIPLIER: u64 = ((1u64 << Self::CT_DIV_SHIFT) + M::U64 - 1) / M::U64; +} + impl Decompose for Elem { // Algorithm 36 Decompose + // + // This implementation uses constant-time division to avoid timing side-channels. + // The original algorithm used hardware division which has variable timing based + // on operand values, potentially leaking secret information during signing. fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) { let r_plus = self.clone(); let r0 = r_plus.mod_plus_minus::<TwoGamma2>(); @@ -63,8 +105,9 @@ impl Decompose for Elem { if r_plus - r0 == Elem::new(BaseField::Q - 1) { (Elem::new(0), r0 - Elem::new(1)) } else { - let mut r1 = r_plus - r0; - r1.0 /= TwoGamma2::U32; + let diff = r_plus - r0; + // Use constant-time division instead of hardware division + let r1 = Elem::new(TwoGamma2::ct_div(diff.0)); (r1, r0) } }