Sprint faster than this binary!
We're given a standard ELF, so we open it in Binary Ninja to try to figure out what it's doing:
(you may have to open the image in another tab and zoom in since it's small)
We can see that the binary mmaps a large chunk of memory, then memcpys some data of length 0xf134 into that chunk of memory. At a cursory glance, the data appears to be a very long format string. Then, various variables are initialized to 0, and var_98 and var_90 are initialized to the large memory chunk. We're then asked for a password, which is of length 255 and is stored at an offset of 0xe000 from the start of the memory. Then, there's a loop that repeatedly calls sprintf with var_98 as the format, and many, many arguments. Additionally, if var_98 is an offset 0xfffe from the memory chunk, the loop ends and the flag is printed. We can reasonably infer that this is a virtual machine, and the logic is controlled by the format string, which is in var_98. So, var_98 should be the program counter, and rax should contain the program memory.
When we look at the "long format string" in a hex view, we see that it is not a long format string, but many format strings. Each one of these probably corresponds to an instruction.
(the .s represent an unprintable character, in this case a null byte)
In addition to the format strings, it's probably also important to look at the format arguments:
- The first argument is
data_1116a, which is a single null byte, which is also an empty string. - The second argument is just 0.
- The third argument is the address of
var_98, the program counter. We can guess that this is used to write to the program counter. - The fourth argument is 0x6000000, which is the address of the buffer that
sprintfis printing into. Strange. - The fifth argument is the 2 bytes at the address pointed to by
var_90. - The sixth argument is
var_90. - The seventh argument is the address of
var_90. - The eigth argument is
var_88. - The ninth argument is the address of
var_88.
This value followed by address pattern continues on for a total of 6 different variables. Knowing that format strings don'o have an easy way to dereference an address, we can guess that the value argument is used to read from the variable, and the address argument is used to write to the variable. This means we basically have 6 "registers", and the first register can actually be dereferenced (via the 5th argument) to read from/write to memory. We'll call these registers r0, r1, r2, r3, r4, and r5. Creative names, I know. When we write to the 7th argument, we write to r0, writing to the 9th writes to r1, and so on. Reading from the 6th argument reads from r0, reading from the 8th argument reads from r1, and so on. Additionally, writing to the 6th argument writes to [r0], where [] denotes dereferencing. Reading from the 5th argument reads from [r0].
For this next portion, any capital letters in format specifiers represent a number (e.g. %Ns could mean %1234s or %4321s).
Now that we know what the arguments are, we can start reversing the format strings. We'll start with the first (with spaces between format specifiers to make it more readable):
%1$00038s %3$hn %1$65498s %1$28672s %9$hn
So, in format strings, the prefix K$ means that instead of just taking the next argument provided, which is the default behavior, the format string should instead pull from argument number K. %Ns means that a string should be printed, and it should be padded to length N with spaces. So, %1$00038s means to print out argument number 1, padded out to a length of 38. Since argument 1 is an empty string, we can be guaranteed that it never exceeds the length of the padding, so the final length will be whatever length it's padded to. Next, the hn format specifier means to write the number of characters printed to one of the arguments. In this case, we have %3$hn, so we're writing the number of characters printed, which should be 38, to the 3rd argument, which is the program counter. That's how the program is advanced. Next, we print out 65498 more characters, which brings the characters printed to 65536. Since hn only writes 2 bytes, 65536 wraps around to 0, essentially resetting the character count. Then, it prints out 28672 more characters, and writes it to argument 9, which is r1. This can roughly be translated to pc = 38, r1 = 28672.
Let's look at the next one:
%1$00074s %3$hn %1$65462s %1$*8$s %7$hn
Here, we see that it also writes a value to the program counter, resets the characters printed, and finishes off by writing to a register (r0 in this case). But what's that %1$*8$s?
The *8 means that the padding should be determined by the value in the 8th argument, which is r1 in this case. This means that the number of characters printed is equal to the value of r1, and this equates roughly to pc = 74, r0 = r1.
The next format string has nothing new, so we'll look at the one after that:
%1$00149s %3$hn %1$65387s %1$*8$s %1$2s %7$hn
This is like a mashup of the first two. It's writing to the program counter, resetting the characters printed, then printing a string padded to the value of r1 and a string padded to a length of 2, before writing into r0. This is adding their lengths together, and equates roughly to pc = 149, r0 = r1 + 2. There are more format strings like this one, but instead of adding a register to a value they could add a register to a register or a value to a register.
Let's skip forward a bit to a very unique-looking format string:
%14$c %1$00419s %2$c %4$s %1$65499s %3$hn
The c format specifier prints out a character, which means it prints out r4 (argument 14) as a character, then prints out 419 spaces. Then, it prints out argument 2 as a character, which as we know from before, is 0. Then, something strange happens. It prints out argument 4 as a string. Argument 4 is the address of the buffer it's printing things into, which means that it essentially doubles the number of characters printed out. Except, there's a catch. What if the first character printed was 0? Then, it'd print a null byte to the buffer, which C recognizes as the end of the string, which means the string has length 0 and %4$s does not print out anything. This is a conditional. Let's generalize this to the string:
$A$c %1$Bs %2$c %4$s %1$Cs %3$hn
If the register at A is not zero, then B + 2 (the two is for both the %A$c and the %2$c) characters are printed to the buffer, then %4$s will print out another B + 1 characters (the nullbyte at %2$c is not printed), then the %1$Cs will print out another C characters, writing a total of 2B + C + 3 to the program counter.
However, if the register at A is zero, then there will still be B + 2 characters printed, but %4$s will not print any extra, so only B + C + 2 will be written to the program counter.
There's also some weird data near the end of the memory chunk that we'll copy into a data.bin file because it might be useful later. The data is at an offset of 0xf000.
This pretty much covers every format string, so we can start disassembling the program.
I chose to write a Binary Ninja plugin for this:
from binaryninja import *
import string
# error if trying to halve an odd number
# makes sure I don't make mistakes
def asserted_halve(n):
# -1 is special and signifies [r0]
if n == -1:
return -1
assert n % 2 == 0
return n // 2
def make_regs():
# binja requires a stack pointer
regs = {
"_sp": RegisterInfo("_sp", 2)
}
for i in range(9):
name = "r" + str(i)
regs[name] = RegisterInfo(name, 2)
return regs
# pc = XXX, r? = XXX
def handle_load(pc, wrap, val, reg):
reg = asserted_halve(reg - 7)
assert pc + wrap == 2**16
return {
"ins": "load",
"pc": pc,
"reg": reg,
"val": val
}
# pc = XXX, r? = r?
def handle_mov(pc, wrap, src, dest):
src = asserted_halve(src - 6)
dest = asserted_halve(dest - 7)
assert pc + wrap == 2**16
return {
"ins": "mov",
"pc": pc,
"src": src,
"dest": dest
}
# pc = XXX, r? = r? + XXX
def handle_mov_add(pc, wrap, src, val, dest):
src = asserted_halve(src - 6)
dest = asserted_halve(dest - 7)
assert pc + wrap == 2**16
return {
"ins": "movadd",
"pc": pc,
"src": src,
"val": val,
"dest": dest
}
# pc = XXX, r? = r? + r?
def handle_mov_add_regs(pc, wrap, lhs, rhs, dest):
lhs = asserted_halve(lhs - 6)
rhs = asserted_halve(rhs - 6)
dest = asserted_halve(dest - 7)
assert pc + wrap == 2**16
return {
"ins": "movaddregs",
"pc": pc,
"lhs": lhs,
"rhs": rhs,
"dest": dest
}
# pc = XXX
def handle_jmp(pc):
if pc == 65534:
ins = "ret"
else:
ins = "jmp"
return {
"ins": ins,
"pc": pc
}
# if r? == 0 then goto XXX else goto XXX
def handle_cond(test, pad1, pad2):
test = (test - 6) // 2 # arg6/7 -> r0, arg8/9 -> r1, ...
return {
"ins": "cond",
"reg": test,
"true_branch": (2 * pad1 + pad2 + 3) % 65536,
"false_branch": (pad1 + pad2 + 2) % 65536
}
instructions = {
"%1${pc}s %3$hn %1${wrap}s %1${val}s %{reg}$hn": handle_load,
"%1${pc}s %3$hn %1${wrap}s %1$*{src}$s %{dest}$hn": handle_mov,
"%1${pc}s %3$hn %1${wrap}s %1$*{src}$s %1${val}s %{dest}$hn": handle_mov_add,
"%1${pc}s %3$hn %1${wrap}s %1${val}s %1$*{src}$s %{dest}$hn": handle_mov_add,
"%1${pc}s %3$hn %1${wrap}s %1$*{lhs}$s %1$*{rhs}$s %{dest}$hn": handle_mov_add_regs,
"%1${pc}s %3$hn": handle_jmp,
"%{test}$c %1${pad1}s %2$c %4$s %1${pad2}s %3$hn": handle_cond
}
def check_matches(fmt, act):
vals = {}
i = 0
j = 0
while i < len(fmt) and j < len(act):
if fmt[i] == " ":
i += 1
continue
if fmt[i] == "{":
end = fmt.index("}", i)
varname = fmt[i + 1:end]
num = ""
i = end + 1
while act[j] in string.digits:
num += act[j]
j += 1
if num == "":
continue
num = int(num)
vals[varname] = num
if fmt[i] != act[j]:
return None
i += 1
j += 1
if i != len(fmt) or j != len(act):
return None
return vals
def get_instruction(fmt):
try:
for ins in instructions:
vals = check_matches(ins, fmt)
if vals is not None:
return instructions[ins](**vals)
except Exception as e:
return None
# quality of life to make creating tokens easier
def makeToken(tokenType, text, data=None):
tokenType = {
"i": InstructionTextTokenType.InstructionToken,
"t": InstructionTextTokenType.TextToken,
"a": InstructionTextTokenType.PossibleAddressToken,
"r": InstructionTextTokenType.RegisterToken,
"d": InstructionTextTokenType.IntegerToken,
"b": InstructionTextTokenType.BeginMemoryOperandToken,
"e": InstructionTextTokenType.EndMemoryOperandToken,
"s": InstructionTextTokenType.OperandSeparatorToken
}[tokenType]
if data is None:
return InstructionTextToken(tokenType, text)
return InstructionTextToken(tokenType, text, data)
def format_reg(regnum):
if regnum == -1:
return [makeToken("b", "["), makeToken("r", "r0"), makeToken("e", "]")]
else:
return [makeToken("r", "r%d" % regnum)]
# read a register in binja LLIL
def il_get_reg(regnum, il):
if regnum == -1:
return il.load(2, il.reg(2, "r0"))
else:
return il.reg(2, "r%d" % regnum)
# write to a register in binja LLIL
def il_set_reg(regnum, val, il):
if regnum == -1:
return il.store(2, il.reg(2, "r0"), val)
else:
return il.set_reg(2, "r%d" % regnum, val)
# jump to an address in binja LLIL
def goto_or_jump(addr, il):
lab = il.get_label_for_address(Architecture["Sprint"], addr)
if lab is not None:
return il.goto(lab)
else:
return il.jump(il.const_pointer(2, addr))
class Sprint(Architecture):
name = "Sprint"
address_size = 2
default_int_size = 2
instr_alignment = 1
max_instr_length = 100
regs = make_regs()
stack_pointer = "_sp"
def get_instruction_info(self, data, addr):
data = data.decode("utf8")
end = data.find("\x00")
if end == -1:
return None
result = InstructionInfo()
result.length = end + 1
fmt = data[:end]
ins = get_instruction(fmt)
if ins is None:
return result
if ins["ins"] == "cond":
result.add_branch(BranchType.TrueBranch, ins["true_branch"])
result.add_branch(BranchType.FalseBranch, ins["false_branch"])
elif ins["ins"] == "ret":
result.add_branch(BranchType.FunctionReturn)
else:
if ins["pc"] != addr + end + 1:
result.add_branch(BranchType.UnconditionalBranch, ins["pc"])
return result
def get_instruction_text(self, data, addr):
data = data.decode("utf8")
end = data.find("\x00")
if end == -1:
return None
tokens = []
fmt = data[:end]
ins = get_instruction(fmt)
if ins is None:
return ([makeToken("t", "INVALID")], end + 1)
if ins["ins"] == "load":
tokens.append(makeToken("i", "mov"))
tokens.append(makeToken("t", " "))
tokens += format_reg(ins["reg"])
tokens.append(makeToken("s", ", "))
tokens.append(makeToken("d", hex(ins["val"]), ins["val"]))
elif ins["ins"] == "mov":
tokens.append(makeToken("i", "mov"))
tokens.append(makeToken("t", " "))
tokens += format_reg(ins["dest"])
tokens.append(makeToken("s", ", "))
tokens += format_reg(ins["src"])
elif ins["ins"] == "movadd":
tokens.append(makeToken("i", "mov"))
tokens.append(makeToken("t", " "))
tokens += format_reg(ins["dest"])
tokens.append(makeToken("s", ", "))
tokens += format_reg(ins["src"])
tokens.append(makeToken("t", " + "))
tokens.append(makeToken("d", hex(ins["val"]), ins["val"]))
elif ins["ins"] == "movaddregs":
tokens.append(makeToken("i", "mov"))
tokens.append(makeToken("t", " "))
tokens += format_reg(ins["dest"])
tokens.append(makeToken("s", ", "))
tokens += format_reg(ins["lhs"])
tokens.append(makeToken("t", " + "))
tokens += format_reg(ins["rhs"])
elif ins["ins"] == "jmp":
tokens.append(makeToken("i", "jmp"))
tokens.append(makeToken("t", " "))
tokens.append(makeToken("a", hex(ins["pc"]), ins["pc"]))
elif ins["ins"] == "ret":
tokens.append(makeToken("i", "ret"))
elif ins["ins"] == "cond":
tokens.append(makeToken("i", "if"))
tokens.append(makeToken("t", " "))
tokens.append(makeToken("t", "("))
tokens += format_reg(ins["reg"])
tokens.append(makeToken("t", " "))
tokens.append(makeToken("t", "&"))
tokens.append(makeToken("t", " "))
tokens.append(makeToken("d", "0xff", 0xff))
tokens.append(makeToken("t", ")"))
tokens.append(makeToken("t", " "))
tokens.append(makeToken("t", "then"))
tokens.append(makeToken("t", " "))
tokens.append(makeToken("a", hex(ins["true_branch"]), ins["true_branch"]))
tokens.append(makeToken("t", " "))
tokens.append(makeToken("t", "else"))
tokens.append(makeToken("t", " "))
tokens.append(makeToken("a", hex(ins["false_branch"]), ins["false_branch"]))
return (tokens, end + 1)
def get_instruction_low_level_il(self, data, addr, il):
data = data.decode("utf8")
end = data.find("\x00")
if end == -1:
return None
fmt = data[:end]
ins = get_instruction(fmt)
if ins is None:
il.append(il.nop())
return end + 1
if ins["ins"] == "load":
il.append(il_set_reg(ins["reg"], il.const(2, ins["val"]), il))
elif ins["ins"] == "mov":
il.append(il_set_reg(ins["dest"], il_get_reg(ins["src"], il), il))
elif ins["ins"] == "movadd":
il.append(il_set_reg(ins["dest"],
il.add(2, il_get_reg(ins["src"], il), il.const(2, ins["val"])), il))
elif ins["ins"] == "movaddregs":
il.append(il_set_reg(ins["dest"], il.add(2, il_get_reg(ins["lhs"], il), il_get_reg(ins["rhs"], il)), il))
elif ins["ins"] == "jmp":
# control flow handled later
pass
elif ins["ins"] == "ret":
# control flow handled later
pass
elif ins["ins"] == "cond":
# control flow handled later
pass
else:
il.append(il.nop())
if ins["ins"] == "cond":
t = LowLevelILLabel()
f = LowLevelILLabel()
il.append(il.if_expr(il.and_expr(2, il_get_reg(ins["reg"], il), il.const(2, 0xff)), t, f))
il.mark_label(t)
il.append(goto_or_jump(ins["true_branch"], il))
il.mark_label(f)
il.append(goto_or_jump(ins["false_branch"], il))
elif ins["ins"] == "ret":
il.append(il.no_ret())
else:
if ins["pc"] != addr + end + 1:
il.append(goto_or_jump(ins["pc"], il))
return end + 1
Sprint.register()Then, we can go into a hex editor, extract just the format strings into a separate file, open that file in Binary Ninja, then create a function at the address 0 with the new Sprint architecture.
It's important to keep in mind that the input is from 0xe000-0xe100, the flag will be put into 0xe800, and there's some data at 0xf000-0xf134.
With that said, we'll take this step by step:
This is equivalent to the pseudocode (or python code, I don't know what the difference is):
PRIME = 0
NOT_PRIME = 1
mem = [PRIME] * 0x100 # 256 bytes is the max
mem[0] = NOT_PRIME
mem[1] = NOT_PRIME
k = 2
while k % 256 != 0:
if mem[k] == PRIME:
n = k * 2
while (n >> 8) == 0:
mem[n] = NOT_PRIME
n += k
k += 1This is essentially the Sieve of Eratosthenes, creating an array at 0x7000 that contains 0 if a number is prime and 1 otherwise.
This is the next block:
Essentially, r2 has the negative length of our input, and then two is subtracted from it. If it's not 0, we jump to a block which returns from the function and sets the flag to a single null byte, which is bad, which means we want our input to have a length of 254.
This is the next block:
It seems to set up some variables, then jump into the main program loop. r1 appears to be the index in our input, and r3 gets the first byte of the data starting at 0xf100. The program loop (starting at the second block) checks if input[r1] is a null-byte, and jumps accordingly. Since we want to see what happens with our input, we'll ignore the right branch and just focus on the left branch (what happens when the input isn't a nullbyte):
One weird thing is that both r4 and r8 are only written to and never read from in this branch. It seems like r8 is never read from in the entire program, so maybe it's some exit-code register that the problem writers left in to help debug. However, r4 is read at the start of the other branch, and if it's 0 then the program exits immediately and sets the flag to an empty string. So, we don't want r4 to get set to 0, since it seems like it will never get set back to 1.
r5 contains our input byte, and it's tested among multiple chars, and once it finds a match, it updates r5 with the appropriate value and continues on. Since the characters are urdl, you can guess that they refer to the directions up, right, down, and left, and this involves some sort of 2d array, and r5 signifies the direction to move. If none of the characters are matched, r4 is set to 0, which is bad.
The next block adds r5 to r3, so we can infer that r3 is our current position. Then, an overflow check is performed, so if r3 is greater than 255 we exit immediately, which we also don't want.
We then see that r3 is used as the offset for some data at 0xf000, and the data is read into r5. r5 is then bitmasked to only have 1 byte, so we're essentially reading in one byte from r3. We see the primality array being loaded in from 0x7000, and we're essentially checking if data[r3] is prime. If it's not, then r4 is set to 0, which is bad, and if it is we move on. We then load in some data from 0xf103 + r2, and if it and r3 sum to a multiple of 256, then we add one to r2. Another cursory glance at the right branch reveals that r2 should be 9 by the time we finish, so we should focus on incrementing it. At this point, we can start to dump the 16x16 maze.
I wrote the following script to dump the maze:
import math
data = open("data.bin", "rb").read()
# slow prime checker because I'm too lazy to write a fast one
def is_prime(n):
if n < 2:
return False
if n == 2 or n == 3:
return True
if n % 2 == 0:
return False
for i in range(3, math.isqrt(n) + 1, 2):
if n % i == 0:
return False
return True
SAFE = "."
WALL = "X"
START = "@"
maze = ["?"] * 256
# dump the walls
for i in range(0x100):
if is_prime(data[i]):
maze[i] = SAFE
else:
maze[i] = WALL
# dump the targets
for i in range(9):
maze[256 - data[0x103 + i]] = str(i + 1)
# dump the starting position
maze[data[0x100]] = START
rowlen = math.isqrt(len(maze))
for i in range(0, len(maze), rowlen):
row = ""
row += " ".join(maze[i:i + rowlen]) # the maze walls
if i + rowlen >= len(maze) or maze[i + rowlen] == WALL:
row += " " + WALL # going out the right side will wrap around to a wall
print(row)
print("X " * (rowlen + 1)) # no going past the bottomRunning it gives us:
X X X X X X X X X X X X X X X X X
X @ X . . . . . X . . . . . . 9 X
X . X . X X X X X . X X X X X X X
X . . . . . . . X . X . X . . 6 X
X . X X X X X . X . X . X . X X X
X 3 X 5 X . . . . . . . . . . . X
X X X . X X X . X X X X X X X . X
X . . . X 8 . . X . . . X 1 . . X
X . X X X X X . X X X . X X X X X
X . . . . . . . X . X . . . X . X
X . X . X X X X X . X . X X X . X
X . X . X . X 4 X . . . . . . . X
X . X X X . X . X . X . X X X X X
X . . . . . . . . . X . . . . . X
X X X . X . X X X X X . X . X X X
X 7 . . X . X . . . . . X . . 2 X
X X X X X X X X X X X X X X X X X
You could write a program to solve the maze, but it's small enough where it's probably easier to solve it manually. I wrote a small extension to my maze dumping program to help me:
import math
data = open("data.bin", "rb").read()
# slow prime checker because I'm too lazy to write a fast one
def is_prime(n):
if n < 2:
return False
if n == 2 or n == 3:
return True
if n % 2 == 0:
return False
for i in range(3, math.isqrt(n) + 1, 2):
if n % i == 0:
return False
return True
SAFE = "."
WALL = "X"
START = "@"
maze = ["?"] * 256
# dump the walls
for i in range(0x100):
if is_prime(data[i]):
maze[i] = SAFE
else:
maze[i] = WALL
# dump the targets
for i in range(9):
maze[256 - data[0x103 + i]] = str(i + 1)
# dump the starting position
maze[data[0x100]] = START
def print_maze():
rowlen = math.isqrt(len(maze))
for i in range(0, len(maze), rowlen):
row = ""
row += " ".join(maze[i:i + rowlen]) # the maze walls
if i + rowlen >= len(maze) or maze[i + rowlen] == WALL:
row += " " + WALL # going out the right side will wrap around to a wall
print(row)
print("X " * (rowlen + 1)) # no going past the bottom
tot = ""
cur = data[0x100]
old = SAFE
while True:
print_maze()
totinp = "".join([x for x in input().strip() if x in "udlr"])
tot += totinp
print(tot)
for inp in totinp:
maze[cur] = old
if inp == "u":
cur -= 16
elif inp == "d":
cur += 16
elif inp == "l":
cur -= 1
elif inp == "r":
cur += 1
old = maze[cur]
maze[cur] = STARTNow I just solve the maze by hand to get the moves:
ddrrrrrrddrrrrrrrrddllrruullllllllddddllllllddddrrrrrrrruurrddrrddrrlluulluullddlllllllluuuurrrrrruuuuuulllllldduurrrrrrddddddllllllddddrrrrrruuddlllllluuuuuurruuddllddrrrrrruuuurrrrrruurrllddllllllddddllllllddddrrddllrruulluuuurrrrrruullrruurruuuurrrrrr
When we enter these as the password, we get the flag! We didn't even need to look very far into the right branch.
Input password:
ddrrrrrrddrrrrrrrrddllrruullllllllddddllllllddddrrrrrrrruurrddrrddrrlluulluullddlllllllluuuurrrrrruuuuuulllllldduurrrrrrddddddllllllddddrrrrrruuddlllllluuuuuurruuddllddrrrrrruuuurrrrrruurrllddllllllddddllllllddddrrddllrruulluuuurrrrrruullrruurruuuurrrrrr
Flag: CTF{n0w_ev3n_pr1n7f_1s_7ur1ng_c0mpl3te}