86

更新:请注意,我不是在问什么是盐,什么是彩虹表,什么是字典攻击,或者盐的目的是什么。我在问:如果你知道用户salt和hash,计算他们的密码不是很容易吗?

我了解这个过程,并在我的一些项目中自己实施。

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,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,只有字母数字字符,解决 10,000 条用户记录需要 4 天,并且我将算法的速度减半以反映开销和非理想情况。

重要的是要认识到这是一种线性蛮力攻击,所有计算都是相互独立的,因此它是多个系统解决的完美任务。(IE 很容易设置 2 台计算机从不同端运行攻击,执行时间减半)。

考虑到对密码进行 1000 次递归散列以使该任务的计算成本更高的情况:

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

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

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

4

11 回答 11

62

它不会阻止字典攻击。

它的作用是阻止设法获取密码文件副本的人使用彩虹表从哈希中找出密码是什么。

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

更新

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

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

于 2010-08-25T13:57:37.220 回答
32

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

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

示例:使用 64 位 salt(即 8 个字节),您需要在字典攻击中检查 2 64 个附加密码组合。使用包含 200,000 个单词的字典,您将不得不

200,000 * 2 64 = 3.69 * 10 24

最坏情况下的测试——而不是 200,000 次无盐测试。

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

更新

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

更新 2

很好地阅读了一般保护密码哈希的问题(远远超出了原始问题,但仍然很有趣):

彩虹表就够了:您需要了解的有关安全密码方案的知识

文章推论:使用通过bcrypt(基于 Blowfish)或Eksblowfish创建的盐渍哈希,允许您使用可配置的设置时间来降低哈希速度。

于 2010-08-25T13:54:58.447 回答
31

是的,sha1(salt | password) 只需要 3 天。这就是为什么好的密码存储算法使用 1000 次迭代散列:你需要 8 年。

于 2010-08-25T15:00:29.747 回答
17

字典是一种结构,其中值由键索引。在预计算字典攻击的情况下,每个键都是一个散列,对应的值是产生散列的密码。有了预先计算好的字典,攻击者可以“立即”查找密码,该密码将产生登录所需的哈希值。

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

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


Salt所做的不仅仅是“让攻击者的工作更烦人”。它消除了一整类攻击——使用预先计算的字典。

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

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

当散列操作非常慢时,预先计算的表对攻击者来说变得越来越可取。但是适当的盐会破坏这种方法。


注释

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


如果没有盐,攻击者将不会使用“更新 2”中演示的方法。他只需在预先计算的表中进行查找,并在 O(1) 或 O(log n) 时间内获得密码(n 是候选密码的数量)。Salt 阻止了这种情况,并迫使他使用“更新 2”中显示的 O(n) 方法。

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

您必须考虑到攻击者将使用最快的工具,而不是 PHP,因此数千次而不是 100 次迭代将是密钥强化的一个很好的参数。计算单个密码的散列应该需要一秒钟的大部分时间。

密钥强化是来自 PKCS #5 的标准密钥派生算法 PBKDF1 和 PBKDF2 的一部分,它们构成了出色的密码混淆算法(“派生密钥”是“哈希”)。

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


当然,您假设攻击者拥有一切:盐、哈希、用户名。假设攻击者是一名腐败的托管公司员工,他将用户表转储到您的 myprettypony.com 粉丝网站上。他正在尝试恢复这些密码,因为他会转过身来看看您的小马粉丝是否在他们的 citibank.com 帐户上使用了相同的密码。

使用精心设计的密码方案,这家伙不可能恢复任何密码。

于 2010-08-25T13:57:36.083 回答
7

加盐的目的是防止攻击者的努力摊销。

没有盐,一个预先计算的哈希密码条目表(例如,所有字母数字 5 字符串的 MD5,很容易在网上找到)可以用于世界上每个数据库中的每个用户。

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

使用每个用户的盐,攻击者必须分别为每个用户付出这种努力。

