CVE-2026-77382: falcon-rust: Discrete-Gaussian sampler runs at 2^-33 precision, far below Falcon's requirement (reference KAT vectors no longer pass)
Medium CVSS 5.9
- OSV id
- GHSA-25rm-9wvm-m38v
- Also known as
- CVE-2026-77382
- Published
- Last modified
Affected packages
| Package | Affected versions | Fixed in |
|---|---|---|
| falcon-rust Cargo |
< 0.2.0 | 0.2.0 |
How to fix it
Upgrade falcon-rust to 0.2.0 or later.
cargo update -p falcon-rust --precise 0.2.0
- If it is an indirect dependency, `cargo update -p` still works; if a parent crate pins an older version, upgrade that crate.
- Check the changelog for breaking changes (especially across major versions), update the lockfile with the package manager, and run your tests.
Not sure whether your project uses an affected version? Check your lockfile below for free.
Details
Reporter: Connor Webber
Package: falcon-rust (crates.io), repository github.com/aszepieniec/falcon-rust
Affected: v0.1.3 and the current master (HEAD cfa1b35). Regression introduced in commit bf2cf00.
Component: discrete-Gaussian sampler, src/samplerz.rs (approx_exp, ber_exp, sampler_z)
Status: Confirmed by source review and by empirical measurement of the crate's own compiled code.
Summary
falcon-rust's discrete-Gaussian rejection sampler evaluates its exp() acceptance step at only 32 bits of fractional precision. Measured directly against the crate's own compiled code, approx_exp has a maximum relative error of 2^-33. For comparison, the Falcon reference implementation achieves about 2^-63, and the f64 code this crate replaced achieved about 2^-52. The current sampler is therefore roughly 2^19 (about 500,000x) less precise than the version it replaced, and about 2^30 less precise than the reference.
Falcon's security proof relies on the sampled signatures being statistically indistinguishable from an ideal discrete Gaussian, so the signature transcript leaks nothing about the secret trapdoor. That guarantee holds only when the sampler's relative error stays small enough, over the roughly 2^64 signature budget, to keep the Renyi divergence between the real and ideal distributions negligible. The precision the security analysis relies on is cited in the literature between roughly 2^-40 and 2^-46 (for example the FACCT and isochronous-sampling analyses). At 2^-33 the sampler is below every value in that range, roughly 128x to 4096x too coarse depending on which bound you take, so the precondition the proof depends on is not met.
There is a second, bound-independent piece of evidence that removes any ambiguity: the crate's sampler can no longer reproduce Falcon's known-answer test (KAT) vectors, which are the authoritative correctness oracle. Rather than restore the precision, the maintainers loosened their own test tolerance and noted that "rejection decisions may differ at the boundary." The regression is already visible in-tree; its security significance was simply not recognized.
Because the sampler's sigma is derived from the secret basis Gram-Schmidt norms, the resulting distribution deviation is secret-dependent. The exp function itself is public, but its inputs, and therefore the deviation, depend on secret quantities. This is the class of flaw that statistical and hidden-number-problem learning attacks on biased Gaussian samplers target.
The crate's own documentation describes this sampler as "side-channel-hardened" and notes that "the sampler defines the secret-key distribution, so getting it wrong weakens the cryptography," which is exactly the property this defect touches.
Technical detail
Root location: src/samplerz.rs
FixedPoint64 = FixedPoint<i64>withFRAC_UNIT = 1 << 32, i.e. 32 fractional bits (src/fixed_point.rs). The crate already definesFixedPoint128with 64 fractional bits, the correct-precision type, but the sampler usesFixedPoint64.approx_exp(samplerz.rs:34) evaluates the FACCT polynomial, whose coefficients are the correct 63-bit constants, but at line 59 it doeslet z: u64 = (x.0 as u64) << 31;. This takes the 32-bit-precision argument and zero-fills the low 31 bits into a 63-bit word, so the polynomial is evaluated at an argument quantized to 2^-32.sampler_zcomputesdss = 0.5 * isigma^2andccs = sigma_min * isigmain this 32-bit type, wheresigmais the per-leaf value derived from the secret basis Gram-Schmidt norms (ffSampling). The precision loss therefore lands on secret-dependent quantities.
Regression: commit bf2cf00 ("Eliminate f64 from key generation via generic FixedPoint<T>") replaced the prior f64 sampler. git show bf2cf00^:src/samplerz.rs shows the old fn approx_exp(x: f64, ccs: f64) operating at 63-bit scale. The change landed before the 0.1.3 release. The maintainers then re-pinned their tests to the degraded output and loosened the tolerance, and the Falcon KAT vectors no longer pass.
Proof of concept (self-contained, reproducible)
Append the following module to falcon-rust/src/samplerz.rs and run:
cargo test -p falcon-rust --release dump_approx_exp_precision -- --nocapture
It calls the crate's own approx_exp and measures its maximum relative error against true exp() over the sampler's input domain [0, ln 2].
```rust
[cfg(test)]
mod prectest { use super::*; #[test] fn dumpapproxexpprecision() { let n: u64 = 500000; let mut maxrel = 0.0f64; let two63 = 9223372036854775808.0f64; // 2^63 for i in 0..=n { let x = (i as f64 / n as f64) * std::f64::consts::LN2; let approxu = approxexp(FixedPoint64::from(x), FixedPoint64::ONE); let approx = approxu as f64 / two63; // ~ exp(-x) let truev = (-x).exp(); let rel = ((approx - truev) / truev).abs();
References
- GHSA-25rm-9wvm-m38v on OSV.dev
- Web: https://github.com/aszepieniec/falcon-rust/security/advisories/GHSA-25rm-9wvm-m38v
- Advisory: https://nvd.nist.gov/vuln/detail/CVE-2026-77382
- Web: https://github.com/aszepieniec/falcon-rust/commit/930d766256f9d67ec9b6d437557286cf47f042ca
- Web: https://github.com/aszepieniec/falcon-rust/commit/bf2cf000e63a9803f7ab1a34f629a5a0e9c49cf6
- Package: https://github.com/aszepieniec/falcon-rust
- Web: https://github.com/aszepieniec/falcon-rust/releases/tag/v0.2.0
Am I affected?
Upload or paste your lockfile. We check every package version in it against OSV.dev, this advisory included, and email you the vulnerable ones with the version that fixes them. Free, and no account needed.
About this data
Source: GitHub Advisory Database via OSV.dev (CC-BY 4.0). Severity comes from the advisory's own rating when it has one, else from its CVSS score.