hashdos_调查HashDoS问题
hashdos
近一個(gè)月前，我就如何在不與供應(yīng)商互動(dòng)的情況下臨時(shí)解決 28C3上出現(xiàn)的HashDoS問題或其他代碼缺陷發(fā)表了一些想法。現(xiàn)在是時(shí)候更深入地研究復(fù)雜性攻擊并查看源了。 我完全假設(shè)java.util.HashMap和java.util.Hashtable是受此攻擊影響的最常用的Java數(shù)據(jù)結(jié)構(gòu)，因此本文僅將代碼集中在這些類型的后面。
哈希函數(shù)和索引數(shù)據(jù)結(jié)構(gòu)的簡(jiǎn)要介紹
哈希索引數(shù)據(jù)結(jié)構(gòu)因其簡(jiǎn)單的用法和優(yōu)點(diǎn)而非常受歡迎：
- 無需打擾索引表即可找到所需數(shù)據(jù)的正確位置
- 通過使用關(guān)鍵字而不是索引號(hào)訪問數(shù)據(jù)
- 添加或刪除操作的時(shí)間幾乎恒定
為了獲得這些好處，哈希索引數(shù)據(jù)結(jié)構(gòu)遵循有關(guān)如何索引數(shù)據(jù)的聰明思想。 索引是通過散列與背后數(shù)據(jù)關(guān)聯(lián)的關(guān)鍵字來計(jì)算的。 考慮以下示例，這是一個(gè)類似于代碼的簡(jiǎn)單示例：
myHashIndexedDataStructure [hash（keyword）] =特定數(shù)據(jù)聽起來很完美，但是它有一個(gè)主要缺點(diǎn)：在大多數(shù)情況下，使用的哈希函數(shù)不是加密函數(shù)。
根據(jù)Wikipedia的說法，函數(shù)本身調(diào)用哈希函數(shù)的唯一強(qiáng)制特征是
“將可變長(zhǎng)度的大型數(shù)據(jù)集（稱為鍵）映射到固定長(zhǎng)度的較小數(shù)據(jù)集”與稱自己為密碼哈希函數(shù)（再次是來自Wikipedia的定義）相反，它必須滿足更多，甚至更強(qiáng)大的要求：
”
- 計(jì)算任何給定消息的哈希值很容易（但不一定很快）
- 生成具有給定哈希值的消息是不可行的
- 在不更改哈希的情況下修改消息是不可行的
- 找到兩個(gè)具有相同哈希值的不同消息是不可行的
”
長(zhǎng)話短說，讓我們總結(jié)一下我們學(xué)到的知識(shí)以及用這些知識(shí)可以得出的結(jié)論：
如果關(guān)鍵字沖突，則哈希索引數(shù)據(jù)結(jié)構(gòu)需要某種計(jì)劃b）–一種后備算法–關(guān)于如何處理具有相同關(guān)鍵字哈希值的多個(gè)數(shù)據(jù)集。
實(shí)際上，有幾種可行的方法：
- 探測(cè)（轉(zhuǎn)移到固定或可計(jì)算的間隔）
- 多重哈希
- 條目鏈接（沖突條目的構(gòu)建列表）
- 覆蓋現(xiàn)有條目
以下哪種策略需要Java？ 首先，我們將檢查java.util的代碼。 Hashtable （僅顯示有趣的部分，為清晰起見，省略了其余代碼：
public synchronized V put(K key, V value) { ... // Makes sure the key is not already in the hashtable. Entry tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) %tab.length; for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { if((e.hash == hash) && e.key.equals(key)) { V old = e.value; e.value = value; return old; } } ... // Creates the new entry. Entry<K,V> e = tab[index]; tab[index] = new Entry<>(hash, key, value, e); count++; return null; } 可以看出，該類使用鍵對(duì)象（ 關(guān)鍵字 ）的hashCode （）函數(shù)來計(jì)算哈希值。 它遵循ANDing（＆運(yùn)算符），為了將其正確表示為Integer，MODULO（％運(yùn)算符），將表大小（建立循環(huán)環(huán)結(jié)構(gòu)：（table.length + 1）mod table.length？1，用余數(shù)除法）始終解決標(biāo)簽 []中的條目。
此后，將考慮所有條目 （-ies）并檢查哈希值是否相同且對(duì)象本身是否相同。 if -clause防止存儲(chǔ)同一對(duì)象的多個(gè)實(shí)例-舊的實(shí)例僅由新的實(shí)例替換。
如果在由key.hashCode （）標(biāo)識(shí)的當(dāng)前位置上找不到相同的對(duì)象（關(guān)于哈希值和equals （）方法），則將創(chuàng)建一個(gè)新的Entry，并將其放置在當(dāng)前位置并在該位置處理舊的Entry對(duì)象。
到目前為止，看起來java.util.Hashtable在每個(gè)tab []之后都使用某種列表作為數(shù)據(jù)結(jié)構(gòu)。
查看私有內(nèi)部類java.util.Hashtable.Entry <K，V>的代碼時(shí)，可以確認(rèn)此假設(shè)。
private static class Entry<K,V> implements Map.Entry<K,V> { int hash; K key; V value; Entry<K,V> next; 下一個(gè)Entry對(duì)象僅指向下一個(gè)Entry 。 這代表一個(gè)定制的鏈表。
java.util.HashMap的代碼更加復(fù)雜，并且表現(xiàn)部分不同（允許使用null值，！不同步！），但是基于相同的思想。 在這里調(diào)查代碼不會(huì)發(fā)現(xiàn)任何新內(nèi)容，除了Entry重新被重新實(shí)現(xiàn)的事實(shí)…）。
兩種實(shí)現(xiàn)都依賴于哈希索引數(shù)組的每個(gè)條目后面的鏈接列表。
進(jìn)攻思路
現(xiàn)在我們知道了java.util.Hashtable和java.util.HashMap背后的實(shí)現(xiàn)細(xì)節(jié)，我們可以回到稱為HashDoS的攻擊。 該攻擊實(shí)現(xiàn)了Crosby，SA，Wallach，DS的想法： 通過算法復(fù)雜性攻擊拒絕服務(wù)。 在：關(guān)于USENIX安全研討會(huì)的第12屆會(huì)議論文集–第12卷，USENIX協(xié)會(huì)（2003）
總結(jié)一下：散列索引的數(shù)據(jù)結(jié)構(gòu)會(huì)因引發(fā)不利的狀態(tài)而大大減慢速度。 理想的哈希索引數(shù)據(jù)結(jié)構(gòu)如下所示：
在這種情況下，使用具有不同哈希值的關(guān)鍵字更改，刪除或添加數(shù)據(jù)的時(shí)間幾乎是恒定的。 通過使用關(guān)鍵字的哈希值作為索引，可以輕松找到位置，并且無需迭代列表即可立即顯示數(shù)據(jù)。
讓我們看一下哈希索引數(shù)據(jù)結(jié)構(gòu)的另一種不利狀態(tài)：
像這樣的結(jié)構(gòu)，CRUD操作的恒定時(shí)間已經(jīng)結(jié)束了……
這會(huì)大大減慢處理線程的速度。 一個(gè)非常快的數(shù)據(jù)結(jié)構(gòu)已經(jīng)變成了一個(gè)鏈表，并帶有額外的開銷（計(jì)算哈希值）。 散列索引數(shù)據(jù)結(jié)構(gòu)的所有好處都將被抹去。 好像還不夠糟糕，大多數(shù)哈希索引數(shù)據(jù)結(jié)構(gòu)都啟用了稱為重新哈希的功能。 當(dāng)數(shù)據(jù)結(jié)構(gòu)超過定義的負(fù)載（例如在Java中為75％）時(shí)，出于優(yōu)化原因重新整理表。 大多數(shù)情況下，絕對(duì)希望使用此功能，但在這種特殊情況下，它甚至?xí)p慢整個(gè)過程。
利用問題
要利用此行為，有必要計(jì)算一大堆沖突關(guān)鍵字。 例如，如果我們假設(shè)關(guān)鍵字的類型為java.lang.String ，我們可以看一下其hashCode （）函數(shù)：
public int hashCode() { int h = hash; if (h == 0) { int off = offset; char val[] = value; int len = count; for (int i = 0; i < len; i++) { h = 31*h + val[off++]; } hash = h; } return h; } 這似乎是DJ Bernstein設(shè)計(jì)的功能DJBX33A的自定義版本，可以在其中輕松發(fā)現(xiàn)沖突。
該函數(shù)具有一個(gè)有趣的屬性，將在以下示例中進(jìn)行演示：
我們看到碰撞值的串聯(lián)再次導(dǎo)致碰撞值。 我們可以繼續(xù)做下去，并獲得大量碰撞關(guān)鍵字。 這使查找沖突比單純的暴力破解更加容易。
我們針對(duì)本地Web服務(wù)對(duì)此進(jìn)行了測(cè)試，并且可以通過使用沖突關(guān)鍵字作為標(biāo)記屬性來顯著降低正在運(yùn)行的Web應(yīng)用程序服務(wù)器的速度。
我不確定是否確實(shí)可能使計(jì)算機(jī)崩潰，或者是否存在某種非顯而易見的機(jī)制來防止服務(wù)器自行殺死（我們尚未在服務(wù)器端研究處理代碼），但是可以肯定地阻止服務(wù)器在可接受的時(shí)間內(nèi)正常運(yùn)行。 對(duì)Web服務(wù)的請(qǐng)求很容易被延遲。
也許我會(huì)在不久的將來付出一些努力來收集測(cè)量數(shù)據(jù)（#colliding keys –系統(tǒng)響應(yīng)時(shí)間）。 如果我這樣做，您將在此博客上找到數(shù)據(jù)…
帶你去的拐角點(diǎn)
- 永遠(yuǎn)不要單獨(dú)依賴hashCode() –容易出錯(cuò)
- 避免像
if(password.hashCode() == referencePassword.hashCode()) {
return godMode; - 在決定/反對(duì)數(shù)據(jù)類型/結(jié)構(gòu)時(shí)，花幾秒鐘的時(shí)間在實(shí)現(xiàn)細(xì)節(jié)上
- 篩選傳入的數(shù)據(jù)–裁剪其大小，拒絕超長(zhǎng)參數(shù)等。
- 小心，并始終注意編碼最佳實(shí)踐！
進(jìn)一步有趣的觀點(diǎn)
在此示例中，我們使用java.lang.String作為關(guān)鍵字對(duì)象。 有趣的是還可以使用什么，以及在JRE代碼或大量使用的項(xiàng)目中，沖突的哈希值在何處用于數(shù)據(jù)結(jié)構(gòu)或什至更壞的目的。
可以看看Object.hashCode （）是如何實(shí)現(xiàn)的（它是本機(jī)代碼）–這將是一個(gè)不錯(cuò)的目標(biāo)，因?yàn)樗衅渌麑?duì)象都擴(kuò)展了該基類。 如果擴(kuò)展類沒有覆蓋hashCode （）函數(shù)，而是依賴于正確的，無沖突的輸出，則這對(duì)于更復(fù)雜的攻擊可能很有用。 考慮一下如果序列化依賴于相應(yīng)的代碼會(huì)發(fā)生什么……。
如果有人已經(jīng)知道一些脆弱的地方，請(qǐng)告訴我們！ 我們非常有興趣，但是由于時(shí)間有限，無法達(dá)到我們想要的深度。
謝謝
我要再次感謝Juraj Somorovsky所做的豐富的聯(lián)合研究工作！ 此外，我們還要感謝oCERT團(tuán)隊(duì)的Andrea Barisani和紅帽安全響應(yīng)團(tuán)隊(duì)的 Vincent Danen ，他們與我們討論了這個(gè)問題！
參考：從我們的JCG合作伙伴處 調(diào)查HashDoS問題 ? Java安全和相關(guān)主題博客中的Christopher Meyer。
翻譯自: https://www.javacodegeeks.com/2012/02/investigating-hashdos-issue.html
hashdos
總結(jié)
以上是生活随笔為你收集整理的hashdos_调查HashDoS问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 书评– Kubernetes Up＆Ru
- 下一篇： 网络游戏备案查询（网游备案查询）