PLAY WITH LINUX HEAP

作者:
memeda@0ops
pwner.xu@gamil.con

BACKGROUND

Linux heap become hard to exploit due to the new version of GLIBC.
- Hundreds of thousands of assertions there.
- ASLR and Non-eXecutable heap.
Heap issues are scarce in CTF games.
- spring up in recent games like HOTCON CTF & Hack.LU CTF.

CATALOGUE

Introduction to GLIBC Heap
View Heap As an Attacker
- free()
- malloc()
- main_arena
- mmap() & munmap()
Examples

Introduction to GLIBC Heap

GLIBC Heap Structure

chunk头包括以下两部分：
prev_size: 如果当前chunk的相邻前一chunk未被使用，prev_size为此前一chunk的大小
size: 当前chunk的大小。由于chunk大小是8的整数倍，所以此size的后3 bit被用于存储其他信息。我们需要记住的便是最低bit，用于指示前一chunk是否已被使用( PREV_INUSE )。
如果当前chunk处于未被使用状态，则mem前8 bytes被用来存储其他信息，具体如下：
fd: 下一个未被使用的chunk的地址
bk: 上一个未被使用的chunk的地址
可以看到，chunk头中包含的大小信息，主要用来在获取内存中相邻chunk的地址（当前chunk地址减去前一chunk的大小，为前一chunk的地址；当前chunk地址加上当前chunk的大小，为后一chunk的地址）。而mem中的fd和bk只在当前chunk处于未被使用时才有意义。如果了解数据结构，便可以立刻看出，这些未被使用的chunks通过fd, bk组成了链表。事实上，malloc确实维护了一系列链表用于内存的分配和回收，这些链表被成为”bins”。
一般来说，每个bin链表中的chunk都有相同或将近的大小。根据bin所包含chunk的大小，可以将bin分为fastbin, unsorted bin, small bin, large bin。

the range of a chunk is between LABEL Chunk and LABEL Next Chunk
PREV_SIZE represents the size of the previous chunk(in memory) only if the previos chunk is free()’d.
SIZE represents the number of bytes between LABEL Chunk and LABEL Next Chunk. If the lowest bit of SIZE is cleared as 0, then the chunk before it is not in use(free).
LABEL Mem makes sense only when this chunk is malloc()’d by user. &Mem is considered as the return value of malloc().
For chunks of certain size range, there is a free list which is a linked list.
FD represents the forward pointer to the next chunk in the linked list.
BK represents the backward pointer to the previous chunk in the linked list.
The above two fields only make sense when the chunk is free()’d
User’s data is stored in the region which starts at LABEL Mem. Notice that the region includes PREV_SIZE of the next chunk.

View Heap as an Attacker — free()

CORRUPT FREE 1

Let’s begin at function free() but not malloc().
In the old version of GLIBC, there is a classical exploition of heap overflow with free().

PROTOSTAR HEAP 3

In old version of GLIBC malloc, there is function called unlink():

If BK and FD is controlled by us, then (in Linux x86)
- *(FD + 12) = BK && *(BK + 8) = FD
- AN ARBITRARY WRITE!
Then the problem comes, why unlink() is called when 3 free()s called? Since free() means linking the chunk into the free list.
THE ANSWER is when GLIBC free a chunk, it will go to see whether the chunk before/after is free. If it is, then the chunk before/after will be unlink()’d off its double-linked list and these two chunks merge into one chunk.
So for this problem, you can overflow chunk a and overwrite the heap header of chunk b.
If you set the lowest bit of SIZE of b to 0, then GLIBC fooled to consider chunk a free()’d. Then unlink() is called on chunk a.

SIZE represents the number of bytes between LABEL Chunk and LABEL Next Chunk. If the lowest bit of SIZE is cleared as 0, then the chunk before it is not in use(free).

You can also set PREV_SIZE f chunk b to fool GLIBC where the chunk b begins. Craft a fake chunk b there and get an arbitrary wirte.

MODERN UNLINK

New checking: FD->bk \== P && BK->fd \== P

