ELF files are sooooo last year :rooVoid:. Instead of making yet another ELF to reverse, I made a new type of executable binary for you to reverse :rooYay:! It uses my new language Roolang. Just execute flag.roo to get the flag :rooPuzzlerDevil:! It's dynamically linked, so make sure you have the provided roo library files in the same directory :rooCash:. It's not very optimized, so it might take a moment (sorry about that) :rooNobooli:... Special shoutout to :rooRobin: and :rooOreos:, who have nothing to do with this challenge, but are both very cool people :rooHeart:. Good luck, and I hope you have fun :rooNervous:! Category: re (400 points) Chall author: puzzler7 Writeup author: malfurious Setup ----- We are provided with a zip archive containing several files: blind.roo * flag.roo (See Roolang.png) imag.roo * nobooli.roo * oreos.roo * robin.roo * roolang.py (See Appendix A) flag.roo is the primary 'executable'. This file is actually a PNG image, made up of a matrix of smaller sub-images (emoji from the CTF's Discord server). The remaining *.roo files (marked with a '*') are the 'library files' referred to by the problem description. They are individual original images for each of the emoji. roolang.py is a regular Python script that serves as an interpreter for Roolang. Execution --------- If you run roolang.py on the flag.roo file, it starts to output text: $ python roolang.py flag.roo Parsing... Running... The flag is ictf{th ... Each additional character takes longer and longer than the last to be displayed. Their calculation is being slowed by an inefficient algorithm. Tweaking the interpreter ------------------------ I initially tried making improvments to the Python code to see what kind of speedup we could see by optimizing the way it executes the various roolang instructions. For example: I tried reducing the amount of stack manipulation per instruction, removing checks to useless internal variables, and rewriting operations to take effect in-place where appropriate. I even replaced their `eval(string+'()')` method for executing instructions with a proper jump table (via a dictionary). This made a _very_ noticable difference in run time (LOL), but is not enough to make full execution of flag.roo feasible (as expected). So, I moved on to reverse engineering of the flag file using the interpreter. Bytecode -------- I mentioned earlier that the program is a matrix of images. This actually forms a linear sequence of emoji, left-to-right, then top-to-bottom. We can see in the functions robinify() and run() how the input file is processed to recover the opcode to execute. Each emoji is detected, reference to the original emoji ('library') files, and is tokenized: image token ----------------------------- robin.roo => r oreos.roo => o blind.roo => b imag.roo => i nobooli.roo => n Every five tokens are grouped as a word. Token ordering is similar to big-endian, so 'robin' means 'r, o, b, i, n'). Runtime ------- The roolang process has access to a stack and a single general-purpose register ('the register'). The calling convention is to push arguments to the stack before jumping. The return address is expected to be 'below' the arguments. The call instruction achieves this by cheating the stack and inserting the address below the already-pushed argument. The subroutine return value is also pushed to the stack. Similar trickery is done by the ret instruction to pop the return address out from underneath the return value. Execution starts at the beginning of the stream and terminates at the end. By studying the interpreter, we can see that roolang implements the following instructions (by Python functions of the same name): Opcode Len(words) Mnemonic Description ---------------------------------------------------------------------------- robin variable push If the 2nd word is the special value 'rinin', the value in the register is pushed to the stack. Otherwise, the 2nd word encodes the number of additional words to read. These additional words encode a value to push to the stack. All encoded values are in base-3 and use the o, b, i tokens to represent digits 0, 1, 2 respectively. rboin 1 pop Value is popped from the stack rinin 1 pop reg Value is popped from the stack into register rbiin 1 print chr Value is popped and is output (as character) rboon 1 print Value is popped and is output (as integer) riobn 1 add Pop 2 off stack, push sum rooon 1 sub Pop 2 off stack, push difference riibn 1 mul Pop 2 off stack, push product riion 1 div Pop 2 off stack, push quotient ribon 1 mod Pop 2 off stack, push remainder ronon 1 and Pop 2 off stack, push bitwise and roion 1 or Pop 2 off stack, push bitwise or roibn 1 xor Pop 2 off stack, push bitwise xor riiin 1 dup Push a copy of the top stack value rioin 1 swap Swap the top two stack values rnbon 2 label Mark a jump point in the program. The second word identifies the jump point. rioon 2 jmp Jump to a jump point, identified by the value of the second word. rbion 2 jnz Jump to a jump point, identified by the value of the second word. Only jump if the top stack value is non-zero. roiin 2 call Push return address to the stack and jump to the jump point identified by the second word. ribbn 1 ret Pop return address from the stack and jump to it. Disassembly ----------- With this understanding, we can easily modify the interpreter to act as a roolang disassembler, outputting the instruction mnemonics for operations used by the flag program (following argument data for multi-word instructions). See Appendix B for the disassembly I generated. It is annotated with equivalent C code to get a better idea of what the program does. The program starts out by pushing a bunch of data to the stack for processing. What follows is a loop which pops a value, performs math on it, and prints a character to the output. A zero value was pushed to the bottom of the stack so the program can detect when it has finished. Each stack value is XOR'd against the result of a recursive function call (identified in the flag program by the label 'robin'). Upon closer inspection, robin appears to implement a fibonacci function. The exact logic of the main loop is: for (i : 0 => len(data)) { print_chr(data[i] ^ robin(i)); } i gets farily large, which leads to a ton of redundant processing by robin(). This is what slows the program, preventing us from finishing it in a reasonable time. Dynamic programming solution ---------------------------- I rewrote the flag program (in Python this time) to leverage dynamic programming via memoization to accelerate robin() calculations. Each result produced by the function is cached, so that it doesn't need to be re-computed the next time that value is part of a call tree. The rest of my program is implemented to match the logic of flag.roo verbatim. See Appendix C for this solution code. "The flag is ictf{thr33_ch33r5_t0_r00r0bin_th3_b3st_0f_u5_a11_r00h3art_7d2e2642}" ================================================================================ = Appendix A: roolang.py = ================================================================================ #!/usr/bin/env python3 import sys from PIL import Image import numpy as np class Stack(list): def push(self, x): self.append(x) def peek(self): return self[-1] stack = Stack([]) program = [] register = 0 insn_pointer = 0 DEBUG = 0 def robinify(im): tiles = [im[x:x+128,y:y+128,0:4] for x in range(0,im.shape[0],128) for y in range(0,im.shape[1],128)] R = np.asarray(Image.open("robin.roo")) O = np.asarray(Image.open("oreos.roo")) B = np.asarray(Image.open("blind.roo")) I = np.asarray(Image.open("imag.roo")) N = np.asarray(Image.open("nobooli.roo")) d = list(zip([R,O,B,I,N], "robin")) ret = '' for c in tiles: for pair in d: if np.all(pair[0]==c): ret += pair[1] break return ret def step(): global insn_pointer insn = c_insn() if DEBUG: print(insn, program[insn_pointer+1], "@", insn_pointer) eval(insn+"()") def run(prog): global insn_pointer, program for ch in prog: if ch not in "robin": print("Syntax Error") exit(1) if len(prog) % 5 != 0: print("Syntax Error") program = [prog[i:i+5] for i in range(0, len(prog), 5)] try: while insn_pointer < len(program): step() insn_pointer += 1 if DEBUG: print(stack) except Exception as e: print("Fatal Error.") raise e print() print(stack) def c_insn(): return program[insn_pointer] def robin(): global insn_pointer insn_pointer += 1 toPush = c_insn() if toPush == "rinin": stack.push(register) else: words = parseDigit(toPush) toPush = 0 for i in range(words): insn_pointer += 1 toPush += parseDigit(c_insn()) toPush *= 27 stack.push(toPush//27) def parseDigit(s): return int(s.replace('o', '0').replace('b', '1').replace('i', '2')[1:-1], 3) def rboin(): stack.pop() def riobn(): stack.push(stack.pop()+stack.pop()) def rooon(): stack.push(stack.pop()-stack.pop()) def riibn(): stack.push(stack.pop()*stack.pop()) def riion(): stack.push(stack.pop()//stack.pop()) def ribon(): stack.push(stack.pop()%stack.pop()) def ronon(): stack.push(stack.pop()&stack.pop()) def roion(): stack.push(stack.pop()|stack.pop()) def roibn(): stack.push(stack.pop()^stack.pop()) def riiin(): x = stack.pop() stack.push(x) stack.push(x) def rioin(): x = stack.pop() y = stack.pop() stack.push(x) stack.push(y) def rinin(): global register register = stack.pop() def rbiin(): print(chr(stack.pop()), end='', flush=True) def rboon(): print(stack.pop(), end='', flush=True) def rnbon(): global insn_pointer insn_pointer += 1 def rioon(): global insn_pointer insn_pointer += 1 for i, word in enumerate(program): if word == "rnbon": if i != len(program)-1 and program[i+1] == c_insn(): insn_pointer = i+1 return print("Label not found!") raise RuntimeError def rbion(): global insn_pointer if stack.peek(): rioon() else: insn_pointer += 1 def ribbn(): global insn_pointer retval = stack.pop() insn_pointer = stack.pop() if DEBUG: print("returning to", insn_pointer) stack.push(retval) def roiin(): global insn_pointer arg = stack.pop() stack.push(insn_pointer+1) stack.push(arg) rioon() if __name__ == "__main__": if len(sys.argv) < 2: print("Usage: ./roolang.py [filename.roo]") exit() if sys.argv[1].split('.')[-1] != "roo": print("Invalid file format!") exit() with Image.open(sys.argv[1]) as f: print("Parsing...") program = robinify(np.asarray(f)) print("Running...") run(program) print("Finished execution.") ================================================================================ = Appendix B: flag.roo annotated disassembly = ================================================================================ Parsing... Disassebling... rnbon label rooon: robin push 0 robin push 14472334024676096 robin push 8944394323791450 robin push 5527939700884769 robin push 3416454622906725 robin push 2111485077978096 robin push 1304969544928756 robin push 806515533049347 robin push 498454011879172 robin push 308061521170150 robin push 190392490709200 robin push 117669030460982 robin push 72723460248127 robin push 44945570212756 robin push 27777890035307 robin push 17167680177653 robin push 10610209857675 robin push 6557470319826 robin push 4052739537835 robin push 2504730782038 robin push 1548008755937 robin push 956722025992 robin push 591286729974 robin push 365435296253 robin push 225851433664 robin push 139583862488 robin push 86267571223 robin push 53316291075 robin push 32951280083 robin push 20365011165 robin push 12586268949 robin push 7778742098 robin push 4807527027 robin push 2971214979 robin push 1836311808 robin push 1134903217 robin push 701408693 robin push 433494481 robin push 267914343 robin push 165580035 robin push 102334114 robin push 63246016 robin push 39088153 robin push 24157707 robin push 14930304 robin push 9227513 robin push 5702805 robin push 3524541 robin push 2178357 robin push 1346217 robin push 832119 robin push 514176 robin push 317697 robin push 196465 robin push 121346 robin push 75129 robin push 46403 robin push 28590 robin push 17692 robin push 10993 robin push 6687 robin push 4157 robin push 2668 robin push 1606 robin push 957 robin push 534 robin push 282 robin push 128 robin push 176 robin push 42 robin push 94 robin push 2 robin push 114 robin push 108 robin push 100 robin push 99 robin push 35 robin push 103 robin push 105 robin push 85 ========================================================================================= ; main rnbon label roobn: robin push 0 rinin pop reg i = 0 rnbon label rooin: rbion jnz robon for (c on stack) { rioon goto robbn (exit) rnbon label robon: robin push reg roiin call robin int p = c ^ robin(i); roibn xor print(p); rbiin print char i++; robin push reg } robin push 1 riobn add rinin pop reg rioon goto rooin rioon goto robbn ========================================================================================= ; fib (recursive) rnbon label robin: rbion jnz roion int robin(int arg) { rboin pop if (arg == 0) { robin push 1 return 1; ribbn ret } rnbon label roion: else { riiin dup int x = arg - 1; robin push 1 if (x == 0) { rooon sub return arg; // return 1; rbion jnz roibn } rboin pop ribbn ret rnbon label roibn: else { rboin pop int y = robin(arg - 2); riiin dup int z = robin(arg - 1); robin push 1 return y + z; rooon sub } robin push 0 } rooon sub } riiin dup robin push 1 rooon sub robin push 0 rooon sub roiin call robin -- rioin swap roiin call robin -- riobn add rioin swap rboin pop ribbn ret ========================================================================================= rnbon label robbn: robin push 0 rboin pop robin push 0 rboin pop ================================================================================ = Appendix C: flag.py solution = ================================================================================ solutions = {} i = 0 data = [ 14472334024676096, 8944394323791450, 5527939700884769, 3416454622906725, 2111485077978096, 1304969544928756, 806515533049347, 498454011879172, 308061521170150, 190392490709200, 117669030460982, 72723460248127, 44945570212756, 27777890035307, 17167680177653, 10610209857675, 6557470319826, 4052739537835, 2504730782038, 1548008755937, 956722025992, 591286729974, 365435296253, 225851433664, 139583862488, 86267571223, 53316291075, 32951280083, 20365011165, 12586268949, 7778742098, 4807527027, 2971214979, 1836311808, 1134903217, 701408693, 433494481, 267914343, 165580035, 102334114, 63246016, 39088153, 24157707, 14930304, 9227513, 5702805, 3524541, 2178357, 1346217, 832119, 514176, 317697, 196465, 121346, 75129, 46403, 28590, 17692, 10993, 6687, 4157, 2668, 1606, 957, 534, 282, 128, 176, 42, 94, 2, 114, 108, 100, 99, 35, 103, 105, 85 ] def robin(arg): if arg in solutions: return solutions[arg] if arg < 2: return 1 ret = robin(arg-2) + robin(arg-1) solutions[arg] = ret return ret while len(data) > 0: c = data[-1] data.pop() print(chr(c ^ robin(i)), end="") i += 1