ZKP Series: Pseudonym Input Vulnerability in Circom’s Verification Contract has Been Replicated

Overview

Earlier, a double-spending vulnerability in a zero-knowledge proof verification contract on Semaphore was uncovered by the Russian developer, Poma. As a matter of curiosity, my intention is to replicate the vulnerability’s PoC initially. However, due to the vulnerability code being old and the project being relatively complex, I opted to create a straightforward PoC to replicate the vulnerability.

Introduction

The foundation of Zero Knowledge Proof (ZKP) technology lies in an algorithm called a “proof system”. By performing a series of computations on the message, the algorithm produces a proof to demonstrate the genuineness of the message. The recipient can confirm the message’s authenticity by verifying the proof alone, without requiring additional information.

There are various implementation schemes for ZKP technology, which we discussed in our earlier article “Technical Features of ZKP Mainstream Implementation Schemes”. In this experiment, the Circom platform is employed, which utilizes Groth16 and PlonK as its proof system. During development, developers can select either system. The development framework generates proof parameters and verification contracts automatically without circuit modification.

In simpler terms, Circom creates witness data and attestation data on the client side and submits them to the contract. The verifier.sol contract verifies the submitted data to confirm whether the proof adheres to the specified rules. This approach enables rapid, efficient, and secure verification while safeguarding the message’s content and privacy.

Vulnerability Analysis

1. There isn’t much to discuss, so let’s proceed straight to the problematic code. Please refer to the “verifyHash” function in the image below. The code enclosed in the red box indicates whether specific witness data has been utilized. This method is commonly employed to prevent double spending. However, the vulnerability has arisen in the witness data “hash1”. Normally, a particular set of proof data should only correspond to a set of “hash1” values for verification purposes.

2. The “verify” function in the “verifier.sol” contract carries out elliptic curve computation verification on the input value via the “scalar_mul()” function. This function conducts calculations on elliptic curves utilizing the input parameters and matches the resulting value against the value specified in the provided proof. The function thereby confirms whether the input value is legitimate or not.

3. In a Solidity smart contract, encoding Fq necessitates the usage of the uint256 type. However, as the maximum value of uint256 is larger than the q value, several distinct integers may correspond to the same Fq value following the modulo operation. For example, “s” and “s+q” indicate the same point, namely the “sth” point. Similarly, “s+2q” and so on are also aliases for point “s”. This phenomenon is known as “Input Aliasing”, whereby these integers serve as pseudonyms for one another.

The “q” value mentioned here pertains to the cyclic group’s order, which signifies the number of values within the same Fq that can be input with numerous large integers. In essence, even if a q value is added to the hash, it can still satisfy the verification criterion. Within the uint256 type’s scope, a maximum of uint256_max/q distinct integers can indicate the same point. This signifies that a set of proofs can have up to 5 hash1 values that match and can pass the contract’s verification.

Vulnerability Recurrence

1. Develop a basic circuit that inputs two data sets and produces a witness data, i.e., “hash1,” utilized in the contract.

2. Compile the circuit to create “circuit_final.zkey”, “circuit.wasm”, and “verifier.sol”. Afterward, generate a collection of proofs, a standard hash, and a corrupted hash.

3. Subsequently, deploy the contract and employ the “checkHash” generated earlier to conduct a verification process. The verification successfully passes.

4. Next, apply the identical witness data and the previously generated “attackHash”. It is discovered that the verification is also successful. This demonstrates that a set of proofs can feature several matching hashes that meet the contract’s verification criteria. Thus, the Circom verification contract input pseudonym vulnerability has been effectively replicated.

Solutions to Vulnerabilities

The vulnerability arises from a set of proofs that can have at most 5 hash values that match and meet the contract’s verification requirements. Thus, the bug fix is straightforward: restricting all input hashes to a value less than “q”.

Summary

Input pseudonym vulnerability is a frequently encountered vulnerability in zero-knowledge proof and cryptography implementation. Its fundamental cause lies in the value being equivalent to the remainder within the finite field. Therefore, developers must focus on the verification group’s order when creating cryptography.

About SlowMist
SlowMist is a blockchain security firm established in January 2018. The firm was started by a team with over ten years of network security experience to become a global force. Our goal is to make the blockchain ecosystem as secure as possible for everyone. We are now a renowned international blockchain security firm that has worked on various well-known projects such as Huobi, OKX, Binance, imToken, Crypto.com, Amber Group, Klaytn, EOS, 1inch, PancakeSwap, TUSD, Alpaca Finance, MultiChain, O3Swap, etc.

Website：
https://www.slowmist.com
Twitter：
https://twitter.com/SlowMist_Team
Github：
https://github.com/slowmist/