2

我见过几个问题，问“两个 16 位散列是否具有与 32 位散列相同的冲突率？” 或“两个 32 位散列是否具有与 64 位散列相同的冲突率？” 答案似乎是“是的，如果它们是不相关的体面散列函数”。但是，这是什么意思？

MurmurHash3 的作者这样说：

MurmurHash2_x86_64 并行计算两个 32 位结果并在最后混合它们，这速度很快，但意味着抗碰撞性仅与 32 位散列一样好。我建议避免使用这种变体。

他建议不要使用MurmurHash2_x86_64，但没有提到关于MurmurHash3_x86_128哪个似乎混合四个32 位结果以产生 128 位结果的建议。

而且这个功能看起来更糟：如果消息小于 8 字节，则h3and的输出h4总是会发生冲突。h2也容易发生碰撞，100% 的时间会产生这样的结果：

种子 = 0，dataArr = {0}
h1 = 2294590956, h2 = 1423049145 h3 = 1423049145 , h4 = 1423049145

种子 = 0，dataArr = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
h1 = 894685359, h2 = 2425853539 , h3 = 2425853539 , h4 = 2425853539

另一个例子：“bryc”的哈希 - e87e2554db409442db409442db409442
db409442 重复 3 次

任何长度小于 16 的空字节组合都将导致这些冲突，无论种子如何。

无论如何，如果Appleby所说的关于他的功能是真的，两个32位结果的抗碰撞性不比单个32位结果好，为什么每次我强制碰撞一个结果，都没有失败，其他不受影响？仅一个哈希中的冲突呈指数级增长。

MurmurHash2_x86_64 中 h1 的碰撞...
[ 2228688450，3117914388 ]！== [ 2228688450，2877485180 ]
[ 957654412，3367924496 ]！== [ 957654412，762057742 ]
[ 1904489323，1019367692 ]！== [ 1904489323，1894970953 ]
[ 2752611220，3095555557 ]！==[ 2752611220，2609462765 ]

我问这个的原因是因为我想在 JavaScript 中实现一个 64 位（或更大）的哈希来进行体面的错误检测。32 位散列函数还不够好。GitHub 上目前没有任何可用的解决方案足够快。由于 JavaScript 使用 32 位按位整数，因此只有使用算术运算的函数uint32_t在 JS 中是兼容的。许多 32 位函数似乎能够产生更大的输出而不会造成太多的性能损失。

我已经（在 JavaScript 中）实现了MurmurHash2_x86_64和MurmurHash3_x86_128，它们的性能令人印象深刻。我还实现了 MurmurHash2_160。

所有这些都具有与 32 位哈希相同的抗碰撞性吗？您如何判断结果是否足够相关以成为问题？我希望 64 位输出具有 64 位散列的强度，160 位输出与 160 位散列等一样强 - 同时满足 32 位算术的要求（JavaScript 限制）。

更新：这是我的自定义 64 位哈希，专为速度而设计（比我在 Chrome/Firefox 下优化的 32 位 MurmurHash3 更快）。

function cyb_beta3(key, seed = 0) {
    var m1 = 1540483507, m2 = 3432918353, m3 = 433494437, m4 = 370248451;
    var h1 = seed ^ Math.imul(key.length, m3) + 1;
    var h2 = seed ^ Math.imul(key.length, m1) + 1;

    for (var k, i = 0, chunk = -4 & key.length; i < chunk; i += 4) {
        k = key[i+3] << 24 | key[i+2] << 16 | key[i+1] << 8 | key[i];
        k ^= k >>> 24;
        h1 = Math.imul(h1, m1) ^ k; h1 ^= h2;
        h2 = Math.imul(h2, m3) ^ k; h2 ^= h1;
    }
    switch (3 & key.length) {
        case 3: h1 ^= key[i+2] << 16, h2 ^= key[i+2] << 16;
        case 2: h1 ^= key[i+1] << 8, h2 ^= key[i+1] << 8;
        case 1: h1 ^= key[i], h2 ^= key[i];
                h1 = Math.imul(h1, m2), h2 = Math.imul(h2, m4);
    }
    h1 ^= h2 >>> 18, h1 = Math.imul(h1, m2), h1 ^= h2 >>> 22;
    h2 ^= h1 >>> 15, h2 = Math.imul(h2, m3), h2 ^= h1 >>> 19;

    return [h1 >>> 0, h2 >>> 0];
}

它基于 MurmurHash2。每个内部状态h1，h2都单独初始化，但与相同的密钥块混合。然后将它们与备用状态（例如h1 ^= h2）混合。作为最终确定的一部分，它们在最后再次混合。

有什么迹象表明这比真正的 64 位散列更弱吗？它正确地通过了我自己的基本雪崩/碰撞测试，但我不是专家。

4

1 回答 1

1

MurmurHash2_x86_64和之间的区别在于MurmurHash3_x86_128前者只做一个[32-bit 32-bit] -> 64-bit mix，而后者每 16 个字节做一个 128-bit mix（虽然不是完全的混合，但它足以达到这个目的）。

因此，从逻辑上讲，MurmurHash2_x86_64将输入分成 2 个完全分离的流，为每个流计算一个 32 位哈希，然后将两个 32 位结果混合为一个 64 位结果。所以这不是真正的 64 位哈希。例如，如果一个流损坏，但偶然保留了相同的哈希值，则不会注意到这种损坏。这个事件的概率大致相同，就好像你一开始就有一个 32 位哈希一样。所以这个散列的强度小于 64 位。

另一方面，MurmurHash3_x86_128内部有一个 128 位状态，每 16 个输入字节混合（即所有 16 字节输入几乎立即影响内部状态，而不仅仅是在末尾），所以这是一个真正的 64 位哈希。

于 2018-04-04T07:54:08.597 回答