In this video we're learning how to link fake chunks into the largebins via the House of Lore.
Once again, we'll begin by covering some malloc internals.
This time, unsurprisingly, we're talking about malloc's largebins.
The largebins are another collection of doubly-linked circular free lists, the heads of which reside in an
arena.
The arena layout diagram shows how the largebins begin after the smallbins.
There are 64 largebins, 63 of which are actually used.
Chunks become eligible for sorting into the largebins from the unsortedbin at sizes of
0x400 and above.
Now the largebins behave a little differently to the other bins, each largebin holds free chunks
within a range of sizes.
For example, the 0x400 largebin can hold chunks with sizes 0x400, 0x410, 0x420
and 0x430.
After the 0x400 largebin comes the 0x440 largebin, that holds chunks with sizes
0x440 through 0x470.
The largebins are, according to the malloc source code, approximately logarithmically spaced, meaning
that larger bins hold a wider range of chunk sizes.
For example, the 0x5000 largebin can hold chunks with sizes from 0x5000 all the way
through 0x5ff0.
The largest largebin holds 0x80000-sized chunks and above, it has no upper limit.
Within a largebin, chunks are ordered from larger to smaller, starting with larger chunks at the
head of the bin decreasing in size towards the tail.
This order is maintained using something that malloc calls a skip list, which I'll do my best to explain.
Here's an example 0x400 largebin. As usual, I've represented the head of this bin in its arena as a
chunk since that's how malloc treats it.
There are five chunks of varying sizes linked into this bin, 2 0x430-sized chunks, 2
0x410 chunks and a 0x400 chunk.
Just like the other doubly-linked circular lists, the first and second quadwords of each chunk's user data
are repurposed as forward and backward pointers.
In addition, the third and fourth quadwords of user data belonging to the first chunk of each size
are repurposed as forward_nextsize and backward_nextsize pointers.
These nextsize pointers form another doubly-linked circular list consisting of the first chunk of each
size within the same largebin.
This is what's known as the skip list and we'll refer to chunks that contain fd and bk nextsize pointers
as skip chunks.
In this case, the first 0x430 chunk would have an fd_nextsize that points to the first
0x410 chunk because there are no 0x420 chunks.
That 0x410 chunk would have an fd_nextsize that points to the 0x400 chunk and the 0x400 chunk's
fd_nextsize would complete the circle, pointing back to the first 0x430 chunk.
Of course, the bk_nextsize pointers do the same in the opposite direction.
When a chunk is linked into a largebin, if it's the only one of its size, it becomes a skip chunk
and is linked into both the largebin itself and that bin's skip list.
When subsequent chunks of the same size are added, rather than disturb the skip list, they're simply
linked into the bin after their skip chunk.
For example, if we were to sort a 0x430-sized chunk into this largebin, it would be added
here and would only receive fd and bk pointers.
The same goes for 0x430-sized allocations, they're taken from the head of the
0x430 skip list, meaning that once a chunk becomes a skip chunk, it will always be the last chunk
of its size to be allocated.
Likewise, 0x410 chunks will be added and removed from the bin at this location and any
0x400 chunks will be added after the 0x400 skip chunk.
Since the 0x400 chunk is currently the only one of its size in this largebin, it would be allocated
to serve the next 0x400-sized request, causing the skip list to be rerouted.
If a 0x420-sized chunk were to be sorted into this largebin, it would be the first of that
size and therefore not only get linked into this bin after the last 0x430 chunk, but also linked
into the skip list between the 0x430 and 0x410 skip chunks.
If you want to experiment with the largebins, the malloc testbed is the perfect place to do it.
There's also a largebins section in the HeapLAB PDF.
For now, armed with this knowledge, let's see if we can link a fake chunk into a largebin via the
House of Lore. I'll edit my smallbins exploit in place,
you can do the same or you can work from the last lecture's solution script.
We're going to start by freeing not one but two chunks into the 0x400 largebin, the reason for which
will become clear shortly.
Change chunk A's size to 0x400 by requesting 0x3f8 bytes of user data and do the same
to chunk B.
Of course, chunks A and B will get consolidated together when we free them, so we'll need to request
a guard chunk between them to stop that from happening.
And another after chunk B to avoid consolidation with the top chunk.
We know that large chunks make their way into the largebins via the unsortedbin, so let's free both
chunks A & B into the unsortedbin.
Once they're there, we can request a larger chunk to trigger an unsortedbin search, sorting both
chunks into the 0x400 largebin.
Comment out of the rest of the script for now, then run it with the GDB and NOASLR options.
Break in GDB, then issue the 'heap' command.
Whilst 'vis' is a great for seeing a detailed heap representation with each chunk's user data, when
you're dealing with multiple large chunks, the 'heap' command's overview can be more compact.
We can see from its output that chunk A and chunk B are both annotated as free chunks linked into the
largebins, confirmed with the 'largebins' command.
They're both 0x400-sized with fd and bk pointers forming a doubly-linked circular list.
Notice that chunk A has become the 0x400 skip chunk, we freed chunk A before chunk B, meaning that it was
linked into the unsortedbin first, making it the last chunk in that list. The unsortedbin is searched
from back to front
so when we requested a 0x410-sized chunk, chunk A was the first to be sorted into the
0x400 largebin, followed by chunk B.
Chunk A is linked into both the 0x400 largebin and its skip list, we can see its fd and bk
nextsize pointers here forming another doubly-linked circular list.
Since there are only 0x400-sized chunks in this bin right now, those pointers simply point back to the
0x400 skip chunk.
It's worth noting that chunk B's nextsize pointers are null, this isn't by chance, large chunks have
their nextsize pointers nulled when they're linked into an unsortedbin.
This is because the unlink macro or function uses the presence of these pointers to determine whether
a chunk needs to be unlinked from a skip list.
So if we want to link a fake chunk into this 0x400 largebin then successfully allocate it, the first question
we need to answer is which of these lists should we target, the skip list or the bin itself?
The answer is either, even though the path through malloc will differ slightly, the prerequisites for
our fake chunk are identical.
If we're targeting a skip list, we'll need to corrupt a large chunk's bk_nextsize pointer.
If we're targeting a largebin itself, corrupting a regular fd is required.
We'll start by corrupting chunk A's fd.
The reason we're targeting a forward pointer rather than a backward pointer is this code snippet from
the largebins allocation routine.
Once malloc has found an appropriately-sized chunk by iterating backwards over a largebins list,
as indicated by this comment, it tries to avoid allocating the skip chunk itself.
Two checks are performed to ensure that the next chunk in the largebin is an allocation candidate,
first malloc determines whether the skip chunk is the last chunk in the bin by following its
largebins bk and seeing if it ends up back at the same skip chunk.
If it isn't the last chunk in the bin, malloc follows the skip chunk's fd and checks if the chunk
at its destination matches the size of the skip chunk.
If it does, that next chunk is allocated instead of the skip chunk. This means that if we want to
allocate our fake chunk this way, its size needs to match that of the chunk we're tampering with.
Note that chunks removed from a largebin are always subject to a full unlink, since they could be
allocated from the middle of a largebin.
This means that our fake chunk will have to pass the safe unlinking checks, which we already know
how to do.
Close GDB and return to your editor, where we'll prepare our fake chunk and link it into the
0x400 largebin.
Let's uncomment the line in which we leverage the write-after-free bug to tamper with chunk A's metadata.
Remove the first null quadword so that we end up overwriting chunk A's fd with the address of our fake
chunk.
Remember that when we do this, chunk A will be a 0x400 skip chunk in the 0x400 largebin.
Next, let's prepare our fake chunk metadata.
Throw out what's there from the smallbin variant and add the following:
A null quadword to fill the unused prev_size field,
a size field that matches chunk A's size, in this case 0x401.
This must match chunk A's size field exactly, including the flags, because malloc uses a macro named
chunksize_nomask() to make this comparison, which does not mask any bits of either size
field.
Will also need to forge forward and backward pointers for our fake chunk that pass the safe unlinking
checks, we've done this before by pointing them both at their own chunk.
Once you've made those changes, run your script with the usual options so we can check everything before
requesting our fake chunk.
Break and inspect the heap with the 'heap' command.
Chunk A is first on the list, and if we dump memory at the "user" struct where our fake chunk resides,
we can see that chunk A's fd points to our fake chunk.
Our fake chunk's size field matches that of Chunk A.
And our forged fd & bk are set up to pass the safe unlinking checks.
Something that we haven't considered are the values of our fake chunk's nextsize pointers.
The unlink macro uses a chunk's fd_nextsize field to determine whether it should be unlinked from a
skip list as well as its parent list.
Remember that large chunks have their nextsize fields nulled out as they're linked into an unsorted
bin.
In our case, the fake chunk's fd_nextsize is null, so we don't have to worry about it.
But if we had to write something other than a null quadword here, both nextsize fields would also
have to pass safe unlinking checks.
Nextsize safe unlinking was introduced in GLIBC version 2.21.
So we're ready to allocate our fake chunk and overwrite the target data. When we request a 0x400-
sized chunk malloc will end up searching the 0x400 largebin.
It will use the skip list to find a skip chunk with size larger than or equal to the size we've requested,
in this case
chunk A. Since chunk A is not the last chunk in the list, malloc will follow its corrupt forward pointer
to our fake chunk to determine whether it is an allocation candidate.
Since our fake chunk size matches that of chunk A, malloc will unlink it, then allocate it.
Let's close GDB and return to our editor, where we'll make that last request and overwrite our target data.
You can remove the next call to the malloc() helper function, then uncomment the next one, replacing
the request size with 0x3f8,
that should allocate our fake chunk.
Lastly, uncomment the call to the edit() helper function that overwrites the target with our own
data.
Now, run your exploit under production conditions without the GDB and NOASLR options.
Hit return to print the menu, then pick option 4 to print the target data, which confirms that
we've successfully leveraged the House of Lore largebins variant to make an arbitrary write.
Once again, there were more constraints here than in the unsortedbin variant, we needed an accurate
size field for our fake chunk, forward and backward pointers that could pass the safe unlinking
checks and nextsize pointers that could either do the same or were null.
At least we didn't need a heap leak.
In this example, we corrupted an fd belonging to a free chunk in the largebins, but we could also
have corrupted its bk_nextsize pointer instead.
I'll add three padding quadwords to our edit() helper call, moving the pointer to our fake chunk from
chunk A's fd to its bk_nextsize pointer.
This has the advantage of allowing the victim to be the last in its bin, so I can also remove chunk B
from the equation.
On top of that, we can now take advantage of the fact that allocations from the largebins are an implicit
remainder operation to change our fake chunk size.
We can even set it to a value that shouldn't be in the 0x400 largebin.
Running the exploit under production conditions yields the same result.
We're going to leave the House of Lore there, dropping a show with this technique may be possible,
but it's best leveraged to do what we've just done, allocate fake chunks overlapping sensitive program
data.
The binary does leak a libc address though, so if you want to take a crack at dropping a shell
from it, you're welcome to try.
If you want to review anything we've covered in all three House of Lore variants, the PDF contains the
malloc internals,
the malloc testbed is a great tool for watching malloc at work and developing your exploits,
and you can download a commented solution script for the House of Lore largebins variant from this lecture's
resources.
Up next, we'll be dealing with poison null bytes and eventually dropping a shell from our most difficult
challenge binary yet.