PHP Hash Collision攻擊原理

哈希表是一種查找效率極高的資料結構，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 hashtable的雜湊演算法如下：

hash(key)=key & ntablemask

即簡單将資料的原始key與hashtable的ntablemask進行按位與即可。如果原始key為字元串，則首先使用times33算法将字元串轉為整形再與ntablemask按位與。

hash(strkey)=time33(strkey) & ntablemask

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

知道了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來生成，因為操作不當就會變成攻擊自己的腳本。

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

通過程式我們生成了65536條碰撞資料，然後在laravel中做個簡單的測試，測試代碼如下：

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

至此寫了三篇關于hashtable的文章，前兩篇文章開頭都有連結，能幫助大家對hahstable有更深的了解，之後不會再更新hashtable相關的文章了。