盐值为提供的情况下,破解一组加盐的SHA-512哈希需要多长时间?

58

以下是Java中的一个算法:

public String getHash(String password, String salt) throws Exception {
    String input = password + salt;
    MessageDigest md = MessageDigest.getInstance(SHA-512);
    byte[] out = md.digest(input.getBytes());
    return HexEncoder.toHex(out);
}
假设盐值已知,我想知道暴力破解一个密码为字典单词时需要多长时间,以及当它不是字典单词时需要多长时间。

10
可能需要一分钟或一周的时间。这取决于密码、盐值、用于暴力破解的计算机和算法实现。 - Cat Plus Plus
2
使用更加优化的算法进行暴力破解,同时使用越来越多的GPU。 - Cat Plus Plus
1
@timothyjc 这篇帖子的被接受答案正在meta上讨论:https://meta.stackoverflow.com/a/370459/2378429 有人称其为“彻头彻尾的胡说八道”和“荒谬至极”。你是否考虑取消接受它? - O.O.Balance
3个回答

122
在您的情况下,破解哈希算法等同于在哈希算法中找到碰撞。这意味着您不需要找到密码本身(这将是预像攻击),您只需要找到一个哈希函数的输出,它等于有效密码的哈希值(因此“碰撞”)。使用生日攻击查找碰撞需要O(2 ^(n / 2))时间,其中n是哈希函数输出长度(以位为单位)。
SHA-2的输出大小为512位,因此查找碰撞需要O(2 ^ 256)时间。假设没有对算法本身的聪明攻击(目前SHA-2哈希系列没有已知的攻击),这就是破解算法所需的时间。
要了解2 ^ 256实际上意味着什么:目前人们认为整个宇宙中的原子数量大约为10 ^ 80,大约为2 ^ 266。假设32字节输入(对于您的情况合理-20字节盐+12字节密码),我的计算机需要约0.22秒(〜2 ^ -2秒)进行65536次计算。因此,2 ^ 256次计算将在2 ^ 240 * 2 ^ 16次计算中完成,这将花费
2^240 * 2^-2 = 2^238 ~ 10^72s ~ 3,17 * 10^64 years

即使称之为数百万年也是荒谬的。而且使用全球最快的硬件并行计算数千个哈希值也无济于事。没有人类技术能够将这个数字转化为可接受的内容。
所以在这里忘记暴力破解SHA-256。你的下一个问题是关于字典单词的。传统上,彩虹表被用来恢复这种弱密码。彩虹表通常只是预先计算的哈希值表,其思想是,如果您能够预先计算并存储每个可能的哈希值及其输入,则使用O(1)查找给定哈希值并检索有效的预像。当然,在实践中这是不可能的,因为没有存储设备可以存储如此巨大的数据量。这个困境被称为内存时间权衡。由于只能存储那么多的值,典型的彩虹表包括一些形式的哈希链和中间减少函数(这在维基百科文章中有详细解释),以节省空间但放弃一些时间上的优势。

盐值是一种针对彩虹表的对策。为了防止攻击者为特定盐值预先计算表格,建议采用每个用户的个人盐值。然而,由于用户不使用安全、完全随机的密码,如果盐值已知,您只需在一个简单的试错方案中迭代一个常见密码大字典,仍然会取得意外的成功。自然语言和随机性之间的关系被表示为entropy。典型的密码选择通常具有较低的熵值,而完全随机的值则包含最大的熵值。

典型密码的低熵值使得您的用户中有相当高的机率使用来自相对较小的常见密码数据库中的密码。如果您在谷歌上搜索它们,您会找到这些密码数据库的种子链接,通常属于几十亿字节级别。如果攻击者没有任何限制,使用这样的工具通常需要几分钟到几天的时间才能成功。

这就是通常仅使用哈希和盐值还不够的原因,您还需要安装其他安全机制。您应该使用人工减速的熵诱导方法,例如PKCS#5中描述的PBKDF2,并且应强制要求给定用户在重试输入密码之前等待一段时间。一个好的方案是从0.5秒开始,然后每次失败尝试将时间加倍。在大多数情况下,用户不会注意到这一点,并且平均而言不会经常失败超过三次。但它将显着减缓任何试图攻击您的应用程序的恶意外部人员。


