在什么时候向 PBKDF2 添加更多迭代不会提供额外的安全性?

信息安全 加密 密码学 哈希 密码分析 pbkdf2
2021-08-27 16:17:08

如果我的真实密码仅用于生成用作密码的实际密钥的哈希,这是否意味着可以尝试暴力破解密码本身?我知道无论哪种方式都需要很长时间,但是在什么时候简单地暴力破解密钥本身而不是通过每次哈希迭代会更快?对于我最安全的驱动器,我使用 20 秒迭代(这会导致大约 200 万次 SHA512 迭代)而不是默认值 1。如果有人想破解它并且拥有宇宙中的所有时间(并且多次),我会如果他们使用生成的哈希或原始密码的所有可能的 ASCII,他们会做得更快吗?

编辑:我想指出我只是对数学感到好奇,而不是实用性。我已经使用了很长的密码,而且我知道暴力破解需要很长时间,我知道橡胶软管密码分析等。我要问的是,如果对手理论上能够直接暴力破解 AES 密钥,经过多少次哈希迭代后,暴力破解 ASCII 密钥会比直接使用 AES 密钥更难......

4个回答

没有确切的答案,原因如下:

蛮力

我们从 128 位对称密钥开始。假设算法(例如 AES)还没有被破坏,我们必须看看功耗。假设 100% 高效的计算设备,其技术远远超过任何计算机、ASIC、图形卡或其他您可以想象的破解密钥设备,那么只需翻转比特就可以计算出这么高的最低能量要求。维基百科为我们做了数学计算,结果表明,对于 128 位密钥,物理学所需的最低能量需求约为 10 18焦耳,或 30 吉瓦一年。显然,对于“真正的”硬件,要求将是几十万倍;超过了整个世界的能源生产。因此,这远远超出了任何现有陆地物体的能力。

但如果我们转向 256 位密钥,数学就会变得更加严重。Schneier 在 Applied Cryptography 中对此进行了数学计算,之前在此处讨论过为了避免重复的细节让你厌烦,我将简单地得出结论:我们的太阳没有产生足够的能量来完成这项任务。

理论上的可逆计算(量子计算机可能实现)可以将有效位长度减少一半,使这样的项目仅仅超出任何现有能力的范围,而不是完全超出物理学的范围。但这都是学术性的。

要点是:无法强制使用大小合理的对称密钥。不是你,不是任何人。

等效回合

那么,PBKDF2有多少轮呢?如果攻击者必须在等待 10 年以完成密钥推导与围绕太阳构建戴森球体之间做出选择,那么 PBKDF2 路线仍然更快。从任何实际的衡量标准来看,为您的密钥派生增加更多时间意味着为攻击增加更多时间,并且在任何时候尝试暴力破解密钥都不会成为一种选择(除非 PBKDF2 路线需要外星建设项目)。

那么,等值点在哪里呢?暴力破解 PBKDF2 何时需要整个 Dyson Sphere 设置?答案是:视情况而定看,在你的攻击中使用散列过程而不是猜测密钥本身的重点是让你尝试更少的密码。如果您知道密码是“monkey”或“123456”,那么您宁愿只猜测两次,而不是尝试在顺序扫描中碰巧找到正确的哈希值。

所以答案取决于攻击者在攻击中使用的字典的大小。如果他知道正确的密码,那么他只猜一次。因此,蛮力攻击所花费的时间与正确登录的时间完全相同。不管你做多久。如果他希望在两次猜测中得到它,那么他的蛮力将花费您正确登录时间的两倍。如果他有一本 100 字的字典要尝试,那么正好是你正确登录的 100 倍,如果你的密码不在他的字典上,那么他永远不会成功。

一些实用数学

所以为了保证他的暴力攻击是不可能的,你还必须保证你的成功登录是不可能的,因为你必须考虑到你的密码是他名单上唯一候选者的可能性。

另一方面,如果您想获得一个合理的平均值,只需进行一些简单的除法即可。假设您希望暴力攻击需要 1 万亿年。假设我们的密码是 14 个字母数字字符(所以 10 25中有 1 个)。假设他的字典都是字母数字密码,那就是在 10 12年(短规模万亿)内猜测 10 25次密码,或每年 10 13次猜测,或每秒大约 316900 次猜测。这是一个完整的列表。有些密码会先猜,有些密码会最后猜,我们可能关心的是平均值,而不是最大值,所以让我们将猜测率降低一半。每秒大约 150000 次猜测使我们在相同的时间内完成了列表的一半。

因此,只要我们调整 PBKDF2 使得猜测每个密码的时间超过 1/150,000 秒,并且我们可以保证我们的密码将出现的最小字典是所有 14 个字母可能性的列表,那么 1万亿年。

更长的密码

当然,很难得到 14 个字符的随机密码。13 个字符将我们的密码列表从 10 25个条目缩小到 10 23 个,需要将破解速度降低约 100 倍(每秒 1500 个密码)才能保持我们 1 万亿年的平均值(从技术上讲,100 倍实际上是 62 倍,因为那是有多少个字母数字字符,但我四舍五入到 10 次方)。从你的长度中删除另一个字符每次都会将你的数字改变62 倍。

