We have analyzed the attack flow and traced the stolen funds of the recent $850 million BNB Chain exploit in our last article. How did the attacker insert the attack payload and pass the verification of IAVL proof? Here’s what we found.

When BSC cross-chains with BNB Beacon Chain, BSC will use the pre-compiled contract 0x65 to submit the IAVL tree’s proof to BNB Beacon Chain for verification. The root cause of the exploit in this case lies in the proof.

Structure of IAVL tree

IAVL tree is also known as “Immutable AVL” tree. In the IAVL tree, the leaf nodes and intermediate nodes have the same data structure, the difference lies in the value of specific fields in the nodes.

For a leaf node, the size field is always 1, the height field is always 0, and the value field really stores the value of the corresponding key, while the fields about the left and right children are nil.

For intermediate nodes, the size field is greater than 1, the height field is greater than 0, the value field is empty, and the key field is equal to the minimum value of the key of the node in its right subtree.

The key values of the leaf nodes are increasing in the order from left to right. The middle node stores the minimum value of the key of the leaf node of the right subtree.

In the figure below, the number in each node indicates the key key field of that node.

Source: longcpp Github

Although leaf nodes and intermediate nodes reuse the same data structure Node, the hash calculation process of the two nodes is different due to the difference in field values:

•Calculating leaf node hash: Hash(height||size||version||key||Hash(value))

•Calculating intermediate node hash: Hash(height||size||version||leftHash||rightHash)

Merkle proof of IAVL tree

By adding the hash values of the left and right child nodes to the Node structure, the existence proof can be made for the values corresponding to the keys stored in the IAVL tree. A non-existence proof can also be constructed if there is no corresponding key-value pair in the tree. Since only the leaf nodes in the IAVL tree store values, the proof of existence for a key-value pair is the path from the root of the tree to the corresponding leaf node. To verify, it is only necessary to compute the hash value from the leaf nodes layer by layer and compare the final hash value with the known hash value of the root node, if it is equal, it proves that the key-value pair does exist in the tree.

The following is the structure of the RangeProof

Where PathToLeaf is an array of ProofInnerNode defined in the file iavl/proof_path.go, indicating the path from the root node to some leaf node, excluding leaf nodes, and proofInnerNode is a structure defined in the file iavl/proof.go, including only in the hash value calculation of the field values of the intermediate nodes involved in the process. The file also defines the structure proofLeafNode, as the height and size fields of the leaf nodes are fixed values that need to be included in the structure. And the ValueHash in it is the hash of the value stored in the leaf node.

However, a vulnerability occurs in cosmos’ IAVL proof.go implementation.

In the code below, you can see that in line 79, when pin.Left is empty, the value of pin.Right is calculated, while in line 88, when pin.Left is not empty, only the value of pin.Left is calculated, without considering whether the value of pin.Right is empty or not, and the case of not being empty is not involved in the hash calculation. When implemented, only the left child node pin.Left or the right child node pin.Right exists by default, and does not take into account the case where both exist. This results in the attacker constructing pin.Right with the attack load if pin.Left is not empty, i.e., a new leaf node is added, which is not involved in the rootHash calculation.

Also, in order to satisfy the checksum between InnerNode and leaves, the attacker adds an empty InnerNode node after adding the leaf node.

Ultimately, this allows the generation of new proof while keeping the rootHash unchanged.

For this, we find the original transaction on the BSC with the same block height of 110217401 as on the BNB Beacon Chain.

https://bscscan.com/tx/0x79575ff791606ef2c7d69f430d1fee1c25ef8d56275da94e6ac49c9c4cc5f433

Comparing the proof of the original transaction with the proof after the attack, we can see that the size of the proof is similar, and the proof constructed by the attacker does have an additional set of information than the original proof.

Vulnerability Fixed

BSC VM code was updated and a blacklist is added.

The vulnerability is fixed in Cosmos’ IAVL proof.go: when both pin.Left and pin.Right are not empty at the same time, an error is returned.

Through this incident, we note that cross-chain bridges are often prone to vulnerabilities in coding implementation because of the complexity of the business and the large amount of code; at the same time, the security of third-party components used by the project is also one of the important reasons for security vulnerabilities.

Beosin recommends that

1）When using third-party components in the core code of the project, a detailed security check should be conducted or a professional security team should be invited to review it.

2）Projects are recommended to conduct a complete security audit before the project goes live.

References:

https://github.com/longcpp/CryptoInAction/blob/master/cosmos-coinex/iavl.md

Contact

If you have need any blockchain security services, please contact us:

Website Email Official Twitter Alert Telegram LinkedIn