Skip to content

Commit 4eb96fb

Browse files
committed
Fix intermittent XMSS verification failure and FN-DSA conversion UB
XMSS signatures failed to verify roughly one run in twelve, on every platform. xmss_hash_f leaves the keyAndMask address field set, and a WOTS+ chain whose base-w digit is zero performs no hash steps at all, so the address fed to the next chain's secret-key PRF depended on how many steps the previous chain took. Key generation always runs w-1 steps while signing runs digit-many, so the two derived different chain secrets whenever an earlier digit was zero. This was latent until the keyAndMask fix in 0.2.0 made that field significant; before then every node shared one key and the leftover state could not matter. Both derivation sites now reset keyAndMask before the PRF. Also clamps out-of-range and NaN double-to-int32_t conversions in ntru_solve.c and sign.c. The NTRU solver can diverge to magnitudes around 1e15, and such a conversion is undefined behaviour rather than a wrapping one. Reported by the UndefinedBehaviorSanitizer job. test_security_audit gains a WOTS+ round-trip check over many digit patterns, which is what isolated the defect; its XMSS groups are now compiled only when XMSS is enabled, so minimal builds link; and its timeout accommodates MemorySanitizer, under which rebuilding a Merkle tree per signature exceeds 600 s. Reported-by: Conner (Spartan8806) <https://github.com/spartan8806>
1 parent 172312e commit 4eb96fb

6 files changed

Lines changed: 176 additions & 6 deletions

File tree

‎CHANGELOG.md‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,41 @@ All notable changes to libpqc-dyber will be documented in this file.
55
The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.1.0/),
66
and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html).
77

8+
## [Unreleased]
9+
10+
### Security
11+
12+
- **XMSS: signatures intermittently failed to verify.** `xmss_hash_f`
13+
leaves the `keyAndMask` address field set, and a WOTS+ chain whose
14+
base-w digit is zero performs no hash steps at all — so the address fed
15+
to the next chain's secret-key PRF depended on how many steps the
16+
previous chain took, which differs between key generation (always w-1
17+
steps) and signing (digit-many steps). Affected chains derived
18+
different secrets in the two paths. This surfaced only once the
19+
`keyAndMask` fix in 0.2.0 made that field significant; before then it
20+
was masked by every node sharing one key. Reproduced at roughly 1 run
21+
in 12, and on every platform.
22+
- **FN-DSA: undefined behaviour converting out-of-range doubles to
23+
`int32_t`** in `ntru_solve.c` and `sign.c`. The NTRU solver can diverge
24+
and produce magnitudes around 1e15; an out-of-range or NaN
25+
float-to-integer conversion is undefined, not wrapping. Conversions are
26+
now clamped, leaving the caller's own correctness checks to reject the
27+
result. Caught by the UndefinedBehaviorSanitizer job.
28+
29+
### Added
30+
31+
- `test_security_audit` now asserts the WOTS+ round-trip invariant
32+
(`pk_from_sig(sign(m), m) == keygen()`) over many digit patterns, which
33+
is what caught the defect above.
34+
35+
### Fixed
36+
37+
- `test_security_audit` no longer fails to link in minimal builds; the
38+
groups that call XMSS internals are compiled only when XMSS is enabled.
39+
- Raised the regression suite's timeout to 1800 s. Rebuilding a Merkle
40+
tree per signature is inherent to what it asserts, and that exceeds a
41+
600 s budget under MemorySanitizer.
42+
843
## [0.2.0] - 2026-07-29
944

1045
This is a security release. It fixes four critical memory-safety defects,

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

Lines changed: 27 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -22,11 +22,35 @@
2222
#include <math.h>
2323
#include <string.h>
2424
#include <stdlib.h>
25+
#include <stdint.h>
2526

2627
#include "fndsa.h"
2728
#include "fndsa_params.h"
2829
#include "fft.h"
2930

