Google Capture The Flag 2019 (Quals) Writeup

この大会は2019/6/22 9:00(JST)～2019/6/24 9:00(JST)に開催されました。
今回もチームで参戦。結果は501点で276チーム中83位でした。
自分で解けた問題をWriteupとして書いておきます。

Reverse a cellular automata (CRYPTO)

Wolfram rule 126というアルゴリズムの問題。rule 126は以下のような変換をするアルゴリズムで、逆変換は複数の値が候補に挙がる。
2進数の先頭からその前（先頭の場合は末尾)とその後（末尾の場合は先頭）を含め、以下のパターンで変換する。

変換前	変換後
111	0
110	1
101	1
100	1
011	1
010	1
001	1
000	0

例えば、011.......111の場合、
先頭の文字は101→1
次の文字は011→1
　　　：
最後から2番目の文字は111→0
最後の文字は110→1

このことを前提に66de3c1bf87fdfcfになる元のhexデータの候補を見つける。

zero = ['000', '111']
one = ['110', '101', '100', '011', '010', '001']

step = bin(int('66de3c1bf87fdfcf', 16))[2:].zfill(64)

dec = []
for i in range(64):
    if i == 0:
        if step[i] == '0':
            for b in zero:
                dec.append(b)
        else:
            for b in one:
                dec.append(b)
    else:
        tmp = []
        for d in dec:
           for zo in ['0', '1']:
               text = d[i] + d[i+1] + zo
               if step[i] == '0' and text in zero:
                   tmp.append(d + zo)
               elif step[i] == '1' and text in one:
                   tmp.append(d + zo)
        dec = tmp

rev = []
for b in dec:
    if b[0] == b[-2] and b[1] == b[-1]:
        rev.append(b[1:-1])

for r in rev:
    print '%x' % int(r, 2)

結果、10752通りの候補が挙がる。あとはブルートフォースで復号し、フラグ文字が入っているものを探す。

import subprocess

def exec_cmd(cmd):
    proc = subprocess.Popen(cmd, shell=True, stdin  = subprocess.PIPE,
        stdout = subprocess.PIPE, stderr = subprocess.PIPE)
    stdout_data, stderr_data = proc.communicate()
    return stdout_data

CMD_FORMAT1 = 'echo \"%s\" > /tmp/plain.key;' \
            + ' xxd -r -p /tmp/plain.key > /tmp/enc.key'
CMD_FORMAT2 = 'echo \"%s\" | openssl enc -d -aes-256-cbc -pbkdf2 -md sha1' \
            + ' -base64 --pass file:/tmp/enc.key'
enc_flag = 'U2FsdGVkX1/andRK+WVfKqJILMVdx/69xjAzW4KUqsjr98GqzFR793lfNHrw1Blc8UZHWOBrRhtLx3SM38R1MpRegLTHgHzf0EAa3oUeWcQ='

with open('result.txt', 'r') as f:
    keys = f.readlines()

for key in keys:
    cmd = CMD_FORMAT1 % key.rstrip()
    exec_cmd(cmd)

    cmd = CMD_FORMAT2 % enc_flag
    ret = exec_cmd(cmd)
    if 'CTF' in ret:
        print 'key  =', key.rstrip()
        print 'flag =', ret
        break

実行結果は以下の通り。

key  = 3c73e7f12fcd767a
flag = CTF{reversing_cellular_automatas_can_be_done_bit_by_bit}

CTF{reversing_cellular_automatas_can_be_done_bit_by_bit}