理解PHP的Hash冲突漏洞

October 19, 2014

Hash表对PHP的重要性是每个phper都非常清楚地。但是PHP却有一个与Hash表相关的致命漏洞,我们完全可以通过PHP的Hash冲突漏洞进行DDoS攻击,可以轻易的搞挂一台服务器。那么是什么导致PHP的Hash冲突呢?如何构造Hash冲突?

1. PHP的Hashtab实现方式

PHP中的哈希表实现在源代码的Zend/zend_hash.c中,Zend/zend_hash.h中描述了Hashtab的结构体,从中我们可以大概了解Hashtab的实现机制。

typedef struct _hashtable { 
    uint nTableSize;        // hash Bucket的大小,最小为8,以2x增长。
    uint nTableMask;        // nTableSize-1 , 索引取值的优化
    uint nNumOfElements;    // hash Bucket中当前存在的元素个数,count()函数会直接返回此值 
    ulong nNextFreeElement; // 下一个数字索引的位置
    Bucket *pInternalPointer;   // 当前遍历的指针(foreach比for快的原因之一)
    Bucket *pListHead;          // 存储数组头元素指针
    Bucket *pListTail;          // 存储数组尾元素指针
    Bucket **arBuckets;         // 存储hash数组
    dtor_func_t pDestructor;    // 在删除元素时执行的回调函数,用于资源的释放
    zend_bool persistent;       //指出了Bucket内存分配的方式。如果persisient为TRUE,则使用操作系统本身的内存分配函数为Bucket分配内存,否则使用PHP的内存分配函数。
    unsigned char nApplyCount; // 标记当前hash Bucket被递归访问的次数(防止多次递归)
    zend_bool bApplyProtection;// 标记当前hash桶允许不允许多次访问,不允许时,最多只能递归3次
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

从结构体_hashtable中我们可以看出,PHP内核是使用常用的拉链法实现Hash表的,其中Bucket **arBuckets存储了实际的数据。

php内核hash表数据结构

其实PHP的Hash冲突漏洞就是利用在极端情况下,拉链法的Hashtab会退化为单链表的漏洞。由于Hash函数是公开的,因此经过精心的构造,是可以构造出导致Hash退化为链表的数据的。

php hash表退化为单链表

2. 本地实现PHP的Hash漏洞攻击

在我们使用数组时,PHP内核都是通过把数组内容插入到一个Hash表实现的,但对于关联数组(字符串下标)和索引数组(整数下标)的处理方法是不同的。关联数组使用如下函数将数据添加的Hash表:

ZEND_API int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC){
...
 h = zend_inline_hash_func(arKey, nKeyLength);//根据字符串计算Hash值
 nIndex = h & ht->nTableMask;
...
}

从上述代码中我们可以看出,关联数组需要使用Hash函数根据字符串计算Hash值。而索引数组却直接使用整数下标作为Hash值:

ZEND_API int _zend_hash_index_update_or_next_insert(HashTable *ht, ulong h, void *pData, uint nDataSize, void **pDest, int flag
ZEND_FILE_LINE_DC){
...
nIndex = h & ht->nTableMask; //直接使用下标作为hash值
...
}

由于实现较为简单,大部分攻击是通过构造索引数组来实现的,只要使 公式h & ht->nTableMask得到同样的值即可,其中ht->nTableMaskzend_hash_init函数中赋值:ht->nTableMask = ht->nTableSize - 1

有了以上基础知识,我们就可以构利用Hash冲突漏洞了。先直接上代码:

<?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 ,PHP_EOL;

这段代码创建了一个包含216 个元素的索引数组,下标依次为:

0,2^16,2*2^16,......,n*2^16,......,(2^16-1)*2^16

这时ht->nTableMask=2^16-1,转换为二进制就是1111 1111 1111 1111。而以上数组中的任意一个下标h和ht->nTableMask进行与运算都得0,nIndex = h & ht->nTableMask = 0。即所有的下标都得到同样的Hash值,这时Hash表就退化为链表了。事实上,这段代码在我的电脑里运行耗时40多秒。多恐怖啊。

3.常见的Hash冲突攻击形式

POST攻击: PHP会自动把HTTP包中POST的数据解析成数组$_POST,如果我们构造一个无限大的哈希冲突的值,则可以拖垮服务器。

PHP5.3.9以后的版本可以通过php.ini设置GET/POST/COOKIE 的最大输入变量数。默认为1000。但这种方法是无法完全避免攻击的,我们也可以在POST的变量值上做手脚,即反序列化攻击。

反序列化攻击: 如果POST的数据有字段为数组serialize后的值,或数组json_encode后的值,在unserialize或json_decode后,会有可能造成哈希碰撞攻击。 到目前位置PHP官方还没有彻底解决反序列化攻击的问题,请避免在公网上以数组的序列化形式传递数据

全面理解React,实现自己的React

通过实现一个简单的React, 来理解React的原理 Continue reading

同构渲染的常见风险

Published on October 01, 2017

React16升级避坑指南

Published on September 10, 2017