調查HashDoS問題

近一個月前，我就如何在不與供應商互動的情況下臨時解決 28C3上出現的HashDoS問題或其他代碼缺陷發表了一些想法。

現在是時候更深入地研究復雜性攻擊并查看來源了。我完全假設java.util.HashMap和java.util.Hashtable是受此攻擊影響的最常用的Java數據結構，因此本文僅將代碼集中在這些類型的后面。

哈希函數和索引數據結構的簡要介紹

哈希索引數據結構因其簡單的用法和優點而非常受歡迎：

無需打擾索引表即可找到所需數據的正確位置
通過使用關鍵字而不是索引號訪問數據
添加或刪除操作的時間幾乎恒定

為了獲得這些好處，哈希索引數據結構遵循有關如何對數據進行索引的聰明思想。索引是通過散列與背后數據關聯的關鍵字來計算的。考慮以下示例，這是一個類似于代碼的簡單示例：

myHashIndexedDataStructure [hash（keyword）] =特定數據

聽起來很完美，但是它有一個主要缺點：在大多數情況下，使用的哈希函數不是加密函數。

根據Wikipedia的說法，函數自行調用哈希函數的唯一強制特征是

“將可變長度的大型數據集（稱為鍵）映射到固定長度的較小數據集”

與稱自己為密碼哈希函數（再次是來自Wikipedia的定義）相反，它必須滿足更多，甚至更強大的要求：

”

計算任何給定消息的哈希值很容易（但不一定很快）
生成具有給定哈希值的消息是不可行的
在不更改哈希值的情況下修改消息是不可行的
找到兩個具有相同哈希值的不同消息是不可行的

”
長話短說，讓我們總結一下我們學到的知識以及用這些知識得出的結論：

哈希索引數據結構利用哈希函數
哈希函數不一定是抗沖突的，只要它們不是加密的
缺乏抗沖突性意味著可以輕松計算具有相同哈希值的多個值

如果關鍵字沖突，則哈希索引數據結構需要某種計劃b）–一種后備算法–關于如何處理具有相同關鍵字哈希值的多個數據集。

實際上，有幾種可行的方法：

探測（轉移到固定或可計算的間隔）
多重哈希
條目鏈接（沖突條目的構建列表）
覆蓋現有條目

以下哪種策略需要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; 
}

可以看出，此類使用鍵對象（ 關鍵字 ）的hashCode （）函數來計算哈希值。它遵循ANDing（＆運算符），為了將其正確表示為Integer，MODULO（％運算符），將表大小（建立循環環結構：（table.length + 1）mod table.length？1，除以余數）始終解決標簽 []中的條目。
此后，將考慮所有條目（-ies）并檢查哈希值是否相同以及對象本身是否相同。 if -clause防止存儲同一對象的多個實例–舊的實例僅由新的實例替換。

如果在key.hashCode （）標識的當前位置上找不到相同的對象（關于哈希值和equals （）方法），則將創建一個新的Entry，將其放置在當前位置并在該位置處理舊的Entry對象。
到目前為止，看起來java.util.Hashtable在每個tab []之后都使用某種列表作為數據結構。

查看私有內部類java.util.Hashtable.Entry <K，V>的代碼時，可以確認此假設。

