TetCTF 2024: adapt

TetCTF comes back with their great crypto challenges. I played with @blackb6a and we ended up securing the 🥉 third place. In this blog post, I will walk through adapt, a challenge which required us to make fake proofs in an IAVL tree implementation. There are only three solves during the contest period.

Challenge Summary⌗

We are started with an empty immutable AVL (IAVL) tree every connection. We can send up to 2024 messages and it will store the key-value pair (message, "") to the tree. In this stage, we have to set the message to $m_0$ at least once. After that, we are asked to provide a proof that $m_0$ is not on the tree.

Solution⌗

Part I: Background⌗

cosmos/iavl@v0.19.2 is known to be vulnerable¹² for the Binance Bridge hack in October 2022, which has been fixed in v0.19.3. However, there is a issue in ≤v0.19.7 that allow us to create fake absence proofs.

Part II: Attack overview⌗

In short, the vulnerability appears because of the below reasons:

1. similarity between serialization of parent nodes and leaf nodes, and
2. missing checks to heights for parent nodes.

We then can create malicious leaf nodes that appeared to be parent nodes, and use that node to generate range proofs to show that an key is absent from the tree.

We now present an example where we assume that there is a single node (namely 🚩) in the IAVL tree. The objective is to supply a proof that 🚩 is absent.

What we do is to insert a single malicious node to the left of the IAVL tree, here 😈 needs to lexicographically smaller than 🚩 so that the malicious node is placed to the left of 🚩:

This malicious node is disguised as a parent node with two child nodes, 👻 and 📁, when supplied as a proof. We require 👻 to be lexicographically greater than 🚩. If we generate a range proof containing 👻 as the only node, we can tell that 👻 is the leftmost element in the IAVL tree. With that said, there are no keys in $(-\infty, 👻)$. Given that $🚩 \in (-\infty, 👻)$, the verifier is convinced that 🚩 is absent.

Part III: Implementation details⌗

Computing a node hash of IAVL trees⌗

There will be a hash for each node in IAVL trees. The parent and leaf nodes use different material to compute the hashes as defined in writeHashBytes in node.go:

• Parent node: SHA256(height || size || version || leftHash || rightHash)
• Leaf node: SHA256(height || size || version || key || valueHash)

Here height, size and version are integers and the remaining are bytes. They are uniquely encoded so that no two parent nodes (resp. leaf nodes) could end up having the same node hash.

For the below node with key being hello and value being the empty string, we have the digest being addee74d....

hashlib.sha256(bytes.fromhex(
    '00' + # height=0
    '02' + # size=1
    '02' + # version=1
    '05 68656c6c6f' + # key=hello
    '20 e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855' # SHA256(value)
)).hexdigest()
# addee74d6c7b968206e8072eb5147e48dc14d1ab78dceb3a352b1e6fa144fc4f

Now proceed to a tree. From above, we know that the digests of the left and right child nodes are respectively addee74d... and bdfd061f....

With that, we can compute the digest of 📂:

hashlib.sha256(bytes.fromhex(
    '02' + # height=1
    '04' + # size=2
    '02' + # version=1
    '20 addee74d6c7b968206e8072eb5147e48dc14d1ab78dceb3a352b1e6fa144fc4f' +
    '20 bdfd061f8989347217253be5a7ef06117d2be62fc6dde0d9752a5debc902f011'
)).hexdigest()
# 166c299760ef7b1e27116893a2623e38a8b3c763b831568eac46138527553bc5

It would be theoretically infeasible to find two trees that yield the same node hash for the root node. Therefore we can use root node hashes to determine the integrity of IAVL trees.

Range proofs⌗

The leaf nodes of IAVL trees are sorted. If node A is lexicographically smaller than node B, we will see node A is on the left of node B. With this property, we are able to reveal a subtree of consecutive leaf nodes to show the absence of a given node.

We can imagine that we have a sorted array. If $a < x < b$, by showing a contiguous subarray [a, b] we can prove that x does not exist in the array. Now you have to convince the verifier that [a, b] is a subarray, and it is contiguous.

By having a IAVL tree, the verifier only have to maintain the digest of the root nodes to verify proofs. For more details, please read the documentation on proofs in cosmos/iavl.

Part IV: Shaping the attack⌗

As mentioned before, the entire attack involves three leaf nodes: 🚩, 😈 and 👻. We assume that 🚩 is already in the tree and will only insert 😈 to it. The values are always empty in the challenge and we can’t alter them.

We will first find the key of 👻. It has to be lexicographically greater than 🚩, and its node hash is lexicographically smaller than 🚩 at the same time.

In our case, the keys for 🚩 and 👻 are Please give me flag and QQR respectively. The node hash for 👻 is 22220311... hex-encoded.

Now we can simply use the hex-encoded 22220311... as the key for 😈, and insert it to the tree. Now there are two nodes in our tree.

In the proof, we can disguise 😈 as a parent node with 👻 being its left child. We then reveal the below subtree to the verifier:

And finally the verifier is convinced that 🚩 is not in the tree.

Below is the equivalent proof that I sent to the verifier, and eventually I got the flag – TetCTF{l34f_c0ns3cut1v3n3ss_n0t_3nf0rc3d}:

{
    "left_path": [
        {
            "height": 1,
            "size": 2,
            "version": 1,
            "right": "pvscYKxyFDUPxP0R6qEYaAMYdJC4G2VXKhgJAuAh4So="
        },
        {
            "height": 0,
            "size": 1,
            "version": 1,
            "right": "47DEQpj8HBSa+/TImW+5JCeuQeRkm5NMpJWZG3hSuFU="
        }
    ],
    "inner_nodes": [],
    "leaves": [
        {
            "key": "515152",
            "value": "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",
            "version": 1
        }
    ]
}