Nop's Blog HomeArchivesTagsCategoriesAbout
Learning Windows pwn -- Nt Heap
|LearningNotes
Word count: 5.1k|Reading time: 20 min

最近正学习windows下的堆利用，本着扩展知识面再加上以后很大概率会用到的想法，从零开始学起，主要是从AngelBoy大神的Slides里面，再加上网上搜到的各种资料以及手动调试分析，试着去了解一下windows heap的管理机制。

不同于linux，由于windows是闭源的，一下子难以摸清，所以该篇会不断更新，目的仅是为了加深印象以及作为以后的参考。

Win10内存管理机制概览

根据AngelBoy的Slides，Win10下的堆管理基址十分复杂，主要分为：

  • Nt Heap: 默认使用的内存管理机制
  • SegmentHeap：Win10中全新的内存管理机制

且其中SegmentHeap为部分系统程序以及UWP(Universal Windows Platform)使用，所以从这个角度来说，我们暂时只学习Nt Heap的内容，其他部分待未来学习加以补充。

Nt Heap Overview

分析内存管理管理机制，当然同样是从malloc和free入手，借用一程图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
                                                                                        (Front-End)
                                                                                        +-------------------------------+
                                                                                        |           ntdll.dll           |
                                                                                        +-------------------------------+
                                                                                        | +---------------------------+ |
                                                                      +-------------->  | |    RtlpLowFragHeapAlloc   | |
                                                                      |                 | |    RtlpLowFragHeapFree    | |
                                                                      |                 | +---------------------------+ |
                                                                      |                 +-------------------------------+
                                                                      |                                | 
                                                                      |                                | 
                                                                      |                     (Back-End) V  
+---------------+         +---------------------+         +-----------------------+         +-----------------------+
| msvcrt140.dll |         |     Kernel32.dll    |         |       ntdll.dll       |         |       ntdll.dll       |
+---------------+         +---------------------+         +-----------------------+         +-----------------------+
| +-----------+ |         | +-----------------+ |         | +-------------------+ |         | +-------------------+ |
| |   malloc  | |  ---->  | |    HeapAlloc    | |  ---->  | |  RtlAllocateHeap  | |  ---->  | |  RtlpAllocateHeap | | 
| |    free   | |         | |    HeapFree     | |         | |    RtlFreeHeap    | |         | |    RtlpFreeHeap   | |
| +-----------+ |         | +-----------------+ |         | +-------------------+ |         | +-------------------+ |
+---------------+         +---------------------+         +-----------------------+         +-----------------------+
                                                                                                       |
                                                                                                       |
                                                                                                       v
                                                                                                 +------------+
                                                                                                 |   Kernel   |
                                                                                                 +------------+

同时，从使用的角度来看，Win10堆可以分为两种：

  • 进程堆：整个进程共享，都可以使用，会存放在_PEB结构中。
  • 私有堆：单独创建的，通过HeapCreate返回的句柄hHeap来指定。

用一个程序简单测试一下，该测试程序主要是从一个新分配的私有堆上通过HeapAlloc不断分配空间：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <Windows.h>
#include <stdio.h>

int main(void)
{
    void *ptr[30] = { NULL };
    HANDLE hHeap = HeapCreate(0, 0x10000, 0);

    int i;

    for(i = 0; i < 30; i++)
    {
        ptr[i] = HeapAlloc(hHeap, 0, 0xF0);
    }

    for(i = 0; i < 30; i++)
    {
        printf("[+] chunk[%02d] address is: %p\n", i, ptr[i]);
    }

    return 0;
}

从输出中可以看出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
[+] chunk[00] address is: 0000000000B50860
[+] chunk[01] address is: 0000000000B50960
[+] chunk[02] address is: 0000000000B50A60
[+] chunk[03] address is: 0000000000B50B60
[+] chunk[04] address is: 0000000000B50C60
[+] chunk[05] address is: 0000000000B50D60
[+] chunk[06] address is: 0000000000B50E60
[+] chunk[07] address is: 0000000000B50F60
[+] chunk[08] address is: 0000000000B51060
[+] chunk[09] address is: 0000000000B51160
[+] chunk[10] address is: 0000000000B51260
[+] chunk[11] address is: 0000000000B51360
[+] chunk[12] address is: 0000000000B51460
[+] chunk[13] address is: 0000000000B51560
[+] chunk[14] address is: 0000000000B51660
[+] chunk[15] address is: 0000000000B51760
[+] chunk[16] address is: 0000000000B51860
[+] chunk[17] address is: 0000000000B50750
[+] chunk[18] address is: 0000000000B54470
[+] chunk[19] address is: 0000000000B55670
[+] chunk[20] address is: 0000000000B54070
[+] chunk[21] address is: 0000000000B54170
[+] chunk[22] address is: 0000000000B54370
[+] chunk[23] address is: 0000000000B55770
[+] chunk[24] address is: 0000000000B54270
[+] chunk[25] address is: 0000000000B54C70
[+] chunk[26] address is: 0000000000B54A70
[+] chunk[27] address is: 0000000000B55C70
[+] chunk[28] address is: 0000000000B55070
[+] chunk[29] address is: 0000000000B54570

前17个chunk地址间隔固定，是由Back-End直接分配的；而后面的chunk地址开始变得随机，是由Front-End分配的。
也就是说，LFH机制是默认开启的，且只有在分配第18个chunk的时候才会开始启用。
至于底层细节，后文将会提到。

Back-End

一些重要结构体

_HEAP

