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:
0110011011011110001111000001101111111000011111111101111111001111
Assuming a is either 0 or 1 and b = !a, we can deduce part of the pattern of the previous step:

aabbbbaaabbba_________________________________________________ba
0110011011011110001111000001101111111000011111111101111111001111

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

_____________cdddddc____________________________________________
0110011011011110001111000001101111111000011111111101111111001111

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

____________________efffffffeeef________________________________
___________________________________ghhhhhhg_____________________
________________________________________________jiiij___________
________________________________________________________lkkkkl__
0110011011011110001111000001101111111000011111111101111111001111

Combining all parts we get the pattern:

aabbbbaaabbbacdddddcefffffffeeef___ghhhhhhg_____jiiij___lkkkklba
0110011011011110001111000001101111111000011111111101111111001111

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])
                  print(bin_str)

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

...
1100001110001011111001111111000111001111110010110111010101111001
1100001110001011111001111111000111001111110010110111011001111001
1100001110001011111001111111000111001111110011000111000101111001
1100001110001011111001111111000111001111110011000111001001111001
1100001110001011111001111111000111001111110011000111001101111001
...

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
CTF{reversing_cellular_automatas_can_be_done_bit_by_bit}

Flag: CTF{reversing_cellular_automatas_can_be_done_bit_by_bit}