57

这是Java中的一个算法：

public String getHash(String password, String salt) throws Exception {
    String input = password + salt;
    MessageDigest md = MessageDigest.getInstance(SHA-512);
    byte[] out = md.digest(input.getBytes());
    return HexEncoder.toHex(out);
}

假设盐是已知的。我想知道当密码是字典单词以及不是字典单词时暴力破解的时间。

4

3 回答 3

122

在您的情况下，破坏哈希算法等同于在哈希算法中发现冲突。这意味着您不需要找到密码本身（这将是原像攻击），您只需要找到与有效密码的哈希值相等的哈希函数的输出（因此是“冲突”）。使用生日攻击发现碰撞需要 O(2^(n/2)) 时间，其中 n 是散列函数的输出长度（以位为单位）。

SHA-2 的输出大小为 512 位，因此发现冲突需要 O(2^256) 时间。鉴于对算法本身没有巧妙的攻击（目前尚无针对 SHA-2 哈希家族的攻击），这就是破解算法所需要的。

感受一下 2^256 的实际含义：目前认为（整个！！！）宇宙中的原子数大约是 10^80，也就是大约 2^266。假设输入 32 字节（这对您的情况来说是合理的 - 20 字节盐 + 12 字节密码）我的机器需要 ~0,22s (~2^-2s) 进行 65536 (=2^16) 计算。所以 2^256 计算将在 2^240 * 2^16 计算中完成，这需要

2^240 * 2^-2 = 2^238 ~ 10^72s ~ 3,17 * 10^64 years

甚至称这为数百万年也是荒谬的。使用地球上最快的硬件并行计算数千个哈希值并没有变得更好。没有任何人类技术能够将这个数字压缩成可以接受的数字。

所以在这里忘记暴力破解 SHA-256。你的下一个问题是关于字典单词的。传统上使用彩虹表来检索这种弱密码。彩虹表通常只是一个预先计算的哈希值的表，其想法是，如果您能够预先计算并存储每个可能的哈希及其输入，那么查找给定哈希并检索一个给定的哈希需要 O(1)它的有效原像。当然这在实践中是不可能的，因为没有存储设备可以存储如此大量的数据。这种困境被称为内存时间权衡. 由于您只能存储这么多值，因此典型的彩虹表包括某种形式的哈希链和中间缩减函数（这在 Wikipedia 文章中有详细说明），以通过节省一些时间来节省空间。

盐是使这种彩虹表不可行的对策。为了阻止攻击者预先计算特定盐的表，建议应用每个用户的盐值。但是，由于用户不使用安全的、完全随机的密码，如果知道 salt 并且您只需在简单的试错方案中迭代一个包含常用密码的大型字典，您仍然可以取得多么成功，这仍然令人惊讶。自然语言与随机性之间的关系用熵表示。典型的密码选择通常具有低熵，而完全随机的值将包含最大熵。

典型密码的低熵使得您的一个用户使用相对较小的常用密码数据库中的密码的可能性相对较高。如果你用谷歌搜索它们，你最终会找到此类密码数据库的种子链接，通常在千兆字节大小的类别中。如果攻击者不受任何限制，那么使用这种工具成功通常在几分钟到几天的范围内。

这就是为什么通常单独散列和加盐是不够的，您还需要安装其他安全机制。您应该使用人为减慢熵诱导方法，例如PKCS#5中描述的 PBKDF2，并且您应该在给定用户重新尝试输入密码之前强制等待一段时间。一个好的方案是从 0.5 秒开始，然后将每次失败尝试的时间加倍。在大多数情况下，用户不会注意到这一点，并且平均失败的次数不会超过 3 次。但它会显着减缓任何试图攻击您的应用程序的恶意外来者。

于 2011-07-21T21:30:51.513 回答
35

我想知道当密码是字典单词以及不是字典单词时暴力破解的时间。

字典密码

大致数字：大约有 1,000,000 个英文单词，如果黑客每秒可以计算大约 10,000 个 SHA-512 哈希（更新：参见 CodesInChaos 的评论，这个估计非常低），1,000,000 / 10,000 = 100 秒。因此，破解单个用户的单字字典密码只需要一分钟多的时间。如果用户连接两个字典单词，你就在几天的范围内，但如果攻击者足够关心的话，仍然很有可能。不仅如此，它开始变得艰难。

随机密码

