为什么SHA-256 (或任何其他)对于密码来说太快，但是对于碰撞来说却是“慢”的？

Question

通常，不应该使用一组哈希算法(包括SHA-256或更高)存储密码的标准答案是“因为它们是‘快速’散列”，“攻击者可以访问特定的硬件”，等等。

为什么SHA-256 (或者其他一些散列)对于密码来说太快了，但是对于碰撞来说却是“慢”的？提出同样问题的其他方法是:什么时候SHA“慢”到足够有用？为什么攻击者用来破解密码的特殊硬件也不能用来查找SHA冲突呢？

我怀疑答案与密码一般都很小有关。如果是这样的话，问题会变得更准确:使用SHA-256 (例如)的消息的大小是多少？

Answer 1

我怀疑答案与密码一般都很小有关。

不，实际上，答案与密码通常是可预测的有关。这意味着，在哈希函数的所有可能输入中，相对较少的输入更有可能是某人的密码。例如，Password1比act chance past language (使用XKCD漫画方法生成)更有可能是某人的密码，后者比 (用此页生成)更有可能。与随机选择的14字节序列相比，最后一个密码更有可能是某人的密码(这甚至不太可能是可打印的ASCII)。

使密码薄弱的是，某些候选密码比其他密码更有可能使用，这意味着攻击者可以有效地利用此策略：

1. 优先考虑的猜测很可能是密码，而不是不太可能是密码的猜测。
2. 使用专用硬件以非常高的速度完成这个猜测过程。

你可能听说过“字典攻击”这个词，这是第一种非常简单而有效的技术。或者从互联网上下载一个；这一个，它收集“可以在互联网上找到的每个单词列表、字典和密码数据库泄漏”，有1,493,677,782个条目，大约是$2^{30}$。

在抗碰撞场景中，这相当于一个过程，对于我们正在攻击的哈希函数来说，它能够优先排列比其他输入更有可能发生碰撞的输入对。对于像MD5或SHA-1这样的中断哈希函数，有一些关于如何做这类事情的知识，但对于SHA-256则不是这样。考虑到我们的知识状况，我们无法确定搜索的优先级，这样我们就可以尝试更有可能在不太可能发生碰撞的情况下发生碰撞。

由于我们不知道优先搜索的聪明方法，那么，一般数学(生日问题)告诉我们，我们应该花费$2^{128}$猜测找到一个SHA-256碰撞对。这个数字比我上面引用的$2^{30}$条目密码字典要大得多。由于SHA-256比专用密码散列函数快得多，所以您可以测试碰撞对的猜测比测试密码猜测快得多，但绝对没有比$2^{98}快一倍(大约$3乘以10^{29}$)。

Answer 2

如果一个哈希花费2纳秒时间，$2^{42}$哈希计算速度很快--您可以在3小时内完成该操作。但是，如果要尝试$2^{128}$散列，怎么办？即使有10亿倍的计算能力，你仍然需要比我们的宇宙更多的时间来解决这个问题。但是，如果您需要2毫秒来计算一个散列，而不是2纳秒呢？$2^{42}$散列现在将花费278年的时间。对任何实际的攻击者来说都太慢了。

要在SHA-256中发现任何一般冲突，您需要强制执行这些$2^{128}的散列计算，只要您不知道算法本身的任何中断。计算SHA-256的速度相对较快，但你很可能永远也找不到这样的碰撞。另一件事是，如果您只需要为给定的哈希找到正确的密码。如果您知道密码长9个字母，a到z，则为$26^9 \{42}$可能性。正如我对SHA-256所说的那样，用蛮力来逆转是非常快的。假设您采用了一个特殊的密码散列方案，比如PBKDF2或bcrypt，它将哈希的计算时间从2纳秒提高到(例如)1毫秒。计算$2^{42}$散列现在是不可行的。这些算法对于密码和碰撞来说是缓慢的。