_HEAP结构体作为一个堆管理结构体，存放着许多的metadata，存在于每个堆的开头：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
0:004> dt _HEAP
ntdll!_HEAP
    +0x000 Segment          : _HEAP_SEGMENT
    +0x000 Entry            : _HEAP_ENTRY
    +0x010 SegmentSignature : Uint4B
    +0x014 SegmentFlags     : Uint4B
    +0x018 SegmentListEntry : _LIST_ENTRY
    +0x028 Heap             : Ptr64 _HEAP
    +0x030 BaseAddress      : Ptr64 Void
    +0x038 NumberOfPages    : Uint4B
    +0x040 FirstEntry       : Ptr64 _HEAP_ENTRY
    +0x048 LastValidEntry   : Ptr64 _HEAP_ENTRY
    +0x050 NumberOfUnCommittedPages : Uint4B
    +0x054 NumberOfUnCommittedRanges : Uint4B
    +0x058 SegmentAllocatorBackTraceIndex : Uint2B
    +0x05a Reserved         : Uint2B
    +0x060 UCRSegmentList   : _LIST_ENTRY
    +0x070 Flags            : Uint4B
    +0x074 ForceFlags       : Uint4B
    +0x078 CompatibilityFlags : Uint4B
    +0x07c EncodeFlagMask   : Uint4B
    +0x080 Encoding         : _HEAP_ENTRY
    +0x090 Interceptor      : Uint4B
    +0x094 VirtualMemoryThreshold : Uint4B
    +0x098 Signature        : Uint4B
    +0x0a0 SegmentReserve   : Uint8B
    +0x0a8 SegmentCommit    : Uint8B
    +0x0b0 DeCommitFreeBlockThreshold : Uint8B
    +0x0b8 DeCommitTotalFreeThreshold : Uint8B
    +0x0c0 TotalFreeSize    : Uint8B
    +0x0c8 MaximumAllocationSize : Uint8B
    +0x0d0 ProcessHeapsListIndex : Uint2B
    +0x0d2 HeaderValidateLength : Uint2B
    +0x0d8 HeaderValidateCopy : Ptr64 Void
    +0x0e0 NextAvailableTagIndex : Uint2B
    +0x0e2 MaximumTagIndex  : Uint2B
    +0x0e8 TagEntries       : Ptr64 _HEAP_TAG_ENTRY
    +0x0f0 UCRList          : _LIST_ENTRY
    +0x100 AlignRound       : Uint8B
    +0x108 AlignMask        : Uint8B
    +0x110 VirtualAllocdBlocks : _LIST_ENTRY
    +0x120 SegmentList      : _LIST_ENTRY
    +0x130 AllocatorBackTraceIndex : Uint2B
    +0x134 NonDedicatedListLength : Uint4B
    +0x138 BlocksIndex      : Ptr64 Void
    +0x140 UCRIndex         : Ptr64 Void
    +0x148 PseudoTagEntries : Ptr64 _HEAP_PSEUDO_TAG_ENTRY
    +0x150 FreeLists        : _LIST_ENTRY
    +0x160 LockVariable     : Ptr64 _HEAP_LOCK
    +0x168 CommitRoutine    : Ptr64     long 
    +0x170 StackTraceInitVar : _RTL_RUN_ONCE
    +0x178 CommitLimitData  : _RTL_HEAP_MEMORY_LIMIT_DATA
    +0x198 FrontEndHeap     : Ptr64 Void
    +0x1a0 FrontHeapLockCount : Uint2B
    +0x1a2 FrontEndHeapType : UChar
    +0x1a3 RequestedFrontEndHeapType : UChar
    +0x1a8 FrontEndHeapUsageData : Ptr64 Wchar
    +0x1b0 FrontEndHeapMaximumIndex : Uint2B
    +0x1b2 FrontEndHeapStatusBitmap : [129] UChar
    +0x238 Counters         : _HEAP_COUNTERS
    +0x2b0 TuningParameters : _HEAP_TUNING_PARAMETERS

其中一些在利用中比较重要的成员：

  • EncodeFlagMask(+0x7C: 4B)：用来标志是否要encode该heap中的chunk头，0x100000表示需要encode。
  • Encoding(+0x80: 16B)：用来和chunk头进行xor的cookie。
  • VirtualAllocdBlocks(+0x110: 16B)：一个双向链表的dummy head，存放着Flink和Blink，将VirtualAllocate出来的chunk链接起来。
  • BlocksIndex(+0x138: 8B)：指向一个_HEAP_LIST_LOOKUP结构（后面会进行介绍）。
  • FreeList(+0x138 8B)：一个双向链表的dummy head，同样存放着Flink和Blink，将所有的freed chunk给链起来，可以类比于linux ptmalloc下的unsorted bin进行理解；不同的是，它是有序的。
  • FrontEndHeap(+0x198: 8B)：指向管理Front-End heap的结构体
  • FrontEndHeapUsageData(+0x1a8: 8B)：指向一个对应各个大小chunk的数组，该数组记录各种大小chunk使用的次数，达到一定数值的时候就会启用Front-End（可以配合前面的示例程序理解）。

_HEAP_ENTRY

