Introduction
On November 7th to 8th, the annual cybersecurity conference called CODEGATE was held in South Korea. Alongside with, a 24 hour CTF was held, where the world’s top cybersecurity researchers solved various challenges on pwn, reverse engineering, web hacking, cryptography, and blockchain.
I actually got to make a few challenges for the qualification round and the final round of this CTF, and in the final round, I made a blockchain/cryptography hybrid challenge that mixes some flavor of ZK security and some flavor of blockchain security. After discussing with others, I decided that it would be best to share the challenge and its solutions to this forum.
If you want to solve the challenge yourself, please visit my github repository.
You will deploy a Setup contract, then attempt to make isSolved() return true.
Here’s the challenge. Below the contract is the solution, so please be careful about spoilers!
Challenge Contract
// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.8.0;
contract Challenge {
uint256 public p = 21888242871839275222246405745257275088548364400416034343698204186575808495617;
bool public solved = false;
bool public solved1 = false;
bool public solved2 = false;
bool public solved3 = false;
function isPowerOf2(uint256 n) public pure returns (bool) {
while(n % 2 == 0) {
n = n / 2;
}
return n == 1;
}
function declareSolved() public {
if(solved1 == true && solved2 == true && solved3 == true) {
solved = true;
}
}
function sanity_check(uint256 n, uint256[] memory f, uint256[] memory t, uint256[] memory s1, uint256[] memory s2) internal returns (bool) {
require(isPowerOf2(n + 1), "n + 1 not power of 2");
require(f.length == n && t.length == n + 1 && s1.length == n + 1 && s2.length == n + 1, "length checks");
for(uint i = 0 ; i < f.length ; i++) {
require(0 <= f[i] && f[i] < p);
}
for(uint i = 0 ; i < t.length ; i++) {
require(0 <= t[i] && t[i] < p);
}
for(uint i = 0 ; i < s1.length ; i++) {
require(0 <= s1[i] && s1[i] < p);
}
for(uint i = 0 ; i < s2.length ; i++) {
require(0 <= s2[i] && s2[i] < p);
}
return true;
}
function final_check(uint256 n, uint256[] memory f, uint256[] memory t, uint256[] memory s1, uint256[] memory s2, uint256 beta, uint256 gamma) internal view returns (bool) {
uint256 LHS = 1;
for(uint i = 0 ; i < n ; i++) {
LHS = mulmod(LHS, 1 + beta, p);
uint256 mul = (mulmod(gamma, 1 + beta, p) + mulmod(beta, t[i + 1], p) + t[i]) % p;
LHS = mulmod(LHS, mulmod(mul, gamma + f[i], p), p);
}
uint256 RHS = 1;
for(uint i = 0 ; i < n ; i++) {
uint256 mul1 = (mulmod(gamma, 1 + beta, p) + mulmod(beta, s1[i + 1], p) + s1[i]) % p;
uint256 mul2 = (mulmod(gamma, 1 + beta, p) + mulmod(beta, s2[i + 1], p) + s2[i]) % p;
RHS = mulmod(RHS, mulmod(mul1, mul2, p), p);
}
require(LHS == RHS, "check failed");
for(uint i = 0 ; i < n ; i++) {
bool ex = false;
for(uint j = 0 ; j <= n ; j++) {
if(f[i] == t[j]) {
ex = true;
}
}
if(ex == false) return true;
}
return false;
}
function challenge1(uint256 n, uint256[] memory f, uint256[] memory t, uint256[] memory s1, uint256[] memory s2) public {
require(sanity_check(n, f, t, s1, s2), "sanity check failed");
bytes32 beta = keccak256(abi.encode(n, f, t, s1, s2, uint256(1)));
bytes32 gamma = keccak256(abi.encode(n, f, t, s1, s2, uint256(2)));
require(final_check(n, f, t, s1, s2, uint256(beta) % p, uint256(gamma) % p), "final check failed");
solved1 = true;
}
function challenge2(uint256 n, uint256[] memory f, uint256[] memory t, uint256[] memory s1, uint256[] memory s2) public {
require(sanity_check(n, f, t, s1, s2), "sanity check failed");
uint256 len = (12 + 4 * n) * 0x20;
bytes32 beta; bytes32 gamma;
assembly {
let ptr := mload(0x40)
calldatacopy(ptr, 4, len)
mstore(add(ptr, len), 1)
beta := keccak256(ptr, add(len, 32))
mstore(add(ptr, len), 2)
gamma := keccak256(ptr, add(len, 32))
}
require(final_check(n, f, t, s1, s2, uint256(beta) % p, uint256(gamma) % p), "final check failed");
require(s1[n] == s2[0], "middle equality check failed");
solved2 = true;
}
function challenge3(uint256 n, uint256[] memory f, uint256[] memory t, uint256[] memory s1, uint256[] memory s2) public {
bytes32 beta; bytes32 gamma;
for(uint i = 0 ; i < 4 * n + 7 ; i++) {
assembly {
let ptr := mload(0x40)
mstore(ptr, beta)
mstore(add(ptr, 32), gamma)
mstore(add(ptr, 64), mload(add(0x80, mul(i, 32))))
mstore8(add(ptr, 96), 1)
mstore8(add(ptr, 97), 2)
beta := keccak256(ptr, 97)
gamma := keccak256(ptr, 98)
}
}
require(sanity_check(n, f, t, s1, s2), "sanity check failed");
require(final_check(n, f, t, s1, s2, uint256(beta) % p, uint256(gamma) % p), "final check failed");
require(s1[n] == s2[0], "middle equality check failed");
solved3 = true;
}
}
Solution
We see that the there are three challenges, and solving each challenges sets solved1, solved2, solved3 to be true respectively. Then, we can call declareSolved() to finish.
Each challenge gets the input of n, f, t, s1, s2, and it all cases it goes through a sanity_check, computes beta, gamma in some way, then goes through a final_check.
In the sanity check, the contract checks that
-
n + 1is a power of2 -
f, t, s1, s2has lengthsn, n+1, n+1, n+1respectively - each value inside
f, t, s1, s2are between0andp
In the final check, the contract checks that
and that there exists an i such that f[i] is not inside the array t.
Now experienced ZK enjoyers might notice that this is exactly the scenario in PLOOKUP.
The fundamental idea from PLOOKUP is that with pseudorandom \beta, \gamma (either selected by the verifier randomly or by Fiat-Shamir) the big equation above will hold (alongside with some additional checks) only if all elements in f is inside t and s1, s2 are chosen appropriately. Then, we do the standard grand product argument to check the big equation, then the usual stuff with the quotient polynomial.
Of course, the soundness proof relies on the Schwartz-Zippel Lemma, which forces the two polynomials in \beta, \gamma in the left/right hand sides to have the exact same coefficients, leading to soundness.
Here, the final check forces us to make the big equation stay true, while breaking soundness.
Let’s see what each of the three sub-challenges has in store for us!
Challenge 1
The computation of \beta, \gamma are done via Fiat-Shamir, hashing every single component via keccak256.
Here, the “overlapping check” inside PLOOKUP is gone. In PLOOKUP, there should be a check on s1[n] == s2[0]. This is the equation (c) from the below, which is from the PLOOKUP paper.
If we could remove this and still get soundness, this would save a decent portion of the computation.
Can we optimize PLOOKUP like this? It turns out the answer is no.
The easiest way to show this is to select two distinct a, b \in \mathbb{F}_p and set
and we see that everything cancels out, and the big equation holds true. Also, we clearly broke the soundness of the new “optimized PLOOKUP” protocol. This solves our first challenge.
This “overlapping check” is definitely a part that can be optimized. In the PLONKUP paper, the authors optimize this part out using a clever alternating halves trick. Now, there is no extra check.
Challenge 2
Here, the missing overlapping check is added. However, the computation of \beta, \gamma is strange.
uint256 len = (12 + 4 * n) * 0x20;
bytes32 beta; bytes32 gamma;
assembly {
let ptr := mload(0x40)
calldatacopy(ptr, 4, len)
mstore(add(ptr, len), 1)
beta := keccak256(ptr, add(len, 32))
mstore(add(ptr, len), 2)
gamma := keccak256(ptr, add(len, 32))
}
It loads (12 + 4n) * 0x20 bytes from the calldata (excluding the 4byte signature), puts it on the free memory location, then hashes it after appending 1 or 2 to get \beta and \gamma.
While it is true that the ABI encoding of n, f, t, s1, s2 has (12 + 4n) * 0x20 bytes, as
-
ntakes0x20bytes - the position, the length, the values of
ftakes(n + 2) * 0x20bytes - the position, the length, the values of
ttakes(n + 3) * 0x20bytes - the position, the length, the values of
s1takes(n + 3) * 0x20bytes - the position, the length, the values of
s2takes(n + 3) * 0x20bytes
which combines for a total of (12 + 4n) * 0x20 bytes, this can easily change.
For example, one can simply add a large number of zeros inside, and push the starting position of an array back. This will cause the first (12 + 4n) * 0x20 bytes of the calldata not fully include the entire n, f, t, s1, s2. Therefore, the derivation of \beta, \gamma via Fiat-Shamir will not fully incorporate all arrays that need to be taken into hashing. Now the solution is simple: push the position of s2 back, force the \beta, \gamma calculation to not include s2 in the hashing, then simply change s2 into whatever we want (while not modifying \beta, \gamma at all!) so that the big equation holds true. This solves our second challenge.
This entire “not hashing everything when doing Fiat-Shamir” is a big theme in ZK security.
Trail of Bits has found vulnerabilities like this in many public ZK repositories and even papers, and named this “Frozen Heart”. This is CVE-2022-29566 as well. You can learn more about these vulns at
so in conclusion, this challenge was
- understanding ABI encodings and how it works
- applying the Frozen Heart vulnerability on PLOOKUP
Challenge 3
Here, the overlapping check is also done properly. The derivation of \beta, \gamma are done as
for(uint i = 0 ; i < 4 * n + 7 ; i++) {
assembly {
let ptr := mload(0x40)
mstore(ptr, beta)
mstore(add(ptr, 32), gamma)
mstore(add(ptr, 64), mload(add(0x80, mul(i, 32))))
mstore8(add(ptr, 96), 1)
mstore8(add(ptr, 97), 2)
beta := keccak256(ptr, 97)
gamma := keccak256(ptr, 98)
}
}
If you use a debugger to check the memory layout, we can see that the array length and values of f, t, s1, s2 are laid out starting from 0x80. This means that
- length / values of
f, son+1values - length / values of
t, son+2values - length / values of
s1, son+2values - length / values of
s2, son+2values
so a total of 7+4n values (32 bytes) are laid out in the memory.
The hashing process goes
for each 0 \le i < 4n+7. Looks like an overkill, right?
The hidden vulnerability can be found if you
- know solidity very, very, very well and keep track of all security updates
- or simply log the calculated values of \beta, \gamma and take a look
Here, the key vulnerability is that \beta = \gamma. How is it possible?
Well, before the solidity team fixed it in solidity 0.8.3, there was an bug inside the bytecode optimizer that incorrectly optimized out a keccak256 evaluation. Basically, if the starting point (of the memory) of the two consecutive keccak256 operations were the same, the hashes were considered equal even when the length of the memory being hashed is different. For more details, check the solidity blog.
Therefore, in the code where
beta := keccak256(ptr, 97)
gamma := keccak256(ptr, 98)
is being done, the bytecode optimizer considers these two hashes as the same one. So \beta = \gamma.
Now we have a new challenge at our hands. It would be nice to keep soundness even when \beta = \gamma. After all, that means that the verifier has to generate less randomness, or, in the case of Fiat-Shamir, the prover gets to just compute a single hash. Can we optimize PLOOKUP in this way?
The answer is no. There are many ways to do this, i.e. find an example that breaks soundness.
- during CODEGATE CTF, some utilized z3 to do this
- it is possible to just assume n=1 and then run a brute force
- or you can just do the math and be tactical about your parameter choices
My solution was to set n=1, f=[1], t=[4,3], s_1=s_2=[2,2]. Checking this is left as exercise.
Solution Script
// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.8.0;
import "../lib/forge-std/src/Script.sol";
import "../src/Setup.sol";
contract ExploitScript is Script {
Setup setup;
Challenge chall;
function run() public {
chall = setup.challenge();
vm.startBroadcast();
{
uint256 n = 1;
uint256[] memory f = new uint256[](1); f[0] = 1;
uint256[] memory t = new uint256[](2); t[0] = 2; t[1] = 2;
uint256[] memory s1 = new uint256[](2); s1[0] = 1; s1[1] = 1;
uint256[] memory s2 = new uint256[](2); s2[0] = 2; s2[1] = 2;
chall.challenge1(n, f, t, s1, s2);
require(chall.solved1());
}
{
bytes memory data = new bytes(19 * 0x20);
assembly {
mstore(add(data, 0x20), 1)
mstore(add(data, 0x40), 0xa0)
mstore(add(data, 0x60), 0xe0)
mstore(add(data, 0x80), 0x140)
mstore(add(data, 0xa0), 0x200)
mstore(add(data, 0xc0), 1)
mstore(add(data, 0xe0), 1)
mstore(add(data, 0x100), 2)
mstore(add(data, 0x120), 2)
mstore(add(data, 0x140), 2)
mstore(add(data, 0x160), 2)
mstore(add(data, 0x180), 1)
mstore(add(data, 0x1a0), 1)
mstore(add(data, 0x1c0), 0)
mstore(add(data, 0x1e0), 0)
mstore(add(data, 0x200), 0)
mstore(add(data, 0x220), 2)
mstore(add(data, 0x240), 1)
mstore(add(data, 0x260), 7287299196098965986618773431837823862418990511618160691753196093008505079825)
}
address(chall).call(abi.encodePacked(chall.challenge2.selector, data));
require(chall.solved2());
}
{
uint256 n = 1;
uint256[] memory f = new uint256[](1); f[0] = 1;
uint256[] memory t = new uint256[](2); t[0] = 4; t[1] = 3;
uint256[] memory s1 = new uint256[](2); s1[0] = 2; s1[1] = 2;
uint256[] memory s2 = new uint256[](2); s2[0] = 2; s2[1] = 2;
chall.challenge3(n, f, t, s1, s2);
require(chall.solved3());
}
chall.declareSolved();
require(chall.solved(), "failed to solve");
vm.stopBroadcast();
}
}
Flag
The flag for this challenge was
codegate2022{1mpr0v1n6_pl00kup_15_h4rd_4f73r_4ll_bu7_47_l3457_w3_h4v3_2022/086_50_ju57_k33p_y0ur_h34r75_w4rm!_4l50_50l1d17y_0.8.3_15_h3r3_70_54v3_u5!}
so translating all the l33t stuff we get
- improving PLOOKUP is hard after all
- but at least we have 2022/086 (PLONKUP paper)
- so just keep your hearts warm (Frozen Heart vuln)
- also solidity 0.8.3 is here to save us! (solidity compiler 1-day vuln)
which summarizes the solutions of the three challenges. Hope you had fun reading this 