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

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

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

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

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

那么對(duì)攻擊者來(lái)說(shuō)，利用這一原理對(duì)某個(gè)web站點(diǎn)發(fā)起拒絕服務(wù)攻擊只需要考慮以下兩個(gè)問(wèn)題：

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

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

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

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

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

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

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