Given a 128-trit state space, is a 3-symbol block cellular automaton secure against preimage attacks?

Question

The following implementation, here for illustration:

void hash(int* bits, int bitsLen, int* out, int outLen){
  const int tt[9] = {1,2,0,0,0,1,1,2,2};
  int st[128], i, k, j, x, y, a, b;     // state st holds 128 trits
  for (i=0; i<128; ++i)                 // initial state setup
    st[i] = i%3;                        //
  for (k=0; k < bitsLen + outLen; ++k){ // for each input and output bit
    for (j=0; j<32; ++j){               // 32 times for each input and output bit 
      if (k < bitsLen)                  // if processing an input bit..
        st[0] = bits[k];                // enter that input bit in state
      for (i=j%2; i<128; i+=2){         // for each pair of trits in state
        x = (i+0)%128;                  // index of first trit
        y = (i+1)%128;                  // index of second trit
        a = st[x];                      // get these current trits values              
        b = st[y];                      //
        st[x] = tt[a*3+b];              // update these trits per table tt
        st[y] = tt[b*3+a];              //
      };                                //
    };                                  //
    if (k >= bitsLen)                   // building an output bit
      out[k-bitsLen] = (st[0] + st[1] + st[2] + st[3]) % 2;
  };
}

uses a 3-symbol block cellular automata, with transition rules encoded as the 3x3 table defined by tt and using a 128-trit (about 202 bits) state space, to materialize an one-way function. It employs k interactions, where each interaction advances the automata by 32 steps, inserting one of the input bits on the first cell of the automata at each step. Under those conditions, is this function secure against preimage attacks? Here is a test run.

^{Note: code commented and trimmed for clarity, without changing the output. See previous link or this for the original.}

Answer 1

This is a not an answer, as I do not touch preimage resistance; it is comments (now removed) made into something hopefully correct, including a description per cryptographic conventions.

The proposed code implements a minimalist hash function with an internal state st of 128 trits, parameterizable message and output size (inLen 16 bits and outLen 256 bits in the illustration). At the core is a simple state transformation, iterated for 32 rounds per input and output bit, potentially changing each state trit.

At each of such round, 64 times, two state trits are selected per a simple schedule (giving potentially full diffusion after 2 rounds), and replaced according to the following transformation (an alternate expression of constant table tt and st[x] = tt[a*3+b]; st[y] = tt[b*3+a]; ):

input   output
 0 0     1 1
 0 1     2 0
 0 2     0 1
 1 0     0 2
 1 1     0 0
 1 2     1 2
 2 0     1 0
 2 1     2 1
 2 2     2 2

This transformation is reversible, therefore the 64 transformations in a round for (i=j%2; i<128; i+=2){..} are entropy-preserving.

Each input bit is injected by replacing a trit at each round, by st[0] = bits[k];. Thus each round processing an input bit looses some amount of state entropy, but not nearly as much as if the above transformation was not reversible.

The output is formed (still with 32 rounds per bit, and no input injected) by a formula combining 4 trits. Under the natural assumption that the state is about unbiased, the output is noticeably biased: a bit is set with odds $40/81<49.4\%$. That would be fixable by mixing much more trits to produce the output. Note: because there is no entropy loss during output production, it is likely that with 256 output bits, almost all the state entropy after input processing makes it to the output, which is good.

This hash can be viewed as a traditional iterated hash function à la Merkle-Damgård or sponge, with 1 bit per message block (compensating the less than complete diffusion per round), no length-strengthening (replaced by iterations in the output production, which also gives the variable-size output), and the unusual characteristic of having sizable state entropy loss per 1-bit message block processed. The later is slightly frightening compared to using an entropy-preserving message injection like st[0] = (st[0]+bits[k])%3;, but I do not immediately see that it opens to a devastating attack (nor have proof that this entropy loss is not in fact a strength); studying this seems interesting in its own regard.