by flyh4t@hotmail.com
一、关于Hashtable collisions
    数据的基本组织可以分为三种形式:
    结构体(或对象)
    数组
    链表
其他任何的数据组织形式都可以看作是这三种数据组织形式的组合变体。就存取数据的速度而言,数组要远远优于链表，因为数组可以在O(1)的时间复杂内完成指定位置元素的读写操作。所以在理想状态，如果一个数组足够长，且存在一个函数可以将每一个key映射到唯一的一个数组下标，那么我们就可以很完美的解决问题。但往往资源都是有限的，我们没有那么大的空间，也不能设计一个无比负责的映射算法保证每一个key对应到一个唯一的数组下标。
hash table便是为解决这类问题而存在的,hash操作其本质上就是将一个数据映射成另一个数据，通常情况下原数据的长度比hash后的数据容量大。这种映射的关系我们叫做哈希函数。一般情况下 哈希函数的输入可能的总数要远远多于哈希值所能表示的总数，所以就有可能两个不同的输入对应同一个哈希值，比如著名的md5碰撞。
解决冲突的方式主要分两类：
    开放定址法(Open addressing)：这种方法就是在计算一个key的哈希的时候，发现目标地址已经有值了，即发生冲突了，这个时候通过相应的函数在此地址后面的地址去找，直到没有冲突为止。这个方法常用的有线性探测，二次探测，再哈希。
    链接法(Separate chaining)：链接法是通过数组和链表组合而成的。当发生冲突的时候只要将其加到对应的链表中即可。

    PHP使用链接法解决冲突，如果攻击者能够人为的制造大量hash冲突，将PHP底层保存POST数据的Hash表退化成链表，造成性能的急剧下降。

二、PHP的Hash函数
PHP的Hash函数采用的是目前最为普遍的DJBX33A (Daniel J. Bernstein, Times 33 with Addition)，代码可以在这里查看：http://lxr.php.net/xref/PHP_5_2/Zend/zend_hash.h#zend_inline_hash_func
-----------------code-------------------------
static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength)
    255 {
    256     register ulong hash = 5381;
    257
    258     /* variant with the hash unrolled eight times */
    259     for (; nKeyLength >= 8; nKeyLength -= 8) {
    260         hash = ((hash << 5) + hash) + *arKey++;
    261         hash = ((hash << 5) + hash) + *arKey++;
    262         hash = ((hash << 5) + hash) + *arKey++;
    263         hash = ((hash << 5) + hash) + *arKey++;
    264         hash = ((hash << 5) + hash) + *arKey++;
    265         hash = ((hash << 5) + hash) + *arKey++;
    266         hash = ((hash << 5) + hash) + *arKey++;
    267         hash = ((hash << 5) + hash) + *arKey++;
    268     }
    269     switch (nKeyLength) {
    270         case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
    271         case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
    272         case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
    273         case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
    274         case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
    275         case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
    276         case 1: hash = ((hash << 5) + hash) + *arKey++; break;
    277         case 0: break;
    278 EMPTY_SWITCH_DEFAULT_CASE()
    279     }
    280     return hash;
    281 }
-----------------------------------------------------
核心算法是

hash = ((hash << 5) + hash) + *arKey++;

hash << 5是一个简单的移位操作，可以换算成hash *32，该算法可以理解为
hash= hash* 33 + *arKey++
同时如果提交的key超过7位，需要逐位进行运算。

三、构造冲突的key
    为了方便计算，我们预期构造的两个key均设置为8位。从zend_inline_hash_func函数来分析，进行unrolled操作的时候，如果两个key的前面6位相同，是不影响结果的，只需要考虑碰撞后面两位字母。我们预期构造的两个key如下：
Key1： xa[1]a[2]
Key2： xb[1]b[2]
其中x是一个随机的6位的字符串。
根据算法hash= hash* 33 + *arKey++，如果需要计算出来的hash相同，我们需要满足如下的条件：
(5381*33+ Ascii(a[1]))*33+ Ascii(a[2])=(5381*33+ Ascii(b[1])*33+ Ascii(b[2])
展开运算，得到如下结果
Ascii(a[1])*33+ Ascii(a[2])= Ascii(b[1])*33+ Ascii(b[2])
剩下的工作就很简单了，查下Ascii表可以找出来很多组合，一组简单的结果如下：
a[1]=2 b[1]=1
a[2]=2 b[2]=S
通过以下的demo代码可以进行验证
-----------------code-------------------------
# include <stdio.h>
# include <stdlib.h>
# include <string.h>

unsigned long  zend_inline_hash_func(char *arKey, int nKeyLength)
{
    unsigned long hash = 5381;
   
    for (; nKeyLength >= 8; nKeyLength -= 8) {
    hash = ((hash << 5) + hash) + *arKey++;
    hash = ((hash << 5) + hash) + *arKey++;
    hash = ((hash << 5) + hash) + *arKey++;
    hash = ((hash << 5) + hash) + *arKey++;
    hash = ((hash << 5) + hash) + *arKey++;
    hash = ((hash << 5) + hash) + *arKey++;
    hash = ((hash << 5) + hash) + *arKey++;
    hash = ((hash << 5) + hash) + *arKey++;
    }
    switch (nKeyLength) {
        case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
         case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
         case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
         case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
         case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
         case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
         case 1: hash = ((hash << 5) + hash) + *arKey++; break;
         case 0: break; 
        }
        return hash;
     }
int main()
{ 
    unsigned long hasha ;
    unsigned long hashb ;
    char *a = "abcdef22";
    char *b = "abcdef1S";
    printf ( "PHP Hashtable collisions Demo\r\nAuthor: Flyh4t\r\n\r\n " );
    hasha  =  zend_inline_hash_func(a,   strlen (a) + 1 );
    printf ("[+]String: %s\r\n PHP5 HASHA: %ld\r\n " ,  a , hasha);
    hashb  =  zend_inline_hash_func(b,   strlen (b) + 1 );
    printf ("[+]String: %s\r\n PHP5 HASHB: %ld\r\n " ,  b , hashb);
    return   0 ;
}
-----------------------------------------------------
结算结果如下：
-----------------------------------------------------
PHP Hashtable collisions Demo
Author: Flyh4t

[+]String: abcdef22
PHP5 HASHA: 1004317790
[+]String: abcdef1S
PHP5 HASHB: 1004317790
-----------------------------------------------------
达到了预期的效果。
四、补丁
官方已经出补丁了，采用了变通的方式“修复”的
-----------------code-------------------------
if (zend_hash_num_elements(symtable1) >= PG(max_input_vars)) {
php_error_docref(NULL TSRMLS_CC, E_ERROR, "Input variables exceeded %ld. To increase the limit change max_input_vars in php.ini.", PG(max_input_vars)); }
-----------------------------------------------------
max_input_vars缺省为1000

五、参考

[1] http://www.2cto.com/kf/201202/118843.html
[2] www.2cto.com/Article/201112/115590.html
[3] http://lxr.php.net/xref/PHP_5_2/Zend/ze … _hash_func
[4]群里兄弟们的讨论