Google CTF 2020 Write-up: Sprint

Picking apart the binary

We’re given a single binary file. Running it through objdump, we see that everything is in a single main function. Let’s pick it apart.

After setting up the stack, the first function call is this:

1199:   41 b9 00 00 00 00       mov    $0x0,%r9d
119f:   41 b8 ff ff ff ff       mov    $0xffffffff,%r8d
11a5:   b9 22 00 00 00          mov    $0x22,%ecx
11aa:   ba 03 00 00 00          mov    $0x3,%edx
11af:   be 00 00 00 04          mov    $0x4000000,%esi
11b4:   bf 00 00 00 04          mov    $0x4000000,%edi
11b9:   e8 82 fe ff ff          callq  1040 <mmap@plt>
11be:   48 89 45 c8             mov    %rax,-0x38(%rbp)

This translates to the following C:

void *mapped = mmap(0x4000000, 0x4000000, PROT_READ | PROT_WRITE,
                    MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

Where mapped is the local variable at -0x38(%rbp). This gives us a chunk of memory at 0x4000000. Technically, it only suggests that the chunk of memory is near 0x4000000, but checking in gdb shows it actually is 0x4000000. This is important later for some pointer calculations.

Next we call memcpy to copy some data from a constant M to mapped:

11c6:   ba 34 f1 00 00          mov    $0xf134,%edx
11cb:   48 8d 35 4e 0e 00 00    lea    0xe4e(%rip),%rsi        # 2020 <M>
11d2:   48 89 c7                mov    %rax,%rdi
11d5:   e8 86 fe ff ff          callq  1060 <memcpy@plt>

Lets check what this data is. We copy bytes starting at 0x2020, and ending at 0x2020+0xf134=0x11154.

$ objdump -s -j .rodata sprint

sprint:     file format elf64-x86-64

Contents of section .rodata:
 02000 01000200 00000000 00000000 00000000  ................
 02010 00000000 00000000 00000000 00000000  ................
 02020 25312430 30303338 73253324 686e2531  %1$00038s%3$hn%1
 02030 24363534 39387325 31243238 36373273  $65498s%1$28672s
 02040 25392468 6e002531 24303030 37347325  %9$hn.%1$00074s%
 02050 3324686e 25312436 35343632 73253124  3$hn%1$65462s%1$
 02060 2a382473 25372468 6e002531 24303031  *8$s%7$hn.%1$001
 03400 39732533 24686e25 31243630 34313773  9s%3$hn%1$60417s
 03410 25312435 39333932 73253724 686e0025  %1$59392s%7$hn.%
 03420 31243035 31353373 25332468 6e253124  1$05153s%3$hn%1$
 03430 36303338 33732531 24307325 3624686e  60383s%1$0s%6$hn
 03440 00253124 36353533 34732533 24686e00  .%1$65534s%3$hn.
 03450 00000000 00000000 00000000 00000000  ................
 03460 00000000 00000000 00000000 00000000  ................
 11000 00000000 00000000 00000000 00000000  ................
 11010 00000000 00000000 00000000 00000000  ................
 11020 ccb0e77b bcc0ee3a fc7381d0 7a6984e2  ...{...:.s..zi..
 11030 48e3d759 116bf1b3 860b89c5 bf536565  H..Y.k.......See
 11040 f0ef6abf 0878c42c 99353c6c dce0c899  ..j..x.,.5<l....
 11050 c83bef29 970bb38b cc9dfc05 1b67b5ad  .;.).........g..
 11060 15c108d0 45452643 456df4ef bb4906ca  ....EE&CEm...I..

So we have a bunch of null-terminated format strings packed together, then zeros, and then finally some binary data. We’ll have fun deciphering those format strings later, but for now let’s just see how this data is used.

The next few instructions zero out 80 bytes of memory at -0x90(%rbp), and then initialize them. That’s the size of 10 pointers, since we’re on x86_64. It is equivalent to

void *regs[10] = {mapped, mapped};

Remember that this means regs[2] through regs[9] is initialized to zero. We’ll see why I’m calling this regs later.

Next we ask the user for a password. We read the input with the equivalent of

scanf("%255s", mapped+0xe000);

This is the only place this program reads input. We have control over 255 bytes starting at mapped+0xe000.

Next we have some jumping around, which we can identify as a loop. The body of the loop is a single call to sprintf, but it takes a lot of code to pass the 25 arguments that it takes. The equivalent C is

while (buf[0] != mapped + 0xfffe) {
    sprintf(0x6000000,           // destination
            regs[0],             // format string
            M + 0xf14a,          // vararg 1, pointer to null character
            0,                   // vararg 2
            &(regs[0]),          // vararg 3
            0x6000000,           // vararg 4
            *((short*) regs[1]), // vararg 5
            regs[1], &(regs[1]), // varargs 6, 7
            regs[2], &(regs[2]), // varargs 8, 9 
            regs[3], &(regs[3]), // varargs 10, 11
            regs[4], &(regs[4]), // varargs 12, 13
            regs[5], &(regs[5]), // varargs 14, 15
            regs[6], &(regs[6]), // varargs 16, 17
            regs[7], &(regs[7]), // varargs 18, 19
            regs[8], &(regs[8]), // varargs 20, 21
            regs[9], &(regs[9])  // varargs 22, 23

Clearly, what exactly this call can do depends on the format string pointed to by regs[0]. This is initialized to mapped, where our list of format strings starts. We’ll get into this in the next section.

Last, our program checks if the 16-bit short at mapped+0xe800 is zero. If it is, it quits, and if it’s not, it prints the flag from memory at mapped+0xe800.

sprintf is Turing complete

From our analysis so far, we haven’t seen any direct reference to the user input (at mapped+0xe000) or the flag (at mapped+0xe800), so the format strings must be doing all the heavy lifting.

We read the strings using gdb, by examining the memory at 0x4000000. We find there are 146 strings, and save them to a file:

(gdb) b *main+555
(gdb) set logging on
(gdb) x/146s 0x4000000

Let’s take apart the first one:


In order:

  1. %1$00038s writes vararg 1 as a string, and pads it with spaces to ensure the length is at least 38. Since this argument is an empty string, it just writes 38 spaces.
  2. %3$hn doesn’t write anything, but it checks the number of characters written so far, and writes it in the short int pointed to by vararg 3. That is, it writes it to the lower two bytes of regs[0].
  3. %1$65498s writes 65498 spaces, so the total number of spaces so far is 65536, or 0x10000.
  4. %1$28672s writes 28672 spaces, or 0x7000 spaces.
  5. %9$hn counts the number of characters written so far, and writes it to the short int pointed to by vararg 9. That is, the lower two bytes of regs[2]. The number of characters is 0x17000, but since we’re only writing two bytes, we’re effectively writing 0x7000.

At the end of this operation, regs[0] is 0x4000026 and regs[2] is 0x7000. It just so happens that 0x4000026 is the address of the next format string, so on the next iteration of the loop we’ll use that string instead. Let’s call this operation mov 0x7000, %r2.

So far:

So really, what’s going on is this: We have a virtual machine with 10 registers, the instructions for this machine are sprintf format strings, and the first register is the program counter. Lets call the registers %r0, %r1, ..., %r9. We’ve allocated 8 bytes for each register, but in reality, we only ever write to the lower 2 bytes, and the registers we read from always have zeros in all but the lower two bytes (we do not read from %r0 or %r1, as we’ll see). The registers %r0 and %r1 are initialized to 0x4000000, so we can use them to reference memory locations 0x4000000 to 0x400ffff. We can think of each of these registers as only being two bytes, with a “virtual” address space of 0x0000 to 0xffff.

At this point, our strategy is to understand what types of instructions we’ll encounter, and then write a disassembler for this language, so we can reason about this embedded program.

Reading from registers

The next format string shows us a new trick:


Again, %1$00074s%3$hn sets the program counter to the next instruction, and %1$65462s ensures the number of spaces written so far is 0 modulo 0x10000. %1$*8$s is new. This writes a number of spaces depending on vararg 8, which is regs[2]. Then it saves this number to the short int pointed to by vararg 7, which is regs[1]. Effectively, this is mov %r2, %r1.

Reading from memory

The 5th variadic argument to sprintf is *((short*) regs[1]). That is, it interprets regs[1] as a pointer to a short, and dereferences it. Since regs[1] was initialized to 0x4000000 and we can modify the lower two bytes of it, this allows us to read from memory locations 0x4000000 to 0x400ffff. To do this, we use %1$*5$s, like in this example:


We’ll write this as mov (%r1), %r5.


By concatenating strings of spaces, we can perform addition. For example,


This prints a number of spaces based on %r2, then prints two more spaces, and saves the total count in %r1. We’ll call this add %r2, 0x2, %r1.

We can also add two registers, like


This is add %r3, %r3, %r6.

Unconditional jumping

To do an unconditional jump, all we have to do is set the program counter, %r0, to the desired value. For example,


This jumps to the instruction at 0x4000000+430, or 0x40001ae. We’ll write this as jmp 01ae.


The most complex type of instruction is branching. Here’s an example of one:


Breaking this down:

  1. %14$c writes the lowest byte of %r5.
  2. %1$00419s writes 419 spaces.
  3. %2$c writes a null byte.
  4. %4$s writes the string at 0x6000000, i.e. the string we’re in the middle of writing to. If the lower byte of %r5 is zero, this writes nothing, but if it’s nonzero, this writes 420 bytes.
  5. %1$65499s writes 65499 bytes.
  6. %3$hn stores the number of bytes written in the program counter.

So if the lower byte of %r5 is zero, we jump to 1+419+1+65499=0x10180, or really 0x0180 since we only keep the lower two bytes. If the lower byte is nonzero, we jump to 1+419+1+420+65499=0x10324, or really 0x0324. It happens that the instruction after this one is at 0x180, so it would make sense to call this instruction jnz %r5, 0324.

Writing a disassebler

Taking our output from gdb from before and running it through sed gives us a file with a format string on each line:

$ sed 's/.*"\(.*\)"/\1/' gdb.txt > format_strings.txt

Now we write a python script to parse each of the types of instructions we’ve seen above, and translate them to human-readable form. We can also check if some of the assumptions we’ve made hold and print an error message if they don’t. The code below is abbreviated, you can find the full code here.

#!/usr/bin/env python3

import fileinput
import re

literalMove = re.compile(r"^%1\$(\d*)s%3\$hn%1\$(\d*)s%1\$(\d*)s%(\d*)\$hn$")
# ... more for each type of instruction

def showRegisterDest(regRef):
    if regRef == 6:
        regStr = "(%r1)"
    elif regRef >= 7 and regRef <= 23 and regRef % 2 == 1:
        regStr = "%r{}".format(regRef // 2 - 2)
        print("bad destination: {}".format(regRef))
    return regStr

addr = 0

for line in fileinput.input():
    oldAddr = addr
    addr += len(line)
    m = literalMove.match(line)
    if m:
        nextAddr = int(
        filler = int(
        literal = int(
        regRef = int(

        if addr != nextAddr:
            print("address is not the next instruction")
        if nextAddr + filler != 0x10000:
            print("first two numbers do not add to 0x10000")

        dest = showRegisterDest(regRef)
        print("{:04x}: mov 0x{:x}, {}".format(oldAddr, literal, dest))
    # ... more for each other type of instruction
    print("unknown instruction")

Now we can see the output:

$ ./ < format_strings.txt > disassembly.txt
$ cat disassembly.txt
0000: mov 0x7000, %r2
0026: mov %r2, %r1
004a: mov 0x1, (%r1)
006c: add %r2, 0x2, %r1
0095: mov 0x1, (%r1)
00b7: mov 0x2, %r3
00da: add %r3, %r3, %r6
0108: add %r6, 0x7000, %r1
0136: mov (%r1), %r5
015b: jnz %r5, 0324

Picking apart the embedded code

Using gdb

Now we have yet another chunk of assembly to reverse. It will be useful to be able to use gdb to step through this code, so lets understand how to do that. The call to sprintf is at main+555, so by putting a breakpoint there, we can step through the embedded code one instruction at a time. To view the 10 registers, we can examine the memory at 0x90(%rbp).

Temporary breakpoint 1, 0x0000555555555189 in main ()
(gdb) b *main+555
Breakpoint 2 at 0x5555555553b0
(gdb) c
Input password:

Breakpoint 2, 0x00005555555553b0 in main ()
(gdb) x/10gx $rbp-0x90
0x7fffffffdde0: 0x0000000004000000  0x0000000004000000
0x7fffffffddf0: 0x0000000000000000  0x0000000000000000
0x7fffffffde00: 0x0000000000000000  0x0000000000000000
0x7fffffffde10: 0x0000000000000000  0x0000000000000000
0x7fffffffde20: 0x0000000000000000  0x0000000000000000
(gdb) c

Breakpoint 2, 0x00005555555553b0 in main ()
(gdb) x/10gx $rbp-0x90
0x7fffffffdde0: 0x0000000004000026  0x0000000004000000
0x7fffffffddf0: 0x0000000000007000  0x0000000000000000
0x7fffffffde00: 0x0000000000000000  0x0000000000000000
0x7fffffffde10: 0x0000000000000000  0x0000000000000000
0x7fffffffde20: 0x0000000000000000  0x0000000000000000

Instead of single-stepping, we can also set breakpoints in the embedded code, by adding conditional breakpoints in gdb. Before the call to sprintf, the program counter is passed in %rsi:

(gdb) clear *main+555
Deleted breakpoint 2 
(gdb) b *main+555 if $rsi == 0x400015b
Breakpoint 3 at 0x5555555553b0
(gdb) c

Breakpoint 3, 0x00005555555553b0 in main ()
(gdb) x/10gx $rbp-0x90
0x7fffffffdde0: 0x000000000400015b  0x0000000004007004
0x7fffffffddf0: 0x0000000000007000  0x0000000000000002
0x7fffffffde00: 0x0000000000000000  0x0000000000000000
0x7fffffffde10: 0x0000000000000004  0x0000000000000000
0x7fffffffde20: 0x0000000000000000  0x0000000000000000

At pretty much every step below, I was checking in gdb as I went, but I’ll leave that out for brevity.

Checking the input length

We’ll jump straight to the first place where we read the user input. Instead of picking apart the code before that, we can just use gdb to examine the state of the program at this point.

0374: mov 0xe000, %r2        # Address of user input
039a: mov 0x0, %r3           # Counter, initialized to 0

03bd: mov %r2, %r1
03e1: mov (%r1), %r4         # Read a char from user input
0406: jnz %r4, 043a          # If it's nonzero, skip to 043a
042b: jmp 04a1               # If it's zero, stop looping

043a: add %r3, 0xffff, %r3   # Decrement %r3
0469: add %r2, 0x1, %r2      # Increment %r2
0492: jmp 03bd               # Repeat the loop

At the end of this loop, %r3 contains the number of characters in the user input, but negated.

04a1: add %r3, 0xfe, %r6
04d0: jnz %r6, 0504          # jump to 0504 if %r3+0xfe != 0
04f5: jmp 0536               # jump to 0536 if %r3+0xfe == 0
0504: mov 0x5, %r9
0527: jmp 13d9               # jump to 139d if %r3+0xfe != 0

This code checks if the length of the user input is 0xfe, or 254. If it’s not, it jumps down to 139d, which writes zero to the flag and halts:

13d9: mov 0xe800, %r1
13ff: mov 0x0, (%r1)
1421: halt

Thus our input needs to be exactly 254 characters long.


Next we load some data into registers

0536: mov 0x0, %r2
0558: mov 0x0, %r3
057b: mov 0xf100, %r1
05a1: mov (%r1), %r4    # Read from 0xf100, value = 0x11
05c6: mov 0x1, %r5
05e9: mov 0x0, %r9

We have another chunk of code the jumps around in a pattern that looks like a loop. The loop starts with this:

060c: add %r2, 0xe000, %r1      # %r2 is index into user input
0639: mov (%r1), %r6            # read two bytes into %r6
065e: jnz %r6, 0692             # if lower byte is zero, break
0683: jmp 0d97                  # 0d97 is the end of the loop
0692: add %r2, 0x1, %r          # increment %r2

So we’re looping over the user input. The byte we just read is in the lower half of %r6. Now we break into cases depending on this byte.

06bb: add %r6, 0xff8b, %r7
06ea: jnz %r7, 0745             # jump to next block if input != 0x75 ('u')
070f: mov 0xfff0, %r6           # %r6 = 0xfff0 (-16) 
0736: jmp 0945                  # jump to end of section

0745: add %r6, 0xff8e, %r7
0774: jnz %r7, 07cb             # jump to next block if input != 0x72 ('r')
0799: mov 0x1, %r6              # %r6 = 0x1 (1)
07bc: jmp 0945                  # jump to end of section

07cb: add %r6, 0xff9c, %r7
07fa: jnz %r7, 0852             # jump to next block if input != 0x64 ('d')
081f: mov 0x10, %r6             # %r6 = 0x10 (16)
0843: jmp 0945                  # jump to end of section

0852: add %r6, 0xff94, %r7
0881: jnz %r7, 08dc             # jump to next block if input != 0x6c ('l')
08a6: mov 0xffff, %r6           # %r6 = 0xffff (-1)
08cd: jmp 0945                  # jump to end of section

# This executes if input was none of {u,r,d,l}
08dc: mov 0x0, %r5
08ff: mov 0x0, %r6
0922: mov 0x1, %r9

At this point, the characters ‘u’,‘r’,‘d’,‘l’ probably stand for “up”, “right”, “down”, and “left”, so we’re moving something around on a grid. It looks like %r6 holds an offset to move. Data must be stored in rows of length 16, since we add or subtract 16 to move up or down. If we don’t enter a valid direction, we don’t move at all, and %r5 and %r9 are updated to remember that.

From the next block of code, it looks like %r4 stores a position on the grid. The code writes and then reads memory at adjacent locations to get just the upper byte of the position.

0945: add %r4, %r6, %r4         # Update the position

0973: mov 0xffef, %r1
0999: mov %r4, (%r1)
09be: mov 0xfff0, %r1
09e4: mov (%r1), %r6

# At this point, the lower byte of %r6 is the upper byte of %r4
# So we jump if the upper byte of the position is nonzero
0a09: jnz %r6, 0d65

# ... snip ...

0d65: mov 0x4, %r9
0d88: halt

Since we haven’t written anything to the flag yet, halting here means we lose, so we had better keep the position between 0 and 255. That means we’re on a 16×16 grid.

Now, as expected, we’re using %r4 as an index into some memory, which we can think of as a map.

0a2e: add %r4, 0xf000, %r1      # %r4 is index into mem starting at 0xf000
0a5c: mov (%r1), %r6            # %r6 is two bytes read from that location

# This snippet just zeros out the high byte of %r6
0a81: mov 0xffef, %r1
0aa7: mov %r6, (%r1)
0acc: mov 0xfff0, %r1
0af2: mov 0x0, (%r1)
0b14: mov 0xffef, %r1
0b3a: mov (%r1), %r6

# Now %r6 holds the byte at 0xf000(%r4)
# Use 2 * %r6 as an index into memory at 0x7000
0b5f: add %r6, %r6, %r6
0b8d: add %r6, 0x7000, %r1
0bbb: mov (%r1), %r6           # Read from 0x7000+2*%r6
0be0: jnz %r6, 0d10            # Jump below if it's nonzero

# ... snip ...

0d10: mov 0x0, %r5
0d33: mov 0x2, %r9
0d56: jmp 060c                 # Continue from start of loop

From this, we see that there is an array of 256 bytes at 0xf000 that we index by our position. Each of these is in turn an index into an array of up to 256 16-bit integers at 0x7000. If the lower byte of the number we read is nonzero, we record it by setting %r5 and %r9, and jump to the next iteration. Since we never modify either of these regions over the course of this loop, this ends up being a round-about way of storing a 16×16 grid of booleans. Let’s call this grid the “terrain”.

We use the position one more time in the loop:

0c05: add %r3, 0x1, %r6
0c30: add %r6, 0xf102, %r1
0c5e: mov (%r1), %r6            # read %r6 <- 0xf103(%r3)

0c83: add %r6, %r4, %r6
0cb1: jnz %r6, 0d01             # check if pos+%r6==0
0cd6: add %r3, 0x1, %r3         # if true, increment %r3
0d01: jmp 060c                  # continue

So we have an array of bytes starting at 0xf103. We start out reading the first one, and read the others as %r3 gets incremented. These are the negations of positions on the map. Once we move to this position, we increment %r3. Call these positions “checkpoints”.

Now we’re done with the loop. Let’s see how the data we set in %r3, %r5, and %r9 are used

# If %r5 == 0, you lose!
0d97: jnz %r5, 0dcb
0dbc: jmp 13d9                  # zeros flag and halts

# If %r3 != 9, you lose!
0dcb: add %r3, 0xfff7, %r6
0dfa: jnz %r6, 0e2e
0e1f: jmp 0e60                  # jump to end of section

0e2e: mov 0x3, %r9
0e51: jmp 13d9                  # zeros flag and halts

So we see that setting %r5 to zero means we lose. That means we can’t ever enter an invalid direction, and we can’t ever step on nonzero terrain. We also see that we need to step on exactly nine checkpoints.

The register %r9 appears to hold a “reason code” for why we lose. This could be useful for debugging later.

There’s still more code after, but for now our task is clear: we need to map out the terrain and checkpoints, and plan our route.

Mapping it out

Since the code at the very beginning appears to mess with memory at 0x7000, we can’t just pull the terrain from the program binary. Instead, we should run our debugger until it’s done messing with memory, but before it starts checking any input, and then dump the memory from the right locations. In gdb:

(gdb) b *main+555 if $rsi == 0x4000374
(gdb) set logging on
(gdb) x/256bu 0x400f000
(gdb) x/256hu 0x4007000
(gdb) x/9bx 0x400f103

Now we manipulate this data into a few files, cleaning it up. First we have the indices at 0xf000:

204 176 231 123 188 192 238 58
252 115 129 208 122 105 132 226
72  227 215 89  17  107 241 179
134 11  137 197 191 83  101 101

Then the values at 0x7000:

1   1   0   0   1   0   1   0
1   1   1   0   1   0   1   1
1   0   1   0   1   1   1   0
1   1   1   1   1   0   1   0

And finally the negated positions of the checkpoints:

83 01 af 49 ad c1 0f 8b e1

Now we run a script to draw our map:

with open("values.txt") as f:
    valuesStr =
    values = [int(s) for s in valuesStr.split()]

with open("indices.txt") as f:
    indicesStr =
    indices = [int(s) for s in indicesStr.split()]

with open("checkpoints.txt") as f:
    checkpointStr =
    checkpoints = [0x100 - int(s, base=16) for s in checkpointStr.split()]

for col in range(16):
    print("  " + hex(col), end="")

for row in range(16):
    print(hex(row), end="")
    for col in range(16):
        pos = row * 16 + col
        if pos in checkpoints:
            print(" {} ".format(checkpoints.index(pos)+1), end="")
        elif values[indices[pos]] == 1:
            print(" # ", end="")
            print(" - ", end="")

And admire the output:

  0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f
0 #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  # 
1 #  -  #  -  -  -  -  -  #  -  -  -  -  -  -  9 
2 #  -  #  -  #  #  #  #  #  -  #  #  #  #  #  # 
3 #  -  -  -  -  -  -  -  #  -  #  -  #  -  -  6 
4 #  -  #  #  #  #  #  -  #  -  #  -  #  -  #  # 
5 #  3  #  5  #  -  -  -  -  -  -  -  -  -  -  - 
6 #  #  #  -  #  #  #  -  #  #  #  #  #  #  #  - 
7 #  -  -  -  #  8  -  -  #  -  -  -  #  1  -  - 
8 #  -  #  #  #  #  #  -  #  #  #  -  #  #  #  # 
9 #  -  -  -  -  -  -  -  #  -  #  -  -  -  #  - 
a #  -  #  -  #  #  #  #  #  -  #  -  #  #  #  - 
b #  -  #  -  #  -  #  4  #  -  -  -  -  -  -  - 
c #  -  #  #  #  -  #  -  #  -  #  -  #  #  #  # 
d #  -  -  -  -  -  -  -  -  -  #  -  -  -  -  - 
e #  #  #  -  #  -  #  #  #  #  #  -  #  -  #  # 
f #  7  -  -  #  -  #  -  -  -  -  -  #  -  -  2 

We start at position 0x11, i.e. (1, 1). Now we just need to plot a path that hits all the checkpoints in order. It turns out such a path is exactly 254 steps long. Save it in a file called directions.

$ cat <(fold directions) <(echo)
$ ./sprint < directions
Input password:
Flag: CTF{n0w_ev3n_pr1n7f_1s_7ur1ng_c0mpl3te}