Plonky2 Lookup Table Soundness Vulnerability

A vulnerability in Plonky2 version 1.0.0 allows a malicious prover to exploit lookup tables in a way that could deceive verifiers. The issue arises because lookup tables whose lengths are not divisible by 26 include a default '0 -> 0' input-output pair. This allows provers to falsely demonstrate knowledge of certain values in specific scenarios. The vulnerability is rooted in the 'LookupTableGate' padding with zeros, rather than with existing table pairs. The flaw is not present in the most common use cases, such as hash functions with table-based S-boxes, which typically do not allow for such exploitation.

Impact

Exploitation of this vulnerability could lead to incorrect verification of proofs, allowing a prover to cheat in circuits that rely on lookup tables for computation.

Reproduction

To reproduce this vulnerability, create a lookup table in Plonky2 version 1.0.0 that is not divisible by 26. Include a pair that maps '0' to '0'. Then, implement a circuit that uses this lookup table in a way that can be exploited, such as one that requires proving knowledge of a value that would satisfy a manipulated output using the lookup table.

Remediation

Upgrade to Plonky2 version 1.0.1, where this vulnerability has been fixed.