此文為Infoq中文站QSecurity專欄供稿

2011年12月28日，由Google贊助成立的安全漏洞研究組織oCERT（Open source Computer Emergency Response Team — 開源軟件應(yīng)急響應(yīng)團(tuán)隊）公開了一份安全漏洞報告。這份報告是幾個月前由德國安全研究公司nrun.com所提供的，其核心內(nèi)容是：目前絕大多數(shù)的web應(yīng)用，都存在著一個叫做哈希碰撞式拒絕服務(wù)攻擊的漏洞（Hash Collision DoS）。這份報告的公布，使得2011年剩下的幾天里，各互聯(lián)網(wǎng)公司的技術(shù)團(tuán)隊集體忙于對網(wǎng)站進(jìn)行針對此漏洞的防護(hù)工作。硝煙散盡之后，讓我們一起從攻擊者的角度重新審視一下這個漏洞及其利用手法。

如果你熟悉幾種常用語言下的哈希表（HashTable）實現(xiàn)，你大概會清楚以下的一些關(guān)于哈希表的基本概念：

哈希表通過一個哈希函數(shù)對鍵值（key）進(jìn)行散列操作，并且最終根據(jù)散列結(jié)果將鍵值對（key-value-pair）儲存到數(shù)組的某個節(jié)點（一般通過對數(shù)組長度取余實現(xiàn)）。哈希表的數(shù)組長度會根據(jù)元素的實際數(shù)量動態(tài)進(jìn)行擴(kuò)容，以保證有足夠空間并降低取余后的結(jié)果出現(xiàn)重復(fù)的可能性。不同的實現(xiàn)，其初始默認(rèn)長度、擴(kuò)容條件及擴(kuò)容算法均可能有所區(qū)別。

極端情況下，哈希表將會退化成鏈表。根據(jù)上面的基礎(chǔ)知識，我們知道這里的極端情況包括兩種：所有元素的哈希值相等；或者所有元素的哈希值針對哈希表數(shù)組長度取余的結(jié)果相等。而退化為鏈表則會導(dǎo)致哈希表性能的急劇下降。實際測試中，針對8萬條級別的數(shù)據(jù)，原本只需要數(shù)毫秒即可完成的插入或者查詢操作，在退化為鏈表后則需要長達(dá)30秒以上的時間才能完成。

那么對攻擊者來說，利用這一原理對某個web站點發(fā)起拒絕服務(wù)攻擊只需要考慮以下兩個問題：

問題一、如何構(gòu)造一個可使哈希表完全退化成鏈表的鍵值集合。問題二、如何使用該集合引導(dǎo)目標(biāo)服務(wù)器建立一個哈希表數(shù)據(jù)結(jié)構(gòu)。

針對問題一，具體的思路很簡單，就是要找到一個字符串集合，使得該集合的每個元素要么滿足哈希值相等；要么使得其哈希值針對哈希表數(shù)組長度取余的結(jié)果相等。構(gòu)造大量的哈希沖突是一個比較困難的問題。但是對攻擊者來說，非常幸運的是目前常見的哈希表的哈希函數(shù)實現(xiàn)，都是基于著名的DJBX33哈希算法或者其變形算法。比如，PHP5使用的是DJBX33A；ASP.NET和Python使用的是DJBX33X；Java使用的是一個做了兩個常數(shù)變形的變種DJBX33A。針對這些哈希算法，攻擊者已經(jīng)可以有很多方法做針對性的哈希碰撞生成了。最常用的方法有“相等子串法”和“中間相遇法”等。以“相等子串法”為例，由于DJBX33A系列哈希算法滿足一個很有意思的特性：如果hash(“string1”) = hash(“string2”)，那么在相同位置包含此2個子串的父串哈希結(jié)果將會產(chǎn)生碰撞，既：hash(“prefix_string1_postfix”) = hash(“prefix_string2_postfix”)。根據(jù)這一特性，攻擊者如果能找到最簡單的兩個碰撞字符串，那么就可以很快通過反復(fù)組合，生成2的n次方個長度為2n的碰撞字符串?！爸虚g相遇法”事實上是一種暴力破解辦法。只不過通過巧妙刪選縮小了結(jié)果集的甄別范圍，然后在可能產(chǎn)生碰撞的結(jié)果集中遍歷尋找碰撞集合。除此之外，針對較為復(fù)雜的哈希算法的碰撞，如MD5等算法，我國的王小云教授的“模差分法”是一種比較實用的碰撞分析方法。

