Udsen - MERKLE LEAVES HAVE THE SAME LENGTH OF 64BYTES AS THE PARENT NODES IN THE `AvailBridge._checkDataRoot` FUNCTION THUS VALIDATING FRAUDULENT MERKLE PROOF

[sherlock-admin2]

Udsen

high

MERKLE LEAVES HAVE THE SAME LENGTH OF 64BYTES AS THE PARENT NODES IN THE AvailBridge._checkDataRoot FUNCTION THUS VALIDATING FRAUDULENT MERKLE PROOF

Summary

Merkle leaves have the same 64 bytes length before hashing as the parent node length before hashing thus leading to hash collision. Hence invalid proofs can be presented to validate invalide leaf data in the AvailBridge._checkDataRoot function, thus letting an attacker execute fraudulent message and asset transfer transactions.

Vulnerability Detail

The AvailBridge._checkDataRoot function is used for verifying a Merkle proof of inclusion for a data root. The verification happens by calling the verify function of the Merkle.sol library as shown below:

    if (
        !input.dataRootProof.verify( //@audit-info - proof of inclusion for the data root
            dataRootCommitment, input.dataRootIndex, keccak256(abi.encode(input.blobRoot, input.bridgeRoot)) //@audit-issue - 64 bytes length before hashing
        ) //@audit-info - dataRootCommitment -> root of the data root merkle tree, dataRootIndex -> index of hte speifici data root, abi.encode(input.blobRoot, input.bridgeRoot) -> leaf of the data root merkle tree
    ) {
        revert InvalidDataRootProof(); //@audit-info - if the verification is false then revert
    }

The leaf value passed to the verify function is calculated as keccak256(abi.encode(input.blobRoot, input.bridgeRoot). Both the input.blobRoot and input.bridgeRoot are bytes32 values thus making the prehashed length of the data bytes64 long.

Impact

As a result the size of a leaf is the same size of the parent data that is hashed, both are 64 bytes. As a result it is possible to have a hash collision between a leaf and any node in the tree. This allows for proofs to be repeated multiple times by taking subtrees as leaves.

abi.encode(bytes32,bytes32) (leaf) will output 64 bytes. And abi.encode(bytes32,bytes32) (node) will also be 64 bytes. Hence it is possible to have a hash collision between a leaf and a parent node.

As a result Fraudulent proofs can be submitted by an attacker to validate invalid input.blobRoot and input.bridgeRoot. Hence fraudulent transactions can be executed on the AvailBridge contract as a result.

Code Snippet

    function _checkDataRoot(MerkleProofInput calldata input) private view {
        bytes32 dataRootCommitment = vectorx.dataRootCommitments(input.rangeHash);
        if (dataRootCommitment == 0x0) {
            revert DataRootCommitmentEmpty();
        }
        // we construct the data root here internally, it is not possible to create an invalid data root that is
        // also part of the commitment tree
        if (
            !input.dataRootProof.verify(
                dataRootCommitment, input.dataRootIndex, keccak256(abi.encode(input.blobRoot, input.bridgeRoot))
            )
        ) {
            revert InvalidDataRootProof();
        }
    }

https://github.com/sherlock-audit/2023-12-avail/blob/main/contracts/src/AvailBridge.sol#L482-L496

Tool used

VSCode and Manual Review

Recommendation

Hence it is recommended to change the abi.encode(input.blobRoot, input.bridgeRoot leaf value calculation in the AvailBridge._checkDataRoot function such that the resulting encoded value length is !=64bytes length. This can be done by adding an addition data field in the merkle tree leaves before being hashed.

Duplicate of #10

[sherlock-admin]

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

takarez commented:

invalid because { invalid: also a dupp of issue 061}