企业官网建设流程全解析

深入 .NET 运行时安全设计：Dictionary<TKey,TValue> 与 HashSet 的哈希洪水攻击防护指南

【免费下载链接】runtime.NET is a cross-platform runtime for cloud, mobile, desktop, and IoT apps.项目地址: https://gitcode.com/GitHub_Trending/runtime6/runtime

Dictionary<TKey, TValue>与HashSet<T>是 .NET 生态中最基础、使用最广泛的键控集合类型，正因其无处不在，消费方往往在自身安全分析中隐式假设它们具备某种安全保证。本文以 docs/design/security/System.Collections.Generic.Dictionary.md 为骨架，结合当前仓库中System.Private.CoreLib的真实实现（Dictionary.cs、HashSet.cs、NonRandomizedStringEqualityComparer.cs、RandomizedStringEqualityComparer.cs），系统讲解这两类集合的安全承诺与非承诺、底层防哈希洪水机制（碰撞阈值 + 每实例随机种子重哈希）、复杂度保证，以及反序列化场景下的攻击面与防御建议。读完本文，你将掌握：哪些实例化方式对恶意键输入是安全的、为什么Dictionary<int, ...>默认不抗哈希洪水、碰撞检测与重新哈希的源码级原理，以及如何安全地反序列化字典载荷。

摘要：安全使用的核心结论

为避免算法复杂度攻击（即哈希洪水攻击），建议仅使用Dictionary<string, ...>和HashSet<string>这两种类型实例化，并且只能在以下构造方式下使用：

• 不传比较器的构造函数（内部回退到EqualityComparer<TKey>.Default）；
• 向构造函数传入null作为比较器；
• 传入内置（inbox）的StringComparer实例，优先推荐StringComparer.Ordinal与StringComparer.OrdinalIgnoreCase。

其余泛型实例化——如Dictionary<int, ...>、Dictionary<long, ...>、Dictionary<Guid, ...>、Dictionary<Tuple<...>, ...>及其对应的HashSet<T>——默认不保证对不受信任输入安全。调用方必须自行构造具备抗哈希洪水能力的比较器（见附录 A）。文档还专门分析了使用序列化器从不信任载荷中重建字典实例的“序列化特定安全问题”，并给出对消费方的一系列要求。

范围与适用对象

Dictionary<TKey, TValue>在逻辑上消费两类数据：

• 可选比较器：在构造时提供；
• 零个或多个键值对：键用于查找对应的值。

HashSet<T>在逻辑上可视为值恒为单位对象（unity object）的字典。本文关于Dictionary<TKey, TValue>的所有论述，除特别说明外，均同样适用于HashSet<T>。

本文不涵盖其他键控集合类型（如SortedDictionary<TKey, TValue>、SortedList<TKey, TValue>、ConcurrentDictionary<TKey, TValue>、Hashtable、NameValueCollection等），也不涵盖IDictionary<TKey, TValue>接口抽象，仅覆盖 .NET Framework 4.x 与 .NET 6+，并在相关处标注运行时行为差异。

本文的目标读者有三类：

• Dictionary<TKey, TValue>的维护者：需要理解并保持该类型的安全保证；
• Dictionary<TKey, TValue>的消费方：依赖这些保证的应用程序开发者；
• IEqualityComparer<T>的实现者：需要满足内置字典类型预期的保证。

总体安全态势

Dictionary<...>实例仅在采用本文点名的安全构造方式时，才可安全地从恶意键输入中填充。若使用其他任何构造方式，恶意输入可能触发消费应用中的安全漏洞，最可能的结果是通过哈希洪水攻击造成拒绝服务（DoS）。

若字典被应用代码误用——例如不正确的多线程访问、实现了有缺陷的比较器逻辑——其内部状态可能被破坏。这最可能导致 DoS，但在极端情况下可能颠覆应用的正常业务逻辑，进而导致权限提升（Elevation of Privilege）。由于序列化器经常对字典做特判处理，本文设有“序列化特定安全问题”一节，列出对序列化库作者和序列化器消费者都有价值的潜在攻击向量。其中某些攻击（如失同步反序列化攻击 desynced serialization attack）已被攻击者在真实生产服务中用于实现权限提升。

