cryptography - SHA-1 密码存储安全吗？

Question

结论: SHA-1 与抵御原像攻击一样安全，但它易于计算，这意味着更容易进行暴力破解或字典攻击。 (对于 SHA-256 等后继者也是如此。)根据情况，设计为计算成本高的哈希函数(例如 bcrypt)可能是更好的选择。

有些人经常抛出诸如“SHA-1 已损坏”之类的言论，因此我试图了解这究竟意味着什么。让我们假设我有一个 SHA-1 密码哈希数据库，一个拥有最先进的 SHA-1 破解算法和一个拥有 100,000 台机器的僵尸网络的攻击者可以访问它。 (控制 10 万台家用计算机意味着他们每秒可以执行大约 10^15 次操作。)他们需要多少时间

找出任何一个用户的密码？

找出给定用户的密码？

找出所有用户的密码？

找到一种以用户身份登录的方法？

找到一种以特定用户身份登录的方法？

如果密码被加盐，那会如何改变？加盐的方法(前缀、后缀、两者或更复杂的东西，如异或)是否重要？

这是我目前的理解，经过一些谷歌搜索。如果我误解了什么，请在答案中更正。

如果没有盐，彩虹攻击会立即找到所有密码(除了极长的密码)。

如果有足够长的随机盐，找出密码的最有效方法是蛮力或字典攻击。碰撞和原像攻击都无助于找出实际密码，因此针对 SHA-1 的加密攻击在这里无济于事。使用什么算法甚至无关紧要 - 甚至可以使用 MD5 或 MD4，并且密码同样安全(存在细微差别，因为计算 SHA-1 哈希值较慢)。

为了评估“同样安全”的安全性，我们假设单个 sha1 运行需要 1000 次操作，并且密码包含大写、小写和数字(即 60 个字符)。这意味着攻击者每天可以测试 1015*60*60*24/1000 ~= 1017 个潜在密码。对于蛮力攻击，这意味着在 3 小时内测试最多 9 个字符、一周最多 10 个字符、一年最多 11 个字符的所有密码。 (每增加一个字符需要 60 倍的时间。)字典攻击要快得多(即使攻击者使用一台计算机也可以在数小时内完成)，但只能找到弱密码。

以用户身份登录，攻击者不需要找出确切的密码；找到一个产生相同散列的字符串就足够了。这称为第一原像攻击。据我所知，没有针对 SHA-1 的原像攻击。 (蛮力攻击需要 2160 次操作，这意味着我们的理论攻击者需要 1030 年才能成功。理论上可能性的限制是大约 260 次操作，攻击需要几年时间。)有 preimage attacks against reduced versions of SHA-1影响可以忽略不计(对于使用 44 步而不是 80 步的简化 SHA-1，攻击时间从 2160 次操作减少到 2157 次)。存在针对 SHA-1 的碰撞攻击，这在理论上是可能的(the best I found 将时间从 280 降低到 252)，但即使没有加盐，这些对密码哈希也无用。

简而言之，使用 SHA-1 存储密码似乎非常安全。我错过了什么吗？

更新: Marcelo 指出一篇文章提到 a second preimage attack in 2¹⁰⁶ operations . (编辑:作为 Thomas explains ，这种攻击是一个假设性的构造，不适用于现实生活场景。)不过，我仍然不明白这对使用 SHA-1 作为 key 推导函数有何危险。通常是否有充分的理由认为碰撞攻击或第二次原像攻击最终可以变成第一次原像攻击？

Answer 1

对您的问题的简短回答是:SHA-1 尽可能安全。 MD5 也可以，即使是 MD4；但这可能会让一些投资者感到紧张。对于公共(public)关系，最好使用“更好”的哈希函数，例如SHA-256，即使您将其输出截断为 160 或 128 位(以节省存储成本)。部分SHA-3 round-2 candidates似乎比 SHA-1 更快，同时可以说“更安全”；但它们仍然有点新，因此现在坚持使用 SHA-256 或 SHA-512 将是更安全的途径。这会让你看起来很专业和谨慎，这很好。

请注意，“尽可能安全”与“完全安全”不同。有关相当冗长的解释，请参见下文。

关于已知攻击:

对 MD4、MD5 和 SHA-1 的已知攻击与碰撞有关，不会影响原像抵抗力。已经证明 MD4 有一些弱点，在尝试破解 HMAC/MD4 时可以(仅在理论上)利用这些弱点，但这不适用于您的问题。 Kesley 和 Schneier 的论文中的 2106 秒原像攻击是一种通用的权衡，它仅适用于非常长的输入(260 字节；即 100 万兆兆字节——请注意 106+60 如何超过 160；这就是您看到交易-off 没有任何魔法)。

