Firstly, this isn’t designed as an introduction to but rather as notes for future me.

The CTF site has a level called Automatic Exploit Generation (AEG), in which you have to write an exploit for a unique program, supplied to you once you connect to the server, in under 10 seconds. The exploitable program is compiled freshly on every connection from a template and differs in a number of ways each run, but has the same general structure:

  • Takes 1000 bytes from argv as input
  • XOR encodes each input byte with one of two alternating values, bouncing between them
  • Feeds this encoded input through a gauntlet of 15 functions which do basic arithmetic on the input to see if it matches hardcoded values
  • If it makes it to the end of the gauntlet, memcpy’s the input over a small stack buffer
  • exit()’s

Below is the first of these functions that we have dubbed ‘gauntlet functions’.


3 bytes taken from our input have already been loaded into edx, ecx and eax prior to calling this function. Each gauntlet function has a similar structure as the one above, but differs from the arithmetic done to the input and the hardcoded results that it is expecting (e.g. the first byte == 0xe9). If all the input is correct, it will load up the next set of bytes continue the gauntlet.

My original technique for solving this level was rather crude but effective. Since each of the checks in a gauntlet function make the program exit early, it allows you to brute force a single byte of the correct input at a time. My first attempt at this was through ptrace but the overhead from ptrace and my naively coded solution proved way too high. To remove ptrace from the equation we overwrote the failure paths with code that would crash the binary, effectively letting me know when a byte was wrong. This too turned out to be rather slow, probably because linux is reporting the crash to syslog, so the injected code was modified to a SYS_EXIT with a special value. Still slightly too slow we sped it up further by extracting the values that didn’t require any arithmetic to happen to them, which is every 3rd byte, and an example can be seen as the first cmp in this above function.

This solution proved to be barely fast enough to let me generate my exploit in 10 seconds and receive a connect back shell.

The second version of my exploit uses the framework to symbolically execute part of the supplied binary and extract the necessary input to make it through the gauntlet. The execution time of the new script is nearly twice as fast as the brute force approach, when setup correctly.

Initially, we setup angr to start just before the first gauntlet function which is past the XOR encoding loop. Beginning the symbolic execution at the start of the program proved way too slow and was unnecessary as we can extract the XOR values and apply them ourselves after the fact.

p = angr.Project('./bin99.ext') 
initial_state = p.factory.blank_state(addr=0x5621D51) # the basic block in the screenshot below


We define our input bytes as a series of 8 bit symbolic values, and create a string out of them just for convenience.

pw_char = claripy.BVS('PW_CHAR', 8) 
pw_str = pw_char 
for i in xrange(length): 
    initial_state.mem[0x5823A00+i:].byte = pw_char 
    pw_char = claripy.BVS('PW_CHAR', 8) 
    pw_str = pw_str.concat(pw_char) 

We store each of these characters in the .bss located at 0x5823A00. Next, we kindly ask angr to define it’s initial state as we have just set it up and try to find the memcpy function located at 0x56211AC while avoiding 0x56219BD, which is one of the incorrect routes.

paths = p.factory.path_group(initial_state, immutable=False) 

If the explorer function has found a path to where we asked it to go, we can extract a concrete value for our pw_str from the symbolic one through We apply the alternating XORs to each byte.

from itertools import cycle 
alternate = cycle(range(2)) 
header = "" 
if paths.found: 
    for c in[:-1]: 
            header += "%x" % (ord(c) ^ xor_right) 
            header += "%x" % (ord(c) ^ xor_left) 
    print header 

The rest of the exploit has some other, non-SMT related, hurdles to overcome such as generating the ROP chain offsets and extracting the various functions locations/XOR values but won’t be covered here. misc

If you’re wondering what the constraints look like, below we have a state where we’ve solved past the first two basic blocks and we will it to demonstrate accessing constraints, with ‘s’ being the state of the found path.


[<Bool PW_CHAR_11_8 == 233>, <Bool ((0x53 * 0x0#24 .. PW_CHAR_11_8)[7:0] - PW_CHAR_12_8) == 67>] 

When creating these variables we passed ‘PW_CHAR’ as the name and it is used as a prefix internally to represent them.

The first constraint is pretty obvious, the variable PW_CHAR_11_8 has to equal 233 or 0xe9 in hex and can be seen easily in the assembly. The second is more interesting as it contains the first symbolic variable inside it.

Basic block alignment


Some addresses that angr takes have to be aligned to the basic block start. For example, if we change the goal address to be the second instruction (0x56211ad) in the above function, it will error out with a cryptic error.

>>> paths 
<PathGroup with 48 avoid, 1 errored> 
>>> paths.errored 
[<Errored Path with 67 runs (at 0x9000010, SimMemoryLimitError)>] 

When it should be the following.

>>> paths 
<PathGroup with 39 avoid, 9 active, 1 found> 
>>> paths.found 
[<Path with 65 runs (at 0x56211ac)>]

Experimenting with timing

When using the symbolic exploration of angr, we experimented with how much setting addresses to avoid affected the amount of time it takes to paths.explore to a particular point in the wargame. The goal address is 15 functions deep past the initial starting state and each of the 15 functions check 3 bytes of input vs a series basic arithmetic.

  • No avoid addresses: 25 seconds
  • A single avoid address: 5.6
  • Fully filled in avoid addresses on all the major error routes (15): 3.6 seconds
  • If we go through each of the 15 functions and solve each one individually instead of going straight for the goal, while setting the correct avoid address for the function, it takes 4.6 seconds.