什么是最佳的 scrypt 工作因子？

Question

我正在使用一个Java scrypt library来进行密码存储。在加密时，它需要一个N、r和p值，文档称之为"CPU cost"、"memory cost"和"parallelization cost"参数。问题是，我不知道它们具体意味着什么，或者它们的好值是多少；也许它们与Colin Percival's original app上的-t、-m和-M开关有某种对应关系吗？

请问有人对此有什么建议吗？该库本身列出了N = 16384、r = 8和p = 1，但我不知道这是强还是弱，或者是什么意思。

- Michael Louis Thaler

---

@JoopEggen 不知道你想说什么。 - CodesInChaos

@CodeInChaos：如果数据被盗，而密码字段中存储了加密的密码和访问名称（混合），那么它就更难被黑客攻击，例如查找常见密码如“secret”或“123456”。由于PASSWORD()、MD5()甚至普通的SHA1()都不是非常安全的，因此这种额外的技术不应被忽视。 - Joop Eggen

@JoopEggen 您所说的非常模糊。您是否意味着使用用户名作为盐？ - CodesInChaos

@Joop Eggen: 不可以。即使加盐，SHA1也不是密钥派生函数。不要使用。另一方面，SCrypt是一个非常好的密钥派生函数。 OP很明显已经意识到了基本问题。 - gimpf

@JoopEggen 这篇文章中没有提到，但是 scrypt +需要+ 作为参数传递一个显式的盐（除了 N/r/p）。而且，顺便说一句，强烈建议使用由密码学安全 PRNG 提供的 +随机+ 盐（我经常使用 16 或 32 字节的盐）。 - Cerber

Answer 1

作为起点： 在他2009年的幻灯片中提到了一些关于 scrypt 的内容：

• (N = 2^14, r = 8, p = 1) 用于 < 100ms（交互使用），以及
• (N = 2^20, r = 8, p = 1) 用于 < 5s（敏感存储）。

这些值对于一般用途（某些WebApp的密码-db）来说，即使在今天（2012-09）也足够好。当然，具体情况取决于应用程序。

此外，这些值（大多数情况下）意味着：

• N：工作因素，迭代次数。
• r：用于底层哈希的块大小；微调相对内存成本。
• p：并行化因子；微调相对CPU成本。

r 和 p 旨在解决 CPU 速度、内存大小和带宽未按预期增加的潜在问题。如果 CPU 性能提高得更快，则增加 p；如果内存技术的突破提供了一个数量级的改进，则增加 r。而 N 则用于保持与某个时段内性能每倍增长一致。

重要提示：所有值都会改变结果。(更新：)这就是为什么所有scrypt参数都存储在结果字符串中的原因。

- gimpf

---

顺便说一下，scrypt参数会自动存储在生成的密钥中，因此不需要单独进行存储。这意味着您可以在随着时间推移用户更改其密码时，在密码存储中为用户密码使用不同的参数值，并且使用当前参数值生成密钥（即散列后的密码）。 - Kaitsu

谢谢您指出这一点；我没有意识到链接的Java实现以合理的方式执行此操作。 - gimpf

顺便提一下，scrypt参数会自动存储在生成的密钥中，因此不需要单独存储。仅供澄清（给其他读者看），这仅适用于Java实现。 scrypt标准和其他实现不需要将成本/参数与生成的哈希一起存储。 - elithrar

只是为了澄清@elithrar的评论，scrypt作者Colin Percival本人使用的格式将工作因素存储在生成的密钥中（详见http://security.stackexchange.com/questions/88678#answer-91050）。 - ChrisV

@elithrar《scrypt文献》中并没有详细阐述其格式（建议在第11页的定义4中提供），但可以在代码或更有用的是Colin的格式规范中看到（很抱歉回复晚了）。 - ChrisV

Answer 2

简短回答

为了验证密码需要250毫秒

详细回答

计算scrypt所需的内存为：

