$ U_1 = PRF(密码,盐)$
$ U_2 = PRF(密码,U_1)$
…
$ U_n = PRF(密码,U_n-1)$
然后标准定义实际关键材料
K
as $ K = F(密码,盐,n)$
其中F是$ U_1 \ oplus U_2 \ oplus \ cdots U_n $
我不明白将块进行XOR的目的是什么。假设PRF是一种加密功能强大的功能,对这些块进行XOR运算有何帮助?为什么$ U_n $本身不能提供足够强的密钥材料?
该标准提到将块进行XORd“以减少对递归退化为一小部分值的担忧”,但我想我不知道因为每次迭代都会将密码反馈到函数中,所以不知道怎么回事。
如果递归可以退化为一小部分值,那并不意味着会出现短暂的情况。哈希函数中循环?
(1)为简单起见,假设密钥与哈希函数输出的长度相同。
#1 楼
XOR实际上是为了防止假设的短周期。对于给定的密码$ P $,$ U_i $的序列应构成“ rho”结构:在序列中的某个点输入一个循环。对于$ n $位的散列函数和随机密码,平均而言,将存在一个大小约为$ 2 ^ {n / 2} $的单个“大”循环,对于几乎所有可能的盐值,该循环将在跟随平均长度为$ 2 ^ {n / 2} $的“队列”。但是,可能存在中央周期小于该周期的密码,并且还可能存在一些额外的较小周期。找到一个产生较小的中央周期的密码,或者找到一个盐值导致另一个较小的周期,这是极其困难的,并且尚无已知的例子。但是PBKDF2设计人员认为XOR是应对这种风险的一种廉价方法:实际上,这意味着$ U_i $将取决于队列以及周期本身。这里有一个潜在的重要意义:应用PRF时,即从$ U_i $跳到$ U_ {i + 1} $时,空格“缩小”:并非所有$ n $位值都可以作为输出PRF。您走得越远,空间缩小得越多,直到达到“中心周期”。这意味着如果$ F $仅使用$ U_c $(最后一个$ U $值),则生成的$ n $位密钥块的空间将小于$ 2 ^ n $;换句话说,您将使用具有$ n $位输出的哈希函数,而不会获得价值$ n $位的安全性。 XOR旨在抵消这种影响。
但是,据我所知,PBKDF2结构从未以任何方式得到证明,因此,我建议仅将其与输出$ 2n $的哈希函数一起使用位,如果要实现$ n $位安全性。例如,对于128位安全性(合理的级别),请使用SHA-256。因此,无论额外的XOR是否真的有益,大的中央周期大小本身就足够了。
评论
$ \ begingroup $
前几天我瞥了一眼,就像在HMAC上使用时一样,组合的内部结构将使攻击者可以预先计算(k ^ ipad)和(k ^ opad)哈希块他的字典,因为它们仅取决于密码。因此,攻击者可以在防御者的天真实施中节省与(输出块数+ 1)成比例的工作。这可能是允许使用非迭代HMAC密钥的故意设计,但似乎没有记录在案。
$ \ endgroup $
–沼泽雷
2011年8月3日,0:16
$ \ begingroup $
空间的确缩小了,但实际上不足以解决这个问题(可以证明)。同样,周期的长度为2 ^ n / 2,但实际上这并不重要。可以证明,如果PRF是安全的,那么它不可能偶然碰到足够短的周期而导致安全问题(对于典型的参数选择)。当然,如果PRF不安全,那么所有赌注都将失效-但是,如果PRF,即使使用XOR,构造也可能不安全,因此您应该采取一切可能的措施来确保PRF是安全的。
$ \ endgroup $
– D.W.
2011年8月15日下午4:09
$ \ begingroup $
@Thomas Pornin +1好帖子,为什么您对证明PBKDF2没有兴趣?也许您不依赖它。
$ \ endgroup $
–浏览
2011年8月17日在17:09
$ \ begingroup $
您能进一步解释什么是“ rho”结构吗?似乎有悖常理,这是针对短周期的有力保护。如果存在某些$ U_n,U_ {n + 1},\ cdots,U_ {n + k-1},U_ {n + k} $,则$ U_ {n + k + 1} $ = $ U_ {n} $,它们的XOR模式将循环遍历从$ U_ {n} $开始的$ 2k $个唯一值,这似乎是微不足道的。
$ \ endgroup $
–斯蒂芬·托瑟(Stephen Touset)
2014年6月11日,0:17
#2 楼
@ D.W。可能最接近真正的原因(这是15年前,所以事情变得有点朦胧),人们担心周期短,而且实际上是免费的-您已经在故意地进行哈希处理以减慢速度这不是问题-为什么不这样做?您还必须记住历史背景,在考虑替换PKCS#5v1时,HMAC还不存在,因此您不能只写一个黑框,上面写有“具有某些可证明属性的PRF”。它。例如,这是从那时起的一个概念:key = {};
state = hash( algorithm, mode, parameters, userKey );
for count = 1 to iterations
state = hash( state );
key ^= hash( state || userKey );
请注意,由于缺少HMAC,因此(顺便说一句,算法参数哈希的原因是在40位RC4密钥上进行密钥恢复(还记得吗?),如果您重复盐操作,也不会恢复大部分56位DES密钥,这是多次发生的错误。 >
@Marsh:也是。 Hans Dobbertin的RIPEMD-160双管设计刚刚问世,这具有一定的影响力。长期运行的is-DES-a-group问题引起的另一个问题是,是否可以将迭代哈希H()折叠成单个哈希H'()。在每个哈希步骤提取数据将防止这种情况。总体而言,这是很久以前的事,各种各样的想法都被提出来了,所以把导致这一点的可能性分离开来。
注意:我不是作者PKCS#5v2,当时我只是参与KDF的讨论。
#3 楼
老实说,没有充分理由需要XOR。我的怀疑是,设计师很可能将其包括在内,因为他们认为“嘿,为什么不呢?它不会受伤”。但是,如果设计者不进行XOR,一切都会很好。特别是,如果PRF()是安全的伪随机函数,并且如果我们坚持使用典型参数,那么您是对的:我们不需要XOR之类的东西,只需要使用U_n就可以了。
就像@Thomas Pornin提到的那样,人们可能会担心周期短或熵损失。事实证明,如果PRF是一种安全的伪随机函数(并且如果我们避免在实践中没人会使用的时髦的参数选择),那么可以证明这不是问题。因此,设计人员使用U_n是完全合理的。
现在我可以想象某些设计人员可能会说,嘿,如果PRF出现缺陷,那么可能是短周期或熵损失可能成为问题;为了解决这种可能性,最好有一些后备,并且即使PRF有缺陷,异或也可以提供一些后备保护。我可以想象有些设计师会这样想。我不知道有任何正式的依据来支持这一点(我不知道有任何确凿的证据表明,如果PRF有缺陷,那么XOR可能会更安全),但是我也不知道任何反对这一建议的正式依据。因此,这似乎是一种无害的变体。这可能有助于安全性。我不会依靠它来帮助提高安全性,而且我们也不知道它是否真的有帮助,但是,嘿,为什么不便宜呢?而且,如果PRF确实是安全的,那么它不会对任何事物造成损害。他们本可以省去XOR,而只使用U_n,那也可以。在PRF意外失败的情况下,这很可能只是一个微调,以尝试优化该方案的安全性。
(还有另一种可能性。另一种可能性是设计者感到困惑:即,如果PRF是安全的,那么设计者并不了解表明在实践中短周期和熵损失并不是问题的结果,并且错误地认为仅使用U_n是不安全的。我认为这是有可能的。但是,当有另一种很好的解释时,我不愿意无知。
#4 楼
我同意你的看法。 XOR似乎毫无意义。哈希链中的短周期似乎比哈希/ XOR链中的短周期更不可能也不太可能。如果一个可以退化为序列,而其他迭代不会更改该值,那么另一个也可以。如果一个不能,则另一个也不能。评论
$ \ begingroup $
我不能说,我知道这是“完全没有意义的”,但是无论有没有XOR,短周期肯定会以相同的速率出现...我想密码学家有时只是喜欢XOR。
$ \ endgroup $
–艾姆·尼克(Iam Nick)
16年1月19日,下午5:20
#5 楼
抛开这是否有用的问题,我的理论是PBKDF2的设计人员熟悉从MD5到SHA-1的设计更改,并认为引入像SHA这样的并行数据通道可能会有所帮助-1键扩展数组(也用XOR构造)。 XOR的开销可忽略不计,使PBKDF1上数据流图最窄部分的带宽增加了一倍。当时这似乎不太可能造成伤害,甚至可能会带来一点安全。#6 楼
我不同意其他答案,因为我认为对块进行XOR是有用的添加,无论其最初放置的原因是什么。假设我们将KDF定义为PBKDF2,但采用最后一块而不是所有块的XOR。让我们忽略多块支持并将其简单定义为:
$$ \ begin {align}
U_1(p,s)&= H_p(s)\\
U_i (p,s)&= H_p(U_ {i-1}(p,s))\ \ || \ i> 1 \\
K(p,s)&= U_n(p,s)
\ end {align} $$
现在,我们有盐$ s $的原因是我们想要$ K(p,s_1)\ not = K(p,s_2) $当人们使用相同的密码时。
给出$ s_1 \ not = s_2 $和$ P(H_p(s_1)= H_p(s_2))= 2 ^ {-b} $,我们得到:
$$ \开始{align}
P(U_1(p,s_1)&\ not = U_1(p,s_2))= 1-2 ^ {-b} \\
P(U_2(p,s_1)&\ not = U_2(p,s_2))=(1-2 ^ {-b})^ 2 \\
P(U_3(p,s_1)&\ not = U_3(p,s_2))=(1-2 ^ {-b})^ 3 \\
... \\
P(U_n(p,s_1)&\ not = U_n(p ,s_2))=(1-2 ^ {-b})^ n \ approx 1-n * 2 ^ {-b} \\
\ end {align} $$
如果$ n = 2 ^ k $,则在两次使用同一密码之间发生冲突的可能性为$ 2 ^ {kb} $。至少这意味着给定两个具有相同密码散列的用户,您可以猜测他们具有相同的密码。而且这在全球范围内适用,而与特定地点的盐或胡椒粉无关,因为已经假定这些盐是不同的。
即使HMAC-SHA-256的大小,甚至是HMAC-SHA-1( –原来的定义中使用)–实际使用$ k $时实际上没关系,添加的迭代次数越多,哈希就越弱。
现在,假设爱丽丝(Alice)正在尝试蛮力破解庞大的密码数据库。可以将每个猜测与所有密码哈希进行比较,因为如果匹配一个,则很可能是相同的密码,因为发生这些冲突的可能性更大。因此,密码哈希不能达到必须独立攻击密码的目的。
评论
我想知道为什么他们不同时为U_i散列计数器i?反馈密码并不会消除存在某些$ U_n $,$ U_ {n + 1} $的可能性,使得$ U_ {n} = PRF(password,U_ {n + 1})$周期短)。
据我了解,当我们使用一个哈希值,一个哈希值...时,我们确实的确以循环结束。平均周期长度似乎接近生日,但确实如史蒂芬所说,对于给定的状态,它最终可能会非常短。