PHP的hash漏洞解决方案

qqwe

工作原理：

PHP的数据类型是人们所喜爱的，因为它用起来方便。然而为了实现这种方便，必然要用到哈希表。
我们先来看一下PHP是怎样储存变量的：

typedef        union        _zvalue_value        {
  long        lval;          /*        long        value        */
             double        dval;                        /*        double        value        */
  struct        {
    char        *val;
    int        len;
  }        str;
  HashTable        *ht;        /*        hash        table        value        */
  zend_object_value        obj;
}        zvalue_value;



以上代码在PHP 5.3.6中位于Zend/zend.h的305行。
在这个联合体中，有long保存整型、double保存浮点型、和struct来保存字符串型的字符串与字符串长度。
在其后的
struct _zval_struct {
        zvalue_value value;
        zend_uint refcount__gc;
        zend_uchar type;
        zend_uchar is_ref__gc;
};





中，type表示这个变量在PHP中的类型(详见附录1)。然而其中的HashTable *ht就是键名所保存的地方。我们知道链表的操作时间复杂度为O(n)，而相比之下，设计得好的哈希表通常情况下只有O(1)。
PHP使用的算法是DJBX33A(http://blog.csdn.net/zuiaituantuan/article/details/6057586)，然而如果键名为整形，那么情况就不一样了。PHP为整型键名做的是 hash & tableMask(&为按位与操作)的操作。

h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask;
p = ht->arBuckets[nIndex];




如果得到的p!==NULL，那么恭喜你，发生碰撞了。这个时候，PHP就会将新元素链接到原有元素链表头部。而查询的时候也是按照相同的策略，将链表中的所有的键名和要查找的键名进行一一比对，但是一般在正常使用的情况下，不会有多大问题。

那么知道了这种特性以后，要发起***，就变得简单了，只要对PHP页面发送POST请求(不论script中是否对POST进行处理)，别有用心的构造key，那么PHP在引擎层面处理POST数据的时候，已经足以崩溃。
例如：64,128,192,256这样的int型key的hash值是0，那么就会发生碰撞，当key为64进行存储的时候，链表操作是0次，128为1次，192为2次，以此类推则有：time(n) = n-1；那么n个这样的key的链表操作数据就是0+1+2+3+...+(n-1) = (n-1)*(n-2)/2。

我们看一段代码：