最近哈希表碰撞攻擊(Hashtable collisions as DOS attack)的話題不斷被提起，各種語言紛紛中招。本文結(jié)合PHP內(nèi)核源碼，聊一聊這種攻擊的原理及實(shí)現(xiàn)。

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

哈希表是一種查找效率極高的數(shù)據(jù)結(jié)構(gòu)，很多語言都在內(nèi)部實(shí)現(xiàn)了哈希表。PHP中的哈希表是一種極為重要的數(shù)據(jù)結(jié)構(gòu)，不但用于表示Array數(shù)據(jù)類型，還在Zend虛擬機(jī)內(nèi)部用于存儲(chǔ)上下文環(huán)境信息(執(zhí)行上下文的變量及函數(shù)均使用哈希表結(jié)構(gòu)存儲(chǔ))。

理想情況下哈希表插入和查找操作的時(shí)間復(fù)雜度均為O(1)，任何一個(gè)數(shù)據(jù)項(xiàng)可以在一個(gè)與哈希表長度無關(guān)的時(shí)間內(nèi)計(jì)算出一個(gè)哈希值(key)，然后在常量時(shí)間內(nèi)定位到一個(gè)桶(術(shù)語bucket，表示哈希表中的一個(gè)位置)。當(dāng)然這是理想情況下，因?yàn)槿魏喂１淼拈L度都是有限的，所以一定存在不同的數(shù)據(jù)項(xiàng)具有相同哈希值的情況，此時(shí)不同數(shù)據(jù)項(xiàng)被定為到同一個(gè)桶，稱為碰撞(collision)。哈希表的實(shí)現(xiàn)需要解決碰撞問題，碰撞解決大體有兩種思路，第一種是根據(jù)某種原則將被碰撞數(shù)據(jù)定為到其它桶，例如線性探測——如果數(shù)據(jù)在插入時(shí)發(fā)生了碰撞，則順序查找這個(gè)桶后面的桶，將其放入第一個(gè)沒有被使用的桶;第二種策略是每個(gè)桶不是一個(gè)只能容納單個(gè)數(shù)據(jù)項(xiàng)的位置，而是一個(gè)可容納多個(gè)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)(例如鏈表或紅黑樹)，所有碰撞的數(shù)據(jù)以某種數(shù)據(jù)結(jié)構(gòu)的形式組織起來。

不論使用了哪種碰撞解決策略，都導(dǎo)致插入和查找操作的時(shí)間復(fù)雜度不再是O(1)。以查找為例，不能通過key定位到桶就結(jié)束，必須還要比較原始key(即未做哈希之前的key)是否相等，如果不相等，則要使用與插入相同的算法繼續(xù)查找，直到找到匹配的值或確認(rèn)數(shù)據(jù)不在哈希表中。

PHP是使用單鏈表存儲(chǔ)碰撞的數(shù)據(jù)，因此實(shí)際上PHP哈希表的平均查找復(fù)雜度為O(L)，其中L為桶鏈表的平均長度;而最壞復(fù)雜度為O(N)，此時(shí)所有數(shù)據(jù)全部碰撞，哈希表退化成單鏈表。下圖PHP中正常哈希表和退化哈希表的示意圖。

哈希表碰撞攻擊就是通過精心構(gòu)造數(shù)據(jù)，使得所有數(shù)據(jù)全部碰撞，人為將哈希表變成一個(gè)退化的單鏈表，此時(shí)哈希表各種操作的時(shí)間均提升了一個(gè)數(shù)量級(jí)，因此會(huì)消耗大量CPU資源，導(dǎo)致系統(tǒng)無法快速響應(yīng)請(qǐng)求，從而達(dá)到拒絕服務(wù)攻擊(DoS)的目的。

可以看到，進(jìn)行哈希碰撞攻擊的前提是哈希算法特別容易找出碰撞，如果是MD5或者SHA1那基本就沒戲了，幸運(yùn)的是(也可以說不幸的是)大多數(shù)編程語言使用的哈希算法都十分簡單(這是為了效率考慮)，因此可以不費(fèi)吹灰之力之力構(gòu)造出攻擊數(shù)據(jù)。下一節(jié)將通過分析Zend相關(guān)內(nèi)核代碼，找出攻擊哈希表碰撞攻擊PHP的方法。

Zend哈希表的內(nèi)部實(shí)現(xiàn)

數(shù)據(jù)結(jié)構(gòu)

PHP中使用一個(gè)叫Backet的結(jié)構(gòu)體表示桶，同一哈希值的所有桶被組織為一個(gè)單鏈表。哈希表使用HashTable結(jié)構(gòu)體表示。相關(guān)源碼在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;  

字段名很清楚的表明其用途，因此不做過多解釋。重點(diǎn)明確下面幾個(gè)字段：Bucket中的“h”用于存儲(chǔ)原始key;HashTable中的nTableMask是一個(gè)掩碼，一般被設(shè)為nTableSize – 1，與哈希算法有密切關(guān)系，后面討論哈希算法時(shí)會(huì)詳述;arBuckets指向一個(gè)指針數(shù)組，其中每個(gè)元素是一個(gè)指向Bucket鏈表的頭指針。

