ric*_*ler 17 hash cryptography sha1 murmurhash
我们正试图在我们的开发团队中解决内部争论:
我们正在寻找64位PHP哈希函数.我们发现了MurmurHash3的PHP实现,但MurmurHash3是32位或128位,而不是64位.
同事#1认为,要从MurmurHash3生成64位散列,我们可以简单地对128位散列的第一个(或最后一个或任何)64位进行切片,并且它将像本机一样防碰撞64位散列函数.
同事#2认为我们必须找到一个原生的64位散列函数来减少冲突,并且128位散列的64位片段不会像本机64位散列那样具有抗冲突性.
谁是对的？
如果我们采用像SHA1而不是Murmur3这样的加密哈希的第一个(或最后一个或任何)64位,答案是否会改变？
emb*_*oss 15
如果你有真正的随机,均匀分布的值,那么"切片"将产生完全相同的结果,就像你从一开始就使用较小的值开始一样.要了解原因,请考虑这个非常简单的示例:假设您的随机生成器输出3个随机位,但您只需要一个随机位即可.我们假设输出是
b1 b2 b3
可能的值是
000, 001, 010, 011, 100, 101, 110, 111
并且所有都以1/8的概率发生.现在无论你为了什么目的从第三,第二或第三个切片,无论位置如何,拥有'1'的概率总是为1/2 - 对于'0来说也是如此".
您可以轻松地将此实验扩展到128位中的64位:无论您切换哪些位,在某个位置以一个或零结束的概率将是一半.这意味着如果你从均匀分布的随机变量中取样,那么切片不会使碰撞的可能性更大或更小.
现在一个很好的问题是随机函数是否真的是我们能够做的最好的事情来防止碰撞.但事实证明,只要函数偏离随机,就会发现发现碰撞的概率会增加.
现实生活中的问题是哈希函数根本不是随机的,相反,它们具有无限的确定性.但是加密散列函数的设计目标如下:如果我们不知道它们的初始状态,那么它们的输出在计算上与真正的随机函数无法区分,也就是没有计算效率的方法来区分散列输出和实际随机值.这就是为什么如果你能找到一个"区分符号",你就会认为哈希已经被破坏了,这个方法用一个概率高于一半的实际随机值告诉哈希值.不幸的是,我们无法真正证明现有加密哈希值的这些属性,但除非有人破坏它们,否则我们可能会认为这些属性具有一定的信心.以下是一篇关于SHA-3提交之一的区分符的文章示例,该文章说明了该过程.
总而言之,除非找到给定加密散列的区分符,否则切片完全正常并且不会增加碰撞的概率.
非加密哈希不必像加密哈希那样满足相同的要求.它们通常被定义为非常快并且在"理智/仁慈条件下"满足某些属性,但如果有人试图恶意操纵它们,它们可能很容易失败.这在实践中意味着一个很好的例子就是今年早些时候对哈希表实现(hashDoS)的计算复杂性攻击.在正常情况下,非加密哈希值可以很好地工作,但是它们的抗碰撞性可能会被一些聪明的输入严重破坏.加密哈希函数不会发生这种情况,因为它们的定义要求它们不受各种智能输入的影响.
因为有可能(有时甚至很容易)找到非加密哈希输出的上述区分符,我们可以立即说它们不符合加密哈希函数的条件.能够分辨出差异意味着输出中存在模式或偏差.
而这一事实本身就意味着它们或多或少地偏离随机函数,因此(在我们上面说过之后)碰撞可能比随机函数更可能发生.最后,由于冲突发生的概率已经高于完整的128位,因此在较短的输出时这不会更好,在这种情况下可能更有可能发生冲突.
tl; dr截断它时,您可以安全地使用加密哈希函数.但是,与使用较大输出到64位的非加密哈希截断相比,使用"本机"64位加密哈希函数更好.
由于雪崩效应,强散列是指源中的单个位变化导致散列平均翻转的一半位的散列.因此,对于良好的散列,"散列"是均匀分布的,因此每个部分或切片受到相等且均匀分布的源位数量的影响,因此与同一位长度的任何其他切片一样强.是.
只要哈希具有良好的属性和均匀分布,我同意同事1.