我想提高哈希大文件的性能，例如数十亿字节 .
通常，您使用散列函数依次散列文件的字节（例如，SHA-256，尽管我很可能会使用Skein，因此与从[来自[]读取文件所花费的时间相比，散列会更慢 . 快] SSD） . 我们称之为方法1 .
这个想法是在8个CPU上并行地散列文件的多个1 MB块，然后将连接的散列散列为单个最终散列 . 我们称之为方法2 .
描绘此方法的图片如下：
我想知道这个想法是否合理，以及在整个文件的 Span 上执行单个散列时，失去了多少“安全性”（就碰撞而言更可能） .
例如：
让我们使用SHA-2的SHA-256变体，并将文件大小设置为2 ^ 34 = 34,359,738,368字节 . 因此，使用简单的单一传递（方法1），我将获得整个文件的256位哈希 .
比较这个：
使用并行散列（即方法2），我会将文件分成32,768个1 MB的块，使用SHA-256将这些块散列为32,768个256位（32字节）的哈希值，连接哈希值并进行最终哈希结果连接的1,048,576字节数据集，以获得整个文件的最终256位哈希值 .
方法2是否比方法1更不安全，因为碰撞更可能和/或可能？也许我应该将这个问题重新解释为：方法2是否使攻击者更容易创建一个哈希值与原始文件相同的哈希值的文件，当然除了蛮力攻击因此更便宜的琐碎事实 . hash可以在N cpus上并行计算？
Update ：我刚刚发现方法2中的构造非常类似于hash list的概念 . 然而，与方法1相比，前一句中链接引用的维基百科文章没有详细说明哈希列表在冲突机会方面的优势或劣势，方法1是文件的普通旧哈希，只有顶部哈希使用哈希列表 .
3 回答
基于块的散列（您的方法2）是一种在实践中使用的众所周知的技术：
Hash tree, Merkle tree, Tiger tree hash
eDonkey2000文件哈希（单层树，块大小约为9 MiB）
就像你正在做的那样，这些方法再次采用块哈希和哈希列表，直到单个短哈希 . 由于这是一个成熟的做法，我认为它与顺序散列一样安全 .
一些现代哈希设计允许它们并行运行 . 见An Efficient Parallel Algorithm for Skein Hash Functions . 如果您愿意使用新的（因而不太全面测试）哈希算法，这可能会使您在多处理器计算机上获得所需的速度提升 .
Skein已经到了NIST SHA-3 competition的最后阶段，所以它并没有完全未经测试 .
我认为攻击者发现冲突要容易得多，因为生成哈希所需的时间是要散列的数据大小的函数 . 密码安全哈希的一个好处是，攻击者无法获取您的100Gb文件，找到他们想要变异的地点，在该块之前和之后散列所有内容，然后使用这些预先计算的值来快速获取哈希值在对他们感兴趣的位进行小/快排列后的整个文件 . 这是因为在散列算法中有一个重叠的滑动窗口 .
简而言之，如果编辑文件的中间部分，则仍需要散列整个文件以获得最终的校验和 . 因此，100Gb文件比100字节文件需要更长的时间来查找冲突 . 例外情况是编辑在文件末尾是无意义的，这就是为什么在大型文件的碰撞示例中经常出现“in-the-wild”的原因 .
但是，如果将原始文件分解为块，则攻击速度现在是最小块（或要变异的块的大小）的函数 . 由于文件大小随着散列时间线性增加，因此对于每个排列/ MD5，100Gb文件将花费大约2000秒，而1Mb块将允许攻击者尝试50 per second .
解决方案是将文件分成重叠块，然后单独MD5那些块 . 结果散列将是从开始到结束顺序和结束到开始的散列的串联 . 现在发现碰撞需要对整个文件进行哈希处理 - 尽管是以并行方式进行 .