为什么盐值可以使字典攻击变得“不可能”?

86

更新:请注意,我并不是在询问什么是盐,什么是彩虹表,什么是字典攻击,或者盐的目的。我的问题是:如果你知道用户的盐和哈希值,那么计算他们的密码是否变得非常容易?

我理解这个过程,并在我的一些项目中实现了它。

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

在数据库中存储的内容:

username | hashed_password | salt

我见过的所有盐值的实现都是将盐值添加到密码的末尾或开头:

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

因此,一个有经验的黑客(哈哈)可以对存储在上述常见组合中的盐值逐个运行每个关键字,从而进行字典攻击。

上述实现只是为黑客增加了一个步骤,而没有解决潜在的问题,是否存在绕过此问题的替代方法,或者我是否误解了这个问题?

我唯一想到的做法是采用一个秘密的混合算法,将盐值和密码以随机模式或添加其他用户字段进行哈希处理,这样黑客必须能够访问数据库和代码才能使用字典攻击成功。 (更新:如评论所指出的那样,最好假设黑客已经能够访问您所有的信息,因此这可能不是最佳方法)。

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

我们被黑客攻击后的数据库数据:

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亿个哈希值。这可能需要几个小时,但这并不是真正的问题。

破解理论更新

我们假设自己是一个腐败的网络托管商,可以访问SHA1哈希值和salt的数据库以及您混合它们的算法。该数据库有10,000个用户记录。

此网站声称使用GPU每秒可以计算2,300,000,000个SHA1哈希值。(在实际情况下可能会慢一些,但现在我们将使用该引用数字)。

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

考虑到95个可打印ASCII字符的全部范围,最大长度为4个字符,除以计算速率(变量),再除以2(假设平均发现密码时间将平均需要50%的排列组合),对于10,000个用户而言,如果密码长度小于或等于4,则需要177秒来找出所有用户的密码。

让我们调整一下以使其更符合现实。

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

假设不区分大小写,密码长度小于或等于7个字符,只使用字母数字字符,则需要4天才能为10,000个用户记录解决问题,并将算法的速度减半以反映开销和非理想情况。

重要的是要认识到这是一个线性暴力攻击,所有计算都是独立的,因此它是多系统解决的完美任务。(比如易于设置两台电脑从不同的端口运行攻击,可以将执行时间缩短一半)。

考虑到递归地哈希密码1,000次可使此任务的计算成本更高:

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

这表示最大长度为7个字母数字字符,对于一个用户而言,执行速度不足引用数字的一半。

递归哈希1,000次有效地阻止了一次性攻击,但用户数据仍然容易受到有针对性的攻击。


12
加盐的整个目的是为了防止你能够查看散列密码并看到多个用户具有相同的哈希值(因此具有相同的密码)。如果不加盐,你可以使用哈希算法生成每个可能的哈希值,然后对其进行暴力搜索。由于算法从未更改,这使得攻击者能够预测,而加盐只会使其更加困难。 - BeRecursive
26
因为薄脆饼干就像是蛞蝓一样,盐能够将它们皮肤上的黏液干燥并杀死它们。 - T.E.D.
6
@T.E.D.:我相当喜欢咸饼干。盐味的蛞蝓就不那么受欢迎了。 - FrustratedWithFormsDesigner
3
在你的攻击示例中,如果没有盐值,攻击者可以对“每个常见密码进行哈希处理。这个密码是否与一个或多个用户匹配?是,我有他们的密码”进行攻击,攻击者能够在没有额外成本的情况下“并行”攻击所有密码。 - Damien_The_Unbeliever
3
@Tom Gullen - 你只了解其中的一部分。没有盐值,攻击者无需使用你在“更新2”中展示的方法。他只需在表格中进行查找,用O(1)或O(log n)的时间(n表示候选密码的数量)获取密码。盐值是防止这种情况发生的,它迫使攻击者使用你所演示的O(n)方法。另一种技术(密钥强化)可以导致循环中的每次尝试需要一整秒钟,这意味着执行那些测试需要3年时间...而且只有10k个密码,在那么长的时间内你可能无法破解到任何一个密码。 - erickson
显示剩余21条评论
11个回答

