什么是Hash碰撞攻擊

就是通過精心構造數據，使得所有數據全部碰撞，人為將哈希表變成一個退化的單鏈表，此時哈希表各種操作的時間均提升了一個數量級，因此會消耗大量CPU資源，導致系統無法快速響應請求，從而達到拒絕服務攻擊（DoS）的目的。

隨著RESTful風格的接口普及，程序員默認都會使用json作為數據傳遞的方式。json格式的數據冗余少，兼容性高，從提出到現在已被廣泛的使用，可以說成為了Web的一種標準。無論我們服務端使用什么語言，我們拿到json格式的數據之后都需要做jsonDecode(),將json串轉換為json對象，而對象默認會存儲于Hash Table，而Hash Table很容易被碰撞攻擊。我只要將攻擊數據放在json中，服務端程序在做jsonDecode()時必定中招，中招后CPU會立刻飆升至100%。16核的CPU，16個請求就能達到DoS的目的。

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

哈希表是一種查找效率極高的數據結構，很多語言都在內部實現了哈希表。php中的哈希表是一種極為重要的數據結構，不但用于表示Array數據類型，還在Zend虛擬機內部用于存儲上下文環境信息（執行上下文的變量及函數均使用哈希表結構存儲）。

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

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

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