Challenge was solved as a team. We had a blast solving it! @WackAttack
Challenge
-[------->+<]>-.-[--->+<]>++.+.-----------.--[--->+<]>-.--[->++++<]>+.----------.++++++.-[---->+<]>+++.++[--->++<]>.---.++.------.--[--->+<]>-.[->+++<]>++.[--->+<]>----.+++[->+++<]>++.++++++++.+++++.--------.---[->+++<]>+.-[--->+<]>.++++++++.-[++>---<]>+.---[->++<]>.++++++++++.(and the ability to deploy a team instance lasting 15 minutes)
challenge author: R0R1
Solution
Decyphering the challenge description using a online brainfuck runner we get, Hope you like brainf*ck :D
Connecting to the server we are greeted with a message telling us that the flag is in 3 parts. Each part is 19 bytes.
Part 1
The fist 19 bytes of the flag is retrived byte for byte. We get a position for our datapointer and a position for a flag byte. We are also able to se the byte-value at the current datapointer’s position after we run our brainfuck code.
Our strategy for retriving the flagbyte was to move the flagbyte to the current datapointer position. We do this by creating the following program:
- Increment the current position to 1 |
+ - Move the nearest flagbyte to start |
<+[-[-[>+>]<->+[-[+<-<]>+]]<+](left) and>+[-[-[<+<]>-<+[-[+>->]<+]]>+](right)
With this we was able to solve the first part and got the flag_1: bi0sctf{M4yb3_I_M1s
Part 2
The next part of the flag had it’s own rules. We had to create a bainf*ck program that went to the tape-positions in the right order to print the flag. This was a challenge since there was a limit of 0x350 = 848 bytes.
We had our snipits, move left <+[-[>->]<+]< and move right <+[-[>->]<+]<. Using them “as is” exceeded the program size. The fist optemization was to remove the flagbyte after we read it. This results in using fewer instructions to move to the next flagbyte.
The next optemization was to create a move_left_far function that carries state of how far it has to move to get to the next flagbyte. When it sees a byte it will decrement the state and continue to move left untill the state is 0 [[-<+>]<<[>[-<<+>>]<<-<]>]>.
We created a python program to generate a solution for this part of the flag:
mov_left = "<+[-[>->]<+]<"
mov_left_far = "[[-<+>]<<[>[-<<+>>]<<-<]>]>"
mark = "."
def solve2(raw_cells, start):
order = [int(num[1:-1]) for num in raw_cells.split()]
assert not start in order
cells = sorted(order + [start])
path = ""
pos = start
for move in order:
steps = find_path(cells, pos, move)
path += move_str(steps)
path += mark
# Remove used nums
path += "[-]"
cells.remove(pos)
pos = move
# remove unnecessary operations
path = path.replace("><", "")
path = path.replace("<>", "")
path = path.replace("+-", "")
path = path.replace("-+", "")
if path.endswith("[-]"):
path = path[:-3]
# heuristics for infinite loop
assert not "[]" in path
return path
def find_path(cells, pos, dest):
# Returns a number of steps to reach the end cell, (e.g. -4 means 4 steps left, 3 means 3 steps right)
return cells.index(dest) - cells.index(pos)
def move_str(steps):
if abs(steps) < 3:
s = mov_left * abs(steps)
else:
s = "<" + abs(steps)*"+"
s += mov_left_far
if steps > 0:
s = s.replace("<", "A").replace(">", "<").replace("A", ">")
return s
flag_2: int3rpret3d_th3_t3r
Part 3
The last part of the flag was the most challenging. We struggled to understand what they was trying to tell us but after a while we understood that we had to create a program that could leak information about the flag without seeing the flagbyte.
Our fist guess for solving this was to use a timing attack. If the flagbyte was the number 65, we wanted to create a brainfuck program that would take longer time if the flagbyte was 66. Our best stragey was to take the (flagbyte^2) * constant, but we found out that the server’s recources was super unreliable, making it impossible to retrive the flag this way.
I woke up to a teammember having a brilliant idea: Use the datapointer position to leak information about the flagbyte. This had to be it!
The new strategy was as follows:
- Move four positions to the right and store the value 1. This indicates the start of the datapointer frame we can see.
- Retrive the flag and move it to the start of the datepointer frame.
- Decrement the flag by a constant, lets call this new value move_dist
- Move the datepointer move_dist amounts to the left
- If flag - constant < 10, we will se the datapointer inside the frame. Then our flagbyte is constant + move_dist
This was a solid plan, so we created a script to automatically manually get each byte from the flag. This was a boring process, but it got the job done.
from pwn import *
from solve2 import solve2
p = remote('<challenge-ip>', 33333)
print("START CHALLENGE 1")
p.recvuntil(b'Your choice :')
p.sendline(b'N')
p.recvuntil(b'Your choice :')
p.sendline(b'Y')
for i in range(19):
print(i)
p.recvuntil(b'INPUT YOUR CODE :')
p.sendline(b'+')
print("SOLVED CHALLENGE 1")
print("START CHALLENGE 2")
p.recvuntil(b'Your choice :')
p.sendline(b'N')
p.recvuntil(b'THE BYTES ARE TO BE MARKED IN THE INDEXES IN THE FOLLOWING ORDER -')
p.recvline()
p.recvline()
raw_cells = p.recvline().strip()
p.recvuntil(b'DATA POINTER IS AT :')
pos = p.recvline().strip()
code = solve2(raw_cells.decode(), int(pos))
p.recvuntil(b'INPUT YOUR CODE :')
print(code)
p.sendline(code.encode())
print("SOLVED CHALLENGE 2")
print("START CHALLENGE 3")
for i in range(19):
print(i)
p.recvuntil(b'IS A BYTE OF THE FLAG DROPPED AT INDEX OF TAPE > [')
flag_byte_pos = p.recvuntil(b']')[:-1]
p.recvuntil(b'THE DATA POINTER WILL INITIALLY BE AT [')
data_pointer_pos = p.recvuntil(b']')[:-1]
move_direction = int(flag_byte_pos) - int(data_pointer_pos)
get_value_left ="<+[-[-[>+>]<->+[-[+<-<]>+]]<+]+[-[<-<]>+]>-"
get_value_right = ">+[-[-[<+<]>-<+[-[+>->]<+]]>+]+[-[>->]<+]<-"
move_code = ">>>>+"
minus_amount = 78 # Constant that we will subtract from the flagbyte
if move_direction > 0:
move_code += get_value_right + ">" + "+"*minus_amount + "[-<->]<" + "<++[-[+<]+[>]<-]<[[-]<]>"
else:
move_code += get_value_left + ">" + "+"*minus_amount + "[-<->]<" + "<++[-[+<]+[>]<-]<[[-]<]>"
p.recvuntil(b'INPUT YOUR CODE :')
index = 2 # What frame do we want to inspect
if i == index:
p.sendline(move_code.encode())
else:
p.sendline(b"+")
if i == index:
p.interactive()
flag_3: m_Tur1ng_c0Mplet3}
(the 19th byte was a <space> character)
The complete flag was: bi0sctf{M4yb3_I_M1sint3rpret3d_th3_t3rm_Tur1ng_c0Mplet3}