0x52 - Merkle leaf values for _clubDivsMerkleRoot are 64 bytes before hashing which can lead to merkle tree collisions

[sherlock-admin]

0x52

high

Merkle leaf values for _clubDivsMerkleRoot are 64 bytes before hashing which can lead to merkle tree collisions

Summary

FootiumAcademy hashes 64 bytes when calculating leaf allowing it to collide with the internal nodes of the merkle tree.

Vulnerability Detail

MerkleProofUpgradeable.sol puts the following warning at the beginning of the contract:

 * WARNING: You should avoid using leaf values that are 64 bytes long prior to
 * hashing, or use 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.

FootiumAcademy.sol#L235-L240

    if (
        !MerkleProofUpgradeable.verify(
            divisionProof,
            _clubDivsMerkleRoot,
            keccak256(abi.encodePacked(clubId, divisionTier)) <- @audit-issue 64 bytes before hashing allows collisions with internal nodes
        )

This is problematic because FootiumAcademy uses clubId and divisionTier as the base of the leaf, which are both uint256 (32 bytes each for 64 bytes total). This allows collision between leaves and internal nodes. These collisions could allow users to mint to divisions that otherwise would be impossible.

Impact

Users can abuse merkle tree collisions to mint in non-existent divisions and bypass minting fees

Code Snippet

FootiumAcademy.sol#L228-L272

Tool used

Manual Review

Recommendation

Use a combination of variables that doesn't sum to 64 bytes

[0xRobocop]

Escalate for 10 USDC

I encountered the same issue, and I will provide my analysis on why this is not an issue in the current codebase, not even to classify as a medium.

The problem described is that the concatenation (which will be of 64 bytes long, if keccak256 is used) of 2 internal nodes of a merkle tree could collide with leaf values that also are 64 bytes long. For example:

Leaf Value (64 bytes), ignore the = symbols, they are used to separate the leaf value into two tranches of 32 bytes for illustration purposes:

0x9c644f34f630d76b78c6ccecfceabcf6b9f0def47e637403ac15c63bc6030920=====d6a1fb97571351113887953420cffc381edf9874c13f336e0c2c01bffe2214f4

Internal Node 1: 0x9c644f34f630d76b78c6ccecfceabcf6b9f0def47e637403ac15c63bc6030920

Internal Node 2: 0xd6a1fb97571351113887953420cffc381edf9874c13f336e0c2c01bffe2214f4

There we have a collision of a leaf value with the concatenation of the hash values of 2 sorted internal nodes.

In the current codebase, the probability of this to happen is negligible. The leaf value is computed as the concatenation of clubId and divisionTier. clubId is a variable that increments 1 by 1 (when a club is minted), if we were to mint 1 club in each second until the year 2106, we could mint a maximum amount of 2^32 clubs and the maximum divisionTier will be way lower than this number, but for illustration purposes I will assume that it is also 2^32.

Then, the maximum value the leaf can have is (again the = symbols are for illustration purposes to show the concatenation):

0x0000000000000000000000000000000000000000000000000000000100000000====0000000000000000000000000000000000000000000000000000000100000000

For a potential collision to happen, the concatenation of 2 internal nodes (which are keccak256 values) must be equal or smaller than the above number. Due to the inequality (equal or smaller) we are only interested in the internal node that will end-up on the left side. The hash value of the left-side internal node will need to be smaller than:

0x0000000000000000000000000000000000000000000000000000000100000000

Which has 55 leading zeros. The lowest hash found in the bitcoin network has 23 leading zeros reference.

Please keep in mind that OZ contracts are too general and that's why they put the warning, not to mention that the warning is a "should" not a "must" since the exploitation of this phenomenon will depend highly on the contracts which uses their MerkleProof library.

If the values that make up the leaf were to be controllable by the users, I would agree this is a medium or even a high vulnerability, but the leaf is made up of values, clubId and divisionTier, that are not controllable by the users and that we can predict their values.

PD: I would argue that issues reported based on warnings written in general-purpose libraries, should be accompanied with proof of concepts (coded or not) on how can be exploited in the codebase, even if it has some hypotheticals in the case of mediums, but not too hypothetical like producing a hash value with 55 leading zeros.

[sherlock-admin]

Escalate for 10 USDC

I encountered the same issue, and I will provide my analysis on why this is not an issue in the current codebase, not even to classify as a medium.

The problem described is that the concatenation (which will be of 64 bytes long, if keccak256 is used) of 2 internal nodes of a merkle tree could collide with leaf values that also are 64 bytes long. For example:

Leaf Value (64 bytes), ignore the = symbols, they are used to separate the leaf value into two tranches of 32 bytes for illustration purposes:

0x9c644f34f630d76b78c6ccecfceabcf6b9f0def47e637403ac15c63bc6030920=====d6a1fb97571351113887953420cffc381edf9874c13f336e0c2c01bffe2214f4

Internal Node 1: 0x9c644f34f630d76b78c6ccecfceabcf6b9f0def47e637403ac15c63bc6030920

Internal Node 2: 0xd6a1fb97571351113887953420cffc381edf9874c13f336e0c2c01bffe2214f4

There we have a collision of a leaf value with the concatenation of the hash values of 2 sorted internal nodes.

In the current codebase, the probability of this to happen is negligible. The leaf value is computed as the concatenation of clubId and divisionTier. clubId is a variable that increments 1 by 1 (when a club is minted), if we were to mint 1 club in each second until the year 2106, we could mint a maximum amount of 2^32 clubs and the maximum divisionTier will be way lower than this number, but for illustration purposes I will assume that it is also 2^32.

Then, the maximum value the leaf can have is (again the = symbols are for illustration purposes to show the concatenation):

0x0000000000000000000000000000000000000000000000000000000100000000====0000000000000000000000000000000000000000000000000000000100000000

For a potential collision to happen, the concatenation of 2 internal nodes (which are keccak256 values) must be equal or smaller than the above number. Due to the inequality (equal or smaller) we are only interested in the internal node that will end-up on the left side. The hash value of the left-side internal node will need to be smaller than:

0x0000000000000000000000000000000000000000000000000000000100000000

Which has 55 leading zeros. The lowest hash found in the bitcoin network has 23 leading zeros reference.

Please keep in mind that OZ contracts are too general and that's why they put the warning, not to mention that the warning is a "should" not a "must" since the exploitation of this phenomenon will depend highly on the contracts which uses their MerkleProof library.

If the values that make up the leaf were to be controllable by the users, I would agree this is a medium or even a high vulnerability, but the leaf is made up of values, clubId and divisionTier, that are not controllable by the users and that we can predict their values.

PD: I would argue that issues reported based on warnings written in general-purpose libraries, should be accompanied with proof of concepts (coded or not) on how can be exploited in the codebase, even if it has some hypotheticals in the case of mediums, but not too hypothetical like producing a hash value with 55 leading zeros.

You've created a valid escalation for 10 USDC!

To remove the escalation from consideration: Delete your comment.

You may delete or edit your escalation comment anytime before the 48-hour escalation window closes. After that, the escalation becomes final.

[SergeKireev]

Escalate for 10 USDC,

As per my report of the issue:
#170

For the issue to be valid there only needs to be a very specific value of clubId crafted. Indeed the divisionId arg should not be an existent division id for the exploit to work.

The specific value which the clubId should be equal to is: any left internal node of the merkle tree.

The owner of the contract has the power to mint arbitrary values (nowhere it is stated that it would be an auto-incremented id):
https://github.com/sherlock-audit/2023-04-footium/blob/main/footium-eth-shareable/contracts/FootiumClubMinter.sol#L68-L82

So the maximums determined in the first escalation do not hold.

Given that the vulnerability is only exploitable if the team decides to open the mint to the public in the future or if the owner account is compromised, the severity can be lowered. However the reasons for which the sponsor found this issue interesting and worth to fix still hold.

[sherlock-admin]

Escalate for 10 USDC,

As per my report of the issue:
#170

For the issue to be valid there only needs to be a very specific value of clubId crafted. Indeed the divisionId arg should not be an existent division id for the exploit to work.

The specific value which the clubId should be equal to is: any left internal node of the merkle tree.

The owner of the contract has the power to mint arbitrary values (nowhere it is stated that it would be an auto-incremented id):
https://github.com/sherlock-audit/2023-04-footium/blob/main/footium-eth-shareable/contracts/FootiumClubMinter.sol#L68-L82

So the maximums determined in the first escalation do not hold.

Given that the vulnerability is only exploitable if the team decides to open the mint to the public in the future or if the owner account is compromised, the severity can be lowered. However the reasons for which the sponsor found this issue interesting and worth to fix still hold.

You've created a valid escalation for 10 USDC!

To remove the escalation from consideration: Delete your comment.

You may delete or edit your escalation comment anytime before the 48-hour escalation window closes. After that, the escalation becomes final.

[0xRobocop]

Escalate for 10 USDC

I totally agree with SergeKireev, I missed that clubID is not incremented 1 by 1 but controlled by the protocol owner. But I think the severity is still low / informational since this is not exploitable unless owner makes a mistake.

[sherlock-admin]

Escalate for 10 USDC

I totally agree with SergeKireev, I missed that clubID is not incremented 1 by 1 but controlled by the protocol owner. But I think the severity is still low / informational since this is not exploitable unless owner makes a mistake.

You've created a valid escalation for 10 USDC!

To remove the escalation from consideration: Delete your comment.

You may delete or edit your escalation comment anytime before the 48-hour escalation window closes. After that, the escalation becomes final.

[ctf-sec]

Based on the escalation and other duplicate report, can be a valid medium, severity is not high

[0xRan4212]

Escalate for 10 USDC.

I disagree with the downgrade to medium, even though I had originally reported this issue with a medium severity (see my report on 209).

The sponsor considered realistic the scenario where the user can control the tokenId value, so much so that stated that after audit they will explicitly prevent it that case (see the sponsor comment on report 179).

Before the sponsor acknowledgment, as I said on my report, the exploitability was theoretical, therefore a medium severity was adequate. Basically, it violated the "attack path is possible with reasonable assumptions that mimic on-chain conditions" requirement from the high severity definition here. However, post-acknowledgment I strongly believe this requirement is now satisfied.

[sherlock-admin]

Escalate for 10 USDC.

I disagree with the downgrade to medium, even though I had originally reported this issue with a medium severity (see my report on 209).

The sponsor considered realistic the scenario where the user can control the tokenId value, so much so that stated that after audit they will explicitly prevent it that case (see the sponsor comment on report 179).

Before the sponsor acknowledgment, as I said on my report, the exploitability was theoretical, therefore a medium severity was adequate. Basically, it violated the "attack path is possible with reasonable assumptions that mimic on-chain conditions" requirement from the high severity definition here. However, post-acknowledgment I strongly believe this requirement is now satisfied.

You've created a valid escalation for 10 USDC!

To remove the escalation from consideration: Delete your comment.

You may delete or edit your escalation comment anytime before the 48-hour escalation window closes. After that, the escalation becomes final.

[hrishibhat]

Escalation accepted

Valid medium
Although the documentation mentions that user is allowed to use choose their club ID this is definitely a valid issue, however the implementation of the code still happens through an admin function, and for that reason considering this issue a valid medium.

[sherlock-admin]

Escalation accepted

Valid medium
Although the documentation mentions that user is allowed to use choose their club ID this is definitely a valid issue, however the implementation of the code still happens through an admin function, and for that reason considering this issue a valid medium.

This issue's escalations have been accepted!

Contestants' payouts and scores will be updated according to the changes made on this issue.