5

有趣的是，我还没有找到关于单个 512 位散列（如漩涡）与 4 个 128 位散列（如 md5、sha1 等）的连接的碰撞机会的任何测试或实验的足够信息。

当执行散列的数据相当小，平均只有 100 个字符时，4 个 128 位散列看起来相同的可能性似乎比单个 512 位散列小。

但这只是一个没有根据的明显猜测，因为我没有进行任何测试。你怎么想的？

编辑它就像 512bit hash vs 128bit hash 。128位哈希。128位哈希。128 位散列（4 128 位散列连接）

Edit2 我想在 url 上使用散列索引或考虑 RAM的散列 ，目的是尽量减少冲突的可能性，因为我想将散列列设置为唯一而不是 url 列。

Edit3 请注意，这个问题的目的是找到将碰撞可能性降至最低的方法。话虽如此，为什么我需要更多地关注减少碰撞的可能性？这是我的 Edit2 描述，它导致找到使用更少 RAM 的解决方案。因此，兴趣在于最大限度地减少冲突和降低 RAM 使用率。但这个问题的主要焦点是降低碰撞的可能性。

4

4 回答 4

6

听起来您想比较以下碰撞行为：

hash512(x)

具有以下碰撞行为：

hash128_a(x) . hash128_b(x) . hash128_c(x) . hash128_d(x)

其中“ .”表示连接，而hash128_a,hash128_b等是四种不同的 128 位哈希算法。

答案是：这完全取决于所涉及的各个散列的属性。

例如，考虑 128 位散列函数可以实现为：

uint128_t hash128_a(T x)   { return hash512(x)[  0:127]; }
uint128_t hash128_b(T x)   { return hash512(x)[128:255]; }
uint128_t hash128_c(T x)   { return hash512(x)[256:383]; }
uint128_t hash128_d(T x)   { return hash512(x)[384:511]; }

在这种情况下，性能将是相同的。

于 2011-09-14T13:09:02.833 回答
4

关于该问题的经典文章是由Hoch 和 Shamir撰写的。它建立在先前的发现之上，尤其是 Joux 的发现。底线如下：如果您采用四个具有 128 位输出的散列函数，并且这四个散列函数使用Merkle-Damgård结构，那么为整个 512 位输出找到一个冲突并不比找到一个哈希函数之一的冲突。MD5, SHA-1... 使用 MD 结构。

另一方面，如果您的一些散列函数使用不同的结构，特别是具有更广泛的运行状态，则连接可能会产生更强大的函数。请参阅@Oli 中的示例：如果所有四个函数都是 SHA-512 并在输出上进行了一些手术，那么连接的哈希函数可以是普通的 SHA-512。

关于四个散列函数的串联唯一可以肯定的是，结果的抗碰撞性不会低于四个散列函数中最强的一个。这已在SSL/TLS中使用，直到版本 1.1，在内部同时使用 MD5 和 SHA-1 以试图抵抗其中任何一个的中断。

于 2011-09-14T16:56:17.517 回答
3

512 位就是 512 位。唯一的区别在于散列中的缺陷不同。最好的整体散列是使用可用的最佳算法的 512。

编辑以添加说明，因为评论太长了：

理想的散列将内容均匀地映射到 x 位。如果您有 4 个（完全独立的）x 位哈希，则将文件统一映射到 4x 位；4x 位散列仍然将同一文件统一映射到 4x 位。4x 位是 4x 位；只要它完全一致，它来自一个 (4x) 散列函数还是 4 (x) 都没关系。然而，没有哈希值是完全理想的，所以你想要最均匀的分布，如果你使用 4 个不同的函数，只有 1 个可以是最接近最优的，所以你有 x 个最优位和 3x 个次优，而单个算法可以覆盖具有最佳分布的整个 4x 空间。

我想有可能足够大的算法可以具有比单个 512 分布更均匀的位子集，并且可以组合以获得更高的均匀性，但这似乎将是大量额外的研究和实现，但潜力不大益处。

于 2011-09-13T20:22:19.383 回答
2

如果您将连接四种不同的“理想”128 位散列算法与一个理想的 512 位散列算法进行比较，那么是的，这两种方法都会让您获得相同的冲突概率。不过，使用 md5 会更容易破解哈希。例如，如果攻击者知道您正在使用另一种盐进行 md5 + md5 w/ salt + md5 .. 那么作为 md5 碰撞攻击将更容易破解。在此处查看有关具有已知攻击的哈希函数的更多信息。

于 2011-09-13T20:24:48.487 回答