10

我想提高散列大文件的性能，例如几十 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 将这些块散列为 32,768 个 256 位（32 字节）的散列，连接散列并进​​行最终散列结果连接了 1,048,576 字节的数据集，以获得整个文件的最终 256 位哈希。

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

更新：我刚刚发现我在方法 2 中的构造与哈希列表的概念非常相似。但是，与方法 1（文件的普通旧哈希）相比，上句中的链接引用的 Wikipedia 文章没有详细说明哈希列表在冲突机会方面的优劣，当只有顶部哈希时使用哈希列表。

4

3 回答 3

9

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

就像您正在做的那样，这些方法将块哈希列表和哈希列表再次提取到单个短哈希。由于这是一种成熟的做法，我认为它与顺序散列一样安全。

于 2011-08-10T18:09:42.863 回答
5

一些现代哈希设计允许它们并行运行。请参阅Skein 散列函数的高效并行算法。如果您愿意使用新的（因此经过不太彻底的测试）哈希算法，这可能会给您在多处理器机器上的速度提升。

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

于 2011-08-10T19:27:54.797 回答
0

我认为攻击者发现冲突要容易得多，因为生成哈希所需的时间是要哈希的数据大小的函数。加密安全哈希的一大优点是攻击者无法获取您的 100Gb 文件、找到他们想要变异的位置、对该块前后的所有内容进行哈希处理，然后使用这些预先计算的值快速获取哈希在对他们感兴趣的位进行小/快速排列之后，整个文件的大小。这是因为哈希算法中有一个重叠的滑动窗口。

简而言之，如果你编辑文件的中间部分，你仍然需要对整个文件进行哈希处理才能得到最终的校验和。因此，与 100 字节文件相比，100 Gb 文件需要更长的时间才能找到冲突。例外情况是在文件末尾的编辑是无意义的，这就是为什么在大文件的冲突示例中经常看到“in-the-wild”的原因。

但是，如果您将原始文件分成块，则攻击速度现在是最小块（或您想要变异的块的大小）的函数。由于文件大小随散列时间线性增加，一个 100Gb 的文件对于每个排列/MD5 大约需要 2000 秒，而一个 1Mb 的块将允许攻击者每秒尝试 50 次。

解决方案是将您的文件分成重叠的块，然后对这些块单独进行 MD5。生成的散列将是散列以开始到结束顺序和端到端顺序的串联。现在发现冲突需要对整个文件进行哈希处理——尽管是以并行化的方式。

于 2016-03-24T13:39:28.610 回答