I need to design a hash function that fits this criteria:
- 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
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.