pbctf 2021 Writeup

October 11, 2021

Crypto Yet Another RSA Seed Me GoodHash Steroid Stream Alkaloid Stream

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, \phi, e, d$ など) からして RSA の亜種でしょう。 add がどのような計算になっているのかは全く追えていないですが、 RSA と同様、 $ed = 1 \mod \phi$ なる $d$ を用いて $M = E^d \mod N$ と復号できるようです。 RSA と異なる点としては $\phi = (p^2 + p + 1)(q^2 + q + 1)$ であることぐらいです。

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

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

となります。 $ed = k\phi + 1$ について $\mod e$ を取ることで、 $k\phi + 1 = 0$ となり、 $k, p+q$ について解く形となります。これを defund-san の coppersmith を使って解きました。これが解ければ $p + q, pq$ が既知なことから二次方程式を解くことで $p, q$ が求まり、 $\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 = \mathrm{0x5DEECE66D}, B = \mathrm{0xB}, M = 2^{48}, x = \mathrm{seed}$ とおくと、 next_float を呼ぶたびに $x = Ax + B \mod M$ と更新されます。 $n$ 番目の $x$ は $A^n x_0 + B \sum_{k=0}^{n-1}A^k$ と表されます。これが $n = 0 \mod 2048, 2048 \le n \le 2048 \times 16$ のときにある値より大きく、 $M$ より小さくなる、という問題を解くことに繋がるのですが、これは 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 として確定したものの数を $n \ge 205$ とします。これらの key で $n \times \mathrm {ln}$ の行列 $K$ を作ります。 fake の中に必ず1つは $\mathrm{fake} = sK, \sum_{m=1}^n s_m = 205$ となるものが存在することが示せます。このような fake が public のある行から見つけることができれば、その他方は 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//3 が ln 未満のときだけ最後の xor をする) となることが示せます。また fake の最後は必ず0となります。これらのことから fake と key を後ろ側から順に見つけていくことができます。

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}

Crypto Yet Another RSA Seed Me GoodHash Steroid Stream Alkaloid Stream