PHP内核探索:哈希表碰撞攻击原理

下面通过图文并茂的方式给大家展示PHP内核探索:哈希表碰撞攻击原理。

最近哈希表碰撞攻击(Hashtable collisions as DOS attack)的话题不断被提起，各种语言纷纷中招。本文结合PHP内核源码，聊一聊这种攻击的原理及实现。

 哈希表碰撞攻击的基本原理

哈希表是一种查找效率极高的数据结构，很多语言都在内部实现了哈希表。PHP中的哈希表是一种极为重要的数据结构，不但用于表示Array数据类型，还在Zend虚拟机内部用于存储上下文环境信息(执行上下文的变量及函数均使用哈希表结构存储)。

理想情况下哈希表插入和查找操作的时间复杂度均为O(1)，任何一个数据项可以在一个与哈希表长度无关的时间内计算出一个哈希值(key)，然后在常量时间内定位到一个桶(术语bucket，表示哈希表中的一个位置)。当然这是理想情况下，因为任何哈希表的长度都是有限的，所以一定存在不同的数据项具有相同哈希值的情况，此时不同数据项被定为到同一个桶，称为碰撞(collision)。哈希表的实现需要解决碰撞问题，碰撞解决大体有两种思路，第一种是根据某种原则将被碰撞数据定为到其它桶，例如线性探测——如果数据在插入时发生了碰撞，则顺序查找这个桶后面的桶，将其放入第一个没有被使用的桶；第二种策略是每个桶不是一个只能容纳单个数据项的位置，而是一个可容纳多个数据的数据结构(例如链表或红黑树)，所有碰撞的数据以某种数据结构的形式组织起来。

不论使用了哪种碰撞解决策略，都导致插入和查找操作的时间复杂度不再是O(1)。以查找为例，不能通过key定位到桶就结束，必须还要比较原始key(即未做哈希之前的key)是否相等，如果不相等，则要使用与插入相同的算法继续查找，直到找到匹配的值或确认数据不在哈希表中。

PHP是使用单链表存储碰撞的数据，因此实际上PHP哈希表的平均查找复杂度为O(L)，其中L为桶链表的平均长度；而最坏复杂度为O(N)，此时所有数据全部碰撞，哈希表退化成单链表。下图PHP中正常哈希表和退化哈希表的示意图。

哈希表碰撞攻击就是通过精心构造数据，使得所有数据全部碰撞，人为将哈希表变成一个退化的单链表，此时哈希表各种操作的时间均提升了一个数量级，因此会消耗大量CPU资源，导致系统无法快速响应请求，从而达到拒绝服务攻击(DoS)的目的。

可以看到，进行哈希碰撞攻击的前提是哈希算法特别容易找出碰撞，如果是MD5或者SHA1那基本就没戏了，幸运的是(也可以说不幸的是)大多数编程语言使用的哈希算法都十分简单(这是为了效率考虑)，因此可以不费吹灰之力之力构造出攻击数据。下一节将通过分析Zend相关内核代码，找出攻击哈希表碰撞攻击PHP的方法。
Zend哈希表的内部实现 数据结构
PHP中使用一个叫Backet的结构体表示桶，同一哈希值的所有桶被组织为一个单链表。哈希表使用HashTable结构体表示。相关源码在zend/Zend_hash.h下：

typedef struct bucket {
 ulong h;						/* Used for numeric indexing */
 uint nKeyLength;
 void *pData;
 void *pDataPtr;
 struct bucket *pListNext;
 struct bucket *pListLast;
 struct bucket *pNext;
 struct bucket *pLast;
 char arKey[1]; /* Must be last element */
} Bucket;
typedef struct _hashtable {
 uint nTableSize;
 uint nTableMask;
 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;
#ifZEND_DEBUG
 int inconsistent;
#endif
} HashTable;

字段名很清楚的表明其用途，因此不做过多解释。重点明确下面几个字段：Bucket中的“h”用于存储原始key；HashTable中的nTableMask是一个掩码，一般被设为nTableSize - 1，与哈希算法有密切关系，后面讨论哈希算法时会详述；arBuckets指向一个指针数组，其中每个元素是一个指向Bucket链表的头指针。
 哈希算法
PHP哈希表最小容量是8(2^3)，最大容量是0×80000000(2^31)，并向2的整数次幂圆整(即长度会自动扩展为2的整数次幂，如13个元素的哈希表长度为16；100个元素的哈希表长度为128)。nTableMask被初始化为哈希表长度(圆整后)减1。具体代码在zend/Zend_hash.c的_zend_hash_init函数中，这里截取与本文相关的部分并加上少量注释。

ZEND_API int_zend_hash_init(HashTable *ht, uintnSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
{
 uinti = 3;
 Bucket **tmp;
 SET_INCONSISTENT(HT_OK);
 //长度向2的整数次幂圆整
 if(nSize >= 0x80000000) {
 /* prevent overflow */
 ht->nTableSize = 0x80000000;
 } else{
 while((1U << i) < nSize) {
  i++;
 }
 ht->nTableSize = 1<< i;
 }
 ht->nTableMask = ht->nTableSize - 1;
 /*此处省略若干代码…*/
 returnSUCCESS;
}

值得一提的是PHP向2的整数次幂取圆整方法非常巧妙，可以背下来在需要的时候使用。

Zend HashTable的哈希算法异常简单：