⏸️Aztec Plonk Verifier: 0 Bug

Book an audit with Zokyo

Summary

Related Vulnerabilities: Missing Curve Point Checks

Identified By: Nguyen Thoi Minh Quan

The Aztec Plonk verifier, written in C++, accepts proofs containing multiple elements as per the Plonk protocol. However, by manually setting two of the elements to 0, the verifier will automatically accept that proof regardless of the other elements. This allows an attacker to successfully forge a proof.

Background

The full description of this bug is quite math heavy and dives deep into the Plonk protocol. The finder of this bug, Nguyen Thoi Minh Quan, has a great detailed description of the bug here.

Elliptic curves have what is known as a point at infinity. Let O = point at infinity and P be any point on the curve. Then O + P = P. When implementing a cryptographic protocol in code, there are different ways to express the point at inifinity. For example, sometimes the number 0 is considered the point at infinity, but other times 0 is considered as the point (0, 0), which is not the point at infinity. This will be important later.

Plonk proofs require a group of elements and curve points, and then will check whether these elements and points satisfy certain equations. One of the main equations to check is an elliptic curve pairing. The curve points that are of importance for this bug are [Wz]1 and [Wzw]1.

The Vulnerability

When [Wz]1 and [Wzw]1 are checked in the verifier code, a value of 0 is recognized as not on the elliptic curve, but the code does not fail immediately. The verifier continues on and later recognizes the 0 value as the point at infinity. This causes the pairing equation to be satisfied, and therefore the proof is successfully verified.

The Fix

The verifier was missing checks at a few different spots in the code. Just one of these checks would stop the 0 bug from working. These checks are explained in more detail in the finder's description. A simple to understand fix would be to agree on a consistent representation of the point at infinity. If 0 was consistently decided as not the point at infinity, then this bug would not work.

This bug is a good example of how implementing a secure cryptographic protocol can become insecure very easily. If one follows the Plonk paper exactly, this bug is not possible. This is a good reminder to test a protocol with inputs that theoretically would never work, as this finder did.

Conclusion

This is a deep dive into a vulnerability in the PLONK Zero-Knowledge Proof (ZKP) implementation. Let's break down the key points:

The Setup:

1. In cryptography, zero is unique because for any number $x$, $x×0=0$.

2. The PLONK ZKP has an issue that allows an attacker to generate a fake proof that would be accepted by all verifiers. This means they can falsely claim to know something without revealing it.

3. The PLONK ZKP uses a specific method that involves pairing, polynomial commitment, and points on elliptic curves.

The Attack:

1. The PLONK ZKP involves the verification of a complex mathematical equation. For an attacker, it's essential to know which parts of the equation they can manipulate.

2. It turns out that certain parameters, specifically [Wz]1 and [Wzω]1, are within the attacker's control.

3. The crux of the attack lies in setting these parameters to zero. By doing so, certain components of the verification equation get neutralized, making it much easier to satisfy the equation fraudulently.

The Vulnerability:

1. In practice, feeding zeros into the PLONK verifier should not work. Yet, it does. The author tried it, and the verifier was deceived, accepting the fake proof.

2. The reason for this is a series of software missteps:

   • The verifier doesn't stop its process when it encounters invalid points (in this case, zero points).

   • Checks in the elliptic curve code do not correctly identify the infinity point.

   • The code incorrectly computes the inverse of 0 mod p, a mathematical impossibility.

   • A batch normalization process inadvertently converts non-zero points into zero points.

   • The software fails to reject points in projective coordinates where z=0.

Wrapping up:

The attack successfully exploits a series of issues in the PLONK ZKP's C++ implementation. This vulnerability is particularly critical given that zero-knowledge proofs are designed to allow one party to prove to another that a statement is true, without revealing any information beyond the validity of the statement.

In simple terms, the discovered bugs let an attacker cheat the system by claiming to know something without having to prove it properly. The series of mistakes in the software lined up in such a way that a savvy attacker could bypass the verification process completely.

It's a good reminder that in the world of software and cryptography, multiple seemingly minor issues can combine to produce a significant vulnerability.

References

1. Nguyen Thoi Minh Quan's Description