哈希表碰撞攻击就是通过精心构造数据，使得所有数据全部碰撞，人为将哈希表变成一个
退化的单链表，此时哈希表各种操作的时间均提升了一个数量级，因此会消耗大量

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;#if ZEND_DEBUG    int 
inconsistent;#endif} HashTable;

字段名很清楚的表明其用途，因此不做过多解释。重点明确下面几个字段：

Bucket 中的“h”

用于存储原始

key；HashTable 中的 nTableMask 是一个掩码，一般被设为 nTableSize - 1，与

哈希算法有密切关系，后面讨论哈希算法时会详述；

arBuckets 指向一个指针数组，其中每

个元素是一个指向

Bucket 链表的头指针。

哈希算法

PHP 哈希表最小容量是 8（2^3），最大容量是 0x80000000（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, uint nSize, hash_func_t pHashFunction, 
dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC){    uint i = 3;    Bucket 
**tmp;

    SET_INCONSISTENT(HT_OK);

    //长度向 2 的整数次幂圆整    if (nSize >= 0x80000000) {        /* prevent overflow */        ht-