128字节 × cost (N) × blockSizeFactor (r)

对于您提供的参数（N=16384，r=8，p=1）

128×16384×8 = 16,777,216字节 = 16 MB

在选择参数时必须考虑到这一点。

Bcrypt比Scrypt“弱”（尽管仍然比PBKDF2强三个数量级），因为它只需要4 KB的内存。您希望使硬件并行破解变得困难。例如，如果一个视频卡有1.5 GB的板载内存，并且您将scrypt调整为消耗1 GB的内存：

128×16384×512 = 1,073,741,824 字节 = 1 GB

那么攻击者无法在他们的视频卡上并行处理它。但是你的应用程序/手机/服务器每次计算密码时需要使用 1 GB 的 RAM。

我将 scrypt 参数想象成一个矩形可以帮助我理解，其中：

• 宽度是所需内存量 (128*N*r)
• 高度是执行的迭代次数
• 结果面积是总体的“难度”

• cost（N）增加了内存使用量和迭代次数。
• blockSizeFactor（r）增加了内存使用量。

剩余的参数parallelization（p）意味着您必须完成整个过程2、3或更多次：

如果您的内存比CPU多，您可以并行计算三条不同的路径 - 需要三倍的内存：

但在所有实际应用中，它是按系列计算的，需要三倍的计算量：

实际上，没有人选择除了p=1之外的p因子。

什么是理想的因子？

• 尽可能多地使用RAM
• 尽可能多地使用时间！

奖励图表

上述内容的图形版本；您的目标是约为250毫秒：

注意：

• 纵轴为对数刻度
• 成本因素（横轴）本身是对数形式（迭代次数= 2^CostFactor）
• 在r = 8曲线中突出显示

并且在合理的区域内放大了上述内容，再次查看约250ms的数量级：

额外聊天

• 如果scrypt配置使用少于4 MB，则scrypt在密码存储方面比bcrypt更弱¹
• 当涉及身份验证的密码哈希（即<1,000毫秒的验证时间）时，Argon2（i/d/id）比bcrypt更弱²

- Ian Boyd

---

谢谢您的分析，非常有用。只有一个问题：我目前正在使用Bouncy Castle实现在Android上进行测试 - http://www.bouncycastle.org/docs/docs1.5on/org/bouncycastle/crypto/generators/SCrypt.html，但内存使用量**恰好**高出2倍（128× N× r× 2）。有任何想法为什么会这样吗...？ - Quark

@Tron 我猜是因为有一个点，它将内存复制到另一个缓冲区（即将16MB传递给PBKDF2，执行实际的最终密钥派生）。 - Ian Boyd

需要改进：虽然N是影响伪随机跳跃次数的唯一因素，但计算成本仍由N和r决定，因为每个N迭代都有4r Salsa20/8迭代（2r用于生成内存块，然后2*r用于在内存块中跳跃）。 - Nick Bauer

@My1 这是一个好问题。Scrypt算法有一个要求，即 N < 2^(128*r/8)。当 r=1 时，简化为 N < 2^16。我需要深入挖掘一下，但这与内部的 BlockMix 函数使用 ROMix 的方式有关。 - Ian Boyd

好的，这很有趣。我以为它可能已经被遗忘或类似的事情，但是每个r>10为什么会在2^19处停止呢？还是说它们只是超出了范围？ - My1

Answer 3

我不想在上面提供的出色答案中重复，但没有人真正讨论“r”为什么具有特定的值。 Colin Percival的Scrypt论文提供的低级答案是，它与“内存延迟-带宽乘积”有关。但这实际上是什么意思呢？

如果你正在正确使用Scrypt，应该有一个大的内存块，大部分时间都停留在主存储器中。从主存储器中拉取需要时间。当块跳转循环的一次迭代首先从大块中选择一个元素混合到工作缓冲区时，它必须等待约100 ns才能到达第一块数据。然后它必须请求另一个，并等待其到达。

