沒想到 Hash 衝突還能這麼玩,你的服務中招了嗎?

LevelDB,你好~

背景

其實這個問題我之前也看到過,剛好在前幾天,洪教授在某個群里分享的一個《一些有意思的攻擊手段.pdf》,我覺得這個話題還是有不少人不清楚的,今天我就準備來“實戰”一把,還請各位看官輕拍。

洪強寧(洪教授),愛因互動創始人兼 CTO,曾任豆瓣首席架構師,為中國 Python 用戶組(CPUG)的創立者之一。

這才是真大佬,原來洪教授在宜信的時候,就有分享過這個內容,可惜當初不知道沒參加。看了之後才知道原來我上一篇的文章中講的 計時攻擊(Timing Attack) 也是其中的內容之一。哈哈,後面有空再研究研究繼續講其他內容。

Hash 衝突

啥叫 Hash 衝突?我們從 Hash 表(或者散列表)講起,我們知道在一個 hash 表的查找一個元素,期望的時間複雜度為 O(1),怎麼做到的呢?其實就是 hash() 函數在起作用。

初略來講,hash 表內部實際存儲還是跟數組類似,用連續的內存空間存儲元素,只要通過某種方法將將要存儲的元素映射為數組的下標,即可像數組一樣通過下標去讀取對應的元素,這也是為什麼能做到 O(1) 的原因。

Hash 示例

以上圖為例,假設是我設計的一個 hash 函數,恰好滿足如下條件:

  • hash("hello")=0:字符串 “hello” 就存儲數組下標為 0 的地方;
  • hash("world")=2: “world” 存儲數組下標為 2 的地方;
  • hash("tangleithu")=5:”tangleithu” 存儲數組下標為 5 的地方;

目前來看一切好像很完美,但這終歸是假設,我不能假設這個 hash 都很完美的將不同的字符串都映射到了不同的下標處。

另外來了個字符串,hash("石頭") = 2,怎麼辦?這就是所謂的 “Hash 衝突”,最常見 Hash 衝突的解決方案其實就是“開鏈”法,其實還有比如線性試探、平方試探等等。

類似講解 HashMap 的文章滿大街都是,一搜一大把,本文就不詳述了。為了方便讀者理解,就簡單來個例子。

Hash衝突開鏈法

開鏈法如上圖所示,我們存儲元素的時候,存儲形式為一個鏈表,當衝突的時候,就在鏈表末尾直接加衝突的元素。上圖示例恰好運氣比較差,字符串 shitoustone 算出來的下標都為 2。

這樣一來,問題大了。原本我們期望 O(1) 的時間複雜度查找元素,現在變成在鏈表中線性查找了,而如果這個時候插入 個數據,最壞的情況下的時間複雜度就是 了。(這裡就不討論鏈錶轉樹的情形)

壞人乘機侵入

這就又給壞人留下了想象空間。只要壞人精心設計一組要放進 hash 表的字符串,且讓這些字符串的 hashcode 都一樣,這就會導致 hash 衝突,結果會導致 cpu 要花費大量的時間來處理 hash 衝突,造成 DoS(Denial of Service)攻擊。

而用 hash 表存儲的情形太常見了。在 Web 服務中,一般表單的處理都是用 hash 表來保存的(後端往往要知道通過某個具體的參數 key 獲取對應的參數 value)。

實戰

本文石頭哥將以 Java SpringBoot 為例,嘗試進行一次攻擊。

不過別以為這種 “Hash 衝突 DoS” 以為只有 Java 才有哦,什麼 Python,Apache Tomcat/Jetty,PHP 之類都會有這個問題的。其實早在 2011 年年末的時候就被大量爆出了,有的框架陸陸續續有一些改進和修復。詳細情況可以看這篇文章:oCERT-2011-003 multiple implementations denial-of-service via hash algorithm collision[1]

這裡,咱們給列舉其中一個 Apatch Tomcat,來自 CVE-2011-4858[2]

Apache Tomcat before 5.5.35, 6.x before 6.0.35, and 7.x before 7.0.23 computes hash values for form parameters without restricting the ability to trigger hash collisions predictably, which allows remote attackers to cause a denial of service (CPU consumption) by sending many crafted parameters.

下面截圖來自洪教授的 PPT,但內容的具體來源不詳了(嘗試找了下,沒找到),大家參考參考就好。

實現 hash 衝突 DoS 攻擊所須帶寬

左邊表示用不同的語言(框架)實現這種攻擊所需要的帶寬,右邊是攻擊的 cpu 目標。可以看出,實施這種攻擊成本其實挺低的(後文石頭的試驗也佐證了這一點)。

PHP是世界上最好的語言1

不得不說 “PHP 是世界上最好的編程語言”(大家別打架),還是有一定道理的,哈哈哈哈哈哈 (一張圖還不夠,再加一張)

PHP是世界上最好的語言2

上面的語言排序,不一定對,大家參考一下即可,不用糾結具體的準確性。

其實要驗證,方法當然也相對簡單,只要找出產生衝突的不同字符串即可,具體語言可能不一樣。

talk is cheap

“talk is cheap”,現在跟着我來嘗試進行一次攻擊吧,本人用自己的筆記本進行試驗(配置:MBP 13-inch,2.5 GHz Intel Core i7,16 GB 2133 MHz LPDDR3)。

首先構造一把 hash 衝突的字符串,下面代碼是 hash 衝突的字符串對的實例,後面的其實可以通過前面排列組合生成。

System.out.println("Aa".hashCode());
System.out.println("BB".hashCode());
System.out.println("BBBBBBBBBBBBBBBBBBBBBBBBAaBBBBAa".hashCode());
System.out.println("BBBBBBBBBBBBBBBBBBBBBBBBAaBBBBBB".hashCode());
// 輸出
2112
2112
2067858432
2067858432

