并行计算大型文件的哈希码是否比按顺序进行计算安全性低？

#1 楼

无论如何，如果您想使用Skein（SHA-3候选对象之一）：它具有用于树哈希的“操作模式”（配置变体），就像您的方法2一样。

它在操作内部进行此操作，因为在单个块上多次调用UBI。这在Skein规范文件（1.3版）的3.5.6节中进行了描述。



您将需要1 MB的叶子大小（因此，Y_l =对于512位变体为14，对于256为15，对于1024为13），最大树高Y_m = 2。 （该图显示了一个Y_m> = 3的示例。）

本文并未真正包含对树形哈希模式的任何密码分析，而是包含了该事实（甚至可能提及）用于密码哈希处理）似乎意味着作者认为它至少与“标准”顺序模式一样保存。 （在证明文件中也没有提及。）


从理论上讲：
在哈希函数中查找冲突的大多数方法都依赖于在哈希函数中查找冲突。底层压缩函数f：S×M-> S（它将先前的状态与数据块映射到新的状态）。

这里的冲突是其中之一：


一对消息和一个状态，使得f（s，m1）= f（s，m2）
两个状态对，一个消息块，使得f（s1， m）= f（s2，m）
一对消息和一对状态，使得f（s1，m1）= f（s2，m2）。

第一个是最容易利用的-只需修改消息的一个块，然后将所有其他块都设置为相同。

要使用其他块，我们还需要对前一个块的压缩功能进行前映像攻击，这通常被认为更加复杂。

如果我们遇到第一种类型的冲突，则可以在树版本以及顺序版本（即最低级别）中利用它。为了在较高级别上产生冲突，我们再次需要在较低级别上进行原像攻击。

因此，只要哈希函数（及其压缩功能）具有原像抵抗能力，树形版本就不会碰撞弱点要比“长流”之一。

#2 楼

实际上，您所描述的基于树的哈希（您的方法2）在某种程度上降低了对第二个原像的抵抗力。

对于具有$ n $位输出的哈希函数，我们期望抵抗力： />

冲突最多$ 2 ^ {n / 2} $，
第二个前映像最多$ 2 ^ {n / 2} $，
前映像最多$ 2 ^ n $。

这里的“工作量”是根据对简短的“基本”输入的哈希函数调用次数（对于SHA-256，按512位块进行数据处理，这是处理一个块的成本）。

让我们看一下第二个原像的情况：您有一个大文件$ m $，攻击者知道；攻击者的目标是找到一个不同于$ m $的哈希值相同的$ m'$。假设您使用了“方法2”，该方法将$ m $拆分为32768个子文件$ m_i $，分别对它们进行哈希处理，然后对串联的$ h（m_i）$进行哈希处理。如果攻击者发现与$ m_i $不同的$ m'_i $，但哈希值相同（对于$ i $的32768个值中的任何一个），攻击者将成功。这可以称为“多目标第二原像攻击”。因此，他可以尝试使用随机字符串，直到其中之一的哈希值与32768哈希值$ h（m_i）$之一匹配为止。攻击的有效成本为$ 2 ^ {n-15} $，这比具有$ n $位输出的良好哈希函数的预期$ 2 ^ n $要少。

（详细而言，由于攻击者需要他的$ m'_i $具有与$ m_i $相同的长度，因此在处理每个$ m_i $的第一个块之后，他将以SHA-256状态为目标，并使用随机的-阻止字符串。）

现在不要惊慌，$ 2 ^ {n-15} $仍然很高。确实，很容易看出，成功的第二次原像攻击必定意味着在树中某处发生了碰撞，因此电阻不会低于$ 2 ^ {n / 2} $，并且您使用的函数恰好具有256位输出，因此$ 2 ^ {n / 2} $太高了。

从密码学的角度来看，基于树的哈希函数所提供的功能还不如我们预期的给定输出大小所能提供的理论上最大的安全性好。这可以通过大多数情况下的修复，方法是将每个单独的哈希函数调用与即将处理的子文件的编号“合并”。正确的做法并不容易。在Skein规范中，如@Paŭlo所述，描述了一种基于树的哈希方法；可以避免我刚才详述的问题；但是，基于树的Skein不是作为SHA-3竞争的一部分而研究的“ the Skein”（“ SHA-3候选Skein”纯粹是顺序的），因此尚未受到外界的广泛审查。同样，“ the” Skein本身仍然是一种新设计，我个人建议不要匆忙处理。可以通过年老获得安全性。