字符串键字典（安全）

若实例被显式类型化为Dictionary<string, ...>或HashSet<string>，并且满足：

• 未向构造函数提供比较器；或
• 提供了内置的StringComparer实例；

则该实例保证免受哈希洪水攻击。集合类型内部具有检测哈希洪水攻击的逻辑，必要时会动态切换到不同的内部算法（详见后文“已知安全比较器的防御”及附录 B）。

该逻辑仅存在于TKey = string的字典。其他实例化，例如Dictionary<object, ...>（即使只填充字符串键），也不会自动获得此保护。

提醒

本文讨论的安全考虑远不止哈希洪水攻击，这些考虑适用于所有字典实例，包括Dictionary<string, ...>。

非字符串键字典（默认不安全）

如果实例是其他泛型实例化，如Dictionary<object, ...>、Dictionary<int, ...>、Dictionary<Guid, ...>、Dictionary<Tuple<...>, ...>，则不应假设存在自动的哈希洪水保护。对攻击者而言，触发哈希洪水可能易如反掌——附录 C 给出了对HashSet<int>发起哈希洪水攻击的完整示例。

如果这些字典实例可能暴露给对抗性键输入，则实例化字典的代码有责任选择能够提供适当抗哈希洪水能力的IEqualityComparer<T>。

警告

IEqualityComparer<T>或IEquatable<T>的实现者在用System.HashCode实现哈希例程前，应查阅 System.HashCode 安全设计文档。该文档列出了HashCode类型的重要保证与非保证，并深入讨论了什么才是良好的哈希例程。

输入可信度

字典的比较器与容量构造参数被假定为可信（见下节“比较器的选择”）。

• 若键具有对抗性，只有IEqualityComparer<T>.GetHashCode的输出具备抗哈希洪水能力时，字典类型才被保证行为良好；否则假定键是非对抗性的。
• 值是不透明的，可能包含对抗性数据。字典类型本身在收到对抗性值时不会表现出不良行为，但应用代码应对收到此类值保持韧性（参见后文对ContainsValue的讨论）。

核心假设

比较器的选择

传给构造函数的IEqualityComparer<T>被假定为可信。这里的“可信”指：所选比较器完全由调用方控制，且调用方已为字典的使用上下文选择了恰当的比较器。例如，对于基于字符串的字典，实例化代码应预先知道消费方期望该字典实例具备怎样的大小写敏感行为，并传入相应的比较器（通常是StringComparer）。

若未向构造函数提供比较器，则默认采用EqualityComparer<T>.Default。这一点在源码中清晰可见：Dictionary.cs 的构造函数对引用类型执行_comparer = comparer ?? EqualityComparer<TKey>.Default;——注释说明这样做的原因是：在共享泛型下每次访问都访问EqualityComparer<TKey>.Default会产生可测量的开销，因此对引用类型总是显式存储比较器实例。

比较器行为与算法复杂度

比较器须遵循 API 文档中列出的通用哈希码与相等性计算指南（Object.GetHashCode）。这些计算对任何给定的比较器实例必须保持稳定，但不要求跨进程稳定（甚至不要求同一比较器类型的不同实例之间稳定）。

复杂度假设如下：

• 比较器的GetHashCode方法复杂度为$O(l)$，其中 $l$ 是传入对象的逻辑大小；
• 比较器的Equals方法复杂度为$O(l_L + l_R)$，其中 $l_L$ 与 $l_R$ 分别是左右两个对象的逻辑大小。

“逻辑大小”的确切含义取决于传入对象的类型。一个实用的定义是：在网络上表示目标对象所需的字节数。对变长输入字符串，通常是字符串的长度（字节数）；对 POD 结构体，通常是各字段逻辑大小之和。

比较器GetHashCode分布的均匀性

比较器的GetHashCode例程被假定在消费它的字典实例中将出现的所有输入键的域上提供近似均匀的分布。

