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

哈希表是一種查找效率極高的數據結構，很多語言都在內部實現了哈希表。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那基本就沒戲了，幸運的是（也可以說不幸的是）大多數編程語言使用的哈希算法都十分簡單（這是為了效率考慮），因此可以不費吹灰之力之力構造出攻擊數據。

二、如何防御

• 打補丁，修改hash算法。

• 限制POST的參數個數，限制POST的請求長度。

• 使用防火墻檢測異常請求

• 增加權限驗證，最大可能的在jsonDecode()之前把非法用戶拒絕

• 重寫jsonDecode()方法

分享一個可以導致hash碰撞的json串：https://raw.githubusercontent.com/laynefyc/php_thread_demo/master/javaHash.json

總結

以上是生活随笔為你收集整理的使用Hash碰撞进行DoS攻击的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。