为什么盐使字典攻击"不可能"？

Question

更新:请注意我不是在询问盐是什么,彩虹表是什么,字典攻击是什么,或盐的目的是什么.我在查询:如果你知道用户的salt和hash,那么计算密码是不是很容易？

我理解这个过程,并在我的一些项目中自己实现它.

s =  random salt
storedPassword = sha1(password + s)

在您存储的数据库中:

username | hashed_password | salt

我所看到的盐析的每次实施都会在密码的末尾添加盐,或者开始:

hashed_Password = sha1(s + password )
hashed_Password = sha1(password + s)

因此,来自黑客的字典攻击是值得他的盐(哈哈),只需针对上面列出的常见组合中存储的盐运行每个关键字.

当然,上述实现只是为黑客增加了另一个步骤,而没有真正解决潜在的问题？有什么替代方法可以解决这个问题,还是我误解了这个问题？

我唯一能想到的就是有一个秘密混合算法,它以随机模式将salt和密码绑定在一起,或者将其他用户字段添加到散列过程中,这意味着黑客必须能够访问数据库和代码才能获得花边他们为字典攻击证明富有成效.(更新,正如评论中指出的那样,最好假设黑客可以访问您的所有信息,因此这可能不是最好的).

让我举一个例子,说明我如何建议黑客用密码和哈希列表来破解用户数据库:

来自我们黑客数据库的数据:

RawPassword (not stored)  |  Hashed   |     Salt
--------------------------------------------------------
letmein                       WEFLS...       WEFOJFOFO...

通用密码字典:

   Common Password
   --------------
   letmein
   12345
   ...

对于每个用户记录,循环公共密码并对其进行哈希:

for each user in hacked_DB

    salt = users_salt
    hashed_pw = users_hashed_password

    for each common_password

        testhash = sha1(common_password + salt)
        if testhash = hashed_pw then
           //Match!  Users password = common_password
           //Lets visit the webpage and login now.
        end if

    next

next

我希望这能更好地说明我的观点.

给定10,000个常用密码和10,000个用户记录,我们需要计算100,000,000个哈希值以发现尽可能多的用户密码.可能需要几个小时,但这不是一个真正的问题.

破解理论的最新进展

我们假设我们是一个损坏的虚拟主机,可以访问SHA1哈希和盐的数据库,以及混合它们的算法.该数据库有10,000个用户记录.

该网站声称能够使用GPU每秒计算2,300,000,000个SHA1哈希值.(在现实世界的情况下可能会更慢,但现在我们将使用引用的数字).

(((95 ^ 4)/ 2300000000)/ 2)*10000 = 177秒

给定全范围的95个可打印ASCII字符,最大长度为4个字符,除以计算速率(变量)除以2(假设发现密码的平均时间平均需要50%的排列)10,000用户需要177秒来计算长度<= 4的所有用户密码.

让我们为现实主义调整一下.

(((36 ^ 7)/ 1000000000)/ 2)*10000 = 2天

假设非大小写敏感,密码长度<= 7,只有字母数字字符,则需要4天才能解决10,000个用户记录,并且我将算法的速度减半以反映开销和非理想情况.

重要的是要认识到这是一次线性暴力攻击,所有计算都是相互独立的,因此对于多个系统来说,这是一个完美的任务.(IE很容易设置2台计算机从不同的端部运行攻击,这将是exectution时间的一半).

鉴于递归散列密码1000次的情况,使这项任务的计算成本更高:

(((36 ^ 7)/ 1 000 000 000)/ 2)*1000秒= 10.8839117小时

这表示最大长度为7个字母数字字符,执行速度低于一个用户的引用数字.

递归散列1000次有效地阻止了全面攻击,但针对用户数据的目标攻击仍然很脆弱.

Answer 1

它不会阻止字典攻击.

它的作用是阻止那些设法获取密码文件副本的人使用彩虹表来确定密码来自哈希的密码.