具體生成過程本文不詳述了,感興趣可以看看 StackOverflow 上的這篇文章 Application vulnerability due to Non Random Hash Functions[3],或者參考耗子叔的這篇 Hash Collision DoS 問題[4]

three.js 歐拉角和四元數

然後我啟用一個 SpringBoot(2.2.2.RELEASE) 的 Web 服務,JDK 1.8(其實用 1.7 效果更明顯)。

@RequestMapping("/hash")
public String hash(HttpServletRequest request) {
    // Demo,簡單返回參數大小和其對應hashCode
    int size = request.getParameterMap().size();
    String key = (String)(request.getParameterMap().keySet().toArray())[0];
    return String.format("size=%s, hashCode=%s", size, key.hashCode());
}

先試水一把(如下圖),看看基本功能正常,用 curl 發送請求即可,然後將 post 的字段放在文件裡面(太長也只能放文件中)。

curl 實驗結果

生成的字符串不夠的話,還可以增加並發請求,可以借用類似 “Apache Benchmarking” 壓測的工具發送請求,我之前也有一篇文章介紹了這個命令 性能測試工具 – ab 簡單應用,感興趣的可以參考一下。

衝突的 hashcode 一樣

打個斷點看看效果,如上圖所示,確實所有的 hash 值都是一樣的。不過一次請求好像並沒有影響我電腦 cpu 的明顯變化。

我測試的字符串已經是 29859 個了,正準備生成更多的衝突的字符串進行嘗試時,結果仔細一看才發現請求被截斷了,請求返回的參數 size 大小為 10000。原來 SpringBoot 內置的 tomcat 給做了手腳,看下圖,因為默認的請求的參數個數大小被限制成 10000 了。

More than the maximum number of request parameters (GET plus POST) for a single request ([10,000]) were detected. Any parameters beyond this limit have been ignored. To change this limit, set the maxParameterCount attribute on the Connector.

post參數數量被限制

一種方法當然是去修改這個請求參數個數的限制。另外其實可以嘗試用 JDK 1.7 去驗證,應該效果會更好(原因,聰明的讀者你肯定知道吧?)。這裡石頭哥就懶得去折騰了,直接嘗試以量來取勝,用前文說的 ab 進行並發提交請求,然後觀察效果。

這是我用如下參數跑的壓測結果:

ab -c 200 -n 100000 -p req.txt 'localhost:8080/hash'

壓測的結果如圖所示:

ab 壓測 hash 衝突結果

然後我們來看看 CPU 的變化情況,特意錄屏做了個動圖,可以看出還是相對比較明顯的。從基本不佔用 cpu 到 39.6%,然後突然就漲到 158% 了。

實際試驗中這個過程沒有一直持續(上面是重試過程中抓到的其中一次),一方面因為本人用的 JDK 1.8,本來衝突後的查找過程已經優化了,可能效果並不明顯,另外也猜測可能會有一些 cache 之類的優化吧,另外對於 10000 的量也還不夠?具體我也沒有深究了,感興趣的讀者可以去嘗試一下玩玩。

hash-collision-demo動圖

實驗算成功了吧。

實驗成功就是拽

我這還是單機,要是多搞幾個 client,不分分鐘把 Web 服務搞死啊。

防禦方法

上面實驗算是成功了,那麼防禦方法呢?其實就是:

  • 改 hash 算法算一種了;例如像有的用隨機算法作為 hash 函數的情況,可以用不同的隨機種子嘗試生成;但其實沒有完美的 hash 算法的。
  • 本文實驗中的也遇到這個了,就是要限制請求的參數個數,以及請求長度。在不影響業務的情況下,限制儘可能更小;
  • 上 WAF(Web Application Firewall),用專業的防火牆清洗流量。

最後

本文只供學習交流使用,請大家不要輕易嘗試線上服務,不要輕易嘗試線上服務,不要輕易嘗試線上服務。

本人才疏學淺,如果有不對的地方,還望大家指出。

原創真心不易,希望你能幫我個小忙唄,如果本文內容你覺得有所啟發,有所收穫,請幫忙點個“在看”唄(若不好意思暴露,你起碼點個贊嘛),轉發分享就更好啦,這將是我繼續輸出更多優質文章的最強動力。

公眾號後台回復“模擬題”獲取算法筆試模擬題精解合集(也可以直接到阿里雲開發者社區下載),該書籍為阿里雲開發電子書系列之一,涵蓋 70+算法題目,近 30 種大廠筆試常考知識點。希望在你“面試戰場”上能夠助你一臂之力。

關於作者:程序猿石頭(ID: tangleithu),現任阿里巴巴技術專家,清華學渣,前大疆後端 Leader。用不同的視角分享高質量技術文章,以每篇文章都讓人有收穫為目的,歡迎關注,交流和指導!

參考資料

[1]

oCERT-2011-003 multiple implementations denial-of-service via hash algorithm collision: http://ocert.org/advisories/ocert-2011-003.html

[2]

CVE-2011-4858: https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2011-4858

[3]

Application vulnerability due to Non Random Hash Functions: https://stackoverflow.com/questions/8669946/application-vulnerability-due-to-non-random-hash-functions

[4]

Hash Collision DoS 問題: https://coolshell.cn/articles/6424.html

沒想到 Hash 衝突還能這麼玩,你的服務中招了嗎?
免責聲明:非本網註明原創的信息,皆為程序自動獲取互聯網,目的在於傳遞更多信息,並不代表本網贊同其觀點和對其真實性負責;如此頁面有侵犯到您的權益,請給站長發送郵件,並提供相關證明(版權證明、身份證正反面、侵權鏈接),站長將在收到郵件12小時內刪除。

深入理解JVM(③)Java的鎖優化