2
$\begingroup$

I need to design a hash function that fits this criteria:

  1. Limited to 32-bit integer operations (for compatibility with JavaScript bitwise operations, my target system)
  2. Produces an n-bit hash digest, greater or equal to 64-bit, with the expected collision probability of a hash of that size. Effectively combining multiple uncorrelated 32-bit states.

However, it seems care must be taken with this approach. I cannot verify it myself, but computing two 32-bit hashes using the same message but a different seed may cause more collisions than expected from a 64-bit hash, due to the two values being correlated.

This issue also seems to extends to the output of a single hash function that outputs two 32-bit results to form a 64-bit (which is exactly what I am trying to do).

I found MurmurHash64B (link to C++ code) which seemed almost ideal for my purpose. It produces a 64-bit hash using 32-bit operations at no significant performance cost.

But on the SMHasher wiki, the author mentions this about what I suspect to be the same function:

MurmurHash2_x86_64 computes two 32-bit results in parallel and mixes them at the end, which is fast but means that collision resistance is only as good as a 32-bit hash. I suggest avoiding this variant.

Then I saw this exchange on the subject:

  • Hacker News comment by martincmartin:
    Computing two 32-bit results in parallel and mixing them at the end does NOT mean collision resistance is only as good as a 32-bit hash. For that, you need to compute ONE 32-bit result, then transform it into a 64-bit result.

    • Hacker News comment (reply) by finnw
      Depends whether the two 32-bit hashes are correlated with each other. If there is no correlation then a pair of 32-bit hashes is no more likely to collide than a single 64-bit hash. But this is difficult to achieve, and you should not assume (for example) running the same algorithm twice with different initial states will produce uncorrelated hashes.

So then, is this function really not as good as a 64-bit hash? A naive test: Searching for a collision in state h1 doesn't seem to cause collisions in state h2. Is it simply not sufficiently mixing the states? It only mixes h1 and h2 at the end, not within the input mixing phase.

MD5 for example which also uses 32-bit arithmetic, computes four hash states which I assume must not suffer from this issue. There also exists a MurmurHash3_x86_128 which computes a 128-bit hash using four 32-bit states and appears to mix it more thoroughly (which has no mention of being weaker by the same author).

So I am wondering how can it be shown that MurmurHash64B (or a similar function) has correlated values that could result in reduced collision resistance than expected of the digest size.

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! Can you provide a link or source for the quote that MurmurHash2_x86_64 is only as good as a 32-bit hash? Also, please ask only one question per post. Please post the question about MurmurHash separately from the question requesting analysis of your new hash function. $\endgroup$ – D.W. Apr 5 '18 at 22:38
  • $\begingroup$ @D.W. edited original post. $\endgroup$ – bryc Apr 5 '18 at 23:10
2
$\begingroup$

MurmurHash2_x86_64 (aka MurmurHash64B) works as follows: it computes a 32-bit value $h_1$ based on bytes 0-3, 8-11, 16-19, 24-27, etc. of the input; it computes a 32-bit value $h_2$ based on bytes 4-7, 12-15, 20-23, etc. of the input; and then it mixes and combines these two values to obtain a 64-bit hashcode, computed as a function of $h_1,h_2$. (Here by $h_1$ I mean the value of the variable h1 at line 180 in the source code you linked to.)

There is a sense in which this has only 32-bits of collision resistance. In particular, if we consider two inputs that are the same in bytes 0-3, 8-11, 16-19, etc., and differ only in the other bytes, then there will be a $1/2^{32}$ chance that they collide. Why? Because there is a $1/2^{32}$ chance that they end up with the same $h_1$ value just by chance; and they will certainly end up with the same $h_2$ value (since it depends only on bytes that are the same for both outputs); so there is a $1/2^{32}$ chance they collide. This is the same chance of collision as for a 32-bit hash. For a 64-bit hash, you might expect a collision probability of $1/2^{64}$.

So this is a sense in which MurmurHash2_x86_64 is less than ideal, i.e., a sense in which one might say it has only 32 bits of collision resistance. Whether it is relevant in your practical situation is unknown.

The latest version of MurmurHash is MurmurHash3. MurmurHash3 supports a 128-bit output. A reasonable approach would be to compute a 128-bit hash using MurmurHash3, then discard all but the first 64 bits.

$\endgroup$
  • $\begingroup$ I see two problems: data has type uint32_t thus consumes 4 bytes at a time, so k1 and k2 are alternating 32-bit words of input. And because h2 is XOR'd with h1 in the finalization stage, there is a chance h2 will change if h1 has changed. $\endgroup$ – bryc Apr 5 '18 at 23:49
  • $\begingroup$ A note about MurmurHash3_x86_128 (128 bit output using 32-bit arithmetic): It is similar to MurmurHash64B, but there are four hash states instead of two. And hash states are mixed during the input mixing phase using addition (no mixing occurs in this phase inMurmurHash64B). I wonder if this is related to the collision resistance. $\endgroup$ – bryc Apr 6 '18 at 0:15
  • $\begingroup$ @bryc, see updated answer. I've revised my answer to address the first problem. The second "problem" doesn't contradict my answer. I've clarified what I meant by $h_1$ in my revised answer. Hopefully it is clearer now. In particular, the finalization stage doesn't change anything -- the finalization stage is what I mean by "combines these two values". MurmurHash3_x86_128's design is different and doesn't have the flaw that I outline in this answer, so yes, it has an impact on collision resistance. $\endgroup$ – D.W. Apr 6 '18 at 1:06
  • $\begingroup$ I see the flaw now—i.e. h2 sometimes wont change (before finalization) because its unaffected by some input bytes). I was confused because final XOR is merely a substitution cipher. However, when searching for collisions of the whole 64-bit output, I get 0 collisons while 32-bit h1 and h2 portions get 1853, 5385 respectively. I can see that h2 is ~3x more likely to collide when hashing integer strings 1000–3999996. But this may be a poor test. How can this be tested properly? I would like to implement (and understand) a possible fix to this flaw for educational purpose. $\endgroup$ – bryc Apr 6 '18 at 23:15
  • 1
    $\begingroup$ @bryc, you're not going to observe collisions by looking at random inputs. You have to look at inputs where you hold bytes 4-7, 12-15, 20-23, etc. fixed and vary only the other bytes. It's not that MurmurHash2 has 32 bits of collision resistance for random inputs. It's that it has 32 bits of collision resistance if you hold some of the input bytes fixed and vary some other ones. $\endgroup$ – D.W. Apr 6 '18 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.