CORRUPT FREE 2

Let us have a look at Problem stkof from HITCON CTF 2014.
Pwnable worth 550 points. It is still available on httpL//ctf2014.hitcon.org/dashboard.html.
The scenario is simple:
- You can give a size and malloc a chunk of the size.
- There is global arrary which records the pointer of every chunk you malloc()’d.
- You can write arbitrary long content into the pointer in the global array.
- You can free any of the chunk you malloc()’d before.
- There is a global variable record the times you malloc()’d.

PWNABLE PROBLEM STKOF

In this scenario, there is a variable counting how much chunk you’ve malloc()’d. Here it is 3 at 0x602100.

3 chunk’s pointer are stored in a global arrary at 0x602140, which is 0xe05010, 0xe05040 and 0xe050d0(Remember is is what we called LABEL Mem).
We can also writing anything long into the data area these pointers pointing to.

CORRUPT FREE 2

Heap Overflow with free()’ called, everything is nice except that
- FD->bk ?= P
- BK->fd ?= P
When facing this, the MOST IMPORTANT thing is that find somewhere in the memory in which the value is P.

PS: Geohot’s futex exploit trick(0x00bf0000) to bypass plist checking in Android Kernel.

In this problem, there is a global arrary which stores all the pointer pointing to all the chunk. Notice that this pointer is pointing to LABEL &Mem but not that start of the chunk!
So we need to craft a fake chunk at &Mem. That is not very difficult because we have heap overflow whcih means the whole control of the content of the chunk on the heap.
Another restriction shown in the code before is the if clause.
- Just set P->fd_nextsize to NULL then skip if.
EXP from acez@Shellphish

http://github.com/acama/ctf-writeups/blob/master/hitcon2014/stkof/x.py

As you can see, the exploit overwrite chunk 3, place a fake chunk at the location of chunk 4.
The fake heap header of chunk 4 fool GLIBC to believe that chunk before chunk 4 is chunk 2.
There is a fake chunk 2 at chunk 2’Mem. Notice that 0x602150 is the pointer in the global array which pointing to chunk 2’s Mem(key point here to bypass the chunk!).
Call free(4) to unlink fake chunk2. Then after unlink, an address in the range of &global_arrary itself is written into the global arrary. That means we can rewrite the content of the global arrary directly.
If we control the global array, then wen can control which pointer we can write into.
This is a case about heap overflow where SPECIFIC WRITE turns into ARBITRARY WRITE！

Always keep in mind

When malloc() returns, it gives you the pointer pointing to LABEL Mem.
When processing some stuff in malloc.c, the pointer of a chunk(whose type is struct malloc_chunk * ) is pointing to LABEL Chunk.

POISINED NULL BYTE

In August Zero released a post about a GLIBC NULL byte off-by-one exploitation.
The null byte will clear all the status bits of the SIZE of the next chunk.
- The PREV_SIZE is actually the user data of the chunk but now it will used to locate the chunk
The exploit decribed in the post is a local unprivilrge exploit with Linux 32bit, which means we could half-disable ASLR and things become easy.

The exploit regerred in the post used fd\nextsize and bk-nextsize to do the arbitrary write which is also a way besides directly use fd and bk.

P->fd_nextsize should not be NULL.
FD->fd_nextsize should not be NULL.

However, the target in the post is Fedora where that two aserts do not exist. When it comes to Ubuntu, Fail.

View Heap as an Attacker — malloc()

CHEAT MALLOC 1

free()’d chunks which has a size in certain range will be put into one free list.
The head of the free list is in main_arena which will be covered later.
The basic idea of the section is to CHEAT GLIBC to malloc the chunk to the special place you want to. Then you can write to that heap chunk, which means that you write to that special place.
If there are some important pointers or data structures at that special place, then it is easy to finish the exploit then.

begin with an easy example – fastbin

When the chunk’s size is small enough, GLIBC called it fastbin.
Different sizes of fastbins also have their free list, but this time it is a single-linked list.
The single-linked list makes things much easier.

