collision resistance - From hash to Cryptographic hash - Cryptography Stack Exchange

Well, first of all, you need to be clear about the meanings of various cryptographical primitives.

• Cryptographic hash function; this is a function that takes an input string, and generates a hash. The idea is that we don't know how to create two input strings with the same hash, and so the hash can be used as a replacement for the original string. Now, cryptographic hash functions don't take a secret key, because we need to assume that anyone is able compute them; xxHash is obviously not a cryptographic hash function. And, yes, there are "keyed hash functions" which do take secret keys; xxHash isn't one of those either.

• Message authentication codes; this is a function that takes a message and a key; it generates an output string (a MAC). The idea is that if someone doesn't know the key, they can't generate the MAC for any message that they haven't seen the MAC for. This is rather closer to what you are hoping xxHash to be.

That being said, to answer the question, yes, there is a way to analyse xxHash and determine whether it is a secure message authentication code. And, the answer is whether it is a secure message authentication code is "no" (and if the answer was "yes", there would have been no really good way to determine that).

One way to see that is that, in fact, xxHash is not second preimage resistant, even to someone who doesn't know the key. Specifically, given a valid message/MAC pair (where the message is at least 32 bytes long), it is possible to construct a second message that, with probability $p=0.5$, evaluates to the same MAC. Remember that this is a violation of the Message Authentication Code security guarantees, not specifically because it is a collision, but because it allows the attacker to compute the MAC of a message he hasn't been given the MAC to (and it's a violation independent of whether that MAC value happens to be a value he has seen before).

As to how to find the alternative message, well, you said to treat this as a learning exercise, this can be considered an exercise to the reader. However, here's how it works overall; you introduce a change at step $X$, which disturbs the state. You also introduce a second change at step $X+1$ (actually, because of how xxHash works, 16 bytes later), and this second change cancels out the effects of the first change, leaving the internal state while processing the altered message exactly the same as the corresponding step for the original message. The success probability $p=0.5$ is there because whether the change is precisely what we expect depends on whether a certain internal carry happens during an addition. For, how can we arrange these two changes to make this happen?

Read full article from collision resistance - From hash to Cryptographic hash - Cryptography Stack Exchange