哪些哈希算法可以并行处理?利用多核CPU优化大文件的哈希处理。

26

我对优化一些大文件的哈希值(优化挂钟时间)很感兴趣。I/O已经得到了很好的优化,而且I/O设备(本地SSD)仅利用了约25%的容量,而其中一个CPU核心完全达到了最大值。

我有更多可用的核心,并且在未来可能会有更多的核心。到目前为止,如果我需要同一文件的多个哈希值,比如同时进行MD5和SHA256,我才能够利用更多的核心。我可以使用相同的I/O流来提供两个或多个哈希算法,并且我可以免费获得更快的算法(就挂钟时间而言)。据我了解,大多数哈希算法中,每个新位都会改变整个结果,因此在并行处理方面它是困难甚至不可能实现的。

是否有任何主流哈希算法可并行化?
是否存在可并行化的非主流哈希算法(并且至少有样例实现可用)?

随着未来的CPU趋向于更多的核心和时钟速度的平稳状态,有没有办法来提高文件哈希的性能?(除了氮冷却超频外?)或者它本质上是不可并行的?


此外,我听说大多数当前的哈希算法是可以并行化的,但我不确定需要什么。显然,一种方法是自己决定对文件的每个4k块进行哈希处理,然后以某种方式组合哈希值。XOR,也许?在密码学上发明自己的算法总是很危险的,所以如果你要防御恶意数据篡改而不是意外数据损坏,我不会相信这种方法。 - sblom
我已经阅读了你提供的Skein规范。你在这里建议的正是它实现并行化的方式(显然被称为“树哈希”)。Skein有一种标准的方法来指定叶子大小、扇出和最大树高,以便使用相同参数的任何人都能得到相同的哈希结果。(这很重要)我想要防御恶意篡改以及意外损坏。我希望标准已经准备好了。 - DanO
http://tools.ietf.org/html/rfc1321 看起来 MD5 不容易进行并行计算,每个块的计算都依赖于之前所有块计算得出的状态。如果这一特性不成立,那么 MD5 将不安全 (交换块的位置不会影响散列值—这是不好的)。无论如何,我并不是说 MD5 的并行化不可能实现,只是乍一看看起来是不可能的。 - kgadek
1
@sblom,您所建议的类似于 Merkle 或哈希树,这些树被文件共享软件用于确保从对等方下载正确的文件。https://en.wikipedia.org/wiki/Merkle_tree - MauganRa
3个回答

11

感谢提供链接,Skein看起来很有趣,在至少六种语言中都有实现。它只能像其他线性哈希函数一样并行化...通过使用标准化的树状分解算法。基本上是对源代码的部分进行哈希处理,将哈希值再次(如有必要)分段哈希在一起等等。但是,树参数随后成为哈希参数的一部分,并且验证需要再次使用完全相同的参数。我想这对我来说可以工作...但如果有一个“标准”的话就更好了。 - DanO

6
你用的是什么样的SSD?我的MD5 C实现在单个Intel Core2核心上运行速度为400 MB/s(2.4 GHz,不是最新的Intel)。你真的有支持1.6 GB/s带宽的SSD吗?我也想要!
树哈希可以应用于任何哈希函数。有一些微妙之处,Skein规范试图处理它们,在函数本身中集成了一些元数据(这对性能没有太大影响),但是“树模式”不是提交给SHA-3的“Skein”。即使选择Skein作为SHA-3,树模式哈希的输出也与“普通Skein”的输出不同。
希望在某个时候定义一个标准,描述通用树哈希。现在还没有。然而,一些协议已经定义了使用Tiger哈希函数支持自定义树哈希的功能,名称为“TTH”(Tiger Tree Hash)或“THEX”(Tree Hash Exchange Format)。TTH的规范似乎有点难以捉摸;我发现一些草案的参考资料已经移动或永久消失了。
尽管如此,我对这个概念有点怀疑。它很漂亮,但只有在您可以读取数据比单个核心处理更快的情况下才提供性能提升,并且在正确的功能和正确的实现下,单个核心可以每秒哈希相当多的数据。分布在多个核心上的树哈希需要将数据发送到适当的核心,并且1.6 GB/s并不是最小的带宽。
SHA-256和SHA-512的速度不是很快。在假设64位模式下使用x86处理器的情况下,SHA-3候选者中有些可以实现高速(在我的2.4 GHz Intel Core2 Q6600上,使用单个核心超过300 MB/s - 这也是我可以从SHA-1获得的结果),例如BMW,SHABAL或Skein。从密码学角度来看,这些设计有点太新了,但是MD5和SHA-1已经被密码学“破解”(在MD5的情况下非常有效,在SHA-1的情况下是理论上的),因此任何第二轮SHA-3候选者都应该没问题。
当我戴上我的“先知”帽子时,我预见到处理器将继续变得比RAM更快,以至于哈希成本将被内存带宽所淘汰:CPU将有空闲的时钟周期,同时等待来自主RAM的数据。在某个时候,整个线程模型(一个大的RAM用于许多核心)将不得不进行修正。

6
有些内容与主题不完全相关。实际上,我很讨厌 OP 提出优化建议的请求,而总有人 1)建议不要费心优化,而是购买更好的硬件 2)试图证明在这种情况下优化是无用的OP 已经证明/试图证明他需要这个,所以我认为你的意见没有帮助 ["你真的有支持1.6 GB/s带宽的SSD吗?我也想要!"]。因此不能给 +1。 - kgadek

4
你没有说明需要哈希的用途。如果仅用于内部使用而不与外界交换,只需将每个文件分成块,计算并存储所有校验和。然后,可以通过将每个块分配给多个核心来使用多个核心。
两种解决方案是将文件分成固定大小的块(更简单,但对于较小的文件将使用较少的核心,在这些文件中您不应该需要所有这些功率)或固定数量的块(每个文件将使用所有核心)。真正取决于您想要实现的目标以及您的文件大小分布情况。
另一方面,如果您需要将哈希用于外部世界,正如您从其他答复中所读到的那样,使用“标准”哈希(例如,如果您想使用不同工具发送SHA1哈希供他人检查)是不可能的,因此您必须在其他地方寻找。例如,在存储文件时计算哈希以供以后检索,或者使用“空闲”核心在后台计算哈希并进行存储以供以后检索。
更好的解决方案取决于您的约束条件以及您可以投入的空间,时间或CPU功率。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接