This picture shows two fastbins in the free list which both have a size of 0x30.

Single-linked list header 0x7fff7bd1770 pointing to Chunk 0x00e05090.
Chunk 0x00e05090’s FD pointing to Chunk 0x00e05030.
Chunk 0x00e05030’s FD is NULL, the end of this linked list.

How does GLIBC work when malloc()ing a fastbin?

It just mainly pick out the first (->fd) fastbin in the linked list, and return it to the user.
That meas if we control just one node of this linked list, then we can cheat GLIBC to malloc the chunk where specified by us.
maclloc two fastbins.
1. Free the 2nd fastbin.
2. Overflow the 1st fastbin to change 2nd fastbin’s FD to our specified value.
3. Malloc one time. GLIBC return the 2nd fastbin to us, meanwhile the header of the single-linked list points to our specified value. The value points to a fake fastbin entry we crafted already.
4. Malloc anather time.
5. Then just write into the new chunk which birth at the specified place you want to and finish your exploit.
EASY to exploit since single-linked list is less troublesome, comparing with double-linked list with countless security check with normal bins in the new version of GLIBC malloc.c.
The only check for the fastbin entr in the list is the SIZE! Craft a proper size for the fake fastbin entry.
- Recall the problem STKOF, where the fakebin could be?
- There is a counting variable at 0x602100, just add it up to a proper value and it somehow could pretend to be SIZE right?(the fake chunk at 0x602100 - 0x8)
If you can free any where you want, then just free the place you could write(craft) directly. You don’t necessarily need to work on the heap and do the overflow.
Or if you can overwrite the malloc()’d pointer to a specia=fy value and then free it, also take the same effect.
- This scenario is mentioned in phrack Malloc_Des-Maleficarum.

CHEAT MALLOC 2

Whether malloc() with normal bins and double-linked can be cheated

I malloc 7 chunks with normal size and free 3 of them. As you can see, they are both in one double-linked list.

Then I do malloc(0x212).

As you can see, strange things happen. Now two double-linked lists there.
In fact, double-linked list(0x7ffff7bd17b8) is called the unsorted bin’s free list.
double-linked list(0x7ffff7bd19b8) is the real list for the real free list for the chunk with size 0x210.
At first, all the free()’d chunks are put in to unsorted bin list.
When alloc() comes, GLIBC travels from the BK of the header of the unsortd bin list.
- If the size is fit, then unlink this chunk and return to the user.
- If not, put this chunk into its free list according to its size.
I am going to give an illustration about exploiting this.

Overflow Chunk 0xe05210 to change 0xe05630’s BK to an address which points to a craft heap chunk. The chunk has a right SIZE(0x211).]

As you can see, after I malloc(0x212), the header of the unsort bin list’s BK points to my fake chunk at 0xe10000.

A very important thing is that during the process shown before, there is NO CHECKING like P->FD->BK == P AND so on.
And after this, you are able to cheat GLIBC to malloc at the place you want(int this case 0xe10000). But during this, Chunk 0xe10000 will be unlinked so make sure its BK->FD points to 0xe10000 this time.
For this case, I just bring out my ideas. Let me know if you have other nice ways to exploit it.

CHEAT MALLOC 3

There is another important concept called wilderness or the top chunk.
In a word, if there is no proper chunk in the free list, then GLIBC will splice a certain size out of the top chunk and then return it to ther user.
That means the top chunk usually has a large SIZE and be located at the bottom of the heap (behind all the normal heao chunks).
Malloc_DES-Maleficarum also described a trick which cheats malloc by using the top chunk.
1. You can use overflow to change the SIZE of the top chunk to 0xffffffff(Linux x86).
2. Then you just malloc, and if the control flow goes into use_top, then actually you can malloc whatever large size you want.
3. You can craft a special size s. Then after malloc()ing, the top chunk’s address will change to the original address plus s. In fact, we can specify any new address we want by specifying s.
4. If we malloc again, then we could get a chunk at the special place we want.
This trick may not make sense when meet ASLR since at most time the location of the top chunk cannot be predicted.