对于r = 1，您将进行4nr Salsa20/8迭代以及2n携带延迟的主存储器读取。

这并不好，因为这意味着攻击者可以通过构建具有较低延迟的系统来获得优势。

但是，如果您增加r并成比例地减少N，则能够满足相同的内存要求并执行与之前相同数量的计算--除了您交换了一些随机访问序列访问。扩展顺序访问允许CPU或库有效地预取所需的下一个数据块。虽然最初的延迟仍然存在，但后续块的减少或消除的延迟将初始延迟平均到最小水平。因此，攻击者从改进他们的内存技术中获得的收益很小。

但是，随着r的增加，存在收益递减点，这与先前提到的“内存延迟-带宽乘积”有关。这个乘积指示了可以在任何给定时间从主存储器传输到处理器的字节数。这与高速公路的原理相同--如果从A点到B点需要10分钟（延迟），并且道路以每分钟从A点向B点交付10辆车（带宽），则A和B之间的道路含有100辆车。因此，最佳r与一次可以请求多少64字节数据块相关，以便覆盖该初始请求的延迟。

这将提高算法的速度，使您可以根据需要增加N以获得更多的内存和计算，或者增加p以获得更多的计算。

增加"r"太多还存在其他问题，这些问题我没有看到过讨论：

1. 在减少N的同时增加r会减少伪随机跳转内存的次数，使得连续访问更容易优化，并可能给攻击者留下窗口。正如Colin Percival在Twitter上告诉我的那样，更大的r可能允许攻击者使用成本更低、速度更慢的存储技术，从而大大降低他们的成本 (https://twitter.com/cperciva/status/661373931870228480)。
2. 工作缓冲区的大小为1024r位，因此最终将被馈送到PBKDF2生成Scrypt输出密钥的可能末产品数量为2^1024r。跳转大内存块周围的排列（可能的序列）数量为2^NlogN。这意味着，记忆跳跃循环有2^NlogN个可能的产品。如果1024r > NlogN，则似乎表明工作缓冲区混合不足。虽然我不能确定，而且很想看到证明或证伪，但可能会发现工作缓冲区的结果与跳转序列之间存在相关性，这可能使攻击者有机会减少他们所需的内存而不需要过多增加计算成本。同样地，这是一个基于数字的观察——可能一切都在每一轮中混合得如此好，以至于这不是一个问题。r=8远低于标准N=2^14 的潜在阈值——对于N = 2^14，该阈值将为r = 224。

总结所有建议：

1. 选择r时要尽量大，以平均设备上内存延迟的影响，但不要太大。请注意，Colin Percival推荐的值r = 8似乎仍然在各种内存技术上保持相当优化，并且这显然没有
2. 过去8年间并没有太大的变化，16也许略微好一点。
3. 决定每个线程要使用多少块内存，记住这会影响计算时间，然后相应地设置N。
4. 将p任意提高到你的使用容量所能承受的程度（注意：在我的系统和使用我的自己的实现时，p = 250（4个线程），N = 16384，r = 8大约需要5秒钟），并在必要时启用线程以处理添加的内存成本。
5. 调整时，优先选择大的N和内存块大小而不是增加p和计算时间。Scrypt的主要优点来自于其大的内存块大小。

在Surface Pro 3上使用i5-4300（2个核心，4个线程）测试我自己的Scrypt实现的基准测试，使用恒定的128Nr = 16 MB和p = 230；左轴是秒数，底轴是r值，误差条为+/- 1标准差：

- Nick Bauer

---

很棒的表格！看起来在您的系统和实现中，使用1个线程、N=8192、r=16、p=1（使用16MB内存），每次认证尝试的时间成本约为40毫秒，这是一个非常好的成本。N=16834、r=8、p=1只稍微慢了一点，但似乎较大的r确实有微小但一致的优势。 - CBHacking