SHA-256d中的“弱点”？

SHA-256d(x) = SHA-256(SHA-256(x))

#1 楼

这开始是对CodeinChaos答案的评论，但不适合。我试图以通俗的方式反省我对他引用的论文中\\ operatorname {SHA-256d} $的后果的理解：Yevgeniy Dodis，Thomas Ristenpart，John Steinberger，Stefano Tessaro：要哈希还是不要哈希再次？ H2和HMAC的可分性结果（在Crypto 2012中进行）。

本文并不暗示我们可以通过随机选择来确定一个具有$ 256 $位输入的黑盒是否具有较大的优势。并且输出是一个随机Oracle，或者使用$ 2 ^ {64} $对那个黑匣子的查询来实现$ \ operatorname {SHA-256d} $，而不知道$ \ operatorname {SHA-256} $使用的初始化值（假设它被一个随机的$ 256 $位值代替），并且使用的计算工作量比破译$ \ operatorname {SHA-256} $的可能性要小得多。换句话说，$ \ operatorname {SHA-256d} $在该术语的标准定义中仍然是安全的伪随机函数。标准论点证明了这一点：一个能够破坏$ \ operatorname {SHA-256d} $的区分符（在该定义中）可以变成一个能够以仅两倍查询量就能破坏$ \ operatorname {SHA-256} $的标识符。

尽管如此，本文显示，我们可以设计涉及哈希的协议，在这种协议中，使用$ \ operatorname {SHA-256} $是安全的；但是使用$ \ operatorname {SHA-256d} $是完全不安全的（只需花费很少的精力，而不是$ 2 ^ {64} $）。此协议的一个示例旨在提供相互证明，即每一方都对$ 256 $位哈希函数$ H $进行了最小数目的求值（注意：Alice执行奇数步，而下一个偶数步由Bob用角色已颠倒）：


Alice抽取一个随机的$ 256 $位$ A_0 $并将其与最小数$ k_A \ in [2 ^ 8..2 ^ {18}] $$她希望小鲍执行的$ H $的评估；
Bob随机抽取了$ 256 $位$ B_0 $并将其与他希望Alice进行的$ H $评估的最小数量$ k_B \ in [2 ^ 8..2 ^ {18}] $一起发送给Alice。执行;
爱丽丝将$ \ hat B_0 $和$ \ hat k_B $设置为她在步骤2中获得的值。如果$ \ hat k_B> 2 ^ {18} $;
鲍勃将$ \ hat A_0 $和$ \ hat k_A $设置为他在第1步中获得的值，并且如果$ \ hat k_A> 2 ^ {18} $失败，则协议终止并失败，
Alice重复$ j = 1 \ dots \ max（k_A，\ hat k_B）$：


如果$ A_ {j-1} = B_0 $，则以失败终止协议；
计算$ A_j = H（A_ {j-1}）$;
计算$ \ hat B_j = H（\ hat B_ {j-1}）$;


Bob重复$ j = 1 \ dots \ max（k_B，\ hat k_A）$：


如果$ B_ {j-1} = A_0 $，则以失败终止协议；
计算$ B_j = H（B_ {j-1}）$;
计算$ \ hat A_j = H（\ hat A_ {j-1}）$;


爱丽丝向鲍勃发送$ \ hat B _ {\ hat k_B} $；
鲍勃向艾丽斯发送$ \ hat A _ {\ hat k_A} $；
如果爱丽丝在第8步得到了什么。与$ A_ {k_A} $，s不同他因失败而终止协议；否则，她宣布成功；
如果Bob在步骤7中得到的与$ B_ {k_B} $不同，则他以失败终止协议；

当$ H $是$ \ operatorname {SHA-256} $时，此协议对于Alice和Bob都是安全的。但是，如果$ H $是$ \ operatorname {SHA-256d} $，定义为$ x \ mapsto \ operatorname {SHA-256}（\ operatorname {SHA-256}（x））$，则有一个简单的“镜像”攻击Bob：


在步骤2，Bob计算并发送$ B_0 = \ operatorname {SHA-256}（A_0）$和$ k_B = k_A-1 $，其中$ A_0 $和$ k_A $是他在第1步中得到的；这将通过爱丽丝在步骤3进行的测试。并通过她在第5步执行的测试，并且失败的几率几乎可以忽略不计，就像鲍勃随机选择$ B_0 $一样；
在第8步，鲍勃计算并发送$ \ operatorname {SHA-256 }（\ hat B _ {\ hat k_B}）$其中$ \ hat B _ {\ hat k_B} $是他在第7步中得到的；这将始终通过爱丽丝在步骤9进行的测试！！