若键由对手提供，比较器必须防御哈希洪水攻击。.NET 字典基于桶（bucket）实现，这意味着字典实例可以自由地进一步缩减计算出的哈希码值。也就是说，虽然GetHashCode的输出是 32 位、拥有 40 亿个可能的哈希码值，但字典实例可以确定性地将其映射到小得多的范围（例如 $[0, 16]$ 内的整数）。实际上这意味着：在当前的字典实现下，随机化比较器是对抗恶意输入的最佳防御（详见附录 A）。

键不可变性

键一旦插入字典，必须保持不可变。任何会影响比较器哈希码或相等性计算的键对象修改都是非法的，一旦发生，字典实例的行为不再良定义——可能错误地报告键存在/不存在、为给定键返回错误的值，甚至查找陷入无限循环。这并非所有可能负面行为的详尽清单。

字典与比较器的线程安全

Dictionary<TKey, TValue>对修改操作（插入与更新）不线程安全，但对读取操作（ContainsKey、TryGetValue、枚举等）设计为线程安全。不正确的多线程修改可能导致类似“键不可变性”一节所述的异常行为。

这要求比较器操作同样线程安全：比较器必须预期多个线程并行调用GetHashCode或Equals。实践中，比较器实例不线程安全会非常反常，但哈希码记忆化（memoization）等模式如果实现不当，会无意引入竞态条件。

使用与复杂度保证

定义

• $l$：键的逻辑大小（表示键数据所需的大致字节数）；
• $n$：字典中的条目数，$l_i$ 是键 $i$ 的逻辑大小（$0 \le i < n$）；
• $l_\mathit{avg}$：字典中每个键的平均长度。乘积 $n \cdot l_\mathit{avg}$ 可视为该字典在网络上表示（不含值）所需的字节数，也可理解为字典的“总”大小（不含值）。

构造

当提供容量参数时，集合类型会主动分配足够容纳指定容量的后备数组，这是$O(\text{capacity})$操作。源码中，Dictionary.cs 通过HashHelpers.GetPrime(capacity)将请求的容量向上取整到合适的素数，避免桶数量为合数时产生的取模偏差。

构造函数还可以接受一个现有集合进行克隆。若提供了集合，其元素会逐个插入新字典实例（见下节）。Dictionary.cs 的AddRange对源类型恰为Dictionary<TKey, TValue>的情形做了优化：当两个实例的比较器相同时直接复制_entries数组而无需重新哈希；比较器不同时才逐个Add重新哈希。

查找

查找操作包括ContainsKey、TryGetValue、索引器 getter，以及AlternateLookup<TAlternateKey>上对应的 API。HashSet<T>.Contains(T)也是查找操作。

查找一个键分两步：

1. 通过GetHashCode确定条目应存在的桶索引；
2. 对该桶中每个哈希码匹配的条目调用Equals，直到某个返回true。

对目标键而言，GetHashCode调用是$O(l)$复杂度。假设哈希码分布良好，每个桶平均只有一个条目，且该条目的哈希码仅在高似然匹配时才与键本身匹配——若哈希码不匹配，查找终止，只付出了 $O(l)$ 的工作量；若需验证相等性，将额外调用一次Equals（逻辑长度为 $l$ 的相同键），复杂度为 $O(l + l)$，仍是 $O(l)$，只是常数因子稍高。

若哈希码分布不良，字典可能退化到所有条目落入同一桶的极端情况，每次查找都要查询全部条目后才返回false，导致 $n$ 次Equals调用，总复杂度$O(n \cdot (l_\mathit{avg} + l))$——即每次查找的时间与字典“总”大小（$n \cdot l_\mathit{avg}$）成正比。

即使哈希码互不相同，多个不同哈希码值也可能被归入同一桶。遍历桶内条目时，字典会跳过哈希码不匹配的键避免调用Equals，但遍历整个桶仍是线性 $O(n)$ 操作。若 $n \gg l_\mathit{avg}$，每次查找可能耗时与字典总大小成正比。

字典还有ContainsValue方法，用于判断集合中是否存在给定值。该操作完全不使用字典捕获的比较器，也不用桶优化，而是通过EqualityComparer<TValue>.Default对字典实例的全部元素做线性搜索。

