哈希表之殇

此文为Infoq中文站QSecurity专栏供稿

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

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

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

极端情况下，哈希表将会退化成链表。根据上面的基础知识，我们知道这里的极端情况包括两种：所有元素的哈希值相等；或者所有元素的哈希值针对哈希表数组长度取余的结果相等。而退化为链表则会导致哈希表性能的急剧下降。实际测试中，针对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年前做的那样：在哈希算法中引入随机盐使得构造哈希冲突变为不可能。