PHP哈希表碰撞攻击原理(三)

文章正文
发布时间:2024-07-24 23:36

PHP哈希表碰撞攻击原理(三)

知道了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资源几乎被用尽:

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

可以证明第二段代码插入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:。

另外的防护方法是在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均进行升级或打补丁。至于从数据结构层面修复这个问题,目前还没有任何方面的消息。

 

首页
评论
分享
Top