62

它不能阻止字典攻击。

它的作用是,即使有人获得了您密码文件的副本,也可以防止他使用彩虹表来计算哈希值生成密码。

然而,它最终也可以通过暴力破解被攻破。对于这一点,答案是强制用户不要使用字典单词作为密码(例如,至少一个数字或特殊字符的最低要求)。

更新:

我早些时候应该提到这一点,但一些(大多数?)密码系统为每个密码使用不同的盐,可能与密码本身一起存储。这使得单个彩虹表无效。这就是UNIX crypt库的工作方式,现代类UNIX操作系统已经通过新的哈希算法扩展了这个库。

我知道事实上支持SHA-256和SHA-512的功能已在较新版本的GNU crypt中添加。


17
食盐可以防止预先计算好的哈希值列表(彩虹表)发挥作用,攻击者必须从头开始。 - Ian Boyd
2
在PHP中,您可以使用mcrypt或bcrypt库进行比md5或sha1更好的加密。如果您被困在md5或sha1中,您应该进行“拉伸”,即在将密码存储到数据库之前对其进行数千次哈希处理。这保持了熵的一致性,但增加了计算哈希的时间。 - Malfist
2
@Tom Gullen,你在读什么文章?是自称专家的文章还是科学期刊上的同行评议文章? - Malfist
7
普通开发者经常会写一些关于如何编写“安全”系统的博客或帮助文章。但是保障安全并非可以轻易掌握,它需要广泛的知识。这是否不公平?也许是。但在某种程度上来说,这样做是安全的。有原因存在着安全专家。然而,并不是所有东西都必须像福特诺克斯一样安全。最好的策略是使用由这些专家设计的预构建系统,并根据自己的需求进行修改。 - Malfist
3
@Michael:如果使用更长的盐值,您需要预先计算所有可能的盐值,以便它出现在彩虹表中。关键是您不会为所有密码保留相同的盐值,而是为每个密码随机选择盐值,并将其存储在存储的哈希盐密码旁边的数据库中。因此,黑客需要为每个可能的大型盐值输入彩虹表,导致表格过大而不可行,这就是重点。 - Colin DeClue
显示剩余21条评论

32
更准确地说,字典攻击,即尝试枚举列表中的所有单词的攻击,不会变得“不可能”,但它变得不切实际每一位盐都会使所需存储和计算的数量翻倍
这与预先计算的字典攻击(如涉及彩虹表的攻击)不同,其中盐是否保密并不重要。
例如:使用64位盐(即8个字节),您需要在字典攻击中检查264个额外的密码组合。如果字典包含200,000个单词,则必须进行

200,000 * 264 = 3.69 * 1024

最坏情况下的测试-而不是没有盐的200,000次测试。
使用盐的另一个好处是攻击者无法从其字典中预先计算密码哈希值。这将需要太多时间和/或空间。 更新 您的更新假定攻击者已经知道盐(或已窃取)。这当然是一种不同的情况。但是,攻击者仍无法使用预先计算的彩虹表。这里非常重要的是散列函数的速度。为了使攻击不切实际,散列函数需要慢。 MD5或SHA在这里不是好的候选算法,更好的哈希算法候选者是Blowfish或其某些变体。

更新2

关于通用密码哈希保护的好文章(超出原问题但仍有趣):

够了彩虹表:关于安全密码方案你需要知道的

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


