From hash to Cryptographic hash

After reading some excellent papers on SipHash, I understood that good non-cryptographic hashes such as MurmurHash and CityHash are not secure for MAC usage, due to a certain type of DDos attack becoming possible, thanks to a combination of Hash-table degeneracy into a list and predictable collisions.

The central hypothesis is that it is possible to build multiple secret-key-independant collisions, because the inner hash loop evolution is secret-key-independant.

The reasoning and solution is clever, however i see that it requires a manual investigation of the algorithm by cryptographic expert. This conclusion wasn't drawned from automated tools. I guess the near-perfect distribution and avalanche of MurmurHash would have defeated such automated analysis. But i may be wrong.

I would like to apply this learning to xxHash. Consider this a learning exercise.

xxHash seems to avoid the specific issue described into the SipHash paper by integrating the secret-key into internal state right at the beginning, before the inner loop. As a consequence, since the next internal state depends on the previous one, the difference between 2 consecutives internal state cannot be secret-key-independant. Therefore, it looks like it prevents the existence of secret-key independant collisions, and solve, or partly solve, the collision-resistance property.

Currently, xxHash is not cryptographic mostly because its output is 32-bits. However, creating 64-bits & 128-bits variants from it can be pretty straighforward.

So let's pretend that the 32-bits output is not a problem (brute-force solution is accessible, but if that is the only solution, then the underlying principles are considered "about okay").

Question : Is there a way to analyse xxHash and tell, either by human analysis, or with an automated tool, that this hash function is or is not cryptographic ? And if not, what needs to be solved ?

PS : as an obvious source of information, let's check Wikipedia on what is a cryptographic hash function. Apparently, pre-image and collision resistance is all it takes to make an already good Hash function become a cryptographic one. Is this correct ?

[EDIT]

Here is a candidate solution to produce a secret-key independant collision for xxHash. Well, almost. Note that many restrictions apply, and that this trick is not guaranteed to work, due to the secret key. In best circumstances however, it's likely to work with a probability of 50%.

1) At position $P$, such as $P$ is a multiple of $4$, there is a 32-bits sequence $S$.

2) Add the value $A =$ 0xBD1C0000 to $S$. This will add a fixed value to $Op1(S) = S * prime2$, which is $Op1(A) = A * prime2 = 000A0000 = bit18$ (due to multiplication transitivity)

3) However, what we really want is not to add $bit18$, but to modify the 18th bit of $op1(S)$, hence from 0 to 1. The reason is, that if $Op1(S) & bit18 == 1$ , by adding $bit18$, we will not only modifiy the 18th bits, but also one or several other upper bits, due to carry spillover. Since we want a predictable result, we want to avoid that.

4) As a consequence, we need to select $P$ containing sequence $S$ such as $Op1(S)$ respects this condition (18th bit = 0). Since, for a random input, there is a 50% chance that the 18th bit of $Op1(S)$ is equal to zero, for any long enough input, a solution is very likely to be found (with S = 0 being an obvious solution).

5) However, it's not finished. $Op1(S+A)$ is then added to an unknown internal state, that we will call $Z$. This internal state is dependant on the secret key.

6) The same condition as before apply : in order to have a controllable effect, we need the 18th bit of $Z$ to be 0. However there is no way to check nor guarantee that condition. As a consequence, the method presented here is not guaranteed to work properly (probability 50%... for now)

7) In fact, it is even worse than that : we need both to ensure that the 18th bit of $Z$ is zero, and that the addition of lower bits of $Z$ and $Op1(S+A)$ do not add up to the 18th bit, as a consequence of carry spillover.

8) Fortunately, this latest condition can be made more probable by ensuring that lower bits of $Op1(S)$ are also zero, such as the 17th bit, then the 16th bit, and so on. Unfortunately, with each more zero condition, the probability to find a suitable $S$ decrease. With respect to this latest condition, the best possible input is $S=0$.

9) Now, if all above conditions are met, then the result of $Z1 = Z + Op1(S)$ has been slightly altered, by turning on its 18th bit : $newZ1 = Z + Op1(S+A) = oldZ1 + bit18$.

