Writeup · 31 Nights of Root

Sediment

miscmediumsolvedFlag: r00t{REDACTED}

Overview

“Can you get the sedimented remains?”

The challenge ships a tiny paged binary database (rocks.db) and a pile of helpers. The flag is hidden as one byte per page, spread over a linked chain of pages, with some pages deliberately corrupted so the bytes have to be repaired from “sibling” pages.

The twist: almost everything documented is a decoy.

File Role Trustworthy?
db_schema.txt Documents the page format No, wrong offsets and wrong repair rule
page_reader.py Reader implementing the doc No, its own comments say TRAP and wrong
index_map.bin 14 × 8-byte records No, a red herring, sediment never opens it
validator Flag checker No, hardcoded decoy string
sediment Computes the real 12 bytes from rocks.db Yes, ground truth
check Flag checker Yes

Prerequisites / Setup

  • Python 3 (struct, hashlib)
  • rocks.db, sediment, check in the working directory

Recon

Step 1 — First look at the files

Goal: List the files and confirm types.

ls
# check  db_schema.txt  index_map.bin  page_reader.py  rocks.db  sediment  validator

file rocks.db            # data
checksec --file=sediment # PIE, NX, no canary, stripped

rocks.db is 7168 bytes = 14 pages × 512. Dumping the header fields of every page (file order, not id order):

