After reading some excellent papers on SipHash, I understood that good non-cryptographic hashes such as MurmurHash and CityHash are not secure for Internet 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, due to the fact that the inner hash loop 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. xxHash seems to avoid the problem described into the SipHash paper by integrating the secret-key right at the beginning of the parallel calculations. It seems that this method prevents the existence of secret-key independant collisions. Once again, i may be wrong.

Currently, xxHash is not cryptographic mostly because its output is 32-bits. However, creating 64-bits & 128-bits variants from it is pretty straighforward. So let's pretend that the 32-bits output is not a problem (no brute-force solution). 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 ?

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 a good Hash function become a cryptographic hash function ?


Browse other questions tagged or ask your own question.