Avoiding correlated values and reduced collision resistance in multiple hash states I need to design a hash function that fits this criteria:


Limited to 32-bit integer operations (for compatibility with JavaScript bitwise operations, my target system)
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.
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.