通过绕过Alice在步骤5进行的测试，此策略使Bob显然可以通过对$ \ operatorname {SHA-256d} $的单个评估的计算工作来履行职责。选择$ B_0 $作为$ A_j $中的一个，这样他的大部分工作实际上就可以由爱丽丝完成。


本文（以及上面的示例，是从论文）隐含着从Oracle不可区分性的定义到足以支持某些协议（尤其是相互工作量证明协议）的安全性证明的前提下，假设该协议使用的哈希是安全的，则不可区分性$ H ^ 2：x \ mapsto H ^ 2（x）= H（H（x））$并非来自$ H $的不可微性。

这特别表明a的定义作为伪随机函数家族的随机公共成员，几乎是安全的哈希，其特征在于：“即使计算上不受限制的对手也无法分散nguish，相对于随机选择，它具有恒定的积极优势，如果具有$ n $位输出的黑盒实现了该家庭的随机成员或RO，并且对$ n $的黑盒多项式有许多查询”（或：“渐近小于生日界限$ O（n ^ {1/2}）$”）不是一种适合用来证明此类协议的实际安全性的安全性度量。

本文进行到表明$ \ bar H（x）= H（H'（x））$其中$ H'$是$ H $的变体，与RO不可区分，假设$ H $和$ H'$在a下

一种看待这种情况的方法是，PRFF的两个随机成员的组成是安全的，但是两次相同随机成员的组成是不安全的一个可以访问实现该随机成员的Oracle的对手，这在实践中是不可避免的。

更新：尽管BitCoin涉及使用哈希和$ \ operatorname {SHA-256d} $的工作量证明，但是如果由于使用哈希而遭受破坏性攻击，我将感到非常惊讶。

#2 楼

从一个随机的oracle（本质上是一个理想的散列）中区分$ H ^ 2 $比它应该便宜得多，即$ \ ^ {64} $ for $ \ operatorname {SHA-256d} $。这不会导致任何实际的攻击，但是会损害难以区分的安全证明。通过为内部和外部哈希使用不同的前缀来避免此问题很容易，因此我几乎没有理由在实践中使用$ H ^ 2 $。

从随机Oracle中区分SHA-256d

$ \ operatorname {SHA-256d}（m）= \ operatorname {SHA-256}（\ operatorname {SHA-256}（m））$是$ H ^ 2（m ）= H（H（m））$构造，因此$ H ^ 2 $的所有通用弱点也适用于$ \ operatorname {SHA-256d} $。

Dodis，Y. ，Ristenpart，T.，Steinberger，J。和Tessaro，S。（2012）。要哈希还是不哈希？ H2和HMAC的（输入）微分结果。表示可以使用$ 2 ^ {n / 4} $个查询将$ H（H（m））$与一个随机的oracle进行区分。

便宜的区分符并不意味着存在实际的攻击。该论文的作者说，他们“没有意识到使用H2或HMAC会导致漏洞的任何已部署密码应用程序。”但是，如果您有安全证明，依靠不可区分的散列，那么使用SHA256d而不是理想的散列，证明的安全性要弱得多。

避免区分符

可以避免通过对内部和外部哈希使用两个不同的前缀来进行这种攻击。 HMAC对内部和外部哈希使用两个不同的键，从而导致键的前缀明显短于块大小。这就是SHA-256d的一种替代选择是使用具有固定密钥的HMAC-SHA-256。另一种选择是$ H ^ 2（0 ^ d || m）$，其中$ d $是哈希的输入块大小。

#3 楼

立即想到的唯一一件事就是，即使您知道某些字符串X的SHA-256d，也可以计算字符串SHA256（X）的SHA-256d，即使您不了解X的其他知识。

从某种意义上讲，这类似于“长度扩展”攻击，因为它允许您在给定Hash（X）的情况下为某些函数F计算Hash（F（X））。

这对您的哈希函数来说是否是关键问题取决于您使用哈希函数的目的。如果它代替随机Oracle，可能是理论上的问题；如果在签名方案中使用它，则可能不是问题。