512位哈希 vs 4个128位哈希

Question

512位哈希 vs 4个128位哈希

hashcryptographyhash-collision

5

有趣的是，我没有找到关于单个512位哈希（比如Whirlpool）与4个128位哈希（如MD5、SHA1等）串联的碰撞概率进行任何测试或实验的足够信息。

当执行哈希运算的数据相对较小，仅平均100个字符时，4个128位哈希出现相同的可能性似乎比单个512位哈希小得多。

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

编辑后，它类似于512位哈希 vs 128位哈希。128位哈希。128位哈希。128位哈希（4个128位哈希串联）。

我想在这里使用哈希：index on url or hashing considering RAM，目的是尽量减少冲突的可能性，因为我想将哈希列设置为唯一而不是url列。

请注意，本问题的目的是找到最小化冲突可能性的方法。话虽如此，为什么我需要更加关注最小化冲突的可能性？这就是我的Edit2描述，导致找到使用更少的RAM的解决方案。所以，兴趣既在于最小化冲突，又在于降低RAM使用率。但本问题的重点是降低冲突可能性。

- Rick James

1

这里的具体问题是什么？（“你对此有什么想法？”不是一个具体的问题。） - Oliver Charlesworth

1

你具体在比较什么？ - Oliver Charlesworth

[@Oil Charlesworth] 具体问题是：512位哈希碰撞与4个128位连接哈希同时发生碰撞的概率是多少？ - Rick James

是的，没错。 :) 我在问题中提到了将4个128位哈希连接起来的操作。 - Rick James

从你在回答中的评论来看，你担心哈希表中的碰撞，就像数据结构中使用的那些，还是哈希保护某些数据的意义上的碰撞，以知道是否有人更改了它？ - woliveirajr

显示剩余5条评论

4个回答

4

这个问题的经典文章是由Hoch and Shamir撰写的。它建立在以前的发现基础上，特别是Joux的发现。底线是：如果您使用128位输出的四个哈希函数，并且这四个哈希函数使用Merkle-Damgård结构，则找到整个512位输出的碰撞不比找到任何一个哈希函数的碰撞困难。MD5，SHA-1等使用MD结构。

另一方面，如果您的某些哈希函数使用不同的结构，特别是具有更宽的运行状态，则连接可能会产生更强的函数。请参见@Oli的示例：如果所有四个函数都是带有一些输出手术的SHA-512，则连接的哈希函数可以是普通的SHA-512。

四个哈希函数的连接唯一确定的事情是，结果将不会比这四个哈希函数中最强的那个更少碰撞。这已经被用于SSL/TLS中，在版本1.1之前，内部同时使用MD5和SHA-1，以试图抵抗对任何一个的攻击。

- Thomas Pornin

你提出了一个非常有力的论点，即连接哈希不会比四个哈希函数中最强的那个更少发生碰撞。您能否详细说明一下，如何通过对4个SHA-512输出进行一些处理，然后将其压缩为单个512位SHA-512哈希，这比4个128位哈希更好？ - Rick James

1

@Oli的四个截断SHA-512连接在一起，确实是SHA-512（相同输入产生相同结果）。 SHA-512被认为是具有512位输出的最佳安全性（即抵抗碰撞的能力高达2^256次尝试）。其他一些连接方式效果不佳；有关详细信息，请参阅Hoch-Shamir文章（其中涉及一些数学，但问题实际上是研究级别的）。 - Thomas Pornin

这个。很容易认为使用多个不同的哈希会增加您的安全性，但事实并非如此。这是一个相当不明显但重要的结果。 - Nick Johnson

3

512位就是512位，差异在于哈希中的不完美之处。最佳的哈希应该使用最好的算法，长度为512位。

理想的哈希将内容均匀地映射到x位。如果你有4个（完全独立的）x位哈希，那么这将把文件均匀地映射到4x位；一个4x位的哈希仍然将同一文件均匀地映射到4x位。4x位就是4x位；只要它是完全均匀的，无论它来自一个（4x）哈希函数还是4个（x）哈希函数都没有关系。然而，没有哈希可以完全理想化，因此您需要最均匀可获得的分布，如果使用4个不同的函数，只有1个可以最接近最佳状态，因此您有x个最优位和3x个次优位，而单个算法可以用最优的分布覆盖整个4x空间。

我想可能足够大的算法可能有子集的位比单个512更均匀分布，并且可以组合以获得更均匀的分布，但这似乎需要进行额外的研究和实现，而效益很小。

- Kevin

1

这个答案的推理是什么？在你看来，为什么4个128位的连接哈希有更大的可能同时发生碰撞？虽然你必须考虑到数据样本不大的情况。 - Rick James

如果最优的512位哈希突然出现漏洞，导致在较少步骤内发生碰撞，整个哈希将陷入麻烦。如果您有4个128位哈希，并且其中一个存在漏洞，您最终会得到3个128位哈希... - woliveirajr

2

如果你要比较连接四个不同的“理想”128位哈希算法和一个理想的512位哈希算法，那么是的，这两种方法都会得到相同的碰撞概率。但使用md5会使破解哈希更容易。例如，如果攻击者知道你正在使用md5 + 带盐的md5 + 另一种盐的md5，则这将更容易受到md5碰撞攻击。有已知攻击的哈希函数的更多信息，请参考此处。

- Craig

这并不容易受到黑客攻击，因为这些是哈希值，用于使MySQL索引更短、查找更快。 - Rick James

@Rick 那你为什么还使用 512 位的哈希呢？在没有对手的情况下，128 位应该已经足够了。 - Nick Johnson

@Nick 我更新了问题，包括考虑哈希的目的。 - Rick James

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Oliver Charlesworth · Accepted Answer

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

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]; }

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