哈希算法

PHP哈希表最小容量是8(2^3)，最大容量是0×80000000(2^31)，并向2的整數(shù)次冪圓整(即長度會(huì)自動(dòng)擴(kuò)展為2的整數(shù)次冪，如13個(gè)元素的哈希表長度為16;100個(gè)元素的哈希表長度為128)。nTableMask被初始化為哈希表長度(圓整后)減1。具體代碼在zend/Zend_hash.c的_zend_hash_init函數(shù)中，這里截取與本文相關(guān)的部分并加上少量注釋。

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的整數(shù)次冪圓整 
   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的整數(shù)次冪取圓整方法非常巧妙，可以背下來在需要的時(shí)候使用。

Zend HashTable的哈希算法異常簡單： 

即簡單將數(shù)據(jù)的原始key與HashTable的nTableMask進(jìn)行按位與即可。

如果原始key為字符串，則首先使用Times33算法將字符串轉(zhuǎn)為整形再與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用于查找整數(shù)key的情況，zend_hash_find用于查找字符串key。邏輯基本一致，只是字符串key會(huì)通過zend_inline_hash_func轉(zhuǎn)為整數(shù)key，zend_inline_hash_func封裝了times33算法，具體代碼就不貼出了。

攻擊

基本攻擊

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

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。

下面是利用這個(gè)原理寫的一段攻擊代碼：

<?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內(nèi)存)上用了近88秒才完成，并且在此期間CPU資源幾乎被用盡：

而普通的同樣大小的哈希表插入僅用時(shí)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個(gè)元素的時(shí)間在O(N)水平，而第一段攻擊代碼則需O(N^2)的時(shí)間去插入N個(gè)元素。

POST攻擊

當(dāng)然，一般情況下很難遇到攻擊者可以直接修改PHP代碼的情況，但是攻擊者仍可以通過一些方法間接構(gòu)造哈希表來進(jìn)行攻擊。例如PHP會(huì)將接收到的HTTP POST請(qǐng)求中的數(shù)據(jù)構(gòu)造為$_POST，而這是一個(gè)Array，內(nèi)部就是通過Zend HashTable表示，因此攻擊者只要構(gòu)造一個(gè)含有大量碰撞key的post請(qǐng)求，就可以達(dá)到攻擊的目的。具體做法不再演示。

防護(hù)

POST攻擊的防護(hù)

針對(duì)POST方式的哈希碰撞攻擊，目前PHP的防護(hù)措施是控制POST數(shù)據(jù)的數(shù)量。在>=PHP5.3.9的版本中增加了一個(gè)配置項(xiàng)max_input_vars，用于標(biāo)識(shí)一次http請(qǐng)求最大接收的參數(shù)個(gè)數(shù)，默認(rèn)為1000。因此PHP5.3.x的用戶可以通過升級(jí)至5.3.9來避免哈希碰撞攻擊。5.2.x的用戶可以使用這個(gè)patch：http://www.laruence.com/2011/12/30/2440.html。

另外的防護(hù)方法是在Web服務(wù)器層面進(jìn)行處理，例如限制http請(qǐng)求body的大小和參數(shù)的數(shù)量等，這個(gè)是現(xiàn)在用的最多的臨時(shí)處理方案。具體做法與不同Web服務(wù)器相關(guān)，不再詳述。

其它防護(hù)

上面的防護(hù)方法只是限制POST數(shù)據(jù)的數(shù)量，而不能徹底解決這個(gè)問題。例如，如果某個(gè)POST字段是一個(gè)json數(shù)據(jù)類型，會(huì)被PHPjson_decode，那么只要構(gòu)造一個(gè)超大的json攻擊數(shù)據(jù)照樣可以達(dá)到攻擊目的。理論上，只要PHP代碼中某處構(gòu)造Array的數(shù)據(jù)依賴于外部輸入，則都可能造成這個(gè)問題，因此徹底的解決方案要從Zend底層HashTable的實(shí)現(xiàn)動(dòng)手。一般來說有兩種方式，一是限制每個(gè)桶鏈表的最長長度;二是使用其它數(shù)據(jù)結(jié)構(gòu)如紅黑樹取代鏈表組織碰撞哈希(并不解決哈希碰撞，只是減輕攻擊影響，將N個(gè)數(shù)據(jù)的操作時(shí)間從O(N^2)降至O(NlogN)，代價(jià)是普通情況下接近O(1)的操作均變?yōu)镺(logN))。

目前使用最多的仍然是POST數(shù)據(jù)攻擊，因此建議生產(chǎn)環(huán)境的PHP均進(jìn)行升級(jí)或打補(bǔ)丁。至于從數(shù)據(jù)結(jié)構(gòu)層面修復(fù)這個(gè)問題，目前還沒有任何方面的消息。

參考

[1] Supercolliding a PHP array

[2] PHP5.2.*防止Hash沖突拒絕服務(wù)攻擊的Patch

[3] 通過構(gòu)造Hash沖突實(shí)現(xiàn)各種語言的拒絕服務(wù)攻擊

[4] PHP數(shù)組的Hash沖突實(shí)例

[5] PHP 5.4.0 RC4 released