大师网-带你快速走向大师之路 解决你在学习过程中的疑惑,带你快速进入大师之门。节省时间,提升效率

php哈希冲突攻击解析

一段攻击代码

<?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 '插入 ', $size, ' 个恶意的元素需要 ', $endTime - $startTime, ' 秒', "\n";
 
$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = $size - 1; $key <= $maxKey; ++$key) {
    $array[$key] = 0;
}
$endTime = microtime(true);
echo '插入 ', $size, ' 个普通元素需要 ', $endTime - $startTime, ' 秒', "\n";

插入结果

php5(5.2)

插入 65536 个恶意的元素需要 79.778307914734 秒
插入 65536 个普通元素需要 0.028948068618774 秒

php7

插入 65536 个恶意的元素需要 9.2177460193634 秒
插入 65536 个普通元素需要 0.004227876663208 秒

php 数组的实现

php 中的数组是 php 中非常好用的一个数据结构,有了这个数据结构的加持 php 的开发效率才能如此之高。
但是我们知道世界上并没有完美的事物,php 的数组虽然给我们带来的简单易用的一些特性,但是也会给我们带来一些隐患。
哈希表是我们非常常见的一个数据结构,php 的数组就是通过哈希表来实现的。
php 的哈希表解决冲突采用的是拉链法,冲突的元素通过加入相应hash槽的链表来解决。

php 经历了很多的版本,我们常用熟悉的版本有5.35.67.0 这几个版本。
其中 php5 版本的 hashtable 的实现与 php7 的有所不同。

php5

//hashTable的数据结构
typedef struct _hashtable {
    uint nTableSize;// hashtable 的大小
    uint nTableMask;//这个和 ntableSize 是对应的关系,为 nTableSize 的负数
    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;
//保存数据的单链表结构
typedef struct bucket {
   ulong h;                  /* Used for numeric indexing */
   uint nKeyLength;        //key长度
   void *pData;        //指向bucket中保存的数据的指针
   void *pDataPtr;    //指针数据
   struct bucket *pListNext;    //指向hashtable桶列中下一个元素
   struct bucket *pListLast;    //指向hashtable桶列前一个元素
   struct bucket *pNext;        //指向具有同一个hash index的桶列的后一个元素
   struct bucket *pLast;        //指向具有同一个hash index的桶列的前一个元素
   const char *arKey;        //必须是最后一个成员,key的名称
} Bucket;

php7

struct _zend_array {
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    flags,
                zend_uchar    nApplyCount,
                zend_uchar    nIteratorsCount,
                zend_uchar    consistency)
        } v;
        uint32_t flags;
    } u;
    uint32_t          nTableMask; //散列函数的映射数
    Bucket           *arData;     //指向当前桶的第一个数据
    uint32_t          nNumUsed;   //已用的Bucket的数量(包含的是那些被删除的或者是无效的bucket)
    uint32_t          nNumOfElements;//有效的bucket的数量
    uint32_t          nTableSize;//可以容纳的bucket的数量
    uint32_t          nInternalPointer;
    zend_long         nNextFreeElement;//用来自动确定php数组的索引
    dtor_func_t       pDestructor;//自动清理无用bucket的函数
};

php7 的 Bucket 实现就简单的多


typedef struct _Bucket {
    zval              val;//元素的数据
    zend_ulong        h;                /* hash value (or numeric index)   */
    zend_string      *key;              /* string key or NULL for numerics */
} Bucket;

这个是 php7 hashtable的数据分布
数据分布是这样的 映射表 + bucket(顺序插入)


/*
 * HashTable Data Layout
 * =====================
 *
 *                 +=============================+
 *                 | HT_HASH(ht, ht->nTableMask) |
 *                 | ...                         |
 *                 | HT_HASH(ht, -1)             |
 *                 +-----------------------------+
 * ht->arData ---> | Bucket[0]                   |
 *                 | ...                         |
 *                 | Bucket[ht->nTableSize-1]    |
 *                 +=============================+
 */
 
bucket1.png

内部冲突的解决

