哈希表之殇

2011 年 12 月 28 日，由 Google 赞助成立的安全漏洞研究组织 oCERT（Open source Computer Emergency Response Team — 开源软件应急响应团队）公开了一份安全漏洞报告。这份报告是几个月前由德国安全研究公司 nrun.com 所提供的，其核心内容是：目前绝大多数的 web 应用，都存在着一个叫做哈希碰撞式拒绝服务攻击的漏洞（Hash Collision DoS）。这份报告的公布，使得 2011 年剩下的几天里，各互联网公司的技术团队集体忙于对网站进行针对此漏洞的防护工作。硝烟散尽之后，让我们一起从攻击者的角度重新审视一下这个漏洞及其利用手法。

如果你熟悉几种常用语言下的哈希表（HashTable）实现，你大概会清楚以下的一些关于哈希表的基本概念：

1. 哈希表通过一个哈希函数对键值（key）进行散列操作，并且最终根据散列结果将键值对（key-value-pair）储存到数组的某个节点（一般通过对数组长度取余实现）。
2. 哈希表的数组长度会根据元素的实际数量动态进行扩容，以保证有足够空间并降低取余后的结果出现重复的可能性。不同的实现，其初始默认长度、扩容条件及扩容算法均可能有所区别。

极端情况下，哈希表将会退化成链表。根据上面的基础知识，我们知道这里的极端情况包括两种：所有元素的哈希值相等；或者所有元素的哈希值针对哈希表数组长度取余的结果相等。而退化为链表则会导致哈希表性能的急剧下降。实际测试中，针对 8 万条级别的数据，原本只需要数毫秒即可完成的插入或者查询操作，在退化为链表后则需要长达 30 秒以上的时间才能完成。

那么对攻击者来说，利用这一原理对某个 web 站点发起拒绝服务攻击只需要考虑以下两个问题：

• 问题一、如何构造一个可使哈希表完全退化成链表的键值集合。
• 问题二、如何使用该集合引导目标服务器建立一个哈希表数据结构。

针对问题一，具体的思路很简单，就是要找到一个字符串集合，使得该集合的每个元素要么满足哈希值相等；要么使得其哈希值针对哈希表数组长度取余的结果相等。构造大量的哈希冲突是一个比较困难的问题。但是对攻击者来说，非常幸运的是目前常见的哈希表的哈希函数实现，都是基于著名的 DJBX33 哈希算法或者其变形算法。比如，PHP5 使用的是 DJBX33A；ASP.NET 和 Python 使用的是 DJBX33X；Java 使用的是一个做了两个常数变形的变种 DJBX33A。针对这些哈希算法，攻击者已经可以有很多方法做针对性的哈希碰撞生成了。最常用的方法有“相等子串法”和“中间相遇法”等。以“相等子串法”为例，由于 DJBX33A 系列哈希算法满足一个很有意思的特性：如果 hash(“string1”) = hash(“string2”)，那么在相同位置包含此 2 个子串的父串哈希结果将会产生碰撞，既：hash(“prefix_string1_postfix”) = hash(“prefix_string2_postfix”)。根据这一特性，攻击者如果能找到最简单的两个碰撞字符串，那么就可以很快通过反复组合，生成 2 的 n 次方个长度为 2n 的碰撞字符串。“中间相遇法”事实上是一种暴力破解办法。只不过通过巧妙删选缩小了结果集的甄别范围，然后在可能产生碰撞的结果集中遍历寻找碰撞集合。除此之外，针对较为复杂的哈希算法的碰撞，如 MD5 等算法，我国的王小云教授的“模差分法”是一种比较实用的碰撞分析方法。