13
不,碰撞并不重要。找到与给定哈希值匹配的输入是第一张图像,即使它不是原始密码。你也曾经写过SHA-256,并且说“SHA-2的输出大小为512位”也不是最好的措辞。 - CodesInChaos
5
SHA-2是一族哈希函数,它不是SHA-256。 - AbiusX
18
这个回答的第一段完全是胡说八道(而且很危险)。如果预映像在字典中,你不需要使用碰撞攻击来找到哈希函数的预映像。(彩虹表也不是必须的,它只是在之前做了一些工作,并将工作分配给多个密码。如你所说,盐值可以帮助这里。但它无法抵御暴力字典密码搜索。) - Paŭlo Ebermann
1
生日攻击如何用于查找哈希函数的输出,该输出等于有效密码的哈希值?生日攻击只能找到两个具有相等哈希值的值(事先不知道)。 - Mike
8
这个答案正在Meta上讨论:https://meta.stackoverflow.com/q/370455/2378429。 - O.O.Balance
显示剩余3条评论

39
我想知道在密码为词典单词和非词典单词时的暴力破解时间。

词典密码

粗略估计:大约有1,000,000个英文单词,如果黑客能够每秒计算10,000个SHA-512哈希值(更新:见CodesInChaos的评论,此估计值十分低),那么100万/10,000 = 100秒。因此,对于单个用户的单词字典密码,仅需一分钟多一点的时间即可破解。如果用户连接了两个单词,那么破解时间将会是几天,但如果攻击者足够重视,则仍然非常可能。如果超过两个单词,就开始变得困难起来。

随机密码

如果密码是一个真正随机的字母数字序列,包括大小写,那么长度为N的可能密码数量是60^N(有60个可能字符)。这次我们将计算反过来; 我们问:在特定时间内,我们可以破解多长的密码?只需使用此公式:

N = Log60(t * 10,000) 其中t是以秒为单位的计算哈希值的时间(同样假设每秒计算10,000个哈希值)。

1 minute:    3.2
5 minute:    3.6
30 minutes:  4.1
2 hours:     4.4
3 days:      5.2

如果密码长度为5个字符,给定3天我们将能够破解密码。这是一个非常粗略的估计,但你可以理解。

更新:请参见下面的评论,实际上可以破解比这更长的密码。

这里发生了什么?

让我们澄清一些误解:

  • 盐并不会使计算哈希变慢,它只是意味着他们必须逐个破解每个用户的密码,并且预先计算的哈希表(流行词:彩虹表)完全无用。如果您没有预先计算的哈希表,并且您只破解一个密码哈希,则加盐不会有任何区别。

  • SHA-512并不是设计成难以暴力破解的。更好的哈希算法如BCrypt、PBKDF2或SCrypt可以被配置为需要更长的计算时间,而平均计算机可能只能每秒计算10-20个哈希值。如果您还没有阅读过关于密码哈希的这篇优秀答案,请务必阅读。

  • 更新:如CodesInChaos在评论中所写,即使使用正确的硬件计算SHA-512哈希,高熵密码(大约10个字符)也可以被暴力破解。


关于已接受答案的说明:

截至2014年9月,已接受的答案是不正确和危险的错误:

在您的情况下,破解哈希算法等同于在哈希算法中找到碰撞。这意味着您不需要找到密码本身(这将是一个预像攻击)...使用生日攻击找到碰撞需要O(2^n/2)时间,其中n是哈希函数输出长度(以比特为单位)。

生日攻击与破解给定哈希值完全无关。事实上,这是一个完美的预像攻击示例。该公式和接下来的几段话会导致攻击时间非常高且完全没有意义。正如上面所演示的,我们完全可以在几分钟内破解盐字典密码。

典型密码的低熵使得很有可能有您的用户之一使用来自相对较小的常用密码数据库的密码...

这就是为什么通常仅进行哈希和加盐不足够,您需要安装其他安全机制。您应该使用人工减速的熵诱导方法,例如PKCS#5中描述的PBKDF2...

