title: “哈希碰撞攻击：为何一条HTTP请求能让服务器CPU飙升到100%” date: “2026-03-05T16:55:02+08:00” description: “深入解析哈希碰撞DoS攻击的技术原理：从2003年Crosby和Wallach的开创性论文到2011年横扫主流语言的安全危机，揭示确定性哈希函数如何将O(1)操作变成O(n²)灾难，以及SipHash如何成为现代语言的标准防线。” draft: false categories: [“安全漏洞”, “数据结构”, “Web安全”] tags: [“哈希碰撞”, “HashDoS”, “算法复杂度攻击”, “SipHash”, “哈希表”, “拒绝服务攻击”, “Web安全”]

2003年8月，莱斯大学的Scott Crosby和Dan Wallach在第12届USENIX安全会议上发表了一篇题为《Denial of Service via Algorithmic Complexity Attacks》的论文。他们在演讲中展示了如何用不到拨号调制解调器的带宽，让一台专用入侵检测系统服务器在六分钟内开始丢弃71%的流量。

八年后的2011年12月28日，oCERT发布了编号为2011-003的安全公告，宣布Java、PHP、Python、Ruby、ASP.NET、V8 JavaScript等主流语言和平台全部受到同类攻击影响。微软罕见地打破了常规补丁周期，在12月29日发布了紧急修复。

这个攻击的核心在于：程序员信赖的"O(1)“哈希表查找，在特定输入下会退化为O(n)甚至O(n²)。

哈希表的致命弱点

哈希表是现代编程语言中最核心的数据结构之一。它的设计承诺很诱人：平均情况下，插入、查找和删除操作的时间复杂度都是O(1)。这个承诺建立在一个假设之上——哈希函数能将键均匀地分散到各个桶（bucket）中。

当两个不同的键被映射到同一个桶时，就发生了哈希碰撞。最常见的处理方式是链地址法（separate chaining）：每个桶维护一个链表，所有哈希到该桶的元素都存储在链表中。

graph LR
    subgraph 正常状态
        A0[桶0] --> A1[元素A]
        A1 --> A2[元素B]
        A2 --> A3[null]
        B0[桶1] --> B1[元素C]
        B1 --> B2[null]
        C0[桶2] --> C1[元素D]
        C1 --> C2[元素E]
        C2 --> C3[元素F]
        C3 --> C4[null]
    end

在正常情况下，每个桶的链表很短，查找操作几乎是常数时间。但如果攻击者能让大量键碰撞到同一个桶，哈希表就会退化成链表：

graph LR
    subgraph 攻击状态
        A0[桶0] --> A1[恶意键1]
        A1 --> A2[恶意键2]
        A2 --> A3[恶意键3]
        A3 --> A4["..."]
        A4 --> A5[恶意键N]
        A5 --> A6[null]
        B0[桶1] --> B1[null]
        C0[桶2] --> C1[null]
    end

当所有N个键都碰撞到同一个桶时，插入第N个元素需要遍历前N-1个元素，总插入时间变成O(n²)。这就是哈希碰撞攻击的数学本质。

等价子串：从两个种子到无限碰撞

攻击的关键在于如何高效地生成大量碰撞键。大多数语言使用的哈希函数都有一个致命特性：等价子串（equivalent substrings）。

以Java的String.hashCode()为例，它使用的哈希函数是：

h = 0
for each character c in string:
    h = 31 * h + c

在这个函数中，字符串"Aa"和"BB"产生相同的哈希值（2112）。更重要的是，由于乘法结合律，如果两个子串哈希值相同，那么在相同位置替换它们，整个字符串的哈希值也相同。

这意味着：

  • “Aa"和"BB"碰撞
  • “AaAa”、“AaBB”、“BBAa”、“BBBB"四个字符串全部碰撞
  • 以此类推，2n个字符可以产生2^n个碰撞字符串

攻击者只需要找到一对碰撞种子，然后通过排列组合就能生成任意数量的碰撞键。对于Java来说，64个字符长度的字符串可以产生2^32个碰撞——远超任何哈希表的处理能力。

中间相遇攻击：破解"更安全"的哈希函数

并非所有哈希函数都有等价子串特性。PHP使用的DJBX33A变体、Python使用的哈希函数都没有这个弱点。但这并不意味着它们安全。

Alexander Klink和Julian Wälde在2011年的研究中展示了**中间相遇攻击（meet-in-the-middle attack）**如何攻破这些哈希函数。

假设哈希函数输出32位，内部状态也是32位。攻击者将字符串分成前缀和后缀两部分：

  1. 遍历所有可能的后缀，计算达到目标哈希值所需的中间状态，存入查找表
  2. 遍历所有可能的前缀，检查是否能达到查找表中的某个中间状态

这种方法将暴力破解的复杂度从O(2^32)降低到O(2^16)。在现代CPU上，几分钟就能找到数千个碰撞。

