Summary
The sample() method in DuplexChallenger returns raw sponge state elements that are canonical field elements in [0, P). When used as challenges in WHIR's ChallengeSampler::sample(), the distribution over the extension field is uniform modulo the field order, introducing a bias of ~(2^31 - P) / 2^31 per base field element. For KoalaBear (P = 2^31 - 2^24 + 1), this bias is 2^24/2^31 = 1/128.
Severity
HIGH -- Materially weakens security guarantees in adversarial settings.
Location
src/duplex_challenger.rs:55-70 -- sample_in_range uses bitwise masking which is correct for power-of-2 ranges, but sample() (line 45-52) returns elements that are already canonical field elements in [0, P), not uniform over [0, 2^31).
Impact
The 1/128 per-element bias accumulates across multiple challenge rounds. For 100+ challenges in a typical WHIR proof, this could reduce security by ~1-2 bits in adversarial settings.
Suggested Fix
Document clearly that sample() returns elements uniform in F_p (not in [0, 2^31)), and verify that all security proofs account for this. If field-element uniformity is insufficient (e.g., for grinding), add a rejection sampling path:
pub fn sample_uniform_bits(&mut self, bits: usize) -> usize {
loop {
let raw = self.sample()[0].as_canonical_u64() as usize;
let candidate = raw & ((1 << bits) - 1);
if raw < ((F::ORDER_U64 as usize) >> bits) << bits {
return candidate;
}
self.duplexing(None);
}
}References
Summary
The
sample()method inDuplexChallengerreturns raw sponge state elements that are canonical field elements in[0, P). When used as challenges in WHIR'sChallengeSampler::sample(), the distribution over the extension field is uniform modulo the field order, introducing a bias of~(2^31 - P) / 2^31per base field element. For KoalaBear (P = 2^31 - 2^24 + 1), this bias is2^24/2^31 = 1/128.Severity
HIGH -- Materially weakens security guarantees in adversarial settings.
Location
src/duplex_challenger.rs:55-70--sample_in_rangeuses bitwise masking which is correct for power-of-2 ranges, butsample()(line 45-52) returns elements that are already canonical field elements in[0, P), not uniform over[0, 2^31).Impact
The 1/128 per-element bias accumulates across multiple challenge rounds. For 100+ challenges in a typical WHIR proof, this could reduce security by ~1-2 bits in adversarial settings.
Suggested Fix
Document clearly that
sample()returns elements uniform inF_p(not in[0, 2^31)), and verify that all security proofs account for this. If field-element uniformity is insufficient (e.g., for grinding), add a rejection sampling path:References