如果暴力搜索密码返回冲突而不是密码,这有关系吗?

信息安全 哈希 蛮力 密码破解
2021-08-16 22:29:43

假设以下非常基本的散列算法。

h(k) = k mod 17

假设我们12345为使用这种非常基本的散列算法的网站创建了一个密码。这将产生 3 的哈希值。

假设一个蛮力攻击者过来并开始猜测从 1 开始的数字,他们只需要在遇到哈希冲突之前达到 3,显然 3 不是原始密码。

是密码散列空间(0-16)比允许密码的空间小得多的问题,还是我忽略了其他问题?

4个回答

Steffen 的回答完美地涵盖了这一点,但我只想添加更多细节。

任何能匹配的东西通常都很好

正如他所说,您通常不关心找到实际密码,因为许多应用程序很乐意使用恰好与存储在数据库中的哈希值散列的任何字符串对您进行身份验证。这对于 Web 应用程序最常见,但在其他情况下可能不太常见这意味着,如果您执行蛮力搜索并找到具有相同哈希值的内容,即使它实际上不是相同的密码,您也可以登录该帐户。正如问题中所暗示的那样,这是散列的本质,是鸽巢原理的直接结果。

直到您需要实际密码

但是,在某些情况下,您确实希望找到原始密码。例如,如果黑客从无价值的服务中窃取了用户名/密码,并想尝试以用户身份登录更有价值的服务(Facebook、银行等),就会出现这种情况。由于人们经常在任何地方使用相同的密码,那么在这种情况下,您确实需要原始密码 - 而不仅仅是针对给定散列算法散列到相同值的密码(毕竟,不同的服务可能使用不同的散列方法,而且大多数也是使用加密盐- h/t @Taemyr)。

但区别并不重要

幸运的是(对于我们的攻击者),这并不重要。原因是穷举蛮力实际上是不可能的。相反,黑客会尝试可能是密码的东西(单词列表、常用密码等)。作为一个反例,假设尽管不可能,但您拥有来自 Web 服务的哈希并设法对所有可能的 256 位 ASCII 字符串执行暴力搜索。您会发现三个输入的哈希值与用户的密码哈希值相同:

  1. BD3EDF42F6D3AF2DAAE93313EB534
  2. 7AF7B8B8F84443872C48EC372DBD1
  3. password

你猜哪个是实际密码?答案显然是#3。我的意思是,从技术上讲,用户碰巧选择了一个非常强的密码(即BD3EDF42F6D3AF2DAAE93313EB534),该密码恰好与 哈希值相同password,但这种可能性实际上为零。

从这个意义上说,攻击者具有很好的优势。他们更愿意找到实际的密码,事实证明,因为人们不善于选择随机密码,所以最好的方法不是检查所有内容——而是检查看起来像密码的东西。这使得蛮力搜索变得非常、非常、非常、更加有效,并且还为攻击者提供了更有用的结果(实际密码,而不是碰巧具有相同哈希值的随机字符串)。

暴力破解的主要目标不是获取原始密码,而是获取有效的密码。因此,只要找到的密码不是原始密码,只要它有效,这并不重要。

尽管基于通用密码字典和典型修改的高效智能暴力破解很可能生成的密码实际上是真实的。这仅仅是因为大多数用户不使用长随机密码,而是使用经过典型修改的普通密码,因此在进行智能暴力破解时将首先找到真正的密码。

如果暴力搜索密码返回冲突而不是密码,这有关系吗?

还有其他答案很好地解决了这个问题,所以我将探索一个不同的角度:没关系,因为蛮力搜索不太可能找到冲突而不是原始密码。

假设:

假设我们的密码是“password”,它有八个字符。1 到 8 个字符之间的字母数字密码数量约为 2.219e+14。

假设最大密码长度为 10。在 9 到 10 个字符之间,有 8.528e+17 个密码,大约是 1 到 8 个之间的 3800 倍。即使我们假设有五次冲突,所有五个都比我们的“密码”长的可能性约为 99.9%。

我用于最大密码长度的数字(希望)比通常使用的数字小得多,并且冲突的数量被大大高估了。实际上,不会发生比实际密码短的冲突。

在实践中使用的任何散列算法都应该有一个无法暴力破解的密钥空间。另一方面,实际密码的设置要有限得多,因此攻击者不会搜索所有可能的密码,而只会搜索真实用户使用的密码。

现在,如果您有一个好的密码,并且攻击者进行了蛮力攻击,那么不同的密码具有相同的哈希值并非不可能。如果散列的密钥空间只有 64 位,那么在数十亿个密码中,您可以预期其中两个具有相同的散列码。因此,攻击者找到具有相同哈希值的不同密码并非不可能(平均检查 2^64 个密码后)。两者都可以让攻击者获得服务。实际上,散列算法应该有更大的密钥空间,没有人会找到具有相同散列的不同密码。

找到该替代密码可让您登录服务。但是大多数攻击者明确地想要密码,因为他们对某些不重要的服务不感兴趣,而是希望您将相同的密码用于其他服务。因此,除非另一个服务使用完全相同的哈希算法和完全相同的盐,否则备用密码对他们来说将完全没有用。