插入与修改

插入与修改操作包括Add、Remove、索引器 setter，以及AlternateLookup<TAlternateKey>上对应的 API。

插入或修改必然涉及一次查找。若存在匹配项，根据调用方的期望行为，会替换该条目或抛出异常。插入与修改在首次查找之后是摊还 $O(1)$操作，因此查找是唯一值得分析的成本。

插入与修改通常批量进行，因此值得分析循环调用时的行为。假设哈希码分布良好（查找为 $O(l)$），完全填充字典的总成本为$O(n \cdot l_\mathit{avg})$，这使得字典能高效地从线数据（wire data）重建。（后备数组扩容有簿记开销，但追加仍是摊还 $O(1)$，可排除在分析外。）

若哈希码分布不良，每次查找耗时与字典中已有数据总量成正比。由于每次插入都是 $O(n \cdot l_\mathit{avg})$，且有 $n$ 次插入，最坏情况总复杂度为$O(n^2 \cdot l_\mathit{avg})$——填充字典所需时间随输入载荷长度二次方增长。

注意

该最坏情况分析解释了为何键可能包含对手提供的数据时，应用必须只使用已知安全的比较器。$O(n^2)$ 复杂度算法对大多数应用而言都构成拒绝服务。

若无法使用已知安全比较器，应用仍可通过限制 $n$ 或 $l_\mathit{avg}$（或两者）的最大值来自我防御。例如限制字典最多 100 个条目、每个键不超过约 1 KB。某些集合——如Dictionary<byte, ...>——因输入域本身极小，天然限制了 $n$。

枚举

枚举集合是$O(n)$操作。就枚举而言，键和值被视为不透明对象，不会调用比较器。应用对枚举数据执行的任何操作超出本文范围。

序列化特定的安全问题

传统序列化模式

虽然Dictionary<TKey, TValue>标注了[Serializable]以支持传统 .NET 序列化模式，但使用该模式反序列化不受信任的序列化载荷并不安全。反序列化恶意实例即使使用“安全”的序列化器，也可能通过进程崩溃或触发无限循环造成 DoS。

反序列化字典实例时，应始终使用对字典有一流支持的反序列化器，而不是依赖传统序列化模式的序列化器。

提醒

传统序列化注解（[Serializable]与ISerializable）只说明某个类型可以被序列化与反序列化，不代表这样做是安全的。

对手提供的比较器构造参数

如前所述，构造函数的比较器参数被假定为可信。比较器的选择应始终由应用代码决定，绝不由传入的载荷决定。若对手能指定与应用内部逻辑预期不同的比较器，就可能颠覆应用的业务逻辑。文档给出了如下攻击示例：

// 前端接收序列化后的字典载荷，需要将其转换为后端可理解的格式（如 JSON）。 // 前端还向字典中注入 UNAUTHENTICATED = true，以便后端识别该请求来自未认证用户。 void ForwardRequestToBackend(byte[] serializedPayload) { Dictionary<string, string> dict = Deserialize(serializedPayload); dict["UNAUTHENTICATED"] = "true"; // 添加或替换条目 string reserialized = System.Text.Json.JsonSerializer.Serialize(dict); SendToBackend(reserialized); }

正常情况下，前端可能收到"Name" := "Lisa Doe"、"Age" := "45"，并向后端发送{ "Name": "Lisa Doe", "Age": "45", "UNAUTHENTICATED": "true" }。

现在假设对手改发原始载荷：(comparer) := InvariantCulture、"Name" := "Lisa Doe"、"Age" := "45"、"UNAUTHENTICATED\u200D" := ""。由于在不变文化（invariant）比较器下"UNAUTHENTICATED"与"UNAUTHENTICATED\u200D"等价，示例中的“添加或替换”一行最终会复用原始载荷中"UNAUTHENTICATED\u200D"的槽位，而不是引入新的"UNAUTHENTICATED"槽位。最终发送到后端的载荷为{ "Name": "Lisa Doe", "Age": "45", "UNAUTHENTICATED\u200D": "true" }——攻击者借此让前端遗漏必需的"UNAUTHENTICATED": "true"标记，后端因看不到预期标记可能走上意外代码路径，将该载荷视为已认证。