一条POST请求的杀伤力

n.runs安全团队在2011年的安全公告中披露了攻击的实际效果：

平台 CPU消耗 所需带宽
Java/Tomcat (2MB POST) 44分钟 6 kbit/s
ASP.NET 90秒 30 kbit/s
PHP (8MB POST) 4小时 70-100 kbit/s
Python/Plone (1MB POST) 7分钟 20 kbit/s
Ruby (2MB POST) 6小时 850 bit/s

这些数字令人震惊：攻击者只需几十kbps的带宽——不到拨号上网的速度——就能让一台i7核心满载运行数小时。如果攻击者有1Gbps带宽，理论上可以让十万个CPU核心同时满载。

更可怕的是，攻击不需要特殊权限，不需要绕过防火墙，只需要向任何接受POST请求的表单提交精心构造的键值对。Web服务器会自动将这些数据解析到哈希表中，攻击就生效了。

Perl的先见之明

有趣的是，在2011年的大规模漏洞披露中，Perl是极少数"幸免于难"的语言之一。原因很简单：Perl早在2003年就修复了这个问题。

Crosby和Wallach的论文直接针对了Perl 5.6.1和5.8.0版本。Perl社区的反应是迅速的——Perl 5.8.1（2003年发布）引入了哈希随机化机制。当检测到异常的碰撞模式时，Perl会自动启用随机化的哈希种子。

这个"先见之明"实际上是被"打"出来的。但讽刺的是，尽管论文公开发表，尽管Perl已经修复，其他主流语言直到八年后才意识到问题的严重性。

Java的特殊困境

在所有受影响的语言中，Java的处境最为尴尬。Java的String.hashCode()返回值会被缓存在String对象的hash字段中——但有一个例外：当哈希值为0时不缓存。

这意味着攻击者如果选择哈希值为0的碰撞字符串，每次哈希计算都会重新执行，进一步放大攻击效果。Klink和Wälde的安全公告中特别指出：Java 2MB的碰撞POST请求可以消耗44分钟的CPU时间。

Oracle的反应令人失望。他们宣布"Java本身不需要修复”，只在后续版本的GlassFish应用服务器中增加了请求参数数量限制。这种态度导致了问题的持续存在。

直到JEP 180（Java 8，2014年）才引入了根本性的解决方案：当单个桶中的元素超过阈值（默认8个）时，将该桶的链表转换为红黑树。这将最坏情况从O(n)降低到O(log n)，使得碰撞攻击的成本大幅上升。

SipHash：为短输入设计的密码学PRF

2012年，密码学家Jean-Philippe Aumasson和Daniel J. Bernstein提出了SipHash——一个专门为哈希表设计的伪随机函数（PRF）。

SipHash的设计目标很明确：

  • 安全性：使用128位密钥，攻击者无法预测哈希值
  • 速度：针对短输入优化，因为哈希表的键通常很短
  • 简洁性：实现简单，便于审计

SipHash的核心是一个简单的轮函数，包含四个加法、四个异或和六个循环移位。SipHash-2-4（每消息块2轮，最终4轮）是推荐的配置，在保证安全性的同时提供良好性能。

graph TB
    subgraph SipHash处理流程
        A[128位密钥 k0, k1] --> B[初始化状态 v0-v3]
        B --> C[消息分块处理]
        C --> D[每块2轮SipRound]
        D --> E[填充与最终化]
        E --> F[4轮SipRound]
        F --> G[64位输出]
    end

关键是密钥的存在：由于攻击者不知道随机生成的128位密钥，即使知道算法，也无法预测哪些输入会碰撞。这从根本上解决了确定性哈希函数的安全问题。

各语言的应对时间线

语言/平台 修复方式 引入版本 时间
Perl 哈希随机化 5.8.1 2003
Ruby 1.9 哈希随机化 1.9.0 2008
PHP max_input_vars限制 5.3.9 2012.01
Python PYTHONHASHSEED随机化 2.6.8/2.7.3/3.2.3 2012.04
Ruby 1.8 哈希随机化 1.8.7-p357 2012
Java 桶内红黑树 Java 8 2014
Python 3.4 SipHash 3.4 2014
Rust SipHash（默认） 1.0 2015

Python的PEP 456（2013年）详细记录了选择SipHash的理由。PEP作者Christian Heimes明确指出，之前的FNV变体加上随机前缀后缀的方案是不安全的——攻击者可以通过分析恢复随机种子。只有密码学强度的哈希函数才能真正防止碰撞攻击。

Rust从第一个稳定版本开始就将SipHash作为HashMap的默认哈希算法。这是一个深思熟虑的设计选择：虽然SipHash比非密码学哈希函数慢，但对于通用哈希表来说，安全性比极致性能更重要。

性能与安全的权衡

SipHash不是免费的午餐。与MurmurHash、FNV等非密码学哈希函数相比，SipHash确实有性能开销。根据基准测试，SipHash-2-4的速度大约是MurmurHash3的一半左右。