10) As a consequence, $Z2 = op2(Z1)$ is slightly altered too. Since $Op2$ is a left-rotation of 32-bits field by 13 bits, we have $newZ2 = oldZ2 + bit31$ (bit31 is highest bit).

11) As a consequence, since $Op3$ is a simple multiplication by a prime number, the $bit31$ effect will remain unmodified.

12) This $bit31$ will be counter-balanced at position $P+16$. Here, it's enough to add to the initial sequence $S2$ the value $B =$ 0x80000000, because $Op1(B) = 80000000 = B$. This will cancel the difference from previous round.

[EDIT 2]

Here is a better solution. This one needs nothing special regarding secret key, and its success rate is almost 100%.

1) We'll do the other way round : we will add just $1$ to $A = Op1(S)$. To get this effect, it's enough to add B6C92F47 to the initial sequence $S$ situated at position $P$ such as $P$ being a multiple of 4.

2) The beauty of this method is that it works as long as the lowest 17 bits of $Op1(S)$ are different from all 1. Which means that it almost always work. Moreover, it's easy to check if the condition is respected.

3) If the above condition is respected, $Op2$ will merely shift the added 1 by 13 bits. So $B = Op2(A)$ is now modified by +(2^13).

4) Now we can calculate the impact on $C=Op3(B)$. Since $newB = oldB + bit13$, we have $newC = oldC + Op3(bit13)$. $Op3(bit13) =$ EF362000.

5) Now, we have to cancel this on the next round. To get this result it's enough to add -EF362000 = 10C9E000. To add 10C9E000, we need to add 981D2000 to $S2$, because $Op1(981D2000) = 10C9E000$.

6) We now have a couple of values. Add B6C92F47 to the 32-bits field at position $P$, such as $P$ is a multiple of 4. Then add 981D2000 at position $P+16$. This solution works with a probability > 99.9%, requiring no special knowledge on secret key.

-
Which of the two inputs do you call "secret key"? The "seed" or the "input" argument? – Paŭlo Ebermann Feb 20 '13 at 20:18
"secret key" = "seed" – Cyan Feb 21 '13 at 10:11

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?

-
Thanks for clarifying, the difference between cryptographic Hash and MAC is much better now. – Cyan Feb 21 '13 at 10:18
That looks like an excellent answer. The principles which make xxHash not suitable for MAC usage seem identical to those targeting MurmurHash : mainly, the claim is that it is possible to forge 2 consecutives sequences which will cancel each other, whatever the underlying internal state is, making this operation independant of the secret key. I would feel better, nonetheless, if i could find such consecutive sequences. – Cyan Feb 21 '13 at 10:32
@Cyan: here's step one in an approach to attacking this; one of the steps within xxHash is the assignment "v1 += XXH_LE32(p) * PRIME32_2". Suppose that, which a certain block from a certain message, the value of 'v1' was $X$ (which you do not know). How could you modify the block being processed at this point so that the value of 'v1' after this step is the value $X+A$ (for a value $A$ that you pick)? – poncho Feb 22 '13 at 3:27
Yes, sure, in this case a solution would be easy. It would be possible to create a A, and then -A. The problem is, this is not the full line of operations. The full line is : v1 += XXH_LE32(p) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; Operations 1 alone would match your hypothesis, Operation 2 makes it more complex but i feel it would still be possible to find a solution; but operation 3 (v1 *= PRIME32_1;) seems to scramble everything. I don't see how it could be made "independant of X", which is the whole point. – Cyan Feb 22 '13 at 10:15
@Cyan: I said it was step 1; step 2 of finding the attack would be 'how do we pick A so that, after the rotate, we have a predictable result; if the real packet had the value $Y$ at that point, our altered packet would have a good chance of being $Y+B$ (for some $B$ we know). Originally, I found an $A$ for which this would hold with $p=0.5$; I now see other $A$ values which have $B$ values that hold with much higher probabilities. In any case, work on step 1; you'll learn from it. – poncho Feb 22 '13 at 16:21