Skip to content

Commit b012e00

Browse files
committed
Fix FN-DSA BerExp sampler precision below Renyi divergence bound
Replace the degree-11 Taylor series approximation of exp(-x) in BerExp with the degree-12 minimax polynomial from the Falcon reference implementation (FACCT, Zhao et al. 2018). The old Taylor series achieved only 2^-34.26 relative precision over [0, ln2), which is ~54x coarser than the ~2^-40 Renyi divergence floor required by the FN-DSA security proof. This is the same defect class as the falcon-rust vulnerability GHSA-25rm-9wvm-m38v. The new minimax polynomial achieves 2^-50.42 precision (73,000x improvement), well within the security bound. Also fixes the Bernoulli comparison to use constant-time integer arithmetic (ct_lt_u64) instead of a data-dependent ternary, and replaces the s-clamping with the reference constant-time idiom. Reported-by: Conner (Spartan8806) <https://github.com/spartan8806>
1 parent 133daf8 commit b012e00

1 file changed

Lines changed: 64 additions & 36 deletions

File tree

‎src/core/sig/fndsa/sampler.c‎

Lines changed: 64 additions & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -14,11 +14,16 @@
1414
* 1. A base sampler via a cumulative distribution table (CDT) that
1515
* samples from a half-Gaussian D_{Z+,sigma_0} with sigma_0 =
1616
* sigma_min (the smallest per-level sigma in the Falcon tree).
17-
* 2. Bernoulli trials for acceptance/rejection, using the
18-
* decomposition of exp(-x) into a product of table-driven
19-
* factors.
17+
* 2. Bernoulli trials for acceptance/rejection, using BerExp to
18+
* compute exp(-x) via a degree-12 minimax polynomial with
19+
* precision better than 2^-50 over [0, ln2), satisfying the
20+
* Renyi divergence bound required by the FN-DSA security proof.
2021
* 3. Combination of base samples with rejection to produce a
2122
* sample from D_{Z,mu,sigma} for arbitrary (mu, sigma).
23+
*
24+
* Polynomial coefficients for the BerExp approximation are from the
25+
* FACCT paper (Zhao et al., 2018) via the Falcon reference
26+
* implementation.
2227
*/
2328