但这个权衡是值得的。首先，哈希计算通常只是应用程序总开销的一小部分。Python的PEP 456基准测试显示，使用SipHash后整体性能影响在1%以内。其次，对于大多数应用来说，安全性比几个百分点的性能提升更重要。

Rust社区的经验很有启发性：如果确实需要极致性能，可以使用hashbrown库或切换到FxHash等非安全哈希函数。但默认选项必须是安全的——因为开发者往往不会意识到需要主动选择安全性。

更广泛的算法复杂度攻击

哈希碰撞攻击只是"算法复杂度攻击"这个大类中的一个例子。任何在"平均情况"和"最坏情况"之间有巨大差距的算法，都可能成为攻击目标：

  • 正则表达式DoS（ReDoS）：某些正则表达式引擎在处理特定输入时会回溯指数级次数。2019年7月2日，Cloudflare因一个正则表达式漏洞导致全球服务中断27分钟，影响了大量网站。
  • XML实体扩展（Billion Laughs）：嵌套的XML实体可以在几KB的输入中展开成数GB的数据。
  • DNS放大攻击：利用DNS响应通常比查询大得多的特性进行反射攻击。
  • 解析器复杂度：JSON、CSV等格式解析器如果实现不当，也可能被恶意输入利用。

这些攻击的共同点是：代码没有逻辑漏洞，只是算法的最坏情况被恶意触发。传统的安全审计很难发现这类问题，因为代码"看起来正确”——平均情况下确实是正确的。

现代防御策略

针对哈希碰撞攻击，现代系统采用多层防御：

第一层：密码学哈希函数

使用SipHash等带密钥的哈希函数，从根本上阻止攻击者预测碰撞。这是最彻底的解决方案，已被Python 3.4+、Rust、Ruby 2.0+等采用。

第二层：数据结构改进

即使发生碰撞，也要限制最坏情况的损害。Java 8的红黑树策略将最坏情况从O(n)改善到O(log n)。这意味着即使攻击成功，CPU消耗也只会是对数增长而非线性或二次增长。

第三层：输入限制

限制POST参数数量、请求大小等。PHP的max_input_vars（默认1000）就是一个例子。这种防御简单直接，但可能影响正常功能（比如需要上传大量数据的表单）。

第四层：运行时检测

监控哈希表的行为，检测异常的碰撞模式。当检测到攻击时，可以切换到更安全的哈希函数或拒绝请求。Perl的"随机扰动"机制就是这类方案。

开发者应该知道的

如果你正在开发接受用户输入的系统，有几个原则值得记住：

永远不要假设输入是随机的。攻击者会精心构造输入来触发最坏情况。任何"概率很低"的假设，在对抗性环境中都是危险的。

哈希表的键如果来自用户输入，必须使用安全哈希函数。大多数现代语言的标准库已经这么做了，但如果你在使用旧版本或自定义实现，需要特别注意。

关注时间复杂度的最坏情况，而不只是平均情况。安全审计时应该问：如果有人刻意触发最坏情况，会发生什么？

性能优化不应该以安全为代价。SipHash比MurmurHash慢，但这个"慢"是必要的代价。如果确实需要极致性能，应该在明确评估风险后做出知情选择。

哈希碰撞攻击揭示了一个深刻的教训：在安全领域，“概率很低"不等于"不会发生”。当攻击者有动机和能力去寻找那0.0001%的情况时，平均情况下的良好表现毫无意义。

从2003年的学术论文到2011年的大规模漏洞，再到今天SipHash成为主流标准，这个过程花了整整十年。而在另一个平行宇宙里，如果更多人在2003年就认真对待Crosby和Wallach的警告，2011年的那场危机也许就不会发生。

安全从来不是一次性解决的问题，而是持续对抗的过程。算法复杂度攻击这个类别，至今仍在不断产生新的变体。下次当你写下一行代码，假设某个操作是"常数时间"的时候，不妨多问一句：在什么情况下，这个假设会失效？

参考文献

  1. Crosby, S. A., & Wallach, D. S. (2003). Denial of Service via Algorithmic Complexity Attacks. USENIX Security Symposium.
  2. Klink, A., & Wälde, J. (2011). n.runs-SA-2011.004: Denial of Service through hash table multi-collisions.
  3. oCERT-2011-003: Multiple implementations denial-of-service via hash algorithm collision.
  4. Aumasson, J. P., & Bernstein, D. J. (2012). SipHash: a fast short-input PRF. INDOCRYPT.
  5. Heimes, C. (2013). PEP 456 – Secure and interchangeable hash algorithm.
  6. Duigou, M. (2013). JEP 180: Handle Frequent HashMap Collisions with Balanced Trees.
  7. US-CERT Vulnerability Note VU#903934.
  8. https://cr.yp.to/siphash/siphash-20120918.pdf