Is any 64-bit portion of a 128-bit hash as collision-proof as a 64-bit hash?

Question

We're trying to settle an internal debate on our dev team:

We're looking for a 64-bit PHP hash function. We found a PHP implementation of MurmurHash3, but MurmurHash3 is either 32-bit or 128-bit, not 64-bit.

Co-worker #1 believes that to produce a 64-bit hash from MurmurHash3, we can simply slice the first (or last, or any) 64 bits of the 128-bit hash and that it will be as collision-proof as a native 64-bit hash function.

Co-worker #2 believes that we must find a native 64-bit hash function to reduce collisions and that 64-bit slices of a 128-bit hash will not be as collision proof as a native 64-bit hash.

Who's correct?

Does the answer change if we take the first (or last, or any) 64-bits of a cryptographic hash like SHA1 instead of Murmur3?

Niobous

What's the goal ? Is it cryptographic ? If so, there is no real secure 64 bits hash function. – Coming

Wouldn't it be better to move this question to crypto.SE? – Willman

@Willman Basic hashing, when you don't go deep, seems to me to be a common preoccupation of all coders. – Coming

@dystroy possibly, but here is not necessarily the place to get answers with the required expertise, unfortunately. – Willman

The goal is a simple hash, not crypto. I didn't know about crypto.SE but I'm open to posting it there if that's the better place for this type of question. – Niobous

When you look at the MurmurHash3 algorithm, it seems there is no real difference between the 32 bits version and the 64 bits than the length. As it's not crypto, I don't think that moving to crypto.SE makes sense. – Coming

coworker #1 is correct unless there is an unexpected weakness in the hash function. – Resignation

Well, if you really want to stump your coworkers, try this link: google.com/… – Jasminjasmina

Answer 1

If you had real random, uniformly distributed values, then "slicing" would yield exactly the same results as if you had started with the smaller value right from the start. To see why, consider this very simple example: Let's say your random generator outputs 3 random bits, but you only need one random bit to work with. Let's assume the output is

b1 b2 b3

The possible values are

000, 001, 010, 011, 100, 101, 110, 111

and all are to occur with equal probability of 1/8. Now whatever bit you slice from those three for your purpose - the first, second or third - the probability of having a '1' is always going to be 1/2, regardless of the position - and the same is true for a '0'.

You can easily scale this experiment to the 64 out of 128 bit case: regardless of which bits you slice, the probability of ending up with a one or a zero in a certain position is going to be one half. What this means is that if you had a sample taken from a uniformly distributed random variable, then slicing wouldn't make the probability for collisions more or less likely.

Now a good question is whether random functions are really the best we can do to prevent collisions. But as it turns out, it can be shown that the probability of finding collisions increases whenever a function deviates from random.

Cryptographic hash functions: co-worker #1 wins

The problem in real life is that hash functions are not random at all, on the contrary, they are boringly deterministic. But a design goal of cryptographic hash functions is as follows: if we didn't know their initial state, then their output would be computationally indistinguishable from a real random function, that is there's no computationally efficient way to tell the difference between the hash output and real random values. This is why you'd consider a hash already as kind of broken if you can find a "distinguisher", a method to tell the hash from real random values with a probability higher than one half. Unfortunately, we can't really prove these properties for existing cryptographic hashes, but unless somebody breaks them, we may assume these properties hold with some confidence. Here is an example of a paper about a distinguisher for one of the SHA-3 submissions that illustrates the process.

To summarize, unless a distinguisher is found for a given cryptographic hash, slicing is perfectly fine and does not increase the probability of a collision.

Non-cryptographic hash functions: co-worker #2 might win

Non-cryptographic hashes do not have to satisfy the same set of requirements as cryptographic hashes do. They are usually defined to be very fast and satisfy certain properties "under sane/benevolent conditions", but they might easily fall short if somebody tries to maliciously manipulate them. A good example for what this means in practice is the computational complexity attack on hash table implementations (hashDoS) presented earlier this year. Under normal conditions, non-crypto hashes work perfectly fine, but their collision resistance may be severely undermined by some clever inputs. This can't happen with cryptographic hash functions, because their very definition requires them to be immune to all sorts of clever inputs.

Because it is possible, sometimes even quite easy, to find a distinguisher like above for the output of non-cryptographic hashes, we can immediately say that they do not qualify as cryptographic hash functions. Being able to tell the difference means that somewhere there is a pattern or bias in the output.

And this fact alone implies that they deviate more or less from a random function, and thus (after what we said above) collisions are probably more likely than they would be for random functions. Finally, since collisions occur with higher probability for the full 128 bits already, this will not get better with shorter ouptputs, collisions will probably be even more likely in that case.

tl;dr You're safe with a cryptographic hash function when truncating it. But you're better off with a "native" 64 bit cryptographic hash function compared to truncating a non-cryptographic hash with a larger output to 64 bits.

Waldack

Thank you for the very thorough response. That was helpful! – Niobous

Answer 2

Due to the avalanche effect, a strong hash is one where a single bit of change in the source results in half the bits of the hash flipping on average. For a good hash, then, the "hashness" is evenly distributed, and so each section or slice is affected by an equal and evenly distributed amount of source bits, and therefore is just as strong as any other slice of the same bit length could be.

I would agree with co-worker 1 as long as the hash has good properties and even distribution.

Nottingham

Would you say that's true for both MurmurHash3 (non-crypto) and SHA1 (crypto)? – Niobous

Assuming SHA1 is more crypto-oriented and Murmur is more performance oriented, then I would say that SHA1 would be better for slicing up, since cryptographically strong hash functions are designed to give more uniform/even distributions. You should profile for both collisions and speed against your requirements. As usual, there will probably be a tradeoff. – Nottingham

Murmur is not a cryptographically strong hash, I would seriously advice you to have a look at SHA-1 or SHA-256 (although the latter is certainly slower again). 64 bit hash functions only offer about 32 bit resistance against collision attack because of the birthday paradox. You won't bump into collisions right away without going to look for them on purpose, but it would not be completely impossible. – Jasminjasmina

Answer 3

This question seems incomplete without this being mentioned:

Some hashes are provably perfect hashes for a specific class of inputs (eg., for input of length n for some reasonable value of n). If you truncate that hash then you are likely to destroy that property, in which case you are, by definition, increasing the rate of collisions from zero to non-zero and you have weakened the hash in that use case.

It's not the general case, but it's an example of a legitimate concern when truncating hashes.

Ode