Skip to content

Commit 9f79bfb

Browse files
spartan8806claude
authored and
aszepieniec
committed
fix: out-of-bounds index in ber_exp's comparison loop
The loop iterated `(0..64).step_by(8).rev()` — eight shifts — while indexing a seven-byte buffer, so `random_bytes[7]` was read whenever the first seven bytes all tied with the corresponding bytes of `z`. Drawn from the sampler's own RNG that happens with probability about 2^-56, which is why it was never observed. Driving the loop from the array instead of an independent range makes the bound hold by construction. No input-output change. The shifts remain 56 down to 8, exactly as before. Adds a regression test that constructs the tying draw directly rather than waiting for it. Pre-fix it panics with "index out of bounds: the len is 7 but the index is 7"; post-fix the draw is rejected, which is what w == 0 means. Full lib suite 169/169, including the 20 BerExp precision vectors — those would have caught a shift that moved by one position. Also: adhere to formatting and linter rules. Co-Authored-By: Claude <[email protected]> Co-authored-by: Conner Webber <[email protected]>
1 parent 4b4cfd5 commit 9f79bfb

7 files changed

Lines changed: 102 additions & 44 deletions

File tree

‎benchmark/benches/babai_per_depth.rs‎

Lines changed: 38 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -7,21 +7,34 @@ use rand::{rng, rngs::StdRng, RngExt, SeedableRng};
77
fn random_integer(bitsize: usize, rng: &mut StdRng) -> BigInt {
88
let num_bytes = bitsize.div_ceil(8);
99
let bytes = (0..num_bytes).map(|_| rng.random::<u8>()).collect_vec();
10-
let sign = if rng.random() { Sign::Minus } else { Sign::Plus };
10+
let sign = if rng.random() {
11+
Sign::Minus
12+
} else {
13+
Sign::Plus
14+
};
1115
BigInt::from_bytes_be(sign, &bytes)
1216
}
1317

1418
fn random_i32(bitsize: usize, rng: &mut StdRng) -> i32 {
1519
let bits = bitsize.min(31);
1620
let mag: i64 = rng.random_range(0..(1i64 << bits));
17-
if rng.random() { mag as i32 } else { -(mag as i32) }
21+
if rng.random() {
22+
mag as i32
23+
} else {
24+
-(mag as i32)
25+
}
1826
}
1927