4
即使有合理的强密码策略,由于人们使用助记符而非随机生成器来选择密码,因此数亿或几十亿个候选字典中可能会有一些命中率。如果不使用盐值,这样大小的字典可以在普通系统上进行预计算。如果使用盐值,攻击者每次都需要重新计算哈希值,如果执行足够多次的哈希迭代,攻击者的攻击速度可以减缓到每秒几次尝试。 - erickson
3
“被保密”完全不是盐的关键。无论如何,您需要访问它们以检查密码,因此任何试图将它们保密的尝试都很可能通过增加复杂性而使系统更加脆弱,而不是真正成功。 - Michael Borgwardt
2
@0xA3:再说一遍,对于攻击者来说,“盐”的重点并不在于它是未知的。您的计算机需要以某种方式访问它,因此入侵计算机的攻击者也可以获取它。任何攻击者不知道“盐”的情况都是一个转移注意力的话题。 - Michael Borgwardt
1
我认为值得一提的是,链接的文章错误地描述了彩虹表。他所描述的只是一个简单的字典攻击。彩虹表实际上是非常不同的(并且有些更加复杂)。在这里有一个相当不错的解释,介绍了彩虹表的真正工作原理:http://kestas.kuliukas.com/RainbowTables/ - Jerry Coffin
3
“当然,盐需要保密。” 如果攻击者可以访问您的密码哈希值,他也将拥有您的盐 - 您需要的是每个用户的盐,而不是“隐藏”盐的安全性。请注意,这里的安全性不能依赖于盐的保密性。 - snemarch
显示剩余9条评论

31

是的,你只需要3天就能破解sha1(盐 | 密码)。这就是为什么好的密码存储算法使用1000次哈希处理:你需要8年。


3
到目前为止,您提供的回答是最简明扼要的,我不知道这是一个选项。 - Tom Gullen
显然,您从未在系统上进行哈希基准测试。您可以每秒执行许多百万个sha1计算。对于攻击者来说,1000轮是毫无意义的。此外,sha1是一种已被破解的哈希函数,因此评分为-1。 - rook
显然我正在使用问题中的名称和数字。如果你听说过主题和清晰度这样的东西...哦,那是Rook。不要紧。 - blaze
1
@Rook,1,000轮意味着暴力破解需要花费1,000倍的时间。对我来说,这似乎是一个不错的功能。 - Tom Gullen
如果攻击者能够猜测密码,那么登录是否也一样(或者是我漏掉了什么?哈哈)? - khaled_webdev
请注意,在2013/2014时间范围内,PBKDF2迭代次数应该是数万到数十万,而不仅仅是1000(WPA2本身仅是PBKDF2-HMAC-SHA-1的4096次迭代)。 - Anti-weakpasswords

17

字典是一种通过键索引值的结构。在预先计算的字典攻击中,每个键是一个哈希值,相应的值是生成该哈希值的密码。拥有预先计算的字典后,攻击者可以“瞬间”查找将产生必要哈希值以登录的密码。

使用盐后,存储字典所需的空间迅速增长...增长得如此之快,以至于尝试预先计算密码字典很快就变得毫无意义。

最好的盐是从加密随机数生成器中随机选择的。八个字节是一个实用的大小,超过16个字节没有任何意义。


盐除了“使攻击者的工作更加麻烦”之外,还能消除整个攻击类别——预计算字典的使用。

完全安全地保护密码还需要另一个元素,那就是“密钥强化”。SHA-1的一轮不够安全:安全的密码散列算法应该在计算上具有非常缓慢的速度。

许多人使用PBKDF2,一种密钥派生函数,将结果反馈到哈希函数中成千上万次。 "bcrypt"算法类似,使用迭代的密钥派生方法缓慢计算。

当哈希操作变得非常缓慢时,攻击者会越来越希望拥有预先计算的表。但正确的盐可以防止这种方式。


评论

在没有盐的情况下,攻击者不会使用“更新2”中演示的方法。他只需在预先计算的表格中进行查找,并在O(1)或O(log n)时间内获得密码(n为候选密码数)。盐是防止此项操作并强制使用“更新2”中显示的O(n)方法的关键。

一旦降低到O(n)攻击,我们必须考虑每次尝试需要多长时间。键强化可能导致循环中的每次尝试需要整整一秒钟的时间,这意味着测试10k个密码对10k个用户所需的时间将从3天延长至3年...而只有10k个密码,你在那段时间内很可能破解不了任何密码。

你必须考虑到攻击者将使用最快的工具,而不是PHP,因此,在关键强化方面,数千次迭代而不是100次将是一个良好的参数。计算单个密码哈希的时间应该需要大部分时间。

