Cyber Apocalypse 2021 | Tetris

#cyber_apocalypse_ctf_2021

# The flag consists of only uppercase ascii letters
# You do have to fix up the flag format yourself

import string, hashlib, itertools

def clean(x):
    return ''.join(c for c in x.upper() if c in string.ascii_letters)

def transpose(x, l):
    return ''.join(x[i::l] for i in range(l))

def alphabet(r):
    a = list(string.ascii_uppercase)
    for i in range(len(a) - 1, 0, -1):
        j = r.randrange(0, i)
        a[i], a[j] = a[j], a[i]
    return ''.join(a)

def encrypt(text, l, key):
    enc = text.translate(''.maketrans(string.ascii_uppercase, key))
    return transpose(enc, l)

class RNG:
    A = 101565695086122187
    C = 56502943171806276
    M = 288230376151711717
    def __init__(self, seed):
        self.state = seed

    def next(self):
        self.state = ((self.state * self.A) + self.C) % self.M
        return self.state

    def randrange(self, low, high):
        assert high > low
        range = high - low
        limit = range * (self.M // range)
        while True:
            res = self.next()
            if res <= limit:
                return (res % range) + low

if __name__ == "__main__":
    with open("content.txt", "r") as f:
        text = clean(f.read())
    with open("flag.txt", "r") as f:
        text += clean(f.read())
    seed = int.from_bytes(hashlib.sha256(text.encode()).digest(), "big")
    rng = RNG(seed)
    L = rng.randrange(1, 100)
    print(f"{L = }")
    key = alphabet(rng)
    with open("content.enc.txt", "w") as f:
        f.write(encrypt(text, L, key))

overview

• PRNG は単純な 線形合同法

• alphabet は uppercaseを RNG の出力に従ってシャッフルしたもの

• encrypt は平文を alphabet の順に並び替えた上で、 L を鍵として transpose して順序を変えたもの

• 平文は適当な文字列にフラグを付け加えたもの

• L は出力されているが与えられていない

solution

• 単一換字暗号 として カシスキーテスト をやって文字の対応を探したあと、 L は全探索すれば良さそう

from collections import Counter
import string, itertools, math

def clean(x):
    return ''.join(c for c in x.upper() if c in string.ascii_letters)

def untranspose(c, l):
    n = len(c) // l
    r = []
    s = 0
    for i in range(l):
        t = n
        if len(c) % l > i:
            t = n + 1
        r.append(c[s:s+t])
        s += t
    res = ''.join(''.join(p) for p in itertools.zip_longest(*r, fillvalue=''))
    assert c == ''.join(res[i::l] for i in range(l))
    return res

def quadgramstats(x):
    c = Counter(x[i:i+4] for i in range(len(x) - 4))
    return {k:math.log(v / len(x), 10) for k, v in c.most_common()}

def score(x):
    return sum(targetQuad.get(x[i:i+4], -24) for i in range(len(x) - 4)) / (len(x) - 3)

def fullscore(x, key):
    return score(x.translate(''.maketrans(string.ascii_uppercase, key)))

def swap(x, a, b):
    assert a <= b
    if a == b: return x
    return x[:a] + x[b] + x[a+1:b] + x[a] + x[b+1:]

def hillclimb(c):
    key = string.ascii_uppercase
    target = fullscore(c, key)
    change = True
    while change:
        change = False
        for a in range(1, 26):
            for b in range(a):
                t = swap(key, b, a)
                ts = fullscore(c, t)
                if ts > target:
                    target = ts
                    change = True
                    key = t
    return key

reference = clean(open("atotc.txt", "r").read())
targetQuad = quadgramstats(reference)
ctxt = clean(open("content.enc.txt", "r").read())
best = None
bb = -float("inf")
bl = -1
for L in range(1, 100):
    t = untranspose(ctxt, L)
    key = hillclimb(t)
    p = t.translate(''.maketrans(string.ascii_uppercase, key))
    bb, bl, best = max((bb, bl, best), (s := score(p), L, p))
    print(L, "=>", s)
print(bb, bl, best)