PQC-XXJTLU · cryptanalysis

Home › Public-key schemes › NEV

KEM · lattice

NEV

Design

nev-1

Failure-boosting bound built on a swapped distribution pair

Security proof gap · Demonstrated · Cause: specification text

Property: IND-CCA security

Cost against claim: designers' own bound falls to 2228.6 to 2230.0 classical, below the 2256 claim; the best costed attack stays at 2309.6

The C2 and C2* sets publish a decryption-failure rate of 2-162, but an independent convolution of the specified distributions gives 2-141.55, about 20 bits higher. With this true rate the designers' own failure-boosting method no longer establishes their claimed 256 classical bits, dropping to 2228.6 to 2230.0; the best attack anyone has costed, including the designers', still needs 2309.6 classical, so no known attack reaches the claim.

Parameter setClaimAttack costVerdict
NEV-C2, NEV-C2*256 classical against failure-boosting attacks by the designers' own Table 7 method2228.6 to 2230.0 classical by the same method with the corrected rate; best known costed attack 2309.6 classical / 2194.8 quantumSecurity proof gap

What causes it

Table 2 (spec p.22) assigns (chi_f, chi_g) = (B1, T1/8) to C2/C2*. Table 7's own mu* (p.61) matches that assignment exactly, but its p* matches the two distributions exchanged instead: recomputing delta with (T1/8, B1) reproduces the published 2-163.1, and mu* under that swap would be 37.33, not the published 21.37. The published failure rate and Table 7 bound come from mixing the two assignments within the same table.

Evidence

An independent script re-derived delta directly from eqs. (3)-(6), written before reading the prior evaluation's code: 2-141.55 for C2 (all-0 M -141.58, all-1 M -141.53), 2-141.32 for C2*, matching the earlier evaluation to 0.01 bit; the swapped assignment reproduces the published 2-163.1/-174.5. A second pass recomputed the Table 7 bound from eqs. (32)-(34) independently, reproducing every published row exactly from the published p*, then substituting the true p* to get 228.6 to 230.0 classical / 154.3 to 155.0 quantum for C2. Re-running the prior evaluation's own scripts (failure rate, Table 7 method, explicit failure-boosting cost) gave output identical to its logs.

Cause in the specification, traced to the specification text.

Limits

The explicit failure-boosting attack, costed at 2309.6 classical and 2194.8 quantum, stays above the 2256/2128 target: this is a gap in the designers' own security argument, not a working attack below the claim.

Credit

Found by PQC-X.

nev-2

Decapsulation timing depends on the decrypted message

Holds · Argued · Cause: specification text

Property: key recovery

Cost against claim: decapsulation leaks 0 to 45 rejected sampler bytes per call, a function of the recovered message

The rejection sampler used for the coins of several parameter sets squeezes hash output one byte at a time and keeps only accepted values, so the number of loop iterations during re-encryption depends on the message the decapsulation just recovered. The loop length is observable through memory access patterns and timing.

Parameter setClaimAttack costVerdict
NEV sets using T1/3 coins (uncompressed and R3)constant-time decapsulation (spec Sec. 9)message-dependent rejection-sampling signal; exploitation argued, not demonstratedHolds

What causes it

The sampler (spec Alg. 13, p.29) is specified as a loop that runs until an accepted byte is found, with no fixed iteration count: it is variable-time as written, even though the specification's own Sec. 9 and 9.1.2 (p.61, 63) claim the design is constant-time. The fix, a fixed number of bytes drawn plus a constant-time selection, is a change to the specified algorithm, not only to one implementation.

Evidence

Valgrind memcheck on a fresh, unmodified build, taint-tracking the secret polynomial, flags the rejection sampler (sample.c) reached through the re-encryption and decapsulation call chain for the sets that use these coins, while control sets using fixed-width coins show no such flag. A 20,000-random-message count of rejected bytes per re-encryption gives averages of 5.5, 11.0 and 21.9 across three flagged sets, ranging up to 45.

Cause in the specification, traced to the specification text.

Limits

The number of hash blocks squeezed is fixed up front, so the signal is only loop length and branch mispredictions, on the order of tens to hundreds of cycles, smaller than the analogous published signal in HQC/BIKE rejection sampling. No end-to-end key-recovery timing attack was run, only the message-dependent signal.

Credit

Found by PQC-X.