My friend, iagox86, invited me to write a few challenges for the BSidesSF 2026 CTF so I wrote a few challenges around BrainFuck (BF). Here's how they work and how to solve them.
If you're not familiar with BF, checkout the BF Wikipedia article first or the rest of this won't make much sense.
Many years ago, I wrote a very simple language and compiler that goes from a simple language where the only datatype is a byte (including function pointers), then compiles it to an intermediate stack based assembly, then to BF. There are not arrays, structs, classes, or many other nice things but it's still better than
Each of the challenges is written in code that looks slightly like Python then transformed to BF. However, CTF participants are only given the BF code for each of the 3 challenges. Each BF program basically asks the user for input (the flag) and outputs "You got it!" if you got the flag or "Sorry..." if you didn't.
def is_digit(c):
"0" <= c and c <= "9"
def read_num():
c = read()
result = 0
while is_digit(c):
result = result * 10 + (c - "0")
c = read()
result
This was the original input language, which is why it's used as an intermediate step towards BF.
(defun is_digit (c)
(and (<= '0' c) (<= c '9')))
(defun read_num ()
(let ((c 0) (result 0))
(setq c (read))
(setq result 0)
(loop while (is_digit c) do
(setq result (+ (* result 10) (- c '0')))
(setq c (read)))
result))
is_digit:
push 48
copy -2
lesseq
copy -1
bool
cond $LABEL_2 $LABEL_3
jump
$LABEL_2:
copy -2
push 57
lesseq
jump $LABEL_1
$LABEL_3:
push 1
cond $LABEL_4 $LABEL_5
jump
$LABEL_4:
copy -1
jump $LABEL_1
$LABEL_5:
push 0
jump $LABEL_1
$LABEL_1:
set -2
pop -2
copy -2
pop -3
jump
read_num:
push 0
push 0
read
copy
set -4
pop
push 0
copy
set -3
pop
push 0
push $LABEL_8
push is_digit
copy -5
copy -2
pop -3
jump
$LABEL_8:
cond $LABEL_6 $LABEL_7
jump
$LABEL_6:
pop
copy -1
push 10
mul
copy -3
push 48
sub
add
copy
set -3
pop
read
copy
set -4
push $LABEL_9
push is_digit
copy -5
copy -2
pop -3
jump
$LABEL_9:
cond $LABEL_6 $LABEL_7
jump
$LABEL_7:
pop
copy -1
set -3
pop
copy -2
pop -3
jump
<[->+>+<<]>>[-<<+>>] ++> <[-<->] +<[>-<[-]]>[-<+>] <[- <[-]
++++++++++++++++++++++++++++++++++++++++++++++++>
<<[->>+>+<<<]>>>[-<<<+>>>]
<[-<[>>+<<[->>-<<]]>>[-<<->>]<]>+<+>[-<<[->>-<<]>[-<+>]>]<
<[->+>+<<]>>[-<<+>>]
<[>+<[-]]>[-<+>]
+++> ++++> <[-<->>+<]>[-<->]<<<[>[->-<]<[-]]>>[-<<->>]<[-]
]
<[->+>+<<]>>[-<<+>>] +++> <[-<->] +<[>-<[-]]>[-<+>] <[- <[-]
<<[->>+>+<<<]>>>[-<<<+>>>]
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
<[-<[>>+<<[->>-<<]]>>[-<<->>]<]>+<+>[-<<[->>-<<]>[-<+>]>]<
+++++++> ]
<[->+>+<<]>>[-<<+>>] ++++> <[-<->] +<[>-<[-]]>[-<+>] <[- <[-]
+>
+++++> ++++++> <[-<->>+<]>[-<->]<<<[>[->-<]<[-]]>>[-<<->>]<[-]
]
<[->+>+<<]>>[-<<+>>] +++++> <[-<->] +<[>-<[-]]>[-<+>] <[- <[-]
<[->+>+<<]>>[-<<+>>]
+++++++> ]
<[->+>+<<]>>[-<<+>>] ++++++> <[-<->] +<[>-<[-]]>[-<+>] <[- <[-]
>
+++++++> ]
<[->+>+<<]>>[-<<+>>] +++++++> <[-<->] +<[>-<[-]]>[-<+>] <[- <[-]
<<[-]>[-<+>]
<<[-]>[-<+>]
<<[->>+>+<<<]>>>[-<<<+>>>]
<<<[-]>[-<+>]>[-<+>]
]
<[->+>+<<]>>[-<<+>>] ++++++++> <[-<->] +<[>-<[-]]>[-<+>] <[- <[-]
>
>
,>
<[->+>+<<]>>[-<<+>>]
<<<<[-]>>>[-<<<+>>>]
<[-]
>
<[->+>+<<]>>[-<<+>>]
<<<[-]>>[-<<+>>]
<[-]
>
+++++++++>
++>
<<<<<[->>>>>+>+<<<<<<]>>>>>>[-<<<<<<+>>>>>>]
<<[->>+>+<<<]>>>[-<<<+>>>]
<<<[-]>[-<+>]>[-<+>]
]
<[->+>+<<]>>[-<<+>>] +++++++++> <[-<->] +<[>-<[-]]>[-<+>] <[- <[-]
++++++++++> ++++++++++++> <[-<->>+<]>[-<->]<<<[>[->-<]<[-]]>>[-<<->>]<[-]
]
<[->+>+<<]>>[-<<+>>] ++++++++++> <[-<->] +<[>-<[-]]>[-<+>] <[- <[-]
<[-]
<[->+>+<<]>>[-<<+>>]
++++++++++>
<<[->>+<<]>>[-<[-<+>>>+<<]>>[-<<+>>]<]<[-]
<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]
++++++++++++++++++++++++++++++++++++++++++++++++>
<[-<->]
<[-<+>]
<[->+>+<<]>>[-<<+>>]
<<<[-]>>[-<<+>>]
<[-]
,>
<[->+>+<<]>>[-<<+>>]
<<<<[-]>>>[-<<<+>>>]
+++++++++++>
++>
<<<<<[->>>>>+>+<<<<<<]>>>>>>[-<<<<<<+>>>>>>]
<<[->>+>+<<<]>>>[-<<<+>>>]
<<<[-]>[-<+>]>[-<+>]
]
<[->+>+<<]>>[-<<+>>] +++++++++++> <[-<->] +<[>-<[-]]>[-<+>] <[- <[-]
++++++++++> ++++++++++++> <[-<->>+<]>[-<->]<<<[>[->-<]<[-]]>>[-<<->>]<[-]
]
<[->+>+<<]>>[-<<+>>] ++++++++++++> <[-<->] +<[>-<[-]]>[-<+>] <[- <[-]
<[-]
<[->+>+<<]>>[-<<+>>]
<<<[-]>>[-<<+>>]
<[-]
<<[->>+>+<<<]>>>[-<<<+>>>]
<<<[-]>[-<+>]>[-<+>]
]
The assembly language is a stack based assembly that only manipulates bytes and there's a 1-to-1 correspondance between lines in assembly and "lines" of BF. For example, every add instruction replaces the last 2 bytes on the stack with the sum of those bytes and corresponds to the BF code <[-<+>].
This was the first challenge and has very straightforward code that reads each byte of user input one at a time and compares each byte to the flag one byte at a time.
def start():
print("What's the flag?: ")
if (
read() == "C"
and read() == "T"
and read() == "F"
and read() == "{"
# ...
and read() == "}"
and 1
):
print("You got it!\n")
else:
print("Sorry... :(\n")
The BF code that's output contains many lines like +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++> which push bytes on the stack, like the ASCII values for "C". Since there's no obfuscation, you can search for BF code like that and output all the bytes as (ASCII) text!
"""
Here's a mostly automated solution to part 1!
The .bf code is compiled from non-bf code *BUT* is not obfuscated
so raw byte values, like 65 (for the 'A' character) will show up in the code like:
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
This script is kind of like the strings utility but specific to this style of bf code.
"""
import re
import string
import sys
def main(argv: list[str]) -> None:
with open("i_love_my_bf_part1.bf" if len(argv) <= 1 else argv[1]) as f:
for line in f:
line = line.strip()
if re.match(r"^\+*>$", line):
c = chr(line.count("+"))
if c in string.printable:
print(end=c)
print()
if __name__ == "__main__":
main(sys.argv)
$ python3 i-love-my-bf-part1/solution/bf_plus_strings.py i-love-my-bf-part1/distfiles/i_love_my_bf_part1.bf
What's the flag?: CTF{i_love_my_brain_fuzzing}You got it!
Sorry... :(
Part 2 is very similar to part 1 but with some obfuscation.
def xor(a, b):
x1 = (a % 2) * (1 - (b % 2)) + (1 - (a % 2)) * (b % 2)
a /= 2
b /= 2
x2 = (a % 2) * (1 - (b % 2)) + (1 - (a % 2)) * (b % 2)
a /= 2
b /= 2
x4 = (a % 2) * (1 - (b % 2)) + (1 - (a % 2)) * (b % 2)
a /= 2
b /= 2
x8 = (a % 2) * (1 - (b % 2)) + (1 - (a % 2)) * (b % 2)
a /= 2
b /= 2
x16 = (a % 2) * (1 - (b % 2)) + (1 - (a % 2)) * (b % 2)
a /= 2
b /= 2
x32 = (a % 2) * (1 - (b % 2)) + (1 - (a % 2)) * (b % 2)
a /= 2
b /= 2
x64 = (a % 2) * (1 - (b % 2)) + (1 - (a % 2)) * (b % 2)
a /= 2
b /= 2
x128 = (a % 2) * (1 - (b % 2)) + (1 - (a % 2)) * (b % 2)
x1 + x2 * 2 + x4 * 4 + x8 * 8 + x16 * 16 + x32 * 32 + x64 * 64 + x128 * 128
def print_num(x):
if x >= 100:
print(x / 100 + "0")
if x >= 10:
print(x / 10 % 10 + "0")
print(x % 10 + "0")
def you_got_it():
print("You got it!\n")
exit()
def square(x):
x * x
def is_digit(c):
"0" <= c and c <= "9"
def read_num():
c = read()
result = 0
while is_digit(c):
result = result * 10 + (c - "0")
c = read()
result
def sorry():
print("Sorry...\n")
exit()
def swap_case(c):
xor(c, 32 * ((c >= "a" and c <= "z") or (c >= "A" and c <= "Z")))
def check_4_read_bytes_equal_make():
m = read()
(
m == 100 + 2 * 5 - 1 and read() == m - m // 9 and read() == m - 2 and read() == m - log2(255) - 1 # m # a # k
) # e
def sqrt(x):
i = 0
while i < 16 and i * i < x:
i += 1
i
def check_the_rest():
e = "e"
(
check_3_read_bytes_equal("B", "F", "_")
and check_4_read_bytes_equal_make()
and read() == 5 * (230 / 10)
and read() == "_" # "s"
and check_3_read_bytes_equal(swap_case("M"), swap_case("Y"), swap_case("_")) # _
and read() == 2**3 * 13
and read() == e # h
and read() == "a" # e
and read() == 2 * 3 * 19 # a
and read() == e + e // 7 + 1 # "r"
and read() == 5 * 19 # t
and read() == 10**2 - sqrt(9) # "_"
and read() == square(2) * square(5) - 1 # a
and read() == e + log2(14) # "c"
and read() == e # h
and read() == 5**3 # e
and 1 # }
)
def check_3_read_bytes_equal(x, y, z):
# a = read()
# b = read()
# c = read()
# ((a == x) * (b == y) * (c == z))
((read() == x) and (read() == y) and (read() == z))
def start():
print("What's the flag?: ")
if not check_3_read_bytes_equal("A" + 2, 2 * 2 * 3 * 7, "F") or read() != div2(247):
sorry()
if check_the_rest():
you_got_it()
sorry()
However, each byte is still read and compared 1 byte at a time... so you can guess the flag one byte at a time and as long as you track which BF instructions you reach or how many bytes were read, you can tell if you're making progress.
Here's some code that executes the BF code and tries guessing every next input byte until the BF code tries to read another byte.
import itertools
import string
import sys
from typing import Iterator
MAX_CELL_VALUE = 256
PRINTABLE_BYTES = tuple(ord(b) for b in string.printable)
# Optionally, sort the chars that are in the flag first, so this code runs faster.
# You can comment this out and the code will run the same... just slower
PRINTABLE_BYTES = tuple(
sorted(PRINTABLE_BYTES, key=lambda b: "CTF{BF_makes_my_heart_ache}".count(chr(b)), reverse=True)
)
def matching_brace_dict(bf_str: str) -> dict[int, int]:
matching_brace = {}
brace_poss = []
for j, c in enumerate(bf_str):
if c == "[":
brace_poss.append(j)
elif c == "]":
matching_brace[j] = brace_poss[-1]
matching_brace[brace_poss.pop()] = j
return matching_brace
def bytes_read_running_bf(
bf_str: str, in_file: Iterator[int], matching_braces: dict[int, int], stack=None, index=0, bf_index=0
) -> int:
if stack is None:
stack = [0] * 60
bytes_read = 0
j = bf_index
while j < len(bf_str):
c = bf_str[j]
if c == ">":
index += 1
elif c == "<":
index -= 1
elif c == "+":
stack[index] = (stack[index] + 1) % MAX_CELL_VALUE
elif c == "-":
stack[index] = (stack[index] - 1) % MAX_CELL_VALUE
elif c == ".":
# print(end=chr(stack[index]))
pass
elif c == ",":
bytes_read += 1
try:
stack[index] = next(in_file) % MAX_CELL_VALUE
except StopIteration:
return bytes_read
elif c == "]":
if stack[index]:
j = matching_braces[j]
elif c == "[":
if not stack[index]:
j = matching_braces[j]
j += 1
return bytes_read
def main(argv: list[str]) -> None:
with open("i_love_my_bf_part2.bf" if len(argv) <= 1 else argv[1]) as f:
bf = f.read()
matching_braces = matching_brace_dict(bf)
def byte_that_causes_more_reads(inputs) -> int | None:
baseline_bytes_read = bytes_read_running_bf(bf, itertools.chain(inputs, (PRINTABLE_BYTES[0],)), matching_braces)
for b in PRINTABLE_BYTES[1:]:
bytes_read = bytes_read_running_bf(bf, itertools.chain(inputs, (b,)), matching_braces)
if bytes_read > baseline_bytes_read:
return b
elif bytes_read < baseline_bytes_read:
return PRINTABLE_BYTES[0]
return None
inputs = list(map(ord, "CTF{"))
while True:
b = byte_that_causes_more_reads(inputs)
if b is None:
print("Can't find any more bytes that cause more reads.")
break
inputs.append(b)
print("Flag prefix:", "".join(map(chr, inputs)))
if __name__ == "__main__":
main(sys.argv)
$ python3 i-love-my-bf-part2/solution/check_inputs_until.py i-love-my-bf-part2/distfiles/i_love_my_bf_part2.bf
Flag prefix: CTF{B
Flag prefix: CTF{BF
Flag prefix: CTF{BF_
...
Flag prefix: CTF{BF_makes_my_heart_ac
Flag prefix: CTF{BF_makes_my_heart_ach
Flag prefix: CTF{BF_makes_my_heart_ache
Can't find any more bytes that cause more reads.
It's a bit slow, but it works!
Part 3 made a few changes over part 2:
nth_prime function below). This makes brute-force attacks harder.def is_prime(x):
j = 2
while x != j:
if x % j != 0:
j += 1
True
else:
j = x
False
def nth_prime(n):
i = 0
p = 2
while i < n:
if is_prime(p):
i += 1
p += 1
p - 1
def print_num(x):
if x >= 100:
print(x / 100 + "0")
if x >= 10:
print(x / 10 % 10 + "0")
print(x % 10 + "0")
def you_got_it():
print("You got it!\n")
exit()
def square(x):
x * x
def is_digit(c):
"0" <= c and c <= "9"
def read_num():
c = read()
result = 0
while is_digit(c):
result = result * 10 + (c - "0")
c = read()
result
def sorry():
print("Sorry...\n")
exit()
def swap_case(c):
if c >= "a" and c <= "z":
c - 32
elif c >= "A" and c <= "Z":
c + 32
else:
c
def sqrt(x):
i = 0
while i < 16 and i * i < x:
i += 1
i
def check_the_rest():
a = read()
b = read()
c = read()
d = read()
e = read()
f = read()
g = read()
h = read()
i = read()
j = read()
k = read()
l = read()
m = read()
n = read()
o = read()
p = read()
q = read()
r = read()
s = read()
correct = (
(a == square(3 * 4 - 1))
+ (b == 3 * 2**4)
+ (c == swap_case("U"))
+ (d == swap_case("A") - 2)
+ (div2(164) == e)
+ (swap_case("E") == f)
+ (nth_prime(24) == g)
+ (19 * 2**2 == h)
+ (h == (17 + 2) * 2 * 2)
+ (square(11) == j)
+ (k == "_")
+ (l == 2 * 2 * 3**3 - log2(3))
+ (m == "N")
+ (n == "O")
+ (o == 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15)
+ (p == 5 * 19)
+ (q == "B")
+ (r == "B" + log2("B") - 2)
+ (s == "}")
)
correct >= 18
def check_3_read_bytes_equal(x, y, z):
a = read()
b = read()
c = read()
((a == x) * (b == y) * (c == z))
def start():
print("What's the flag?: ")
if not check_3_read_bytes_equal("C", "T", "F") or read() != "{":
sorry()
if check_the_rest():
you_got_it()
sorry()
All the BF code for parts 1-3 have a very regular structure with repeating patterns for instructions. Decoding some of those lines can help identify what's going on. For example, if we look at the most common instructions, we can decode what they're doing:
$ sort i-love-my-bf-part3/distfiles/i_love_my_bf_part3.bf | uniq -c | sort -rh | head
103 <[-]
75 <[->+>+<<]>>[-<<+>>]
59 ]
53 >
42 <[-<+>]
35 <<[->>+>+<<<]>>>[-<<<+>>>]
26 <[-<->] +<[>-<[-]]>[-<+>]
25 ,>
23 <<[-]>[-<+>]
22 <<<[-]>[-<+>]>[-<+>]
pop 1 byte off the stack
103 <[-]
copy last byte on the stack
75 <[->+>+<<]>>[-<<+>>]
end of loop
59 ]
push a 0/null byte on the stack
53 >
add last 2 bytes (destructively)
42 <[-<+>]
copy 2nd to last byte on the stack
35 <<[->>+>+<<<]>>>[-<<<+>>>]
subtract last byte then replace last byte on the stack with 1 iff it's > 0 else 0
in other words... replace the last 2 bytes on the stack with 1 iff they're equal and 0 otherwise
26 <[-<->] +<[>-<[-]]>[-<+>]
read 1 byte and push it on the stack
25 ,>
pop second to last byte on the stack
23 <<[-]>[-<+>]
pop third to last byte on the stack
22 <<<[-]>[-<+>]>[-<+>]
Since each byte of user input is being compared directly to the expected value, we can execute the BF and look at what's on the stack each time we see a comparison/equal operation (<[-<->] +<[>-<[-]]>[-<+>]).
There are lots of comparisons happening in the code so we need to do some kind of filtering. For this problem, filtering on the 1st comparison for each BF instruction works really well:
import itertools
import string
import sys
from typing import Iterator
MAX_CELL_VALUE = 256
EQ_INSTRUCTION = "\n<[-<->] +<[>-<[-]]>[-<+>]\n"
def matching_brace_dict(bf_str: str) -> dict[int, int]:
matching_brace = {}
brace_poss = []
for j, c in enumerate(bf_str):
if c == "[":
brace_poss.append(j)
elif c == "]":
matching_brace[j] = brace_poss[-1]
matching_brace[brace_poss.pop()] = j
return matching_brace
def run_bf(
bf_str: str, in_file: Iterator[int], matching_braces: dict[int, int], stack=None, index=0, bf_index=0
) -> None:
if stack is None:
stack = [0] * 60
j = bf_index
already_printed = set()
comparison_instructions = frozenset(
i
for i in range(len(bf_str) - len(EQ_INSTRUCTION))
if bf_str[i:i + len(EQ_INSTRUCTION)].startswith(EQ_INSTRUCTION)
)
print(f"{'inst':>6s} {'lhs':>4s} {'rhs':<4s} printable")
flag = ""
while j < len(bf_str):
# Print out debug info when comparisons are detected
if j in comparison_instructions and j not in already_printed:
# If the next "instruction" is an equal comparison,
# then output the bytes that we are comparing against.
lhs = chr(stack[index - 2])
rhs = chr(stack[index - 1])
if lhs in string.printable:
flag += lhs
elif rhs in string.printable:
flag += rhs
is_printable = lhs in string.printable or rhs in string.printable
print(f"{j: 6d} {repr(lhs)[1:-1]:>4s} {repr(rhs)[1:-1]:<4s} {'*' if is_printable else ' '} {flag=}")
already_printed.add(j)
c = bf_str[j]
if c == ">":
index += 1
elif c == "<":
index -= 1
elif c == "+":
stack[index] = (stack[index] + 1) % MAX_CELL_VALUE
elif c == "-":
stack[index] = (stack[index] - 1) % MAX_CELL_VALUE
elif c == ".":
# print(end=chr(stack[index]))
pass
elif c == ",":
try:
stack[index] = next(in_file) % MAX_CELL_VALUE
except StopIteration:
return
elif c == "]":
if stack[index]:
j = matching_braces[j]
elif c == "[":
if not stack[index]:
j = matching_braces[j]
j += 1
def main(argv: list[str]) -> None:
bf_path = "i_love_my_bf_part3.bf" if len(argv) <= 1 else argv[1]
bf_user_input = itertools.chain("CTF{".encode(), itertools.repeat(0)) if len(argv) <= 2 else iter(argv[2].encode())
with open(bf_path) as f:
bf = f.read()
matching_braces = matching_brace_dict(bf)
run_bf(bf, bf_user_input, matching_braces)
if __name__ == "__main__":
main(sys.argv)
$ python3 i-love-my-bf-part3/solution/help_solve.py i-love-my-bf-part3/distfiles/i_love_my_bf_part3.bf
inst lhs rhs printable
28399 C C * flag='C'
28515 T T * flag='CT'
28662 F F * flag='CTF'
32429 { { * flag='CTF{'
21749 \x00 y * flag='CTF{y'
22033 \x00 0 * flag='CTF{y0'
22581 \x00 u * flag='CTF{y0u'
23111 \x00 _ * flag='CTF{y0u_'
23473 R \x00 * flag='CTF{y0u_R'
23991 e \x00 * flag='CTF{y0u_Re'
181 \x02 \x02 flag='CTF{y0u_Re'
567 \x01 \x00 flag='CTF{y0u_Re'
1318 \x03 \x03 flag='CTF{y0u_Re'
24430 a \x00 * flag='CTF{y0u_Rea'
24717 L \x00 * flag='CTF{y0u_ReaL'
24969 \x00 L * flag='CTF{y0u_ReaLL'
25395 y \x00 * flag='CTF{y0u_ReaLLy'
25601 \x00 _ * flag='CTF{y0u_ReaLLy_'
25978 \x00 k * flag='CTF{y0u_ReaLLy_k'
26155 \x00 N * flag='CTF{y0u_ReaLLy_kN'
26327 \x00 O * flag='CTF{y0u_ReaLLy_kNO'
26663 \x00 w * flag='CTF{y0u_ReaLLy_kNOw'
26813 \x00 _ * flag='CTF{y0u_ReaLLy_kNOw_'
26954 \x00 B * flag='CTF{y0u_ReaLLy_kNOw_B'
27236 \x00 F * flag='CTF{y0u_ReaLLy_kNOw_BF'
27424 \x00 } * flag='CTF{y0u_ReaLLy_kNOw_BF}'
There's a small chance I'll write a part 4 for next year's CTF, so I won't put spoilers here even though you can probably guess most of them. ;)