2429
#include <math.h>
@@ -139,64 +144,79 @@ base_sampler(pqc_shake256_ctx *sctx)
139144
* BerExp: accept with probability ~ exp(-x), where x is a non-negative
140145
* double. This uses the standard Falcon approach:
141146
* - Decompose x = s * ln(2) + r, 0 <= r < ln(2).
142-
* - Flip s coins each with probability 1/2; if any fail, reject.
143-
* - Accept with probability exp(-r) using a polynomial approx.
147+
* - Evaluate exp(-r) using a degree-12 minimax polynomial with
148+
* precision better than 2^-50 over [0, ln2).
149+
* - Shift right by s bits for the 2^(-s) factor.
150+
* - Constant-time Bernoulli comparison against uniform random.
144151
*
145-
* Returns 1 (accept) or 0 (reject). Constant-time.
152+
* Returns 1 (accept) or 0 (reject).
146153
*/
147154
static int
148155
ber_exp(pqc_shake256_ctx *sctx, double x)
149156
{
150157
int s;
151-
double r;
158+
double r, y;
152159
uint64_t w, z;
153-
int32_t sw;
160+
uint32_t sw;
154161

155162
static const double LN2 = 0.6931471805599453;
156163
static const double INV_LN2 = 1.4426950408889634;
157164

158165
s = (int)floor(x * INV_LN2);
159166
r = x - (double)s * LN2;
160167

161-
/* s should be small (< 64 normally). Clamp for safety. */
162-
sw = (int32_t)s;
163-
sw |= (int32_t)(63 - sw) >> 31; /* if s > 63, set sw = 63 */
164-
sw &= 63;
165-
166168
/*
167-
* Compute w = floor(exp(-r) * 2^63) using a degree-11 polynomial.
168-
* Coefficients are chosen for the range [0, ln(2)].
169+
* When x < 0 (possible with the current simplified ffSampling
170+
* that uses a global sigma), s is negative. Clamp to s=0, r=0
171+
* so the polynomial yields exp(0) = 1 and the test accepts
172+
* with probability ~1.
169173
*/
170-
{
171-
double p;
172-
double rr = -r;
173-
double term;
174-
int k;
175-
176-
/* exp(-r) = sum_{k=0}^{11} (-r)^k / k! */
177-
p = 0.0;
178-
term = 1.0;
179-
for (k = 0; k <= 11; k++) {
180-
p += term;
181-
term *= rr / (double)(k + 1);
182-
}
183-
/* p is now approximately exp(-r), in [exp(-ln2), 1] ~ [0.5, 1]. */
184-
/* Scale to 63-bit integer. */
185-
w = (uint64_t)(p * 9223372036854775808.0); /* p * 2^63 */
174+
if (s < 0) {
175+
s = 0;
176+
r = 0.0;
186177
}
187178

179+
/* Clamp s to [0, 63] (constant-time). */
180+
sw = (uint32_t)s;
181+
sw ^= (sw ^ 63u) & -(uint32_t)((63u - sw) >> 31);
182+
188183
/*
189-
* Rejection for the integer part s: flip s independent fair coins.
190-
* We shift w right by s bits (constant-time).
184+
* Evaluate exp(-r) using a degree-12 minimax polynomial via
185+
* Horner's method. Coefficients from Zhao et al., FACCT (2018),
186+
* via the Falcon reference implementation (fpr_expm_p63).
187+
*
188+
* Maximum relative error over [0, ln2) is below 2^-50, well
189+
* within the ~2^-40 Renyi divergence floor required by the
190+
* FN-DSA security proof.
191+
*/
192+
y = 0.000000002073772366009083061987;
193+
y = 0.000000025299506379442070029551 - y * r;
194+
y = 0.000000275607356160477811864927 - y * r;
195+
y = 0.000002755586350219122514855659 - y * r;
196+
y = 0.000024801566833585381209939524 - y * r;
197+
y = 0.000198412739277311890541063977 - y * r;
198+
y = 0.001388888894063186997887560103 - y * r;
199+
y = 0.008333333327800835146903501993 - y * r;
200+
y = 0.041666666666110491190622155955 - y * r;
201+
y = 0.166666666666984014666397229121 - y * r;
202+
y = 0.500000000000019206858326015208 - y * r;
203+
y = 0.999999999999994892974086724280 - y * r;
204+
y = 1.000000000000000000000000000000 - y * r;
205+
206+
/* Scale to 63-bit fixed-point. */
207+
w = (uint64_t)(y * 9223372036854775808.0); /* y * 2^63 */
208+
209+
/*
210+
* Multiply by 2^(-s): shift right by sw bits.
191211
*/
192212
w >>= sw;
193213

194214
/*
195-
* Final Bernoulli test: accept if a uniform random < w.
215+
* Constant-time Bernoulli test: accept if uniform random < w.
196216
*/
197217
z = prng_u64(sctx);
198-
z &= 0x7FFFFFFFFFFFFFFFULL; /* mask to 63 bits for comparison with w */
199-
return (z < w) ? 1 : 0;
218+
z &= 0x7FFFFFFFFFFFFFFFULL;
219+
return (int)ct_lt_u64(z, w);
200220
}
201221

202222
/* ------------------------------------------------------------------ */
@@ -228,6 +248,14 @@ fndsa_sampler_init(fndsa_sampler_ctx_t *ctx,
228248
* 4. Accept with probability proportional to
229249
* exp(-( (z0 - r)^2 / (2*sigma^2) - z0^2/(2*sigma0^2) ))
230250
* where r = mu - round(mu).
251+
*
252+
* NOTE: The full Falcon SamplerZ multiplies the acceptance probability
253+
* by ccs = sigma_min / sigma. This factor is currently omitted because
254+
* the ffSampling in sign.c uses a single global sigma rather than the
255+
* per-coefficient sigmas from the LDL* Gram-Schmidt tree. With the
256+
* global sigma, ccs would be ~0.008, making acceptance vanishingly rare.
257+
* The ccs factor should be added when ffSampling is corrected to use
258+
* per-coefficient sigmas (where ccs is typically 0.3--1.0).
231259
*/
232260
int32_t
233261
fndsa_sampler_sample(fndsa_sampler_ctx_t *ctx, double mu, double sigma)

0 commit comments

Comments
 (0)