Reverse Cellular Automata


We were given a single random step in a cellular automata which follows Wolfram rule 126 and its boundary condition wraps around so that the last bit is a neighbor of the first bit – 0x66de3c1bf87fdfcf .
The following image represents rule 126 by describing all possible cases and outcomes:

In order to catch the flag, we first must reverse the given step and find its previous step.
Though there can be multiple previous steps which will generate the given step. The idea is to minimize that list of possible previous steps to the minimum.
To achieve that, we can deduce the relationship between the different bits of the previous step by looking at the current step bits.
For example, if the current step is 11011, we can know for sure (because of that middle ‘0’), the corresponding previous step should be something like ?xxx? where ‘x’ is either 0 or 1. In addition (because of all other ‘1’ occurrences) we can know that there cannot be another sequence of 3 ‘x’ in the previous step (if there was, we should see more ‘0’ occurrences in the current step). So, obviously, we know that the previous step should be (!x)xxx(!x) which means either 01110 or 10001.

Following this concept, lets look on the binary representation of the actual given step:
Assuming a is either 0 or 1 and b = !a, we can deduce part of the pattern of the previous step:


Given another pair cd (where c is either 0 or 1 and d = !c), we can deduce another part:


Similarly, for pairs ef, gh, ij, kl:


Combining all parts we get the pattern:


We still got 2 sequences of 3 bits and 1 sequence of 5 bits which we couldn’t get a pattern for but we do know there cannot be any sequence of 3 of the same bit in a row in them (Otherwise we should see another ‘0’ in the current step). The 3 bit sequences must be one of [001,010,011,100,101,110] while the 5 bit sequence must be one of [00100,00101,00110,01001,01010,01011,01100,01101,10010,10011,10100,10101,10110,11001,11010,11011].

Now that we have a pretty strict pattern, we can generate all possible previous steps by constructing a binary string using this simple and dirty python script:

dic = ['0','1']
indx = [0,1]

seq3 = [(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0)]
seq5 = [(0,0,1,0,0),(0,0,1,0,1),(0,0,1,1,0),(0,1,0,0,1),(0,1,0,1,0),(0,1,0,1,1),(0,1,1,0,0),(0,1,1,0,1),(1,0,0,1,0),(1,0,0,1,1),(1,0,1,0,0),(1,0,1,0,1),(1,0,1,1,0),(1,1,0,0,1),(1,1,0,1,0),(1,1,0,1,1)]

for a in indx:
  for c in indx:
    for e in indx:
      for g in indx:
        for i in indx:
          for k in indx:
            for un1 in seq3:
              for un2 in seq5:
                for un3 in seq3:
                  bin_str = (dic[a]*2)+(dic[1-a]*4)+(dic[a]*3)+(dic[1-a]*3)+(dic[a]) + (dic[1-c])+(dic[c]*5)+(dic[1-c]) + (dic[1-e])+(dic[e]*7)+(dic[1-e]*3)+(dic[e]) + dic[un1[0]]+dic[un1[1]]+dic[un1[2]] + (dic[1-g])+(dic[g]*6)+(dic[1-g]) + dic[un2[0]]+dic[un2[1]]+dic[un2[2]]+dic[un2[3]]+dic[un2[4]] + (dic[1-i])+(dic[i]*3)+(dic[1-i]) + dic[un3[0]]+dic[un3[1]]+dic[un3[2]] + (dic[1-k])+(dic[k]*4)+(dic[1-k]) + (dic[1-a])+(dic[a])

This script will generate exactly 36864 possible previous steps. This is by far less than 2^64 (18446744073709551616):


All we have to do now is iterate this list and use each entry as a key to decrypt the given encrypted flag – U2FsdGVkX1/andRK+WVfKqJILMVdx/69xjAzW4KUqsjr98GqzFR793lfNHrw1Blc8UZHWOBrRhtLx3SM38R1MpRegLTHgHzf0EAa3oUeWcQ=. Then, look for the substring ‘CTF’ in the decrypted data.

Fortunately, one of our keys, 11110001110011111001111111000100101111110011010111011001111010 (0x3c73e7f12fcd767a) decrypted the encrypted flag into such text:

stsio@stsio:/tmp/openssl-1.1.1a⟫ echo "U2FsdGVkX1/andRK+WVfKqJILMVdx/69xjAzW4KUqsjr98GqzFR793lfNHrw1Blc8UZHWOBrRhtLx3SM38R1MpRegLTHgHzf0EAa3oUeWcQ=" | openssl enc -aes-256-cbc -d -pbkdf2 -md sha1 -base64 -pass file:/tmp/3c73e7f12fcd767a.key

Flag: CTF{reversing_cellular_automatas_can_be_done_bit_by_bit}