当然,这对于直接从字典中保护非常弱的密码并没有多大作用,但它可以保护相当强的密码免受这种摊销。

于 2010-08-25T15:15:35.150 回答
6

另外——还有一点很重要——使用特定于用户的盐可以防止检测到两个密码相同的用户——他们的哈希值会匹配。这就是为什么很多时候哈希是哈希(盐+用户名+密码)

如果您尝试将哈希值保密,攻击者也无法验证哈希值。

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

于 2010-08-25T19:22:27.663 回答
5

实施盐以防止彩虹表攻击。彩虹表是预先计算的散列列表,这使得将散列转换为短语变得更加简单。您需要了解,除非我们拥有现代散列算法,否则加盐不能有效地防止破解密码。

因此,假设我们正在使用 SHA1,利用最近发现的利用该算法的漏洞,假设我们有一台以 1,000,000 哈希/秒运行的计算机,需要 530 万年才能找到冲突,所以是的 php每秒可以工作 300 次,大大,没关系。我们加盐的原因是因为如果有人确实费心生成所有常见的字典短语,(2^160 人,欢迎来到 2007 时代的漏洞利用)。

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

RegistrationTime        UserName        UserPass    
1280185359.365591       briang      a50b63e927b3aebfc20cd783e0fc5321b0e5e8b5
1281546174.065087       test        5872548f2abfef8cb729cac14bc979462798d023

其实加盐方案就是你的sha1(注册时间+用户名)。来吧,告诉我我的密码,这些是生产中的真实密码。您甚至可以坐在那里并在 php 中散列一个单词列表。去野外。

我没疯,我只知道这是安全的。为了好玩,test 的密码是test. sha1(sha1(1281546174.065087 + test) + test) = 5872548f2abfef8cb729cac14bc979462798d023

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

不要将加盐混淆为一种您无法解码的散列方法,它是一种防止彩虹表翻译所有用户密码的方法。在这种技术水平上是不可能的。

于 2010-08-25T17:40:59.360 回答
3

字典攻击背后的想法是,您获取一个哈希值并找到计算此哈希值的密码,而无需进行哈希计算。现在对加盐密码做同样的事情 - 你不能。

不使用盐使密码搜索与在数据库中查找一样容易。添加盐会使攻击者对所有可能的密码执行哈希计算(即使对于字典附加,这也会显着增加攻击时间)。

于 2010-08-25T13:55:24.853 回答
2

简单地说,加盐并不能防止哈希受到攻击(暴力破解或字典),它只会让它变得更难;攻击者要么需要找到加盐算法(如果实施得当,将使用更多的迭代)或暴力破解算法,除非非常简单,否则几乎是不可能的。加盐也几乎完全放弃了彩虹表查找的选项......

于 2010-11-18T17:55:44.147 回答
2

用最简单的话说:不加盐,每个候选密码只需要哈希一次,以针对“已知宇宙”(受损数据库集合)中任何地方的每个用户检查它,其密码通过相同的算法进行哈希处理。使用加盐,如果可能的加盐值的数量大大超过“已知宇宙”中的用户数量,则每个候选密码必须针对每个将对其进行测试的用户单独进行散列。

于 2010-08-25T15:04:37.807 回答
1

Salt 使Rainbow 表攻击变得更加困难,因为它使单个密码哈希更难以破解。想象一下,你有一个只有数字 1 的可怕密码。彩虹表攻击会立即破解它。

现在想象数据库中的每个密码都用许多随机字符的长随机值加盐。现在,您糟糕的密码“1”作为 1 的哈希值加上一堆随机字符(盐)存储在数据库中,因此在此示例中,彩虹表需要具有类似以下内容的哈希值:1。

所以假设你的盐是安全和随机的,比如说()%ISLDGHASKLU( %#%#,黑客的彩虹表需要有一个 1*()%ISLDGHASKLU(*%#%# 的条目。现在使用彩虹表就连这个简单的密码也不再实用了。

于 2010-08-25T14:01:29.753 回答