GSS資安電子報0061期【雜湊函式碰撞讓網頁伺服器遭受 DoS攻擊】

alt

原        文：http://blog.fortify.com/blog/2012/01/04/Web-Server-DoS-by-Hash-Collisionalt

翻譯整理：叡揚資訊 資訊安全事業處

大多數的網頁伺服器為了效能考量，都使用雜湊表(Hash Table)儲存來自瀏覽器的要求(Request)參數。當這些要求內含許多個參數，假設10,000個參數，且參數名稱的雜湊值都是相同的，此時，網頁伺服器將會耗費許多時間來剖析這些要求。於此狀況下，因為雜湊碰撞，將導致新增雜湊的動作，變得十分緩慢，進而造成網頁伺服器效能明顯下降，並可能導致阻斷服務(DoS)攻擊的情況發生。

如果程式語言不提供隨機雜湊函式，或是網頁伺服器無法辨識使用多重碰撞的攻擊，攻擊者便可藉由傳送眾多的碰撞鍵(Colliding Key)，來讓雜湊表「變質」，以達到攻擊的目的。此時，插入n個項目到雜湊表的演算法複雜度會變成O(n**2)；因此，使用單一個 HTTP 要求可能會耗用CPU數小時的時間，達到阻斷服務攻擊之目的。

以前就有人撰文提及雜湊表會造成阻斷服務，但是從沒有人真正知道要如何去產生大量的多重碰撞字串，直到2011年12月28日在德國柏林所舉辦的第28屆Chaos Communication Congress（簡稱 28C3）之後，才有實際的攻擊示範出現。

Alexander Klink與Julian Wälde在該會場演講《Efficient Denial of Service Attacks on Web Application Platforms》指出，大部分的字串雜湊函式不是以 DJBX33A (Dan Bernstein's times 33, addition)演算法、就是DJBX33X(Dan Bernstein's times 33, XOR)演算法為基礎，這2個演算法分別存在「等價子字串」(Equivalent substrings)與「中途相遇」(Meet-in-the-middle)攻擊的弱點。

DJBX33A有個特性，如果兩個字串碰撞，例如：
hash('GSS') = hash('655')
雜湊之後，在相同位置也有這樣的子字串，例如：
hash('prefixGSSpostfix') = hash('prefix655postfix')

因此，我們可以輕易地產生碰撞字串的初始字串，比方說：GSSGSS、GSS655、655GSS …等。

至於DJBX33X演算法不會有「等價子字串」弱點，但是會有「中途相遇」的弱點。藉由「中途相遇」手法，攻擊者大約有1/2^16的機會可以取得碰撞字串，以便輕鬆地進行搜尋。Alexander Klink與Julian Wälde使用這些技術，成功地在下列伺服器進行 DoS 攻擊：

 

伺服器

結果

PHP
  • 70~100 kbit/s 讓單一i7 核心的伺服器持續忙碌
  • Gigabit 連線讓10,000 個i7 核心的伺服器忙碌

ASP.NET
  • 30 kbit/s 讓單一Core2 核心的伺服器持續忙碌
  • Gigabit 連線讓30,000 個Core2 核心的伺服器忙碌

Java Tomcat6
  • 6 kbit/s 讓單一i7 心的伺服器持續忙碌
  • Gigabit 連線讓100,000 個i7 的伺服器忙碌

Python（僅32 位元）
  • 20 kbit/s 讓單一Core Duo 核心的伺服器持續忙碌
  • Gigabit 連線讓50,000 個Core Duo 核心的伺服器忙碌

Ruby
  • 850 kbit/s 讓單一i7 核心的伺服器持續忙碌
  • Gigabit 連線讓1,000,000 個i7 核心的伺服器忙碌

 

解決之道：

  1. 微軟已經在2011年12月29日發行了MS11-100 的修正程式，加入了一個新的設定參數aspnet:MaxHttpCollectionKeys，預設值為 1,000。
  2. Tomcat發行7.0.23與6.0.35，提供新的設定參數：maxParameterCount，預設值為10,000。
  3. PHP發行5.4.0 RC4，提供新的設定參數，用來控制輸入的參數總數：max_input_vars，以避免雜湊碰撞的攻擊。
  4. 若因某些因素不能升級網頁伺服器版本，最簡單的修復方式為，調降CPU針對要求的回應時間，例如：PHP可以設定max_input_time參數；在IIS 6.0 以上（含）的伺服器上，則設定工作者處理序的關閉時間限制這個參數，如下圖所示。

alt

參考資料：

1. 《Efficient Denial of Service Attacks on Web Application Platforms》報告原文：
http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf

2. n.runs-SA-2011.004 Advisory：
http://www.nruns.com/_downloads/advisory28122011.pdf

上一篇 下一篇