128位散列中的任何64位部分是否与64位散列一样具有防冲突能力？

Question

我们正在尝试解决我们开发团队的内部争论：

我们正在寻找一个64位的PHP散列函数。我们找到了PHP implementation of MurmurHash3，但MurmurHash3是32位或128位，而不是64位。

同事#1认为，要从MurmurHash3生成64位散列，我们可以简单地对128位散列的第一个(或最后一个或任何)64位进行切片，并且它将像本机64位散列函数一样具有防冲突能力。

同事#2认为，我们必须找到一个本机64位散列函数来减少冲突，并且128位散列的64位片段不会像本机64位散列那样具有防冲突能力。

谁是对的？

如果我们采用像SHA1这样的加密散列的第一个(或最后一个，或任何)64位而不是Murmur3，答案会发生变化吗？

Answer 1

如果你有真正的随机的、均匀分布的值，那么“切片”将产生完全相同的结果，就像你从一开始就从较小的值开始一样。要了解原因，请考虑这个非常简单的示例:假设您的随机生成器输出3个随机比特，但您只需要使用一个随机比特。让我们假设输出是

b1 b2 b3

可能的值包括

000, 001, 010, 011, 100, 101, 110, 111

现在，无论你为了你的目的而从这三个位中切出什么位-第一位、第二位或第三位-出现“1”的概率始终是1/2，无论位置如何-对于“0”也是如此。

您可以很容易地将此实验扩展到128位中的64位:无论您对哪些位进行切片，在某个位置以1或0结尾的概率将是一半。这意味着，如果你从一个均匀分布的随机变量中抽取样本，那么切片不会增加或减少碰撞的可能性。

现在一个很好的问题是，随机函数是否真的是我们防止碰撞的最佳方法。但事实证明，当函数偏离随机时，发现碰撞的概率就会增加。

加密散列函数:同事#1胜出

现实生活中的问题是，哈希函数根本不是随机的，相反，它们是无聊的确定性。但是密码散列函数的设计目标如下:如果我们不知道它们的初始状态，那么它们的输出将在计算上与真实的随机函数无法区分，也就是说，没有计算有效的方法来区分散列输出和真实的随机值之间的差异。这就是为什么如果你能找到一种“判别器”，一种以高于一半的概率区分散列和真实随机值的方法，你就会认为散列已经被破坏了。不幸的是，我们不能真正证明现有密码散列的这些属性，但除非有人破解它们，否则我们可以假定这些属性具有一定的可信度。这是一个paper的例子，关于一个SHA-3提交的区分符来说明这一过程。

总而言之，除非找到给定密码散列的区别符，否则切片是非常好的，并且不会增加冲突的概率。

非加密哈希函数:同事#2可能获胜

非加密哈希不必满足与加密哈希相同的一组要求。它们通常被定义为非常快，并在“正常/仁慈的条件下”满足某些属性，但如果有人试图恶意操纵它们，它们可能很容易达不到要求。这实际上意味着什么的一个很好的例子是今年早些时候提出的对哈希表实现(hashDoS)的计算复杂性攻击。在正常情况下，非加密哈希可以很好地工作，但它们的抗冲突性可能会被一些聪明的输入严重破坏。这不会发生在加密哈希函数中，因为它们的定义要求它们不受各种智能输入的影响。

因为有可能，有时甚至很容易，为非加密散列的输出找到一个像上面这样的判别符，我们可以立即说它们不符合加密散列函数的条件。能够分辨出差异意味着在输出中的某个地方存在模式或偏差。

这一事实本身就意味着它们或多或少地偏离了随机函数，因此(在我们上面说过的)碰撞可能比随机函数更有可能发生。最后，由于冲突发生的概率已经很高，对于完整的128位，这不会随着较短的输出而变得更好，在这种情况下，冲突可能更有可能发生。

tl;dr使用加密散列函数截断它是安全的。但是，与截断具有更大输出到64位的非加密散列相比，使用“原生”64位加密散列函数更好。

Answer 2

由于雪崩效应，强哈希是指源中的一位更改平均会导致哈希位翻转的一半。因此，对于良好的散列，“哈希度”是均匀分布的，因此每个区段或片都受到相等且均匀分布的源比特量的影响，因此其强度与相同位长度的任何其他片一样强。

只要散列具有良好的属性和均匀的分布，我就会同意同事1的观点。

Answer 3

如果不提到这个问题，这个问题似乎不完整：

一些散列可以证明是针对特定类别输入的perfect散列(例如，对于长度为n且n为某个合理值的输入)。如果您截断散列，那么您很可能会破坏该属性，在这种情况下，根据定义，您会将冲突率从零增加到非零，而且您已经削弱了该用例中散列。

这不是一般的情况，但它是截断散列时合理关注的一个例子。