private static class Entry<K,V> implements Map.Entry<K,V> { int hash; K key; V value; Entry<K,V> next;

下一個Entry對象僅指向下一個Entry 。這代表一個定制的鏈表。
java.util.HashMap的代碼更加復雜，并且表現部分不同（允許使用null值，！不同步！），但是基于相同的思想。在這里調查代碼不會發現任何新內容，除了Entry重新被重新實現的事實…）。

兩種實現都依賴于哈希索引數組的每個條目后面的鏈接列表。

進攻思路

現在我們知道了java.util.Hashtable和java.util.HashMap背后的實現細節，我們可以回到稱為HashDoS的攻擊。該攻擊實現了Crosby，SA，Wallach，DS的想法： 通過算法復雜性攻擊拒絕服務。 在：第十二屆USENIX安全研討會的會議記錄–第12卷，USENIX協會（2003）
總結一下：散列索引的數據結構可能會因引發不利的狀態而大大減慢速度。理想的哈希索引數據結構如下所示：

... table[hash(keyA)] = dataA table[hash(keyB)] = dataB table[hash(keyC)] = dataC table[hash(keyD)] = dataD ...

在這種情況下，使用具有不同哈希值的關鍵字更改，刪除或添加數據的時間幾乎是恒定的。通過使用關鍵字的哈希值作為索引，可以輕松找到位置，并且無需迭代列表即可立即顯示數據。
讓我們看一下哈希索引數據結構的另一種不利狀態：

...     hash(keyA) == hash(keyB) == hash(keyC) == hash(keyD)= k table[k] = dataA -> dataB -> dataC -> dataD ...

像這樣的結構，CRUD操作的恒定時間已經結束了……

計算關鍵字的哈希值
遍歷鏈表
比較每個條目的關鍵字（如果它與應用程序正在尋找的關鍵字匹配）

這會大大減慢處理線程的速度。一個非常快的數據結構已變成一個鏈表，并帶有額外的開銷（計算哈希值）。散列索引數據結構的所有好處都將被抹去。好像還不夠糟糕，大多數哈希索引數據結構都啟用了稱為重新哈希的功能。當數據結構超過定義的負載（例如，在Java中為75％）時，出于優化原因，將重新整理表。大多數情況下，絕對希望使用此功能，但在這種特殊情況下，它甚至會減慢整個過程。

利用問題

要利用此行為，必須計算出一大堆沖突關鍵字。例如，如果我們假設關鍵字的類型為java.lang.String ，我們可以看一下其hashCode （）函數：

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設計的功能DJBX33A的自定義版本，可以很容易地發現沖突。
該函數具有一個有趣的屬性，將在以下示例中進行演示：

"0w".hashCode() = 1607 "1X".hashCode() = 1607 "29".hashCode() = 1607 "0w1X".hashCode() = 1545934 "0w29".hashCode() = 1545934 "1X0w".hashCode() = 1545934 "1X29".hashCode() = 1545934 "290w".hashCode() = 1545934 "291X".hashCode() = 1545934 ...

我們看到碰撞值的串聯再次導致碰撞值。我們可以繼續做下去，并獲得大量碰撞關鍵字。這使查找沖突比單純的暴力破解更加容易。

我們針對本地Web服務對此進行了測試，并且可以通過使用沖突關鍵字作為標記屬性來顯著降低正在運行的Web應用程序服務器的速度。
我不確定是否真的可能使計算機崩潰，或者是否存在某種非顯而易見的機制來防止服務器自行殺死（我們尚未在服務器端研究處理代碼），但是可以肯定地阻止服務器在可接受的時間內正常運行。對Web服務的請求很容易被延遲。

也許我會在不久的將來付出一些努力來收集測量數據（#colliding keys –系統響應時間）。如果我這樣做，您將在此博客上找到數據…

帶你去的拐角點

永遠不要只依賴hashCode() –容易出錯
避免像 if(password.hashCode() == referencePassword.hashCode()) { } else {
在決定/反對數據類型/結構時，花幾秒鐘的時間在實現細節上
篩選傳入的數據–裁剪其大小，拒絕超長參數等。
小心，并始終注意編碼最佳實踐！

進一步有趣的觀點

在此示例中，我們使用java.lang.String作為關鍵字對象。有趣的是還可以使用什么，以及在JRE代碼或大量使用的項目中，沖突的哈希值在何處用于數據結構或什至更糟糕的目的。
可以看看Object.hashCode （）是如何實現的（它是本機代碼）–這將是一個不錯的目標，因為所有其他對象都擴展了該基類。如果擴展類沒有覆蓋hashCode （）函數，而是依賴于正確的，無沖突的輸出，則這對于更復雜的攻擊可能很有用。考慮一下如果序列化依賴于相應的代碼會發生什么……。

如果有人已經知道一些脆弱的地方，請告訴我們！我們非常有興趣，但是由于時間有限，無法達到我們想要的深度。

謝謝

我要再次感謝Juraj Somorovsky所做的豐富的聯合研究工作！此外，我們還要感謝oCERT團隊的Andrea Barisani和紅帽安全響應團隊的 Vincent Danen ，他們與我們討論了這個問題！

參考：從我們的JCG合作伙伴處調查HashDoS問題 ? Java安全和相關主題博客中的Christopher Meyer。