Let's continue with our third technique
the Unsafe Unlink, and we'll need to start with some more malloc internals.
So far, we've only seen what happens to chunks small enough to qualify for the fastbins
when freed, 0x80 and below. We'll be introducing another bin called the "unsortedbin" and the concept
of chunk consolidation.
Navigate to the 'unsafe_unlink' directory and load the 'demo' binary into GDB.
Set the context output to just source code,
set a breakpoint on the main() function and run the program.
We know what requesting chunks from malloc looks like by now
so use 'next 2' to make those first two requests, followed by 'vis', which shows us that we've got
two 0x90-sized chunks, A and B, on the default heap.
Before, when we freed chunks into the fastbins, they didn't have any noticeable effect on their surrounding
chunks,
neither did being next to the top chunk change their behavior
when freed.
But watch what happens when we free chunk B, which is both too large to qualify for the fastbins and
adjacent to the top chunk.
It disappears. Chunks adjacent to the top chunk that are too large to qualify for the fastbins, herein
referred to as "normal" chunks, are consolidated into the top chunk. And the 'bins' command confirms that
all of the bins are empty.
'next 2' requests
chunk B again, followed by a 0x20-sized chunk.
We'll come back to chunk B in a moment.
In the meantime, let's see what happens when we free a normal chunk that doesn't abut the top chunk.
Use 'next' to free chunk A.
Now 'vis' shows us that three changes have occurred on the heap.
The first is that the prev_inuse
bit of the succeeding chunk has been cleared,
something that didn't happen when we freed fast chunks.
We'll see what significance this has shortly.
The second change is that the last quadword of chunk A's user data has been repurposed as a
prev_size field, which we can see matches its size,
something else that didn't happen when we were dealing with the fastbins.
Note how the quadword containing the prev_size field is now colored to indicate that it belongs to
chunk B rather than chunk A,
this is an example of how malloc's chunks can change shape throughout their lifetime.
Lastly, chunk A has been linked into the unsortedbin.
The 'vis' command has annotated that here and we can confirm this from the output of the 'unsortedbin'
command.
The unsortedbin is another of malloc's free lists.
Unlike the fastbins, there is only one unsortedbin per arena.
It's a doubly linked, circular list that holds free chunks of any size. Because it's doubly linked
it uses both forward and backward, or fd and bk, pointers respectively.
And we can see that the first two quadwords of chunk A's user data have been repurposed as
unsortedbin forward and backward pointers.
The head of an unsortedbin exists in a heap's arena, just like the fastbins, where there are a pair
of forward and backward pointers that malloc treats as if they were part of a fake chunk.
The 'Arena Layout' diagram in your PDF shows the location of the unsortedbin pointers, which start
two quadwords after the top chunk pointer.
We can see them in memory by dumping the first sixteen quadwords of the main arena.
Right now they both point to chunk A, which is the only chunk in this unsortedbin. Chunk A's
fd and bk both point to the unsortedbin "chunk", which starts at the top chunk pointer.
This is what I mean about malloc treating the head of the unsortedbin as a fake chunk, which is done
to avoid having to treat it as a special case.
Here's an example unsortedbin with the head represented as a chunk. Each chunk's
forward pointer forms a circular linked list with the unsortedbin fd pointing to the first chunk
in the bin, that chunk's fd pointing to the next chunk and so on.
The last chunk in the bin has an fd that points back to the head of the unsortedbin.
Similarly, the last chunk's bk points to the previous chunk in the bin and so on.
And the unsorted's bk points back to the last chunk, completing the circle.
Like the fastbins, newly freed chunks are added to the head of the unsortedbin, whereas unlike the
fastbins, chunks are allocated from the tail of the unsortedbin.
We'll deal with allocations from the unsortedbin
in a later technique.
We've seen that freeing a fast chunk doesn't affect its surrounding chunks,
but what happens when we free chunk B, which is adjacent to the already free chunk A with 'next'? The
'vis' and 'unsortedbin' commands tell a different story
this time. Chunks A and B have been consolidated into the same larger chunk,
the size field of which reads 0x120,
the sum of both 0x90-sized chunks.
We can also see that the 0x20 chunk's prev_inuse flag is now clear and it's adopted a prev_size
field, indicating the previous chunk is
0x120 bytes long, matching the new chunk's size field.
We see from the output of the 'unsortedbin' command that there's still only one chunk in the
unsortedbin,
this new larger chunk.
So adjacent, free, normal chunks get consolidated together.
The process appears simple enough,
but consider what malloc has to do in order to achieve this.
When you free a chunk, it has to first check whether either adjacent chunk is available for consolidation.
It does this using prev_inuse flags. malloc checks the prev_inuse flag of the chunk being freed
to see if the previous chunk is free. And to check whether the succeeding chunk is free
it has to look forward by two chunks using their size fields to check the prev_inuse flag of the chunk
after the succeeding chunk.
Once malloc has established whether either or both of these chunks are consolidation candidates, it
must remove them from whichever free list they're already linked into,
otherwise a chunk might get linked into two different lists or the same list twice.
Then malloc has to add up the total space occupied by the new, larger chunk and set the size and prev_size
fields accordingly.
Finally, the new consolidated chunk is linked into the unsortedbin.
Of most interest to us in the consolidation process is the unlinking part where chunks being consolidated
are removed from a list.
For those of you with computer science backgrounds, this is basic linked lists,
but it's still worth explaining.
One of the benefits of linked lists is the ability to easily remove an item from the middle of said
list.
If you want to remove an item from the middle of a singly linked list like a fastbin, you have to
iterate over that list until you find the item preceding the one you want to remove,
then modify its forward pointer to skip your item.
If the item you want to remove is number 1000, you have to check the forward pointers of nine hundred
and ninety nine items before finding the one preceding your victim.
With normal chunks however, consolidation means that malloc has to be able to easily remove a chunk
from the middle of a potentially long list. In a doubly linked list
this is easy.
Let's say we want to remove this chunk from an unsortedbin with a handful of chunks in it.
Follow the victim chunk's fd to the next chunk in the list and overwrite that chunk's
bk with your victim's bk.
Now the victim chunk is unlinked from the backward list.
Next, follow the victim's bk to the previous chunk and overwrite that chunk's fd with your victim's
fd. Now the victim chunk is unlinked from both the forward and the backward lists.
In older versions of GLIBC, this unlinking process was done via a macro without any integrity checks
on the fd and bk pointers,
hence "unsafe" unlink.
If an attacker found themselves able to tamper with the fd and bk of a chunk that was subsequently
unlinked, it yielded a "reflected write" primitive, meaning that an attacker could select two addresses
and write one near the other and vice versa.
So before we approach the modern version of this technique, which involves a little more complexity,
we're going to visit the year 2000, before the introduction of NX, and leverage the Unsafe Unlink
technique in the way it was originally designed.