注意

大多数对字典提供一流支持的现代序列化器不允许载荷指定比较器，它们回退到创建包裹EqualityComparer<TKey>.Default（等价于StringComparer.Ordinal）的字典。

对手提供的容量构造参数

容量构造参数是优化手段：当调用方预先知道将向集合添加多少元素时，可让字典实例急切分配底层数据结构。若该值由对手指定，过度分配可能导致 OOM，进而造成 DoS。

序列化器被建议不要传递容量参数，而让字典实例随元素添加动态扩容。若序列化器出于性能目标必须指定容量，可考虑以下缓解措施之一：

• 将容量钳制到小的安全值，并允许字典随条目添加动态增长。例如用Math.Clamp(untrustedValue, 0, 20)将初始创建限制为最多 20 个条目，超过 20 个条目时字典自然扩展；
• 验证传入载荷确实包含其声明的元素数量。注意不要向读取器中引入易受攻击的回溯逻辑。

对手提供的TKey或TValue

由于Dictionary<TKey, TValue>是泛型类型，对手可能试图诱骗序列化器创建包含特权（或恶意！）TKey或TValue类型参数的字典。例如诱骗序列化器创建Dictionary<string, Process>，以此为跳板获得进程启动能力。

对手能在载荷内指定类型信息的攻击向量在 .NET 生态（及其他生态如 Java）中广为人知。序列化器负责防御这些攻击，这超出本文范围。

失同步反序列化（Desynced deserialization）

在失同步反序列化攻击中，对手构造包含歧义数据的载荷，然后将其发送给两台不同的服务器（如前端与后端，或联合认证服务器与依赖方）。对手希望两台服务器对歧义的处理方式不同，并利用这种差异获利。

考虑对手向登录处理器提交如下 JSON 载荷：

{ "username": "admin", "username": "evil", "password": "evil-password" }

登录处理器可能由两个不同组件支撑——成员数据库服务和认证令牌铸造服务（可能由不同团队开发）。两台服务看到的是完全相同的 JSON 载荷（因为只向服务器发送了一个请求），但载荷因username字段多次出现而产生歧义。

• 若成员数据库服务采用“最后一个字段胜出”规则去歧义，其反序列化的字典读作"username" := "evil"、"password" := "evil-password"，查找成功并返回 OK；
• 控制权随后转到令牌铸造服务。若它采用“第一个字段胜出”策略，反序列化同一载荷读作"username" := "admin"、"password" := "evil-password"，铸造服务丢弃密码，为 “admin” 用户铸造认证 cookie 并返回给客户端。

攻击成功：攻击者以 admin 身份获得认证令牌。

对于特判字典的序列化器，防止此攻击最可靠的方式是从源头避免歧义：与其采用“最后字段胜出”“第一字段胜出”或“拼接某字段的所有出现”等策略，不如默认让反序列化操作直接失败，这样反序列化器就无法被用于失同步反序列化攻击。

提示

使用Dictionary<TKey, TValue>.Add(TKey, TValue)方法而非索引器 setter，会在同一键在集合中多次出现时强制抛出异常。HashSet<T>.Add(T)在相同项多次出现时不会抛出异常；但失同步反序列化攻击不适用于哈希集。

空值与可空引用类型（NRT）注解

Dictionary<TKey, TValue>不能包含 null 键，但可以包含 null 值（若TValue是引用类型或可空值类型）。许多序列化器不遵循目标类型上的 NRT 注解，对手可能希望发送含 null 的特制载荷，在应用中触发NullReferenceException。

HashSet<T>允许null 条目（若T是引用类型或可空值类型）。同样，序列化器可能不遵循目标类型上的 NRT 注解。

消费方应查阅序列化器文档，确认其是否强制执行 NRT 注解。若不强制，消费方应编写对字典和哈希集中可能出现的 null 值有韧性的代码。

已知安全比较器的防御机制

