Checksum — fortid2026

Description

Surely you can't recover anything based on a one-byte checksum...

English summary: A Rust x86-64 ELF (checksum, rustc 1.90.0, not stripped) prints a prompt and a list of variables (FLAG, AZURE_API_KEY, DB_PASSWORD, MANS_BEST_FRIEND). It reads one variable name (not a flag candidate), computes an 8-bit checksum and prints it as two hex digits. The goal is to recover the hidden secret behind one of those names — the flag is the value of FLAG. The binary models the check as an apparently irreversible one-byte hash ("SFSN161"), but the checksum is simply the XOR of all secret bytes, and the generated call tree leaks the whole secret through its symbol names.

Analysis

What the binary actually does. checksum::main dispatches on the exact input string and calls one root function per variable:

variable	root function
FLAG	checksum_defa60ccef758e50fb2f70e838b3d36e5d1aeb71
AZURE_API_KEY	checksum_4f4800fbd67030125774d819d981e9a73dec6b37
DB_PASSWORD	checksum_d596da6220389f86c1d95ee0f64e443297c1159a
MANS_BEST_FRIEND	checksum_9b9436e07bfc893af9111c09d308c4feb1684610

There are 5030 functions named checksum::checksum_<40hex>_. Every body is trivial:

• leaf: xor byte [rdi], imm ; ret
• node: xor byte [rdi], imm ; call c1 ; [mov rdi,rbx ; call c2 ; ...] ; ret
• a few nodes use not byte [rdi] instead of xor.

So each function XORs one constant byte into *(uint8_t*)rdi and optionally calls up to five children (the children are invoked sequentially through rbx). Executing the root with [rdi] = 0 yields

checksum = XOR of every `xor imm` operand and every `not` (0xff) along the tree,
           weighted by execution multiplicity (XOR = parity).

This reproduces the four observed runtime values exactly. The value is a fixed XOR circuit; the secret is nowhere in plain memory.

The leak. The 40-hex function names look random and every naive inversion (sha1/md5/sha256 of the value, the variable name, dictionary words, child names, …) failed. The real relation is

name = sha1(f"{VAR}_{n // P}_{n % P}")     with P = 162

where n is the node's global preorder index in that variable's call tree, expanded with duplicates (a node invoked twice has two preorder positions). In other words each symbol name discloses a page index a = n // P and a slot b = n % P.

Why a page is a secret byte. With P = 162, every block of 162 consecutive preorder nodes holds random XOR shares of exactly one secret byte. Therefore

secret[i] = XOR of the constant operands of all nodes whose preorder index n satisfies n // P == i

(the tree structure only decides which shares exist; the sum over a page is the byte).

Three LLVM artefacts that must be handled when reconstructing the preorder counter purely from the names:

1. MergeFunctions folded identical leaves (xor C; ret). All 255 distinct leaf bodies exist once, so a leaf's name no longer identifies its secret slot. Leaves must take their index from the running preorder counter (i.e. their position), not from sha1.
2. Leaves with C = 0 are empty functions whose calls were deleted — they leave gaps in the preorder sequence. A gap before the next internal node contributes 0; the counter must still advance through them.
3. A few identical internal subtrees were also merged. A child whose decoded name index falls outside [counter, next_sibling_index) is a merged duplicate: it is not the real (unique) node, so it and its subtree are placed by position, like a leaf.

Control: MANS_BEST_FRIEND has runtime checksum 0x6c, which equals ord('d')^ord('o')^ord('g') — confirming both "checksum = XOR of bytes" and that a 3-char value is right for that name. Recovered values corroborate: the FLAG XOR equals the runtime 0x39; DB_PASSWORD XOR equals 0x21; MANS_BEST_FRIEND XOR equals 0x6c.

AZURE_API_KEY is a known near-miss: it comes out two bytes off because one leaf is mis-slotted at a page boundary in the name map. That artefact does not affect FLAG, whose full XOR cross-check passes.

Solution

Step 1 — build the DAG from the ELF

Parse .symtab for checksum_<40hex> names and disassemble each function (functions are contiguous, so a function ends at the next symbol). Record (ops, call_addrs) per address, then key everything by the 40-hex name so children are address-independent.

Step 2 — recover the (var, page, offset) for every name

Brute-force the four variable names against a small search space of (a, b) and match the SHA-1 hex digest to the set of symbol names. With P = 162, a in 0..63, b in 0..161 this maps 5030 / 5030 functions with zero misses.

Step 3 — walk each tree in call order and XOR shares per page