对于每一个使用的堆块，也就是我们常说的chunk，在Win10下就是_HEAP_ENTRY：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
0:004> dt _HEAP_ENTRY
ntdll!_HEAP_ENTRY
    +0x000 UnpackedEntry    : _HEAP_UNPACKED_ENTRY
    +0x000 PreviousBlockPrivateData : Ptr64 Void
    +0x008 Size             : Uint2B
    +0x00a Flags            : UChar
    +0x00b SmallTagIndex    : UChar
    +0x008 SubSegmentCode   : Uint4B
    +0x00c PreviousSize     : Uint2B
    +0x00e SegmentOffset    : UChar
    +0x00e LFHFlags         : UChar
    +0x00f UnusedBytes      : UChar
    +0x008 CompactHeader    : Uint8B
    +0x000 ExtendedEntry    : _HEAP_EXTENDED_ENTRY
    +0x000 Reserved         : Ptr64 Void
    +0x008 FunctionIndex    : Uint2B
    +0x00a ContextValue     : Uint2B
    +0x008 InterceptorValue : Uint4B
    +0x00c UnusedBytesLength : Uint2B
    +0x00e EntryOffset      : UChar
    +0x00f ExtendedBlockSignature : UChar
    +0x000 ReservedForAlignment : Ptr64 Void
    +0x008 Code1            : Uint4B
    +0x00c Code2            : Uint2B
    +0x00e Code3            : UChar
    +0x00f Code4            : UChar
    +0x00c Code234          : Uint4B
    +0x008 AgregateCode     : Uint8B

其中一些比较重要的成员：

  • PreviousBlockPrivateData(+0x0: 8B)：由于需要对齐0x10，所以这个地方存放的基本上是前一个堆块的数据，和linux ptmalloc类似，只是处于free状态的时候不会作为prev_size使用。
  • Size(+0x8: 2B)：当前chunk的size，存放的是size >> 4之后的值。
  • Flags(+0xA: 1B)：当前chunk的标志：0x1表示处于占用状态、0x2表示存在额外描述、0x4表示使用固定模式填充、0x8表示VirtualAlloc、0x10表示为该段最后一个chunk。
  • SmallTagIndex(+0xB: 1B)：为Size和Flags成员共三字节数据的xor结果，即校验位，用于检查是否被修改。
  • PreviousSize(+0xC: 2B)：上一个chunk的size，同样存放size >> 4。
  • SegmentOffset(+0xE: 1B)：某些情况下用来找segment。
  • UnusedBytes(+0xF: 1B)：在inuse的时候，表示malloc之后剩下的chunk的空间大小，可以用来判断chunk是来自于Front-End还是Back-End；在freed的时候，恒为0。

另外，用户数据区域在inuse的时候可以进行读写，在freed的时候存放Flink和Blink分别指向前一个和后一个freed chunk；与linux ptmalloc不同的是，这里Flink和Blink指向不是chunk头，而是数据区域。

_HEAP_VIRTUAL_ALLOC_ENTRY

维护通过VirtualAlloc分配出来的chunk，可以类比linux ptmalloc中的mmap chunk：

1
2
3
4
5
6
7
8
9
10
11
12
0:004> dt _HEAP_VIRTUAL_ALLOC_ENTRY
ntdll!_HEAP_VIRTUAL_ALLOC_ENTRY
    +0x000 Entry            : _LIST_ENTRY
    +0x010 ExtraStuff       : _HEAP_ENTRY_EXTRA
    +0x020 CommitSize       : Uint8B
    +0x028 ReserveSize      : Uint8B
    +0x030 BusyBlock        : _HEAP_ENTRY

0:004> dt _LIST_ENTRY
MSVCP140!_LIST_ENTRY
    +0x000 Flink            : Ptr64 _LIST_ENTRY
    +0x008 Blink            : Ptr64 _LIST_ENTRY

其中一些比较重要的成员：

  • Entry(+0x0: 16B)：链表的Flink和Blink，分别指向上一个和下一个通过VirtualAlloc分配出来的chunk。
  • BusyBlock(+0x30: 8B)：与普通的_HEAP_ENTRY头基本一样，不同在于这里的Size是没有使用的size，储存时也没有进行size >> 4的操作，UnusedBytes恒为4。

_HEAP_LIST_LOOKUP

_HEAP中BlocksIndex指向的结构体，方便快速寻找到合适的chunk：

1
2
3
4
5
6
7
8
9
10
11
0:004> dt _HEAP_LIST_LOOKUP
ntdll!_HEAP_LIST_LOOKUP
    +0x000 ExtendedLookup   : Ptr64 _HEAP_LIST_LOOKUP
    +0x008 ArraySize        : Uint4B
    +0x00c ExtraItem        : Uint4B
    +0x010 ItemCount        : Uint4B
    +0x014 OutOfRangeItems  : Uint4B
    +0x018 BaseIndex        : Uint4B
    +0x020 ListHead         : Ptr64 _LIST_ENTRY
    +0x028 ListsInUseUlong  : Ptr64 Uint4B
    +0x030 ListHints        : Ptr64 Ptr64 _LIST_ENTRY

其中一些比较重要的成员：

  • ExtendedLookup(+0x0: 8B)：指向下一个ExtendedLookup，通常下一个会管理更大的chunk。
  • ArraySize(+0x8: 4B)：该结构管理的最大chunk的大小，通常为0x80（实际上是0x80 << 4 = 0x800）。
  • ItemCount(+0x10: 4B)：目前该结构管理的chunk数目。
  • OutOfRangeItems(+0x14: 4B)：超出该结构所管理大小的chunk的数量。
  • BaseIndex(+0x18: 8B)：该结构所管理的chunk的起始index，用来从ListHint中找到合适大小的freed chunk用的。
  • ListHead(+0x20: 8B)：指向Freelist的dummy head。
  • ListsInUseUlong(+0x28: 8B)：一个bitmap，用来判断ListHint中是否有合适大小的chunk。
  • ListHints(+0x20: 8B)：用来指向对应大小的chunk array，该array以0x10大小为间隔，存放一个对应size的freed chunk的地址，用于快速找到合适大小的chunk；可以类比linux ptmalloc的tcache bin，只不过chunk的组织仍然通过双向链表维护。

