哪些哈希算法可并行化？利用多核CPU优化大文件的散列

Question

我有兴趣优化一些大文件的散列(优化挂钟时间).I/O已经进行了足够的优化,I/O设备(本地SSD)仅以大约25%的容量进行分流,而其中一个CPU内核完全超出.

我有更多核心可用,将来可能会有更多核心.到目前为止,如果我碰巧需要同一个文件的多个哈希值,我只能使用更多内核,同时说MD5和SHA256.我可以使用相同的I/O流来提供两个或更多哈希算法,并且我可以免费获得更快的算法(就挂钟时间而言).据我了解大多数哈希算法,每个新位都会改变整个结果,而且并行地具有挑战性/不可能性.

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

由于未来的CPU将趋向于更多核心并且时钟速度趋于平稳,有没有办法提高文件散列的性能？(除了液氮冷却超频？)或者它本身是不可并行化的？

Answer 1

这个领域实际上有很多研究正在进行中.美国国家标准与技术研究院目前正在举办一场设计下一代政府级哈希函数的竞赛.大多数提案都可以并行化.

一个例子:http://www.schneier.com/skein1.2.pdf

维基百科对比赛现状的描述:http://en.wikipedia.org/wiki/SHA-3

Answer 2

你有什么样的SSD？MD5的我的C实现在单个Intel Core2内核(2.4 GHz,而不是最新的Intel)上以400 MB/s的速度运行.你真的拥有支持1.6 GB/s带宽的SSD吗？我想要一样!

树哈希可以应用于任何哈希函数.有一些细微之处,Skein规范试图处理它们,在函数本身中集成一些元数据(这不会改变很多性能),但Skein的"树模式"不是提交给的"Skein" SHA-3.即使选择Skein作为SHA-3,树模式散列的输出也不会与"plain Skein"的输出相同.

希望在某个时候定义标准,以描述通用树哈希.现在没有.但是,已经定义了一些协议,它们支持使用Tiger散列​​函数的自定义树散列,名称为"TTH"(Tiger Tree Hash)或"THEX"(Tree Hash Exchange Format).TTH的规范似乎有点难以捉摸; 我找到了一些关于草稿的提法,这些草稿已经移动或消失了.

不过,我对这个概念有点怀疑.它有点整洁,但只有当您能够比单个内核处理的数据更快地读取数据时才能提供性能提升,并且,如果正确的功能和正确的实现,单个内核可以每秒散列大量数据.分布在多个核心上的树形散列需要将数据发送到适当的核心,而1.6 GB/s不是有史以来最小的带宽.

SHA-256和SHA-512不是很快.在SHA-3候选者中,假设x86处理器处于64位模式,其中一些实现了高速(我的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).