如果密码是真正随机的字母数字字符序列，大写和小写，那么长度为 N 的可能密码的数量为 60^N（有 60 个可能的字符）。这次我们从另一个方向进行计算；我们会问：给定特定的时间长度，我们可以破解多长的密码？只需使用以下公式：

N = Log60(t * 10,000)其中 t 是以秒为单位计算散列所花费的时间（再次假设每秒 10,000 个散列）。

1 minute:    3.2
5 minute:    3.6
30 minutes:  4.1
2 hours:     4.4
3 days:      5.2

因此，给定 3 天的时间，如果密码长度为 5 个字符，我们将能够破解密码。

这一切都很简单，但你明白了。更新：请参阅下面的评论，实际上可以破解比这更长的密码。

这里发生了什么？

让我们澄清一些误解：

  • salt 不会让计算哈希变慢，它只是意味着他们必须单独破解每个用户的密码，并且预先计算的哈希表（流行词：彩虹表）完全没用。如果您没有预先计算的哈希表，并且您只破解一个密码哈希，那么加盐没有任何区别。

  • SHA-512 的设计并非难以破解。更好的散列算法（如BCrypt、PBKDF2 或 SCrypt）可以配置为需要更长的计算时间，而普通计算机可能每秒只能计算 10-20 个散列。如果您还没有，请阅读有关密码哈希的出色答案。

  • 更新：正如 CodesInChaos 在评论中所写，如果使用正确的硬件来计算 SHA-512 哈希，即使是高熵密码（大约 10 个字符）也可能被暴力破解。

接受答案的注意事项：

截至 2014 年 9 月，公认的答案是不正确且危险的错误：

在您的情况下，破坏哈希算法等同于在哈希算法中发现冲突。这意味着您不需要查找密码本身（这将是原像攻击）...使用生日攻击查找冲突需要 O(2^n/2) 时间，其中 n 是哈希的输出长度位的功能。

生日攻击与破解给定的哈希完全无关。这实际上是原像攻击的完美例子。该公式和接下来的几段导致攻击时间的值非常高且完全没有意义。如上所示，完全有可能在几分钟内破解加盐字典密码。

典型密码的低熵使得您的一个用户使用相对较小的常用密码数据库中的密码的可能性相对较高......

这就是为什么通常单独散列和加盐是不够的，您还需要安装其他安全机制。您应该使用人为减慢熵诱导方法，例如 PKCS#5 中描述的 PBKDF2 ...

是的，请使用计算速度慢的算法，但什么是“熵诱导”？通过散列放置低熵密码不会增加熵。它应该保留熵，但你不能用散列更好地制作垃圾密码，它不是那样工作的。通过 PBKDF2 输入的弱密码仍然是弱密码。

于 2014-09-24T22:12:20.207 回答
8

这个问题没有一个单一的答案，因为变量太多，但是 SHA2 还没有真正破解（参见：加密哈希函数的生命周期），所以它仍然是一个很好的算法来存储密码。 salt 很好，因为它可以防止字典攻击或彩虹表的攻击。盐的重要性在于它对于每个密码应该是唯一的。存储散列密码时，您可以使用 [128-bit salt][512-bit password hash] 之类的格式。

唯一可行的攻击方法是实际计算不同可能性密码的哈希值，并最终通过匹配哈希值找到正确的密码。

为了说明一秒钟可以完成多少哈希，我认为比特币是一个不错的例子。比特币使用 SHA256，简而言之，你生成的哈希越多，你获得的比特币就越多（你可以用这些比特币换取真钱），因此人们有动力为此目的使用 GPU。您可以在硬件概览中看到，平均只需 150 美元的显卡可以计算超过 2 亿次哈希/秒。您的密码越长越复杂，所需的时间就越长。以 200M/s 的速度计算，尝试 8 个字符的字母数字（大写、小写、数字）的所有可能性大约需要 300 小时。如果密码是符合条件的或常见的英文单词，则实时时间很可能会减少。

因此，您需要在上下文中查看任何安全性。攻击者的动机是什么？什么样的应用程序？为每个哈希使用随机盐可以很好地防止诸如数千个密码被泄露的情况。

您可以做的一件事是通过减慢散列过程来添加额外的蛮力保护。由于您只对密码进行一次哈希处理，而攻击者必须多次这样做，这对您有利。典型的做法是获取一个值，对其进行散列，获取输出，再次对其进行散列等等，以进行固定数量的迭代。例如，您可以尝试 1,000 或 10,000 次迭代。这将使攻击者找到每个密码的速度要慢很多倍。

于 2011-07-21T20:50:52.327 回答