• 欢迎访问本网站,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站 QQ群
  • Git主题现已支持滚动公告栏功能,兼容其他浏览器,看到的就是咯,在后台最新消息那里用li标签添加即可。
  • 最新版Git主题已支持说说碎语功能,可像添加文章一样直接添加说说,新建说说页面即可,最后重新保存固定连接,演示地址

PHP哈希表碰撞攻击原理

最近哈希表碰撞攻击(Hashtable collisions as DOS attack)的话题不断被提起,各种语言纷纷中招。本文结合 PHP 内核源码,聊一聊这种攻击的原理及实现。

哈希表碰撞攻击的基本原理

哈希表是一种查找效率极高的数据结构,很多语言都在内部实现了哈希表。PHP 中的哈希表是一种极为重要的数据结构,不但用于表示 Array 数据类型,还在 Zend 虚拟机内部用于存储上下文环境信息(执行上下文的变量及函数均使用哈希表结构存储)。

理想情况下哈希表插入和查找操作的时间复杂度均为 O(1),任何一个数据项可以在一个与哈希表长度无关的时间内计算出一个哈希值(key),然后在常量时间内定位到一个桶(术语 bucket,表示哈希表中的一个位置)。当然这是理想情况下,因为任何哈希表的长度都是有限的,所以一定存在不同的数据项具有相同哈希值的情况,此时不同数据项被定为到同一个桶,称为碰撞(collision)。哈希表的实现需要解决碰撞问题,碰撞解决大体有两种思路,第一种是根据某种原则将被碰撞数据定为到其它桶,例如线性探测——如果数据在插入时发生了碰撞,则顺序查找这个桶后面的桶,将其放入第一个没有被使用的桶;第二种策略是每个桶不是一个只能容纳单个数据项的位置,而是一个可容纳多个数据的数据结构(例如链表或红黑树),所有碰撞的数据以某种数据结构的形式组织起来。

不论使用了哪种碰撞解决策略,都导致插入和查找操作的时间复杂度不再是 O(1)。以查找为例,不能通过 key 定位到桶就结束,必须还要比较原始 key(即未做哈希之前的 key)是否相等,如果不相等,则要使用与插入相同的算法继续查找,直到找到匹配的值或确认数据不在哈希表中。

PHP 是使用单链表存储碰撞的数据,因此实际上 PHP 哈希表的平均查找复杂度为 O(L),其中 L 为桶链表的平均长度;而最坏复杂度为 O(N),此时所有数据全部碰撞,哈希表退化成单链表。下图 PHP 中正常哈希表和退化哈希表的示意图。

PHP 哈希表碰撞攻击原理

哈希表碰撞攻击就是通过精心构造数据,使得所有数据全部碰撞,人为将哈希表变成一个退化的单链表,此时哈希表各种操作的时间均提升了一个数量级,因此会消耗大量 CPU 资源,导致系统无法快速响应请求,从而达到拒绝服务攻击(DoS)的目的。

可以看到,进行哈希碰撞攻击的前提是哈希算法特别容易找出碰撞,如果是 MD5 或者 SHA1 那基本就没戏了,幸运的是(也可以说不幸的是)大多数编程语言使用的哈希算法都十分简单(这是为了效率考虑),因此可以不费吹灰之力之力构造出攻击数据。下一节将通过分析 Zend 相关内核代码,找出攻击哈希表碰撞攻击 PHP 的方法。

 

Zend 哈希表的内部实现

数据结构

PHP 中使用一个叫 Backet 的结构体表示桶,同一哈希值的所有桶被组织为一个单链表。哈希表使用 HashTable 结构体表示。相关源码在 zend/Zend_hash.h 下:

字段名很清楚的表明其用途,因此不做过多解释。重点明确下面几个字段:Bucket 中的“h”用于存储原始 key;HashTable 中的 nTableMask 是一个掩码,一般被设为 nTableSize – 1,与哈希算法有密切关系,后面讨论哈希算法时会详述;arBuckets 指向一个指针数组,其中每个元素是一个指向 Bucket 链表的头指针。

哈希算法

PHP 哈希表最小容量是 8(2^3),最大容量是 0×80000000(2^31),并向 2 的整数次幂圆整(即长度会自动扩展为 2 的整数次幂,如 13 个元素的哈希表长度为 16;100 个元素的哈希表长度为 128)。nTableMask 被初始化为哈希表长度(圆整后)减 1。具体代码在 zend/Zend_hash.c 的 _zend_hash_init 函数中,这里截取与本文相关的部分并加上少量注释。

值得一提的是 PHP 向 2 的整数次幂取圆整方法非常巧妙,可以背下来在需要的时候使用。

