💀Example Vulnerabilities
In the previous section, we discussed potential vulnerabilities that might occur due to incorrect or poor implementation of Merkle Trees in cryptographic systems. While the theory of Merkle Trees is sound, in practice, there have been instances where these vulnerabilities have been exposed, leading to security issues. In this section, we will delve into real-life scenarios where vulnerabilities arose due to improper use or implementation of Merkle Trees. These case studies will underscore the importance of secure design principles when using Merkle Trees and illuminate common pitfalls that developers should be wary of.
Example 1: OpenSea -> Merkle Tree criteria can be resolved by wrong tokenIDs
This vulnerability, at its core, arises from the mishandling of leaves in the Merkle tree construction within the smart contract. To give some context, a leaf in a Merkle tree represents the data — in this case, the tokenId — being included in the tree.
Looking at the provided function _verifyProof, the issue is that the tokenIds are directly used as the leaves of the tree, not their hashes. In other words, the actual data (the tokenId) isn't being hashed to form the leaves. Consequently, any intermediate hash value from the Merkle tree — not just the leaves — can be used to fulfil the trade, which means that a token the offerer did not specify could be used.
Let's consider an example. Alice wishes to buy an NFT with either tokenId 1 or tokenId 2. She constructs a Merkle tree with these tokenIds, and the root becomes the hash of the concatenation of 1 and 2. Alice then creates an offer using this root as the criterion.
An attacker could, however, fulfill the trade using any NFT with a tokenId that happens to be an intermediate hash value from the Merkle tree. Consequently, Alice receives a token that doesn't meet her criteria, leading to losses.
This vulnerability exploits the standard behavior of ERC-721 tokens, which allows the tokenId to be an arbitrary number, not necessarily a simple counter. ERC-721 treats the tokenId as a "black box," and doesn't require any specific pattern.
The key to resolving this vulnerability lies in hashing the tokenId to form the leaf nodes of the Merkle tree, not the tokenId itself. This can be achieved by replacing let computedHash := leaf with bytes32 computedHash = keccak256(abi.encodePacked(leaf)), thus hashing the tokenIds to form the leaves. This simple yet crucial modification ensures there can't be any collision between a leaf hash and an intermediate hash, as they result from hashing different byte lengths. Note that this fix would require changes to the off-chain process of how the Merkle tree is generated, as leaves must be hashed first.
In conclusion, this case exemplifies how a simple oversight in the implementation of a Merkle tree can lead to serious vulnerabilities, underscoring the importance of proper handling and processing of leaves in the tree structure.
Example 2: Nomad Bridge -> Bad Merkle Proofs - Included 0x0 address as a root
Understanding How Mismanagement of Trusted Roots and EVM Storage Defaults Led to a $190m DeFi Hack
The August 2022 exploit on the Nomad bridge was centered around a smart contract code vulnerability within the Replica contract. The process function in this contract is responsible for dispatching a message to its final recipient, and this can only be successful if the message has already been proven, i.e., it has been added to the Merkle tree leading to an accepted and trustworthy root.
This message check is done against the message hash using the acceptableRoot view function, which reads from the confirmed roots mapping.
During a routine upgrade in April 21st, a zero value was passed as the pre-approved committed root, which was stored into the confirmAt mapping.
This zero value was the source of the vulnerability. In the Ethereum Virtual Machine (EVM), all storage slots are initialized as zero values. This means that any unused key on a Solidity mapping will return 0x00. Therefore, when the message hash is not present in the messages mapping, 0x00 is returned, and that is passed to the acceptableRoot function.
As a result, if 0x00 has been set as a trusted root, the acceptableRoot function will return true, marking the message as processed. However, an attacker can simply change the message to create a new unused one and resubmit it.
When an attacker submits a crafted message to the process() function, a hash of the message (_messageHash) is created using the keccak() function. This hash is then used as a key to look up a corresponding value in the messages mapping.
In an Ethereum smart contract, any uninitialized storage slot, including those in mappings, will default to a value of 0x0 (a 'zero-hash'). Thus, if a hash key is not found in the messages mapping (which will be the case for a new, unique message submitted by an attacker), the default return value will be 0x0.
The acceptableRoot() function then checks if this returned value (0x0) is a 'trusted root' in the confirmAt mapping. Due to the misconfiguration during the initialization of the Replica contract, 0x0 had been inadvertently marked as a trusted root.
This means the requirement require(acceptableRoot(messages[_messageHash]), "!proven") will pass, even for the attacker's unique, unproven message, as the acceptableRoot() function erroneously returns true when it encounters the default 'zero-hash' value. As a result, the attacker's message can be processed and the funds can be unlocked, leading to the exploitation.
Among the parameters encoded in the input message is the recipient address. After the first successful transaction, anyone who understood the message format could alter the recipient address and replay the attack transaction, this time with a different message that would yield profit to a new address.
This replay-ability, coupled with the faulty zero value initialization, allowed multiple attackers to drain the funds from the bridge.
Here is the full code of the process function:
here is the full code of the initialize function
Example 3: Duplicate Claim Exploit Found in Balancer's Merkle Orchard: Understanding the Vulnerability
A deep-dive into the high-severity flaw that allowed liquidity providers to submit duplicate claims and potentially drain assets from the Balancer's Vault.
On January 22, 2023, the Balancer protocol, a renowned decentralized finance (DeFi) liquidity infrastructure provider, was alerted to a high-severity vulnerability by the white-hat hacker known as 0xriptide. This bug, if exploited, would have allowed liquidity providers to submit duplicate claims and drain the Merkle Orchard's assets from the Balancer's Vault. The vulnerability could have impacted around $3.2 million worth of funds across Ethereum mainnet, Polygon, and Arbitrum.
Despite the Merkle Orchard contract not being within the bug bounty program's scope, Balancer awarded 0xriptide a 50 ETH bounty, appreciating the importance of the finding. This demonstrates the effectiveness of Balancer's well-run bounty program with fast response times and attractive rewards, leading to such funds-saving discoveries.
The Vulnerability Breakdown
The bug was nestled in the Merkle Orchard contracts, implemented in late 2021. The main purpose of these contracts was to enable liquidity providers to claim reward distributions of multiple tokens in a single transaction. This was accomplished via calling the MerkleOrchard.claimDistributions function, which internally invokes the _processClaims function.
This function processes an array of claims. Each claim has a distributionId, from which _getIndices computes a word index and a bit index. In parallel, the _getChannelId function calculates the channel id.
If there are duplicate claims in the array, they produce the same channel id. Consequently, the function bypasses the _setClaimedBits call. This function sets bits in a bitmap to track the committed claims and prevents duplicated transactions. Therefore, duplicate claims within the array would accumulate currentClaimAmount without any bitmap checks.
The function only calls _setClaimedBits when it reaches the final element of the array, so the claim still needs to be valid and must provide a corresponding Merkle proof. At the end, the function calls manageUserBalance on Balancer’s Vault contract to send the claimed funds to the recipient.
Example 4: Binance Bridge -> flaw in the IAVL Merkle proof verification system
This flaw allowed a malicious hacker to steal 2m BNB, or about $600m USD equivalent at the time.
On October 7th, 2022, the Binance Bridge was hacked due to a flaw in the IAVL Merkle proof verification system, which allowed a malicious hacker to steal 2m BNB, or about $600m USD equivalent at the time.
Binance is a centralized exchange (CEX) that offers a wide range of services. It has two chains under its name: BNB Beacon Chain (BEP), which is used for governance, and BNB Chain (BNB), an L1 blockchain that is compatible with EVM and allows anyone to deploy and execute smart contracts on its chain.
BSC Token Hub is the bridge between BNB Beacon Chain (BEP2) and BNB Chain (BNB). It interacts with the Cross Chain contract, which allows a relayer to forward the user’s token to BSC from BEP2. It verifies the token transfer through an IAVL verification, which can be validated from payload, proofs, package sequence, height, and channel id. And if the verification is deemed successful, the token would be transferred to the user in BSC.
Merkle tree
With a Merkle tree structure, we can verify if data is included in a database without disclosing all of the data in that database by hashing its value and comparing it against the root hash of the Merkle tree.
The data in each node in the Merkle tree is a hash of each child concatenated value. If it’s a leaf node, the data is the hash value of the underlying data. So, the data in P1 is the hash of P3, and P4 (i.e P1=h(P3, P4)), and the data in P3 is the hash value of the data (i.e P3=h(data)).
To be able to verify the data against the Merkle tree, we must first know what’s the path node of the data that we want to verify. The path node is nodes that lie on the path from the leaf node to the root node of the Merkle tree. The path node essentially is a guidance node that will bring our data to reach its root node.
For example, suppose we have some data in P3, and we want to verify whether this data is included in the Merkle tree or not. First, we must hash our data to generate the P3 value. Then, we must determine the path node of P3. In this case, the path node for P3 is P4 and P2. So by providing only the P4 and P2 values, we can reach the root node. The value for P4 and P2 can be considered as the Merkle proofs of the data we have in P3. And these proofs can be used to verify the data in P3.
You might ask: why is P1 not included in the path node? This is because we can generate the P1 value ourselves by concatenating the value of P3 and P4, which is equal to the value of P1.
Naturally, one character difference in hashing will produce a completely different output. Therefore, the order of the concatenation of the node to generate the P1 or any non-leaf node is crucial. And there are multiple ways to do this ordering. In this case, we will cover the common ordering in the Merkle tree and the ordering that was used by Binance, which unfortunately led to the exploit.
Common Ordering
The common concatenation ordering for Merkle verification in the Merkle tree is done by comparing the values of its child node. If the value of the child node is bigger than the value of the other child, then it’s being concatenated to the child node that has a bigger value.
For example, node P1 has a P3 and P4 node as its child node. To get the value of P1, we must concat the P3 and P4 values and then hash the concatenated value. If the P3 value is bigger than the P4, then the ordering is (P3, P4), and if the P4 value is bigger than the P3, then the ordering is (P4, P3)
Ordering in the IAVL verification:
IAVL verification does its concatenation ordering by adding additional attributes to its path nodes. These attributes are right and left attributes. This was done to determine whether it should be hashed to the left or right side of the node.
For example, we can look at node P4 which has left attributes set to null and right attributes set to P4. This means that we can get the value P1 by hashing its child value with the P4 value as the right side of the data, or P1=H(P3, P4).
The root cause of this exploit is that the right attribute of the node was not used to calculate the root hash of the tree. Since the proof was user-controllable, the hacker was able to pass the malicious right attributes, which is the hash of the malicious payload, and the proof would be considered valid.
To consolidate:
IAVL trees are different from standard Merkle trees in that they have attributes assigned to their nodes, called "right" and "left". These attributes are used to determine how to concatenate and hash node values. If the node has a "right" attribute, it is hashed to the right side of its child node value. For example, if node P4 has its "right" attribute set to P4 and "left" attribute set to null, to obtain the value of P1, you hash the value of child node P3 with the value of P4 as the right-side data.
The exploit described here is based on the fact that user-controlled "proof" data was not correctly validating the "right" attribute of a node when calculating the root hash of the tree. Essentially, the "right" attribute was not being properly checked or validated, allowing an attacker to provide a malicious "right" attribute. Because the verification code did not properly check this value, the malicious proof was accepted as valid.
But how does faking the right side give a valid root?
In the case of this exploit, it seems that the attacker was able to manipulate the proof in such a way that the calculated root from the malicious proof matched the expected root, even though the malicious data was inserted into the proof.
Remember, the proof is essentially a series of hashes and metadata that allow anyone to verify that a specific piece of data is part of the tree without seeing the entire tree.
In a correctly functioning system, any change to the data (or the proof) should cause the calculated root to differ from the expected root, making the proof invalid.
However, the bug in the IAVL tree was that it did not properly verify the "right" attribute during the proof verification. The "right" attribute specifies which side (left or right) a node should be hashed with its sibling.
In this exploit, the attacker manipulated the proof's "right" attribute to insert their malicious payload into the proof. Because of the bug, this manipulation wasn't caught during verification, and the calculated root from the manipulated proof ended up matching the expected root, thus making the proof appear valid.
So in this case both the root has and the right side of the tree isn't being verified?
Yes, according to the vulnerability discussed in the patent, it seems both the right side of the tree and the root hash are not being properly validated in this flawed implementation.
Normally, the right side should be verified. In a correctly implemented Merkle tree, each leaf node (transaction data) is hashed and then these hashes are paired and hashed again. This process is repeated up to the root node. If any of the transaction data is changed, it would change the hash of that leaf node, which would then change the hash of the parent node, and so on, up to the root node. Therefore, any change in the tree (left or right) should cause the root hash to change.
Moreover, the root hash should also be verified. It's the ultimate proof of the integrity of all the transaction data in the tree. If all data is unchanged, the root hash should match the expected value. If any data is tampered with, the root hash would change, and this change would signal the tampering.
However, according to the patent, in this flawed implementation, the system isn't checking the right side or recalculating and validating the root hash after the left side is verified. This means an attacker can substitute a different right half of the tree, and the system doesn't notice because it isn't checking the right half or the root hash again. The system continues to operate under the assumption that the root hash is still valid, even though the tree has been tampered with.
Please refer to this article for a full proof of concept:
Last updated
