falcon512_poseidon2: Polynomial zeroization is an unbacked promise, secret polynomial temporaries and encoded key buffers are never wiped
- Dominant language
- Rust
- Stars
- 772
- Forks
- 352
- Avg merge
- 1d 12h
- Merged PRs (30d)
- 93
Description
## Summary
Follow-up from the review discussion on 0xMiden/crypto#1057. `SecretKey` wipes its own basis on drop, but everything around it that carries the same secrets does not:
- `FalconFelt` has no `Zeroize` impl, so `Polynomial` does not satisfy the generic `impl Zeroize for Polynomial` and cannot be wiped even explicitly.
- `polynomial.rs:650` declares `impl ZeroizeOnDrop for Polynomial {}` with no `Drop` impl behind it. `ZeroizeOnDrop` is a marker trait, so this compiles and wipes nothing. Every `Polynomial` drops with its coefficients intact, including the `Polynomial` values the secret basis is built from.
- `SecretKey::write_into` builds the full encoded secret key in a heap buffer and drops it unwiped (secret_key.rs:310-341). The comment at line 341 says the buffer is consumed by `write_bytes`, but `write_bytes(&buffer)` only borrows it.
The third point bites on every signature: `generate_seed` zeroizes its own sk-bearing buffer (secret_key.rs:270-280) but builds it from `self.to_bytes()`, which leaves two more copies of the encoded key on the heap, the `write_into` buffer and the returned `Vec` temporary, neither of which is wiped.
## Walkthrough
Verified on `next` (9f98be9); line numbers below are from 0xMiden/crypto#1057's branch where the two differ.
In `SecretKey::read_from`, after 0xMiden/crypto#1057 the serialized buffer and the decoded `Vec` outputs are wiped, but coverage ends at the conversion to polynomials (secret_key.rs:394-405):
- `f`, `g`, `big_f` become `Polynomial` temporaries. No `Zeroize` impl is reachable for them, so they drop intact.
- `big_g = g.fft().hadamard_div(&f.fft()).hadamard_mul(&big_f.fft()).ifft()` allocates at least six more secret-carrying polynomials along the way: `fft()`/`ifft()` clone before transforming in place (fft.rs:17-21, 27-31) and the hadamard ops allocate fresh results (polynomial.rs:40-60). All drop intact, and the inverse vector `hadamard_div` allocates internally is not even reachable from the call site.
- Building the basis negates two polynomials (secret_key.rs:402, 404). `Neg` allocates a new polynomial (polynomial.rs:298-312) and the consumed originals drop intact. These are `Polynomial`, exactly the type the marker claims wipes itself on drop.
On why the marker has no `Drop` behind it: Rust rejects `Drop` impls with stricter bounds than the struct. `Polynomial` is unbounded (polynomial.rs:21), so `impl Drop for Polynomial` fails with E0367 (compiler output: ``Drop` impl requires `F: Zeroize` but the struct it is implemented for does not``), and bounding the struct with `F: Zeroize` is not an option either because the signing path uses `Polynomial>` (`to_complex_fft`, secret_key.rs:414-421) and `Complex` has no `Zeroize`. So the marker is not just unimplemented, it is unimplementable as declared. Notably `LdlTree` sits in the same `Complex64` boat and gets it right with a manual volatile-write `Drop` (ffsampling.rs:115-123); `Polynomial` is the only `ZeroizeOnDrop` impl in the crate with nothing backing it.
## Proposed fix
1. Implement `Zeroize` for `FalconFelt` (transparent `u32`, one line). That makes `Polynomial` wipeable through the existing generic impl.
2. Remove the unbacked `ZeroizeOnDrop` marker and make wipe-on-drop explicit at the use sites with `Zeroizing>`, the same pattern 0xMiden/crypto#1057 uses for the byte-level temporaries.
3. In `read_from`, wrap `f`/`g`/`big_f`/`big_g` in `Zeroizing` and bind the fft chain stepwise so the intermediates get wiped too, inlining `hadamard_div` as `hadamard_inv` plus `hadamard_mul` so the inverse lands in a wrapped value instead of an internal allocation. Negate the basis polynomials through references so the un-negated copies stay wrapped.
4. In `write_into`, zeroize `buffer` and the encoded chunks and fix the stale comment. In `generate_seed`, bind the serialized key in `Zeroizing` so the per-signature copies are covered.
5. Sweep the remaining `falcon512_poseidon2` call sites that hold secret polynomials (key generation, signing) for the same pattern.
An alternative for (2) is a dedicated secret-polynomial newtype with a real `Drop`, but that churns every signature along the secret path, and `Zeroizing` at the use sites gets the same guarantee without the churn.
Usual caveat applies: this covers the heap allocations the code can reach, anything spilled to stack or registers is out of scope, same as the existing zeroize usage in the crate.
I have the fix for all five items building and passing the falcon test suite locally, including reference-impl signature determinism. The sweep in (5) turned up two more live spots: `compute_pub_key_poly` clones `f` and `g` into `FalconFelt` polynomials on every signature and drops them intact, and `ntru_gen` drops rejected candidate pairs intact on every retry of its sampling loop; both are wiped now. The `BigInt` arithmetic inside `ntru_solve` and the `Complex64` FFT domain (`sign_helper`, `ffsampling`, `gram_schmidt_norm_squared`, `to_complex_fft`) are left as documented residue, since wiping those needs the volatile treatment `LdlTree` uses rather than `Zeroize`. This is the follow-up I offered in the 0xMiden/crypto#1057 review thread. The fix is open as 0xMiden/crypto#1061, stacked on 0xMiden/crypto#1057 so it should go in after that one.
Contributor guide
Assessment
This issue has not been assessed yet.