Insomni'hack 2018 teaser: Rule86

solve.py

from scryptos import *

N_BYTES = 32
N = 8 * N_BYTES

RULE = [86 >> i & 1 for i in range(8)]

def next(x):
  x = (x & 1) << N+1 | x << 1 | x >> N-1
  y = 0
  for i in range(N):
    y |= RULE[(x >> i) & 7] << i
  return y

plain = open('rule86.txt', 'rb').read()
cipher = open('rule86.txt.enc', 'rb').read()
base_key = bytes_to_long(xorstr(plain[:N_BYTES][::1], cipher[:N_BYTES][::1])[::-1])

print '[+] Base key: ', base_key
base_key_orig = base_key
base_key = map(int, format(base_key, '0%db' % N))[::-1]

rounds = r = N // 2
cand = [base_key]
while r != 0:
  cand_next = []
  for key in cand:
    for i1 in [0, 1]:
      for i2 in [0, 1]:
        k2 = [i1, i2]
        for j in xrange(N):
          k2 += [key[N-j-1] ^ (k2[j+1] | k2[j])]
        if k2[0] == k2[N] and k2[1] == k2[N+1]:
          k2 = k2[1:-1]
          cand_next += [k2[::-1]]
  cand = cand_next
  r -= 1

print map(lambda x: long_to_bytes(int(''.join(map(str, x[::-1])), 2))[::-1], cand)
for x in map(lambda x: int(''.join(map(str, x[::-1])), 2), cand):
  for _ in xrange(rounds):
    x = next(x)
  print x == base_key_orig
  assert x == base_key_orig

solve_log

Tue Jan 23 11:49:50 JST 2018 ~/Downloads/Rule86 100%
> python solve.py 
[+] Base key:  37450399269036614778703305999225837723915454186067915626747458322635448226786
['INS{Rule86_is_W0lfr4m_Cha0s}']
True