pbctf 2021 Writeup

Mon Oct 11 2021

    10/9-11 で開催していた pbctf 2021 にチーム WreckTheLine で参加しました。結果は 13th/210 (得点のあるチームのみカウント) でした。 Yet Another PRNG はじっくり時間をかけ、ありとあらゆる手を尽くしたけど解けなくてつらい… 以下 Crypto 問の writeup です。

    Crypto

    Yet Another RSA

    12 solves

    gen.py
    #!/usr/bin/env python3
    
    from Crypto.Util.number import *
    import random
    
    
    def genPrime():
        while True:
            a = random.getrandbits(256)
            b = random.getrandbits(256)
    
            if b % 3 == 0:
                continue
    
            p = a ** 2 + 3 * b ** 2
            if p.bit_length() == 512 and p % 3 == 1 and isPrime(p):
                return p
    
    
    def add(P, Q, mod):
        m, n = P
        p, q = Q
    
        if p is None:
            return P
        if m is None:
            return Q
    
        if n is None and q is None:
            x = m * p % mod
            y = (m + p) % mod
            return (x, y)
    
        if n is None and q is not None:
            m, n, p, q = p, q, m, n
    
        if q is None:
            if (n + p) % mod != 0:
                x = (m * p + 2) * inverse(n + p, mod) % mod
                y = (m + n * p) * inverse(n + p, mod) % mod
                return (x, y)
            elif (m - n ** 2) % mod != 0:
                x = (m * p + 2) * inverse(m - n ** 2, mod) % mod
                return (x, None)
            else:
                return (None, None)
        else:
            if (m + p + n * q) % mod != 0:
                x = (m * p + (n + q) * 2) * inverse(m + p + n * q, mod) % mod
                y = (n * p + m * q + 2) * inverse(m + p + n * q, mod) % mod
                return (x, y)
            elif (n * p + m * q + 2) % mod != 0:
                x = (m * p + (n + q) * 2) * inverse(n * p + m * q + r, mod) % mod
                return (x, None)
            else:
                return (None, None)
    
    
    def power(P, a, mod):
        res = (None, None)
        t = P
        while a > 0:
            if a % 2:
                res = add(res, t, mod)
            t = add(t, t, mod)
            a >>= 1
        return res
    
    
    def random_pad(msg, ln):
        pad = bytes([random.getrandbits(8) for _ in range(ln - len(msg))])
        return msg + pad
    
    
    p, q = genPrime(), genPrime()
    N = p * q
    phi = (p ** 2 + p + 1) * (q ** 2 + q + 1)
    
    print(f"N: {N}")
    
    d = getPrime(400)
    e = inverse(d, phi)
    k = (e * d - 1) // phi
    
    print(f"e: {e}")
    
    to_enc = input("> ").encode()
    ln = len(to_enc)
    
    print(f"Length: {ln}")
    
    pt1, pt2 = random_pad(to_enc[: ln // 2], 127), random_pad(to_enc[ln // 2 :], 127)
    
    M = (bytes_to_long(pt1), bytes_to_long(pt2))
    E = power(M, e, N)
    
    print(f"E: {E}")

    問題名や変数名 (p,q,N,ϕ,e,dp, q, N, \phi, e, d など) からして RSA の亜種でしょう。 add がどのような計算になっているのかは全く追えていないですが、 RSA と同様、 ed=1modϕed = 1 \mod \phi なる dd を用いて M=EdmodNM = E^d \mod N と復号できるようです。 RSA と異なる点としては ϕ=(p2+p+1)(q2+q+1)\phi = (p^2 + p + 1)(q^2 + q + 1) であることぐらいです。

    dd は400bits以下であり他の数と比べて小さいです。なので Boneh-Durfee のような方法が使えないか考えます。 ϕ\phip,qp, q について対称式なので、 p+q,pq=Np + q, pq = N を使って表すように式変形をすると、

    ϕ=N2+N(p+q)+(p+q)2N+(p+q)+1\phi = N^2 + N(p+q) + (p+q)^2 - N + (p + q) + 1

    となります。 ed=kϕ+1ed = k\phi + 1 について mode\mod e を取ることで、 kϕ+1=0k\phi + 1 = 0 となり、 k,p+qk, p+q について解く形となります。これを defund-san の coppersmith を使って解きました。 これが解ければ p+q,pqp + q, pq が既知なことから二次方程式を解くことで p,qp, q が求まり、 ϕdM\phi \to d \to M とわかります。

    solve.sage
    # https://github.com/defund/coppersmith
    R = Integers(e)
    PR.<p_q, k> = PolynomialRing(R)
    f = k * (N**2 + N*p_q + p_q**2 - N + p_q + 1) + 1
    bounds = (2**513, 2**400)
    p_q, k = small_roots(f, bounds, m=3, d=4)[0]
    
    PR.<x> = PolynomialRing(ZZ)
    f = x**2 - int(p_q) * x + N
    (p, _), (q, _) = f.roots()
    phi = (p ** 2 + p + 1) * (q ** 2 + q + 1)
    d = int(pow(e, -1, phi))
    tmp = power(E, d, N)
    print(long_to_bytes(tmp[0]))
    print(long_to_bytes(tmp[1]))

    pbctf{I_love_to_read_crypto_papers_and_implement_the_attacks_from_them}

    first blood でした!ガチな CTF かつ難しめな問題で first blood 取れたのは恐らく初めてです。嬉しい

    Seed Me

    24 solves

    Main.java
    import java.nio.file.Files;
    import java.nio.file.Path;
    import java.io.IOException;
    import java.util.Random;
    import java.util.Scanner;
    
    class Main {
    
        private static void printFlag() {
            try {
                System.out.println(Files.readString(Path.of("flag.txt")));
            }
            catch(IOException e) {
                System.out.println("Flag file is missing, please contact admins");
            }
        }
    
        public static void main(String[] args) {
            int unlucky = 03777;
            int success = 0;
            int correct = 16;
    
            System.out.println("Welcome to the 'Lucky Crystal Game'!");
            System.out.println("Please provide a lucky seed:");
            Scanner scr = new Scanner(System.in);
            long seed = scr.nextLong();
            Random rng = new Random(seed);
    
            for(int i=0; i<correct; i++) {
                /* Throw away the unlucky numbers */
                for(int j=0; j<unlucky; j++) {
                    rng.nextFloat();
                }
    
                /* Do you feel lucky? */
                if (rng.nextFloat() >= (7.331f*.1337f)) {
                    success++;
                }
            }
    
            if (success == correct) {
                printFlag();
            }
            else {
                System.out.println("Unlucky!");
            }
        }
    }

    2048回ごとに rng.nextFloat() >= (7.331f*.1337f) (約0.98) となる乱数を生成するような seed を指定することができればフラグが得られます。

    まず java の Random の仕様について調べます。 ここ を参考にしました (writeup を書くときに気づいたけどバージョン一致してなかったっぽい、危ない…)。 python でそれっぽく書くとこんな感じです。

    java_random.py
    class Random():
        def __init__(self, seed):
            self.seed = (seed ^ 0x5DEECE66D) % 2 ** 48
    
        def next(self, bits):
            self.seed = (self.seed * 0x5DEECE66D + 0xB) % 2 ** 48
            return self.seed >> (48 - bits)
    
        def next_float(self):
            return self.next(24) / (1 << 24)

    __init__ で xor が取られていることを除けば、LCG となっていることがわかります。 A=0x5DEECE66D,B=0xB,M=248,x=seedA = \mathrm{0x5DEECE66D}, B = \mathrm{0xB}, M = 2^{48}, x = \mathrm{seed} とおくと、 next_float を呼ぶたびに x=Ax+BmodMx = Ax + B \mod M と更新されます。 nn 番目の xxAnx0+Bk=0n1AkA^n x_0 + B \sum_{k=0}^{n-1}A^k と表されます。これが n=0mod2048,2048n2048×16n = 0 \mod 2048, 2048 \le n \le 2048 \times 16 のときにある値より大きく、 MM より小さくなる、という問題を解くことに繋がるのですが、これは CVP を解くことに相当します。もっというと rkm-san のソルバ が刺さります。

    しかしナイーブに実装すると、15回以下の回数成功する seed は簡単に見つかるのですが、16回成功するものは意外と見つかりません。 上記ソルバの実装を見てみると (初めて見たことがバレた) (lb + ub) // 2 を target として CVP を解いています。そこで lb を各回数目で緩めたり厳しくしたりすることでなんとか所望の seed を見つけ出しました。ハイパラチューニング感…。

    solve.sage
    A = 0x5DEECE66D
    B = 0xB
    M = 2 ** 48
    thres = int(7.331 * 0.1337 * (1 << 24)) + 1
    
    const_list = []
    for i in range(2048, 2048+2048*20, 2048):
        tmp = 0
        for j in range(i):
            tmp += pow(A, j, M)
            tmp %= M
        tmp *= B
        tmp %= M
        const_list.append(int(tmp))
    mul_list = []
    for i in range(2048, 2048+2048*20, 2048):
        mul_list.append(int(pow(A, i, M)))
    
    # https://github.com/rkm0959/Inequality_Solving_with_CVP
    N = 16
    mat = Matrix(ZZ, 1+N, N+1)
    for i in range(N):
        mat[0, i] = int(mul_list[i])
        mat[1+i, i] = int(-M)
    mat[0, N] = 1
    lb = [(thres + 25000) * 2**24] + [(thres-55000) * 2**24] * (N-1) + [0]
    for i in range(N):
        lb[i] -= const_list[i]
    ub = [M] * N + [2**48]
    for i in range(N):
        ub[i] -= const_list[i]
    res = solve(mat, lb, ub)
    print(int(res[2][0]) ^^ A)
    # 272526698751795

    pbctf{intended_is_LLL_with_branch_and_bound_9ad09becbc4c7685}

    branch_and_bound ってなんだろう。

    GoodHash

    30 solves

    main.py
    #!/usr/bin/env python3
    
    from Crypto.Cipher import AES
    from Crypto.Util.number import *
    from flag import flag
    import json
    import os
    import string
    
    ACCEPTABLE = string.ascii_letters + string.digits + string.punctuation + " "
    
    
    class GoodHash:
        def __init__(self, v=b""):
            self.key = b"goodhashGOODHASH"
            self.buf = v
    
        def update(self, v):
            self.buf += v
    
        def digest(self):
            cipher = AES.new(self.key, AES.MODE_GCM, nonce=self.buf)
            enc, tag = cipher.encrypt_and_digest(b"\0" * 32)
            return enc + tag
    
        def hexdigest(self):
            return self.digest().hex()
    
    
    if __name__ == "__main__":
        token = json.dumps({"token": os.urandom(16).hex(), "admin": False})
        token_hash = GoodHash(token.encode()).hexdigest()
        print(f"Body: {token}")
        print(f"Hash: {token_hash}")
    
        inp = input("> ")
        if len(inp) > 64 or any(v not in ACCEPTABLE for v in inp):
            print("Invalid input :(")
            exit(0)
    
        inp_hash = GoodHash(inp.encode()).hexdigest()
    
        if token_hash == inp_hash:
            try:
                token = json.loads(inp)
                if token["admin"] == True:
                    print("Wow, how did you find a collision?")
                    print(f"Here's the flag: {flag}")
                else:
                    print("Nice try.")
                    print("Now you need to set the admin value to True")
            except:
                print("Invalid input :(")
        else:
            print("Invalid input :(")

    AES GCM モードの問題。ある nonce で b"\0" * 32 を暗号化したときの暗号文とタグが与えられます。それらの暗号文、タグと全く同じ暗号化がされる nonce のうち、 "admin":true を含んだ json 形式のものを見つけられればフラグが得られます。

    nonce が12bytesでないときの処理を詳しく知らなかったので、 pycryptodome の実装 を眺めました。

    _mode_gcm.py
            # Step 1 in SP800-38D, Algorithm 4 (encryption) - Compute H
            # See also Algorithm 5 (decryption)
            hash_subkey = factory.new(key,
                                      self._factory.MODE_ECB,
                                      **cipher_params
                                      ).encrypt(b'\x00' * 16)
    
            # Step 2 - Compute J0
            if len(self.nonce) == 12:
                j0 = self.nonce + b"\x00\x00\x00\x01"
            else:
                fill = (16 - (len(nonce) % 16)) % 16 + 8
                ghash_in = (self.nonce +
                            b'\x00' * fill +
                            long_to_bytes(8 * len(nonce), 8))
                j0 = _GHASH(hash_subkey, ghash_c).update(ghash_in).digest()
    
            # Step 3 - Prepare GCTR cipher for encryption/decryption
            nonce_ctr = j0[:12]
            iv_ctr = (bytes_to_long(j0) + 1) & 0xFFFFFFFF
            self._cipher = factory.new(key,
                                       self._factory.MODE_CTR,
                                       initial_value=iv_ctr,
                                       nonce=nonce_ctr,
                                       **cipher_params)
    
            # Step 5 - Bootstrat GHASH
            self._signer = _GHASH(hash_subkey, ghash_c)
    
            # Step 6 - Prepare GCTR cipher for GMAC
            self._tag_cipher = factory.new(key,
                                           self._factory.MODE_CTR,
                                           initial_value=j0,
                                           nonce=b"",
                                           **cipher_params)

    12bytesの nonce のときは、 j0 = nonce||00000001 として CTR モードを使っているのに対し、12bytesでないときは _GHASH というものを通したものを j0 としています。 j0 が一致していれば暗号文、タグも一致するので、以下ではこの _GHASH が衝突する条件を考えていきます。

    _GHASH実装 を見てみると、 docstring に書かれていることがすべてでした。

    _mode_gcm.py
    class _GHASH(object):
        """GHASH function defined in NIST SP 800-38D, Algorithm 2.
        If X_1, X_2, .. X_m are the blocks of input data, the function
        computes:
           X_1*H^{m} + X_2*H^{m-1} + ... + X_m*H
        in the Galois field GF(2^256) using the reducing polynomial
        (x^128 + x^7 + x^2 + x + 1).
        """
    

    これが一致するような nonce を探索させました。

    具体的には、 {"admin":true,"A || 16bytes || 16bytes || dmin": false} という形式の文字列を送ることを考えます。16bytesの中に ACCEPTABLE に含まれない文字や " が含まれていない限り、この json は admin=true となります。また、元の nonce と4番目以降のブロック (pad も含む) が同じになるため、最初の3ブロックだけ考えればいいことになります。 計算はごり押しで行ったため、特に言うことはないです…もっと賢くできそうだけど思いつかなかったです。

    solve.sage
    from itertools import product
    
    from Crypto.Util.number import bytes_to_long
    from pwn import remote
    
    
    X = GF(2).polynomial_ring().gen()
    poly = X ** 128 + X ** 7 + X ** 2 + X ** 1 + 1
    F = GF(2 ** 128, name='a', modulus=poly)
    R.<x> = PolynomialRing(F)
    
    
    def tobin(x, n):
        x = Integer(x)
        nbits = x.nbits()
        assert nbits <= n
        return [0] * (n - nbits) + x.bits()[:: -1]
    
    
    def frombin(v):
        return int("".join(map(str, v)), 2)
    
    
    def toF(x):
        x = frombin(tobin(x, 128)[:: -1])
        return F.fetch_int(x)
    
    
    def fromF(x):
        x = x.integer_representation()
        x = frombin(tobin(x, 128)[:: -1])
        return x
    
    
    key = b"goodhashGOODHASH"
    cipher = AES.new(key, mode=AES.MODE_ECB)
    H = toF(bytes_to_long(cipher.encrypt(b"\x00" * 16)))
    
    io = remote("good-hash.chal.perfect.blue", 1337)
    io.recvuntil(b"Body: ")
    token = io.recvline().strip().decode()
    io.recvuntil(b"Hash: ")
    _hash = io.recvline().strip().decode()
    print(_hash)
    
    j0_token = toF(0)
    for i in range(0, 48, 16):
        j0_token += toF(bytes_to_long(token[i:i+16].encode())) * H**((80-i)//16)
    rhs = (j0_token - toF(bytes_to_long(new_token_prefix.encode())) * H**5) / H**3
    
    for elems in product(ACCEPTABLE[:62], repeat=16):
        tmp = "".join(elems)
        root = toF(bytes_to_long(tmp.encode())) * H + rhs
        try:
            inp = long_to_bytes(fromF(root)).decode()
            tmp_token = long_to_bytes(fromF(root))
            new_token = (new_token_prefix.encode() + tmp.encode() + tmp_token + b'dmin": false}').decode()
            # GoodHash(token.encode()).digest() == GoodHash(new_token.encode()).digest()
            if any(v not in ACCEPTABLE for v in inp):
                continue
            print("Found!!!")
            io.sendlineafter(b"> ", new_token)
            print(io.recvline())
            print(io.recvline())
            io.close()
            break
        except UnicodeDecodeError:
            continue

    pbctf{GHASH_is_short_for_GoodHash_:joy:}

    Steroid Stream

    38 solves

    gen.py
    #!/usr/bin/env python3
    
    import random
    from flag import flag
    
    def keygen(ln):
        # Generate a linearly independent key
        arr = [ 1 << i for i in range(ln) ]
    
        for i in range(ln):
            for j in range(i):
                if random.getrandbits(1):
                    arr[j] ^= arr[i]
        for i in range(ln):
            for j in range(i):
                if random.getrandbits(1):
                    arr[ln - 1 - j] ^= arr[ln - 1 - i]
    
        return arr
    
    def gen_keystream(key):
        ln = len(key)
        assert ln > 50
        
        # Generate some fake values based on the given key...
        fake = [0] * ln
        for i in range(ln - ln // 3):
            arr = list(range(i + 1, ln))
            random.shuffle(arr)
            for j in arr[:ln // 3]:
                fake[i] ^= key[j]
    
        # Generate the keystream
        res = []
        for i in range(ln):
            t = random.getrandbits(1)
            if t:
                res.append((t, [fake[i], key[i]]))
            else:
                res.append((t, [key[i], fake[i]]))
    
        # Shuffle!
        random.shuffle(res)
    
        keystream = [v[0] for v in res]
        public = [v[1] for v in res]
        return keystream, public
    
    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)
    
    flag = bytes_to_bits(flag)
    
    key = keygen(len(flag))
    keystream, public = gen_keystream(key)
    assert keystream == recover_keystream(key, public)
    enc = bits_to_bytes(xor(flag, keystream))
    
    print(enc.hex())
    print(public)

    ビットをごちゃまぜにして作った線形独立な key に対し、これらの key を205個 (=len(public)//3) 足し合わせて (xor の意味) fake が作られています。 public の各行でどちらが fake でどちらが key かを見破ることができればフラグが復元できます。

    fake の作り方からして、 fake の205個の要素については必ず0になることがわかります。そのため public に0があれば、その行の0でないほうは key で確定です。これで key が205個求まります。

    今、 key として確定したものの数を n205n \ge 205 とします。これらの keyn×lnn \times \mathrm {ln} の行列 KK を作ります。 fake の中に必ず1つは fake=sK,m=1nsm=205\mathrm{fake} = sK, \sum_{m=1}^n s_m = 205 となるものが存在することが示せます。このような fakepublic のある行から見つけることができれば、その他方は key で確定し、 n++ します。 これを繰り返すことですべての key が求まるため keystream を復元することができます。

    ↓のソルバは結構重く、30分ぐらいかかってしまった…

    solve.sage
    from binascii import unhexlify
    
    
    enc = unhexlify("792137ecd08d478208e850a60680ccb7e937778222b1ceb8a1ac89046f421706930d240300cdf3ed07691c14a5ed60b226841238fee420feda73174021a557f552b5181dfb717aee329c44b90a")
    
    ln = len(public)
    public_bits = []
    for i, p in enumerate(public):
        tmp0 = []
        tmp1 = []
        for j in range(ln):
            tmp0.append((p[0] & (1 << j)) // (1 << j))
            tmp1.append((p[1] & (1 << j)) // (1 << j))
        public_bits.append([vector(GF(2), tmp0), vector(GF(2), tmp1)])
    used = [0] * ln
    
    mat = matrix(GF(2), ln, ln)
    n_found = 0
    cands = []
    for i, p in enumerate(public):
        if p[0] == 0:
            mat[n_found] = public_bits[i][1]
            n_found += 1
        elif p[1] == 0:
            mat[n_found] = public_bits[i][0]
            n_found += 1
        else:
            cands.append(i)
    
    while True:
        if n_found == ln:
            break
        cur_cands = []
        for idx in cands:
            try:
                ans = mat[:n_found].solve_left(public_bits[idx][0])
                if sum(ans.change_ring(ZZ)) == ln // 3:
                    cur_cands.append((idx, 1))
            except ValueError as e:
                pass
            try:
                ans = mat[:n_found].solve_left(public_bits[idx][1])
                if sum(ans.change_ring(ZZ)) == ln // 3:
                    cur_cands.append((idx, 0))
            except ValueError as e:
                pass
        print(n_found, cur_cands)
        if len(cur_cands) == 0:
            print("error!!!")
            break
        for idx, used in cur_cands:
            mat[n_found] = public_bits[idx][used]
            n_found += 1
            cands.remove(idx)
    
    key = []
    for i in range(ln):
        tmp = 0
        for j in range(ln):
            tmp += int(mat[i, j]) * (1 << j)
        key.append(tmp)
    
    keystream = recover_keystream(key, public)
    print(bits_to_bytes(xor(bytes_to_bits(enc), keystream)))

    pbctf{I_hope_you_enjoyed_this_challenge_now_how_about_playing_Metroid_Dread?}

    Alkaloid Stream

    132 solves

    gen.py
    #!/usr/bin/env python3
    
    import random
    from flag import flag
    
    def keygen(ln):
        # Generate a linearly independent key
        arr = [ 1 << i for i in range(ln) ]
    
        for i in range(ln):
            for j in range(i):
                if random.getrandbits(1):
                    arr[j] ^= arr[i]
        for i in range(ln):
            for j in range(i):
                if random.getrandbits(1):
                    arr[ln - 1 - j] ^= arr[ln - 1 - i]
    
        return arr
    
    def gen_keystream(key):
        ln = len(key)
        
        # Generate some fake values based on the given key...
        fake = [0] * ln
        for i in range(ln):
            for j in range(ln // 3):
                if i + j + 1 >= ln:
                    break
                fake[i] ^= key[i + j + 1]
    
        # Generate the keystream
        res = []
        for i in range(ln):
            t = random.getrandbits(1)
            if t:
                res.append((t, [fake[i], key[i]]))
            else:
                res.append((t, [key[i], fake[i]]))
    
        # Shuffle!
        random.shuffle(res)
    
        keystream = [v[0] for v in res]
        public = [v[1] for v in res]
        return keystream, public
    
    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)
    
    flag = bytes_to_bits(flag)
    
    key = keygen(len(flag))
    keystream, public = gen_keystream(key)
    assert keystream == recover_keystream(key, public)
    enc = bits_to_bytes(xor(flag, keystream))
    
    print(enc.hex())
    print(public)

    時系列的には Steroid Stream より先に出た問題です。diff は fake の作り方の部分です。

    shuffle 前の fake について、 fake[i] = fake[i-1] ^ key[i] (^ key[i + ln//3]) (i + ln//3ln 未満のときだけ最後の xor をする) となることが示せます。また fake の最後は必ず0となります。これらのことから fakekey を後ろ側から順に見つけていくことができます。

    solve.py
    from binascii import unhexlify
    
    
    enc = unhexlify(
        "cd4c1a7edd7a421dcea72ae8bf47946d74f6cdba763a6a052a3f2955333dc6fa267f5297c405bf807e922380ebf9628194bf319e8ae4074dc5476de1d81a52d72c29f0e8b590ac8f6a78bb"
    )
    
    key_rev = [None] * 600
    fake_rev = [None] * 600
    k_f = sum([[p[0], p[1]] for p in public], [])
    fake_rev[0] = 0
    # 同じ数が存在しているため、2通りの探索が必要。面倒なので正しいほうをハードコードしている
    key_rev[0] = 1400714221870952494615363674397671002942566332491236206763593417473795738355401350930926673064015705912976960035864926610332139062931171063676126565794843044414821051808290441350503
    fake_rev[1] = 1400714221870952494615363674397671002942566332491236206763593417473795738355401350930926673064015705912976960035864926610332139062931171063676126565794843044414821051808290441350503
    key_rev[1] = 2757696071210081807360560576412795699230755024318763149013967339353762389921680057821717495151761096162627419558972312206286782426655299773478926876284074659695710535424355133843847
    fake_rev[2] = 4089266517024382694848158990236371618525758802435666569113677651195292964914091912713023780032073401220483687541769102300167747815537847432448268329941427225831362872849233653867744
    for i in range(2, 599):
        idx = k_f.index(fake_rev[i])
        key_rev[i] = public[idx//2][1-idx%2]
        if i >= 200:
            fake_rev[i+1] = key_rev[i] ^ fake_rev[i] ^ key_rev[i - 200]
        else:
            fake_rev[i+1] = key_rev[i] ^ fake_rev[i]
    idx = k_f.index(fake_rev[599])
    key_rev[599] = public[idx//2][1-idx%2]
    
    keystream = recover_keystream(key_rev[::-1], public)
    
    enc_bits = bytes_to_bits(enc)
    print(bits_to_bytes(xor(enc_bits, keystream)))

    pbctf{super_duper_easy_brute_forcing_actually_this_one_was_made_by_mistake}