是的,请使用计算速度较慢的算法,但什么是“熵引导”?将低熵密码通过哈希处理并不能增加熵。它应该保持熵,但你不能用哈希来改善一个垃圾密码,它不起作用。一个弱密码经过PBKDF2处理仍然是一个弱密码。


好的,即使使用自定义硬件,15个字符的密码也应该耗费数十亿。因此,可以肯定地说,没有攻击者会费力去猜测并破解它。高熵密码即使使用廉价的未加盐哈希算法也是安全的,只是高熵比你想象的要多一些。 - CodesInChaos
2
此答案提到了@CodesInChaos的评论,但并未引用其内容。该评论认为答案估计的每秒10000个哈希值非常低。然而,实际上并没有这样的评论存在,只有一个由CodesInChaos发表的评论,它涉及到不同的观点。我猜测一些“热心”的评论标记者看到了答案中提到了该评论,便决定将其删除,认为其已经过时,导致了这个答案出现了问题。也许你们两个中的其中一个可以通过更新答案来指出一个更现实的速率,从而解决这个混乱的局面? - Mark Amery

8
这个问题没有一个单一的答案,因为有太多的变量,但是SHA2还没有被真正破解(请参见:密码哈希函数的寿命),因此它仍然是一种用于存储密码的良好算法。盐的使用很好,因为它可以防止字典攻击或彩虹表攻击。盐的重要性在于每个密码都应该是唯一的。当存储散列密码时,可以使用类似[128位盐][512位密码哈希]的格式。
唯一可行的攻击方式是实际计算不同密码可能性的哈希值,并最终通过匹配哈希值找到正确的密码。
举个例子,比特币是一个不错的例子,可以给出每秒可以完成多少哈希计算的概念。 比特币使用SHA256,简而言之,生成的哈希数越多,获得的比特币就越多(可以交易成真钱),因此人们会动力更强地使用GPU进行计算。您可以在硬件概述中看到,一个只需150美元的普通显卡可以计算超过2亿个哈希/秒。您的密码越长且越复杂,所需时间就越长。以200M/s的速度计算,尝试所有8个字符的字母数字(大写,小写,数字)可能性将需要约300小时。如果密码是常见的英文单词,则实际时间很可能会更短。
因此,在任何安全问题上,您需要考虑上下文。攻击者的动机是什么?应用程序的种类是什么?对于每个随机盐的哈希,可以为防止类似数千个密码被泄露的情况提供相当好的保护。
您可以做的一件事是通过减慢散列过程来添加额外的暴力保护。由于您只散列密码一次,而攻击者必须多次进行散列,因此这对您有利。通常的方法是取一个值,对其进行哈希,取输出,再次哈希等等,进行固定数量的迭代。例如,您可以尝试1,000或10,000次迭代。这将使攻击者找到每个密码的时间变慢许多倍。

1
但是既然输出仍然是相同数量的字节,哈希-再哈希-再哈希-再哈希有什么好处呢?毕竟,聪明的攻击者只需对一些随机内容进行哈希,并尝试找到哈希冲突,不是吗? - Pacerier
通过进行字典攻击,猜测密码会变得更加耗时。例如,如果攻击者以某种方式获得了密码哈希值,他可以尝试猜测密码、对其进行哈希并查看它们是否匹配。在拥有正确硬件的情况下,攻击者可能每秒测试数亿个密码。任何能够显著减缓这种速度的事物都会使攻击者找到密码的可能性降低。 - Can Gencer
@Pacerier:当通过暴力破解找到第二个预像比暴力破解正确密码更容易时,你已经赢了,因为你需要尝试大约2^(n-1)个不同的预像才能找到一个,即使是具有良好输出大小的快速哈希函数(即使是相当不安全的MD5),也无法做到这一点,更不用说慢的哈希函数了。 - Paŭlo Ebermann
减速其实是有必要的,因为关键不在于哈希函数是否破损,而在于可能的(易记)密码的输入空间很小。 - Paŭlo Ebermann
1
我不会链接http://valerieaurora.org/hash.html,因为它将SHA-2标记为被削弱的,这是相当夸张的。我不知道有任何真正的攻击超过46轮(SHA-256有64轮,SHA-512有64轮)。与SHA-3相比,安全边际肯定更小,但它仍然远未被破解。 - CodesInChaos

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