eeshenggoh - The verification can lead to Merkle tree collision

[sherlock-admin2]

eeshenggoh

medium

The verification can lead to Merkle tree collision

Summary

AvailBridge utilizes Merkle Proof for leaf verification; however, it overlooks the verification of the length of the leaf bytes.

Vulnerability Detail

It's a must to ensure to avoid using leaf values that are 64 bytes long before hashing or utilize a hash function other than keccak256 for hashing leaves. This is because the concatenation of a sorted pair of internal nodes in the Merkle tree could be reinterpreted as a leaf value.

abi.encode encodes the params according to the ABI specs. Params are padded out to 32 bytes.
Since abi.encode(bytes32,bytes32) will also be 64 bytes it is possible to have a hash collision between a leaf and a parent node.

Reference & Credits

Impact

The leaf and parent data have the same 64-byte size, allowing hash collisions between a leaf and any node. This enables the repetition of proofs using subtrees as leaves, leading to the creation of fraudulent proofs.

Code Snippet

https://github.com/sherlock-audit/2023-12-avail/blob/1afb56b8d4dfbf5d3f21bed0ddf80a04730204b5/contracts/src/interfaces/IAvailBridge.sol#L22C1-L39C6

//contracts/src/interfaces/IAvailBridge.sol
    struct MerkleProofInput {
        // proof of inclusion for the data root
        bytes32[] dataRootProof;
        // proof of inclusion of leaf within blob/bridge root
        bytes32[] leafProof;
        // abi.encodePacked(startBlock, endBlock) of header range commitment on vectorx
        bytes32 rangeHash;
        // index of the data root in the commitment tree
        uint256 dataRootIndex;
        // blob root to check proof against, or reconstruct the data root
        bytes32 blobRoot; //@audit 
        // bridge root to check proof against, or reconstruct the data root
        bytes32 bridgeRoot;//@audit 
        // leaf being proven
        bytes32 leaf;
        // index of the leaf in the blob/bridge root tree
        uint256 leafIndex;
    }

https://github.com/sherlock-audit/2023-12-avail/blob/1afb56b8d4dfbf5d3f21bed0ddf80a04730204b5/contracts/src/AvailBridge.sol#L491

 dataRootCommitment, input.dataRootIndex, keccak256(abi.encode(input.blobRoot, input.bridgeRoot))

Tool used

Manual Review

Recommendation

Use a combination of variables that does not sum to 64 bytes

[QEDK]

It is theoretically impossible to find a leaf-pair combination that corresponds to a specific concatenated hash. Secondly, since the alignment of blobRoot and bridgeRoot is fixed and both have to be revealed during a transaction, it is unclear how an internal node collision is feasible - for e.g. an internal node will never be 0x0 and it is impossible to find an internal node that resembles either root. Submit a PoC and/or proper theoretical explanation for this attack vector.

[sherlock-admin]

1 comment(s) were left on this issue during the judging contest.

takarez commented:

invalid because { invalid: same as previous issue which was deemed invalid : https://github.com/sherlock-audit/2023-12-footium-judging/issues/5}

[QEDK]

Disputing per what I've said before + until there is a valid PoC.

[cvetanovv]

I'm closing this issue for now. If Watson wants he can escalate and provide a POC