Merkle tree second preimage attack in Solidity

มาลุยกัน

โอเค ก่อนไปที่ตัวช่องโหว่ มาดูโจทย์กันก่อน โดยอันนี้เป็นโจทย์จาก Paradigm ctf 2022 ชื่อว่า merkledrop

โดยตัว contract จะเป็น contract สำหรับการ airdrop

โดยเริ่มจากการ set whitelist และเหรียญที่จะ airdrop

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

จากนั้นก็จะปล่อยให้คนเข้ามา claim ได้

    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);
    }

โดยในการเช็คว่าการ claim ถูกต้องมั้ยจะเริ่มจากการเช็คว่า index ของ ticket อันนั้นๆ claim ไปแล้วยัง

require(!isClaimed(index), 'MerkleDistributor: Drop already claimed.');

โดยใช้ bitmap ในการทดค่าไว้

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

    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;
    }

จากนั้นการเช็คความถูกต้องอันต่อมา จะเป็นการเช็คว่า ค่า index, account และ amount ที่ส่งมานั้น ได้ whitelist ไว้จริงๆมั้ย

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

จากนั้นเมื่อผ่านการเช็คต่างๆแล้วก็จะทำการ update ว่า index นี้เคลมแล้ว และส่ง token ให้กับ account ที่เป็น input

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

โอเค จุดที่เป็น red flag ของ contract นี้คือการที่ขนาดของ leaf ที่จะมาใช้ verify merkle proof เนี่ย ได้ขนาด 64 byte แบบเป๊ะๆ

ตามนี้เลย

uint256 index => 256 / 8 = 32 bytes

address account => address = 20 bytes

uint96 amount => 96 / 8 = 12 bytes

32 + 20 + 12 = 64

โอเค แล้วทำไมเลข 64 ถึงเป็น magic number ?

ก่อนอื่น เราต้องมาดูหลักการทำงานของ Merkle proof กันก่อน

จากรูป ค่า uint256 index, address account, uint96 amount ที่เราส่งมาเนี่ยคือ l2 ละกัน

ทีนี้การจะพิสูจน์ว่า h(l2) เนี่ยอยู่ใน tree นี้จริงๆ เราก็ต้องส่ง proof ซึ่งก็คือ [h(l1), h(b), h(f)] มาด้วย

โอเค แล้วช่องโหว่ คืออะไรละ

เรื่องเริ่มมาจาก จริงๆแล้ว merkle proof เนี่ย ไม่ได้ทำได้แค่เช็คว่า l1-l8 อยู่ใน tree มั้ย

แต่เช็คได้หมดเลยว่า leaf ไหนอยู่ใน tree บ้าง

เช่นเช็คว่า a ซึ่งเป็น node ชั้นที่ 2 ที่มาจาก h(l1) + h(l2) อยู่ใน tree มั้ยก็ทำได้ ตามรูป

ทีนี้ประเด็นมันอยู่ตรงนี้แหละ

ไม่ว่าจะส่ง l2 หรือ a มา ก็ proof ผ่านอยู่ดี

แสดงว่าจาก code ด้านล่าง มีโอกาสที่เหรียญจะส่งไปยัง account อะไรสักอย่าง ด้วย amount อะไรสักอย่าง ซึ่ง 2 ค่านี้ไม่ได้อยู่ใน whitelist เลย (ไม่ได้อยู่ในชั้น leaf) แต่เป็นค่าใน tree ชั้นอื่นๆที่เกิดขึ้นขณะ proof

// 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.');

โอเค แต่ทำไมขนาด leaf 64 byte ถึงเป็น magic number ของช่องโหว่นี้ละ ?

โอเค มาดูรูปกันอีกรอบ

คือ h() หรือ keccak256() เนี่ย return ค่าขนาด 32 byte ออกมา

โดยจากรูป a = h(l1) + h (l2) ดังนั้น a จะขนาด 64 byte เพราะเอา string 32 byte มาต่อกัน

แสดงว่า

