Binance Chain Bridge Exploitation Writeup - Part 1

Binance Chain was hacked with almost $600M of asset value with roughly $90M being moved out of the Binance ecosystem. In this writeup, we write an analysis of the exploit used and suggest fixes.

by Verichains Team 

On October 7th 2022, Binance Chain was hacked with almost $600M of asset value with roughly $90M being moved out of the Binance ecosystem. The hack was triggered in a transaction where the Binance Bridge sends out a large portion of BNB native.

We came to know about the bridge hack a bit late after we woke up in the morning. Our team then started to investigate on the root cause of the hack and figured out how the exploit worked after 2 hours of looking into implementation of the related codes. The write up was then sent to Binance dev team and we are working with the team on reviewing the fixes.

We should note that the exploit is not exclusive on Binance Chain. The hacker exploited the IAVL Proof bug in the Tendermint Core and any projects using Cosmos library with IAVL merkle proof system is all subjected to the attack.

Preliminary

BC to BSC cross-chain communication is based on the light client technique. A smart contract is deployed on BSC to track the consensus state of BC including the appHash (analogous to stateRoot of Ethereum), which is essentially a root of a verifiable key-value store implemented as an AVL tree. Messages coming from BC will be verified against the appHash so their integrity can be guaranteed.

The store allows consecutive key-value pairs to be proved in batch (better in performance than proving each one individually). However its range proof verification logic contains a critical bug that can be exploited to prove membership of arbitrary key-value pairs chosen by the attacker.

IAVl Proof

The attacker exploited the range proof of IAVL Proof (similar to Merkle Proof). A valid transaction must submit the proof containing a verification path, a list of leaves and a list of InnerNodes. A transaction is verified if

1. the root hash (calculated from the proof) is equal to the root hash on the chain.

2. all recursive checks are valid

A verification path is an array with two fields (left, right) each of them is 32 bytes. Leaf is hash-able, InnerNodes are similar to verification paths but for recursive checks.

We now learn how to calculate root hash from a path and leaf.

The root is calculated by hashing repeatedly (just like in Merkle proof) as in the pseudocode below:

https://github.com/cosmos/iavl/blob/6c1300ae54a9bb851e77dbcc4ba4b21832279027/proof_path.go#L70

https://github.com/cosmos/iavl/blob/6c1300ae54a9bb851e77dbcc4ba4b21832279027/proof.go#L79

Readers may have already seen the buggy logic here: "What would happen if both left and right exist?". If both left and right exist, the digest will ignore the right field. Because of this, if the verification path contains all items with both left and right, the root is unchanged with any arbitrary right values (using the same leaf). This is one factor to be exploited.

Another factor lies in the recursive checks. Let's start explaining from the start of the verification routine.

Assuming we have a tree containing 4 leaves, leaf 1, leaf 2, leaf 3, leaf 4. And we want to make a range proof for leaf 2 and leaf 3. It starts by calculating the root. After that, it goes up from leaf 2 until right exists and starts recursively calculating the root hash of the tree whose root is right. In the illustration, A.right holds the root of the new tree containing leaf 3. For leaf 3, it calculates the root hash and validates only if it's equal to A.right.

So what could go wrong in these recursive checks? It's not wrong on its own. But if we combine this with the above factor where right values are completely unused when calculating root hash, it becomes a serious issue and makes the attack possible.

The bug

For any proof, by keeping the left values in verification path and a genuine first leaf, we can inject a leaf node that satisfies the verification as long as we have a recursive check with an InnerNodes equals right value at some point in the verification path. As stated above, the root is unchanged when right values are changed. So we can change right values that satisfy the new leaf inserted. In the attacker payload, they used InnerNodes = {}[nil]. This is to make the right value easier to modify as the root hash for the InnerNodes, leaf is hash(leaf).

Suggestion for fixes

The easiest fix is to drop all proofs consisting of any item where both left and right values exist. The assertion should only qualify either (nil, right) or (left, nil). Alternatively, the design could be changed to use up all left and right values to produce root hash.

https://github.com/cosmos/iavl/blob/6c1300ae54a9bb851e77dbcc4ba4b21832279027/proof.go#L64

Conclusion

The hack to the Binance Chain is another devastating loss to the chain developers and Binance. It is even more dangerous that the exploited bug is in the Tendermint Core, used in many projects in the Cosmos ecosystem. We suggest all projects using Cosmos library with IAVL merkle proof system do a rough check and apply the fix to prevent n-day attack.

Part 2:

Binance Chain Bridge Exploitation Writeup - Part 2