為什么，如何防止在 Java 中應(yīng)用？

哈希泛濫攻擊是網(wǎng)絡(luò)安全中最重要的攻擊之一——也是區(qū)分軟件工程師和安全工程師思維方式的直觀方式。 為什么要進(jìn)行哈希泛洪攻擊？

哈希泛洪攻擊是拒絕服務(wù)攻擊。一旦后端接口出現(xiàn)漏洞，整個服務(wù)器將停止服務(wù)。 我們所說的“脆弱性”是什么？ 不得不提

Hash

，這種簡單的數(shù)據(jù)結(jié)構(gòu)幾乎每個軟件都實現(xiàn)了。人們選擇它是因為它具有超快的查找時間：平均

O(1)

和最壞情況下的

O(n)

。

哈希表的最壞時間復(fù)雜度為 O(n)，原因有二：

1. 如果太多元素散列到同一個鍵中：查看這個鍵內(nèi)部可能需要 O(n) 時間。

2. 一旦哈希表通過了它的負(fù)載平衡——它必須重新哈希[創(chuàng)建一個新的更大的表，并將每個元素重新插入到表中]。

這意味著，當(dāng)我們要不斷地向哈希表中插入n個元素時，如果鍵沒有相同的哈希值，則需要大約O(n)的時間；但是如果鍵的哈希值不斷地發(fā)生沖突，

最壞情況將花費大約 O(n^2) 時間

，這使得平均運行時間和最壞情況運行時間彼此非常不同。 這就是為什么 Scott A. Crosby 和 Dan S. Wallach 在 2003 年提出了一個想法，即如果存在一種方法可以利用這種數(shù)據(jù)結(jié)構(gòu)的漏洞（最壞情況復(fù)雜度）手動創(chuàng)建最壞情況的設(shè)想。 java.lang.String.hashCode()

此方法返回此字符串的哈希碼。 String 對象的哈希碼計算如下：

s[0]*31^(n - 1) + s[1]*31^(n - 2) + ... + s[n - 1]

使用int算法，其中s[i]是字符串的第i個字符，n是字符串的長度，^表示求冪。 （空字符串的哈希值為零。）

使用這個算法，我們可以很容易地創(chuàng)建一組具有相同散列值的字符串。一旦交給服務(wù)器做哈希表，服務(wù)器就會用這種廉價的方法宕機(jī)。 2011年的一項實驗表明，攻擊 Tomcat 服務(wù)器只需6KB/s就可以并行化 Intel i7 處理器； 1GB/s 并行化 100000 個 Intel i7 處理器；這使得散列泛洪攻擊成為一種更經(jīng)濟(jì)有效的 DOS 攻擊方式。

如何預(yù)防？

現(xiàn)在我們已經(jīng)為攻擊者進(jìn)行散列泛洪攻擊建立了條件：了解

算法的所有細(xì)節(jié)

，這樣他們就可以很容易地制作出一組沖突的密鑰。 所以，如果我們讓攻擊者無法完全使用算法呢？ 現(xiàn)在我們可以引入

Hash Seed

，它是每次創(chuàng)建哈希表時隨機(jī)生成的秘密參數(shù)。使用這種哈希種子的哈希算法稱為

Keyed Hash Function

。 迄今為止，許多研究機(jī)構(gòu)和組織已經(jīng)設(shè)計了新的哈希函數(shù)，例如：

SipHash, MurmurHash, CityHash …

CTF：哈希沖突

在 CTF 中，哈希沖突是指兩段數(shù)據(jù)或文本具有相同的加密哈希。這是非常罕見的。碰撞的重要之處在于它們可用于破解密碼哈希。密碼通常以散列形式存儲在計算機(jī)上，因為很難從散列中獲取密碼。 參考

Scott A. Crosby and Dan S. Wallach. 2003. Denial of service via algorithmic complexity attacks. In Proceedings of the 12th conference on USENIX Security Symposium - Volume 12 (SSYM’03), Vol. 12. USENIX Association, Berkeley, CA, USA, 3-3.

!(Hash table runtime complexity (insert, search and delete))https://stackoverflow.com/questions/9214353/hash-table-runtime-complexity-insert-search-and-delete

Hash-flooding DoS - isdanni (https://isdanni.com/hash-flooding/#javalangstringhashcode)

結(jié)束，感謝大家閱讀

翻譯：阿曜ちゃん