1. ตัว merkle tree เนี่ย ตัว a b c d e f g จะมีขนาด 64 byte เสมอ

และอีกข้อที่เราพูดไปแล้วคือ

2. ปกติแล้วการเช็ค merkle proof เนี่ย ส่งค่า node ที่ไม่ใช่ leaf มาก็ผ่าน เช่นส่ง a มาก็ผ่าน

และเมื่อมาคอมโบกับ

3. ขนาดของ input ที่เป็น leaf ในข้อนี้คือ 64 byte พอดี (uint256 index, address account, uint96 amount)

จะกลายเป็น

attacker สามารถ

1. คำนวณ a ได้จาก

a = h(leaf ที่เป็น input ชุดที่ 1) + h(leaf ที่เป็น input ชุดที่ 2)

จากนั้น

2. นำ a ไปปรับ format ให้เป็น input ในการ verify ใหม่

เช่น

index = 32 byte แรกของ a

account = 20 byte ต่อมาของ a

amount = 12 byte สุดท้ายของ a

โดย

input ที่ความยาวรวมกันเท่ากับ 64 byte แบบนี้ จะเอาค่า a มาหั่นใช้ได้พอดี

แต่พอเป็นความยาวอื่นๆ เช่น 84 เนี่ย จะไม่ได้ละ ทำไม ? มาดูกัน

เอา a ยาว 64 byte เหมือนเดิม มาหั่น

uint256 index = 32 byte แรกของ a

address account = 20 byte ต่อมาของ a

uint256 amount = อันนี้ต้องใช้ 32 byte แต่ a เหลือแค่ 12 byte ทำให้กลายเป็น 12 byte สุดท้ายของ a + padding 20 byte

ประเด็นคือ hash(a แบบหั่น 64 byte เป็น 3 ส่วน) กับ hash(a แบบหั่น 64 byte เป็น 3 ส่วน แต่ส่วนสุดท้ายมี padding) เนี่ย ได้ค่าไม่เท่ากัน

ทำให้เมื่อ input ที่ใช้เป็น leaf เนี่ยไม่ได้มีความยาว 64 byte => ทำ attack นี้ไม่ได้

โอเค

ต่อมา เรากลับมาที่โจทย์กัน

ตัวโจทย์จะให้ tree มาด้วย

โดยจาก tree ที่โจทย์ให้ เราลองมาดู node 37 กัน

"0x8a85e6D0d2d6b8cBCb27E724F14A97AeB7cC1f5e": {
    "index": 37,
    "amount": "0x5dacf28c4e17721edb",
    "proof": [
        "0xd48451c19959e2d9bd4e620fbe88aa5f6f7ea72a00000f40f0c122ae08d2207b",
        "0x8920c10a5317ecff2d0de2150d5d18f01cb53a377f4c29a9656785a22a680d1d",
        "0xc999b0a9763c737361256ccc81801b6f759e725e115e4a10aa07e63d27033fde",
        "0x842f0da95edb7b8dca299f71c33d4e4ecbb37c2301220f6e17eef76c5f386813",
        "0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c",
        "0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5"
    ]
},

พอเราลอง hash จะได้ค่าคือ

โอเค ได้ h(l1) มาละ

ในการประกอบ a สูตรคือ

a = h(l1) + h(l2)

แล้วเราจะหา h(l2) ได้ยังไง ?

คำตอบคือ เอาจาก proof ของ leaf 37 ได้เลย

เพราะจริงๆแล้วตัว hash ข้างๆ leaf 37 เนี่ย ก็จะถูกส่งมาเป็น proof อยู่แล้ว

อย่างในรูป เวลา verify h(l2) ก็ต้องส่ง h(l1) มาใน proof

ดังนั้นจากข้อมูลของ index 37

