Data root validation is vulnerable to the second preimage attack

Summary

The Merkle tree used to validate the inclusion in the data root uses 64-byte leaves, making it vulnerable to an attack known as the second preimage attack, in which internal nodes of the tree can be used as leaves.

Vulnerability Detail

During message verification, the blobRoot and bridgeRoot are first verified to be included in the data root tree.

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

These two variables are concatenated and used as leaves in this Merkle tree. Both blobRoot and bridgeRoot are bytes32, thus making leaves (abi.encode(input.blobRoot, input.bridgeRoot)) 64 bytes long.

Merkle trees that use 64-byte leaves are vulnerable to the second preimage attack. Since internal nodes are 32 byte long (as these are the output of a keccak hash), then these can be combined to prove the presence of certain values that aren’t actually leaves in the tree.

Impact

The attack allows to prove the inclusion of internal nodes as leaves in the data root tree, which essentially means that an attacker can use non-valid bridgeRoot values, which are critical during message validation, as this is the root of the Merkle tree that is used to prove the inclusion and validation of messages (the Message struct).

Code Snippet

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

Tool used

Manual Review

Recommendation

Potential solutions are:

Use a different hash function for leaves, for example double hash leaves: keccak256(abi.encode(keccak256(abi.encode(input.blobRoot, input.bridgeRoot))))
Use a different length for leaves. During tree construction, prepend a certain constant value that could be used to discern leaves.

Duplicate of #10

sherlock-audit / 2023-12-avail-judging

fugazzi - Data root validation is vulnerable to the second preimage attack #61