PHP Hash Collision攻击原理

哈希表是一种查找效率极高的数据结构，php中的哈希表用于表示array数据类型，在zend虚拟机内部也用于存储上下文环境信息（执行上下文的变量及函数均使用哈希表结构存储）。

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

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

php是使用单链表存储碰撞的数据，因此实际上php哈希表的平均查找复杂度为o(l)，其中l为桶链表的平均长度；而最坏复杂度为o(n)，此时所有数据全部碰撞，哈希表退化成单链表。哈希表结构如下图

hash function也叫哈希散列函数，通过散列函数我们能将各种类型的key转换为有限空间内的一个内存地址。常见的散列函数有md5，sha*。不过hashtable中基本不会用md5，sha*算法,因为这两类算法太耗时，基本所有的编程语言都会选择times*类型算法，比如times31,times33,times37。java使用的hash算法为times31，php使用的hash算法为times33……

php hashtable的哈希算法如下：

hash(key)=key & ntablemask

即简单将数据的原始key与hashtable的ntablemask进行按位与即可。如果原始key为字符串，则首先使用times33算法将字符串转为整形再与ntablemask按位与。

hash(strkey)=time33(strkey) & ntablemask

下面是zend源码中查找哈希表的代码：

知道了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。

如上我们已经推算出碰撞数据的实现方式，接下来我通过php生成碰撞数据。如果要生成大量的碰撞数据，这里最好不要使用php来生成，因为操作不当就会变成攻击自己的脚本。

最后我们生成了如下数据(截取了前面几条)：

通过程序我们生成了65536条碰撞数据，然后在laravel中做个简单的测试，测试代码如下：

测试结果，一个cpu被打到100%，持续了20多秒。结束该php-fpm进程后恢复。

至此写了三篇关于hashtable的文章，前两篇文章开头都有链接，能帮助大家对hahstable有更深的理解，之后不会再更新hashtable相关的文章了。