最终,它可能是暴力强迫.该部分的答案是强制您的用户不要使用字典单词作为密码(例如,至少一个数字或特殊字符的最低要求).

更新:

我之前应该提到这一点,但是一些(大多数？)密码系统对每个密码使用不同的盐,可能与密码本身一起存储.这使得单个彩虹表无用.这就是UNIX crypt库的工作原理,现代类UNIX操作系统使用新的哈希算法扩展了这个库.

我知道在较新版本的GNU crypt中添加了对SHA-256和SHA-512的支持.

Answer 2

更准确地说,字典攻击,即在穷举列表中尝试所有单词的攻击,并非"不可能",但它变得不切实际:每一点盐都会使所需的存储量和计算量翻倍.

这与预先计算的字典攻击不同,例如涉及彩虹表的攻击,其中盐是否是秘密并不重要.

示例:使用64位盐(即8个字节),您需要在字典攻击中检查2 ^64个其他密码组合.使用包含200,000个单词的字典,您将不得不制作

200,000*2 ⁶⁴ = 3.69*10 ²⁴

在最坏的情况下测试 - 而不是没有盐的200,000次测试.

使用salt的另一个好处是攻击者无法从他的字典中预先计算密码哈希值.它只需要太多的时间和/或空间.

更新

您的更新假定攻击者已经知道了盐(或者已经偷了它).这当然是一种不同的情况.攻击者仍然不可能使用预先计算的彩虹表.这里重要的是散列函数的速度.要使攻击不切实际,散列函数需要很慢.MD5或SHA在这里不是很好的候选者,因为它们被设计为快速,更好的哈希算法候选者是Blowfish或它的一些变体.

更新2

关于保护密码哈希问题的一个很好的解读(远远超出原始问题,但仍然很有趣):

足够的彩虹表:您需要了解的安全密码方案

本文的推论:使用使用bcrypt(基于Blowfish)或Eksblowfish创建的盐渍哈希,允许您使用可配置的设置时间使散列变慢.

Answer 3

是的,sha1(盐|密码)只需要3天.这就是为什么好的密码存储算法使用1000次迭代哈希:你需要8年.

Answer 4

字典是一种结构,其中值由键索引.在预先计算的字典攻击的情况下,每个密钥是散列,并且对应的值是导致散列的密码.在手预先计算的字典,攻击者可以"立即"查找,将产生必要的哈希登录密码.

使用salt,存储字典所需的空间迅速增长......如此迅速,试图预先计算密码字典很快变得毫无意义.

从加密随机数发生器中随机选择最好的盐.八个字节是实际大小,超过16个字节没有用处.

Salt不仅仅是"让攻击者的工作更具刺激性".它消除了一整类攻击 - 使用预先计算的词典.

另一个因素是完全保护密码所必需的,这就是"加强密钥".一轮SHA-1还不够好:安全的密码哈希算法在计算上应该非常慢.

许多人使用密钥派生函数PBKDF2,将结果反馈给哈希函数数千次."bcrypt"算法类似,使用缓慢的迭代密钥推导.

当散列操作非常慢时,预先计算的表对于攻击者来说变得越来越令人满意.但适当的盐会失败.

评论

以下是我对这个问题的评论.

如果没有盐,攻击者就不会使用"Update 2"中演示的方法.他只是在预先计算的表中进行查找,并在O(1)或O(log n)时间内获取密码(n是候选密码的数量).Salt就是阻止它并迫使他使用"Update 2"中显示的O(n)方法的原因.

一旦减少到O(n)攻击,我们必须考虑每次尝试需要多长时间.密钥加强可能导致循环中的每次尝试都花费一整秒,这意味着在10k用户上测试10k密码所需的时间将从3天延长到3 年 ......并且只有10k密码,您可能会破解零那个时候的密码.