关键强化是标准密钥派生算法PBKDF1和PBKDF2的一部分,来自PKCS#5,这些算法是很好的密码混淆算法(“派生密钥”是“哈希”)。

许多StackOverflow用户提到这篇文章,因为它是对Jeff Atwood有关彩虹表危险的帖子的回应。这不是我最喜欢的文章,但它确实更详细地讨论了这些概念。


当然,你要假设攻击者已经拥有所有东西:盐、哈希、用户名。假设攻击者是一个腐败的托管公司员工,在你的myprettypony.com粉丝网站上转储了用户表。他试图恢复这些密码,因为他打算检查你的pony粉丝是否在他们的citibank.com帐户上使用了相同的密码。

通过设计良好的密码方案,这个人将无法恢复任何密码。


1
我认为Tom所说的“字典攻击”,是指尝试使用已知的弱密码(即来自人类语言词典的密码),而不是预先计算好的哈希明文表。这也是我在阅读此上下文中的“字典”时首先想到的。 - Michael Borgwardt
@Michael Borgwardt: 我同意,@erickson 指的是预先计算的字典攻击。 - Dirk Vollmar
1
盐值可以防止预先计算的字典攻击。密钥强化可以防止字典攻击。两者必须一起使用以实现安全的密码认证。 - erickson
我确实是指普通的英文表格。这个问题旨在解决如何阻止黑客为每个用户帐户计算出所有可能的哈希组合的问题。 - Tom Gullen

7
盐的作用是防止攻击者的努力被摊销。
如果没有盐,可以在世界上每个数据库中的每个用户上使用单个预计算哈希密码条目表(例如所有字母数字5个字符字符串的MD5,易于在网上找到)。
有了特定于站点的盐,攻击者必须自己计算表,然后可以将其用于站点的所有用户。
有了每个用户的盐,攻击者必须为每个用户单独耗费这个努力。
当然,这对于直接从字典中取出的真正弱密码并没有太大帮助,但它可以保护相对较强的密码免受此摊销。

1
简短而精确的答案 - 值得补充的是,如果没有盐或使用站点范围的盐,您可以轻松地发现具有相同密码的用户,并且只需要暴力破解一个。但是,如果使用每个用户的盐,则无法这样做。 - snemarch

6
此外,还有一个重要的点 - 使用用户特定的盐可以防止检测到两个使用相同密码的用户 - 他们的哈希值将匹配。这就是为什么很多时候哈希是哈希(盐+用户名+密码)。
如果您试图保密哈希值,攻击者也无法验证哈希值。
编辑-刚注意到上面的评论已经提出了主要观点。

1
你应该编辑以指定每个用户的盐; 使用站点范围盐的网站仍将允许您检测相同的密码。 - snemarch
@snemarch - 是的 - 非常感谢您对这个重要区别的指出! - Dominik Weber

5

盐被用来防止彩虹表攻击。彩虹表是一个预先计算好的哈希值列表,这使得将哈希值转换为其对应短语更加简单。需要理解的是,除非我们使用现代的哈希算法,否则仅使用盐并不是一种有效的防止密码破解的方法。

假设我们正在使用SHA1算法,利用最近发现的漏洞,假设我们有一台每秒运行1,000,000次哈希值操作的计算机,需要53亿亿年才能找到碰撞, 因此PHP每秒只能处理300个也无所谓。我们之所以使用盐,是因为如果有人真的生成了所有常见的字典短语,那么(2^160 个人,欢迎来到2007年的漏洞时代)。

这里是一个实际的数据库,包含了我用于测试和管理目的的两个用户。

RegistrationTime        UserName        UserPass    
1280185359.365591       briang      a50b63e927b3aebfc20cd783e0fc5321b0e5e8b5
1281546174.065087       test        5872548f2abfef8cb729cac14bc979462798d023