如附录 B 所述，某些Dictionary<string, ...>与HashSet<string>实例化对恶意键是安全的。这些保护最初随 CVE-2011-3414 提供，且无论全局字符串哈希码随机化是启用（.NET Core 1.0+ 默认）还是禁用（.NET Framework 默认）都持续有效。

为了提升性能，.NET Framework 与 .NET 中的Dictionary<string, ...>和HashSet<string>实例针对非恶意输入做了优化，尽可能使用非随机化的哈希码计算例程。为避免无界的 $O(n^2)$ 工作量，字典内部跟踪任一给定哈希桶观察到的碰撞次数。一旦该计数达到关键阈值（当前为 100，见 Dictionary.cs 与 HashSet.cs 中的collisionCount > HashHelpers.HashCollisionThreshold && comparer is NonRandomizedStringEqualityComparer判断），字典实例将使用抗碰撞的哈希码例程并配合该字典实例独有、随机生成的种子，对所有已有键执行重新哈希（Resize(newSize, forceNewHashCodes: true)，见 Dictionary.cs）。

源码印证了这套机制：

• 非随机化阶段：NonRandomizedStringEqualityComparer.cs 的GetStringComparer仅对EqualityComparer<string>.Default、StringComparer.Ordinal、StringComparer.OrdinalIgnoreCase三个特例返回包装比较器（三个静态单例见 L23-L25）。其GetHashCode使用GetNonRandomizedHashCode等快速例程（L85-L92），即文档所述“为改善性能而采用的非随机化例程”。
• 随机化切换：Dictionary构造函数在 L69-L76 对字符串键做特判，安装非随机化比较器。当碰撞超过阈值时，Resize(entries.Length, forceNewHashCodes: true)调用NonRandomizedStringEqualityComparer.GetRandomizedEqualityComparer()（NonRandomizedStringEqualityComparer.cs），并把比较器替换为 RandomizedStringEqualityComparer.cs 中基于Marvin32的随机化比较器，随后用新比较器对全部既有条目重新计算哈希码（Dictionary.cs）。
• 每实例种子：RandomizedStringEqualityComparer.cs 的构造函数通过Interop.GetRandomBytes为每个实例生成独立的 64 位MarvinSeed（p0/p1），Marvin32 哈希（Marvin.ComputeHash32，见 L82-L85）使用该实例级种子。这正是文档所说的“防御纵深”：即便全局/共享种子被侧信道泄露，每实例种子仍然独立。

每实例种子是针对任何可能无意泄露全局/共享种子的侧信道的纵深防御。仍存在字典实例自身通过侧信道泄露每实例种子的可能性；不过实践中问题不大，因为多数字典实例的预期生命周期不超过单个 Web 请求。

注意

每实例种子随机化仅适用于以 null 比较器、EqualityComparer<string>.Default、StringComparer.Ordinal或StringComparer.OrdinalIgnoreCase构造的字典。其他内置StringComparer实例（见附录 B）在字典内使用时仍享有哈希码随机化，但实现可能退而使用全局种子而非每实例种子。这可能是未来的改进机会，但由于此类比较器使用相对不频繁，对真实应用不应构成显著风险。

让其他内置类型（如long、Guid）乃至用户自定义类型在达到碰撞阈值后也参与这种哈希码随机化，可能会有所裨益。暴露此类功能本可简化对 CVE-2024-43483、CVE-2014-4072 和 GHSA-7q36-4xx7-xcxf 等问题的响应。详见 System.HashCode 安全设计文档 的“未来改进与考虑”一节。

值得一提的是，同类防御机制也存在于 ConcurrentDictionary.cs 等并发键控集合中，但本安全设计文档只对Dictionary<...>与HashSet<...>负责。

附录 A：关于GetHashCode哈希洪水的说明

注意

编写GetHashCode实现的哲学不在本文范围内。但鉴于Dictionary<TKey, TValue>自身的安全性确实依赖底层比较器哈希例程的特性，这里值得展开讨论。另见 System.HashCode 安全设计文档。

传统规则要求GetHashCode在整个可能输入域上提供均匀输出分布。但这是一条非常天真的规则，可能无意中造成伤害。考虑以下实现：