您必须考虑攻击者将使用他能够使用的最快的工具,而不是PHP,因此数千次迭代而不是100次将是加强密钥的好参数.它应该花费很长时间来计算单个密码的哈希值.

密钥强化是来自PKCS#5的标准密钥派生算法PBKDF1和PBKDF2的一部分,它们制作了很好的密码混淆算法("派生密钥"是"哈希").

StackOverflow上的很多用户都参考了这篇文章,因为它是对Jeff Atwood关于彩虹表危险的帖子的回应.这不是我最喜欢的文章,但它确实更详细地讨论了这些概念.

当然,你认为攻击者拥有一切:salt,hash,用户名.假设攻击者是一个腐败的托管公司员工,他将用户表转储到myprettypony.com粉丝上.他正在尝试恢复这些密码,因为他要转身看看你的小马粉丝是否在他们的citibank.com帐户上使用了相同的密码.

使用精心设计的密码方案,这个人不可能恢复任何密码.

Answer 5

腌制的目的是防止攻击者的努力摊销.

在没有盐的情况下,可以在世界上每个数据库中的每个用户上使用单个预先计算的哈希密码条目表(例如,所有字母数字5字符串的MD5,易于在线查找).

使用特定于站点的盐,攻击者必须自己计算表,然后可以在站点的所有用户上使用它.

对于每用户盐,攻击者必须分别为每个用户花费这些精力.

当然,这对于直接从字典中保护真正的弱密码并没有太大作用,但它保护了相当强的密码以防止这种摊销.

Answer 6

此外 - 一个更加明确的观点 - 使用特定于用户的盐可以防止使用SAME密码检测到两个用户 - 它们的哈希值会匹配.这就是为什么哈希很多次哈希(盐+用户名+密码)

如果您尝试保持哈希秘密,则攻击者也无法验证哈希值.

编辑 - 刚刚注意到主要观点是在上面的评论中做出的.

Answer 7

实施盐以防止彩虹表攻击.彩虹表是预先计算的散列列表,这使得将散列转换为它的短语更加简单.你需要明白,除非我们有现代的哈希算法,否则腌制作为破解密码的现代预防是无效的.

所以我们假设我们正在使用SHA1,充分利用这个算法发现的最新漏洞,并且假设我们有一台运行在1,000,000哈希/秒的计算机,它需要530万亿年才能找到碰撞,所以是的PHP可以工作300秒,大woop,并不重要.我们盐的原因是因为如果有人确实懒得生成所有常见的字典短语,(2 ^ 160人,欢迎来到2007年时代的漏洞).

所以这是一个实际的数据库,有2个用户用于测试和管理目的.

RegistrationTime        UserName        UserPass    
1280185359.365591       briang      a50b63e927b3aebfc20cd783e0fc5321b0e5e8b5
1281546174.065087       test        5872548f2abfef8cb729cac14bc979462798d023

事实上,腌制方案是你的sha1(注册时间+用户名).来吧,告诉我我的密码,这些是生产中的真实密码.你甚至可以坐在那里用PHP挖出一个单词列表.去野外.

我并不疯狂,我只知道这是安全的.为了好玩,测试的密码是test. sha1(sha1(1281546174.065087 + test) + test) = 5872548f2abfef8cb729cac14bc979462798d023

您将需要生成perpended整个彩虹表27662aee8eee1cb5ab4917b09bdba31d091ab732的只是该用户.这意味着我实际上可以允许我的密码不会被一个彩虹表所破坏,黑客需要为27662aee8eee1cb5ab4917b09bdba31d091ab732生成一个完整的彩虹表进行测试,并再次为briang生成f3f7735311217529f2e020468004a2aa5b3dee7f.回想所有哈希值的530万年.想想存储2 ^ 80个哈希值(大约超过20个yottabytes)的大小,它不会发生.

不要将salting混淆为制作无法解码的哈希的手段,这是防止彩虹表翻译所有用户密码的一种方法.这种技术水平无法实现.