那么 php 的内部冲突 php 是怎么解决的那?
首先涉及到的一个常量是 php hashtable 中 nTableMask。
我们先来看php数组是如何初始化的

 ZEND_API void ZEND_FASTCALL _zend_hash_init(HashTable *ht, uint32_t nSize, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
{
    GC_REFCOUNT(ht) = 1;
    GC_TYPE_INFO(ht) = IS_ARRAY;
    ht->u.flags = (persistent ? HASH_FLAG_PERSISTENT : 0) | HASH_FLAG_APPLY_PROTECTION | HASH_FLAG_STATIC_KEYS;
    ht->nTableMask = HT_MIN_MASK; //这里对 nTableMask 进行了定义
    HT_SET_DATA_ADDR(ht, &uninitialized_bucket);
    ht->nNumUsed = 0;
    ht->nNumOfElements = 0;
    ht->nInternalPointer = HT_INVALID_IDX;
    ht->nNextFreeElement = 0;
    ht->pDestructor = pDestructor;
    ht->nTableSize = zend_hash_check_size(nSize);
}

下面是上面关键常量的定义

#define HT_MIN_MASK ((uint32_t) -2) // 11111111111111111111111111111000
#define HT_MIN_SIZE 8 //初始化最大nTableSize

uint32_t 是无符号的int类型,吧 -2 转换成无符号就是将-2原码区反加一

php 添加数据到hashTable的代码
主要关注的变量 nIndex h u2.next

  • nIndex:哈希槽
  • h:当前的数组的key
  • u2.next:冲突链表前一个bucket的位置记录(Bucket是顺序插入的,php7性能提高就是因为做了hashTable的数据结构重构)
 ...
 add_to_hash:
    idx = ht->nNumUsed++;
    ht->nNumOfElements++;
    if (ht->nInternalPointer == HT_INVALID_IDX) {
        ht->nInternalPointer = idx;
    }
    zend_hash_iterators_update(ht, HT_INVALID_IDX, idx);
    p = ht->arData + idx;
    p->key = key;
    if (!ZSTR_IS_INTERNED(key)) {
        zend_string_addref(key);
        ht->u.flags &= ~HASH_FLAG_STATIC_KEYS;
        zend_string_hash_val(key);
    }
    p->h = h = ZSTR_H(key);
    ZVAL_COPY_VALUE(&p->val, pData);
    nIndex = h | ht->nTableMask;  //这里就是计算的方法  nTableMask初始值11111111111111111111111111111000
    Z_NEXT(p->val) = HT_HASH(ht, nIndex); // 这里将上一个bucket的u2.next的值放到下一个Bucket的u2.next
    HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);

    return &p->val;
...

我们知道了hash的计算方式了,就可以分析上面的攻击代码了。
我们取出来几个数据进行调试测试,新建一个 php 文件使用php -f 运行文件

$arr1 = [
    0 => '!',//4294967288
    65536 => '@',//4294967288
    131072 => '#',
    196608 => '$',
    262144 => '%',
];

下面的nIndex的变化

65536.png
196608.png
1311072.png
262144.png

我们可以看到nIndex几次都没有变化,这说明我们的Bucket都是放到同一个hash槽中,我们在通过p *(Bucket*)ht.arData@5
查看bucket数据中u2.next指向。

{

{val = {value = {lval = ....}, u2 = {next = 4294967295, ....}}, h = 0, key = 0x0},

{val = {value = {lval = ....}, u2 = {next = 0, ....}}, h = 65536, key = 0x0},

{val = {value = {lval = ....}, u2 = {next = 1, ....}}, h = 131072, key = 0x0},

{val = {value = {lval = ....}, u2 = {next = 2, ....}}, h = 196608, key = 0x0},

{val = {value = {lval = ....}, u2 = {next = 3, ....}}, h = 262144, key = 0x0}

}

为什么第一个是4294967295 因为这个是第一个引用的hash槽的位置

butcket2.png

为何会有攻击效果

如果所有的元素都进了同一个hash槽,那么我们的Hashtable查询和插入的时间复杂度就会从 O(1) => O(n)
当然 php7 有所改善,如果在php5中的插入方式会慢很多。

hash冲突

有效预防

  1. 在 php5.3 以上的版本中,post 参数的数量存在最大的限制 max_input_vars => 1000

  2. 在web服务器层面进行处理,如通过限制请求 body 大小和参数的数量等,这个也是目前使用最多的解决方案

其实以上的两种解决方案并不能解决问题,因为只是单纯的在参数的数量上进行限制了,但是入股请求的数据中包含 json 数据,但其中的数据就是碰撞的 array。理论上,只要 php 代码某处构造 array 的数据依赖于外部输入,则都可能造成这个问题,因此彻底的解决方案是更改 Zend 底层的 HashTable 实现

  1. 限制每个桶链表的最长长度

  2. 使用其他数据结构如红黑树取代链表组织碰撞哈希(并不解决哈希碰撞,只是减轻攻击影响,将N个数据的操作时间从 O(N^2) 降至 O(NlogN) ,代价是普通情况下接近 O(1) 的操作均变为 O(logN)