SHA-1对密码存储是否安全？

Question

结论: SHA-1和preimage攻击一样安全,但它很容易计算,这意味着更容易安装暴力攻击或字典攻击.(对于像SHA-256这样的后继者也是如此.)根据具体情况,设计成计算成本高的哈希函数(例如bcrypt)可能是更好的选择.

---

有些人会像"SHA-1被打破"那样发表评论,所以我试图理解究竟是什么意思.假设我有一个SHA-1密码哈希的数据库,一个攻击者使用最先进的SHA-1破解算法和一个拥有100,000台机器的僵尸网络可以访问它.(控制超过10万台家用计算机意味着他们每秒可以完成大约10 ^ 15次操作.)他们需要多长时间

1. 找出任何一个用户的密码？
2. 找出给定用户的密码？
3. 找出所有用户的密码？
4. 找到一种以用户身份登录的方法？
5. 找到以特定用户身份登录的方法？

如果密码被腌制,它会如何改变？腌制的方法(前缀,后缀,两者,还是像xor-ing这样复杂的东西)是否重要？

这是我目前的理解,经过一些谷歌搜索.如果我误解了某些内容,请在答案中更正.

• 如果没有盐,彩虹攻击会立即找到所有密码(超长密码除外).
• 如果有足够长的随机盐,找出密码的最有效方法是暴力破解或字典攻击.碰撞和preimage攻击都没有找到实际密码的任何帮助,因此对SHA-1的加密攻击在这里没有帮助.使用什么算法甚至不重要 - 人们甚至可以使用MD5或MD4,密码也同样安全(因为计算SHA-1哈希的速度较慢).
• 为了评估"同样安全"的安全性,我们假设单个sha1运行需要1000次操作,密码包含大写,小写和数字(即60个字符).这意味着攻击者每天可以测试10个¹⁵*60*60*24/1000~ = 10 ^17个潜在密码.对于暴力攻击,这意味着在3小时内测试最多9个字符的所有密码,一周最多10个字符,一年最多11个字符.(每增加一个字符需要花费60倍.)字典攻击速度要快得多(即使是一台计算机的攻击者也可以在几小时内完成它),但只能找到弱密码.
• 要以用户身份登录,攻击者无需找到确切的密码; 它足以找到导致相同哈希的字符串.这被称为第一次原像攻击.据我所知,没有针对SHA-1的preimage攻击.(A暴力破解攻击需要2点¹⁶⁰的操作,这意味着我们的理论,攻击者需要10 ³⁰年,把它关闭.的理论可能性的限制是大约2个⁶⁰操作,在该攻击将需要几年的时间.)有原像攻击对抗缩减版本的SHA-1,效果可以忽略不计(对于使用44步而不是80步减少的SHA-1,攻击时间从2 ^160次操作减少到2 ^157次).有针对SHA-1的碰撞攻击,这在理论上是可能的(我发现最好的时间从2 ^80减少到2 ⁵²),但是这些对密码哈希没用,即使没有腌制.

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

更新:马塞洛指出了一篇文章,其中提到了2 ^106次操作中的第二次原像攻击.(编辑:正如托马斯解释的那样,这种攻击是一种假设的结构,不适用于现实场景.)但我仍然没有看到这对于使用SHA-1作为关键的派生函数是多么危险.通常有充分的理由认为碰撞攻击或第二次原始图像攻击最终会变成第一次原始图像攻击吗？

Answer 1

对您的问题的简短回答是:SHA-1尽可能安全.MD5也可以,即使是MD4; 但它可能让一些投资者感到紧张.对于公共关系,最好使用"更好"的哈希函数,例如SHA-256,即使将其输出截断为160或128位(以节省存储成本).一些SHA-3第二轮候选人似乎比SHA-1更快,而可以说是"更安全"; 但它们仍然有点新,所以坚持使用SHA-256或SHA-512将是一个更安全的路线.它会让你看起来专业和谨慎,这是好的.

请注意,"尽可能安全"与"完全安全"不同.请参阅下面的相当冗长的解释.

关于已知攻击:

对MD4,MD5和SHA-1的已知攻击是关于碰撞,其不影响前像像抗性.已经证明MD4有一些弱点,在尝试打破HMAC/MD4时可以(仅在理论上)被利用,但这不适用于您的问题.Kesley和Schneier在论文中的2 ¹⁰⁶秒前映像攻击是一种通用的权衡,仅适用于非常长的输入(2 ⁶⁰个字节;这是一百万TB - 注意106 + 60超过160;这就是你看到的地方权衡没有任何魔力).

此消息的其余部分假定您使用的哈希函数(例如SHA-1)是一个"黑盒子",没有攻击者可能使用的特殊属性.这就是你现在拥有的"破碎"散列函数MD5和SHA-1.

关于彩虹表:

"彩虹攻击"实际上是字典或暴力攻击的成本分担.它是Hellman在1980年首次描述的时间记忆权衡的衍生物.假设你有N个可能的密码(这是你字典的大小,如果你考虑使用输出的粗暴强制哈希函数,则为2 ⁿ⁾ n位),存在一种分时攻击,您可以在其中预先计算N个散列密码并将其存储在一个大表中.如果对哈希输出进行排序,则可以在单个查找中获取密码.一个彩虹表是该表存储与显着降低的空间,一个聪明的办法.您只存储N/t哈希密码,并使用O(t ²)查找破解密码.彩虹表允许您虚拟处理比实际存储的大得多的预计算表.

