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的哈希算法異常簡單：
即簡單將數據的原始key與HashTable的nTableMask進行按位與即可。
如果原始key為字符串，則首先使用Times33算法將字符串轉為整形再與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個元素。
POST攻擊
當然，一般情況下很難遇到攻擊者可以直接修改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。
另外的防護方法是在Web服務器層面進行處理，例如限制http請求body的大小和參數的數量等，這個是現在用的最多的臨時處理方案。具體做法與不同Web服務器相關，不再詳述。
其它防護
上面的防護方法只是限制POST數據的數量，而不能徹底解決這個問題。例如，如果某個POST字段是一個json數據類型，會被PHPjson_decode，那么只要構造一個超大的json攻擊數據照樣可以達到攻擊目的。理論上，只要PHP代碼中某處構造Array的數據依賴于外部輸入，則都可能造成這個問題，因此徹底的解決方案要從Zend底層HashTable的實現動手。一般來說有兩種方式，一是限制每個桶鏈表的最長長度;二是使用其它數據結構如紅黑樹取代鏈表組織碰撞哈希(并不解決哈希碰撞，只是減輕攻擊影響，將N個數據的操作時間從O(N^2)降至O(NlogN)，代價是普通情況下接近O(1)的操作均變為O(logN))。
目前使用最多的仍然是POST數據攻擊，因此建議生產環境的PHP均進行升級或打補丁。至于從數據結構層面修復這個問題，目前還沒有任何方面的消息。
參考
[1] Supercolliding a PHP array
[2] PHP5.2.*防止Hash沖突拒絕服務攻擊的Patch
[3] 通過構造Hash沖突實現各種語言的拒絕服務攻擊
[4] PHP數組的Hash沖突實例
[5] PHP 5.4.0 RC4 released