View Heap as an Attacker — main_arena / predict heap chunk’s location despite ASLR

MAIN_ARENA

It’s time for us back to the most basic and important structure main_arena.
Hack the core then we control all.
main_arena is defined as below(Linux x86_64)

It is a structure of type malloc_state and size is 0x888.
Array fastbinY
- The Value in each entry represents the head of (single-linked) free list of the fastbins whcih has a size in certain range.
Top
- It is the top-most chunk. When there is no good target chunk for a new malloc request in these free lists, it is used.(label use_top in function _int_malloc)
Array bins
- Heads of all the (double-linked) free list of different size ranges.
next
Pointing to the next arena.
system_mem
Memory allocated from the system in this arena.

FAKE MAIN_ARENA

A POINTER pointing to arena structure is near TLS.
- How to use heap overflow to rewrite it? I’ll talk about it later.
Now, let us have a discussion on how to do an exploitation when we could specify the arena which we can fully controlled.
The main idea is to specify the head of the linked list in the arena, and then cheat GLIBC to malloc a new chunk at that specified place we prefer.
But thing are not very easy. The specified place(the fake chunk) must satisfy many conditions, otherwise malloc will go to failure.

FIGHTING WITH ASSERTIONS

Let us trace back the source.
Before _libc_malloc exit, there is an assert on victim, the chunk which is going to return to you.
1. If victim == NULL, just don’t care this
2. If the chunk is labelled mmapped
  - a chunk is mmapped when its SIZE has 0x2 bit set.
3. If ar_ptr == victim’s arena ptr
  - Due to the faked arena we crafted, chunk_non_main_arena will return true.
    - If the SIZE has 0x4 bit set, it means NON_MAIN_ARENA.
  - And it is very hard to control the value which address (ptr & ~(HEAP_MAX_SIZE - 1)) pointing to.
    - It is very hard to control on Linux x86_64. If ptr is not big enough, it will cause NULL pointer dereference.
- So in a word, the best choice is to satisfy [2] and then bypass this assert.

BTW
Actually when we call free(p), it weill call arena_for_chunk(p) to get the arena of the chunk.
What if we use heap overflow to set a chunk’s NON_MAIN_ARENA bit?
it will then try (ptr & ~(HEAP_MAX_SIZE - 1))->ar_ptr to get the arena pointer…
That may cause problems, which is mentioned in phrack Malloc_Des-Maleficarum.

To satisfy [2], you faked chunk’s SIZE should have 0x2 bit (mmapped).
If you deep into _int_malloc, you will find out that sometimes before it return p; to exit, it will finally reset the head of the chunk which it will then return to you, which means you’ll lose the 0x2 bit.
We do not hope that happeds.
3 scenarios where the head of our crafted chunk wont’t be reset
- fastbin size range;
- corresponding small bin’s free list is not empty;
- a free()’d candidate chunk in unsort bin free list and the size of free()’d candidate chunk in the free list is exactly the same as our crafted chunk’s size.
Again,fastbin becomes our first choice, since we must deal witg FD and BK when use whether normal small bin or normal large bin.
[1] A crafted chunk you want to malloc on which has a proper SIZE(0x2 bit set).
- Remember an non-NULL illegal FD of this chunk will not make a crash during this malloc() but will bring a side effect in the furture.
- [2] The entry of fastbinY’s free list should be set to the address of your crafted chunk.(&SIZE - 0x8 on Linux x86_64).

A FAKE ARENA EXAMPLE

you do not need to specify the whole 0x888 bytes. For example, if you use fast bin to exploit, you may must specify the first several bytes.

DEFEAT ASLR

Where is the problem of main_arena? How could we touch it?
If the size you want to malloc is not less than 128KB, then GLIBC may use mmap() to allocate a new area for you.
There are many gaps in the program’s VM map, and GLIBC will use these large gaps to satisfy your malloc request.