空闲chunk的管理

同样借用Slides中的一张图来说明，结构清晰明朗：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
+-----------------------+                     BlocksIndex                                 +----------------------+
|000001...1...1000000000|   +----------->+-------------------+                            | PreviousBlockPrivate |         
+-----------------------+   |            |        ...        |                            +----------------------+
           ^                |            +-------------------+                            |  Chunk header (0x70) |
           |                             |     ListHead      |-----+  +------------------>+----------------------+
           +--------+       |            +-------------------+     |  |                   |         Flink        |----+
       _HEAP        +-------+------------|  ListsInUseUlong  |--+  |  |                   +----------------------+    |
+------------------+        |            +-------------------+  |  |  |           +-------|         Blink        |    |
|        ...       |        |            |     ListHint      |  |  |  |           |  +--->+----------------------+    |
+------------------+        |            +-------------------+  |  |  |           |  |    |          ...         |    |
|  EncodeFlagMask  |        |                  +----------------+--+  |           |  |    +----------------------+    |
+------------------+        |                  |                |     |           |  |                                |
|     Encoding     |        |                  V                |     |           |  |    +----------------------+    |
+------------------+        |   +------->+-----------+<---------+-----|-----------+  |    | PreviousBlockPrivate |    |
|        ...       |        |   |        |   Flink   |          |     |              |    +----------------------+
+------------------+        |   |        +-----------+          |     |              |    | Chunk header (0x110) |    |
|   BlocksIndex    |--------+   |        |   Blink   |          |     |     +--------+--->+----------------------+<---+  
+------------------+            |     +->+-----------+<---------+-----|-----|-----+  |    |         Flink        |----+
|        ...       |            |     |        +----------------+     |     |     |  |    +----------------------+    |
+------------------+------------+     |        |                      |     |     |  +----|         Blink        |    |     
|     FreeList     |                  |        V                      |     |     |  +--->+----------------------+    |
+------------------+------------------+  +-----------+                |     |     |  |    |          ...         |    |
|        ...       |                     |    ...    |                |     |     |  |    +----------------------+    |
+------------------+                     +-----------+                |     |     |  |                                |
                              ListHint[7]|   Flink   |----------------+     |     |  |    +----------------------+    |
                                         +-----------+                      |     |  |    | PreviousBlockPrivate |    |
                                         |    ...    |                      |     |  |    +----------------------+    |      
                                         +-----------+                      |     |  |    | Chunk header (0x160) |    |
                             ListHint[17]|   Flink   |----------------------+  +--+--+--->+----------------------+<---+
                                         +-----------+                         |  |  |    |         Flink        |----+
                                         |    ...    |                         |  |  |    +----------------------+    |
                                         +-----------+                         |  |  +----|         Blink        |    |
                             ListHint[22]|   Flink   |-------------------------+  |       +----------------------+    |
                                         +-----------+                            |       |          ...         |    |
                                         |    ...    |                            |       +----------------------+    |
                                         +-----------+                            +-----------------------------------+

分配机制

Allocate (RtlpAllocateHeap)

根据size分为三种情况:

size <= 0x4000
基本都会通过RtlpAllocateHeap进行分配：

  1. 首先会看该size对应的FrontEndHeapStatusBitmap是否有启用LFH：
    • 如果没有则在对应的FrontEndHeapUsageData += 0x21。
    • 如果FrontEndHeapUsageData > 0xff00 || FrontEndHeapUsageData & 0x1f > 0x10，那么启用LFH。
  2. 接下来会查看对应的ListHint中是否有值（也就是否有对应size的freed chunk）：
    • 如果刚好有值，就检查该chunk的Flink是否是同样size的chunk：
      • 若是则将Flink写到对应的ListHint中。
      • 若否则清空对应ListHint，并最后将该chunk从Freelist中unlink出来（Unlink细节后面利用的时候会进行解释）。
    • 如果对应的ListHint中本身就没有值，就从比较大的ListHint中找：
      • 如果找到了，就以上述同样的方式处理该ListLink，并unlink该chunk，之后对其进行切割，剩下的重新放入Freelist，如果可以放进ListHint就会放进去，再encode header。
      • 如果没较大的ListHint也都是空的，那么尝试ExtendedHeap加大堆空间，再从extend出来的chunk拿，接着一样切割，放回ListHIint，encode header。
  3. 最后将分配到的chunk返回给用户。

0x4000 < size <= 0xff000
除了没有LFH相关操作外，其余都和第一种情况一样。

size >= 0xff000
直接调用ZwAllocateVirtualMemroy进行分配，类似于linux下的mmap直接给一大块地址，并且插入_HEAP->VirtualAllocdBlocks中。

Free (RtlpFreeHeap)

根据size分为两种情况：

size <= 0xff000

  1. 首先会检查地址对齐0x10，并通过unused bytes判断该chunk的状态（为0则是free状态，反之则为inuse状态）。
  2. 如果LFH未开启，会将对应的FrontEndHeapUsageData -= 1（并不是0x21）。
  3. 接着判断前后的chunk是否是freed的状态，如果是的话就将前后的freed chunk从Freelist中unlink下来（与上面的方式一样更新ListHint），再进行合并。
  4. 合并完之后更新Size和PreviousSize，然后查看是不是最前跟最后，是就插入，否则就从ListHint中插入，并且update ListHint；插入时也会对Freelist进行检查（但是此检查不会触发abort，原因在于没有做unlink写入）。

size > 0xff000
检查该chunk的linked list并从_HEAP->VirtualAllocdBlocks中移除，接着使用RtlpSecMemFreeVirtualMemory将chunk整个munmap掉。

Exploitation

目前看来主要是针对Unlink的利用方式，虽然Windows下对freed chunk的管理比较复杂，但是unlink原理和linux ptmalloc十分类似，所以利用方法也是共通的。
主要有两点不同：

  1. 进行decode header然后进行check的时候，需要保证其正确性，比如找到previous freed chunk，进行decode以及check的操作的时候。
  2. 前面也曾提到，windows下chunk的Flink和Blink直接指向数据区域而不是chunk header。

整体的利用思路为：

  1. 在已知linux下unlink attack的基础上，以完全相同的方式，对windows heap进行unlink attack，可以实现将一个指针指向本身的效果（细节这里不再赘述，Slides的图解十分详细）。
  2. 利用这个指向自身的指针，我们可以控制周围的可能的指针，达到任意地址读写的效果。
  3. 不同于linux下的利用，windows下似乎不存在各种hook函数可以覆盖从而控制程序的执行流，所以只存在两条路，一是ROP，二十写shellcode。
  4. 不论如何，首先需要的是leak出text，各种dll，以及stack地址。
    • text： 
      1
      PEB --> text
    • 针对dll： 
      1
      2
      3
      4
      5
      text --> IAT --> xxx.dll --> xxx.dll
      // or
      _HEAP->LockVariable.Lock --> ntdll.dll
      // or
      CrticalSection->DebugInfo --> ntdll.dll
    • 针对stack： 
      1
      2
      3
      Kernel32.dll --> kernelbase.dll --> KERNELBASE!BasepFilterInfo --> stack address // 高机率会有
      // or
      kernel32.dll --> ntdll.dll --> ntdll!PebLdr --> PEB --> TEB --> stack address
  5. 后面就可以覆盖返回地址做ROP，调VirtualProtect获得执行权限，然后jump到shellcode执行。（个人认为如果可以的话，也能修复Freelist的双向链表，然后ROP直接执行system("cmd.exe")）

Front-End

一些重要结构体

_LFH_HEAP

管理Front-End heap的结构体：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
0:002> dt _LFH_HEAP
ntdll!_LFH_HEAP
    +0x000 Lock             : _RTL_SRWLOCK
    +0x008 SubSegmentZones  : _LIST_ENTRY
    +0x018 Heap             : Ptr64 Void
    +0x020 NextSegmentInfoArrayAddress : Ptr64 Void
    +0x028 FirstUncommittedAddress : Ptr64 Void
    +0x030 ReservedAddressLimit : Ptr64 Void
    +0x038 SegmentCreate    : Uint4B
    +0x03c SegmentDelete    : Uint4B
    +0x040 MinimumCacheDepth : Uint4B
    +0x044 CacheShiftThreshold : Uint4B
    +0x048 SizeInCache      : Uint8B
    +0x050 RunInfo          : _HEAP_BUCKET_RUN_INFO
    +0x060 UserBlockCache   : [12] _USER_MEMORY_CACHE_ENTRY
    +0x2a0 MemoryPolicies   : _HEAP_LFH_MEM_POLICIES
    +0x2a4 Buckets          : [129] _HEAP_BUCKET
    +0x4a8 SegmentInfoArrays : [129] Ptr64 _HEAP_LOCAL_SEGMENT_INFO
    +0x8b0 AffinitizedInfoArrays : [129] Ptr64 _HEAP_LOCAL_SEGMENT_INFO
    +0xcb8 SegmentAllocator : Ptr64 _SEGMENT_HEAP
    +0xcc0 LocalData        : [1] _HEAP_LOCAL_DATA

其中一些比较重要的成员：

  • Heap(+0x18: 8B)：指向其对应的_HEAP结构体。
  • Buckets(+0x2A4: 4B * 129)：一个存放129个_HEAP_BUCKET结构体的数组（_HEAP_BUCKET后面会分析），用来寻找配置大小对应到Block大小的阵列结构。
  • SegmentInfoArrays(+0x4A8: 8B * 129)：一个存放129个_HEAP_LOCAL_SEGMENT_INFO结构体指针的数组（_HEAP_LOCAL_SEGMENT_INFO后面会分析），不同大小对应到不同的_HEAP_LOCAL_SEGMENT_INFO结构体，主要管理对应到的_HEAP_SUBSEGMENT的信息。
  • LocalData：一个_HEAP_LOCAL_DATA结构体： 
    1
    2
    3
    4
    5
    6
    7
    0:002> dt _HEAP_LOCAL_DATA
    ntdll!_HEAP_LOCAL_DATA
        +0x000 DeletedSubSegments : _SLIST_HEADER
        +0x010 CrtZone          : Ptr64 _LFH_BLOCK_ZONE
        +0x018 LowFragHeap      : Ptr64 _LFH_HEAP
        +0x020 Sequence         : Uint4B
        +0x024 DeleteRateThreshold : Uint4B
    其中LowFragHeap指回_LFH_HEAP结构本身的位置，通常用来找回LFH。

_HEAP_BUCKET

结构如下：

1
2
3
4
5
6
7
0:002> dt _HEAP_BUCKET
ntdll!_HEAP_BUCKET
    +0x000 BlockUnits       : Uint2B
    +0x002 SizeIndex        : UChar
    +0x003 UseAffinity      : Pos 0, 1 Bit
    +0x003 DebugFlags       : Pos 1, 2 Bits
    +0x003 Flags            : UChar

其中一些比较重要的成员：

  • BlockUnits(+0x0: 2B)：要分配出去的一个block的大小，实际存放是size >> 4。
  • SizeIndex(+0x2: 1B)：使用者需要的大小，实际存放是size >> 4。

_HEAP_LOCAL_SEGMENT_INFO

结构如下：

1
2
3
4
5
6
7
8
9
10
11
0:002> dt _HEAP_LOCAL_SEGMENT_INFO
ntdll!_HEAP_LOCAL_SEGMENT_INFO
    +0x000 LocalData        : Ptr64 _HEAP_LOCAL_DATA
    +0x008 ActiveSubsegment : Ptr64 _HEAP_SUBSEGMENT
    +0x010 CachedItems      : [16] Ptr64 _HEAP_SUBSEGMENT
    +0x090 SListHeader      : _SLIST_HEADER
    +0x0a0 Counters         : _HEAP_BUCKET_COUNTERS
    +0x0a8 LastOpSequence   : Uint4B
    +0x0ac BucketIndex      : Uint2B
    +0x0ae LastUsed         : Uint2B
    +0x0b0 NoThrashCount    : Uint2B

其中一些比较重要的成员：

  • LocalData(+0x0: 8B)：一个_HEAP_LOCAL_DATA结构体指针，指向_LFH_HEAP->LocalData，方便从_HEAP_LOCAL_SEGMENT_INFO找回_LFH_HEAP。
  • BucketIndex(+0xAC: 2B)：对应到的BucketIndex，也就是_LFH_HEAP->SegmentInfoArrays数组中对应的下标。
  • ActiveSubsegment(+0x8: 8B)：非常重要的成员，一个_HEAP_SUBSEGMENT结构体指针，目的在于管理UserBlocks，记录剩余等多chunk、该UserBlocks最大分配数等信息。
  • CachedItems：一个存放16个_HEAP_SUBSEGMENT结构体指针的数组，存放对应到该_HEAP_LOCAL_SEGMENT_INFO且还有可以分配chunk给用户的_HEAP_SUBSEGMENT指针；可以理解为一个内存池，当ActiveSubsegment没有可用chunk的时候，即用完的时候，就从CachedItems选择填充，替换掉ActiveSubsegment。

_HEAP_SUBSEGMENT

结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
0:002> dt _HEAP_SUBSEGMENT
ntdll!_HEAP_SUBSEGMENT
    +0x000 LocalInfo        : Ptr64 _HEAP_LOCAL_SEGMENT_INFO
    +0x008 UserBlocks       : Ptr64 _HEAP_USERDATA_HEADER
    +0x010 DelayFreeList    : _SLIST_HEADER
    +0x020 AggregateExchg   : _INTERLOCK_SEQ
    +0x024 BlockSize        : Uint2B
    +0x026 Flags            : Uint2B
    +0x028 BlockCount       : Uint2B
    +0x02a SizeIndex        : UChar
    +0x02b AffinityIndex    : UChar
    +0x024 Alignment        : [2] Uint4B
    +0x02c Lock             : Uint4B
    +0x030 SFreeListEntry   : _SINGLE_LIST_ENTRY

其中一些比较重要的成员：

  • LocalInfo(+0x0: 8B)：一个指回到对应_HEAP_LOCAL_SEGMENT_INFO结构体位置的指针。
  • UserBlocks(+0x8: 8B)：一个指向_HEAP_USERDATA_HEADER结构的指针（后面会对_HEAP_USERDATA_HEADER进行分析），也就是指向LFH chunk的内存分配池。该内存分配池包括一个_HEAP_USERDATA_HEADER，存放一些metatdata；紧跟着后面会有要分配出去的所有chunk。
  • AggregateExchg(+0x20: 4B)：一个_INTERLOCK_SEQ结构（后面会对_INTERLOCK_SEQ进行分析），储存对应的UserBlocks的状态信息。
  • BlockSize(+0x24: 2B)：该UserBlocks中每个chunk的大小。
  • BlockCount(+0x28: 2B)：该UserBlocks中chunk的总个数。
  • SizeIndex(+0x2A: 1B)：该UserBlocks对应的index。

_INTERLOCK_SEQ

结构如下：

1
2
3
4
5
6
7
0:002> dt _INTERLOCK_SEQ
ntdll!_INTERLOCK_SEQ
    +0x000 Depth            : Uint2B
    +0x002 Hint             : Pos 0, 15 Bits
    +0x002 Lock             : Pos 15, 1 Bit
    +0x002 Hint16           : Uint2B
    +0x000 Exchg            : Int4B

一些重要的成员：

  • Depth(+0x0: 2B)：用来管理对应到的UserBlocks还有多少freed chunk，LFH会用这个判断是否还从该UserBlock进行分配。
  • Lock(+0x2: 1Bit)：Lock，即提供锁的作用，其实只占用第4 byte的最后一个bit。

_HEAP_USERDATA_HEADER

结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
0:002> dt _HEAP_USERDATA_HEADER
ntdll!_HEAP_USERDATA_HEADER
    +0x000 SFreeListEntry   : _SINGLE_LIST_ENTRY
    +0x000 SubSegment       : Ptr64 _HEAP_SUBSEGMENT
    +0x008 Reserved         : Ptr64 Void
    +0x010 SizeIndexAndPadding : Uint4B
    +0x010 SizeIndex        : UChar
    +0x011 GuardPagePresent : UChar
    +0x012 PaddingBytes     : Uint2B
    +0x014 Signature        : Uint4B
    +0x018 EncodedOffsets   : _HEAP_USERDATA_OFFSETS
    +0x020 BusyBitmap       : _RTL_BITMAP_EX
    +0x030 BitmapData       : [1] Uint8B

一些重要成员：

  • SubSegment(+0x0: 8B)：指回对应的_HEAP_SUBSEGMENT结构。
  • EncodedOffsets(+0x18: 8B)：一个_HEAP_USERDATA_OFFSETS结构，用来验证chunk header是否被改过。
  • BusyBitmap(+0x20: 10B)：记录该UserBlocks那些chunk被使用了。

_HEAP_ENTRY

结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
0:002> dt _HEAP_ENTRY
ntdll!_HEAP_ENTRY
    +0x000 UnpackedEntry    : _HEAP_UNPACKED_ENTRY
    +0x000 PreviousBlockPrivateData : Ptr64 Void
    +0x008 Size             : Uint2B
    +0x00a Flags            : UChar
    +0x00b SmallTagIndex    : UChar
    +0x008 SubSegmentCode   : Uint4B
    +0x00c PreviousSize     : Uint2B
    +0x00e SegmentOffset    : UChar
    +0x00e LFHFlags         : UChar
    +0x00f UnusedBytes      : UChar
    +0x008 CompactHeader    : Uint8B
    +0x000 ExtendedEntry    : _HEAP_EXTENDED_ENTRY
    +0x000 Reserved         : Ptr64 Void
    +0x008 FunctionIndex    : Uint2B
    +0x00a ContextValue     : Uint2B
    +0x008 InterceptorValue : Uint4B
    +0x00c UnusedBytesLength : Uint2B
    +0x00e EntryOffset      : UChar
    +0x00f ExtendedBlockSignature : UChar
    +0x000 ReservedForAlignment : Ptr64 Void
    +0x008 Code1            : Uint4B
    +0x00c Code2            : Uint2B
    +0x00e Code3            : UChar
    +0x00f Code4            : UChar
    +0x00c Code234          : Uint4B
    +0x008 AgregateCode     : Uint8B

其中重要的成员：

  • SubSegmentCode(+0x8: 4B)：encode过的metadata，用来推回UserBlocks的位置。
  • PreviousSize(+0xC: 2B)：该chunk在UserBlock中的index，实际上是第0xD个byte。
  • UnusedBytes(+0xF: 1B)：用来判断该LFH chunk是否为freed状态，如果是busy状态，则为0x80。

一些补充

_HEAP_USERDATA_HEADER->EncodedOffsets在UserBlocks初始化的时候设置，其算法为下面四个值进行xor：

  • (sizeof(_HEAP_USERDATA_HEADER)) | ((_HEAP_BUCKET->BlockUnits) * 0x10 << 16)
  • LFHkey
  • UserBlocks的地址
  • _LFH_HEAP的地址

所有UserBlocks里的chunk header在初始化的时候都会经过xor，其算法为下面各个值得xor：

  • _HEAP的地址
  • LFHkey
  • chunk本身的地址address >> 4
  • ((chunk address) - (UserBLocks address)) << 12

整个LFH的结构布局

因为涉及的结构体多而杂乱，用图辅助比较好理解，因此依然使用Slides中的图来说明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
                                                                                                                         _HEAP_USERDATA_HEADER 
                                                                                                                    +-->+---------------------+
                                                                                                                    |   |      SubSegment     |
         _HEAP                                                   _HEAP_BUCKET                                       |   +---------------------+
+---------------------+                               +---->+---------------------+                                 |   |         ...         |
|         ...         |                               |     |      BlockUnits     |                                 |   +---------------------+
+---------------------+              _LFH_HEAP        |     +---------------------+          _HEAP_SUBSEGMENT       |   |    EncodedOffsets   |
|    EncodeFlagMask   |   +-->+---------------------+ |     |       SizeIndex     |    +->+---------------------+   |   +---------------------+
+---------------------+   |   |         ...         | |     +---------------------+  +-+--|      LocalInfo      |   |   |      BusyBitmap     |
|       Encoding      |   |   +---------------------+ |     |         ...         |  | |  +---------------------+   |   +---------------------+
+---------------------+   |   |        Heap         | | +-->+---------------------+  | |  |      UserBlocks     |---+   |         ...         |
|         ...         |   |   +---------------------+ | |                            | |  +---------------------+       +---------------------+
+---------------------+   |   |         ...         | | |                            | |  |         ...         |       |     chunk header    |
|     BlocksIndex     |   |   +---------------------+-+ |                            | |  +---------------------+----+  +---------------------+
+---------------------+   |   |      Buckets[0]     |   |                            | |  |    AggregateExchg   |    |  |         ...         |
|         ...         |   |   +---------------------+---+   _HEAP_LOCAL_SEGMENT_INFO | |  +---------------------+--+ |  +---------------------+
+---------------------+   |   |         ...         |   +-->+---------------------+  | |  |      BlockSize      |  | |  |     chunk header    |
|       FreeList      |   |   +---------------------+   | +-|      LocalData      |<-+ |  +---------------------+  | |  +---------------------+
+---------------------+   |   | SegmentInfoArray[x] |---+ | +---------------------+    |  |      BlockCount     |  | |  |         ...         |
|         ...         |   |   +---------------------+     | |   ActiveSubsegment  |----+  +---------------------+  | |  +---------------------+
+---------------------+   |   |         ...         |     | +---------------------+       |         ...         |  | |  |     chunk header    |
|     FrontEndHeap    |---+   +---------------------+     | |     CachedItems     |       +---------------------+  | |  +---------------------+
+---------------------+       |      LocalData      |<----+ +---------------------+       |      SizeIndex      |  | |  |         ...         |
|         ...         |       +---------------------+       |         ...         |       +---------------------+  | |  +---------------------+
+---------------------+       |         ...         |       +---------------------+       |         ...         |  | |  
|FrontEndHeapUsageData|       +---------------------+       |     BucketIndex     |       +---------------------+  | |       _INTERLOCK_SEQ
+---------------------+                                     +---------------------+                                | +->+---------------------+
|         ...         |                                     |         ...         |                                |    |        Depth        |
+---------------------+                                     +---------------------+                                |    +---------------------+
                                                                                                                   |    |    Hint(15 bits)    |
                                                                                                                   |    +---------------------+
                                                                                                                   |    |     Lock(1 bit)     |
                                                                                                                   +--->+---------------------+

分配机制

LFH的初始化

在Back-End中也对LFH也有所提及，也就是在FrontEndHeapUsageData[x] & 0x1F > 0x10的时候，置位_HEAP->CompatibilityFlag |= 0x20000000，下一次Allocate就会对LFH进行初始化：

  1. 首先会ExtendFrontEndUsageData及增加更大的_HEAP->BlocksIndex，因为这里_HEAP->BlocksIndex可以理解为一个_HEAP_LIST_LOOKUP结构的单向链表（参考上面Back-End的解释），且默认初始情况下只存在一个管理比较小的（0x0 ~ 0x80）的chunk的_HEAP_LIST_LOOKUP，所以这里会扩展到（0x80 ~ 0x400），即在链表尾追加一个管理更大chunk的_HEAP_LIST_LOOKUP结构体结点。
  2. 建立并初始化_HEAP->FrontEndHeap（通过mmap），即初始化_LFH_HEAP的一些metadata。
  3. 建立并初始化_LFH_HEAP->SegmentInfoArrays[x]，在SegmentInfoArrays[BucketIndex]处填上对应的_HEAP_LOCAL_SEGMENT_INFO结构体指针。

再接下来Allocate相同大小的chunk就会开始使用LFH：

  1. 分配UserBlocks并进行初始化，即设置对应大小的chunk。
  2. 然后再设置对应_HEAP_LOCAL_SEGMENT_INFO->ActiveSubsegment。
  3. 随机地从UserBlocks中返回一个chunk。

Allocate (RtlpLowFragHeapAllocFromContext)

根据以下步骤：

  1. 先看看ActiveSubsegment中有没有空闲的chunk，也就是通过ActiveSubsegment->AggregateExchg.depth（free chunk的个数）判断：
    • 如果没有则从CacheedItems中找，找到有存在空闲chunk的Subsegment就替换掉当前的ActiveSubsegment。
    • 如果有则继续往下。
  2. 取得RtlpLowFragHeapRandomData[x]上的值；且取值是依次循环取的，x为1 byte大小的值，即下一次x = (x + 1) % 256；由于RtlpLowFragHeapRandomData是一个存放256个随机数的数列（范围为0x0 ~ 0x7F），所以这里相当于在取随机数。
  3. 计算相应的UserBlocks里chunk的index，通过RtlpLowFragHeapRandomData[x] * max_index >> 7（其中max_index显然是能取到的最大的index）：
    • 如果发生了collision，即该index对应的chunk是busy的，那么往后取最近的；细节上，就是检查index对应到的bitmap是否为0，如果是0就返回对应的bitmap，否则选取最近的下一个。
    • 如果没有发生，则继续往下。
  4. 检查chunk->UnusedBytes & 0x3F != 0，因为满足此式表示chunk是free状态的，否则状态非法；该过程中还会设置对应的bitmap，以及更新ActiveSubsegment->AggregateExchg.depth等相关信息。
  5. 最后设置index（即chunk->PreviousSize）以及chunk->UnusedBytes，并把chunk返回给用户。

Free (RtlFreeHeap)

根据以下步骤：

  1. 首先更新chunk->UnusedBytes。
  2. 找到该chunk对应的在UserBlocks中的index，并且置UserBlocks->BusyBitmap对应的bit为0。
  3. 更新ActiveSubsegment->AggregateExchg。
  4. 如果该chunk不属于当前的ActiveSubsegment则看能不能放进CachedItems中去，如果可以就放进去。

Exploitation

从Slides上面看，只提到了一种Reuse attack，如下面的情况：
假如我们拥有UAF的漏洞可以利用，但是因为LFH分配的随机性，我们无法预测下一个那到的chunk是在哪个位置，也就是说现在我们free的chunk，下一次malloc不一定拿得到。
那么此时可以通过填满UserBlocks的方式，再free掉目标chunk，这样下一次malloc就必然会拿到目标chunk（因为只剩下一个），然后可以利用这个特性构造chunk overlap做进一步利用。
当然这只是提了一种利用思路，至于其他的还需要慢慢摸索，具体情况下还需做特定的分析利用。

参考链接

  1. https://www.slideshare.net/AngelBoy1/windows-10-nt-heap-exploitation-chinese-version
  2. https://www.anquanke.com/post/id/180372
  3. https://bbs.pediy.com/thread-246570.htm
Author: Nop
Link: https://n0nop.com/2021/04/15/Learning-Windows-pwn-Nt-Heap/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
CTFpwnWindows