This is a follow up of the KingMaker challenge from Codegate CTF Preliminary 2019. We solved this challenge during the CTF but when someone asked if it was possible to solve it using angr, I wanted to try it out myself.
The binary asks us for 5 keys which are then used to xor parts of the code segment. So if you get the keys right, the rest of the code will be correctly decrypted. We got the keys by xor’ing the first few bytes at each address with the assembled values of the instructions push rbp
and mov rbp, rsp
and some other such instructions.
Once you’ve got all the keys, there’s one more function which asks you for a string and then does some kind of verification.
The remaining inputs are all integers which represent choices which you (the prince) must decide between. And if all your choices are right, then you get to become the King and get the flag. This is done by a function which checks the value of 5 global variables and if they’re all equal to 5, then you get the flag. Also, this function has to be called with the second argument set to 1.
We solved this by first figuring out the required strings and then trying all possible combinations of integers.
But for the rest of this post, I will be detailing two days of effort that I’ve spent on something that is little more than a fruit of pure arrogance.
The first thing I did was to patch the original binary with all the keys that we found. I’ve added the code for that at the end. Note that this code is Python2.7 only because I was too lazy to figure out why my Python3 code was creating an invalid ELF.
The next thing to do is to patch the functions which verify the string inputs. This is where angr’s hooking functionality becomes useful. I could’ve just as easily overwritten the first byte of these functions with a ret
instruction, but what fun would that be ?
Now, the function which gives us the flag is pretty much called in every function with the second argument set to 0, There’s only one block from which this function is called with the second argument is set to 1. So that’s where we need to reach.
The integers that represent our choices are read in via scanf
. So, in order to avoid reading the symbolic variables off the stack, I decided to hook scanf
with a function that returned a symbolic variable if the format was ‘%d’.
But angr couldn’t find a path from the main
function to the target block even after 110 minutes and after using up 98% of 64 gigs of RAM.
Then I found that the first couple of functions did not use the input to manipulate the global variables. These functions only had two choices and if you entered the wrong one, the program exits. So, I decided to skip those functions and try exploration once again. This time, I tried setting the auto_drop
feature to automatically drop the avoid
and unsat
states which I hoped would free up some memory.
No luck. angr still used up too much memory.
Then I tried going through the different exploration techniques listed in the angr docs. ManualMergepoint seemed promising at first glance. But in retrospect, I don’t think it would’ve really made much of a difference.
The technique that eventually worked was DFS. It found the first path to the target block in less than 40 seconds.
But this path didn’t really satisfy the constraints that were required. And I couldn’t ask angr to find as many paths as possible because that would probably end up in another path explosion.
That’s when I looked up the angr documentation and it said that the find
argument in the explore
method can also be a function that returns either True
or False
.
So, I wrote up a function that would first check if the state had reached the target address and if so, it would then apply the constraints on the global variables.
I created a list to store the symbolic variables which I then stored in the state.globals
. But at the end of exploration, the list contained nearly 3000 symbolic variables which is nearly 10 times the number of times the expected value.
It seemed like every state wrote to the same global
object. So in order to get rid of that, I modified the code so that it would reset this list every time a state was not satisfiable. This lead to a different problem as now, the list contained too few symbolic variables. This probably happened because of a branching instruction at which the state split into two. When the first one was unsat
, it probably reset the list which contained all the symbolic variables that were created up until that point. So the second state only contains the symbolic variables that were created after the branching instruction.
The solution was to just use a dictionary to map the basic block which calls scanf
to the symbolic variable. So, if at some point, a state is unsat
, the state which succeeds it should overwrite this symbolic variable.
And that eventually worked. It took about 40 minutes and only 1% of RAM for angr to find a path from the address 0x403197 to the target block. But trying to find a path from main
to the target block took significantly more amount of time.
Anyway, here are the relevant scripts.
The solution
from pwn import * keys = ['lOv3', 'D0l1', 'HuNgRYT1m3', 'F0uRS3aS0n', 'T1kT4kT0Kk'] nums = [1, 1, 2, 2, 3, 1, 2, 1, 1, 2, 1, 2, 2, 3, 1, 1, 1, 2, 3, 2, 2, 1] vals = [] for x in nums: vals.append(str(x)) p = process('./KingMaker') p.sendline(vals[0]) p.sendline(keys[0]) for x in range(1, 5): p.sendline(vals[x]) p.sendline(keys[1]) for x in range(5, 11): p.sendline(vals[x]) p.sendline(keys[2]) for x in range(11, 14): p.sendline(vals[x]) p.sendline(keys[3]) p.sendline(vals[14]) p.sendline(vals[15]) p.sendline('A'*6) p.sendline(vals[16]) p.sendline(vals[17]) p.sendline(keys[4]) for x in range(18, len(vals)): p.sendline(vals[x]) print p.recvall()
Patching
fixes = {0x40341D: {'key': 'lOv3', 'sz': 0xf0}, 0x40330F: {'key': 'lOv3', 'sz': 0xf0}, 0x4033FF: {'key': 'lOv3', 'sz': 0x1e}, 0x4032C0: {'key': 'lOv3', 'sz': 0x1e}, 0x4032DE: {'key': 'lOv3', 'sz': 0x31}, 0x403197: {'key': 'lOv3', 'sz': 0x129}, 0x4030D4: {'key': 'lOv3', 'sz': 0xc3}, 0x402D55: {'key': 'D0l1', 'sz': 0xfa}, 0x402C25: {'key': 'D0l1', 'sz': 0x112}, 0x402D37: {'key': 'D0l1', 'sz': 0x1e}, 0x4027E9: {'key': 'D0l1', 'sz': 0x44}, 0x4029B9: {'key': 'D0l1', 'sz': 0xe6}, 0x402B2B: {'key': 'D0l1', 'sz': 0xfa}, 0x4028B5: {'key': 'D0l1', 'sz': 0xe6}, 0x40299B: {'key': 'D0l1', 'sz': 0x1e}, 0x40271C: {'key': 'D0l1', 'sz': 0xcd}, 0x402A9F: {'key': 'D0l1', 'sz': 0x4e}, 0x402AED: {'key': 'D0l1', 'sz': 0x3e}, 0x40282D: {'key': 'D0l1', 'sz': 0x44}, 0x402871: {'key': 'D0l1', 'sz': 0x44}, 0x4020E2: {'key': 'HuNgRYT1m3', 'sz': 0x18d}, 0x40201F: {'key': 'HuNgRYT1m3', 'sz': 0xc3}, 0x401B0A: {'key': 'F0uRS3aS0n', 'sz': 0xf0}, 0x4019F2: {'key': 'F0uRS3aS0n', 'sz': 0xfa}, 0x401AEC: {'key': 'F0uRS3aS0n', 'sz': 0x1e}, 0x40192C: {'key': 'F0uRS3aS0n', 'sz': 0xa8}, 0x4019D4: {'key': 'F0uRS3aS0n', 'sz': 0x1e}, 0x4016D0: {'key': 'F0uRS3aS0n', 'sz': 0xc3}, 0x4011BB: {'key': 'T1kT4kT0Kk', 'sz': 0x131}, 0x400F25: {'key': 'T1kT4kT0Kk', 'sz': 0xdc}, 0x40108B: {'key': 'T1kT4kT0Kk', 'sz': 0x130}, 0x401001: {'key': 'T1kT4kT0Kk', 'sz': 0x1e}, 0x40101F: {'key': 'T1kT4kT0Kk', 'sz': 0x4e}, 0x40106D: {'key': 'T1kT4kT0Kk', 'sz': 0x1e}, 0x400DE7: {'key': 'T1kT4kT0Kk', 'sz': 0x120}, 0x400F07: {'key': 'T1kT4kT0Kk', 'sz': 0x1e}, 0x400C8C: {'key': 'T1kT4kT0Kk', 'sz': 0x15b} } def xor(code, key): new_code = '' for x in range(len(code)): new_code += chr(ord(code[x]) ^ ord(key[x % len(key)])) return new_code def fix_file(addr, length, content, key): offset = 0x40341D - addr start = 13341 source = content[start-offset:start-offset+length] original = content[:start-offset] original += xor(source, key) original += content[start-offset+length:] return original def patch(): f1 = open("KingMaker", "rb") content = f1.read() f1.close() for addr in fixes: key = fixes[addr]['key'] sz = fixes[addr]['sz'] content = fix_file(addr, sz, content, key) f2 = open("Patched.bin", "wb") f2.write(content) f2.close() if __name__ == '__main__': patch()
Exploration
import angr from angr.exploration_techniques.dfs import DFS GOAL = 0x400B58 XOR_FUNC = 0x400AB9 RUN_TEST = 0x400A16 DECRYPT_FUNC = 0x401793 inputs = {} LE = angr.archinfo.Endness.LE class scanf_hook(angr.SimProcedure): def run(self): global inputs if self.state.solver.eval(self.state.regs.rdi) == 0x4041F9: # %s return elif self.state.solver.eval(self.state.regs.rdi) == 0x40394F: # %d expr = self.state.solver.BVS('inp', 32) self.state.solver.add(expr > 0) self.state.solver.add(expr < 5) block_addr = list(self.state.history.bbl_addrs)[-3] inputs[block_addr] = expr self.state.memory.store(self.state.regs.rsi, expr, endness=LE) else: print("!!!!!!!!!!!!!New condition!!!!!!!!!!!!!!") print(self.state.solver.eval(self.state.regs.rdi)) def get_target(cfg): targets = [] for addr in cfg.kb.callgraph.predecessors(GOAL): sites = [] func = cfg.functions.function(addr) for x in func.get_call_sites(): if func.get_call_target(x) == GOAL: b = cfg.get_any_node(x).block ins = b.capstone.insns[-3] op = ins.insn.operands[1] if op.imm == 1: targets.append(x) return targets def apply_constraints(state): global inputs # This is the address which get_target returns if state.addr != 0x400C3C: return False stats = [0x60716C, 0x607170, 0x607174, 0x607178, 0x60717C] for addr in stats: expr = state.memory.load(addr, 4, endness=LE) state.solver.add(expr == 5) return state.satisfiable() def explore(): p = angr.Project('./Patched.bin', load_options={'auto_load_libs': False}) # cfg = p.analyses.CFG() # target = get_target(cfg) p.hook_symbol('__isoc99_scanf', scanf_hook()) p.hook(XOR_FUNC, angr.SIM_PROCEDURES['stubs']['Nop']()) p.hook(RUN_TEST, angr.SIM_PROCEDURES['stubs']['ReturnUnconstrained']()) p.hook(DECRYPT_FUNC, angr.SIM_PROCEDURES['stubs']['ReturnUnconstrained']()) # This one takes nearly 2 hours to find a path # s = p.factory.blank_state(addr=0x403780) # And this one takes 40 minutes s = p.factory.blank_state(addr=0x403197) pg = p.factory.simulation_manager(s, auto_drop=['avoid', 'unsat']) pg.use_technique(DFS()) pg.explore(find=apply_constraints, avoid=GOAL) for state in pg.found: print("Inputs") for x in list(state.history.bbl_addrs): if x in inputs.keys(): print(state.solver.eval(inputs[x])) if __name__ == '__main__': explore()