php内核

php哈希冲突攻击解析

哈希冲突攻击

Posted by Lerko on August 5, 2018

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]    |
 *                 +=============================+
 */

数据分布

内部冲突的解决

那么 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的变化

数据分布1

数据分布2

数据分布3

数据分布5

我们可以看到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槽的位置

冲突结构

为何会有攻击效果

如果所有的元素都进了同一个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)

CATALOG
    FEATURED TAGS
    docker database server leetcode TCP mysql golang K8S 分布式 go Istio k8s istio 数据结构
    FRIENDS