31+
/*
32+
* Convert a double to int32_t with a defined result for every input.
33+
*
34+
* Converting a floating-point value that is outside the destination
35+
* integer's range -- or NaN -- is undefined behaviour in C, not a
36+
* wrapping conversion. The NTRU solver can diverge and produce
37+
* magnitudes far beyond int32_t (values around 1e15 have been observed
38+
* during key generation), so the conversion must be guarded rather than
39+
* assumed in range.
40+
*
41+
* Clamping keeps the conversion defined; a clamped coefficient is
42+
* nonsense as a solution, but the caller's own norm and correctness
43+
* checks reject it, which is the intended failure path.
44+
*/
45+
static inline int32_t fpr_to_i32(double x)
46+
{
47+
/* Written so that NaN takes the first branch rather than falling
48+
* through to the cast. */
49+
if (!(x >= -2147483648.0)) return INT32_MIN;
50+
if (x > 2147483647.0) return INT32_MAX;
51+
return (int32_t)x;
52+
}
53+
3054
/* Working prime. Must be > 2*q and fit in int64_t after squaring. */
3155
#define MOD_P 1073741789LL /* prime near 2^30 */
3256

@@ -131,8 +155,8 @@ ntru_lift_fft(unsigned logn,
131155
fndsa_fft_inverse(t3, logn);
132156

133157
for (i = 0; i < n; i++) {
134-
F[i] = (int32_t)floor(t2[i] + 0.5);
135-
G[i] = (int32_t)floor(t3[i] + 0.5);
158+
F[i] = fpr_to_i32(floor(t2[i] + 0.5));
159+
G[i] = fpr_to_i32(floor(t3[i] + 0.5));
136160
}
137161

138162
/* Babai reduction. */
@@ -174,7 +198,7 @@ ntru_lift_fft(unsigned logn,
174198
for (i = 0; i < n; i++) { Fn[i] = F[i]; Gn[i] = G[i]; }
175199

176200
for (i = 0; i < n; i++) {
177-
int32_t ki = (int32_t)floor(t2[i] + 0.5);
201+
int32_t ki = fpr_to_i32(floor(t2[i] + 0.5));
178202
if (ki == 0) continue;
179203
any = 1;
180204
for (j = 0; j < n; j++) {

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

Lines changed: 14 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -34,6 +34,19 @@
3434
#include "pqc/rand.h"
3535
#include "core/common/hash/sha3.h"
3636

37+
/*
38+
* Convert a double to int32_t with a defined result for every input.
39+
* See the note on fpr_to_i32 in ntru_solve.c: an out-of-range or NaN
40+
* float-to-integer conversion is undefined behaviour, and the recovered
41+
* G can be far outside int32_t when the key is malformed.
42+
*/
43+
static inline int32_t fpr_to_i32(double x)
44+
{
45+
if (!(x >= -2147483648.0)) return INT32_MIN;
46+
if (x > 2147483647.0) return INT32_MAX;
47+
return (int32_t)x;
48+
}
49+
3750
/* ------------------------------------------------------------------ */
3851
/* Hash-to-point: SHAKE-256 XOF -> polynomial in Z_q[x]/(x^n+1) */
3952
/* ------------------------------------------------------------------ */
@@ -462,7 +475,7 @@ fndsa_sign(uint8_t *sig, size_t *siglen, size_t sig_max,
462475
fndsa_fft_inverse(G_fft, logn);
463476

464477
for (i = 0; i < n; i++)
465-
G[i] = (int32_t)floor(G_fft[i] + 0.5);
478+
G[i] = fpr_to_i32(floor(G_fft[i] + 0.5));
466479
}
467480

468481
/*

‎src/core/sig/xmss/wots.c‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -154,6 +154,16 @@ void xmss_wots_keygen(uint8_t *pk, const uint8_t *seed,
154154
for (i = 0; i < LEN; i++) {
155155
xmss_addr_set_chain(addr, (uint32_t)i);
156156
xmss_addr_set_hash(addr, 0);
157+
/*
158+
* Reset keyAndMask before deriving the chain secret. xmss_hash_f
159+
* leaves it at 1, and a chain whose base-w digit is 0 performs no
160+
* hash steps at all -- so without this reset the address fed to
161+
* the PRF depends on how many steps the *previous* chain took,
162+
* which differs between key generation (always w-1 steps) and
163+
* signing (digit-many steps). That makes the derived secret, and
164+
* hence the chain, disagree between the two.
165+
*/
166+
xmss_addr_set_key_and_mask(addr, 0);
157167

158168
/* Derive chain secret key: sk[i] = PRF(seed, addr) */
159169
xmss_prf(sk_chain, seed, addr);
@@ -184,6 +194,8 @@ void xmss_wots_sign(uint8_t *sig, const uint8_t *msg,
184194
for (i = 0; i < LEN; i++) {
185195
xmss_addr_set_chain(addr, (uint32_t)i);
186196
xmss_addr_set_hash(addr, 0);
197+
/* See the note in xmss_wots_keygen. */
198+
xmss_addr_set_key_and_mask(addr, 0);
187199

188200
xmss_prf(sk_chain, seed, addr);
189201
xmss_chain(sig + (size_t)i * N, sk_chain, 0, basew[i], pub_seed, addr);

‎tests/CMakeLists.txt‎

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -43,8 +43,17 @@ target_link_libraries(test_security_audit PRIVATE pqc_static)
4343
target_include_directories(test_security_audit PRIVATE
4444
${PQC_INCLUDE_DIRS}
4545
${CMAKE_CURRENT_SOURCE_DIR}/../src)
46+
# The XMSS groups link against internal symbols, so they can only be
47+
# built when the algorithm is compiled in.
48+
if(PQC_ENABLE_SIG_XMSS)
49+
target_compile_definitions(test_security_audit PRIVATE PQC_TEST_XMSS_INTERNALS=1)
50+
endif()
4651
add_test(NAME test_security_audit COMMAND test_security_audit)
47-
set_tests_properties(test_security_audit PROPERTIES TIMEOUT 600)
52+
# The stateful-signature groups rebuild a full Merkle tree per operation
53+
# (XMSS re-runs treehash on every signature), which is slow enough under
54+
# MemorySanitizer to exceed a 600 s budget. The work is inherent to what
55+
# is being asserted, so allow for it rather than reduce coverage.
56+
set_tests_properties(test_security_audit PROPERTIES TIMEOUT 1800)
4857

4958
# Benchmarks (not added to CTest by default)
5059
if(PQC_BUILD_BENCHMARKS)

‎tests/unit/test_security_audit.c‎

Lines changed: 78 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -108,6 +108,13 @@ static void test_sig_buffer_bounds(void)
108108
}
109109
}
110110

111+
/*
112+
* The groups below call XMSS internals directly, so they are only built
113+
* when XMSS is compiled in. A minimal build with the algorithm disabled
114+
* has no such symbols to link against.
115+
*/
116+
#ifdef PQC_TEST_XMSS_INTERNALS
117+
111118
/* ------------------------------------------------------------------ */
112119
/* 2. XMSS: distinct leaves must derive distinct WOTS+ keys */
113120
/* ------------------------------------------------------------------ */
@@ -148,6 +155,69 @@ static void test_xmss_wots_leaf_separation(void)
148155
check(all_distinct, "XMSS: WOTS+ public keys differ across leaf indices");
149156
}
150157

158+
/* ------------------------------------------------------------------ */
159+
/* 2b. XMSS: WOTS+ must round-trip for every base-w digit pattern */
160+
/* */
161+
/* pk_from_sig(sign(m), m) must reproduce keygen()'s public key. This */
162+
/* is the invariant the whole scheme rests on, and it is sensitive to */
163+
/* leftover address state: a chain whose digit is 0 performs no hash */
164+
/* steps, so any field the hash function mutates but the caller does */
165+
/* not reset makes signing and key generation disagree. Many trials */
166+
/* are needed because the failure depends on the message digits. */
167+
/* ------------------------------------------------------------------ */
168+
169+
static void test_xmss_wots_roundtrip(void)
170+
{
171+
uint8_t sk_seed[PQC_XMSS_SHA2_N], pub_seed[PQC_XMSS_SHA2_N];
172+
uint8_t msg[PQC_XMSS_SHA2_N];
173+
static uint8_t pk_ref[PQC_XMSS_WOTS_LEN * PQC_XMSS_SHA2_N];
174+
static uint8_t sig[PQC_XMSS_WOTS_LEN * PQC_XMSS_SHA2_N];
175+
static uint8_t pk_chk[PQC_XMSS_WOTS_LEN * PQC_XMSS_SHA2_N];
176+
uint8_t addr[PQC_XMSS_ADDR_BYTES];
177+
const int trials = 400;
178+
int trial, i, mismatches = 0, first_bad = -1;
179+
180+
printf("\n[2b] XMSS: WOTS+ sign/recover round-trip (%d trials)\n", trials);
181+
182+
for (trial = 0; trial < trials; trial++) {
183+
for (i = 0; i < PQC_XMSS_SHA2_N; i++) {
184+
sk_seed[i] = (uint8_t)(i * 7 + trial);
185+
pub_seed[i] = (uint8_t)(i * 3 + trial * 5);
186+
/* Vary the digits, including zeros, across trials. */
187+
msg[i] = (uint8_t)(trial * 131 + i * 29);
188+
}
189+
190+
xmss_addr_zero(addr);
191+
xmss_addr_set_type(addr, PQC_XMSS_ADDR_TYPE_OTS);
192+
xmss_addr_set_ots(addr, (uint32_t)trial);
193+
xmss_wots_keygen(pk_ref, sk_seed, pub_seed, addr);
194+
195+
xmss_addr_zero(addr);
196+
xmss_addr_set_type(addr, PQC_XMSS_ADDR_TYPE_OTS);
197+
xmss_addr_set_ots(addr, (uint32_t)trial);
198+
xmss_wots_sign(sig, msg, sk_seed, pub_seed, addr);
199+
200+
xmss_addr_zero(addr);
201+
xmss_addr_set_type(addr, PQC_XMSS_ADDR_TYPE_OTS);
202+
xmss_addr_set_ots(addr, (uint32_t)trial);
203+
xmss_wots_pk_from_sig(pk_chk, sig, msg, pub_seed, addr);
204+
205+
if (memcmp(pk_ref, pk_chk, sizeof(pk_ref)) != 0) {
206+
mismatches++;
207+
if (first_bad < 0) first_bad = trial;
208+
}
209+
}
210+
211+
if (mismatches) {
212+
printf(" %d/%d trials mismatched (first at trial %d)\n",
213+
mismatches, trials, first_bad);
214+
}
215+
check(mismatches == 0,
216+
"XMSS: WOTS+ recovered public key matches keygen for all digits");
217+
}
218+
219+
#endif /* PQC_TEST_XMSS_INTERNALS */
220+
151221
/* ------------------------------------------------------------------ */
152222
/* 4. XMSS: WOTS+ checksum must sign its top nibble */
153223
/* ------------------------------------------------------------------ */
@@ -201,6 +271,8 @@ static void test_xmss_checksum(void)
201271
/* 7. XMSS: per-node hash keys must not collapse */
202272
/* ------------------------------------------------------------------ */
203273

274+
#ifdef PQC_TEST_XMSS_INTERNALS
275+
204276
static void test_xmss_addr_fields(void)
205277
{
206278
uint8_t a[PQC_XMSS_ADDR_BYTES], b[PQC_XMSS_ADDR_BYTES];
@@ -233,6 +305,8 @@ static void test_xmss_addr_fields(void)
233305
"XMSS: distinct nodes at one height get distinct key addresses");
234306
}
235307

308+
#endif /* PQC_TEST_XMSS_INTERNALS */
309+
236310
/* ------------------------------------------------------------------ */
237311
/* 3. LMS / XMSS: sign must actually verify */
238312
/* ------------------------------------------------------------------ */
@@ -469,9 +543,12 @@ int main(int argc, char **argv)
469543

470544
RUN("sizes", test_declared_sizes);
471545
RUN("bounds", test_sig_buffer_bounds);
546+
#ifdef PQC_TEST_XMSS_INTERNALS
472547
RUN("wots", test_xmss_wots_leaf_separation);
473-
RUN("checksum",test_xmss_checksum);
548+
RUN("wotsrt", test_xmss_wots_roundtrip);
474549
RUN("addr", test_xmss_addr_fields);
550+
#endif
551+
RUN("checksum",test_xmss_checksum);
475552
RUN("stateful",test_stateful_roundtrip);
476553
RUN("veriflen",test_verify_length_validation);
477554
RUN("kem", test_kem_implicit_rejection);

0 commit comments

Comments
 (0)