Heap overflow
Last updated
Last updated
This is an unlink method vulnerability in Doug Lea's malloc. The hint offers a well-written explanation. This challenge is an example taken from Secure Coding in C and C++. A complete analysis of the example exists in the book (section 4.6, Doug Lea's Memory Allocator, a.k.a. dlmalloc), and this writeup is inspired by it.
Doug Lea’s malloc manages the heap and provides standard memory management. In dlmalloc, memory chunks are either allocated to a process or are free.
Free chunks are organized into double-linked lists. Each free chunk also contains forward and backward pointers to the next and previous chunks in the list to which it belongs. These pointers occupy the same 8 bytes of memory as user data in an allocated chunk. The first 4 bytes of both allocated and free chunks contain either the size of the previous adjacent chunk, if it is free, or the last 4 bytes of user data of the previous chunk, if it is allocated.
Both allocated and free chunks make use of a PREV_INUSE bit (represented by P in the figure) to indicate whether or not the previous chunk is allocated. Since chunk sizes are always a multiple of 2, the least significant bit is always empty and therefore can be used to indicate whether the previous chunk is in use or not.
Each double-linked list has a head that contains forward and backward pointers to the first and last chunks in the list
There are bins that hold chunks of a particular size to allow a correctly sized free chunk to be quickly found. Memory chunks are consolidated during the free() operation. The chunks before and after the chunk to be freed are inspected. If either of them is also free, it is merged with the chunk to be removed and the combined chunk is placed into the appropriate bin.
unlink() macro:
Steps to unlink:
FD = P->fd;: assigns FD so that it points to the next chunk in the list
BK = P->bk;: assigns BK so that it points to the previous chunk in the list
FD->bk = BK;: the forward pointer (FD) replaces the backward pointer of the next chunk in the list with the pointer to the chunk preceding the chunk being unlinked
BK->fd = FD;: the backward pointer (BK) replaces the forward pointer of the preceding chunk in the list with the pointer to the next chunk
The unlink technique is used to exploit a buffer overflow to manipulate the boundary tags on chunks of memory to trick the unlink() macro into writing 4 bytes of data to an arbitrary location.
Just pwn this using a heap overflow taking advantage of douglas malloc free program and get a flag. Its also found in /problems/heap-overflow_4_3753f93c50c60685d83eea78243a85a0 on the shell server. Source.
Three buffers are allocated:
Visual of the heap after the allocations are done:
The sizes are a result of taking the size that the user requested, adding 4 for the size DWORD itself and rounding up to the next multiple of 8 bytes.
It is recommended to send -4 for the bytes containing PREV_INUSE since this number is even, has no NULL bytes and is interpreted as a large unsigned int which ensures that no fastbin-related logic will be involved.
The payload we'll be sending as input for gets(fullname) will be as follows:
The above shell code makes the heap loop as follows (as described in step 4):
The address -12 is included in the malicious argument so that the unlink() method overwrites the address of the free() library call with the address of the shellcode. The shellcode jumps over the first 12 bytes because some of this memory is overwritten by unlink() when making the assignment BK->fd = FD.
The "Adapted shellcode" section of the hint was influential in creating the shellcode. The simple way out is to prefix our favourite shellcode with a 12-byte header:
Run the script.py to run the exploit and get the flag python script.py USER=<username> PASSWORD=<password>:
picoCTF{a_s1mpl3_h3ap_222e5b52}
Because the vulnerable buffer is allocated in the heap and not on the stack, the attacker cannot simply overwrite the return address to exploit the vulnerability and execute arbitrary code. However, we can overwrite the length of the second chunk of memory, as shown below, because this boundary tag is located immediately after the end of the first chunk.
We can overwrite the size field in the second chunk with the value -4 by overflowing fullname by 4 bytes. Therefore, when free() attempts to determine the location of the third chunk by adding the size field to the starting address of the second chunk, it instead subtracts 4. free() is trying to determine if it should consolidate the first and second chunks. But, in order to determine if the second chunk is allocated, it needs to look at the PREV_INUSE bit of the third chunk. By setting the length to -4 we can trick Doug Lea’s malloc into thinking that the start of the third contiguous chunk is 4 bytes before the start of the second chunk. If we write an even number (one where the PREV_INUSE is 0) in the 4 bytes before the length then malloc will see the second chunk as unallocated. Thus, the free() operation invokes the unlink() macro to consolidate the two chunks.
