# 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

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

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:

Thanks a lot for the write-up!

I'm having trouble understanding how the attack works in detail, though.

The problem is that I can't make sense of the example. First of all, in the first diagram, it says that left = nil but there is a left tree. What does that mean?

Also, the example should have 4 leaves but I can only see 2. Where are the other 2?

I think it would help if you provided a minimal example of a complete tree and the changes made during the attack.