空想情形下哈希表插入和查找操作的韶光繁芜度均为O(1)，任何一个数据项可以在一个与哈希表长度无关的韶光内打算出一个哈希值（key），然后在常量韶光内定位到一个桶（术语bucket，表示哈希表中的一个位置）。当然这是空想情形下，由于任何哈希表的长度都是有限的，以是一定存在不同的数据项具有相同哈希值的情形，此时不同数据项被定为到同一个桶，称为碰撞（collision）。哈希表的实现须要办理碰撞问题，碰撞办理大体有两种思路，第一种是根据某种原则将被碰撞数据定为到其它桶，例如线性探测——如果数据在插入时发生了碰撞，则顺序查找这个桶后面的桶，将其放入第一个没有被利用的桶；第二种策略是每个桶不是一个只能容纳单个数据项的位置，而是一个可容纳多个数据的数据构造（例如链表或红黑树），所有碰撞的数据以某种数据构造的形式组织起来。
不论利用了哪种碰撞办理议方案略，都导致插入和查找操作的韶光繁芜度不再是O(1)。以查找为例，不能通过key定位到桶就结束，必须还要比较原始key（即未做哈希之前的key）是否相等，如果不相等，则要利用与插入相同的算法连续查找，直到找到匹配的值或确认数据不在哈希表中。
PHP是利用单链表存储碰撞的数据，因此实际上PHP哈希表的均匀查找繁芜度为O(L)，个中L为桶链表的均匀长度；而最坏繁芜度为O(N)，此时所有数据全部碰撞，哈希表退化成单链表。下图PHP中正常哈希表和退化哈希表的示意图。
哈希表碰撞攻击便是通过精心布局数据，使得所有数据全部碰撞，人为将哈希表变成一个退化的单链表，此时哈希表各种操作的韶光均提升了一个数量级，因此会花费大量CPU资源，导致系统无法快速相应要求，从而达到谢绝做事攻击（DoS）的目的。
可以看到，进行哈希碰撞攻击的条件是哈希算法特殊随意马虎找出碰撞，如果是MD5或者SHA1那基本就没戏了，幸运的是（也可以说不幸的是）大多数编程措辞利用的哈希算法都十分大略（这是为了效率考虑），因此可以不费吹灰之力之力布局出攻击数据。下一节将通过剖析Zend干系内核代码，找出攻击哈希表碰撞攻击PHP的方法。
Zend哈希表的内部实现数据构造
PHP中利用一个叫Backet的构造体表示桶，同一哈希值的所有桶被组织为一个单链表。哈希表利用HashTable构造体表示。干系源码在zend/Zend_hash.h下：
typedef struct bucket {
ulong h; / Used for numeric indexing /
uint nKeyLength;
void pData;
void pDataPtr;
struct bucket pListNext;
struct bucket pListLast;
struct bucket pNext;
struct bucket pLast;
char arKey[1]; / Must be last element /
} Bucket;
typedef struct _hashtable {
uint nTableSize;
uint nTableMask;
uint nNumOfElements;
ulong nNextFreeElement;
Bucket pInternalPointer; / Used for element traversal /
Bucket pListHead;
Bucket pListTail;
Bucket arBuckets;
dtor_func_t pDestructor;
zend_bool persistent;
unsigned char nApplyCount;
zend_bool bApplyProtection;
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;
字段名很清楚的表明其用场，因此不做过多阐明。重点明确下面几个字段：Bucket中的“h”用于存储原始key；HashTable中的nTableMask是一个掩码，一样平常被设为nTableSize - 1，与哈希算法有密切关系，后面谈论哈希算法时会详述；arBuckets指向一个指针数组，个中每个元素是一个指向Bucket链表的头指针。
哈希算法
PHP哈希表最小容量是8（2^3），最大容量是0x80000000（2^31），并向2的整数次幂圆整（即长度会自动扩展为2的整数次幂，如13个元素的哈希表长度为16；100个元素的哈希表长度为128）。nTableMask被初始化为哈希表长度（圆整后）减1。详细代码在zend/Zend_hash.c的_zend_hash_init函数中，这里截取与本文干系的部分并加上少量注释。
ZEND_API int _zend_hash_init(HashTable ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
{
uint i = 3;
Bucket tmp;
SET_INCONSISTENT(HT_OK);
//长度向2的整数次幂圆整
if (nSize >= 0x80000000) {
/ prevent overflow /
ht->nTableSize = 0x80000000;
} else {
while ((1U << i) < nSize) {
i++;
}
ht->nTableSize = 1 << i;
}
ht->nTableMask = ht->nTableSize - 1;
/此处省略多少代码…/
return SUCCESS;
}
值得一提的是PHP向2的整数次幂取圆整方法非常奥妙，可以背下来在须要的时候利用。
Zend HashTable的哈希算法非常大略：
hash(key)=key & nTableMask
即大略将数据的原始key与HashTable的nTableMask进行按位与即可。
如果原始key为字符串，则首先利用Times33算法将字符串转为整形再与nTableMask按位与。
hash(strkey)=time33(strkey) & nTableMask
下面是Zend源码中查找哈希表的代码：
ZEND_API int zend_hash_index_find(const HashTable ht, ulong h, void pData)
{
uint nIndex;
Bucket p;
IS_CONSISTENT(ht);
nIndex = h & ht->nTableMask;
p = ht->arBuckets[nIndex];
while (p != NULL) {
if ((p->h == h) && (p->nKeyLength == 0)) {
pData = p->pData;
return SUCCESS;
}
p = p->pNext;
}
return FAILURE;
}
ZEND_API int zend_hash_find(const HashTable ht, const char arKey, uint nKeyLength, void pData)
{
ulong h;
uint nIndex;
Bucket p;
IS_CONSISTENT(ht);
h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask;
p = ht->arBuckets[nIndex];
while (p != NULL) {
if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
if (!memcmp(p->arKey, arKey, nKeyLength)) {
pData = p->pData;
return SUCCESS;
}
}
p = p->pNext;
}
return FAILURE;
}
个中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。
下面是利用这个事理写的一段攻击代码：
<?php
$size = pow(2, 16);
$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = ($size - 1) $size; $key <= $maxKey; $key += $size) {
$array[$key] = 0;
}
$endTime = microtime(true);
echo $endTime - $startTime, ' seconds', \公众\n\"大众;
这段代码在我的VPS上（单CPU，512M内存）上用了近88秒才完成，并且在此期间CPU资源险些被用尽：
而普通的同样大小的哈希表插入仅用时0.036秒：
<?php
$size = pow(2, 16);
$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = ($size - 1) $size; $key <= $size; $key += 1) {
$array[$key] = 0;
}
$endTime = microtime(true);
echo $endTime - $startTime, ' seconds', \"大众\n\"大众;
可以证明第二段代码插入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
AddThis Sharing ButtonsShare to WeChat
