Quote from: dentldir on July 29, 2014, 04:49:54 PM

Quote from: Anders on July 29, 2014, 03:44:21 PM

I noticed that the rightmost bit in initial condition needs to be 1. If all the bits are zero on the right side of the initial condition then the hash values become nonrandom and with collisions for similar messages. The whole left side of the Rule 30 cellular automaton is nonrandom it seems.

This observation is a key part of the paper I linked on the first page. You can use that non-randomness to reverse the "right adjacent" states effectively (i.e. taking 2^17 possibilities down to 32 or so). After messing with it for some time, you can see the importance of the structure left in the CA diagrams as they iterate. You ideally don't want any recognizable continuities.

One of the papers you linked (with the omega-flip network), overcomes this by alternating with a different rule and performing a permutation between subsequent runs. That paper also links to the correct testing framework you'd want to use if you intend to go further. (NIST's sts, apply the strict avalance criterion, etc.)

I'm a huge fan of CAs and Wolfram's work from the 80's but I was disappointed at the non-peer reviewed approach he took with NKS. This is one area where his intuition is superseded by decades of rigorous work by cryptography experts.

This image shows how the left side is easy to determine when the bits are sampled too tight:

Notice that when every other row of the center column is sampled, the left side becomes difficult to determine. That's the sample method I use in my hash function.