这个故事的寓意是,正在散列的内容比你如何散列更重要。例如,一个 22 个字符的字母数字密码是一个 131 位的密钥,即使根本不使用 PBKDF2,也无法尝试破解它。

警告

请记住,如果底层加密曾经被破坏,以至于可以在不猜测密钥的情况下对其进行攻击,那么这可能会成为首选的攻击方法。但是我们不知道 AES 中没有这样的攻击,我们也不希望这样的攻击永远存在。

来自 Colin Percival 关于scrypt的论文:

通过使用需要加密操作来计算的密钥派生函数,对具有熵位的2^s密码执行蛮力攻击的成本操作中提高。t2^t2^(s+t)

2,000,000 大约是 SHA-512 的 2^21 次迭代。为了超过 128 位密钥提供的安全性,您的密码需要有大约 107 位的熵,或大致相当于从大写、小写、数字和十二个符号中随机选择的 17 个字符的密码。

迭代是为了减慢攻击者的速度。让我们假设该函数已正确加盐,因此攻击者所能做的最好的事情就是尝试所有潜在的密码,直到找到匹配项。如果攻击者所能做的最好的事情是平均尝试2 n-1 个密码,我们将密码熵定义为等于n位:攻击者知道哪些密码更常被用户选择,并尝试以“最佳“订单,这将取得平均成功。(请注意,“平均”在这里是一个非常重要的词。没有这个词,所有的数学都会失败。)

“位”的使用来自这样一个事实,即如果密码是一个k位序列,那么所有可能的2 k个序列都有相同的机会被用户选择,那么根据上面的定义,熵是,等于k位。请参阅此答案以获取著名案例中的更长解释。

然后,您应用r次迭代以试图减慢攻击者的速度。攻击者计算成本平均为r·2 n-1因此,您的目标是使rn足够高,以使此成本过高,并且攻击者无法实现(攻击者认为不值得努力,或者根本做不到)。没有超越牢不可破的安全级别因此,确实存在最大迭代次数,超过该次数就无法获得实际的安全增益。一旦攻击者被击败,他就被击败了。没有办法再打败他了(尽管使用与哈利法塔一样高的迭代次数来羞辱和威慑攻击者可能会在心理上有所收获)。重要的一点是,攻击者的动机取决于受密码保护的数据的价值,因此价值不大的数据需要较少的保护。

现在可以对这个“牢不可破”水平的量化进行辩论。传统上,密码学家使用“80 位”,即2 80 个“简单操作”作为限制。这里的“简单操作”被理解为对小消息的底层哈希函数(比如 SHA-256)的调用;它实际上涉及数千个 32 位或 64 位算术运算。这个水平仍然保持得很好;已发表的最大可比努力是破解 64 位 RC5 密钥,正在进行 72 位努力,但尚未接近完成(请参阅此页)。另一方面,这个 80 位限制在 20 年前就已经使用了(这个限制意味着 SHA-1 具有 160 位输出,或 DSA 签名具有 160 位子组),并且从那时起技术已经改进(有关该辩论中通常引用的切入点,请参见摩尔定律)。

如今,“128 位”被用作现在和未来几十年的“安全限制”。事实上,这包括一个巨大的安全边际,但 128 是 2 的幂,因此它具有巨大的美学吸引力(如果密码学家使用十进制而不是二进制,他们将停止在 100 位)。

但是,在实践中,您的迭代不会达到那个水平。实际上,您可以期望普通人类用户的密码具有 30 位左右的熵;更多的人会过于乐观。众所周知,同样的用户没有耐心(您显然已经准备好等待 20 秒,但大多数人不会有耐心)。因此,您可能希望以百万计,而不是更多。这大约达到2 50,即比传统的 80 位不可破坏性限制容易十亿倍。这导致两个结论:

  1. 您应该使用用户(包括您自己)可以容忍的尽可能多的迭代,因为高迭代计数意味着更高的延迟。在达到牢不可破限制之前,您将耗尽用户的耐心。

  2. 增加密码熵总是更好的。“正确的马”方法产生的密码不难记住,但提供了比通常方法更好的熵(44 位,因为它被暴露了)。

“如果有人想要破解它并且拥有宇宙中的所有时间(并且多次),如果他们使用生成的哈希或原始密码的所有可能的 ASCII,他们会做得更快吗?”

这取决于散列函数的输出宽度。假设输出是一个非常低的 32 位,并且您的“真实密码”(顺便说一句,这是真的吗?)具有 64 位的熵。如果您还知道一些明文,那么破解 32 位可能需要更少的时间。第一个需要大约 2^32 解密,第二个需要 2^64,虽然不同,但猜测

通过尝试“原始密码的所有可能的 ASCII”不能成功地攻击长密码。取而代之的是基于字典的攻击。所以平均恢复时间的计算不同于尝试所有字符的计算。

为什么不成功?以 5 个单词的密码为例,只有 28 个小写字符。一个愚蠢的蛮力方案必须最多测试 26^28 = 10^40 个组合。

您是否考虑过使用更长的密码而不是大幅延迟?使用 Diceware 词典时,200 万因子需要多出 2 个单词。每个单词提供大约 12.9 位,请参阅Optional stuff you don't really need to know