沒(méi)想到 Hash 沖突還能這么玩,你的服務(wù)中招了嗎?
背景
其實(shí)這個(gè)問(wèn)題我之前也看到過(guò)，剛好在前幾天，洪教授在某個(gè)群里分享的一個(gè)《一些有意思的攻擊手段.pdf》，我覺(jué)得這個(gè)話題應(yīng)該還是有不少人不清楚的，今天我就準(zhǔn)備來(lái)“實(shí)戰(zhàn)”一把，還請(qǐng)各位看官輕拍。
洪強(qiáng)寧（洪教授），愛(ài)因互動(dòng)創(chuàng)始人兼 CTO，曾任豆瓣首席架構(gòu)師，為中國(guó) Python 用戶組（CPUG）的創(chuàng)立者之一。
這才是真大佬，原來(lái)洪教授在宜信的時(shí)候，就有分享過(guò)這個(gè)內(nèi)容，可惜當(dāng)初不知道沒(méi)參加?？戳酥蟛胖涝瓉?lái)我上一篇的文章中講的 計(jì)時(shí)攻擊（Timing Attack） 也是其中的內(nèi)容之一。哈哈，后面有空再研究研究繼續(xù)講其他內(nèi)容。
Hash 沖突
啥叫 Hash 沖突？我們從 Hash 表（或者散列表）講起，我們知道在一個(gè) hash 表的查找一個(gè)元素，期望的時(shí)間復(fù)雜度為 O(1)，怎么做到的呢？其實(shí)就是 hash() 函數(shù)在起作用。
初略來(lái)講，hash 表內(nèi)部實(shí)際存儲(chǔ)還是跟數(shù)組類似，用連續(xù)的內(nèi)存空間存儲(chǔ)元素，只要通過(guò)某種方法將將要存儲(chǔ)的元素映射為數(shù)組的下標(biāo)，即可像數(shù)組一樣通過(guò)下標(biāo)去讀取對(duì)應(yīng)的元素，這也是為什么能做到 O(1) 的原因。
Hash 示例以上圖為例，假設(shè)是我設(shè)計(jì)的一個(gè) hash 函數(shù)，恰好滿足如下條件：
hash("hello")=0：字符串 "hello" 就存儲(chǔ)數(shù)組下標(biāo)為 0 的地方；hash("world")=2："world" 存儲(chǔ)數(shù)組下標(biāo)為 2 的地方；hash("tangleithu")=5："tangleithu" 存儲(chǔ)數(shù)組下標(biāo)為 5 的地方；
目前來(lái)看一切好像很完美，但這終歸是假設(shè)，我不能假設(shè)這個(gè) hash 都很完美的將不同的字符串都映射到了不同的下標(biāo)處。
另外來(lái)了個(gè)字符串，hash("石頭") = 2，怎么辦？這就是所謂的 “Hash 沖突”，最常見(jiàn) Hash 沖突的解決方案其實(shí)就是“開(kāi)鏈”法，其實(shí)還有比如線性試探、平方試探等等。
類似講解 HashMap 的文章滿大街都是，一搜一大把，本文就不詳述了。為了方便讀者理解，就簡(jiǎn)單來(lái)個(gè)例子。
Hash沖突開(kāi)鏈法開(kāi)鏈法如上圖所示，我們存儲(chǔ)元素的時(shí)候，存儲(chǔ)形式為一個(gè)鏈表，當(dāng)沖突的時(shí)候，就在鏈表末尾直接添加沖突的元素。上圖示例恰好運(yùn)氣比較差，字符串 shitou，stone 算出來(lái)的下標(biāo)都為 2。
這樣一來(lái)，問(wèn)題大了。原本我們期望 O(1) 的時(shí)間復(fù)雜度查找元素，現(xiàn)在變成在鏈表中線性查找了，而如果這個(gè)時(shí)候插入 個(gè)數(shù)據(jù)，最壞的情況下的時(shí)間復(fù)雜度就是 了。（這里就不討論鏈表轉(zhuǎn)樹(shù)的情形）
壞人可乘機(jī)而入這就又給壞人留下了想象空間。只要壞人精心設(shè)計(jì)一組要放進(jìn) hash 表的字符串，且讓這些字符串的 hashcode 都一樣，這就會(huì)導(dǎo)致 hash 沖突，結(jié)果會(huì)導(dǎo)致 cpu 要花費(fèi)大量的時(shí)間來(lái)處理 hash 沖突，造成 DoS（Denial of Service）攻擊。
而用 hash 表存儲(chǔ)的情形太常見(jiàn)了。在 Web 服務(wù)中，一般表單的處理都是用 hash 表來(lái)保存的（后端往往要知道通過(guò)某個(gè)具體的參數(shù) key 獲取對(duì)應(yīng)的參數(shù) value）。
實(shí)戰(zhàn)
本文石頭哥將以 Java SpringBoot 為例，嘗試進(jìn)行一次攻擊。
不過(guò)別以為這種 “Hash 沖突 DoS” 以為只有 Java 才有哦，什么 Python，Apache Tomcat/Jetty，PHP 之類都會(huì)有這個(gè)問(wèn)題的。其實(shí)早在 2011 年年末的時(shí)候就被大量爆出了，有的框架陸陸續(xù)續(xù)有一些改進(jìn)和修復(fù)。詳細(xì)情況可以看這篇文章：oCERT-2011-003 multiple implementations denial-of-service via hash algorithm collision[1]。
這里，咱們給列舉其中一個(gè) Apatch Tomcat，來(lái)自 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.
下面截圖來(lái)自洪教授的 PPT，但內(nèi)容的具體來(lái)源不詳了（嘗試找了下，沒(méi)找到），大家參考參考就好。
實(shí)現(xiàn) hash 沖突 DoS 攻擊所須帶寬左邊表示用不同的語(yǔ)言（框架）實(shí)現(xiàn)這種攻擊所需要的帶寬，右邊是攻擊的 cpu 目標(biāo)?？梢钥闯?，實(shí)施這種攻擊成本其實(shí)挺低的（后文石頭的試驗(yàn)也佐證了這一點(diǎn)）。
不得不說(shuō) “PHP 是世界上最好的編程語(yǔ)言”（大家別打架），還是有一定道理的，哈哈哈哈哈哈 ?（一張圖還不夠，再加一張）
上面的語(yǔ)言排序，不一定對(duì)，大家參考一下即可，不用糾結(jié)具體的準(zhǔn)確性。
其實(shí)要驗(yàn)證，方法當(dāng)然也相對(duì)簡(jiǎn)單，只要找出產(chǎn)生沖突的不同字符串即可，具體語(yǔ)言可能不一樣。
talk is cheap
現(xiàn)在跟著我來(lái)嘗試進(jìn)行一次攻擊吧，本人用自己的筆記本進(jìn)行試驗(yàn)（配置：MBP 13-inch，2.5 GHz Intel Core i7，16 GB 2133 MHz LPDDR3）。
首先構(gòu)造一把 hash 沖突的字符串，下面代碼是 hash 沖突的字符串對(duì)的實(shí)例，后面的其實(shí)可以通過(guò)前面排列組合生成。
System.out.println("Aa".hashCode());
System.out.println("BB".hashCode());
System.out.println("BBBBBBBBBBBBBBBBBBBBBBBBAaBBBBAa".hashCode());
System.out.println("BBBBBBBBBBBBBBBBBBBBBBBBAaBBBBBB".hashCode());
//?輸出
2112
2112
2067858432
2067858432
具體生成過(guò)程本文不詳述了，感興趣可以看看 StackOverflow 上的這篇文章 Application vulnerability due to Non Random Hash Functions[3]，或者參考耗子叔的這篇 Hash Collision DoS 問(wèn)題[4]。
然后我啟用一個(gè) SpringBoot（2.2.2.RELEASE） 的 Web 服務(wù)，JDK 1.8（其實(shí)用 1.7 效果更明顯）。
@RequestMapping("/hash")
public?String?hash(HttpServletRequest?request)?{
????//?Demo，簡(jiǎn)單返回參數(shù)大小和其對(duì)應(yīng)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 發(fā)送請(qǐng)求即可，然后將 post 的字段放在文件里面（太長(zhǎng)也只能放文件中）。
curl 實(shí)驗(yàn)結(jié)果生成的字符串不夠的話，還可以增加并發(fā)請(qǐng)求，可以借用類似 “Apache Benchmarking” 壓測(cè)的工具發(fā)送請(qǐng)求，我之前也有一篇文章介紹了這個(gè)命令 性能測(cè)試工具 - ab 簡(jiǎn)單應(yīng)用，感興趣的可以參考一下。
沖突的 hashcode 一樣打個(gè)斷點(diǎn)看看效果，如上圖所示，確實(shí)所有的 hash 值都是一樣的。不過(guò)一次請(qǐng)求好像并沒(méi)有影響我電腦 cpu 的明顯變化。
我測(cè)試的字符串已經(jīng)是 29859 個(gè)了，正準(zhǔn)備生成更多的沖突的字符串進(jìn)行嘗試時(shí)，結(jié)果仔細(xì)一看才發(fā)現(xiàn)請(qǐng)求被截?cái)嗔?，?qǐng)求返回的參數(shù) size 大小為 10000。原來(lái) SpringBoot 內(nèi)置的 tomcat 給做了手腳，看下圖，因?yàn)槟J(rèn)的請(qǐng)求的參數(shù)個(gè)數(shù)大小被限制成 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參數(shù)數(shù)量被限制一種方法當(dāng)然是去修改這個(gè)請(qǐng)求參數(shù)個(gè)數(shù)的限制。另外其實(shí)可以嘗試用 JDK 1.7 去驗(yàn)證，應(yīng)該效果會(huì)更好（原因，聰明的讀者你肯定知道吧？）。這里石頭哥就懶得去折騰了，直接嘗試以量來(lái)取勝，用前文說(shuō)的 ab 進(jìn)行并發(fā)提交請(qǐng)求，然后觀察效果。
這是我用如下參數(shù)跑的壓測(cè)結(jié)果：
ab?-c?200?-n?100000?-p?req.txt?'localhost:8080/hash'
壓測(cè)的結(jié)果如圖所示：
ab 壓測(cè) hash 沖突結(jié)果然后我們來(lái)看看 CPU 的變化情況，特意錄屏做了個(gè)動(dòng)圖，可以看出還是相對(duì)比較明顯的。從基本不占用 cpu 到 39.6%，然后突然就漲到 158% 了。
hash-collision-demo動(dòng)圖實(shí)際試驗(yàn)中這個(gè)過(guò)程沒(méi)有一直持續(xù)（上面是重試過(guò)程中抓到的其中一次），一方面因?yàn)楸救擞玫?JDK 1.8，本來(lái)沖突后的查找過(guò)程已經(jīng)優(yōu)化了，可能效果并不明顯，另外也猜測(cè)可能會(huì)有一些 cache 之類的優(yōu)化吧，另外對(duì)于 10000 的量也還不夠？具體我也沒(méi)有深究了，感興趣的讀者可以去嘗試一下玩玩。
到這里實(shí)驗(yàn)算成功了吧。
實(shí)驗(yàn)成功就是拽我這還是單機(jī)，要是多搞幾個(gè) client，不分分鐘把 Web 服務(wù)搞死啊。
防御方法
上面實(shí)驗(yàn)算是成功了，那么防御方法呢？其實(shí)就是：
- 改 hash 算法算一種了；例如像有的用隨機(jī)算法作為 hash 函數(shù)的情況，可以用不同的隨機(jī)種子嘗試生成；但事實(shí)上并沒(méi)有完美的 hash 算法的。
- 本文實(shí)驗(yàn)中的也遇到這個(gè)了，就是要限制請(qǐng)求的參數(shù)個(gè)數(shù)，以及請(qǐng)求長(zhǎng)度。在不影響業(yè)務(wù)的情況下，限制盡可能更小；
- 上 WAF（Web Application Firewall），用專業(yè)的防火墻清洗流量。
本文只供學(xué)習(xí)交流使用，請(qǐng)大家不要輕易嘗試線上服務(wù)，不要輕易嘗試線上服務(wù)，不要輕易嘗試線上服務(wù)。
本人才疏學(xué)淺，如果有不對(duì)的地方，還望大家指出。
點(diǎn)個(gè)在看,贊?支持我吧