如果通過算法構(gòu)造哈希結(jié)果完全一致的字符串集合有難度，那么也可以退而求其次，只要滿足哈希值對哈希表數(shù)組長度取余的最終結(jié)果相等就可以了。網(wǎng)上目前有很多針對PHP的示例攻擊代碼，就是根據(jù)這個原理實現(xiàn)的。利用這種方式，需要對該語言下哈希表數(shù)組經(jīng)過反復(fù)擴(kuò)容后的最終長度如何產(chǎn)生有一個清楚的了解。例如在PHP的實現(xiàn)中，所有哈希表數(shù)組的長度一定是2的n次方。根據(jù)元素總個數(shù)和加載因子（一個哈希表實現(xiàn)中滿足擴(kuò)容條件的臨界值），就可以計算出最終生成的哈希表的數(shù)組長度。剩下的事情就只需要保證待選鍵值的哈希結(jié)果對這個長度取余的結(jié)果相等，這樣即可達(dá)到制造大量哈希沖突字符串的目的。

在成功構(gòu)造好一個可以使哈希表完全退化成鏈表的鍵值集合后，攻擊者需要來解決第二個問題：如何使用該集合在服務(wù)器端建立一個哈希表數(shù)據(jù)結(jié)構(gòu)。

這個問題事實上已經(jīng)再簡單不過了：在所有的web應(yīng)用中，為了方便程序?qū)eb請求的各項參數(shù)進(jìn)行快速讀操作，HTTP Request中的Header, Form以及QueryString，都使用了哈希表進(jìn)行存儲。那么剩下的工作很簡單：就是以我們精心構(gòu)造好的鍵值列表作為一次HTTP請求的Header，F(xiàn)orm或者QueryString就可以了。實際攻擊中，由于大量Form表單的Post構(gòu)造更加簡單，甚至可以使用瀏覽器完成，所以也會通常成為進(jìn)行攻擊的首選突破口。通過在單機上重復(fù)構(gòu)造大量的HTTP Post請求，向Web服務(wù)器發(fā)送大量表單數(shù)據(jù)，會使得目標(biāo)服務(wù)器的CPU迅速被占滿而失去服務(wù)能力，達(dá)到攻擊目的。

如果對方的服務(wù)器數(shù)量比較多，或者防火墻敏銳地發(fā)現(xiàn)了攻擊者短時間內(nèi)向服務(wù)器Post大量數(shù)據(jù)的行為，并進(jìn)行了阻截，那么有可能還是達(dá)不到讓對方“拒絕服務(wù)”的目的。這種情況下，攻擊者會傾向于使用一定數(shù)量的“僵尸網(wǎng)絡(luò)”對目標(biāo)發(fā)起攻擊。由于這個攻擊非常簡單，只需要構(gòu)造一個HTTP請求即可實現(xiàn)，那么你可以去自己創(chuàng)建一個內(nèi)容非常吸引人的頁面，或者利用一個訪問量較大但是存在跨站腳本漏洞（XSS）的頁面，在頁面中加入一小段對最終用戶不可見，但是會自動發(fā)送一個Post請求到目標(biāo)站點的JavaScript腳本，你的拒絕服務(wù)攻擊（DoS）就成功升級為分布式拒絕服務(wù)攻擊（DDoS）了。而訪問這些頁面的普通用戶，則會在不知情的情況下成為幫助你繼續(xù)攻擊的“僵尸”群。

文章的最后，還是想補充一下關(guān)于針對這類攻擊的防護(hù)工作。目前絕大部分的補丁都是針對HTTP請求中表單項的數(shù)量加以限制。這個方法確實有效。測試數(shù)據(jù)顯示，1000個元素的鏈表操作對性能的影響還是可以接受的。但是如果你的Web應(yīng)用在服務(wù)端需要接收某個表單項，并通過字符處理（不管是XML還是JSON）將用戶輸入的表單值轉(zhuǎn)換成哈希表的話，那么很遺憾，目前這些補丁都幫不了你，你的應(yīng)用將依然存在被拒絕服務(wù)攻擊的可能。只不過攻擊的方式從構(gòu)造HTTP Request中的哈希表，變成了構(gòu)造實際業(yè)務(wù)處理代碼中的哈希表。對這一問題的完美解決方案，應(yīng)該是如Perl在n年前做的那樣：在哈希算法中引入隨機鹽使得構(gòu)造哈希沖突變?yōu)椴豢赡堋?/p>