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.3、5.6、7.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冲突
有效预防
-
在 php5.3 以上的版本中，post 参数的数量存在最大的限制 max_input_vars => 1000
-
在web服务器层面进行处理，如通过限制请求 body 大小和参数的数量等，这个也是目前使用最多的解决方案
其实以上的两种解决方案并不能解决问题，因为只是单纯的在参数的数量上进行限制了，但是入股请求的数据中包含 json 数据，但其中的数据就是碰撞的 array。理论上，只要 php 代码某处构造 array 的数据依赖于外部输入，则都可能造成这个问题，因此彻底的解决方案是更改 Zend 底层的 HashTable 实现
-
限制每个桶链表的最长长度
-
使用其他数据结构如红黑树取代链表组织碰撞哈希（并不解决哈希碰撞，只是减轻攻击影响，将N个数据的操作时间从 O(N^2) 降至 O(NlogN) ，代价是普通情况下接近 O(1) 的操作均变为 O(logN)
