71

我正在使用Java scrypt 库来存储密码。当我加密事物时，它需要一个N,r和p值，它的文档将其称为“CPU成本”、“内存成本”和“并行化成本”参数。唯一的问题是，我实际上并不知道它们的具体含义，或者对它们有什么好的价值；也许它们以某种方式对应于Colin Percival 原始应用程序上的 -t、-m 和 -M 开关？

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

4

3 回答 3

72

作为开始：

cpercival在他 2009 年的幻灯片中提到了一些东西

  • (N = 2^14, r = 8, p = 1) for < 100ms (交互式使用), 和
  • (N = 2^20, r = 8, p = 1) for < 5s (敏感存储)。

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

此外，这些值（大部分）意味着：

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

r并且p旨在解决 CPU 速度、内存大小和带宽未按预期增加的潜在问题。如果 CPU 性能提高得更快，你就会提高p，相反，如果内存技术的突破提供一个数量级的改进，你就会提高r。并且N是否可以跟上每个时间跨度的一般性能翻倍。

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

于 2012-09-25T10:41:14.013 回答
66

简短的回答

这样验证密码需要 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)
  • 高度是执行的迭代次数
  • 得到的面积就是整体硬度

内存所需的次数迭代是 scrypt 硬度

  • cost( N ) 增加了内存使用和迭代。
  • ( rblockSizeFactor )增加内存使用量。

剩余的参数parallelization( p ) 意味着您必须执行整个操作 2、3 或更多次：

在此处输入图像描述

如果您的内存比 CPU 多，则可以并行计算三个单独的路径 - 需要三倍的内存：

在此处输入图像描述

但在所有现实世界的实现中，它是按顺序计算的，所需的计算量增加了三倍：

在此处输入图像描述

实际上，没有人选择过p除 以外的因素p=1。

理想的因素是什么？

  • 尽可能多的 RAM
  • 尽可能多的时间！

奖金表

以上的图形版本；你的目标是~250ms：

在此处输入图像描述

笔记：

  • 纵轴是对数刻度
  • 成本因子（水平）本身是对数（迭代次数 = 2 CostFactor）
  • 在r=8曲线中突出显示

并将上述版本放大到合理区域，再次查看~250ms 幅度：

在此处输入图像描述

奖金喋喋不休

  • 如果 scrypt 配置为使用小于 4 MB 的空间，则 scrypt 的密码存储比 bcrypt 弱 1
  • Argon2 (i/d/id) 在用于身份验证的密码散列方面比 bcrypt 弱（即 <1,000 毫秒验证时间）  2
于 2015-05-18T16:44:54.980 回答
14

我不想踩到上面提供的出色答案，但没有人真正谈论为什么“r”具有它所具有的价值。Colin Percival 的 Scrypt 论文提供的低级答案是它与“内存延迟-带宽乘积”有关。但这实际上意味着什么？

如果您正确使用 Scrypt，则应该有一个大内存块，该内存块主要位于主内存中。主内存需要时间来提取。当块跳跃循环的迭代首先从大块中选择一个元素以混合到工作缓冲区中时，它必须等待大约 100 ns 的时间才能让第一个数据块到达。然后它必须请求另一个，并等待它到达。

对于 r = 1，您将执行 4nr Salsa20/8 迭代和2n 延迟从主内存读取。

这不好，因为这意味着攻击者可以通过构建一个对主内存的延迟减少的系统来获得优势。

但是，如果您增加 r 并按比例减少 N，您就能够实现与以前相同的内存需求并执行相同数量的计算——除了您已经将一些随机访问换成了顺序访问。扩展顺序访问允许 CPU 或库有效地预取下一个所需的数据块。虽然初始延迟仍然存在，但后期块的减少或消除延迟将初始延迟平均到最低水平。因此，攻击者从改进他们的内存技术中获益甚微。

但是，随着 r 的增加，存在一个收益递减点，这与前面提到的“内存延迟-带宽乘积”有关。该产品表示的是在任何给定时间可以从主存储器传输到处理器的数据字节数。这与高速公路的想法相同——如果从 A 点行驶到 B 点需要 10 分钟（延迟），而道路从 A 点（带宽）以 10 辆/分钟的速度运送到 B 点，则 A 点和 B 点之间的道路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 对于内存技术而言似乎仍然是相当理想的，而且这显然在 8 年内没有太大变化；16可能会稍微好一点。
  2. 确定每个线程要使用多大的内存块，记住这也会影响计算时间，并相应地设置 N。
  3. 将 p 任意增加到您的使用可以容忍的程度（注意：在我的系统上并使用我自己的实现，p = 250（4 个线程），N = 16384 和 r = 8 需要约 5 秒），如果可以处理，请启用线程增加了内存成本。
  4. 调整时，更喜欢大的 N 和内存块大小，而不是增加 p 和计算时间。Scrypt 的主要优势在于其大内存块大小。

我自己在具有 i5-4300（2 核，4 线程）的 Surface Pro 3 上实现 Scrypt 的基准，使用常数 128Nr = 16 MB 和 p = 230；左轴是秒，下轴是 r 值，误差线是 +/- 1 标准偏差：

Scrypt r 值与具有恒定大块大小的 p

于 2015-10-23T08:31:18.533 回答