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.
