哈希洪水 DOS

为什么，如何防止在 Java 中应用？

哈希泛滥攻击是网络安全中最重要的攻击之一——也是区分软件工程师和安全工程师思维方式的直观方式。 为什么要进行哈希泛洪攻击？

哈希泛洪攻击是拒绝服务攻击。一旦后端接口出现漏洞，整个服务器将停止服务。 我们所说的“脆弱性”是什么？ 不得不提

Hash

，这种简单的数据结构几乎每个软件都实现了。人们选择它是因为它具有超快的查找时间：平均

O(1)

和最坏情况下的

O(n)

。

哈希表的最坏时间复杂度为 O(n)，原因有二：

1. 如果太多元素散列到同一个键中：查看这个键内部可能需要 O(n) 时间。

2. 一旦哈希表通过了它的负载平衡——它必须重新哈希[创建一个新的更大的表，并将每个元素重新插入到表中]。

这意味着，当我们要不断地向哈希表中插入n个元素时，如果键没有相同的哈希值，则需要大约O(n)的时间；但是如果键的哈希值不断地发生冲突，

最坏情况将花费大约 O(n^2) 时间

，这使得平均运行时间和最坏情况运行时间彼此非常不同。 这就是为什么 Scott A. Crosby 和 Dan S. Wallach 在 2003 年提出了一个想法，即如果存在一种方法可以利用这种数据结构的漏洞（最坏情况复杂度）手动创建最坏情况的设想。 java.lang.String.hashCode()

此方法返回此字符串的哈希码。 String 对象的哈希码计算如下：

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

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

使用这个算法，我们可以很容易地创建一组具有相同散列值的字符串。一旦交给服务器做哈希表，服务器就会用这种廉价的方法宕机。 2011年的一项实验表明，攻击 Tomcat 服务器只需6KB/s就可以并行化 Intel i7 处理器； 1GB/s 并行化 100000 个 Intel i7 处理器；这使得散列泛洪攻击成为一种更经济有效的 DOS 攻击方式。

如何预防？

现在我们已经为攻击者进行散列泛洪攻击建立了条件：了解

算法的所有细节

，这样他们就可以很容易地制作出一组冲突的密钥。 所以，如果我们让攻击者无法完全使用算法呢？ 现在我们可以引入

Hash Seed

，它是每次创建哈希表时随机生成的秘密参数。使用这种哈希种子的哈希算法称为

Keyed Hash Function

。 迄今为止，许多研究机构和组织已经设计了新的哈希函数，例如：

SipHash, MurmurHash, CityHash …

CTF：哈希冲突

在 CTF 中，哈希冲突是指两段数据或文本具有相同的加密哈希。这是非常罕见的。碰撞的重要之处在于它们可用于破解密码哈希。密码通常以散列形式存储在计算机上，因为很难从散列中获取密码。 参考

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)

结束，感谢大家阅读

翻译：阿曜ちゃん