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

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.

• Someone voted to close, leading me to this page, which explains cryptanalysis questions aren't allowed here. I, thus, tried adapting it to the format suggested on that link. Commented Jan 30, 2017 at 6:46
• Can you provide any insight into what this does or why you think it might be useful? Commented Jan 30, 2017 at 10:10
• @Elias partly because I don't know why it wouldn't. It looks "random" and "chaotic" enough to be irreversible and collision free, and I lack a better knowledge of what attacks could possibly ruin it. Commented Jan 30, 2017 at 11:33
• @MaiaVictor: in modern cryptography, decades of experience make us frown at security arguments on the line of: no one has broken it so far. Respectable security arguments are of the kind: breaking my system would break another elementary (preferably well-studied) problem. Also, qualities making a scheme worth studying, beyond such security argument, are minimality (your's is fine on that ground, at least with the revision I consider of the output formula), or speed (but with $2^{11}$ table lookup for each input bit, your scheme is rather slow).
– fgrieu
Commented Jan 30, 2017 at 13:17
• Be aware that some classes of cellular automations are known to be easy to reverse, while others are not. Maybe it has bearing on your hash function? With that said, my gut feeling is to modify Daum's narrow T-function solution graphs to try breaking this. Commented Jan 31, 2017 at 17:59

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.

• I'm not sure what to comment but this answer nailed it in all senses, thanks for dissecting what I did in such a precise way, for pointing the relevant resources and for suggesting improvements such as having less biased bits and avoiding losing entropy on the injection. I can't overstate how insightful that was. Commented Jan 30, 2017 at 18:03
• (I noticed I could get rid of the lookup table by using st[i] = ((a*39 + b*13 + 19) ^ 12) % 3; st[y] = ((b*39 + a*13 + 19) ^ 12) % 3;... sadly, this makes the code slower, not faster.) Commented Jan 30, 2017 at 20:26