關(guān)于 Hash Collision DoS 問(wèn)題（哈希碰撞）

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

• 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 沒(méi)有打MS11-100補(bǔ)丁

注意，Perl沒(méi)有這個(gè)問(wèn)題，因?yàn)镻erl在N年前就fix了這個(gè)問(wèn)題了。關(guān)于這個(gè)列表的更新，請(qǐng)參看 oCERT的2011-003報(bào)告，比較坑爹的是，這個(gè)問(wèn)題早在2003 年就在論文《通過(guò)算法復(fù)雜性進(jìn)行拒絕式服務(wù)攻擊》中被報(bào)告了，但是好像沒(méi)有引起注意，尤其是Java。

弱點(diǎn)攻擊解釋

你可以會(huì)覺(jué)得這個(gè)問(wèn)題沒(méi)有什么大不了的，因?yàn)楹诳褪强床坏絟ash算法的，如果你這么認(rèn)為，那么你就錯(cuò)了，這說(shuō)明對(duì)Web編程的了解還不足夠底層。

無(wú)論你用JSP，PHP，Python，Ruby來(lái)寫后臺(tái)網(wǎng)頁(yè)的時(shí)候，在處理HTTP POST數(shù)據(jù)的時(shí)候，你的后臺(tái)程序可以很容易地以訪問(wèn)表單字段名來(lái)訪問(wèn)表單值，就像下面這段程序一樣：

這是怎么實(shí)現(xiàn)的呢？這后面的東西就是Hash Map啊，所以，我可以給你后臺(tái)提交一個(gè)有10K字段的表單，這些字段名都被我精心地設(shè)計(jì)過(guò)，他們?nèi)�是Hash Collision ，于是你的Web Server或語(yǔ)言處理這個(gè)表單的時(shí)候，就會(huì)建造這個(gè)hash map，于是在每插入一個(gè)表單字段的時(shí)候，都會(huì)先遍歷一遍你所有已插入的字段，于是你的服務(wù)器的CPU一下就100%了，你會(huì)覺(jué)得這10K沒(méi)什么，那么我就發(fā)很多個(gè)的請(qǐng)求，你的服務(wù)器一下就不行了。

舉個(gè)例子，你可能更容易理解：

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

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

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

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

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

（關(guān)于Hash表的實(shí)現(xiàn)，如果你忘了，那就把大學(xué)時(shí)的《數(shù)據(jù)結(jié)構(gòu)》一書拿出來(lái)看看）

  Hash Collision DoS 詳解

StackOverflow.com是個(gè)好網(wǎng)站， 合格的程序員都應(yīng)該知道這個(gè)網(wǎng)站。上去一查，就看到了這個(gè)貼子“Application vulnerability due to Non Random Hash Functions”。我把這個(gè)貼子里的東西摘一些過(guò)來(lái)。

首先，這些語(yǔ)言使用的Hash算法都是“非隨機(jī)的”，如下所示，這個(gè)是Java和Oracle使用的Hash函數(shù)：

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

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

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

3）然后，我們可以用這4個(gè)長(zhǎng)度的字符串，構(gòu)造8個(gè)長(zhǎng)度的字符串，如下所示：

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

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

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

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

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

在攻擊時(shí)，我只需要把這些數(shù)據(jù)做成一個(gè)HTTP POST 表單，然后寫一個(gè)無(wú)限循環(huán)的程序，不停地提交這個(gè)表單。你用你的瀏覽器就可以了。當(dāng)然，如果做得更精妙一點(diǎn)的話，把你的這個(gè)表單做成一個(gè)跨站腳本，然后找一些網(wǎng)站的跨站漏洞，放上去，于是能過(guò)SNS的力量就可以找到N多個(gè)用戶來(lái)幫你從不同的IP來(lái)攻擊某服務(wù)器。

防守

要防守這樣的攻擊，有下面幾個(gè)招：

• 打補(bǔ)丁，把hash算法改了。
• 限制POST的參數(shù)個(gè)數(shù)，限制POST的請(qǐng)求長(zhǎng)度。
• 最好還有防火墻檢測(cè)異常的請(qǐng)求。

不過(guò)，對(duì)于更底層的或是其它形式的攻擊，可能就有點(diǎn)麻煩了。

（全文完）