如果密码没有设置最大长度,不会发生冲突吗?

信息安全 密码 哈希
2021-08-28 19:01:31

当我考虑在数据库中存储密码哈希时,我突然意识到,如果没有设置哈希密码的最大长度,可能会出现哈希冲突。

我的理解是任何密码都会生成一个固定长度的散列(比如 128 位)。因此,一旦使用了 2 128 + 1 个唯一密码,就会发生冲突(由于鸽巢原理),而从技术上讲,根据哈希算法,冲突发生得更快。

假设在满足 pingeonhole 原则之前不存在冲突,存储近似唯一的密码似乎相当荒谬3.403e+38,所以我可以理解强加密码最大值可能可以忽略不计。

没有设置密码的最大字符数(关于哈希冲突)是否有合理的担忧?

这与这个问题有关正如好奇的家伙所提到的 “哈希冲突的影响不存在”是真的吗?

2个回答

对于初学者来说,散列函数应该基本上是随机的,所以输入字符串的长度并不重要。两个随机的 3 个字符的字符串散列到同一事物的概率与两个随机的 100 个字符的字符串散列相同的概率相同。

对于现代散列函数(SHA1, SHA2, not MD5),它们的结构在数学上足够复杂,我们不能从代数上说太多。此外,可能输入字符串的空间,即使是长度为 32 的字符串,也非常巨大,以至于我们无法通过实验检查所有这些字符串。因此,我们实际上并不知道前 2 128个字符串(二进制表示为1, 10, 11... 2 128的字符串)中有多少冲突理论上应该有一些,但据我所知,我们还没有发现任何SHA1or SHA2因此,您认为将输入字符串的长度限制为小于 2 128位将消除冲突风险的直觉并不完全正确。

在任何情况下,假设前 2 128个字符串中有一对密码具有相同的哈希值,您在数据库中命中一个的概率大约是<number of entries in db>/ 2 128

原因是

“不存在哈希冲突的影响”?

是因为 1/ 2 128是一个小得难以想象的数字,即使你编写了一个程序来生成随机密码,直到太阳耗尽能量,你仍然不会期望看到一次随机的碰撞。(如果有人正在积极尝试进行碰撞攻击,那就另当别论了)。

还要考虑碰撞风险(~ 1/2 128)与标准字典攻击的风险相比如何。根据2013 年 Adob​​e 密码泄露事件,互联网上 68 个帐户中有 1 个使用该密码1234561/68 是一个比 1/2 128大得多的数字,因此单次猜测123456有 1/68 的机会是正确的这一事实比理论上可能的碰撞要担心得多。解决方案:允许(或强制执行)长的非字典密码,为每个密码哈希使用唯一的盐,不要担心冲突。

这里没什么好担心的,但让我们来谈谈其中的一些:

在满足 pingeonhole 原则之前不存在碰撞

不是这种情况。标准散列算法是确定性的(否则它们将不起作用。)将发生冲突的密码(并且有无限数量的密码长度没有限制)。冲突与数据库的大小无关。例如考虑我的新整数散列算法 mod100。实现是你将一个整数乘以 100,得到的余数就是你的哈希值。如果我对数字 101、201 和 301 进行了散列,即使我的集合只有散列空间的 3%,我也有 100% 的冲突率。

因此,可以肯定的是,有人可以猜出与实际密码具有相同哈希值的其他密码之一的可能性很小。如果散列算法是一个好的算法,它更有可能,但是他们会猜出实际的密码。不要为此失眠。