2028
/// Returns `(f_i32, g_i32, capital_f_bi, capital_g_bi)` at the given depth.
2129
fn generate_depth_inputs_bigint(
2230
depth: usize,
2331
rng: &mut StdRng,
24-
) -> (Polynomial<BigInt>, Polynomial<BigInt>, Polynomial<BigInt>, Polynomial<BigInt>) {
32+
) -> (
33+
Polynomial<BigInt>,
34+
Polynomial<BigInt>,
35+
Polynomial<BigInt>,
36+
Polynomial<BigInt>,
37+
) {
2538
let n = 1024usize >> depth;
2639
let (fg_bits_f, _, cap_bits_f, _) = NTRU_SOLVE_BABAI_COEFF_BITS[depth];
2740
let fg_bits = fg_bits_f.ceil() as usize;
@@ -45,16 +58,28 @@ fn generate_depth_inputs_rns(
4558
let cap_bits = cap_bits_f.ceil() as usize;
4659
let f = Polynomial::new((0..n).map(|_| random_i32(fg_bits, rng)).collect_vec());
4760
let g = Polynomial::new((0..n).map(|_| random_i32(fg_bits, rng)).collect_vec());
48-
let cf: Vec<i128> = (0..n).map(|_| {
49-
let bits = cap_bits.min(127);
50-
let mag: u128 = rng.random_range(0..(1u128 << bits));
51-
if rng.random() { mag as i128 } else { -(mag as i128) }
52-
}).collect();
53-
let cg: Vec<i128> = (0..n).map(|_| {
54-
let bits = cap_bits.min(127);
55-
let mag: u128 = rng.random_range(0..(1u128 << bits));
56-
if rng.random() { mag as i128 } else { -(mag as i128) }
57-
}).collect();
61+
let cf: Vec<i128> = (0..n)
62+
.map(|_| {
63+
let bits = cap_bits.min(127);
64+
let mag: u128 = rng.random_range(0..(1u128 << bits));
65+
if rng.random() {
66+
mag as i128
67+
} else {
68+
-(mag as i128)
69+
}
70+
})
71+
.collect();
72+
let cg: Vec<i128> = (0..n)
73+
.map(|_| {
74+
let bits = cap_bits.min(127);
75+
let mag: u128 = rng.random_range(0..(1u128 << bits));
76+
if rng.random() {
77+
mag as i128
78+
} else {
79+
-(mag as i128)
80+
}
81+
})
82+
.collect();
5883
(f, g, cf, cg)
5984
}
6085

‎falcon-rust/src/cyclotomic_fourier.rs‎

Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -253,7 +253,14 @@ impl CyclotomicFourier for Complex64 {
253253

254254
impl<T: FixedInt> CyclotomicFourier for Complex<FixedPoint<T>>
255255
where
256-
Complex<FixedPoint<T>>: Copy + One + Zero + Add<Output = Self> + Sub<Output = Self> + Mul<Output = Self> + MulAssign + Inverse,
256+
Complex<FixedPoint<T>>: Copy
257+
+ One
258+
+ Zero
259+
+ Add<Output = Self>
260+
+ Sub<Output = Self>
261+
+ Mul<Output = Self>
262+
+ MulAssign
263+
+ Inverse,
257264
{
258265
fn primitive_root_of_unity(n: usize) -> Self {
259266
let c = Complex64::primitive_root_of_unity(n);

‎falcon-rust/src/encoding.rs‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -137,7 +137,7 @@ pub(crate) fn decompress(x: &[u8], n: usize) -> Option<Vec<i16>> {
137137
// approach is that acc_len is updated with a simple decrement — no
138138
// division or modulo by 8 on every bit.
139139
let mut result = Vec::with_capacity(n);
140-
let mut i = 0usize; // byte cursor into x
140+
let mut i = 0usize; // byte cursor into x
141141
let mut acc: u32 = 0;
142142
let mut acc_len: u32 = 0;
143143

@@ -150,7 +150,7 @@ pub(crate) fn decompress(x: &[u8], n: usize) -> Option<Vec<i16>> {
150150
acc = (acc << 8) | x[i] as u32;
151151
i += 1;
152152
// After the shift, the fresh byte occupies bits acc_len..acc_len+7.
153-
let s = (acc >> (acc_len + 7)) & 1; // sign: 0 = positive, 1 = negative
153+
let s = (acc >> (acc_len + 7)) & 1; // sign: 0 = positive, 1 = negative
154154
let mut m = (acc >> acc_len) & 0x7F; // |coeff| low 7 bits
155155

156156
// Read the unary-encoded high bits: zero or more 0-bits, terminated

‎falcon-rust/src/fast_fft.rs‎

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@ use num_complex::{Complex, Complex64};
99
use crate::{
1010
cyclotomic_fourier::CyclotomicFourier,
1111
falcon_field::Felt,
12-
fixed_point::{FixedPoint64, FixedPoint128},
12+
fixed_point::{FixedPoint128, FixedPoint64},
1313
fp_field::FpField,
1414
polynomial::Polynomial,
1515
U32Field,
@@ -1111,8 +1111,7 @@ impl FastFft for Polynomial<Complex64> {
11111111
type ComplexFP = Complex<FixedPoint64>;
11121112

11131113
lazy_static! {
1114-
static ref FP_BITREVERSED_POWERS_1024: Vec<ComplexFP> =
1115-
ComplexFP::bitreversed_powers(1024);
1114+
static ref FP_BITREVERSED_POWERS_1024: Vec<ComplexFP> = ComplexFP::bitreversed_powers(1024);
11161115
}
11171116

11181117
impl FastFft for Polynomial<ComplexFP> {

‎falcon-rust/src/ffsampling.rs‎

Lines changed: 16 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -133,7 +133,6 @@ pub(crate) fn build_falcon_tree(
133133
convert_tree_fixed128(tree)
134134
}
135135

136-
137136
// ---------------------------------------------------------------------------
138137
// LDL tree (FixedPoint64) — stored in SecretKey, used by ffsampling
139138
// ---------------------------------------------------------------------------
@@ -171,21 +170,17 @@ pub(crate) fn ffsampling(
171170
}
172171
LdlTree::Leaf(value) => {
173172
let sigmin = FixedPoint128::from(parameters.sigmin);
174-
let z0 = sampler_z(
175-
t.0.coefficients[0].re,
176-
value[0].re,
177-
sigmin,
178-
rng,
179-
);
180-
let z1 = sampler_z(
181-
t.1.coefficients[0].re,
182-
value[0].re,
183-
sigmin,
184-
rng,
185-
);
173+
let z0 = sampler_z(t.0.coefficients[0].re, value[0].re, sigmin, rng);
174+
let z1 = sampler_z(t.1.coefficients[0].re, value[0].re, sigmin, rng);
186175
(
187-
Polynomial::new(vec![Complex::new(FixedPoint128::from(z0), FixedPoint128::ZERO)]),
188-
Polynomial::new(vec![Complex::new(FixedPoint128::from(z1), FixedPoint128::ZERO)]),
176+
Polynomial::new(vec![Complex::new(
177+
FixedPoint128::from(z0),
178+
FixedPoint128::ZERO,
179+
)]),
180+
Polynomial::new(vec![Complex::new(
181+
FixedPoint128::from(z1),
182+
FixedPoint128::ZERO,
183+
)]),
189184
)
190185
}
191186
}
@@ -243,10 +238,12 @@ mod test {
243238
let a: [Polynomial<ComplexFP>; 4] = (0..4)
244239
.map(|_| {
245240
(0..n)
246-
.map(|_| Complex::new(
247-
FixedPoint64::from(rng.random::<f64>()),
248-
FixedPoint64::from(rng.random::<f64>()),
249-
))
241+
.map(|_| {
242+
Complex::new(
243+
FixedPoint64::from(rng.random::<f64>()),
244+
FixedPoint64::from(rng.random::<f64>()),
245+
)
246+
})
250247
.collect_vec()
251248
})
252249
.map(Polynomial::new)

‎falcon-rust/src/polynomial.rs‎

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -157,10 +157,9 @@ impl<F: Zero + PartialEq + Clone> Polynomial<F> {
157157
}
158158
let mut max_index = self.coefficients.len() - 1;
159159
while self.coefficients[max_index] == F::zero() {
160-
if let Some(new_index) = max_index.checked_sub(1) {
160+
{
161+
let new_index = max_index.checked_sub(1)?;
161162
max_index = new_index;
162-
} else {
163-
return None;
164163
}
165164
}
166165
Some(max_index)

‎falcon-rust/src/samplerz.rs‎

Lines changed: 34 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -85,9 +85,12 @@ fn ber_exp(x: FixedPoint128, ccs: FixedPoint128, random_bytes: [u8; 7]) -> bool
8585
let shamt = usize::min(s, 63);
8686
let z = ((((approx_exp(r, ccs) as u128) << 1) - 1) >> shamt) as u64;
8787
let mut w = 0i16;
88-
for (index, i) in (0..64).step_by(8).rev().enumerate() {
89-
let byte = random_bytes[index];
90-
w = (byte as i16) - (((z >> i) & 0xff) as i16);
88+
89+
// Compare `random_bytes` against the bytes of `z`, most significant first.
90+
// Zip takes the length of the shortest sequence.
91+
let shifts = (0..u64::BITS).step_by(8).rev();
92+
for (byte, shift) in random_bytes.into_iter().zip(shifts) {
93+
w = (byte as i16) - (((z >> shift) & 0xff) as i16);
9194
if w != 0 {
9295
break;
9396
}
@@ -467,6 +470,34 @@ mod test {
467470
);
468471
}
469472

473+
/// Regression test for an out-of-bounds index in `ber_exp`.
474+
///
475+
/// Previously, all-equal bytes led to a panic.
476+
#[test]
477+
fn ber_exp_all_bytes_tie_leads_to_rejection() {
478+
let x = FixedPoint128::from(0.05_f64);
479+
let ccs = FixedPoint128::from(0.709_907_609_444_444_4_f64);
480+
481+
// Reconstruct z exactly as ber_exp does.
482+
let s = (x / FixedPoint128::LN_2).trunc() as usize;
483+
let r = x - FixedPoint128::LN_2 * FixedPoint128::from(s as i32);
484+
let shamt = usize::min(s, 63);
485+
let z = ((((approx_exp(r, ccs) as u128) << 1) - 1) >> shamt) as u64;
486+
487+
// Every available byte equals z's byte at the same position, so the
488+
// loop never breaks early and runs to the end of the buffer.
489+
let mut bytes = [0u8; 7];
490+
for (index, byte) in bytes.iter_mut().enumerate() {
491+
*byte = ((z >> (8 * (7 - index))) & 0xff) as u8;
492+
}
493+
494+
// Pre-fix this panicked with "index out of bounds: the len is 7 but the index is 7".
495+
assert!(
496+
!ber_exp(x, ccs, bytes),
497+
"all bytes tie, so w == 0 and the draw is rejected"
498+
);
499+
}
500+
470501
/// The 20 published BerExp precision vectors from
471502
/// https://github.com/spartan8806/falcon-sampler-kat (`vectors/berexp.json`, vendored).
472503
///

0 commit comments

Comments
 (0)