cryptography - 并行计算大文件的哈希码

Question

我想提高对大文件(例如数十 GB 大小)进行哈希处理的性能。

通常，您使用散列函数(例如 SHA-256，尽管我很可能会使用 Skein)顺序散列文件的字节，因此与读取文件所需的时间相比，散列会更慢来自[快速] SSD)。我们将此称为方法 1。

这个想法是在 8 个 CPU 上并行散列文件的多个 1 MB block ，然后将连接的散列散列为单个最终散列。我们将此称为方法 2。

描述此方法的图片如下:

<小时/>

<小时/>

我想知道这个想法是否合理，以及与在整个文件范围内执行单个哈希相比，损失了多少“安全性”(就更有可能发生冲突而言)。

例如:

让我们使用 SHA-2 的 SHA-256 变体，并将文件大小设置为 2^34=34,359,738,368 字节。因此，使用简单的单遍(方法 1)，我将获得整个文件的 256 位哈希值。

比较一下:

使用并行哈希(即方法 2)，我会将文件分成 32,768 个 1 MB 的 block ，使用 SHA-256 将这些 block 哈希为 256 位(32 字节)的 32,768 个哈希，连接哈希并执行生成的串联 1,048,576 字节数据集的最终哈希值，以获得整个文件的最终 256 位哈希值。

就碰撞可能性更大和/或可能而言，方法 2 是否比方法 1 安全性较低？也许我应该将这个问题改写为:方法 2 是否使攻击者更容易创建一个散列到与原始文件相同的散列值的文件，当然除了一个简单的事实，即暴力攻击会更便宜，因为hash可以在N个cpu上并行计算吗？

更新:我刚刚发现我在方法 2 中的构造与 hash list 的概念非常相似。 。然而，前一句中的链接引用的维基百科文章并没有详细说明哈希列表在冲突机会方面与方法 1 相比的优越性或劣势，方法 1 是文件的普通旧哈希，当只有 使用哈希列表的顶部哈希。

Answer 1

基于 block 的散列(您的方法 2)是一种众所周知的技术，已在实践中使用:

• Hash tree, Merkle tree, Tiger tree hash
• eDonkey2000 文件哈希(单级树， block 大小约为 9 MiB)

就像您正在做的那样，这些方法获取 block 哈希列表并再次哈希，直到单个短哈希。由于这是一种行之有效的做法，我认为它与顺序散列一样安全。