import struct
raw = open("rocks.db", "rb").read()
for i in range(len(raw) // 512):
    c = raw[i*512:(i+1)*512]
    print(i, struct.unpack_from("<HBHHHHH", c, 0))

Page ids present: 0..11 and 20, 21. Ids 12/13 (which index_map.bin mentions) do not exist, a first hint that the index map is junk.

Step 2 — Run the shipped tooling

Goal: Confirm which binaries are verifiers vs. flag printers.

echo test | ./check       # INCORRECT
echo test | ./validator   # INCORRECT
./sediment rocks.db       # blocks / prints "need 12 bytes"

sediment reads 12 bytes from stdin, so it is a verifier, not a flag printer. It exits 0 only when stdin equals the 12 bytes it derives from rocks.db.

Step 3 — Read the documented format (decoy)

Goal: See what the docs claim, so you know what to disbelieve.

db_schema.txt claims:

offset 0:2  page_id
offset 2    data_byte
offset 3:5  crc16([pid_lo, pid_hi, data_byte])
offset 5:7  next_id        <- "use this to traverse"
offset 7:9  sibling_id     <- "only ONE sibling"
offset 9:11 reserved, ignore
repair: data ^ sibling.data

Following that (what page_reader.py does) goes wrong in two ways: page 3’s “next” at offset 5 points into the false branch (page 20), so the walk stops after 6 bytes, and the single-sibling XOR gives wrong repairs. The resulting candidate flag is rejected.

Exploitation

Step 4 — Reverse sediment

Goal: Recover the real parsing logic from the disassembly.

Disassembling sediment (objdump -d -M intel) shows the real logic. The key observations, in order of the function:

  1. fopen(argv[1]), then fread up to 0x40 pages of 0x200 bytes into a stack buffer.

  2. A 64K-entry table (memset to 0xFF, then filled) maps page_id -> physical index, read from the uint16 at the start of each page.

  3. The walk starts at the physical index of page id 0.

  4. For each page it computes a table-driven CRC16 over [pid_lo, pid_hi, data] (xor/bit-reverse/lookup table in .rodata, standard CRC-16/MODBUS) and compares it to the uint16 at +3.

  5. On mismatch it loads two sibling ids, uint16 at +7 and uint16 at +0xB, looks both pages up, and does:

    data ^= sib1.data ^ sib2.data
  6. The next id is the uint16 at +9 (not +5). The loop ends when it is 0xFFFF (or after 12 bytes).

  7. Finally fread(stdin, 12) and memcmp against the derived bytes. Return 0 on match.

So the real layout is:

0:2   page_id
2     data_byte
3:5   crc16  (MODBUS)
5:7   DECOY next_id  (points into 20/21 false branch)
7:9   sibling #1
9:11  next_id   <-- real chain pointer
11:13 sibling #2

Step 5 — Recover the real chain

Goal: Parse the page graph with the corrected layout.

Parsed with the corrected layout, the page graph looks like this (ok = CRC valid, bad = needs repair):

Page id CRC next sib1 sib2
0 ok 1 20 21
1 bad 2 9 20
2 ok 3 20 21
3 ok 4 20 21
4 bad 5 6 20
5 bad 6 0 3
6 ok 7 20 21
7 bad 8 10 8
8 ok 9 20 21
9 ok 10 20 21
10 ok 11 20 21
11 bad 0xFFFF 2 10
20 ok 21 decoy branch
21 ok 0xFFFF decoy branch
flowchart LR
    P0 --> P1 --> P2 --> P3 --> P4 --> P5 --> P6 --> P7 --> P8 --> P9 --> P10 --> P11 --> END([0xFFFF])
    P3 -. decoy next @+5 .-> P20 --> P21

Note how sibling ids 20/21 on healthy pages are just filler; only the five bad pages use their siblings meaningfully.

Step 6 — Re-implement the real parser

Goal: Recover the 12 bytes and validate with sediment.

import struct, hashlib

def crc16(data):
    crc = 0xFFFF
    for b in data:
        crc ^= b
        for _ in range(8):
            crc = (crc >> 1) ^ 0xA001 if crc & 1 else crc >> 1
    return crc & 0xFFFF

raw = open("rocks.db", "rb").read()
pages = {}
for i in range(len(raw) // 512):
    c = raw[i*512:(i+1)*512]
    pid = struct.unpack_from("<H", c, 0)[0]
    pages[pid] = dict(
        data=c[2],
        csum=struct.unpack_from("<H", c, 3)[0],
        sib1=struct.unpack_from("<H", c, 7)[0],
        next=struct.unpack_from("<H", c, 9)[0],    # real next
        sib2=struct.unpack_from("<H", c, 11)[0],   # second sibling
    )

out, cur = bytearray(), 0
while cur != 0xFFFF and cur in pages:
    p = pages[cur]
    if crc16(bytes([cur & 255, cur >> 8, p["data"]])) == p["csum"]:
        v = p["data"]
    else:
        v = p["data"] ^ pages[p["sib1"]]["data"] ^ pages[p["sib2"]]["data"]
    out.append(v)
    cur = p["next"]

The walk yields 12 bytes (pages 0 → 11), five of which needed repair (pages 1, 4, 5, 7, 11). The first bytes are 486c0496… (remainder redacted).

Step 7 — Validate against the oracle

Goal: Confirm the re-implementation is bit-exact.

python3 -c "import sys; sys.stdout.buffer.write(bytes.fromhex('<12 recovered bytes>'))" \
  | ./sediment rocks.db
echo $?     # 0  -> bytes match the binary's own computation

Exit code 0 confirms the re-implementation is bit-exact (CRC variant, two-sibling XOR, offset-9 chain).

Step 8 — Turn the bytes into the flag

Goal: Hash the 12 bytes and format the flag.

The 12 recovered bytes are not printable text. The only wrapper hinted anywhere is in page_reader.py (r00t{s3d1m3nt_<sha256[:24]>}), which is wrong in its inputs but right in its output format. Hashing the correct bytes with it:

flag = "r00t{s3d1m3nt_%s}" % hashlib.sha256(bytes(out)).hexdigest()[:24]

Step 9 — Confirm with check

Goal: Verify the flag with the real checker.

check XOR-decodes a hardcoded string with 0x5c and strcmps it against one line of stdin. Statically decoding it yields the same string produced in Step 8:

echo 'r00t{REDACTED}' | ./check
# CORRECT

validator, by contrast, embeds a different string that decodes to a wr0ng_0rd3r placeholder, so it rejects the real flag. It is a decoy (a nod to the bogus chain order implied by index_map.bin).

Solver script

The full automated solver is in sediment_solver.py:

python3 sediment_solver.py rocks.db --verify --show-decoy
  • --show-decoy also runs the db_schema.txt method to show the wrong candidate.
  • --verify pipes the recovered bytes into ./sediment (expects rc=0) and the flag into ./check (expects CORRECT).

Flag

r00t{REDACTED}

Derived as r00t{s3d1m3nt_<first 24 hex of SHA-256 over the 12 recovered bytes>}.

Lessons / Takeaways

  • Documentation and “helper” scripts in a challenge are part of the puzzle. Comments like # TRAP offset and # wrong: only XOR one sibling are the author telling you to go find the truth in the binary. When a doc says “ignore this field”, check whether the binary reads it.
  • Use the binary as an oracle. sediment’s memcmp against stdin lets you check a re-implementation in one shot (exit code 0), without needing to fully understand every instruction.
  • Don’t reverse what you can fingerprint. The table-driven bit-reversal CRC in the disassembly is just CRC-16/MODBUS; testing the standard routine against the stored checksums confirmed it instantly (9 of 14 pages validate, the 5 failures are the corrupted ones).
  • Count your fields. 512-byte pages with an 11-byte “header” and “padding” after it: the real header was 13 bytes. Probing the “padding” for non-zero data exposed the extra next/sibling fields.
  • Multiple decoy layers. Wrong doc, wrong reader, wrong index map, wrong validator. Prefer the one artefact that actually executes the logic.
  • Watch for blocking binaries. A tool that reads stdin will hang an unattended shell; always wrap with timeout and < /dev/null.

Techniques

  • Reverse Engineering
  • Custom File Format Parsing
  • CRC16 Checksums
  • XOR Obfuscation
  • Decoy Analysis

References