TokyoWesterns CTF 6th 2020 writeup - XOR and shift encryptor

#!/usr/bin/python3

s = []
p = 0

def init():
  global s,p
  s = [i for i in range(0,64)]
  p = 0
  return

def randgen():
  global s,p
  a = 3
  b = 13
  c = 37
  s0 = s[p]
  p = (p + 1) & 63
  s1 = s[p]
  res = (s0 + s1) & ((1<<64)-1)
  s1 ^= (s1 << a) & ((1<<64)-1)
  s[p] = (s1 ^ s0 ^ (s1 >> b) ^ (s0 >> c))  & ((1<<64)-1)
  return res

def jump(to):
  # Deleted...
  return

def check_jump():
   ...

check_jump()

init()
for a in range(31337):randgen()

flag = open("flag.txt").read()
assert len(flag) == 256

enc = b""

for x in range(len(flag)):
  buf = randgen()
  sh = x//2
  if sh > 64:sh = 64
  mask = (1 << sh) - 1
  buf &= mask
  jump(buf)
  enc += bytes([ ord(flag[x]) ^ (randgen() & 0xff) ])
  print ("%r" % enc)

open("enc.dat","wb").write(bytearray(enc))

The given python script implements a random number generator like xorshift but 64 internal states. The script requires to generate number quite a lot of times and define utility to do it jump. But it is deleted, so our purpose is to implement a fast jump function.

So, in such a case, we want to use the mathematical tool recurrence formula and matrix exponentiation. If we could show the xorshift algorithm as the recurrence formula and accumulate them into the matrix multiplication, it becomes very easy to repeat.

For this purpose, we are thinking of the and make each state a vector who has 64 elements. On the , XOR operation is equivalent to the addition. As treating each state as the vector, we can use matrix operation to update all states at once.

Luckily, knowing the matrix means the left/right shift operation, we can write down all operations about xorshift in the matrix context. For example, updating s1 is shown in the following, where means x bit left shift matrix and means right shift matrix.

Now nothing is hard. The following formula updates internal states simultaneously.

In this form, multiple times update can be shown using the matrix exponentiation. Let the above formula as . For example, jump(n) is made by .

So now, we can easily implement jump using the matrix form of xorshift. As the large size (64² * 64²) matrix, the calculation is heavy. However, this method is faster than in other ways. On my laptop, 30minutes - 1hour to finish and yield all the keys by the following script.

gist.github.com

reference: TinyMTの更新を行列で書いてみようのコーナー(前編) - yatsuna_827’s blog