main_arena is in the marked area(TLS is there), and if we can malloc a chunk before this arena nad overflow it, then we can overwrite main_arena.

Although the existence of ASLR, I would like to say that it is possible to know it is possible to know it is the time I malloc()’d just before TLS.
In fact, the location of the chunk you malloc()’d could be predicted even on Linux x86_64.
Consider a program(stkof) which doesn’t have any chunk malloc90d before the user’s input comes.
[1] Then I try to malloc(2147483648) as many times as possible.
[2] And then I malloc(135168).The chunk will be located just before TLS. I will fill it with As to give an illustration.
Note that all the malloc()s in [1] & [2] will actually call mmap().

The chunk just before arena is located at 0x7f0313248010. And with no surprise, the pointer of arena is at 0x7f031326a700. So, it is able to overflow it for sure. Btw, the stack canary is at 0x7f031326a768.

Before the pointer of the arena, there are some values.
Actually most of these values can just be overwritten to 0x0 except the first entry(which is located at 0x7f031326a690 in the previous picture).
- Its symbol is _nl_global_lacale.
- And is used in ____strtoll_I_internal.

We should put an accessible pointer for a fake _nl_global_locale. And think it as %r8, make sure that these will not cause a segmentation fault:

mov 0x8(%r8), % rax
mov 0x68(%r8), %r15
testb $0x20, 0x1 (%r15, %rax, 2)
- Here %rax usually range from ord(‘0’) to ord(‘9’)

OK! Now just replace the pointer of the arena with an address which a fake arena structure is located at there.
BUT! Due to ASLR, you may not know the exact address of your fake arena structure……

Actually there are two gaps and the location of the two gaps are easy to predicted.

When I malloc() for hundreds of thousands of times, the process will try its best to bring out its virtual memory to satisfy my demand.
And finally the chunk will be located between 0x10000 - 0x400000 and 0x401000 - 0x601010.
AS you can see, I get two chunk, one is at 0x10000 and one is at 0x4010000.
You can just put the fake arena and the fake _nl_global_locale in the 0x10000 chunk and then overwrite the pointer of the arena to 0x10010 (0x10000 + 0x10 is the beginning of the user data).

FURTHERMORE

The main_arena exploit on x86 is much more easier so I do not mention here.
A writeup from 217 refers this:
http://217.logdown.com/posts/241446-isg-2014-pepper

View Heap as an Attacker – mmap() and munmap()

OWN THE PAGE

A trick
Turn a r-- page into rw- page without calling mprotect() or even unmap .text page.
Special thanks to jerry@217 for sharing this idea.
As is mentioned before, if a chunk’s SIZE has 0x2 bit, it means this chunk is MMAPPED.
And if we want to free a MMAPPED chunk, GLIBC will not call free() routine for normal heap chunk but munmap()!
If you could overwrite the SIZE of a chunk, set its 0x2 bit and any large size you want, then free it!
- The memory of the size will be directly kicked out!

Malloc()’d for thousands of times to push GLIBC to malloc a chunk at 0x300000 and 0x200000.
Overflow the chunk at 0x200000 to make 0x300000’s SIZE to 0x200002.
0x400000 - 0x401000 is .text section of the process.

It is really interesting right? Memory from 0x300000 to 0x500000 is munmap()’d by me. $rip is at 0x400b7f but it is an illegal address now!

GOT is in the marked page. We could allocate a chunk in 0x401000-0x601000, overflow it and rewrite GOT.

The sad thing is that if we want to overwrite GOT, we must cross 0x601000-0x602000, but however this page is non-writable!

Use heaop heapoverflow to change the SIZE of chunk to 0x101002. Then free it!

With no surprise, memory from 0x501000 to 0x602000 is kicked out.
That means the non-writable page has already gone away.

If we malloc(1052600), Non-writable page 0x601000-0x602000 will never be existed. Just overflow it to write GOT!

It is a very interesting trick about mmap() and munmap() in GLIBC heap menagement.
Keep in mind that the fake SIZE of the chunk you set must be times of a page size, due to ASSERT