通过指针键控数据结构导致的指针泄露
引言
2024年的某个时候，在一次Project Zero团队讨论中，我们谈到了远程ASLR泄露对于利用某些类型的内存破坏漏洞会有帮助或必要，特别是在苹果设备的背景下。从"哪里是寻找远程ASLR泄露的好起点"这个角度出发，这导致我们发现了一个技巧，可能被用来远程泄露指针，无需任何内存安全违规或时序攻击，前提是攻击面能够到达这样的场景：反序列化攻击者提供的数据，重新序列化生成的对象，并将重新序列化的数据发送回攻击者。
团队进行了头脑风暴，我们没能立即想出macOS/iOS上任何具体的攻击面会以这种方式运行，尽管我们没有进行广泛分析来测试这种攻击面是否存在。我没有针对真实的攻击面，而是在macOS上使用人工测试用例测试了这里描述的技术，该测试用例使用NSKeyedArchiver序列化作为目标。由于缺乏实际影响的证明，我将问题报告给了苹果，但没有在我们的bug跟踪器中提交。该问题已在2025年3月31日的安全更新中修复。本文中指向苹果代码的链接指向多年未更新的过时代码版本，关于代码如何工作的描述也指的是旧的未修复版本。
我决定写一下这个技术，因为它有点有趣和新颖，其中的一些想法可能推广到其他场景。它与我过去发现的部分指针泄露和另一个指针排序泄露密切相关，并展示了在理想情况下如何使用基于指针键的数据结构来泄露地址。
背景 - 技术树
hashDoS
对我来说，这个问题的故事始于2011年，当时在28C3上介绍了hashDoS攻击（幻灯片，录像）。本质上，hashDoS是针对服务（特别是Web服务器）的拒绝服务攻击，这些服务用大量攻击者控制的键（如POST参数）填充哈希表。它基于这样的观察：许多哈希表实现在平均情况下每次插入/查找操作具有O(1)复杂度，但在最坏情况下（所有键的哈希值落在同一个哈希桶中，哈希表本质上变成了类似链表或未排序数组的结构，具体取决于实现方式）相同操作具有O(n)复杂度。特别是，如果攻击者知道用于键的哈希函数，那么通过构造一个充满参数的请求，这些参数的键都映射到同一个哈希桶，攻击者可以使服务器花费O(n²)时间处理这样的请求；事实证明，这足以用可笑的小量网络流量使Web服务器的CPU饱和。
关于故意创建哈希表碰撞以泄露地址的想法，也有更早的先前工作，正如关于同一主题的29C3演讲中指出的那样。Solar Designer早在1998年的Phrack第53期中写道：
—-[ 数据结构和算法选择
当为普通应用程序选择排序或数据查找算法时，人们通常优化典型情况。然而，对于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/
（正如我在那篇文章中指出的，这对于打破依赖于指针标记的概率性内存安全缓解措施可能特别有趣。如果指针的最高位是秘密的标记位，并且攻击者可以确定对象地址（包括标记位）的顺序，攻击者可以推断对象的标记在重新分配后是否发生了变化。）
从这里得到的启示是：键控数据结构不仅通过时序泄露有关对象哈希码的信息；遍历键控数据结构也可以生成其顺序揭示对象哈希码信息的数据。
序列化攻击
序列化对象图有多种方法。在频谱的一端是基于模式的序列化，理想情况下：
- 可序列化类型及其成员与其他类型分开声明
- 字段明确声明它们可以指向哪些其他类型（没有可以指向任何东西的通用指针）
- 反序列化从特定的起始类型开始
在序列化频谱的另一端是像经典Java序列化（没有序列化过滤器）这样的东西，其中本质上任何标记为Serializable的类都可以被反序列化，序列化字段通常可以灵活地指向许多不同的类型，因此序列化数据也可以对结果对象图的形状有很大控制。关于Java中"序列化小工具链"的主题有大量公开研究，其中对象可以组合，使得反序列化它们导致远程代码执行等结果。这种类型的序列化通常被认为不适合跨安全边界使用，尽管Android在本地安全边界内暴露它。
在这个频谱的中间某处是序列化，其构建方式本质上像不安全的反序列化，但添加了一些粗略的过滤器，只允许反序列化的对象具有来自允许列表的类型以使其安全。在Java中，这被称为"序列化过滤"。这也大致是苹果的NSKeyedUnarchiver.unarchivedObjectOfClasses的行为，本文重点讨论此功能。
人工测试用例
本文描述的技术目标是通过单次执行以下测试用例泄露指向"共享缓存"（一个大型映射，在系统上所有进程中位于相同的虚拟地址，其地址仅在重启时改变）的指针，该测试用例使用NSKeyedUnarchiver.unarchivedObjectOfClasses反序列化攻击者提供的对象图，该图由类型NSDictionary、NSNumber、NSArray和NSNull组成，重新序列化结果，并写回结果序列化数据：
@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，没有提供hash处理程序。当在像__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的哈希表为例：
bucket index: 0123456
bucket contents: #_#_#_#
这留下了三个可以插入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的更多信息：
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。
因此，通过向某个目标进程发送包含两个NSDictionary实例的序列化NSArray，这些实例具有这些NSNumber和NSNull键的模式，然后从受害者那里接收重新序列化的副本，攻击者可以确定NSArray的hash_code % num_buckets。
一些数学：泄露整个hash_code
为了泄露关于hash_code的更多信息，可以用不同的哈希表大小重复此操作。上一节的攻击泄露了hash_code % num_buckets，其中num_buckets是攻击者可以从可能的大小__CFBasicHashTableSizes中挑选的质数，基于每个NSDictionary中有多少元素。
这里一个有用的数学技巧是：基于计算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单例的地址。
复现程序
我为这个问题写了一个复现程序，包括我自己的在目标机器上运行的受害者程序，以及向目标机器提供序列化数据并从目标接收重新序列化数据的攻击者程序。（为了便于复现，你可以在单台机器上测试，我也是这样做的；尽管我在"攻击者"和"目标"之间重启以确保攻击者不使用与目标相同的共享缓存地址。）
首先，在攻击者机器上生成序列化数据：
% clang -o attacker-input-generator attacker-input-generator.c
% ./attacker-input-generator > attacker-input.plist
% plutil -convert binary1 attacker-input.plist
然后，在目标机器上反序列化并重新序列化此数据：
% 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单例的真实地址：
% clang debug-nsnull-hash.m -fobjc-arc -fmodules -o debug-nsnull-hash
% ./debug-nsnull-hash
null singleton pointer = 0x1eb91ab60, null_hash = 0x00000001eb91ab60
然后，在攻击者机器上处理重新序列化的数据：
% 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而不是对象的地址可能会在查找的关键路径上增加内存加载。