int GetHashCodeForString(string value) { // 返回输入字符串的前 32 位作为哈希码。 if (string.IsNullOrEmpty(value)) { return 0; } else if (value.Length == 1) { return value[0]; } else { return value[1] || (((int)value[0]) << 16); } }

如果每种可能的输入字符串等概率出现——即输入域本身均匀分布——这很完美。但现实世界并非如此：字符串有技术结构（除非应用有 bug，否则不会出现非法 UTF-16 序列）、有语言学结构（英文句子常以 “the” 等冠词或 “my” 等所有格开头，单个字母在单词中的分布并不均匀），其他书面语言也类似；HTTP 头字符串常用"X-"前缀，等等。

另一个例子，为定长 64 位输入计算 32 位哈希码：

int GetHashCodeForUInt64(ulong value) { return (int)value; // 只使用低 32 位 // - 或者 - // return (int)value ^ (int)(value >> 32); // 混合高 32 位与低 32 位 }

同样，如果所有输入整数等概率出现，这也没问题。该假设是否成立取决于具体场景。

真正可取的不是在“所有可能输入”域上的均匀分布，而是在“现实可能出现的输入”域上的均匀分布。仓库中就有遵循这一理念的比较器实现可供参照。

重要

若输入由对手提供，仅为“现实可能出现的输入”优化哈希码计算可能不切实际。对手能生成任意合法输入集合——甚至应用正常运行中不切实际的输入——以利用哈希码鸽笼效应触发哈希洪水攻击。这是一种拒绝服务（DoS）攻击，可导致应用对合法请求无响应。

仅模糊GetHashCode的结果不足以阻止哈希洪水攻击。字典这类键控集合常对返回的哈希码做算术运算，这开辟了新的攻击途径。例如字典常见做法是计算<hashCode> MOD <numBuckets>作为插入条目的桶索引。若对手知道当前使用 13 个桶，就可以尝试提交哈希码为 $0, 13, 26, 39, \ldots$ 的值，因为字典内部会把这些值视为相同的缩减哈希码。若比较器转而操作返回的哈希码值，使对手只知道某个输入哈希值为 $n$，则对手可尝试提交产生 $n, n+13, n+26, n+39, \ldots$ 哈希值的输入，即使不知道 $n$ 的实际值。这对对手是更高的门槛，但并非不可能。

对给定类型 $T$，理想化的相等性比较器模拟随机预言机 $\mathcal{O}(t \in T) \mapsto \mathtt{int32}$。这显然不切实际，因此实践中大多数相等性比较器使用一点熵作为密钥种子，配合具有合理抗碰撞与抗第一原像性质的键控哈希函数。该种子理想情况下按集合实例随机化，以限制种子经侧信道暴露的风险。详见 System.HashCode 安全设计文档。

若种子是静态的——即使按应用执行随机化——这些侧信道理论上可让对手构建哈希输出的定制数据库，进而发现种子信息。可行性取决于被哈希的数据与种子的熵量。更安全的设计是让集合实例本身（而非相等性比较器）负责生成熵，并在有攻击迹象时就地滚动熵。

附录 B：已知对哈希洪水攻击安全的实例化

重要

默认情况下，消费方不得假设除Dictionary<string, ...>之外的任何泛型实例化提供针对哈希洪水攻击的防御。

例如Dictionary<int, ...>、Dictionary<long, ...>、Dictionary<ValueTuple<...>, ...>、Dictionary<Guid, ...>默认都不应假设具备抗哈希洪水能力。

Dictionary<string, ...>实例仅在以下构造方式下对哈希洪水攻击安全：

• 调用不接受比较器参数的构造函数；
• 为构造函数比较器参数传null；
• 为构造函数比较器参数传EqualityComparer<string>.Default；
• 为构造函数比较器参数传任何内置StringComparer。

这里的“内置”指StringComparer类型上悬挂的静态单例属性（如Ordinal、OrdinalIgnoreCase），或由Create、FromComparison静态工厂方法创建的实例。自定义的StringComparer派生子类不被假设提供哈希洪水保护。

注意

若接受对手提供的字符串作为字典键，建议传入序数（ordinal）比较器：完全不传（默认回退到EqualityComparer<string>.Default）、显式传EqualityComparer<string>.Default、StringComparer.Ordinal，或StringComparer.OrdinalIgnoreCase。在接收对手提供字符串键的字典中使用任何其他比较器通常表明用法错误。

哈希洪水保护是集合类型自身的特性，而非所用StringComparer实例的特性。更多信息见 System.StringComparer 安全设计文档。

以下是在遵循上述构造规则（不传比较器、或EqualityComparer<string>.Default、或内置StringComparer）时，内置了哈希洪水攻击保护的完整集合类型清单：

• System.Collections.Generic.Dictionary<string, ...>
• System.Collections.Generic.HashSet<string>
• System.Collections.Concurrent.ConcurrentDictionary<string, ...>
• System.Collections.Hashtable
• System.Collections.Specialized.NameObjectCollectionBase
  • 以及内置子类类型如System.Collections.Specialized.NameValueCollection

提醒

只有Dictionary<...>与HashSet<...>在本安全设计文档范围内。虽然上述清单显示其他键控集合类型具备针对哈希洪水攻击的内置保护，但本文其余内容不应被假定适用于Dictionary<...>或HashSet<...>之外的类型。

附录 C：哈希洪水攻击演示

哈希洪水常被理解为鸽笼效应（pigeonholing）。例如字符串有无穷多个，但 32 位整数只有 $2^{32}$ 个，显然有些字符串必然产生相同的哈希值。这在 .NET Framework 4.8 应用中显而易见：

using System; // 在 32 位应用中以下各行都会打印 '0' Console.WriteLine("\uB5A7\uB5A7\uB5A7\uB5A7".GetHashCode()); Console.WriteLine("\uB1A2\u8BE2\u5678\u1234".GetHashCode()); Console.WriteLine("\u0578\u7134\uAAAA\uBBBB".GetHashCode());

然而，非鸽笼式的哈希码生成同样允许哈希洪水攻击。考虑实现int int.GetHashCode() => this;——int32 直接返回自身值作为哈希码。显然在此实现下每个整数输入都产生唯一哈希码，鸽笼效应不会发生。然而，由于字典底层数据结构固有的取模运算（见附录 A），仍可挑选全部落入同一桶的对抗性输入，即便实际哈希码值各不相同：

using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; Console.WriteLine("Count\tTime to add (ms)"); Stopwatch stopwatch = new Stopwatch(); for (int i = 0; i <= 60000; i += 1000) { var set = new HashSet<int>(capacity: i); int prime = HashHelpers.GetPrime(i); stopwatch.Restart(); for (int currentValue = 0; set.Count < i; currentValue += prime) { set.Add(currentValue); if (set.Count < i) { set.Add(currentValue | int.MinValue); } } Console.WriteLine($"{set.Count}\t{stopwatch.ElapsedMilliseconds}"); } // ref: https://github.com/microsoft/referencesource/blob/4.6.2/mscorlib/system/collections/hashtable.cs#L1655 static class HashHelpers { private static readonly int[] primes = new int[] { 3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369 }; public static int GetPrime(int min) => primes.First(prime => prime >= min); }

将该程序输出绘制为折线图，即可看到哈希洪水攻击特有的 $O(n^2)$ 增长——即使对Dictionary<int, ...>与HashSet<int>也是如此（见本文开头配图，横轴为元素数量、纵轴为填充耗时，曲线在元素数超过约 20000 后斜率明显增大）。这就是默认非字符串键字典不安全的实证。

相关文档

• System.HashCode 安全设计文档：HashCode类型的保证与非保证、良好的哈希例程应具备的特质，以及未来改进方向；
• System.StringComparer 安全设计文档：序数比较器与语言比较器的安全特性、NLS/ICU 差异、持久化数据的跨运行时排序风险。

【免费下载链接】runtime.NET is a cross-platform runtime for cloud, mobile, desktop, and IoT apps.项目地址: https://gitcode.com/GitHub_Trending/runtime6/runtime