I’ve been going through how2heap problems recently, and I really enjoyed solving search-engine from 9447 CTF 2015. This was a pretty complicated problem, but it was also a lot of fun so I’ll be sharing a writeup of my solution below. I’d highly recommend going over sploitfun’s glibc malloc article and the fastbin_dup_into_stack.c example from how2heap before going through this writeup.
Reversing the binary
We first run
checksec before jumping into reversing the binary:
1 2 3 4 5 6 7 8
So we’re working with a 64-bit, dynamically linked, stripped binary, which has NX and canaries enabled.
The binary is a program for indexing sentences and then searching for words in those sentences. Here’s some example output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
After entering a sentence, the binary takes each word and adds it to a linked list of words. A node in this linked list looks like this:
1 2 3 4 5 6 7 8 9
Each word in the sentence has a
word_ptr that points into the
sentence pointer, which all words in a sentence share. When indexing a new sentence, the words are simply added to the front of the linked list, so it acts like a stack.
Searching for a word involves iterating over this linked list of words, ensuring the sentence string isn’t empty, and comparing the word to the target word. If we have a match, the sentence is printed and you have the option of deleting the sentence:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Note how the sentence is zeroed out before freeing it. This prevents the
*i->sentence check from passing for any of the words in that sentence. However this is a standard use after free (UAF). Once you zero out and free some data, that data doesn’t go untouched. glibc keeps free chunks in a doubly linked list, and the forward and backwards pointers for this list in the same region of memory where the data for the chunk used to be stored. This means that those pointers can cause the
*i->sentence check to pass even after the data was freed and zeroed out. This means we might be able to free the same sentence twice, causing a double free. This can lead to both memory leaks as well as allowing us to write to various locations in memory, as we’ll see later.
Another function worth mention is
read_num, which is used to supply the length of any strings we need to enter:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
The function reads up to 48 characters into a 48 byte buffer before attempting to convert the string to a number.
read_until_newline is backed by the libc
read function, and will read until either the number of characters specified is read or a newline is encountered. Note that it does not NULL-terminate the buffer. Since it does not NULL-terminate the string explicitly, any attempts to print the string will also print any data following the string until a NULL byte is run into. Lucky for us, the string is printed in the next few lines when the input begins with something that can’t be converted to a number by
strtol. We will use this for a stack leak later in the exploit.
Now that we understand the binary, we can talk about how to exploit it. The general approach will be to call
system('/bin/sh'). However, we don’t know the address of
system because of ASLR. We will thus need a libc leak to calculate this address. In order to jump to this code, we will need to control a return address of a function. Our analysis of the code shows that a double free is likely, which means we may be able to write to “arbitrary” memory by making a chunk in the free list point to the memory we want to write to (we can’t exactly write anywhere, as there a few checks we need to pass. Hence the quotes around “arbitrary”). We won’t be able to write a GOT address without failing these checks, but we may be able to pass these checks if we overwrite a return address on the stack instead (the details of why are explained in the corresponding section). However, in order to overwrite a return address on the stack, we need a stack leak (again because of ASLR).
Thus, our approach will 1) leak a stack address, 2) leak a libc address, 3) get a double free, and 4) use the double free to overwrite a return address to a call to
Getting a stack leak
The stack leak is the easiest part of the exploit, so we’ll start with that.
Here’s a basic pwntools script to fill up the buffer and see it printed. As mentioned in the previous section,
read_until_newline is backed by
read which does not terminate it’s input with a NULL byte, so filling up the buffer will leak any memory after it until we hit a NULL byte.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
You can comment in the
gdb.attach section when you want to attach
gdb to the binary.
Running the script gives:
1 2 3 4 5 6 7
So no leak. This isn’t surprising considering the code isn’t storing any data in that location in this particular function. We were hoping to get lucky and leak any previous data stored there, but we can open up GDB and confirm that memory is filled with zeros. Luckily, instead of looping whenever the input is invalid, the binary recurses instead. This means we can shift the stack lower and see if we get lucky somewhere else!
Let’s try sending the same string again:
1 2 3 4 5 6 7 8
We have a leak! Note that we occassionally get unlucky and have a null byte in the leaked address, but this doesn’t happen too often so it isn’t a problem. We can now parse out this address using Python:
1 2 3 4 5 6 7 8 9
We’ll use this function in our final exploit.
Getting a libc leak
This part of the exploit took me some time to come up with. The main observation we can make is that if we can exploit the UAF to allocate a sentence on top of a Word node, we can then control the
sentence pointer. We can then search for words in that sentence, and when we get a match, the sentence will be printed, and since we control that pointer we can read arbitrary memory.
Another important observation is that when a sentence is zeroed out, the words of that sentence are also zeroed out because words are simply pointers into the original sentence. However, if we can bypass the sentence NULL check (using the UAF), then we can still match on words by matching on the empty string!
Using that information, we come up with the following plan:
- Allocate a sentence that has the same length as a
Wordnode (40 bytes).
- Delete the sentence.
- Index a new sentence that is more than 16 bytes greater than the original sentence (so that it doesn’t reuse the chunk we just freed). When we create this sentence, a new
Wordnode is allocated where our original sentence is.
sentencewe originally freed is no longer NULL, because there’s a
Wordon top of it! That means the NULL check is bypassed. We can then search for an empty string to match a word in the sentence (as long as that word is still NULL and was not overwritten).
- We now have a 40 byte free chunk in a fastbin, but that same chunk is still being used as a
Wordnode. Thus, we can allocate a new 40 byte sentence and put a fake node in this sentence, thus setting the
sentencepointer to whatever we want (we’ll leak a GOT address).
- When we search for that
Wordnode, when we get a match the
sentencewill be printed, which will leak memory.
This is implemented in the following function, which is commented with some of the details.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
One important note is that the choice of GOT address (
0x602028 in this case) is important. I originally used a different GOT address, whose corresponding function just happened to have a least significant byte of zero. This means that the corresponding
sentence is an empty string. This is entirely dependent on your libc.
Alternate libc leak
After I solved this problem, I was looking up other solutions, and I saw a useful technique used by PPP’s solution.
The fastbins are different from small and large bins in that only the forward pointers are used for fastbins. For the other bins, the first index in each list is a libc address (probably pointing to the address of the index in the array, but I’m not completely sure). So if we allocate a small bin sized sentence instead (simply by allocating a chunk larger than 128 bytes), free the sentence, and then print the sentence (by matching on a word with an empty string), we’d print the small bin, including the libc address.
While I’ll definitely be using this trick in the future, the rest of this post assumes my original method of leaking a libc address.
Exploiting a double free
So we have a stack leak and a libc leak, now we just need to be able to overwrite a return address on the stack. Let’s start by figuring out how to get a double free, and then we can figure out how to exploit it later.
For our first attempt, let’s create two sentences:
'a'*54 + ' d' (let’s call this
'b'*54 + ' d' (let’s call this
sentence_c). The reason we choose sentences of size 56 is that this puts us in the fastbin of size 64, which prevents the allocations of the
Word nodes (40 bytes puts them in the 48 byte fastbin) and search words (the words we search for are small enough to fit in the 32 byte fastbin). If we allocate and free these two sentences (by searching for the word ’d’), we have our fastbin looks like
sentence_a_addr -> sentence_b_addr -> NULL, since the sentence with ‘b’s is freed first. Then let’s try to get a double free by searching for ’\x00’, since we know that the zeroed out ’d’ byte should still be zero. We first iterate over both words in the sentence with ‘b’s, but the sentence pointer points to an empty string (because this is the last element in the linked list), so we don’t double free this sentence. However, since
sentence_a_addr points to
sentence_b_addr (which is not NULL), we pass the NULL check and free this sentence. Our fastbin list would now look something like
sentence_a_addr -> sentence_a_addr -> sentence_b_addr, however glibc prevents us from doing that. glibc checks to see whether two adjacent chunks in the free list have the same address, aborting if this is the case.
We can easily fix this problem by allocating three strings of length 56 instead of two. Following the same steps as above, we would start off with a fastbin list like
sentence_a_addr -> sentence_b_addr -> sentence_c_addr -> NULL, and then after searching for ‘\x00’ we would match on
sentence_b, and the free list would look like:
sentence_b_addr -> sentence_a_addr -> sentence_b_addr -> .... We’ve created our double free cycle! We will also match on
sentence_a in this case, but we’ll choose not to delete it. Here’s the code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
Now that we have our double free, what can we do with it? We can first allocate a new sentence of size 56, and we’d get back the
sentence_b chunk. We’d put a fake heap chunk (in particular a fake
fwd pointer) in this sentence, and since this heap chunk is still in the free list (because we created that cycle), we can thus control the next chunk in the free list! We can make the fake chunk with the function below:
1 2 3 4
The next question is what address we pass to it. We can’t just make our fake chunk anywhere, because glibc checks to make sure the size of the chunk matches up with the fastbin it’s in. In our case, our chunk is 64 bytes, which is 0x40, so our index is 2. We can thus only create a chunk in a location where this condition will be satisfied, meaning we need to allocate our chunk in a place where the size is between 0x40 and 0x4F inclusive (The index is calculated with
(size >> 4) - 2), which is why this works). This is why we can’t overwrite a GOT address, as mentioned in the first section. My original idea was to start indexing a string, but when asked for the size of a string, put a long invalid string that ends with the qword 0x40. Then we allocate our chunk there (which is easy because we have a stack leak), and then we can overwrite the return address. This almost worked, but if you look in the
index function you’ll see there’s a
malloc, which modifies the stack and removes the 0x40 we put on it.
At this point I decided to just dump the stack and see if there was already a 0x40 I could use on it. After running
telescope $rsp 20 in pwndbg, I saw a bunch of code segment addresses that started with the byte 0x40 very close to the return address of the function. We could thus use this as the size of our fake heap chunk. We use ROPGadget to find a
pop rdi; ret gadget at 0x400e23, and we use that with the address of ‘/bin/sh’ and
system in the libc (calculated with the libc leak) to spawn a shell. The code for this is below, and you can find the full exploit at the bottom of this post.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
I added a few commands to pwndbg a while ago to display some useful heap information (as long as your libc has debugging symbols), but it seems like most people don’t know about them.
bins displays the fastbins, and
heap displays all the chunks in the heap.
malloc_chunk <addr> prints a nicely formatted chunk at the supplied address. I’ll be improving these commands using some of the lessons learned from this problem.
One neat trick I used was based on something I saw in a livestream by Gynvael, captain of Dragon Sector. Essentially instead of breaking on every
free and inspecting memory/registers or using the
heap commands to see what’s getting allocated, we can simply print out that information as it happens. Put the following code in
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
You can source it with
source helper.py in GDB, but I’d recommend putting it in a directory-local
.gdbinit. Now as the program runs, you’ll see messages like:
I’m going to be working on getting this functionality into
This last tip was also taken from Gynvael’s livestream. You can put structs into a C file (like the
Word struct file above), compile them with
gcc -gstabs -c structs.c -o structs.o, and then load them in GDB with
add-symbol-file structs.o 0. Then if you have a pointer to that struct at address
0xabcd, you can easily dump that struct with
p *(struct Word*)0xabcd and see all the fields of the struct. You can even use that struct in loops. For example, you can give the following GDB function an address to a
Word* and it’ll print out the entire
1 2 3 4 5 6 7
The output after indexing the sentence ‘a b’ and ‘c d’ looks like:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
Putting all this inside a
.gdbinit in the local directory is a convenient way of loading all this automatically:
1 2 3 4 5 6 7 8 9 10 11 12
The full exploit is provided below. Remember that you’ll need to change the offsets for a different libc. You also may need to run it a few times because the stack leak occassionally fails, as mentioned above.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140