Brainfuck encoding

Why This Matters

Brainfuck is an esoteric programming language created by Urban Müller in 1993, designed to be a minimal Turing-complete language using only eight single-character commands. In CTF challenges it functions as an obfuscation layer: a Brainfuck program that outputs the flag looks like random punctuation to the uninitiated, but is trivially executed by any Brainfuck interpreter. The language also appears in malware samples where it is used to obfuscate payload generation logic, and in challenge chains where Brainfuck output feeds into a subsequent encoding layer. Beyond direct execution, CTF analysts sometimes need to read Brainfuck programs analytically — understanding what a program does without running it — to solve challenges that ask about the computation rather than just the output.

Core Concept

Brainfuck operates on a memory tape of cells (typically 30,000 bytes) initialised to zero, with a data pointer that starts at cell 0 and an instruction pointer that traverses the program. The eight commands are: > (move pointer right), < (move pointer left), + (increment current cell), - (decrement current cell), . (output current cell as ASCII character), , (read one byte of input into current cell), [ (if current cell is zero, jump to matching ]), ] (if current cell is non-zero, jump back to matching [). Every other character in the source is a comment and is ignored during execution.

The recognition signature is highly reliable: a Brainfuck program contains only the characters >, <, +, -, ., ,, [, ], and whitespace. Any string composed exclusively of these characters (with at least a few + and .) is almost certainly Brainfuck. The related language Ook! translates word-for-word to Brainfuck (Ook. Ook. = >, Ook! Ook! = <, etc.) and appears in themed challenges.

Technical Deep-Dive

def run_brainfuck(code: str, stdin: str = "") -> str:
    tape = [0] * 30000
    ptr = 0
    ip = 0
    output = []
    input_pos = 0
    prog = [c for c in code if c in "><+-.,[]"]

    # Pre-compute bracket pairs for O(1) jumps
    bracket_map = {}
    stack = []
    for i, c in enumerate(prog):
        if c == "[":
            stack.append(i)
        elif c == "]":
            j = stack.pop()
            bracket_map[i] = j
            bracket_map[j] = i

    while ip < len(prog):
        c = prog[ip]
        if   c == ">": ptr += 1
        elif c == "<": ptr -= 1
        elif c == "+": tape[ptr] = (tape[ptr] + 1) & 0xFF
        elif c == "-": tape[ptr] = (tape[ptr] - 1) & 0xFF
        elif c == ".": output.append(chr(tape[ptr]))
        elif c == ",":
            tape[ptr] = ord(stdin[input_pos]) if input_pos < len(stdin) else 0
            input_pos += 1
        elif c == "[" and tape[ptr] == 0: ip = bracket_map[ip]
        elif c == "]" and tape[ptr] != 0: ip = bracket_map[ip]
        ip += 1

    return "".join(output)

# Usage
bf_code = "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++."
print(run_brainfuck(bf_code))  # Hello (first few chars of "Hello World")

ook_to_bf_map = {
    "Ook. Ook.": ">",
    "Ook! Ook!": "<",
    "Ook. Ook?": "+",
    "Ook? Ook.": "-",
    "Ook! Ook.": ".",
    "Ook. Ook!": ",",
    "Ook! Ook?": "[",
    "Ook? Ook!": "]"
}

# Online Brainfuck interpreters:
#   copy.sh/brainfuck   — paste code, see output
#   tio.run             — supports Brainfuck + input
#   dcode.fr            — "Brainfuck" interpreter

# Python package
pip install brainfuck
python3 -c "import brainfuck; brainfuck.evaluate(open('prog.bf').read())"

Analytical Methodology

1. Confirm the character set. If the input consists only of >, <, +, -, ., ,, [, ], and whitespace, it is Brainfuck (or a closely related esoteric language). No further identification is needed — execute it immediately.
2. Identify the language variant. Check for Ook! (uses "Ook." and "Ook!" words), Whitespace (uses only space, tab, newline), or COW (uses "moo" variants). These are all structurally equivalent to Brainfuck and translate directly before execution.
3. Determine if input is required. Count commas (, command). Zero commas means the program requires no input and will produce deterministic output. Non-zero commas means you need to supply input — check challenge context for what to provide.
4. Execute using a trusted interpreter. Use copy.sh/brainfuck, tio.run, or the Python implementation above. Do not attempt to trace mentally except for very short programs.
5. Check output format. Brainfuck output via . is ASCII characters. If output is not printable text, the program may be outputting binary data (values outside 0x20–0x7E) which feeds into a further decoding step.
6. Estimate output length from dot count. Count the number of . commands in the program — this gives the exact number of bytes output (each . outputs exactly one character). Compare with expected flag length to validate you have the right program.

Common Analytical Errors

• Executing untrusted Brainfuck without reviewing for infinite loops. Programs with [ and no matching termination condition will hang. Use interpreters with execution step limits, or set a maximum iteration count in custom implementations.
• Confusing Ook! with Brainfuck. Ook! programs contain "Ook" words — they will not run in a Brainfuck interpreter without translation. Always translate Ook! to Brainfuck first using an Ook!→Brainfuck converter.
• Assuming no input is needed. Challenges sometimes embed the decoding key as Brainfuck input. If the program contains , commands and produces no output, try providing different inputs (empty string, , challenge-provided data).
• Overlooking the wrap-around cell behaviour. Cell values wrap at 255 (adding 1 to 255 yields 0 in standard Brainfuck). Some extended variants use unbounded integers. A mismatch in cell size causes incorrect character computation.
• Treating comment characters as significant. Any character outside the 8 valid commands is a comment. Text interspersed with Brainfuck commands (a common CTF obfuscation) does not change program semantics — strip non-command characters before execution if the interpreter does not handle them automatically.
• Not accounting for cell pointer wrap-around. Most standard interpreters do not wrap the data pointer (going left past cell 0 is undefined or causes an error). Programs that assume pointer wrap-around require a wrapping interpreter; standard interpreters will crash or behave incorrectly.

NICE Framework Alignment

Further Reading

• Urban Müller's original Brainfuck distribution — Aminet archive (1993)
• Esoteric Programming Languages — esolangs.org wiki
• Obfuscation: A Researcher's Perspective — Barak et al., CRYPTO 2001