Forgery Attack on Unbalanced Merkle Trees

[c4-bot-2]

Lines of code

https://github.com/code-423n4/2024-05-arbitrum-foundation/blob/6f861c85b281a29f04daacfe17a2099d7dad5f8f/src/challengeV2/libraries/MerkleTreeLib.sol#L110

Vulnerability details

Impact

consensus issues,denial of service attacks,double spending attack.

Proof of Concept

https://github.com/code-423n4/2024-05-arbitrum-foundation/blob/6f861c85b281a29f04daacfe17a2099d7dad5f8f/src/challengeV2/libraries/MerkleTreeLib.sol#L110

The root function assumes that the provided Merkle expansion represents a balanced Merkle tree by calculating the root hash to non-zero values at each level but there's no check for checking if the provided Merkle tree is balanced or unbalanced

require(me.length > 0, "Empty merkle expansion");

Here's a test function in MerkleTreeLib.t.sol

function testForgeryAttackOnUnbalancedTree() public {
    
    uint256 numLeaves = 7;
    bytes32[] memory leaves = random.hashes(numLeaves);
    bytes32[] memory expansion = ProofUtils.expansionFromLeaves(l>
    bytes32 originalRoot = MerkleTreeLib.root(expansion);

    bytes32[] memory forgedExpansion = new bytes32[](4); // A bal>
    forgedExpansion[0] = leaves[0];
    forgedExpansion[1] = leaves[1];
    forgedExpansion[2] = hashTogether(leaves[2], leaves[3]);
    forgedExpansion[3] = hashTogether(hashTogether(leaves[4], lea>

    bytes32 forgedRoot = MerkleTreeLib.root(forgedExpansion);

assertEq(forgedRoot, originalRoot, "root checking");
}

forge test --match-test testForgeryAttackOnUnbalancedTree -vvvv

How it works:

Unbalanced Merkle Tree Construction:

Unbalanced Merkle tree with an odd number of leaf nodes (7 as demonstrated in the test function), the leaf nodes are represented as hashes of transactions.
leaves = [h1, h2, h3, h4, h5, h6, h7]. To construct the Merkle tree, the last leaf node h7 is duplicated to ensure that every non-leaf node has two children.

    Root
   /    \
  /      \
 /        \
/          \

h12 h34
/ \ /
h1 h2 h3 h4
/ \ /
h5 h6 h7 h7

Here the hashes at each level is identical to the unbalanced tree after duplicating the last leaf node.

Forging a Balanced Merkle Tree:
An attacker can forge a balanced Merkle tree with 8 leaf nodes by duplicating the last leaf node h7 to create balanced tree: forgedLeaves = [h1, h2, h3, h4, h5, h6, h7, h7].

    Root
   /    \
  /      \
 /        \
/          \

h12 h34
/ \ /
h1 h2 h3 h4
/ \ /
h5 h6 h7 h7

Here, the structure and the hashes at each level are identical to the unbalanced tree after duplicating the last leaf node resulting the same root hash as the original unbalanced tree, duplication of the last leaf node in the unbalanced tree (h7) allow the forged balanced tree with the same root hash.

Both trees end up with the same root hash because the structure and the hashes at each level is the same after the duplication of the last leaf node.

Sources:
HarryR/panautomata#4

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2012-August/001806.html

Tools Used

Manual review

Recommended Mitigation Steps

Consider adding a check in the root function to ensure that the provided Merkle tree is balanced by comparing the expected size of a balanced tree

uint256 expectedSize = 2 ** (me.length - 1);
require(treeSize(me) == expectedSize, "Unbalanced Merkle tree");

with the actual size calculated using the treeSize function.

Assessed type

Invalid Validation