Security pass over the legacy Kyber code

The CVEs this month spooked me, so this goes through the old code properly. It's a tracking issue: every real finding gets its own issue and PR, and goes into SECURITY.md once it's fixed. This doesn't have to block 2.0.0 and can carry on in 2.0.x.

Leads I already have (not confirmed yet):

poly_frommsg in src/kyber/poly.rs uses the same mask pattern as CVE-2024-37880 ("Clangover"), where the compiler turned it into a branch
Check that every compress path uses the multiply-and-shift trick instead of / q (KyberSlash)
verify/cmov in verify.rs: is there anything stopping the optimizer from adding a branch?
Key generation uses thread_rng(); compare with OsRng
Decaps doesn't zeroize all of its intermediates
from_keys takes any public/secret key pair. Check whether it can bind a key to the wrong pair, which is the kind of bug in the 2026 ML-KEM CVEs in other libraries

Also go through every CVE and paper listed in PLAN-2.0.md section 9 and note whether we're affected, with evidence.

Rule: no fix may change Kyber output. The golden vectors from #6 have to keep passing.

Open question: if something serious turns up before the release, do we hold 2.0.0 for it? I'd say yes for anything High or above, otherwise ship and patch.

Plan: WP-9.

Part of #3.

Two findings from the WP-2 audit (#28), logged here to fix later, plus what the same audit says about some of the leads above.

Finding 1: legacy Compress_11 is off by one at two residues

Severity: Info. It is not a timing or secrecy problem. Kyber-1024 differs from Compress_11 as defined in FIPS 203 (4.7) for two coefficient values. I did not check the round-3 spec text.
Location: src/kyber/polyvec.rs, polyvec_compress_1024 (du = 11).
Class: spec-deviation.
Evidence: demonstrated. The routine reuses the d = 4/5/10 multiplier (x << 11) + 1664) * 10321345 >> 35, which is exact for d = 1, 4, 5, 10 but not for 11. Compared with exact integer rounding over all of Z_q it differs only at x = 1875 and x = 3125 (each result is one too high). tests/mlkem_shared_primitives.rs pins this as legacy_compress_11_deviates_from_spec_at_two_residues. A multiplier that is exact for all of Z_q is ((x << 11) + 1664) * 645084 >> 31 (checked exhaustively; the pq-crystals reference uses the same one).
Legacy impact: any fix changes Kyber-1024 ciphertext bytes. I tried it and legacy_kyber_v1_0_5_outputs_are_frozen fails, so it cannot be fixed in place under the "no fix may change Kyber output" rule. Both ends of a Kyber exchange use the same routine, so it also does not break interop between pykyber versions.
Not assessed: whether the extra rounding error changes the decryption failure rate in a measurable way. I expect not, since it is one unit in 2^11 at two values, but I did not compute it.
Suggested handling: leave the legacy routine as is, document the deviation in SECURITY.md or the legacy docs, and keep the pinned test. ML-KEM-1024 does not use it (src/mlkem/compress.rs has an exact version).

Finding 2: zeroizing the Keccak state does not clear the permutation's stack spills

Severity: Low (memory hygiene, no remote vector).
Location: src/kyber/fips202.rs, keccakf1600_statepermute, called from sha3_256, sha3_512 and the SHAKE paths.
Class: memory-hygiene.
Evidence: demonstrated for x86_64, rustc 1.95, release. The function has a 0xf8-byte frame and about 70 stores of registers to it, and nothing clears the frame on return. The zeroize added in refactor: audit shared primitives, add generic ML-KEM types and refresh CLAUDE.md baseline (WP-2) #28 clears the 25-word state array (I confirmed those stores survive optimization in sha3_256 and sha3_512), but not these temporaries, which depend on the hashed input (m, z, the PRF seed). Not checked on other targets.
Related: FIPS 203 section 3.3 (intermediates shall be destroyed).
Legacy impact: none expected. Scrubbing stack space does not touch the output.
Suggested handling: decide whether this is worth fixing without unsafe (for example restructuring the permutation to keep the state in a caller-owned array, or accepting and documenting it). If not fixed, say so in SECURITY.md.

What the audit says about the leads in the description (same toolchain and targets as above, release builds; not the WP-8 gate)

poly_frommsg: the mask uses wrapping_neg() on a message bit, as in CVE-2024-37880. With rustc 1.95 I looked at a non-inlined copy on x86_64 and aarch64 and found no branch on message bits (the branches compare lengths and counters). So not seen here, but nothing guarantees it for other compilers or flags. Still worth hardening with a barrier.
Compress paths and KyberSlash: poly_tomsg, poly_compress, poly_compress_1024, polyvec_compress, polyvec_compress_1024 and poly_tobytes contain no div/idiv/udiv/sdiv on x86_64 or aarch64, and no branch compares a coefficient. Decompress was not scanned.
sha3_256 and sha3_512 now zeroize their state (refactor: audit shared primitives, add generic ML-KEM types and refresh CLAUDE.md baseline (WP-2) #28). The rest of the decaps intermediates lead is not covered.
Not looked at: verify/cmov barriers, thread_rng versus OsRng, from_keys binding, and the CVE and paper list.

Confirmed the last lead (from_keys and a wrong key pair) for the legacy classes while working on #13.

Kyber768.from_keys(a.public_key, b.secret_key) with two unrelated keypairs is accepted. The only check in from_keys is the public key length (_validate_pk); the secret key length is first looked at when you decapsulate. The keypair that comes back encapsulates without complaint, and decapsulate then returns a different secret than the one encapsulate produced, with no error. I ran this for 768 only. 512 and 1024 share the same code, so I expect the same, but I did not run them.

I'd call it Low: it is a silent misuse and leaks nothing. A fix is cheap because the Kyber secret key embeds the public key (sk = sk_pke || pk || H(pk) || z), so from_keys could compare pk with that copy. Both are public data, so a plain comparison is fine. It would change what an existing class accepts, so it needs your decision and the golden vectors from #6 must still pass. I did not touch it.

The new ML_KEM_*.from_keys in the #13 PR behaves the same way for now (sizes only, and the key checks run at use). I left it alone there too and say so in the PR.

Decisions for the fix pass, so the PR does not have to relitigate them. The legacy classes get fixed now, in one PR against dev-v2, instead of one issue and PR per finding. Kyber output stays byte-identical: the golden vectors from #6 must pass unchanged, and anything that would change them is not fixed.

To fix: harden poly_frommsg with an optimization barrier; put a barrier in verify and cmov; take legacy key generation randomness from OsRng and return an error if it fails (thread_rng goes); zeroize the decaps intermediates; make Kyber from_keys reject a public key that does not match the copy embedded in the secret key (the behavior change goes in the CHANGELOG).

Not fixed, documented in SECURITY.md: the Compress_11 deviation at x = 1875 and 3125 (a fix changes Kyber-1024 ciphertexts), and the Keccak permutation stack spills (no fix without unsafe).

Also in that PR: the affected / not affected table for every CVE and paper in PLAN-2.0.md section 9, with evidence. If a finding is High or above, it goes at the top of the PR description and 2.0.0 waits for my call.

fix: make Kyber from_keys reject a public key that is not the one in …

Navigation Menu

Repository navigation

Security pass over the legacy Kyber code #18

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Security pass over the legacy Kyber code #18

Description

Activity

Zikithezikit commented on Oct 30, 2026

Zikithezikit commented on Oct 30, 2026

Zikithezikit commented on Oct 30, 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions