指针泄露通过指针键数据结构

作者：Jann Horn，Google Project Zero

引言

2024年，在Project Zero团队的一次讨论中，我们谈到了远程ASLR泄露对于利用某些类型内存损坏漏洞的帮助或必要性，特别是在苹果设备的背景下。从"寻找远程ASLR泄露的好地方"的角度出发，这导致我们发现了一种技巧，可以在某些场景下远程泄露指针，而无需任何内存安全违规或时序攻击。

这些场景包括：能够到达的攻击面可以反序列化攻击者提供的数据，重新序列化结果对象，并将重新序列化的数据发送回攻击者。

团队进行了头脑风暴，但未能立即找到任何在macOS/iOS上表现出这种行为的特定攻击面，尽管我们没有进行广泛的分析来测试这种攻击面是否存在。我没有针对真实的攻击面，而是在macOS上使用了一个人工测试案例来测试这里描述的技术，该测试案例使用NSKeyedArchiver序列化作为目标。

由于缺乏实际影响的证明，我向苹果报告了这个问题，但没有在我们的bugtracker中提交。该问题在2025年3月31日的安全更新中得到了修复。本文中指向苹果代码的链接指向一个多年未更新的过时代码版本，对代码工作方式的描述指的是旧的未修复版本。

我决定写关于这种技术的内容，因为它有些有趣和新颖，其中的一些想法可能会推广到其他上下文中。它与我过去发现的部分指针泄露和另一个指针排序泄露密切相关，并展示了在理想情况下如何使用指针键数据结构来泄露地址。

背景 - 技术树

hashDoS

对我来说，这个问题的故事始于2011年，当时在28C3上介绍了hashDoS攻击（幻灯片，录像）。本质上，hashDoS是对服务的拒绝服务攻击（特别是Web服务器），这些服务使用大量攻击者控制的键（如POST参数）填充哈希表。

它基于这样的观察：许多哈希表实现在平均情况下每个插入/查找操作具有O(1)复杂度，但在最坏情况下（所有键的哈希落在同一个哈希桶中，哈希表基本上变成了类似链表或未排序数组的东西，具体取决于实现方式）相同操作具有O(n)复杂度。

特别是，如果攻击者知道用于键的哈希函数，那么通过构造一个充满参数键的请求，所有这些键都映射到同一个哈希桶，攻击者可以使服务器花费O(n²)时间处理这样的请求；这被证明足以使用小得可笑的网络流量使Web服务器的CPU饱和。

关于故意创建哈希表碰撞以泄露地址的想法，还有更早的先前工作，正如在29C3关于同一主题的演讲中指出的那样。Solar Designer在1998年的Phrack第53期中写道：

1
2
3
4
5
6
7
8
9

----[ 数据结构和算法选择

当选择用于普通应用程序的排序或数据查找算法时，人们通常优化典型情况。然而，对于IDS[入侵检测系统]，应始终考虑最坏情况：攻击者可以向我们的IDS提供她喜欢的任何数据。如果IDS是故障开放的，她将能够绕过它，如果它是故障关闭的，她可能对整个受保护系统造成DoS。

让我通过一个例子来说明。在scanlogd中，我使用哈希表来查找源地址。只要哈希表足够大（因为我们保留的地址数量毕竟是有限的），这对于典型情况非常有效。平均查找时间比二分查找更好。然而，攻击者可以选择她的地址（很可能是伪造的）来引起哈希碰撞，有效地将哈希表查找替换为线性搜索。根据我们保留多少条目，这可能使scanlogd无法及时获取新数据包。在像scanlogd这样的基于主机的IDS中，这也将总是从其他进程占用更多CPU时间。

[...]

可能值得一提的是，类似的问题也适用于像操作系统内核这样的东西。例如，哈希表在那里广泛用于查找活动连接、监听端口等。通常有其他限制使这些不是真正危险的，但可能需要更多研究。

hashDoS作为时序攻击

从稍微不同的角度来看，hashDoS的核心观察是：如果攻击者可以将大量选择的键插入哈希表（或哈希集合），并且知道这些键哈希到哪些哈希桶，那么攻击者可以（取决于哈希表实现细节）基本上减慢对所选哈希桶的未来访问。

如果攻击者可以导致将哈希是秘密的其他键插入同一个哈希表中，这就变得有趣了。实际上，例如，这可以发生在支持混合多种键类型的哈希表中，比如JavaScript的Map。早在2016年，在Firefox实现中，int32数字使用固定的哈希函数ScrambleHashCode(number)进行哈希，而字符串被原子化/内部化，然后基于它们的虚拟地址进行哈希。

这使得可以首先用大量元素填充攻击者选择的哈希桶，然后插入一个字符串，观察其插入是快还是慢，并从中确定字符串的哈希是否匹配攻击者选择的哈希桶。

借助依赖于Firefox中内部化单字符字符串地址模式的一些技巧，这使得可以通过Map插入和时序测量泄露堆地址的低32位。有关更多细节，请参阅原始文章和错误报告。当然，如今那种基于时序的进程内部分指针泄露从JavaScript中被认为不太有趣，因为通常假设JavaScript无论如何都可以读取同一进程中的所有内存…

从这里得出的结论是：当指针用作对象哈希码的基础时，这可以通过键控数据结构中的侧信道泄露指针。

Linux：通过指针键树的有序列表进行对象排序泄露

正如我在几年前的一篇博客文章中指出的，在Linux上，非特权用户空间可以通过从/proc/self/fdinfo/读取来发现struct file实例在内核虚拟内存中的存储顺序——该文件通过迭代红黑树列出由epoll实例监视的所有文件，该红黑树（基本上）按引用的struct file的虚拟地址排序，因此给予用户空间的数据以相同的方式排序。

（正如我在那篇文章中指出的，这对于打破依赖于指针标记的概率内存安全缓解措施可能特别有趣。如果指针的最高位是秘密的标记位，并且攻击者可以确定地址（包括标记位）的顺序，攻击者可以推断对象在重新分配后标记是否改变。）

从这里得出的结论是：键控数据结构不仅通过时序泄露关于对象哈希码的信息；迭代键控数据结构还可以生成其排序揭示对象哈希码信息的数据。

序列化攻击

有多种序列化对象图的方法。在频谱的一端是基于模式的序列化，理想情况下：

• 可序列化类型及其成员与其他类型分开声明
• 字段明确声明它们可以指向哪些其他类型（没有可以指向任何东西的通用指针）
• 反序列化从特定的起始类型开始

在序列化频谱的另一端是像经典Java序列化（没有序列化过滤器）这样的东西，其中基本上任何标记为Serializable的类都可以被反序列化，序列化字段通常可以灵活地指向许多不同的类型，因此序列化数据也可以对结果对象图的形状有很多控制。

关于Java中"序列化小工具链"的主题有很多公共研究，其中对象可以组合，使得反序列化它们会导致远程代码执行等事情。这种类型的序列化通常被认为在跨安全边界使用时是不安全的，尽管Android在本地安全边界之间暴露了它。

在这个频谱的中间是基本上像不安全反序列化一样构建的序列化，但添加了一些粗粒度过滤器，只允许反序列化的对象具有来自允许列表的类型以使其安全。在Java中，这被称为"序列化过滤"。这也是Apple的NSKeyedUnarchiver.unarchivedObjectOfClasses的大致行为，本文重点讨论这个。

人工测试案例

本文描述的技术目标是通过单次执行以下测试案例泄露指向"共享缓存"（一个大的映射，它在系统上所有进程的相同虚拟地址，其地址仅在重启时改变）的指针，该测试案例使用NSKeyedUnarchiver.unarchivedObjectOfClasses反序列化由类型NSDictionary、NSNumber、NSArray和NSNull组成的攻击者提供的对象图，重新序列化结果，并写回结果序列化数据：

 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

@import Foundation;

int main() {
  @autoreleasepool {
    NSArray *args = [[NSProcessInfo processInfo] arguments];
    if (args.count != 3) {
      NSLog(@"bad invocation");
      return 1;
    }
    NSString *in_path = args[1];
    NSString *out_path = args[2];
    NSError *error = NULL;
    NSData *input_binary = [NSData dataWithContentsOfFile:in_path];
    /* decode */
    NSArray<Class> *allowed_classes = @[ [NSDictionary class], [NSNumber class], [NSArray class], [NSString class], [NSNull class] ];
    NSObject *decoded_data = [NSKeyedUnarchiver unarchivedObjectOfClasses:[NSSet setWithArray:allowed_classes] fromData:input_binary error:&error];
    if (error) {
      NSLog(@"Error %@ decoding", error);
      return 1;
    }
    NSLog(@"decoded");
    NSData *encoded_binary = [NSKeyedArchiver archivedDataWithRootObject:decoded_data requiringSecureCoding:true error:&error];
    if (error) {
      NSLog(@"Error %@ encoding", error);
      return 1;
    }
    NSLog(@"reencoded");
    [encoded_binary writeToFile:out_path atomically:NO];
  }
  return 0;
}

（测试案例也允许NSString，但我认为那是无关的。）

构建块

NSNull / CFNull单例

CFNull类型是特殊的：只有一个它的单例实例，kCFNull，在CFBase.c中实现，它存储在共享缓存中。当你反序列化一个NSNull对象时，这实际上不会创建新对象——而是使用单例。

在CFNull的CFRuntimeClass，__CFNullClass中，没有提供哈希处理程序。当在具有像__CFNullClass这样不实现->hash处理程序的类型的对象上调用CFHash时，对象的地址被用作哈希码。

基于指针的哈希不是NSNull特有的；但可能没有许多其他类型在反序列化时使用共享缓存中的单例。可能有更多类型的实例哈希是堆地址。

NSNumber

NSNumber类型封装一个数字并支持几种类型的数字；它的哈希处理程序__CFNumberHash使用_CFHashInt对32位整数进行哈希，这几乎只是执行与某个大质数的乘法。

NSDictionary

NSDictionary类型的实例是不可变的哈希表，可以包含任意类型的键。键哈希使用简单的模运算映射到哈希桶：hash_code % num_buckets。NSDictionary中的哈希桶数量始终是质数（参见__CFBasicHashTableSizes）；基于__CFBasicHashTableCapacities选择哈希表大小，使得哈希表通常大约半满（约38%-62%），尽管对于小尺寸的大小调整有点不同。

这些是探测式哈希表；因此，不是每个哈希桶都有一个链表，而是通过使用策略__kCFBasicHashLinearHashingValue / FIND_BUCKET_HASH_STYLE == 1找到备用桶来存储冲突元素，在该策略下，插入会向前扫描哈希桶。

我没有找到NSDictionary序列化的源代码，但它似乎以明显的方式发生，通过按顺序迭代哈希桶。

攻击

基本思想：通过序列化NSDictionary中的键排序进行信息泄露

如果目标进程使用攻击者选择的NSNumber键填充NSDictionary（通过反序列化），攻击者可以通过使用数字的哈希模哈希表大小导致所需桶索引的数字来控制将使用哪些哈希桶。如果目标进程然后插入一个NSNull键（仍然作为同一反序列化的一部分），然后序列化结果NSDictionary，NSNull键在字典序列化键中的位置将揭示关于NSNull哈希的信息。

特别是，攻击者可以使用NSNumber键创建这样的模式（其中#是被NSNumber占用的桶，_是留空的桶），其中偶数编号的桶被占用，奇数编号的桶为空，这里以大小为7的哈希表示例：

1
2

桶索引：   0123456
桶内容： #_#_#_#

这留下了三个可以插入NSNull的位置（用!标记）：

• 在索引1（#!###）。如果hash_code % num_buckets是6、0或1，则会发生这种情况。（对于6和0，插入将线性扫描桶，直到找到索引1处的空闲桶。）这将导致NSNull在序列化数据中排在第二位。
• 在索引3（##!##）。如果hash_code % num_buckets是2或3，则会发生这种情况。这将导致NSNull在序列化数据中排在第三位。
• 在索引5（###!#）。如果hash_code % num_buckets是4或5，则会发生这种情况。这将导致NSNull在序列化数据中排在第四位。

如果序列化数据然后被发送回攻击者，攻击者可以区分这三种状态（基于NSNull键在序列化数据中的索引），并了解hash_code % num_buckets在哪个范围内。

扩展它：泄露整个桶索引

如果上一节的攻击使用以下模式重复（占用奇数编号的桶并留下偶数编号的桶为空），这产生关于hash_code % num_buckets的更多信息：

1
2

0123456
_#_#_#_

（注意：不要过多思考具有3个元素的哈希表如何只使用3个桶因此不会看起来像这样。实际的再现器使用具有>=23个桶的哈希表。）

现在我们有四个可以插入NSNull的位置：

• 在索引0，如果hash_code % num_buckets是0。
• 在索引2，如果hash_code % num_buckets是1或2。
• 在索引4，如果hash_code % num_buckets是3或4。
• 在索引6，如果hash_code % num_buckets是5或6。

通过结合来自使用偶数桶占用模式的NSDictionary和使用奇数桶占用模式的NSDictionary的信息，可以确定hash_code % num_buckets的确切值；例如，如果第一个模式产生##!##，第二个模式产生_#!##，那么hash_code % num_buckets是2。

因此，通过向某个目标进程发送包含两个具有这些NSNumber和NSNull键模式的NSDictionary实例的序列化NSArray，然后从受害者接收重新序列化的副本，攻击者可以确定hash_code % num_buckets对于NSArray。

一些数学：泄露整个hash_code

为了泄露关于hash_code的更多信息，这可以用不同的哈希表大小重复。上一节的攻击泄露hash_code % num_buckets，其中num_buckets是攻击者可以根据每个NSDictionary中有多少元素从可能的大小__CFBasicHashTableSizes中选择的质数。

这里一个有用的数学技巧是：基于计算hash_code模一堆不同质数的结果值，可以使用扩展欧几里得算法计算hash_code模所有这些质数的乘积。因此，基于知道哈希表大小23、41、71、127、191、251、383、631和1087的hash_code % num_buckets，可以确定hash_code模2341711271912513836311087 = 0x5’ce23'017b'3bd5'1495。因为0x5’ce23'017b'3bd5'1495大于hash_code可以具有的最大值（因为hash_code是64位），这将是hash_code的实际值——NSNull单例的地址。

组合起来

因此，为了泄露共享缓存中NSNull单例的地址，攻击者必须发送序列化数据，该数据由一个大型容器（如NSArray）组成，该容器对于每个感兴趣的质数包含两个具有偶数和奇数索引模式的NSDictionary实例。（NSNull键在攻击者提供的序列化NSDictionary实例中应该最后出现，因此我的再现器手动将序列化数据构造为XML plist，然后我使用plutil将其转换为二进制plist。）

这种攻击者提供的序列化数据大小约为50 KiB。

然后，目标进程必须反序列化此数据，再次序列化它，并将其发送回攻击者。

之后，攻击者可以确定NSNull在每个NSDictionary中存储在哪个桶中，使用来自NSDictionary对的桶索引确定每个哈希表大小的hash_code % num_buckets，然后使用扩展欧几里得算法获得hash_code，即NSNull单例的地址。

再现器

我为这个问题写了一个再现器，由我自己的在目标机器上运行的受害者程序和向目标机器提供序列化数据并从目标接收重新序列化数据的攻击者程序组成。（为了便于再现，你可以在单台机器上测试这个，这也是我所做的；尽管我在"攻击者"和"目标"之间重新启动以确保攻击者不使用与目标相同的共享缓存地址。）

首先，在攻击者机器上，生成序列化数据：

1
2
3

% clang -o attacker-input-generator attacker-input-generator.c
% ./attacker-input-generator > attacker-input.plist
% plutil -convert binary1 attacker-input.plist

然后，在目标机器上，反序列化和重新序列化此数据：

1
2
3
4

% clang round-trip-victim.m -fobjc-arc -fmodules -o round-trip-victim
% ./round-trip-victim attacker-input.plist reencoded.plist
2024-11-25 22:29:44.043 round-trip-victim[1257:11287] decoded
2024-11-25 22:29:44.049 round-trip-victim[1257:11287] reencoded

为了验证，你也可以在目标机器上使用此帮助程序查看CFNull单例的真实地址：

1
2
3

% clang debug-nsnull-hash.m -fobjc-arc -fmodules -o debug-nsnull-hash
% ./debug-nsnull-hash
null singleton pointer = 0x1eb91ab60, null_hash = 0x00000001eb91ab60

然后，在攻击者机器上，处理重新序列化的数据：

 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

% plutil -convert xml1 reencoded.plist
% clang -o extract-pointer extract-pointer.c
% ./extract-pointer < reencoded.plist
serialized data with 1111 objects
NSNull class is 12, NSNull object is 11
NSNull is elem 8 out of 13
NSNull is elem 7 out of 12
NSNull is elem 7 out of 22
NSNull is elem 7 out of 21
NSNull is elem 6 out of 37
NSNull is elem 5 out of 36
NSNull is elem 61 out of 65
NSNull is elem 60 out of 64
NSNull is elem 32 out of 97
NSNull is elem 31 out of 96
NSNull is elem 95 out of 127
NSNull is elem 95 out of 126
NSNull is elem 175 out of 193
NSNull is elem 175 out of 192
NSNull is elem 188 out of 317
NSNull is elem 188 out of 316
NSNull is elem 214 out of 545
NSNull is elem 214 out of 544
NSNull mod 23 = 14
NSNull mod 41 = 13
NSNull mod 71 = 10
NSNull mod 127 = 120
NSNull mod 191 = 62
NSNull mod 251 = 189
NSNull mod 383 = 349
NSNull mod 631 = 375
NSNull mod 1087 = 427
NSNull mod 0x000000000000000000000000000003af =0x0000000000000000000000000000017e
NSNull mod 0x00000000000000000000000000010589 =0x000000000000000000000000000059e6
NSNull mod 0x0000000000000000000000000081bef7 =0xfffffffffffffffffffffffffff4177a
NSNull mod 0x00000000000000000000000060cd7a49 =0x000000000000000000000000078e47f3
NSNull mod 0x00000000000000000000005ee976e593 =0x000000000000000000000001eb91ab60
NSNull mod 0x000000000000000000008dff48e176ed =0x000000000000000000000001eb91ab60
NSNull mod 0x0000000000000000015e003ca3bc222b =0x000000000000000000000001eb91ab60
NSNull mod 0x0000000000000005ce23017b3bd51495 =0x000000000000000000000001eb91ab60
NSNull = 0x1eb91ab60

结论

这是一个相当理论化的攻击；但我认为它表明，如果一切条件合适，使用指针作为键控数据结构的对象哈希可能导致指针泄露，甚至无需使用时序攻击。

我的例子依赖于受害者重新序列化数据；但这种的时序攻击版本也可能，需要更多请求和足够精确的测量。

在我的测试案例中，NSDictionary通过混合不同类型的键使得基本上可以泄露关于指针排序和数字哈希的信息；但即使从只使用指针键而不混合键类型的数据结构中，也可能泄露一定量的信息，特别是当攻击者可以猜测堆对象分配的距离等和/或可以在多个容器中重复引用相同的对象时。

最稳健的缓解措施是避免使用对象地址作为查找键，或者使用带键的哈希函数对它们进行哈希（这应该将潜在的地址泄露减少为指针相等预言机）。然而，这可能会带来负面性能影响——特别是，使用对象内部存储的ID而不是对象的地址可能会在查找的关键路径上增加内存负载。