作为补充，Skein优于SHA-256的速度优势取决于所使用的体系结构。特别是在32位系统上，Skein运行缓慢。最近的x86处理器具有SSE2单元，即使在32位模式下也可以提供64位计算，因此，只要使用本机代码（带有内在函数或汇编语言的C），Skein在过去几年的任何PC上都可以快速运行。在其他架构上，情况也不尽如人意。例如，在ARM处理器（甚至是智能手机或平板电脑中最新的大型处理器）上，SHA-256将比Skein快2至3倍。实际上，在32位MIPS和ARM平台上，以及在32位x86处理器上运行的纯Java实现上，SHA-256的速度要比所有其他SHA-3候选速度更快（请参阅此报告）。

#3 楼

修订：提议的构造很好，尤其是：



至少具有与SHA-256一样安全的抵御碰撞攻击的能力，这就是对手使用以下命令构造两个文件的能力：相同的散列；
对于第一和第二原像攻击而言，其安全性几乎与SHA-256一样，这是指对手能够构造（对于第一原像）具有任意散列值的文件（对于第一原像），或者（对于第二个原图像）具有与任意给定文件相同的哈希值的文件。

该构造会稍微降低最大抵抗哈希值的第二个原图像抵抗力。但是对于SHA-256，第二原像的抵抗力似乎仍然不比对RD Dean在其1999年论文中提出的Merkle-Damgård散列的一般攻击所允许的允许的差（第5.3.1节），J。Kelsey对其进行了更好地暴露和完善。和B. Schneier在关于$ n $位哈希函数的第二张原像中，其工作量不到$ 2 ^ n $。

#4 楼

方法2的安全性不亚于方法1。

这是为什么：散列函数具有的密码属性是，在计算上无法找到任何两个散列为相同值的不同原像，这在计算上是不可行的。方法1直接依赖于此。但是，如果我们想举一个与方法2发生冲突的示例，则意味着：


两次运行之间对最终哈希的输入有所不同（在这种情况下，因为我们有两个输入实例导致完全相同的输出，所以这是基础哈希函数的冲突），或者
最终哈希的输入完全相同（所以，因为输入在某处有所不同） ，这意味着至少有一个初始哈希具有不同的输入但具有相同的输出，再次说明，这是基础哈希函数的冲突。

在两种情况下，我们都可以恢复冲突，这表明哈希函数不像我们希望的那样具有抗冲突性，而且如果我们在方法1中将这两个输入用作文件，方法1也将遭受冲突。

#5 楼

就碰撞而言，方法2的安全性是否比方法1的安全性低？



您正在产生更多的值，这些值可以用于尝试碰撞，但是如果您选择足够大的哈希空间，则其区别与海洋中的分子与海洋中的液滴之间的区别是相同的。...完全不必担心！

#6 楼

如果哈希函数适用于一般用途，则适用于此用途。只要攻击者无法找到两个散列为相同值的二进制字符串，您的方法就是安全的。如果您不确定所使用的哈希算法是否正确，则选择了错误的算法。

说攻击者有32,768次机会可以找到冲突，因此比较容易，这是无效的。通过一次尝试32,768种不同的可能输入，他可以轻松地为单个二进制图像查找冲突。没有理由期望某些障碍会比其他障碍强或弱，因此没有理由认为更多的机会会使其变得更容易。 （因为他可以复制，所以还是只有一次机会。）

#7 楼

拖曳方法具有大致相同的安全性。在SHA-2和其他加密哈希函数中，消息分为512位块。提到PaŭloEbermann的好方法可以提供更高的安全性。如果方法1是安全的，则没有已知的针对方法2的攻击。<​​br />
编辑：
@Pornin描述：


攻击将是$ 2 ^ {n-15} $，小于对于具有$ n $位输出的良好哈希函数的预期$ 2 ^ n $。


和


阻力不会低于$ 2 ^ {\ frac {n} {2}} $