Zend HashTable 的哈希算法异常简单:

PHP 哈希表碰撞攻击原理

 

即简单将数据的原始 key 与 HashTable 的 nTableMask 进行按位与即可。

如果原始 key 为字符串,则首先使用Times33算法将字符串转为整形再与 nTableMask 按位与。

PHP 哈希表碰撞攻击原理

 

下面是 Zend 源码中查找哈希表的代码:

其中 zend_hash_index_find 用于查找整数 key 的情况,zend_hash_find 用于查找字符串 key。逻辑基本一致,只是字符串 key 会通过 zend_inline_hash_func 转为整数 key,zend_inline_hash_func 封装了 times33 算法,具体代码就不贴出了。

攻击

基本攻击

知道了 PHP 内部哈希表的算法,就可以利用其原理构造用于攻击的数据。一种最简单的方法是利用掩码规律制造碰撞。上文提到 Zend HashTable 的长度 nTableSize 会被圆整为 2 的整数次幂,假设我们构造一个 2^16 的哈希表,则 nTableSize 的二进制表示为:1 0000 0000 0000 0000,而 nTableMask = nTableSize – 1 为:0 1111 1111 1111 1111。接下来,可以以 0 为初始值,以 2^16 为步长,制造足够多的数据,可以得到如下推测:

0000 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0001 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0010 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0011 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0100 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

……

概况来说只要保证后 16 位均为 0,则与掩码位于后得到的哈希值全部碰撞在位置 0。

下面是利用这个原理写的一段攻击代码:

这段代码在我的 VPS 上(单 CPU,512M 内存)上用了近 88 秒才完成,并且在此期间 CPU 资源几乎被用尽:

PHP 哈希表碰撞攻击原理

PHP 哈希表碰撞攻击原理

而普通的同样大小的哈希表插入仅用时 0.036 秒:

PHP 哈希表碰撞攻击原理

可以证明第二段代码插入 N 个元素的时间在 O(N)水平,而第一段攻击代码则需 O(N^2)的时间去插入 N 个元素。

 

POST 攻击

当然,一般情况下很难遇到攻击者可以直接修改 PHP 代码的情况,但是攻击者仍可以通过一些方法间接构造哈希表来进行攻击。例如 PHP 会将接收到的 HTTP POST 请求中的数据构造为$_POST,而这是一个 Array,内部就是通过 Zend HashTable 表示,因此攻击者只要构造一个含有大量碰撞 key 的 post 请求,就可以达到攻击的目的。具体做法不再演示。

 

防护

POST 攻击的防护

针对 POST 方式的哈希碰撞攻击,目前 PHP 的防护措施是控制 POST 数据的数量。在>=PHP5.3.9 的版本中增加了一个配置项 max_input_vars,用于标识一次 http 请求最大接收的参数个数,默认为 1000。因此 PHP5.3.x 的用户可以通过升级至 5.3.9 来避免哈希碰撞攻击。5.2.x 的用户可以使用这个 patch:http://www.laruence.com/2011/12/30/2440.html

另外的防护方法是在 Web 服务器层面进行处理,例如限制 http 请求 body 的大小和参数的数量等,这个是现在用的最多的临时处理方案。具体做法与不同 Web 服务器相关,不再详述。

 

其它防护

上面的防护方法只是限制 POST 数据的数量,而不能彻底解决这个问题。例如,如果某个 POST 字段是一个 json 数据类型,会被 PHP json_decode,那么只要构造一个超大的 json 攻击数据照样可以达到攻击目的。理论上,只要 PHP 代码中某处构造 Array 的数据依赖于外部输入,则都可能造成这个问题,因此彻底的解决方案要从 Zend 底层 HashTable 的实现动手。一般来说有两种方式,一是限制每个桶链表的最长长度;二是使用其它数据结构如红黑树取代链表组织碰撞哈希(并不解决哈希碰撞,只是减轻攻击影响,将 N 个数据的操作时间从 O(N^2)降至 O(NlogN),代价是普通情况下接近 O(1)的操作均变为 O(logN))。

目前使用最多的仍然是 POST 数据攻击,因此建议生产环境的 PHP 均进行升级或打补丁。至于从数据结构层面修复这个问题,目前还没有任何方面的消息。

 

参考

[1] Supercolliding a PHP array

[2] PHP5.2.*防止 Hash 冲突拒绝服务攻击的 Patch

[3] 通过构造 Hash 冲突实现各种语言的拒绝服务攻击

[4] PHP 数组的 Hash 冲突实例

[5] PHP 5.4.0 RC4 released


本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:PHP 哈希表碰撞攻击原理
喜欢 (0)
[]
分享 (0)

您必须 登录 才能发表评论!