Run a preorder counter through each root (leaves advance the counter by one), accumulate acc[idx // P] ^= const(node), and emit the bytes.

#!/usr/bin/env python3
"""checksum (fortid2026) solver.

name = sha1(f"{VAR}_{n//P}_{n%P}"), n = global preorder index, P = 162.
Each page of P consecutive preorder nodes holds the XOR shares of one secret byte.
LLVM merged identical leaves (leaves indexed by position), deleted const-0 leaves
(gaps contribute 0) and merged a few identical internal subtrees (out-of-range
name index => place by position).
"""
import re, sys, hashlib
from elftools.elf.elffile import ELFFile
from capstone import Cs, CS_ARCH_X86, CS_MODE_64

BIN = "checksum"
P = 162
ENTRIES = {"FLAG": 0x6aa00, "AZURE_API_KEY": 0x52b00,
           "DB_PASSWORD": 0x5ae60, "MANS_BEST_FRIEND": 0x5c5a0}
sys.setrecursionlimit(100000)


def load(path=BIN):
    """Return addr -> (hash40, ops, call_addrs) and hash40 -> addr."""
    f = open(path, "rb")
    e = ELFFile(f)
    symtab = e.get_section_by_name(".symtab")
    text = e.get_section_by_name(".text")
    taddr, toff = text["sh_addr"], text["sh_offset"]
    f.seek(toff)
    T = f.read(text["sh_size"])

    funcs = {}
    for s in symtab.iter_symbols():
        m = re.match(r"_ZN8checksum50checksum_([0-9a-f]{40})_", s.name)
        if m:
            funcs[s["st_value"]] = m.group(1)

    md = Cs(CS_ARCH_X86, CS_MODE_64)
    info = {}
    for addr, name in funcs.items():
        end = min([a for a in funcs if a > addr] + [taddr + len(T)])
        code = T[addr - taddr: end - taddr]
        ops, calls = [], []
        for ins in md.disasm(code, addr):
            if ins.mnemonic == "xor" and "[rdi]" in ins.op_str:
                ops.append(int(ins.op_str.split(",")[-1].strip(), 16) & 0xff)
            elif ins.mnemonic == "not" and "[rdi]" in ins.op_str:
                ops.append(0xff)
            elif ins.mnemonic == "call":
                calls.append(int(ins.op_str, 16))
            elif ins.mnemonic == "ret":
                break
        info[addr] = (name, ops, calls)
    return info


def solve():
    info = load()
    addr2hash = {a: info[a][0] for a in info}
    hash2ops, hash2kids = {}, {}
    for a, (h, ops, calls) in info.items():
        hash2ops[h] = ops
        hash2kids[h] = [addr2hash[c] for c in calls]

    # --- brute-force the naming map: sha1(f"{VAR}_{a}_{b}") ---
    name2abc = {}
    for V in ENTRIES:
        for a in range(0, 64):
            for b in range(0, P):
                h = hashlib.sha1(f"{V}_{a}_{b}".encode()).hexdigest()
                if h in hash2ops:
                    name2abc[h] = (V, a, b)
    print("mapped", len(name2abc), "of", len(hash2ops), "functions")

    const = lambda h: 0 if not hash2ops[h] else __import__("functools").reduce(
        lambda x, y: x ^ y, hash2ops[h], 0)
    leaves = {h for h in hash2kids if not hash2kids[h]}
    print("leaves", len(leaves))

    for V, root_addr in ENTRIES.items():
        root = addr2hash[root_addr]
        acc, n = {}, [0]

        def walk(h, hi, forced=False):
            idx = None
            if h not in leaves and not forced and h in name2abc:
                _, a, b = name2abc[h]
                idx = a * P + b
                if not (n[0] <= idx < hi):
                    forced, idx = True, None          # LLVM-merged duplicate -> by position
            if idx is None:
                idx = n[0]
            n[0] = idx + 1
            acc[idx // P] = acc.get(idx // P, 0) ^ const(h)
            if h in leaves:
                return
            ks = hash2kids[h]
            for j, k in enumerate(ks):
                nxt = hi
                for k2 in ks[j + 1:]:
                    if k2 not in leaves and not forced and k2 in name2abc:
                        i2 = name2abc[k2][1] * P + name2abc[k2][2]
                        if n[0] < i2 < hi:
                            nxt = i2
                            break
                walk(k, nxt, forced)

        walk(root, 10 ** 9)
        secret = bytes(acc[i] for i in sorted(acc))
        print(f"{V:17s} {secret!r}   xor=0x{__import__('functools').reduce(lambda x, y: x ^ y, secret, 0):02x}")


if __name__ == "__main__":
    solve()

Step 4 — verify

For each recovered value, XOR all bytes and compare with the binary's printed checksum (e.g. run ./checksum in a linux/amd64 container and enter the variable name). The XOR of the recovered FLAG string must equal the runtime FLAG checksum 0x39; the XOR of MANS_BEST_FRIEND must equal 0x6c. Both match, so the recovery is self-consistent.

The recovered FLAG is a valid 30-character FortID{...} value: FortID{REDACTED}.

Run

pip install capstone pyelftools
python3 solve.py

Key Indicators

Use this technique when:

• A Rust (or C++) ELF contains thousands of tiny, structurally identical generated functions with random-looking 40-hex or hash-like symbol names.
• Every generated function body is a single xor byte [rdi], imm (or not), optionally followed by call operands — i.e. an input-independent constant circuit.
• The program's output is an intentionally lossy one-byte value but the names of the generated symbols encode a serial index (sha1(f"{tag}_{page}_{offset}")).
• Help text brags that a "statically generated hashing function" prevents the secret from existing in memory — a hint that the secret lives in the generated code layout.
• You must reconstruct a call-tree preorder from symbol metadata and then group nodes into fixed-size pages whose XOR equals one output byte.
• LLVM MergeFunctions / identical-code folding has removed some nodes: leaves have no meaningful names and must be indexed by position, const-0 leaves leave gaps, and duplicated internal subtrees must be detected by an out-of-range index (place by position).