"0x8a85e6D0d2d6b8cBCb27E724F14A97AeB7cC1f5e": {
    "index": 37,
    "amount": "0x5dacf28c4e17721edb",
    "proof": [
        "0xd48451c19959e2d9bd4e620fbe88aa5f6f7ea72a00000f40f0c122ae08d2207b",
        "0x8920c10a5317ecff2d0de2150d5d18f01cb53a377f4c29a9656785a22a680d1d",
        "0xc999b0a9763c737361256ccc81801b6f759e725e115e4a10aa07e63d27033fde",
        "0x842f0da95edb7b8dca299f71c33d4e4ecbb37c2301220f6e17eef76c5f386813",
        "0x0e3089bffdef8d325761bd4711d7c59b18553f14d84116aecb9098bba3c0a20c",
        "0x5271d2d8f9a3cc8d6fd02bfb11720e1c518a3bb08e7110d6bf7558764a8da1c5"
    ]
},

เราจะได้ว่า

a = h(l1) + h(l2)

h(l1) = hash ของ index 37 = 0xd43194becc149ad7bf6db88a0ae8a6622e369b3367ba2cc97ba1ea28c407c442

h(l2) = proof แรก ของ index 37 = 0xd48451c19959e2d9bd4e620fbe88aa5f6f7ea72a00000f40f0c122ae08d2207b

จะได้ a = 0xd43194becc149ad7bf6db88a0ae8a6622e369b3367ba2cc97ba1ea28c407c442d48451c19959e2d9bd4e620fbe88aa5f6f7ea72a00000f40f0c122ae08d2207b

พอเอามาหั่นเป็น input ในการ attack จะได้

index = 32 byte แรก ของ a = 0xd43194becc149ad7bf6db88a0ae8a6622e369b3367ba2cc97ba1ea28c407c442
account = 20 byte ถัดมาของ a = 0xd48451c19959e2d9bd4e620fbe88aa5f6f7ea72a
amount = 12 byte สุดท้ายของ a = 0xf40f0c122ae08d2207b

โดยเมื่อเรายิง tx นี้ไป จะผ่าน check ทุกอย่างหมดทั้ง

1. index ตัว index เลขเกินจำนวน leaf ไปไกลละ ไม่เคยถูกใช้แน่นอน
2. verify merkle proof ผ่าน เพราะเป็น node ชั้นที่สองใน tree
3. การส่งเหรียญผ่าน โดย amount 0xf40f0c122ae08d2207b เนี่ย ไม่เกินจำนวนเหรียญที่ contract มี งั้นก็แสดงว่า tx ไม่ revert ละ เป็นอันใช้ได้

เหลืออีกขั้นคือการหา proof ที่จะส่งไปกับ a ซึ่งก็ต้องดูว่า node ข้างๆเป็นอะไร ไต่ลำดับไปเรื่อยๆ

คร่าวๆคือ ถ้าจากรูปถ้าเราเป็น a ก็ลองหาดูว่าต้องหา h(b) โดย b = h(l3) + h(l4)

โดยเมื่อเราเป็น leaf 37 ดังนั้นก็จะนับต่อไปได้ว่า l3 l4 ที่ต้องหาเป็น leaf ถัดๆไป

เมื่อยิง tx ไป ก็จะเกิดการโจมตีแบบ griefing นั่นคือ attacker ไม่ได้ดูดเงินหาตัวเอง แต่ดูดเงิน contract ไปทิ้งที่ address นึงนั่นเอง

โอเค คร่าวๆประมาณนี้ครับ

Author Detail

Nattawat Songsom, Smart Contract Auditor and Consultant

About Valix Consulting

Valix Consulting is a blockchain and smart contract security firm offering a wide range of cybersecurity consulting services. Our specialists, combined with technical expertise, industry knowledge, and support staff, strive to deliver consistently superior quality services.

For any business inquiries, please contact us via Twitter, Facebook, or info@valix.io.

Referrence

The second preimage attack for Merkle Trees in Solidity

paradigm-ctf-2022/merkledrop at main · paradigmxyz/paradigm-ctf-2022

[TH] Paradigm CTF 2022 Writeup

MerkleProof: Intermediate nodes can be reinterpreted as leaves · Issue #3091 ·…