Plonky3 MultiField32Challenger: transcript malleability and challenge entropy loss
Impact
- Key:
challenger/src/multi_field_challenger.rs|MultiField32Challenger::duplexing|transcript_malleability - Affected files:
challenger/src/multi_field_challenger.rs,field/src/helpers.rs - Violated invariant: The Fiat-Shamir sponge must bind challenges to the exact sequence of observed field elements. Specifically: (1) absorption must be injective — distinct observation streams must produce distinct sponge states, (2) squeezing must be injective — distinct PF rate cells must yield distinct F challenge sequences, and (3) all bits of each absorbed PF element must influence the sponge state.
- Exploit scenario: An attacker controlling prover-side observations can craft distinct transcripts that produce identical challenges, breaking the binding property of Fiat-Shamir. Three independent attack vectors exist:
- Partial-chunk aliasing (absorb):
duplexing()packsinput_buffer.chunks(num_f_elms)viareduce_32(base 2^32) with no length marker and no zeroing of unused rate slots. Observing[x]followed by a sample yields the same sponge state as[x, 0, ..., 0](padded tonum_f_elms) followed by a sample, sincereduce_32treats missing high limbs identically to explicit zeros. The attacker can extend or truncate the tail of any observation batch without changing future challenges. - Non-injective squeeze (squeeze):
split_32decomposes each PF rate cell into base-2^64 digits and maps each throughTF::from_u64, which reduces modF::ORDER(~2^31). Two distinct PF values whose base-2^64 digits differ only in their upper 33 bits produce identical F challenge sequences. This weakens the entropy of sampled challenges and can enable selective forgery when the attacker can influence the sponge state pre-squeeze. - High-bit truncation (observe Hash/MerkleCap):
num_f_elms = PF::bits() / 64computes the number of F limbs per PF element. For BN254 (254-bit field), this yields 3 limbs covering 192 bits — the top 62 bits of every digest word are silently discarded. An attacker can find two distinct BN254 hash digests that differ only in bits 192–253 and observe them interchangeably without affecting challenges. - Evidence: In
duplexing(), the absorb path (reduce_32with base 2^32) and the squeeze path (split_32with base 2^64) use incompatible radices with no length domain separation.reduce_32is a plain Horner foldacc * 2^32 + digitwith no padding or tag, so trailing zeros are free.split_32extracts u64 digits and casts each viaTF::from_u64, which performs modular reduction, collapsing the top bits. The limb countPF::bits() / 64is a floor division that silently drops all bits beyond64 * num_f_elmsfor fields whose bit-width is not a multiple of 64.
Patches
Included in v0.4.3 and v0.5.3