此消息的其余部分假定您使用的哈希函数(例如 SHA-1)是一个“黑匣子”，没有攻击者可能使用的特殊属性。即使使用“损坏的”散列函数 MD5 和 SHA-1，这就是您现在所拥有的。

关于彩虹表:

“彩虹攻击”实际上是字典或蛮力攻击的成本分摊。它是 time-memory trade-off 的衍生物Hellman 于 1980 年首次描述。假设您有 N 个可能的密码(这是您的字典的大小，如果您考虑使用 n 位输出对哈希函数进行暴力破解，则为 2n)，存在一种分时攻击，其中您预先计算了 N 个散列密码并将它们存储在一个大表中。如果对散列输出进行排序，则可以通过一次查找获得密码。彩虹 table 是一种巧妙的方式来存放 table ，空间大大减少。您只存储 N/t 个散列密码，并使用 O(t2) 查找破解密码。彩虹表允许您虚拟处理比实际存储的表大得多的预计算表。

然而，无论彩虹与否，攻击者仍然必须至少进行一次全面攻击。这可以看作是几个连续的优化层:

蛮力/字典攻击花费 N 来破解每个密码。

使用预先计算好的表格，攻击者支付 N 的费用一次 然后可以攻击许多 每个密码的额外成本非常低。

如果预先计算的表是彩虹表，那么N可以大一些，因为存储成本降低了。 N 上的瓶颈成为攻击者可以集结的 CPU 能力，而不是他的硬盘大小。

如果 N 足够大，以至于散列 N 个密码的 CPU 成本是可笑的，那么无论是否使用彩虹表，这种攻击都不可行。这意味着具有 80 位或更多输出的(抗原像的)散列函数足以使蛮力攻击不可行。

关于盐:

盐是一种击败预计算的方法。在上面的描述中，salt 将攻击者带回到第 1 步:salting 防止攻击者在多个被攻击的密码之间共享 O(N) 成本。预先计算的表，更不用说彩虹表，不再可行。

你想要加盐是因为当散列数据包含在密码中时，即适合随机人类大脑的东西，那么 N 可能非常低:人类在选择和记住密码方面非常糟糕。这就是“字典攻击”的含义:假设许多用户密码将位于该特别选择的空间中，从而使用减少的潜在密码空间(“字典”)。

因此，加盐至少会阻止攻击者使用预先计算的表，特别是预先计算的彩虹表。这假设攻击者能够破解一两个密码；我们不希望他以很少的额外开销破解其他 1000 个密码。

此外，腌制有利于公共(public)关系。

关于 SHA-1 成本:

SHA-1 的基本成本是对 64 字节块进行散列。这就是 SHA-1 的工作原理:填充数据，然后拆分为 64 字节的块。在 Intel Core2 系统上处理单个块的成本大约为 500 个时钟周期，这是单核的。 MD5 和 MD4 更快，分别计算大约 400 和 250 个周期。不要忘记，大多数现代 CPU 都有多个内核，因此要相应地增加。

一些盐腌计划规定了大量的盐；例如进入散列函数的实际上是单个 128 位盐的 40000 个连续副本，然后是密码本身。这使得密码散列对于合法用户和攻击者来说都更加昂贵(在我的示例中是 10000 倍)。这是否是一个好主意取决于设置。对于在桌面系统上登录，这很好:用户甚至不会注意到散列密码需要 10 毫秒，而不是 1 微秒；但是攻击者的成本增加了非常明显的 10000 倍。在每秒有数千个客户端的共享服务器上，总成本可能会变得过高。从概念上讲，将合法用户和攻击者的标准提高相同的因素最终并不是很好的安全性；但在某些特定情况下，这可能是一个有值(value)的想法。

关于网络攻击:

以上所有内容都是关于击败离线攻击。离线攻击是攻击者拥有“测试”密码所需的所有数据的攻击；例如攻击者可以获得包含散列密码的数据库副本。在离线攻击中，攻击者仅受其计算资源的限制。相反，在线攻击是一种攻击，其中攻击者的每次猜测都必须经过诚实的验证者(例如，攻击者只是尝试登录被攻击的系统)。通过强制限制每秒可以尝试的密码数量来阻止在线攻击。极端的例子是在三个错误的 PIN 后关闭的智能卡。

通常，为了密码安全，安排系统不让攻击者构建离线攻击的返回要高得多。这就是 Unix 系统所做的:散列密码，它曾经是世界可读的 /etc/password文件，现在在 /etc/shadow除少数特权应用程序外，该文件不受读取访问保护。这里的假设是，如果攻击者可以读取 /etc/shadow ，那么他可能对系统有足够的控制权，他真的不再需要密码了......