Facebook: Critical bugs in Facebook/Polygon Winterfell library

### Summary In any succinct proof system, the prover’s goal is to convince the verifier that a certain statement is true. In practical systems, the verifier and the prover must agree on a set of security parameters that define how secure the system is. For instance, if the security parameter is set to 128-bit, we expect an attacker to spend 2128 resources to break it; in other extremes if the security parameter is 0-bit, the system has no security at all. The question is where security parameters come from? In simple systems, the security parameters are hard-coded constants and in complicated ones, the security parameters are defined in config files or keyset style like Google Tink. From the security perspective, it’s crucial that the prover can not affect the verifier's security parameters. The Winterfell system allows the malicious prover to set security parameters and makes it completely insecure. [Verifier's bug](https://github.com/facebook/winterfell/blob/cd76df242fcec8bab45efcdabf366fb0d8c76fbd/verifier/src/lib.rs#L96): let air = AIR::new(proof.get_trace_info(), pub_inputs, proof.options().clone()); As we can see, the verifier extracts the proof options from the proof which is fully controlled by the prover. Winterfell’s [ProofOptions](https://github.com/facebook/winterfell/blob/cd76df242fcec8bab45efcdabf366fb0d8c76fbd/air/src/options.rs#L37) defines several critical security parameters that the prover can manipulate. Note that proof soundness is bounded by `num_queries * log2(blowup_factor) + grinding_factor`. This lead to several attack directions: Set [num_queries](https://github.com/facebook/winterfell/blob/cd76df242fcec8bab45efcdabf366fb0d8c76fbd/air/src/options.rs#L61) to 1 (Winterfell checks for [0](https://github.com/facebook/winterfell/blob/cd76df242fcec8bab45efcdabf366fb0d8c76fbd/air/src/options.rs#L103) value) which reduces the security system to around 1 bit with blowup_factor equals to 2. Set [grinding_factor ](https://github.com/facebook/winterfell/blob/cd76df242fcec8bab45efcdabf366fb0d8c76fbd/air/src/options.rs#L63)to 0 so effectively reduces the system security by grinding_factor bits where the “expected” grinding factor is typically 20 bits. There is a 3rd way to exploit it. We can set [FieldExtension](https://github.com/facebook/winterfell/blob/cd76df242fcec8bab45efcdabf366fb0d8c76fbd/air/src/options.rs#L230) to 1 which significantly downgrades the system’s security. For instance, Plonky2 uses a 64-bit base field and uses field extension of degree 2 to make the system 128-bit security. By setting field extension degree back to 1, the attacker effectively reduces the system back to 64-bit security. There may be other ways to exploit this issue. ### Severity High - the verifier accepts a configuration parameter that can be controlled entirely by the adversary. This configuration parameter sets critical values such as the security parameter and field extension size. ### Proof of Concept ``` Preliminary PoCs to make sure that the verifier accepts malicious parameters. We also created PoC to bypass FRI -layer verification checks if the verifier doesn’t ask enough queries. We haven’t created a full PoC with a false statement yet. Patch winterfell as described in [Git diff](https://docs.google.com/document/d/11mkjCfm9k7rbJXN8gUyZv_xJX3wLGMyIS0laWLe63SI/edit#heading=h.borvwyxolp2t) section and either run 1/ ./target/debug/winterfell fib -n 128 Output: “Proof security: 0 bits Verifer's proof options at the end of execution: ProofOptions { num_queries: 1, blowup_factor: 2, grinding_factor: 16, field_extension: None, fri_folding_factor: 8, fri_max_remainder_size: 8 }” 2/ Run fib2_test_basic_proof_verification Output: “Proof: StarkProof { context: Context { trace_layout: TraceLayout { main_segment_width: 2, aux_segment_widths: [0], aux_segment_rands: [0], num_aux_segments: 0 }, trace_length: 8, trace_meta: [], field_modulus_bytes: [1, 0, 0, 0, 0, 211, 255, 255, 255, 255, 255, 255, 2

Severity from

GitHub (reviewed advisory)

• github.com/google/security-research/security/advisories/GHSA-8fhq-pf83-pv93
• github.com/google/security-research