并行计算大文件的哈希码

Question

我想提高哈希大文件的性能,例如数十亿字节.

通常,您使用散列函数依次散列文件的字节(例如,SHA-256,尽管我很可能会使用Skein,因此与从[来自[]读取文件所花费的时间相比,散列会更慢.快] SSD).我们称之为方法1.

这个想法是在8个CPU上并行地散列文件的多个1 MB块,然后将连接的散列散列为单个最终散列.我们称之为方法2.

描绘此方法的图片如下:

在此输入图像描述

我想知道这个想法是否合理,以及在整个文件的跨度上执行单个散列时,失去了多少"安全性"(就碰撞而言更可能).

例如:

让我们使用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上并行计算？

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

Answer 1

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

就像你正在做的那样,这些方法再次采用块哈希和哈希列表,直到单个短哈希.由于这是一个成熟的做法,我认为它与顺序散列一样安全.

Answer 2

一些现代哈希设计允许它们并行运行。请参阅Skein 哈希函数的高效并行算法。如果您愿意使用新的（因此测试较少）哈希算法，这可能会为您提供多处理器机器上所需的速度提升。

Skein 已进入NIST SHA-3 竞赛的最后阶段，因此并非完全未经测试。