然而,无论是否彩虹,攻击者仍然必须至少进行一次完整的攻击.这可以看作几个连续的优化层:

1. 破解每个密码的暴力/字典攻击花费了N.
2. 使用预先计算的表,攻击者支付该费用N 一次,然后可以以非常小的每个密码的额外成本攻击许多密码.
3. 如果预先计算的表是彩虹表,则N可以稍大,因为存储成本降低.N上的瓶颈成为攻击者可以集合的CPU能力,而不是他硬盘的大小.

如果N足够大以至于散列N个密码的CPU成本是荒谬的,那么无论是否使用彩虹表,这种攻击都是不可行的.这意味着具有80位或更多输出的(抗映射图像的)散列函数足以使暴力攻击变得不可行.

关于盐:

盐是一种打败预计算的方法.在上面的描述中,盐将攻击者带回到步骤1:salting防止攻击者在几个受攻击的密码之间共享O(N)成本.预先计算的表格,更为繁荣的彩虹表格,已不再可行.

你想要腌制,因为当散列数据包含密码时,即适合随机人类大脑的东西时,N就可以很低:人类在选择和记忆密码时非常糟糕.这就是"词典攻击"的含义:假设许多用户密码将位于特别选择的空间中,那就是使用潜在密码的缩小空间("词典").

因此,盐析将至少阻止攻击者使用预先计算的表,特别是预先计算的彩虹表.这假定攻击者将能够打破一个密码或两个; 我们不希望他用额外的开销来打破1000个其他密码.

此外,腌制有利于公共关系.

关于SHA-1费用:

SHA-1的基本成本是关于散列64字节块.这就是SHA-1的工作原理:数据被填充,然后分成64字节块.在英特尔酷睿2系统上处理单个块的成本约为500个时钟周期,而单核处理成本则为500个时钟周期.MD5和MD4更快,分别计数约400和250个循环.不要忘记,大多数现代CPU都有多个内核,因此相应地增加.

一些腌制方案规定了巨大的盐; 例如,进入散列函数的实际上是单个128位盐的40000个连续副本,然后是密码本身.对于合法用户和攻击者而言,这使得密码散列更加昂贵(我的例子为10000倍).这是否是一个好主意取决于设置.对于在桌面系统上登录,这很好:用户甚至不会注意到他的密码需要10ms,而不是1μs; 但攻击者的成本上升了一个非常明显的因素10000.在每秒有数千个客户端的共享服务器上,总成本可能会变得过高.从概念上讲,为合法用户和攻击者提高相同因素并不是最好的安全性; 但在某些特定情况下,这可能是一个有价值的想法.

关于在线攻击:

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

通常,对于密码安全性,安排系统不让攻击者构建脱机攻击会带来更多回报.这就是Unix系统所做的事情:以前在世界可读/etc/password文件中使用的散列密码现在位于/etc/shadow受到读取访问保护的文件中,除了少数特权应用程序.这里的假设是,如果攻击者可以阅读/etc/shadow,那么他可能对系统有足够的控制权,他不再需要密码......

Answer 2

之前的答案没有提及GPU,它可以平行化SHA-1散列,以至于整个数据库现在可以在几分钟或几小时而不是几天或几周内强制强制,即使密码已被腌制.

现代密码哈希算法(如bcrypt或scrypt)专门设计为难以在GPU上运行,因为它们是具有更高内存要求的分组密码(并且GPU中的内存访问不能在相同程度上并行).它们还具有"工作功能",随着技术的进步,它们可以随时变慢.

简而言之,您应该只使用最好的工具来完成工作.SHA-1与现有技术相差甚远.

进一步阅读:

• https://crypto.stackexchange.com/questions/400/why-cant-one-implement-bcrypt-in-cuda
• http://codahale.com/how-to-safely-store-a-password/
• http://www.codinghorror.com/blog/2012/04/speed-hashing.html
• https://security.stackexchange.com/questions/4781/do-any-security-experts-recommend-bcrypt-for-password-storage/6415#6415

Answer 3

您的描述对于当前的技术水平来说听起来很准确.

但是,您不应该使用任何散列函数的单次迭代:至少,您应该多次迭代(散列的1000次迭代会使攻击者的工作量增加1000倍.它会使您的工作量增加相同的数量,但是你做的密码哈希比他们少得多.)

但是,理想情况下,您应该使用现有的密码存储原语,例如此处描述的那些.

Answer 4

SHA1是一个消息摘要,它从来就不是密码散列(或密钥派生)函数.(虽然它可以用于KDF的构建块,例如在带有HMAC-SHA1的PBKDF2中.)

密码散列函数应该抵御字典攻击和彩虹表.已经设计了几种算法来实现这一目标.

目前,最好的选择可能是Argon2.这一系列密码散列函数赢得了2015年的密码哈希竞赛.

如果Argon2不可用,唯一的其他标准化密码散列或密钥派生函数是PBKDF2,这是一个古老的NIST标准.如果不需要使用标准,其他选择包括bcrypt和scrypt.

维基百科有这些功能的页面:

• https://en.wikipedia.org/wiki/Argon2
• https://en.wikipedia.org/wiki/Bcrypt
• https://en.wikipedia.org/wiki/Scrypt
• https://en.wikipedia.org/wiki/PBKDF2