我想提高散列大文件的性能,例如大小为数十 GB 的文件。
通常,您使用散列函数(例如 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 将这些块哈希为 256 位(32 字节)的 32,768 个哈希,连接哈希并进行最终哈希由此产生的串联 1,048,576 字节数据集以获得整个文件的最终 256 位哈希值。
就碰撞可能性更大和/或更有可能而言,方法 2 是否比方法 1 更不安全?也许我应该将这个问题改写为:方法 2 是否使攻击者更容易创建一个散列到与原始文件相同的散列值的文件,当然除了一个简单的事实,即暴力攻击会更便宜,因为hash可以在N个cpu上并行计算吗?
Update:我刚刚发现我在方法 2 中的构造与 a 的概念非常相似哈希表 http://en.wikipedia.org/wiki/Hash_list。然而,前一句中的链接引用的维基百科文章并没有详细说明哈希列表与方法 1 相比在冲突机会方面的优劣,方法 1 是文件的普通旧哈希,当仅top hash使用哈希列表。