实际上,这个加盐方案是你的sha1(注册时间+用户名)。继续吧,告诉我我的密码,这些都是生产中真实的密码。你甚至可以坐在那里用php敲出一个单词列表。尽情发挥吧。
我并不疯狂,我只是知道这很安全。为了好玩,测试的密码是“test”。 sha1(sha1(1281546174.065087 + test) + test) = 5872548f2abfef8cb729cac14bc979462798d023
你需要为每个用户生成一张完整的彩虹表,以 27662aee8eee1cb5ab4917b09bdba31d091ab732 为前缀,仅对于这个用户而言。这意味着我可以允许我的密码不被单个彩虹表破解,黑客需要为测试生成一个以 27662aee8eee1cb5ab4917b09bdba31d091ab732 为前缀的完整彩虹表,再为 briang 生成一个以 f3f7735311217529f2e020468004a2aa5b3dee7f 为前缀的完整彩虹表。想象一下所有哈希值需要 5.3 亿万年的时间,想象一下只存储 2^80 个哈希值所需的空间(远超过 20 yottabytes),这是不可能的。不要把盐值混淆为使哈希值永远无法解码的手段,它是一种防止彩虹表翻译出所有用户密码的手段。在当前技术水平上,这是不可能的。

我理解什么是彩虹表,但你没有理解我的问题重点。如果你提供了你的盐值算法、哈希密码和盐值,那么我很可能可以在几分钟内告诉你你的密码是什么。 - Tom Gullen
当然可以,但是你刚才在示例中告诉我密码是什么,给我一个盐值、散列密码和如何组合盐值+密码的方法(非递归),只要密码<= 5个小写字母数字字符(无空格/特殊字符),我就会在这个框中告诉你它是什么。如果你想让我把钱放在上面,就告诉我,尽管我几分钟前的评论可能是一个严重低估,但几个小时内是可以完成的。 - Tom Gullen
1
也许只需要几秒钟,参见http://www.golubev.com/hashgpu.htm,该网站使用GPU计算,引用了“每秒2300M/s SHA1哈希值”的速度。如果密码包含95个ASCII字符的完整范围,长度在1-6个字符之间,则我们可以在不到6分钟的时间内破解它。如果密码只包含小写字母和数字,长度最多为8个字符,则不到25分钟即可破解。如果有一个包含10,000个用户记录的数据库,我们可以在不到200秒的时间内找到所有4个字符的完整ASCII密码((((95^4)/2300000000)/2)*10000)。(比引用的情况多一些开销,而引用的GPU速度可能是理想情况下的)。 - Tom Gullen
那么,有人破解了他的密码吗? - Andy
公平地说,我实际上学到了更多,而标准的PKCS#5第4.2节说我应该运行至少1000次我的哈希函数,而不是一次。自那时以来,我忽略了其他考虑因素。https://docs.google.com/viewer?url=http%3A%2F%2Fwww.truecrypt.org%2Fdocs%2Fpkcs5v2-0.pdf - Incognito
显示剩余3条评论

3
字典攻击的思路是,你拿到一个哈希值,然后找到生成这个哈希值的密码,而不需要重新计算哈希值。但如果加盐了,你就做不到了。
没有使用盐值的话,密码搜索就像在数据库中查找一样容易。添加盐值可以让攻击者对所有可能的密码进行哈希计算(即使是字典攻击,这也会显著增加攻击时间)。

在OP的情境中,攻击者已经获得了数据库中的盐值,并且将不得不尝试每个盐值与“字典”中的每个条目进行匹配。...我想是这样。 - FrustratedWithFormsDesigner

2

简单来说,盐值并不能完全防止哈希攻击(暴力或字典攻击),只是让攻击变得更困难;攻击者要么需要找到盐值算法(如果实现正确会使用更多迭代),要么就需要暴力破解算法,除非非常简单,否则几乎不可能成功。盐值也几乎完全消除了彩虹表查询的选项...


2

简单来说,如果不加盐,只需要对每个候选密码进行一次哈希运算,就可以检查它是否与任何使用相同算法哈希的用户在“已知宇宙”(被攻击数据库集合)中匹配。但是如果加盐,如果可能的盐值数量远远超过“已知宇宙”中的用户数量,则必须对每个候选密码与将要测试的每个用户分别进行哈希运算。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接