Comment by aappleby
6 days ago
MurmurHash/SMHasher author here. While I don't doubt this passes BigCrush etc, I do find it very surprising that it does.
The state update function is effectively "a = rotate(a, constant) + b; b = rotate(b, constant) + constant;" and the output derivation is "output = (a + b) * constant".
That update function is _barely_ nonlinear, and the output derivation is linear. The output would probably be slightly better as "(a ^ b) * constant".
The slow_loop thing to guarantee 2^128 period is probably not needed - anyone with an application that cares about a period that high is probably going to choose a more robust generator (a few rounds of hardware-accelerated AES in counter mode is your best bet there)
The use of the Z3 prover is neat and I should read up on that more.
Hello! Awesome work on your hashing by the way!
When iterating I first tried to make fast_loop as random as possible by trying all possible rotational values and then having each option tested in PractRand 1000 times from 256M to 8GB. There was a wide range of performance by rotation. 47 was the best (for the GR constant) and resulted in the most tests being passed. The goal was a stronger than normal core for the PRNG that could feed actively into mix.
I found the multiplication to be necessary for passing PractRand and BigCrush with the state mixing as posted.
I had a variant which assigned mix as rotate(mix,constant) + (mix^fast_mix). That would pass cleanly with mix directly outputted (with no multiplication) - but I couldn’t get Z3 prover to show injectivity so I decided to go with the posted route.
I'm not sure that the claim "the mix function is injective" is sufficient to support the claim "The period is at least 2^128". If the mix is reversible then it forms a permutation on 2^192, but that does not imply that it forms a single cyclic permutation.
For example, if f(0) = 1 and f(1) = 0, even if the rest of f's domain is injective the period of f is still only 2 when the initial value is 0 or 1.
That is correct. The permutations will likely break up into multiple cycles, and the cycle lengths follow a poisson distribution.
https://dms.umontreal.ca/~andrew/PDF/CycleLengths1.pdf
I wasn't able to analyze the cyclic behavior of the mix directly, but for the purpose of minimal period only fast_loop and slow_loop are used (as a 128bit counter).