ZEND_API int zend_hash_index_find(constHashTable *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; returnSUCCESS; } p = p->pNext; } returnFAILURE; } ZEND_API int zend_hash_find(constHashTable *ht, constchar *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; returnSUCCESS; } } p = p->pNext; } returnFAILURE; }
其中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";
这段代码在我的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个元素的时间在O(N)水平，而第一段攻击代码则需O(N^2)的时间去插入N个元素。
POST攻击
当然，一般情况下很难遇到攻击者可以直接修改PHP代码的情况，但是攻击者仍可以通过一些方法间接构造哈希表来进行攻击。例如PHP会将接收到的HTTP POST请求中的数据构造为$_POST，而这是一个Array，内部就是通过Zend HashTable表示，因此攻击者只要构造一个含有大量碰撞key的post请求，就可以达到攻击的目的。具体做法不再演示。
防护 POST攻击的防护