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

Question

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

我正在使用Java scrypt库进行密码存储.当我加密东西时N,它需要一个r和p值,其文档称为"CPU成本","内存成本"和"并行化成本"参数.唯一的问题是,我实际上并不知道它们的具体含义,或者对它们有什么好的价值; 也许他们以某种方式对应于Colin Percival原创应用中的-t,-m和-M开关？

有人对此有任何建议吗？图书馆本身列出N = 16384,r = 8和p = 1,但我不知道这是强还是弱或是什么.

Answer 1

gim*_*mpf 65

作为开始:

cpercival提到在他的幻灯片,从2009年的东西约

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

即使在今天(2012-09),这些值恰好足以用于一般用途(某些WebApp的密码-db).当然,细节取决于应用程序.

此外,这些值(大多数)意味着:

N:一般工作因素,迭代计数.
r:blocksize用于底层哈希; 微调相对内存成本.
p:并行化因子; 微调相对cpu-cost.

r并且p旨在适应CPU速度和内存大小和带宽不会如预期那样增加的潜在问题.如果CPU性能增加得更快,你p应该增加,而应该是内存技术的突破提供一个数量级的改进,你增加r.而且N是有跟上的每场演出一般加倍一些时间跨度.

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

顺便说一下,scrypt参数会自动存储在生成的密钥中,因此不需要单独存储.这意味着随着时间的推移,当密码存储中的用户密码中的参数具有不同的值时,并且当用户更改其密码时,将使用当前参数值生成密钥(=哈希密码). (27认同)
"顺便说一句,scrypt参数会自动存储在生成的密钥中,因此它们不需要单独存储." - 只是为了澄清(对于其他读者)这只适用于Java实现.scrypt标准和其他实现不需要将成本/参数与结果散列一起存储. (4认同)
感谢您指出了这一点; 我没有意识到链接的Java实现以一种理智的方式实现了这一点. (2认同)
只是为了澄清 @elithrar 的评论，Colin Percival 本人（scrypt 的作者）使用的格式将工作因素存储在结果密钥中（详见 http://security.stackexchange.com/questions/88678#answer-91050） (2认同)
@elithrar [scrypt paper](https://www.tarsnap.com/scrypt/scrypt.pdf)没有详细列出格式(在定义4,p11中提出),但可以在[代码](https://github.com/Tarsnap/scrypt/blob/e0e65f457ad74d1d14092ddfd69343c1c6d9c550/lib/scryptenc/scryptenc.c#L224)或更有用的科林[格式规范](https://github.com/Tarsnap/scrypt/blob/master/FORMAT)(对于迟到的回复感到抱歉). (2认同)

Answer 2

Ian*_*oyd 54

scrypt操作所需的内存计算如下:

128字节N_cost××r_blockSizeFactor

对于参数你引用(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(Ñ)同时增加内存使用和迭代.
的blockSizeFactor([R )增加的内存使用情况.

剩下的参数parallelization(p)意味着你必须完成2,3或更多次的整个事情:

在此输入图像描述

如果你有比CPU更多的内存,你可以并行计算三个独立的路径 - 需要三倍的内存:

在此输入图像描述

但在所有实际实现中,它是按顺序计算的,所需的计算增加了三倍:

在此输入图像描述

实际上,没有人选择过p其他因素p=1.

什么是理想因素？

尽可能多的RAM
尽可能多的时间!

奖金图表

以上图形版本:

笔记:

垂直轴是对数刻度
成本因子(水平)本身是log(迭代= 2 ^CostFactor)
在r=8曲线中突出显示

并将以上版本放大到合理区域:

@Tron我会猜测,因为有一点它将内存复制到另一个缓冲区(即将16MB传递给PBKDF2,后者执行实际的最终密钥推导). (2认同)

Answer 3

Nic*_*uer 11

我不想踩到上面提供的优秀答案,但没有人真正谈论为什么"r"具有它的价值.Colin Percival的Scrypt论文提供的低级答案是它与"内存延迟 - 带宽产品"有关.但这究竟意味着什么呢？

如果你正在做正确的Scry,你应该有一个大的内存块,它主要位于主内存中.主存储器需要时间来拉动.当块跳转循环的迭代首先从大块中选择一个元素以混合到工作缓冲区时,它必须等待100ns的量级才能到达第一块数据.然后它必须请求另一个,并等待它到达.

对于r = 1,你将从主内存进行4nr Salsa20/8次迭代和 2n次延迟读取.

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

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

然而,随着r的增加,存在收益递减点,这与之前提到的"存储器延迟 - 带宽积"有关.该产品表示在任何给定时间可以从主存储器传输到处理器的数据字节数.它与高速公路的想法相同 - 如果从A点到B点(延迟)需要10分钟,并且道路从A点(带宽)到A点之间的道路提供10辆车/分钟,A点和A点之间的道路B包含100辆汽车.因此,最优r与您可以一次请求多少64字节数据块有关,以便掩盖初始请求的延迟.

这提高了算法的速度,允许您根据需要增加N以获得更多内存和计算,或增加p以进行更多计算.

还有一些其他问题,增加"r"太多,我没有看到太多讨论:

在减小N的同时增加r会减少内存周围的伪随机跳转次数.顺序访问更容易优化,并且可以为攻击者提供一个窗口.正如Colin Percival在Twitter上向我指出的那样,更大的r可能允许攻击者使用更低成本,更慢的存储技术,大大降低其成本(https://twitter.com/cperciva/status/661373931870228480).
工作缓冲区的大小为1024r位,因此最终将被送入PBKDF2以生成Scrypt输出密钥的可能最终产品的数量为2 ^ 1024r.大存储块周围跳跃的排列(可能序列)的数量是2 ^ NlogN.这意味着内存跳跃循环有2 ^ NlogN个可能的产品.如果1024r> NlogN,那似乎表明工作缓冲区正在混合不足.虽然我不确定这一点,并且希望看到证据或反证,但它可能会可以在工作缓冲区的结果和跳转序列之间找到相关性,这可以使攻击者有机会减少他们的内存需求而不会大大增加计算成本.同样,这是一个基于数字的观察 - 可能是每一轮中的一切都如此混合,这不是一个问题.对于标准N = 2 ^ 14,r = 8远低于该潜在阈值 - 对于N = 2 ^ 14,该阈值将是r = 224.

总结所有建议:

选择r足够大,可以平均设备内存延迟的影响,而不是更多.请记住,Colin Percival建议的值r = 8,对于内存技术来说似乎仍然是相当优化的,并且这显然在8年内没有太大变化; 16可能会稍微好一些.
确定每个线程要使用多大的内存,记住这也会影响计算时间,并相应地设置N.
将p任意增加到你的使用可以容忍的值(注意:在我的系统上并使用我自己的实现,p = 250(4个线程),N = 16384,r = 8需要~5秒),并启用线程,如果你可以处理增加了内存成本.
调整时,更喜欢大N和内存块大小,以增加p和计算时间.Scrypt的主要优势来自其大容量内存块.

我在Surface Pro 3上使用i5-4300(2核,4个线程)实现Scrypt的基准测试,使用常数128Nr = 16 MB和p = 230; 左轴为秒,底轴为r值,误差棒为+/- 1标准偏差:

归档时间：	13 年，4 月前
查看次数：	12703 次
最近记录：	9 年，9 月前