🚨14. MiMC Hash: Assigned but not Constrained

Book an audit with Zokyo

Summary

Related Vulnerabilities: 1. Under-constrained Circuits, 2. Nondeterministic Circuits, 8. Assigned but not Constrained

Identified By: Kobi Gurkan

The MiMC hash circuit from the circomlib package had a missing constraint during its computation logic. The circuit was under-constrained and nondeterministic because it didn't properly constrain MiMC inputs to the correct hash output.

Background

In circom constraints are created by the following three operators: <==, ===, and ==>. If other operators are used such as <--, =, or -->, then a constraint will not be added to the R1CS file. These other operators assign numbers or expressions to variables, but do not constrain them. Proper constraints are what is needed for the circuit to be sound.

The Vulnerability

During a computation step for this circuit, the = operator was used instead of the <== operator that was needed to create a constraint. Here is the code before the fix:

outs[0] = S[nInputs - 1].xL_out;

The = operator assigned S[nInputs - 1].xL_out to outs[0], but did not actually constrain it. An attacker could then manipulate outs[0] when creating their own proof to manipulate the final output MiMC hash. Essentially, an attacker can change the MiMC hash output for a given set of inputs.

Since this hash function was used in the TornadoCash circuits, this would allow the attacker to fake a merkle root and withdraw someone else's ETH from the contract.

The Fix

The fix was simply to change = to a constraint operator <==.

outs[0] <== S[nInputs - 1].xL_out;

Conclusion:

The code utilized the assignment operator = when it should have used a constraint operator, specifically <==. This oversight meant that while the assignment happened correctly, there was no cryptographic guarantee that it followed the intended logic of the circuit.

Let's take a closer look at the problematic line:

javascriptCopy codeouts[0] = S[nInputs - 1].xL_out;

Here, the value of S[nInputs - 1].xL_out is assigned to outs[0], but this assignment doesn't create a constraint. Consequently, when an attacker is generating their zk-SNARK proof, they could potentially manipulate the value of outs[0], effectively allowing them to decide the output of the MiMC hash for certain inputs.

References

1. TornadoCash Explanation

2. Actual Github Fix