Insecure implementation of the Fiat-Shamir transformation

[seresistvanandras]

The incorrect implementation of the Fiat-Shamir transformation enables the following attack. This attack allows an adversary to create a structured reference string that does not have the correct form needed for the trusted setup.

The main observation is that the sampled randomness only depends on the first updated group element g1s[0] and not on the others. This is how currently the random coefficients are computed.

https://github.com/a16z/evm-powers-of-tau/blob/88eeb8bca6af6b34e35b1db7ef4228955340c6b5/contracts/KZG.sol#L53

https://github.com/a16z/evm-powers-of-tau/blob/88eeb8bca6af6b34e35b1db7ef4228955340c6b5/contracts/KZG.sol#L82

Then in a loop, the contract generates all the random coefficients depending on the previous random coefficient. Gas efficient and neat solution, but is it secure? https://github.com/a16z/evm-powers-of-tau/blob/88eeb8bca6af6b34e35b1db7ef4228955340c6b5/contracts/KZG.sol#L89

This allows an attacker that given the previous element in G1 prevG1_0, the new updated G1 element g1s[0] and the first element of the Schnorr-proof of knowledge of discrete logarithm can pre-compute all the random coefficients regardless of the remaining elements in the structured reference string.

Let's take the simplest adversarial example to illustrate the attack. It is straightforward to generalize the attack for longer structured reference strings. We'll use the notation of the tech report. The adversary convinces the verifier that $B1, P{1,j},P{2,j},P{+,j}$ is of the form $B_1,\tau B_1,\tau^2 B_1,\tau B2$. However, $P{2,j}, P_{+,j}$ are chosen adversarially, yet the verification equation goes through. The adversary is given $\rho_0,\rho_1$ sampled as above. The pairing equation checks whether $$e(\rho_0 B_1+\rho1 P{1,j},P_{+,j})=e(\rho0 P{1,j}+\rho1 P{2,j}, B_2).$$

Note that the adversary can freely choose $P{+,j}$ and $P{2,j}$. Let's denote the discrete logarithms of these elements as $P_{+,j}=xB2$ and $P{2,j}=yP_1$. Then the pairing equation essentially checks that $$(\rho_0 +\rho_1\tau)x = \rho_0\tau+\rho_1 y.$$

Now the adversary samples $x$ randomly and computes $P_{+,j}=xB_2$. The adversary can do this because the random coefficients $\rho_0$ and $\rho1$ are not dependent on $P{+,j}$. Now the adversary wishes to compute $P_{2,j}$ such that the verification equation is satisfied. The adversary scalar multiplies $\rho_0 B_1+\rho1 P{1,j}$ by $x$ (it has just sampled $x$ by its own) to obtain $x\rho_0 B_1+x\rho1 P{1,j}$. Furthermore, the adversary computes $P':=x\rho_0 B_1+x\rho1 P{1,j}-\rho0 P{1,j}$. Finally, the adversary outputs $P_{2,j}=(\rho1)^{-1} P^{'}$. This $P{2,j}$ satisfies the pairing verification equation (it is constructed in such a way); however, it is not $\tau^2 B_1$ but rather a random group element.

It is easy to generalize this attack to longer trusted setup strings. The problem is that the adversary can choose $P{+,j}$ and $P{n,j}$ at its own will.

How to fix this bug?

• It should be enforced that $P_{+,j}=\tau B_2$. Maybe this requires another pairing check, hence this is not a gas efficient solution.
• All random $\rho$ values should also depend on $P{+,j}$ and the other $P{k,j}$ values for all $k\in[1,n]$ not only $k=1$.

[coventry]

It should be enforced that P+,j=τB2. Maybe this requires another pairing check, hence this is not a gas efficient solution.

Schnorr proofs of knowledge in AltBN128 should be quite cheap to verify onchain (much cheaper than a pairing), so that might be worth looking into.

[sragss]

Thanks for the review @seresistvanandras! The additional gas cost wasn't too bad (+5% for n=256).

[seresistvanandras]

You're welcome. Congrats on this work for you and the team! Excited to see this deployed soon! Now the contract looks secure to me.

It'll be interesting to watch how low we can get the overall gas cost of the ceremony's verification. I think the biggest savings will come from using compressed point formats and then decompressing them in the contract. That would cut half the calldata size immediately. Apart from this, I don't see many opportunities for gas golfing, but I'm not the best at gas golfing. Maybe, would it be possible to squash the DLOG check into the pairing check?

[sragss]

Same here!

Unfortunately point decompression is very expensive (2.7M gas for n=256), mainly due to this loop, so it makes sense to keep the calldata cost for now.

Lucas Meier has some ideas on making the proofs cheaper: https://cronokirby.com/notes/2022/09/trusted-setup-proofs/.

Another cool solution would be to create a STARK proof of the update. That has another host of concerns, but would remove the linear relation between n and update verification compute cost.

[seresistvanandras]

Unfortunately, point decompression is very expensive (2.7M gas for n=256), mainly due to this loop, so it makes sense to keep the calldata cost for now.

Why do you need that loop? It's a loop from the hash-to-curve function, no? I don't think you need that function for point decompression, maybe I'm missing something. The decompress function seems quite gas efficient for me: it only does arithmetic operations and a few bit shifts. I'd estimate that the decompress function burns less gas than the cost of storing the y-coordinate of the point in the calldata (that amounts to 68*32=2176 gas).

Lucas Meier has some ideas on making the proofs cheaper: https://cronokirby.com/notes/2022/09/trusted-setup-proofs/.

I've seen this proposal and made a back-of-the-envelope gas cost estimation here. The problem with Maurer proofs is that the proof size grows linearly in the ceremony size. Both approaches have roughly the same number of ECMUL and ECADD. The only difference is that one of the approaches uses pairings (113k gas), while the Maurer approach includes n scalars in the proof (each for 2176 gas). So after 50 or so elements, it is more efficient to do the pairing check and not include n scalars in the calldata. This is just a rough estimate, but overall I think Maurer proofs are not worth it for larger ceremonies.

Another cool solution would be to create a STARK proof of the update. That has another host of concerns, but would remove the linear relation between n and update verification compute cost.

Sounds cool. Though not sure if there is a stable implementation of BN or BLS curves in Cairo. So, maybe, as of today, it would be a lot of work to make this transition. But in the future, if such Cairo libraries are readily available, then it might be worth the effort. Now, it might be too much work IMHO.