CUSTOMMediumReversing

Braindead

XESXOR9/10/20264 min read

#reversing#custom#medium#block_by_block_execution#brainfuck_interpretation#score_guided_bruteforce

Braindead

Platform: spbctf | Category: Reversing | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-08 | Status: Solved Techniques: block_by_block_execution, brainfuck_interpretation, score_guided_bruteforce

Summary

Task: the challenge provides a Brainfuck source file that prints a prompt and validates a 32-byte flag instead of revealing it directly. Solution: run the program with a small interpreter, recover immediate-check positions block by block around each comma, then brute-force delayed positions by maximizing the final internal score cell.

Braindead — spbctf

Description

Reverse this: https://rev-kids20.forkbomb.ru/files/rev/newX/braindead.brainfuck

The artifact is a Brainfuck program, braindead.brainfuck. It does not print the flag directly: it prints a prompt, reads user input, and validates a 32-byte candidate.

Analysis

The title is a strong hint that the source itself is the target. Running the Brainfuck program with any simple interpreter shows the prompt:

 text read-only • copy allowed
-=&# BRAINDEAD #&=-   waaaaaahh
Enter flag to check:

Static inspection and dynamic execution show 32 input operations, so the checker expects a 32-byte flag. ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

The useful trick is that the program can be split at each , instruction:

execute until the first input,
feed one byte,
continue until the next input,
inspect memory,
repeat.

Many positions are checked immediately. When a tested byte is correct, the program increments an internal success counter right away, so those characters can be recovered independently.

Not every position is local, though. Some bytes only influence later logic, so they cannot be identified from the next block alone. For those delayed checks, the easiest approach is to keep the already recovered prefix, try candidates for the unknown position, run the full program, and pick the value that maximizes the final internal score stored in cell11. ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

This avoids fully decompiling the Brainfuck into higher-level code. The challenge is a deterministic checker, and interpreter-assisted probing is enough to reconstruct the accepted input.

Solution

Load braindead.brainfuck into a tiny Brainfuck interpreter.
Run until the first , to confirm it prints the prompt.
Split execution into blocks between consecutive input instructions.
For each position, test printable candidates and watch whether the success counter increases immediately.
Recover the delayed/non-local positions by running the whole program and maximizing the final score in cell11.
Verify the full 32-byte input against the checker. ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

 python read-only • copy allowed
#!/usr/bin/env python3
from string import printable

CODE = open("braindead.brainfuck", "r", encoding="utf-8").read()
ALPHABET = [ord(c) for c in printable if c not in "\r\n\x0b\x0c"]
FLAG_LEN = 32
SCORE_CELL = 11


def build_jumps(code):
    st, mp = [], {}
    for i, ch in enumerate(code):
        if ch == '[':
            st.append(i)
        elif ch == ']':
            j = st.pop()
            mp[i] = j
            mp[j] = i
    return mp


JUMPS = build_jumps(CODE)


class BF:
    def __init__(self, code, data=None):
        self.code = code
        self.ip = 0
        self.dp = 0
        self.mem = [0] * 4096
        self.out = []
        self.jumps = JUMPS
        if data:
            for i, b in enumerate(data):
                self.mem[i] = b
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

    def step(self, inp=None):
        ch = self.code[self.ip]
        if ch == '>':
            self.dp += 1
        elif ch == '<':
            self.dp -= 1
        elif ch == '+':
            self.mem[self.dp] = (self.mem[self.dp] + 1) & 0xff
        elif ch == '-':
            self.mem[self.dp] = (self.mem[self.dp] - 1) & 0xff
        elif ch == '.':
            self.out.append(self.mem[self.dp])
        elif ch == ',':
            if inp is None:
                return False
            self.mem[self.dp] = inp & 0xff
        elif ch == '[' and self.mem[self.dp] == 0:
            self.ip = self.jumps[self.ip]
        elif ch == ']' and self.mem[self.dp] != 0:
            self.ip = self.jumps[self.ip]
        self.ip += 1
        return True
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

    def run_until_input(self):
        while self.ip < len(self.code):
            if self.code[self.ip] == ',':
                return True
            self.step()
        return False

    def run_block(self, byte):
        assert self.code[self.ip] == ','
        self.step(byte)
        while self.ip < len(self.code) and self.code[self.ip] != ',':
            self.step()
        return self.mem[:]

    def run_all(self, data):
        inp_i = 0
        while self.ip < len(self.code):
            if self.code[self.ip] == ',':
                self.step(data[inp_i])
                inp_i += 1
            else:
                self.step()
        return self.mem[:], bytes(self.out)
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍


def recover_immediate_positions():
    vm = BF(CODE)
    vm.run_until_input()
    guess = [ord('?')] * FLAG_LEN
    fixed = {}
    prev_score = vm.mem[SCORE_CELL]

    for pos in range(FLAG_LEN):
        best = None
        for c in ALPHABET:
            test = BF(CODE, vm.mem)
            test.ip, test.dp = vm.ip, vm.dp
            mem = test.run_block(c)
            if mem[SCORE_CELL] > prev_score:
                best = c
                prev_score = mem[SCORE_CELL]
                vm = test
                break
        if best is None:
            vm.run_block(ord('?'))
        else:
            guess[pos] = best
            fixed[pos] = best
    return guess, fixed
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍


def final_score(candidate):
    mem, _ = BF(CODE).run_all(candidate)
    return mem[SCORE_CELL]


def solve():
    guess, fixed = recover_immediate_positions()

    for pos in range(FLAG_LEN):
        if pos in fixed:
            continue
        best_c, best_score = None, -1
        for c in ALPHABET:
            candidate = guess[:]
            candidate[pos] = c
            score = final_score(candidate)
            if score > best_score:
                best_c, best_score = c, score
        guess[pos] = best_c
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

    flag = bytes(guess).decode()
    print(flag)


if __name__ == "__main__":
    solve()

Recovered and verified flag:

 text read-only • copy allowed
spbctf{REDACTED}

‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