如果通过算法构造哈希结果完全一致的字符串集合有难度，那么也可以退而求其次，只要满足哈希值对哈希表数组长度取余的最终结果相等就可以了。网上目前有很多针对 PHP 的示例攻击代码，就是根据这个原理实现的。利用这种方式，需要对该语言下哈希表数组经过反复扩容后的最终长度如何产生有一个清楚的了解。例如在 PHP 的实现中，所有哈希表数组的长度一定是 2 的 n 次方。根据元素总个数和加载因子（一个哈希表实现中满足扩容条件的临界值），就可以计算出最终生成的哈希表的数组长度。剩下的事情就只需要保证待选键值的哈希结果对这个长度取余的结果相等，这样即可达到制造大量哈希冲突字符串的目的。

在成功构造好一个可以使哈希表完全退化成链表的键值集合后，攻击者需要来解决第二个问题：如何使用该集合在服务器端建立一个哈希表数据结构。

这个问题事实上已经再简单不过了：在所有的 web 应用中，为了方便程序对 web 请求的各项参数进行快速读操作，HTTP Request 中的 Header, Form 以及 QueryString，都使用了哈希表进行存储。那么剩下的工作很简单：就是以我们精心构造好的键值列表作为一次 HTTP 请求的 Header，Form 或者 QueryString 就可以了。实际攻击中，由于大量 Form 表单的 Post 构造更加简单，甚至可以使用浏览器完成，所以也会通常成为进行攻击的首选突破口。通过在单机上重复构造大量的 HTTP Post 请求，向 Web 服务器发送大量表单数据，会使得目标服务器的 CPU 迅速被占满而失去服务能力，达到攻击目的。

如果对方的服务器数量比较多，或者防火墙敏锐地发现了攻击者短时间内向服务器 Post 大量数据的行为，并进行了阻截，那么有可能还是达不到让对方“拒绝服务”的目的。这种情况下，攻击者会倾向于使用一定数量的“僵尸网络”对目标发起攻击。由于这个攻击非常简单，只需要构造一个 HTTP 请求即可实现，那么你可以去自己创建一个内容非常吸引人的页面，或者利用一个访问量较大但是存在跨站脚本漏洞（XSS）的页面，在页面中加入一小段对最终用户不可见，但是会自动发送一个 Post 请求到目标站点的 JavaScript 脚本，你的拒绝服务攻击（DoS）就成功升级为分布式拒绝服务攻击（DDoS）了。而访问这些页面的普通用户，则会在不知情的情况下成为帮助你继续攻击的“僵尸”群。

文章的最后，还是想补充一下关于针对这类攻击的防护工作。目前绝大部分的补丁都是针对 HTTP 请求中表单项的数量加以限制。这个方法确实有效。测试数据显示，1000 个元素的链表操作对性能的影响还是可以接受的。但是如果你的 Web 应用在服务端需要接收某个表单项，并通过字符处理（不管是 XML 还是 JSON）将用户输入的表单值转换成哈希表的话，那么很遗憾，目前这些补丁都帮不了你，你的应用将依然存在被拒绝服务攻击的可能。只不过攻击的方式从构造 HTTP Request 中的哈希表，变成了构造实际业务处理代码中的哈希表。对这一问题的完美解决方案，应该是如 Perl 在 n 年前做的那样：在哈希算法中引入随机盐使得构造哈希冲突变为不可能。

参考文章

• http://www.ocert.org/advisories/ocert-2011-003.html
• http://www.nruns.com/_downloads/advisory28122011.pdf

关于作者

殷钧钧（ Joey Yin ），Web 开发者，某外企企业架构师。业余时间，他是一名白帽子，独立安全组织 OWASP 成员。主要关注的技术领域有应用安全、分布式系统架构、以及程序员的敏捷实践。个人博客： http://unclejoey.com 。

感谢郑柯对本文的审校。

给InfoQ 中文站投稿或者参与内容翻译工作，请邮件至 editors@cn.infoq.com 。也欢迎大家通过新浪微博（ @InfoQ ）或者腾讯微博（ @InfoQ ）关注我们，并与我们的编辑和其他读者朋友交流。