關于 Hash Collision DoS 問題（哈希碰撞）

作者：來源：發布時間：2012-1-6 9:42:10 點擊：

最近，除了國內明文密碼的安全事件，還有一個事是比較大的，那就是 Hash Collision DoS （Hash碰撞的拒絕式服務攻擊），有惡意的人會通過這個安全弱點會讓你的服務器運行巨慢無比。這個安全弱點利用了各語言的Hash算法的“非隨機性”可以制造出N多的value不一樣，但是key一樣數據，然后讓你的Hash表成為一張單向鏈表，而導致你的整個網站或是程序的運行性能以級數下降（可以很輕松的讓你的CPU升到100%）。目前，這個問題出現于Java, JRuby, PHP, Python, Rubinius, Ruby這些語言中，主要：

Java, 所有版本
JRuby <= 1.6.5 （目前fix在 1.6.5.1）
PHP <= 5.3.8, <= 5.4.0RC3 （目前fix在 5.3.9, 5.4.0RC4）
Python, all versions
Rubinius, all versions
Ruby <= 1.8.7-p356 （目前fix在 1.8.7-p357, 1.9.x）
Apache Geronimo, 所有版本
Apache Tomcat <= 5.5.34, <= 6.0.34, <= 7.0.22 （目前fix在 5.5.35, 6.0.35, 7.0.23）
Oracle Glassfish <= 3.1.1 （目前fix在mainline）
Jetty, 所有版本
Plone, 所有版本
Rack <= 1.3.5, <= 1.2.4, <= 1.1.2 （目前fix 在 1.4.0, 1.3.6, 1.2.5, 1.1.3）
V8 JavaScript Engine, 所有版本
ASP.NET 沒有打MS11-100補丁

注意，Perl沒有這個問題，因為Perl在N年前就fix了這個問題了。關于這個列表的更新，請參看 oCERT的2011-003報告，比較坑爹的是，這個問題早在2003 年就在論文《通過算法復雜性進行拒絕式服務攻擊》中被報告了，但是好像沒有引起注意，尤其是Java。

弱點攻擊解釋

你可以會覺得這個問題沒有什么大不了的，因為黑客是看不到hash算法的，如果你這么認為，那么你就錯了，這說明對Web編程的了解還不足夠底層。

無論你用JSP，PHP，Python，Ruby來寫后臺網頁的時候，在處理HTTP POST數據的時候，你的后臺程序可以很容易地以訪問表單字段名來訪問表單值，就像下面這段程序一樣：

1
2
3

$usrname = $_POST['username'];

$passwd = $_POST['password'];

這是怎么實現的呢？這后面的東西就是Hash Map啊，所以，我可以給你后臺提交一個有10K字段的表單，這些字段名都被我精心地設計過，他們全是Hash Collision ，于是你的Web Server或語言處理這個表單的時候，就會建造這個hash map，于是在每插入一個表單字段的時候，都會先遍歷一遍你所有已插入的字段，于是你的服務器的CPU一下就100%了，你會覺得這10K沒什么，那么我就發很多個的請求，你的服務器一下就不行了。

舉個例子，你可能更容易理解：

如果你有n個值—— v1, v2, v3, … vn，把他們放到hash表中應該是足夠散列的，這樣性能才高：

0 -> v2
1 -> v4
2 -> v1
…
…
n -> v(x)

但是，這個攻擊可以讓我造出N個值—— dos1, dos2, …., dosn，他們的hash key都是一樣的（也就是Hash Collision），導致你的hash表成了下面這個樣子：

0 – > dos1 -> dos2 -> dos3 -> …. ->dosn
1 -> null
2 -> null
…
…
n -> null

于是，單向鏈接就這樣出現了。這樣一來，O(1)的搜索算法復雜度就成了O(n)，而插入N個數據的算法復雜度就成了O(n^2)，你想想這是什么樣的性能。

（關于Hash表的實現，如果你忘了，那就把大學時的《數據結構》一書拿出來看看）

Hash Collision DoS 詳解

StackOverflow.com是個好網站，合格的程序員都應該知道這個網站。上去一查，就看到了這個貼子“Application vulnerability due to Non Random Hash Functions”。我把這個貼子里的東西摘一些過來。

首先，這些語言使用的Hash算法都是“非隨機的”，如下所示，這個是Java和Oracle使用的Hash函數：

static int hash(int h) 
{ 
h ^= (h >>> 20) ^ (h >>> 12); 
return h ^ (h >>> 7) ^ (h >>> 4); 
}

所謂“非隨機的” Hash算法，就可以猜。比如：

1）在Java里， Aa和BB這兩個字符串的hash code(或hash key) 是一樣的，也就是Collision 。

2）于是，我們就可以通過這兩個種子生成更多的擁有同一個hash key的字符串。如：”AaAa”, “AaBB”, “BBAa”, “BBBB”。這是第一次迭代。其實就是一個排列組合，寫個程序就搞定了。

3）然后，我們可以用這4個長度的字符串，構造8個長度的字符串，如下所示：

 "AaAaAaAa", "AaAaBBBB", "AaAaAaBB", "AaAaBBAa",

 "BBBBAaAa", "BBBBBBBB", "BBBBAaBB", "BBBBBBAa",

 "AaBBAaAa", "AaBBBBBB", "AaBBAaBB", "AaBBBBAa",

 "BBAaAaAa", "BBAaBBBB", "BBAaAaBB", "BBAaBBAa",

4）同理，我們就可以生成16個長度的，以及256個長度的字符串，總之，很容易生成N多的這樣的值。

在攻擊時，我只需要把這些數據做成一個HTTP POST 表單，然后寫一個無限循環的程序，不停地提交這個表單。你用你的瀏覽器就可以了。當然，如果做得更精妙一點的話，把你的這個表單做成一個跨站腳本，然后找一些網站的跨站漏洞，放上去，于是能過SNS的力量就可以找到N多個用戶來幫你從不同的IP來攻擊某服務器。