pbctf 2021 Writeup

この大会は2021/10/9 9:00(JST)～2021/10/11 9:00(JST)に開催されました。
今回もチームで参戦。結果は 134点で210チーム中201位でした。
自分で解けた問題をWriteupとして書いておきます。

Alkaloid Stream (Crypto)

暗号の処理概要は以下の通り。

・flag: flagを2進数表記
・key = keygen(len(flag))
・keystream, public = gen_keystream(key)
　※len(key)=600の場合
　・i=0, j=0, fake[0] ^= key[1]
　・i=0, j=1, fake[0] ^= key[2]
　　　　　　：
　・i=0, j=199, fake[0] ^= key[200]
　・i=1, j=0, fake[1] ^= key[2]
　・i=1, j=1, fake[1] ^= key[3]
　　　　　　：
　・i=1, j=199, fake[1] ^= key[201]
　　　　　　：
　・i=398, j=0, fake[398] ^= key[399]
　　　　　　：
　・i=399, j=199, fake[399] ^= key[598]
　・i=399, j=0, fake[399] ^= key[400]
　　　　　　：
　・i=399, j=199, fake[399] ^= key[599]
　・i=597, j=0, fake[597] ^= key[598]
　・i=597, j=1, fake[597] ^= key[599]
　・i=598, j=0, fake[598] ^= key[599]

このことから以下のように算出し、fakeとkeyを求めることができる。

fake[599] = 0 -> key[599] = ペアの数値
fake[598] = key[599] -> key[598] = ペアの数値
fake[597] = key[598] ^ key[599] -> key[597] = ペアの数値
fake[596] = key[597] ^ key[598] ^ key[599] -> key[596] = ペアの数値
　　　　　　：

fakeとkeyを求めたら、keystreamを算出し、暗号文とXORをとればフラグになる。

#!/usr/bin/python3
import copy

def xor(a, b):
    return [x ^ y for x, y in zip(a, b)]

def recover_keystream(key, public):
    st = set(key)
    keystream = []
    for v0, v1 in public:
        if v0 in st:
            keystream.append(0)
        elif v1 in st:
            keystream.append(1)
        else:
            assert False, "Failed to recover the keystream"
    return keystream

def bytes_to_bits(inp):
    res = []
    for v in inp:
        res.extend(list(map(int, format(v, '08b'))))
    return res

def bits_to_bytes(inp):
    res = []
    for i in range(0, len(inp), 8):
        res.append(int(''.join(map(str, inp[i:i+8])), 2))
    return bytes(res)

with open('output.txt', 'r') as f:
    enc = bytes.fromhex(f.readline().rstrip())
    public = eval(f.readline().rstrip())

ln = len(public)

key = [0] * ln
fake = [0] * ln
tmp_pub = copy.copy(public)

for i in range(ln - 1, -1, -1):
    for p in tmp_pub:
        if p[0] == fake[i]:
            key[i] = p[1]
            if i > 0:
                for j in range(ln // 3):
                    if i + j >= ln:
                        break
                    fake[i-1] ^= key[i + j]
            tmp_pub.remove([p[0], p[1]])
            break
        if p[1] == fake[i]:
            key[i] = p[0]
            if i > 0:
                for j in range(ln // 3):
                    if i + j >= ln:
                        break
                    fake[i-1] ^= key[i + j]
            tmp_pub.remove([p[0], p[1]])
            break

keystream = recover_keystream(key, public)

enc = bytes_to_bits(enc)
flag = bits_to_bytes(xor(enc, keystream)).decode()
print(flag)

pbctf{super_duper_easy_brute_forcing_actually_this_one_was_made_by_mistake}