TSG CTF 2023 writeup - チョコラスクのブログ

TSG CTF 2023 に TokyoWesterns で参加し、2位を取ることができました！

私はcrypto全問とrev1問、misc1問を解き、うち2問でfirst bloodを取ることができました。

[crypto] Unique Flag
[crypto] Complicated Function
[crypto] Streamer
[crypto] RANDOM SEED RANDOM
[crypto] Learning with Exploitation
[crypto] Delta Force
[rev] beginners_rev_2023
[misc] Secret Sequence

[crypto] Unique Flag

次のソースコードとその実行結果が与えられます。

from Crypto.Util.number import getPrime

p = getPrime(1024)
q = getPrime(1024)
N = p * q
e = 0x10001

with open('flag.txt', 'rb') as f:
    flag = f.read()

assert len(flag) == 33

flag_header = flag[:7] # TSGCTF{
flag_content = flag[7:-1]
flag_footer = flag[-1:] # }

assert len(flag_content) == len({byte for byte in flag_content}) # flag_content is unique

c_list = [pow(byte, e, N) for byte in flag]
clues = [x * y % N for x, y in zip(c_list[:-1], c_list[1:])]
clues.sort()

print(f'N = {N}')
print(f'e = {e}')
print(f'clues = {clues}')

フラグの $i$ 文字目と $i+1$ 文字目をRSAで暗号化した結果の積たちをソートした配列 clues が与えられます。フラグの最初の7文字は TSGCTF{ であることがわかっています。

フラグの $i$ 文字目までがわかっているとして、次の文字を求めることを考えます。 $i+1$ 文字目として全ての文字を試し、 $i$ 文字目と $i+1$ 文字目を暗号化した結果の積が clues に含まれれば $i+1$ 文字目の候補とすればよいです。これを繰り返すことで、フラグが前から順に求まります。

ここで、フラグの {} 内の文字は相異なることが保証されてはいますが、このアルゴリズムにおいて次の文字の候補は複数ありうることに注意が必要です。例えば、flag[i]=3 で flag[i+1] を求めようとしているとき、その先に flag[j]=2, flag[j+1]=6 の箇所があれば、実際は flag[i+1] が4でなくても、flag[i+1]=4 が候補になってしまいます。

from Crypto.Util.number import *
from output import *

flag = b'TSGCTF{'
for i in range(6):
    c = pow(flag[i]*flag[i+1], e, N)
    clues.remove(c)

def solve(flag, clues):
    if len(flag) == 33:
        print(flag)
        return
    for i in range(0x20, 0x80):
        c = pow(flag[-1]*i, e, N)
        if c in clues:
            clues_nxt = clues[:]
            clues_nxt.remove(c)
            solve(flag+bytes([i]), clues_nxt)

solve(flag, clues)
# TSGCTF{OK,IsTHi5A_un1qUe-flag?XD}

[crypto] Complicated Function

次のソースコードとその実行結果が与えられます。

from Crypto.Util.number import isPrime, getStrongPrime
from math import isqrt, sin, ceil
from secrets import flag


def f(p):
    return isqrt(p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p))) + 2**1023


while True:
    p = getStrongPrime(1024)
    if p < 2**1023:
        continue
    q = f(p)
    if isPrime(q):
        break

N = p * q
e = 0x10001
m = int.from_bytes(flag, 'big')
c = pow(m, e, N)

print(f'N = {N}')
print(f'c = {c}')

RSA暗号の問題ですが、 $q$ の値が次のように $p$ の値から決められています。

q = isqrt(p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p))) + 2**1023

外側のルートの値は $p+2^{511}$ くらいになりそうです。そこで、ルートの値から $p$ を引いた値を出力させてみると、常に $2^{511}-4$ となることが推測できます。

def f(p):
    x = isqrt(p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p)))
    print(hex(x-p))
    return isqrt(p**2 + p * (2**512-6) + ceil(isqrt(p)*sin(p))) + 2**1023

よって、 $p(p+2^{1023}+2^{511}-4)=N$ なので、この $p$ についての2次方程式を解くことで $p$ が求まり、復号できます。

from Crypto.Util.number import *
from output import *
e = 0x10001

PR.<x> = PolynomialRing(ZZ)
f = x*(x+2**1023+2**511-4)-N
p = int(f.roots()[0][0])
q = N//p
m = pow(c, inverse(int(e), int((p-1)*(q-1))), N)
print(long_to_bytes(int(m)))
# TSGCTF{From which angle did you solve this, binary search or convergence of f(p)-p?}

first bloodでした。

[crypto] Streamer

次のソースコードとその実行結果が与えられます。

import secrets
import hashlib
import base64
import re

pattern = re.compile("[a-zA-Z0-9!-/:-?\[-`|~]+")
flag_content = b"@@REDUCTED@@"
assert pattern.fullmatch(flag_content.decode())

flag_hash = hashlib.md5(flag_content).digest()
flag = b"TSGCTF{"+flag_content+b"@"+base64.b64encode(flag_hash)+b"}"

key_stream = list(secrets.token_bytes(16))
encrypted_flags = [flag[i]^key_stream[i%16] for i in range(len(flag))]

print("cipher =",encrypted_flags)
print("flag_length =",len(flag))

16bytesの鍵を繰り返したものをフラグにXORしてできる暗号文が与えられます。フラグの {} 内は、flag_content, "@", flag_content のMD5ハッシュのbase64、を連結したものとなっています。

フラグの先頭は TSGCTF{ なので、鍵の先頭7bytesはわかります。また、MD5ハッシュは128bitなので、フラグのbase64部分は24文字で、後ろ2文字は == となります。よって、フラグの末尾は ==} なので、鍵の末尾3bytesもわかります。

鍵の残り6bytesは、フラグが表示可能な文字 (base64部分はbase64の文字) からなることを用いて全探索できます。

import hashlib
import base64
import string
from itertools import product
from output import *

key_stream = [-1]*16
for i in range(7):
    key_stream[i] = cipher[i] ^ b'TSGCTF{'[i]

key_stream[(flag_length-1)%16] = cipher[-1]^ord('}')
key_stream[(flag_length-2)%16] = cipher[-2]^ord('=')
key_stream[(flag_length-3)%16] = cipher[-3]^ord('=')

kouhos = []
for i in range(7, 13):
    kouho = []
    for c in range(0x20, 0x80):
        k = c^cipher[i]
        ok = True
        for j in range(i, flag_length, 16):
            if not (0x20 < (cipher[j]^k) < 0x80):
                ok = False
                break
            if j>=flag_length-25:
                if cipher[j]^k not in list((string.digits+string.ascii_letters+'/+=').encode()):
                    ok = False
                    break
        if ok:
            kouho.append(k)
    kouhos.append(kouho)

for key in product(*kouhos):
    key_stream = key_stream[:7]+list(key)+key_stream[13:]
    flag = [cipher[i]^key_stream[i%16] for i in range(len(cipher))]
    flag_content = bytes(flag[7:-26])
    hash = base64.b64encode(hashlib.md5(flag_content).digest())
    if hash == bytes(flag[-25:-1]):
        print(bytes(flag))

# TSGCTF{The_l0n63|2_+|-|3_fla6_the_saf3|2_i+_m4`/_8e_as_lo|\|g_4$_you_use_a|\|_a|*pr0|*ria+3_3|\|cry|*+i0n._Thi$_ci|*|-|3r_i$_4_0ne_+i|\/|e_|*a|)_ra+h3|2_t|-|4|\|_a_s+re4m_(iph3r,_but_it_i$_ins3(u|2e_be(ause_it_us3s_the_$4|\/|e_r4ndom_num83r$_re|*34+3|)ly._enjoy_hahaha_:-)-:)-:)@TWp6sQXidRLICfdhOMY+IA==}

[crypto] RANDOM SEED RANDOM

次のソースコードが与えられます。

import os
import random
import string

flag = os.getenv("FLAG", "FAKECTF{THIS_IS_FAKE}")

key = [random.randrange(10 ** 4) for _ in flag]
cs = string.printable[:-6]

def r(k):
    for _ in range(k):
        random.seed(x := random.randrange(20231104, 20231104 * 10))
    return x

random.seed(int(input("seed: ")))
print('flag:', ''.join([cs[(cs.index(f) + r(k)) % len(cs)] for f, k in zip(flag, key)]))

フラグの各文字について、

random.seed(x := random.randrange(20231104, 20231104 * 10))

を $10^{4}$ 未満のランダムな回数だけ繰り返し、得られた x の値だけ文字をずらす、という変換をした結果の文字列が得られます。seedの初期値を指定できます。

少ない回数で元の値に戻るような x (seed) を指定すれば、ずらす数としてありうるものの種類が少なくなるので、フラグの各文字の候補を絞り込むことができます。そのためまずは、元に戻るまでの回数 (周期) としてありうるものと、それを達成するseedの初期値を列挙します。

import random

N = 20231104

nxt = [-1] * (N * 10)

for x in range(N, N * 10):
    random.seed(x)
    y = random.randrange(N, N * 10)
    nxt[x] = y

cnt = [-2] * (N * 10)

for x in range(N, N * 10):
    if cnt[x]!=-2:
        continue
    cnt[x] = 0
    y = x
    c = 0
    while True:
        y = nxt[y]
        c += 1
        if cnt[y]!=-2:
            break
        cnt[y] = c

    if cnt[y]!=-1:
        l = c-cnt[y]
        print(l, y)

    cnt[x] = -1
    y = nxt[x]
    while cnt[y]>=0:
        cnt[y] = -1
        y = nxt[y]

これを実行すると次のようになり ("周期 seedの初期値"の形式)、6回で元の値に戻るようなseedが見つかります。

6848 28347911
3761 158482846
7282 110665403
42 40538547
182 37635707
111 79190593
12 169256700
6 92574978
6 151006513
15 152413113
...

seedが 92574978 (周期6), 151006513 (周期6), 169256700 (周期12) の場合の結果を用いると、フラグを絞り込めます (以下のスクリプトを実行すると3文字目が 4 となりますが、G に修正することで正しいフラグになります)。

import string
import random

N = 20231104
cs = string.printable[:-6]

def nxt(x):
    random.seed(x)
    return random.randrange(N, N * 10)

xs = [92574978, 169256700, 151006513]
kouhos = []
for x in xs:
    kouho = [x]
    y = nxt(x)
    while y!=x:
        kouho.append(y)
        y = nxt(y)
    kouhos.append(kouho)

encs = [",k84'7ee,R4Ic*(3SXSV#fdISq>nsl,Y$..kxW", "3i-=hXu=m{U+QwwT|3#lC&e4QqK<sq(GKN|M_U", "W[&Fb*K8S-_$I@V&d\j(ZQ79|*!&zW)3uJ$a;n"]
flag = ''
for i in range(len(encs[0])):
    for j in range(len(cs)):
        ok = True
        for k in range(3):
            if cs.index(encs[k][i]) not in [(j+t)%len(cs) for t in kouhos[k]]:
                ok = False
        if ok:
            flag += cs[j]
            break
print(flag)
# TSGCTF{D4NCE_R0BOT_D4NCE_8caa8d05ff7f}

[crypto] Learning with Exploitation

次のソースコードとその実行結果が与えられます。

from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
from sage.crypto.lwe import LWE, samples
from sage.misc.prandom import randrange

p = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
F = GF(p)
d = 100
n = 10
q = p // (2 ** 64)
D = DiscreteGaussianDistributionIntegerSampler(q // d // 6) # six sigma

lwe = LWE(n=n, q=p, D=D)

public_key = list(zip(*samples(m=d, n=n, lwe=lwe)))
private_key = lwe._LWE__s

def encrypt(m, public_key):
  A, T = public_key
  r = vector([F(randrange(2)) for _ in range(d)])
  U = r * matrix(A)
  v = r * vector(T) + m * q
  return U, v

def decrypt(c, private_key):
  U, v = c
  return int(v - U * private_key + q // 2) // q

with open('flag.txt', 'rb') as f:
  flag = f.read()
assert(len(flag) == 64)

print(f'{public_key = }')

ciphertext = []
for i in range(0, 64, 8):
  m = int.from_bytes(flag[i:i+8], 'big')
  c = encrypt(m, public_key)

  assert(decrypt(c, private_key) == m)

  ciphertext.append(c)

print(f'{ciphertext = }')

公開鍵は $100\times 10$ 行列 $A$ と長さ100のベクトル $T$ で、秘密鍵は長さ10のベクトル $s$ です。 $p$ は192bit素数で、鍵の成分は $\mathbb{F}_{p}$ の元です。また、この鍵を用いた暗号化と復号の関数が実装されており、公開鍵と、フラグを暗号化した結果が与えられます。

LWEが誤差付きの連立方程式を解く問題であったことを思い出しながら試すと、 $e=As-T$ の各成分が小さい値 (121bit程度) になっていることがわかります。よって、次のような行列

$\displaystyle{ \begin{pmatrix} ^{t}\!A & I_{10} & O \\ pI_{100} & O & O \\ -^{t}T & O & \infty \end{pmatrix} }$

に対してLLLアルゴリズムを適用すると、最後の行に秘密鍵 $s$ を含むベクトル

$\displaystyle{ (^{t}\!e, ^{t}\!s, \infty) }$

が現れることが期待できます。実際は、 $e$ の列に $2^{70}$ 倍程度の重みをつけて $s$ の列と大きさを合わせることで、欲しいベクトルが得られます。

秘密鍵が求まれば、与えられた復号関数を用いてフラグを復号できます。

from Crypto.Util.number import *
from output import *

A = public_key[0] # 100 x 10
T = public_key[1] # 100

p = 0xfffffffffffffffffffffffffffffffeffffffffffffffff
d = 100
n = 10
q = p // (2 ** 64)

inf = 2**256
weight = 2**75
mat = [[0]*(d+n+1) for _ in range(d+n+1)]

for i in range(n):
    for j in range(d):
        mat[i][j] = A[j][i]*weight
for i in range(d):
    mat[i+n][i] = p*weight
for i in range(d):
    mat[d+n][i] = -T[i]*weight
for i in range(n):
    mat[i][i+d] = 1
mat[d+n][d+n] = inf

res = Matrix(mat).LLL()
private_key = vector(GF(p), res[-1][-1-n:-1])

def decrypt(c, private_key):
  U, v = c
  return int(v - vector(U) * private_key + q // 2) // q

flag = b''
for i in range(len(ciphertext)):
    c = ciphertext[i]
    m = decrypt(c, private_key)
    flag += long_to_bytes(int(m))
print(flag)
# TSGCTF{PQC_5T4NDS_FOR_"P-AND-Q_CRYPTOSY5T3M";_4LSO_KNOWN_A5_RSA}

[crypto] Delta Force

次のソースコードとその実行結果が与えられます。楕円曲線のクラス EC が実装されている elliptic_curve.py も与えられます。

from secret import flag, p, q
from random import SystemRandom
from elliptic_curve import EC

randgen = SystemRandom()
flag += randgen.randbytes(4000 // 8 - len(flag))

f = int.from_bytes(flag, 'big')

assert is_prime(p) and is_prime(q)
N = p * q

R = IntegerModRing(N)
a1 = 3444824117 ...
a2 = 4220657222 ...
a3 = 5580533280 ...
a4 = 2409686375 ...
a6 = 3470078186 ...

x = 3187380289 ...
y = 3098509628 ...

P = (x, y)

ec = EC(R, (a1, a2, a3, a4, a6))
assert ec.iszeropoint(P) == True

print(N)
print(ec.scalar(f, P))

$\mathbb{Z}/n\mathbb{Z}$ 上の楕円曲線の離散対数問題(DLP)に見えます。 $N$ は4099bitで、2つの素数 $p, q$ の積です。

楕円曲線のクラスが独自実装されている点が怪しいです。SageMathで問題の楕円曲線を扱おうとすると、singular curveであるというエラーが出ます。

sage: E = EllipticCurve(Zmod(N), [a1, a2, a3, a4, a6])                                  
---------------------------------------------------------------------------
ArithmeticError                           Traceback (most recent call last)
<ipython-input-3-2518f5d34f0b> in <module>
----> 1 E = EllipticCurve(Zmod(N), [a1, a2, a3, a4, a6])
...
ArithmeticError: y^2 + 34448...*x*y + 55805...*y = x^3 + 42206...*x^2 + 24096...*x + 34700... defines a singular curve

実際、楕円曲線の判別式 $\Delta$ を計算すると0となっており、singularな曲線であることがわかります。

singularな楕円曲線には、nodeとcuspの2種類があります。楕円曲線の方程式を $y^{2}=x^{3}-27c_{4}x-54c_{6}$ の形に変形すると、cuspであるための条件は $c_{4}=0$ と書けます。ちょうどRicerca CTF 2023の賞品のタンブラーにこの条件が書かれていたのを思い出しました。

singularな楕円曲線におけるDLPの解き方は、nodeの場合とcuspの場合で異なります。cuspの場合は、 $(x, y)\mapsto x/y\in \mathbb{F}_{p}$ により加法群 $\mathbb{F}_{p}$ 上のDLPに帰着します。また、nodeの場合は、楕円曲線を $\mathbb{F}_{p^{2}}^{\times}$ に埋め込むことができることが知られており、 $\mathbb{F}_{p^{2}}^{\times}$ 上のDLPに帰着します。

今回、 $c_{4}$ を計算すると0でない値になりますが、 $\bmod{p}$ と $\bmod{q}$ のうち片方がcusp、もう片方がnodeになっているかもしれないと推測して $\gcd (c_{4}, N)$ を計算してみると、1より大きい値が現れます。これにより、 $N$ が素因数分解できて、推測通り $\bmod{p}$ でcusp、 $\bmod{q}$ でnodeとなっていることがわかります。

$\bmod{q}$ (nodeの場合) におけるDLPは、今回 $(q+1)P=O$ であり、 $q+1$ がちょうど $10^{9}$ 程度の素因数の積になっていることから、Pohlig-Hellmanのアルゴリズムで解くことができます。

from Crypto.Util.number import *
from elliptic_curve import EC

a1 = 3444824117 ...
a2 = 4220657222 ...
a3 = 5580533280 ...
a4 = 2409686375 ...
a6 = 3470078186 ...

x = 3187380289 ...
y = 3098509628 ...

# output
N = 4861176438 ...
Q = (2940137648 ... , 4309188751 ... )
xq, yq = Q[0], Q[1]

b2 = (a1**2+4*a2)%N
b4 = (2*a4+a1*a3)%N
b6 = (a3**2+4*a6)%N
b8 = (a1**2*a6+4*a2*a6-a1*a3*a4+a2*a3**2-a4**2)%N
c4 = (b2**2-24*b4)%N
c6 = (-b2**3+36*b2*b4-216*b6)%N
delta = (-b2**2*b8-8*b4**3-27*b6**2+9*b2*b4*b6)%N

p = GCD(c4, N)
q = N//p

def myon(x, y):
    y1 = (2*y+a1*x+a3)%N
    x1 = (36*x+3*b2)%N
    y1 = 108*y1%N
    assert (y1**2-(x1**3-27*c4*x1-54*c6))%N == 0
    return x1, y1
x1, y1 = myon(x, y)
x2, y2 = myon(xq, yq)

# mod p
v = x1*pow(int(y1),int(-1),int(p))%p
vq = x2*pow(int(y2),int(-1),int(p))%p
fp = vq*pow(int(v),int(-1),int(p))%p

# mod q
fac = [r[0] for r in factor(q+1)][1:]
rs = [int(fp)]
qs = [p] + fac

ec = EC(GF(q), (a1, a2, a3, a4, a6))

for r in fac:
    P1 = ec.scalar((q+1)//r, (x%q,y%q))
    Q1 = ec.scalar((q+1)//r, (xq%q,yq%q))
    
    # bsgs
    fr = -1
    sq = isqrt(r)
    R = ec.negate(ec.scalar(sq, P1))
    S = ec.O
    mp = dict()
    for i in range(0, sq):
        mp[S] = i
        S = ec.add(S, P1)
    S = Q1
    for i in range(0, r, sq):
        if S in mp:
            fr = i+mp[S]
            break
        S = ec.add(S, R)
    rs.append(int(fr))

m = CRT_list(rs, qs)
print(long_to_bytes(int(m)))
# TSGCTF{@l1_y0u_n3Ed_IS_ReaDiNG_5ilvErman_ThE_@r1thmetic_of_e11iPtiC_cURVe5}

first bloodでした。

[rev] beginners_rev_2023

64bitのexeファイル beginners-rev-2023.exe が与えられます。

Ghidraで解析します。メインの処理はFUN_140001880にあります。

void FUN_140001880(void)

{
  ulonglong *puVar1;
  int iVar2;
  undefined8 *puVar3;
  void *_Dst;
  ulonglong *puVar4;
  char *_Str;
  longlong lVar5;
  undefined8 uVar6;
  longlong lVar7;
  undefined8 uVar8;
  longlong lVar9;
  undefined8 in_R9;
  undefined auStack_258 [32];
  char local_238 [16];
  undefined local_228 [24];
  ulonglong local_210 [63];
  ulonglong local_18;
  
  local_18 = DAT_140004008 ^ (ulonglong)auStack_258;
  puVar3 = (undefined8 *)malloc(0x408);
  *puVar3 = 0;
  local_238 = s_2023TTSSGG2023!_140003270;
  lVar7 = -1;
  do {
    lVar5 = lVar7 + 1;
    lVar9 = lVar7 + 1;
    lVar7 = lVar5;
  } while (local_238[lVar9] != '\0');
  FUN_140001480(puVar3,(int)lVar5,(longlong)local_238);
  _Dst = malloc(0x201);
  uVar6 = 0;
  uVar8 = 0x201;
  memset(_Dst,0,0x201);
  FUN_140001020("Flag> ",uVar6,uVar8,in_R9);
  FUN_140001080(&DAT_140003288,_Dst,0x201,in_R9);
  memset(local_228,0,0x201);
  lVar7 = 2;
  lVar9 = 2;
  puVar4 = (ulonglong *)((longlong)_Dst + 0x18);
  do {
    puVar4[-3] = puVar4[-3] ^ puVar4[-3] >> 0xc;
    // 中略
    puVar4[0x1c] = puVar4[0x1c] >> 0xc ^ puVar4[0x1c];
    lVar9 = lVar9 + -1;
    puVar4 = puVar1;
  } while (lVar9 != 0);
  FUN_1400010e0((uint *)puVar3,puVar1,(longlong)_Dst,(longlong)local_228);
  puVar4 = local_210;
  do {
    puVar4[-3] = puVar4[-3] ^ puVar4[-3] >> 0xc;
    // 中略
    puVar4[0x1c] = puVar4[0x1c] >> 0xc ^ puVar4[0x1c];
    lVar7 = lVar7 + -1;
    puVar4 = puVar4 + 0x20;
  } while (lVar7 != 0);
  iVar2 = memcmp(local_228,&DAT_140004040,0x200);
  _Str = "Correct!!!";
  if (iVar2 != 0) {
    _Str = "Wrong...";
  }
  puts(_Str);
  FUN_140001de0(local_18 ^ (ulonglong)auStack_258);
  return;
}

暗号化処理はFUN_1400010e0にあります。

void FUN_1400010e0(uint *param_1,undefined8 param_2,longlong param_3,longlong param_4)

{
  uint uVar1;
  uint uVar2;
  uint uVar3;
  ulonglong uVar4;
  byte *pbVar5;
  longlong lVar6;
  ulonglong uVar7;
  uint uVar8;
  byte *pbVar9;
  
  uVar4 = (ulonglong)*param_1;
  uVar7 = (ulonglong)param_1[1];
  lVar6 = 0x20;
  pbVar5 = (byte *)(param_4 + 2);
  pbVar9 = (byte *)(param_3 + 2);
  do {
    uVar3 = (int)uVar4 + 1U & 0xff;
    uVar1 = param_1[(ulonglong)uVar3 + 2];
    uVar8 = uVar1 + (int)uVar7 & 0xff;
    uVar2 = param_1[(ulonglong)uVar8 + 2];
    param_1[(ulonglong)uVar3 + 2] = uVar2;
    param_1[(ulonglong)uVar8 + 2] = uVar1;
    pbVar9[(param_4 - param_3) + -2] =
         *(byte *)(param_1 + (ulonglong)(uVar2 + uVar1 & 0xff) + 2) ^ pbVar9[-2];
    uVar3 = uVar3 + 1 & 0xff;
    uVar1 = param_1[(ulonglong)uVar3 + 2];
    uVar8 = uVar8 + uVar1 & 0xff;
    uVar2 = param_1[(ulonglong)uVar8 + 2];
    param_1[(ulonglong)uVar3 + 2] = uVar2;
    param_1[(ulonglong)uVar8 + 2] = uVar1;
    pbVar5[-1] = *(byte *)(param_1 + (ulonglong)(uVar2 + uVar1 & 0xff) + 2) ^ pbVar9[-1];
    // 中略
    uVar3 = uVar3 + 1 & 0xff;
    uVar1 = param_1[(ulonglong)uVar3 + 2];
    uVar8 = uVar8 + uVar1 & 0xff;
    uVar2 = param_1[(ulonglong)uVar8 + 2];
    param_1[(ulonglong)uVar3 + 2] = uVar2;
    param_1[(ulonglong)uVar8 + 2] = uVar1;
    pbVar5[0xc] = *(byte *)(param_1 + (ulonglong)(uVar2 + uVar1 & 0xff) + 2) ^ pbVar9[0xc];
    uVar3 = uVar3 + 1 & 0xff;
    uVar4 = (ulonglong)uVar3;
    uVar1 = param_1[uVar4 + 2];
    uVar8 = uVar8 + uVar1 & 0xff;
    uVar7 = (ulonglong)uVar8;
    uVar2 = param_1[uVar7 + 2];
    param_1[uVar4 + 2] = uVar2;
    param_1[uVar7 + 2] = uVar1;
    pbVar5[0xd] = *(byte *)(param_1 + (ulonglong)(uVar2 + uVar1 & 0xff) + 2) ^ pbVar9[0xd];
    lVar6 = lVar6 + -1;
    pbVar5 = pbVar5 + 0x10;
    pbVar9 = pbVar9 + 0x10;
  } while (lVar6 != 0);
  param_1[1] = uVar8;
  *param_1 = uVar3;
  return;
}

RC4に似た暗号化処理が行われており、

pbVar5[0xd] = *(byte *)(param_1 + (ulonglong)(uVar2 + uVar1 & 0xff) + 2) ^ pbVar9[0xd];

の部分を見ると、少なくともストリーム暗号であることがわかります。

行われている処理をまとめると次のようになります。

固定の鍵 2023TTSSGG2023! から、ストリーム暗号のkeystream生成に用いる初期状態512bytesを作る (FUN_140001480)
512bytesの平文 (フラグ) を入力する (FUN_140001080)
平文を8bytesごとに x = x ^ (x >> 12) と変換する
RC4に似たストリーム暗号で暗号化する (FUN_1400010e0)
暗号文を8bytesごとに x = x ^ (x >> 12) と変換する
ハードコードされた暗号文と比較する

鍵が固定であることから、keystreamは固定なので、暗号化処理を正確にreversingしなくても、適当に入力して暗号化前後の文字列を取得し、それらをXORしてkeystreamを求めれば復号できます。暗号化前後の文字列は、x64dbgを用いて 0x140001b59 (call FUN_1400010e0) にブレークポイントを張り、r8, r9レジスタのアドレスを読むことで得られます。

また、x = x ^ (x >> 12) の逆変換は次のようにできます。

x = x ^ (x >> 12) ^ (x >> 24) ^ (x >> 36) ^ (x >> 48) ^ (x >> 60)

from Crypto.Util.number import *

with open('beginners-rev-2023.exe', 'rb') as f:
    f.seek(0x3040)
    enc_flag = f.read(0x200)

kasu_plain = '''77 77 77 77 77 77 67 61 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00'''

kasu_enc = '''5D DB A4 08 84 86 8D D2 FE 97 54 DB D7 AE 0C E2
DF 66 72 6D 62 AF E5 B9 99 31 DA 81 3D DE D9 FD
0F B5 55 93 C9 A0 09 CD 2D 30 8A D0 9C C1 C6 F2
09 27 38 4C A4 56 99 BC 75 07 7A EC 74 85 AD 1A
1C 86 6F D8 61 12 C5 75 48 D1 CB B1 87 9C 1F 0A
8B 01 B4 E2 8B 28 98 FA C7 91 67 35 59 81 23 31
DE D6 87 78 66 AD 45 53 AD 1B 2E D7 04 D3 BB 87
88 D4 32 A4 AA 55 5B A7 0E 05 8A A0 B8 E0 5A 3D
B0 8A 1B 79 B0 2E 15 86 A2 77 90 A1 59 CB 61 08
F3 AF C9 B6 4D 61 1A 93 32 0A 81 5E E4 E4 B2 0B
E4 63 34 C5 1F E9 38 FD 48 A2 29 2B 18 07 FE D3
7B E4 1A 26 84 BF F5 17 11 FE 95 40 9A 73 24 B3
6C C4 34 80 8D 31 FD A9 4F 4B C8 B6 4D 3C 6B FF
B7 44 7F FD 3F 1C 92 BF 74 58 33 E1 4A 46 90 94
90 74 5C F9 03 22 70 8A 86 01 F8 5F E6 41 5D 83
34 6D 88 1E 16 08 4D 62 57 86 9D 03 4E 65 38 31
08 62 55 5E 73 6D C4 52 F5 9E E9 24 9E 45 55 82
C4 DE ED B6 87 1E 99 2F AF 87 89 0D 84 7C C7 45
FD 61 63 22 EC 5E B9 FB 97 3E B4 F6 76 33 84 FA
15 D6 32 00 58 8B 4B 6C 9A 50 CD 1D FC 05 B4 78
96 E3 7D A0 EF B2 1D 01 AC F8 0F E6 C7 81 E4 7A
52 9D 43 82 45 B3 73 C8 C2 6D 10 B0 5B 6F E1 EE
C7 45 C0 B9 A1 AA 9F FC 57 3B 36 72 EB AC 43 BB
AC 0E AD 62 4F 43 66 D7 1C 5E DE B8 30 29 DD 50
72 3F 38 DD BE 73 69 F2 B7 0E 64 42 F4 73 40 03
9D C8 28 F8 D6 25 16 35 C5 5F F1 4A 61 50 56 FE
F8 49 C0 D0 A5 4E 10 A7 14 C5 4B E9 CA B8 E3 DE
DB 76 22 5B EA 0A 31 07 BF 52 DB A6 E9 88 13 4D
93 1D 99 3F DC 61 DE CD 00 08 48 2B 26 66 9D A1
E2 28 17 67 A1 4E D8 00 48 2D 5A 5F D1 FB 09 FD
12 CD B6 FD F1 56 B3 6A C4 6F 94 C6 A8 2C BA 29
37 8F 8B 80 5E BE 77 D0 48 6E E2 E5 7D A1 38 86'''

def inv(x):
    return x^(x>>12)^(x>>24)^(x>>36)^(x>>48)^(x>>60)

tmp = []
for i in range(0, 0x200, 8):
    tmp.append(inv(bytes_to_long(enc_flag[i:i+8][::-1])))
enc_flag = tmp

tmp = []
for line in kasu_plain.split('\n'):
    vs = line.split()[:16]
    v1 = bytes_to_long(bytes.fromhex(''.join(vs[:8][::-1])))
    tmp.append(v1)
    v2 = bytes_to_long(bytes.fromhex(''.join(vs[8:][::-1])))
    tmp.append(v2)
kasu_plain = tmp

tmp = []
for line in kasu_enc.split('\n'):
    vs = line.split()[:16]
    v1 = bytes_to_long(bytes.fromhex(''.join(vs[:8][::-1])))
    tmp.append(v1)
    v2 = bytes_to_long(bytes.fromhex(''.join(vs[8:][::-1])))
    tmp.append(v2)
kasu_enc = tmp

keystream = [x^y for x, y in zip(kasu_enc, kasu_plain)]
flag = [inv(x^y) for x, y in zip(enc_flag, keystream)]
print(b''.join(long_to_bytes(x)[::-1] for x in flag))
# TSGCTF{y0u_w0uld_und3r57and_h0w_70_d3cryp7_arc4_and_h0w_70_d3cryp7_7h3_l3ak3d_5af3_l1nk1ng_p01n73r}

[misc] Secret Sequence

次のソースコードとその実行結果が与えられます。

import numpy as np
import secrets
import base64
def block_to_words(block):
    # block 128bit byteString
    # words 32 * 4bit int np.array
    # little endian
    divided_blocks = np.array([block[4*i:4*(i+1)] for i in range(4)])
    f = np.frompyfunc(int.from_bytes, 2, 1)
    words = f(divided_blocks,'little')
    return words

def words_to_block(words):
    # words 32 * 4bit int np.array
    # block 128bit byteString
    # little endian
    block = b''.join([i.to_bytes(4,'little') for i in words])
    return block

def rotate_left(x, n):
    # x 32bit int
    # n int
    # rotated 32bit int
    rotated = ((x << n) & 0xffffffff) | (x >> (32 - n))
    return rotated

def rotate_right(x, n):
    # x 32bit int
    # n int
    # rotated 32bit int
    rotated = (x >> n) | ((x << (32 - n)) & 0xffffffff)
    return rotated

primitive_polynomial_g = 0b01101001

def xtime(a):
    # a: 8bit
    # b: 8bit
    if a & 0b10000000 == 0b10000000:
        a = ((a << 1) ^ primitive_polynomial_g) & 0b11111111
    else:
        a <<= 1
    return a

def gmul(a, b):
    # a: 8bit
    # b: 8bit
    # c: 8bit
    c = 0
    for i in range(8):
        if b & 1 == 1:
            c ^= a
        a = xtime(a)
        b >>= 1
    return c

MDS = np.array([
    [0x01, 0xEF, 0x5B, 0x5B],
    [0x5B, 0xEF, 0xEF, 0x01],
    [0xEF, 0x5B, 0x01, 0xEF],
    [0xEF, 0x01, 0xEF, 0x5B]
],dtype='object')

def q0(x):
    # x 8bit int
    # y 8bit int
    t = np.array([
        [0x8,0x1,0x7,0xd,0x6,0xf,0x3,0x2,0x0,0xb,0x5,0x9,0xe,0xc,0xa,0x4],
        [0xe,0xc,0xb,0x8,0x1,0x2,0x3,0x5,0xf,0x4,0xa,0x6,0x7,0x0,0x9,0xd],
        [0xb,0xa,0x5,0xe,0x6,0xd,0x9,0x0,0xc,0x8,0xf,0x3,0x2,0x4,0x7,0x1],
        [0xd,0x7,0xf,0x4,0x1,0x2,0x6,0xe,0x9,0xb,0x3,0x0,0x8,0x5,0xc,0xa]
    ],dtype='object')
    a = np.zeros(5,dtype='object')
    b = np.zeros(5,dtype='object')
    a[0] = (x>>4)%16
    b[0] = x%16
    a[1] = a[0] ^ b[0]
    b[1] = a[0] ^ (((b[0]<<3)&(0b1000)) | b[0]>>1) ^ ((8*a[0])%16)
    a[2] = t[0][a[1]]
    b[2] = t[1][b[1]]
    a[3] = a[2] ^ b[2]
    b[3] = a[2] ^ (((b[2]<<3)&(0b1000)) | b[2]>>1) ^ ((8*a[2])%16)
    a[4] = t[2][a[3]]
    b[4] = t[3][b[3]]
    y = 16*b[4] + a[4]
    return y

def q1(x):
    # x 8bit int
    # y 8bit int
    t = np.array([
        [0x2,0x8,0xb,0xd,0xf,0x7,0x6,0xe,0x3,0x1,0x9,0x4,0x0,0xa,0xc,0x5],
        [0x1,0xe,0x2,0xb,0x4,0xc,0x3,0x7,0x6,0xd,0xa,0x5,0xf,0x9,0x0,0x8],
        [0x4,0xc,0x7,0x5,0x1,0x6,0x9,0xa,0x0,0xe,0xd,0x8,0x2,0xb,0x3,0xf],
        [0xb,0x9,0x5,0x1,0xc,0x3,0xd,0xe,0x6,0x4,0x7,0xf,0x2,0x0,0x8,0xa]
    ],dtype='object')
    a = np.zeros(5,dtype='object')
    b = np.zeros(5,dtype='object')
    a[0] = (x>>4)%16
    b[0] = x%16
    a[1] = a[0] ^ b[0]
    b[1] = a[0] ^ (((b[0]<<3)&(0b1000)) | b[0]>>1) ^ ((8*a[0])%16)
    a[2] = t[0][a[1]]
    b[2] = t[1][b[1]]
    a[3] = a[2] ^ b[2]
    b[3] = a[2] ^ (((b[2]<<3)&(0b1000)) | b[2]>>1) ^ ((8*a[2])%16)
    a[4] = t[2][a[3]]
    b[4] = t[3][b[3]]
    y = 16*b[4] + a[4]
    return y

def h_func(X,L):
    # X 32bit int
    # L 32 * k bit int np.array
    # Y 32bit int
    k=2
    x = np.array([X>>(8*i) &0xff for i in range(4)])
    l = np.zeros((k,4),dtype='object')
    for i in range(k):
        l[i] = np.array([L[i]>>(8*j) &0xff for j in range(4)])
    y = np.zeros((k+1,4) ,dtype='object')
    y[k] = [i for i in x]
    y[0][0] = q1(q0(q0(y[k][0]) ^ l[1][0]) ^ l[0][0])
    y[0][1] = q0(q0(q1(y[k][1]) ^ l[1][1]) ^ l[0][1])
    y[0][2] = q1(q1(q0(y[k][2]) ^ l[1][2]) ^ l[0][2])
    y[0][3] = q0(q1(q1(y[k][3]) ^ l[1][3]) ^ l[0][3])
    z = [0]*4
    for i in range(4):
        for j in range(4):
            z[i] ^= gmul(MDS[i][j],y[0][j])
    Z = 0
    for i in range(4):
        Z += (z[i] << (8*i))
    return Z

def xtime_k(a):
    # a: 8bit
    # b: 8bit
    primitive_polynomial_k = 0b01001101
    if a & 0b10000000 == 0b10000000:
        a = ((a << 1) ^ primitive_polynomial_k) & 0b11111111
    else:
        a <<= 1
    return a

def gmul_k(a, b):
    # a: 8bit
    # b: 8bit
    # c: 8bit
    c = 0
    for i in range(8):
        if b & 1 == 1:
            c ^= a
        a = xtime_k(a)
        b >>= 1
    return c

def key_schedule(key):
    # key 128bit byteSrting
    # Me 32 * 2 bit byteString np.array
    # Mo 32 * 2 bit byteString np.array
    # S 32 * 2 bit byteString np.array
    # keys byteString np.array
    # [key,Me[0],Me[1],Mo[0],Mo[1],S[0],S[1]]
    keys = np.full(7,b"")
    keys[0] = key
    RS = np.array([
        [0x01,0xA4,0x55,0x87,0x5A,0x58,0xDB,0x9E],
        [0xA4,0x56,0x82,0xF3,0x1E,0xC6,0x68,0xE5],
        [0x02,0xA1,0xFC,0xC1,0x47,0xAE,0x3D,0x19],
        [0xA4,0x55,0x87,0x5A,0x58,0xDB,0x9E,0x03]
    ],dtype='object')
    m = np.array([keys[0][4*i:4*(i+1)] for i in range(4)])
    keys[1] = m[0]
    keys[2] = m[2]
    keys[3] = m[1]
    keys[4] = m[3]
    S = np.zeros(2,dtype='object') 
    m2 = np.array([(int.from_bytes(keys[0],'big')>>(8*(15-i))) & 0xff for i in range(16)])
    for i in range(2):
        s = [0]*4
        for j in range(4):
            for k in range(8):
                s[j] ^= gmul_k(RS[j][k],m2[8*i+k])
        for j in range(4):
            S[i] += (s[j] << (8*j))
        keys[6-i] = S[i].to_bytes(4,'little')
    Me = np.full(2,b"")
    Mo = np.full(2,b"")
    S = np.full(2,b"")
    Me[0] = keys[1]
    Me[1] = keys[2]
    Mo[0] = keys[3]
    Mo[1] = keys[4]
    S[0] = keys[5]
    S[1] = keys[6]
    return Me,Mo,S
            
def sbox_with_key(X,i,S):
    # X 8bit int
    # i int 0-3
    # S 32 * 2 bit int
    # Y 8bit int
    k=2
    l = np.zeros((2,4),dtype='object')
    for m in range(k):
        l[m] = [S[m]>>(8*j) &0xff for j in range(4)]
    y = np.zeros((k+1,4) ,dtype='object')
    y[k][i] = X
    if i == 0:
        y[0][0] = q1(q0(q0(y[k][0]) ^ l[1][0]) ^ l[0][0])
    elif i == 1:
        y[0][1] = q0(q0(q1(y[k][1]) ^ l[1][1]) ^ l[0][1])
    elif i == 2:
        y[0][2] = q1(q1(q0(y[k][2]) ^ l[1][2]) ^ l[0][2])
    elif i == 3:
        y[0][3] = q0(q1(q1(y[k][3]) ^ l[1][3]) ^ l[0][3])
    return y[0][i]

def expand_key(Mo,Me):
    # key 128bit byteString
    # keys 32 * 40 bit int
    # little endian
    Mo_int = np.frompyfunc(int.from_bytes, 2, 1)(Mo,'little')
    Me_int = np.frompyfunc(int.from_bytes, 2, 1)(Me,'little')
    keys = []
    rho = 2**24 + 2**16 + 2**8 + 2**0
    A = np.zeros(20,dtype='object')
    B = np.zeros(20,dtype='object')
    for i in range(20):
        A[i]=h_func(2*i*rho,Me_int)
        B[i]=rotate_left(h_func((2*i+1)*rho,Mo_int),8)
    keys = np.zeros(40,dtype='object')
    for i in range(20):
        keys[2*i] = (A[i] + B[i])%(2**32)
        keys[2*i+1] = rotate_left((A[i] + 2*B[i])%(2**32),9)
    return keys

def g_func(X,S):
    # X 32bit int
    # S 32 * 2 bit int
    # Z 32bit int
    x = [X>>(8*i) &0xff for i in range(4)]
    y = [sbox_with_key(x[i],i,S) for i in range(4)]
    z = np.zeros(4,dtype='object')
    for i in range(4):
        for j in range(4):
            z[i] ^= gmul(MDS[i][j],y[j])
    Z = 0
    for i in range(4):
        Z += (z[i] << (8*i))
    return Z
    
def f_func(r0,r1,keys,rounds,S):
    # r0 32bit int
    # r1 32bit int
    # keys 32 * n bit int
    # rounds int 0-15
    # f0 32bit int
    # f1 32bit int
    t0 = g_func(r0,S)
    t1 = g_func(rotate_left(r1,8),S)
    f0 = (t0+t1+keys[2*rounds+8]) % 2**32
    f1 = (t0+2*t1+keys[2*rounds+9]) % 2**32
    return f0,f1

def one_round(words,rounds,keys,S):
    # words 32 * 4bit int
    # rounds int 0-15
    # exchanged_words 32 * 4bit int
    S_int = np.frompyfunc(int.from_bytes, 2, 1)(S,'little')
    f0,f1 = f_func(words[0],words[1],keys,rounds,S_int)
    exchanged_words = [0]*4
    exchanged_words[2] = words[0]
    exchanged_words[3] = words[1]
    exchanged_words[0] = rotate_right(words[2] ^ f0,1)
    exchanged_words[1] = rotate_left(words[3],1) ^ f1
    return exchanged_words

def input_whitening(words,keys):
    # words 32 * 4bit int
    # keys 32 * 4bit int
    # whitened_words 32 * 4bit int
    whitened_words = [0]*4
    for i in range(4):
        whitened_words[i] = words[i] ^ keys[i]
    return whitened_words

def output_whitening(words,keys):
    # words 32 * 4bit int
    # keys 32 * 4bit int
    # whitened_words 32 * 4bit int
    whitened_words = [0]*4
    for i in range(4):
        whitened_words[i] = words[(i+2)%4] ^ keys[i]
    return whitened_words

def twofish_encrypt(block,key):
    # block 128bit byteString
    # key 128bit byteString
    # encrypted_block 128bit byteString
    words = block_to_words(block)
    Me,Mo,S = key_schedule(key)
    keys = expand_key(Mo,Me)
    whitened_words = input_whitening(words,keys[0:4])
    for i in range(16):
        whitened_words = one_round(whitened_words,i,keys,S)
    encrypted_words = output_whitening(whitened_words,keys[4:8])
    encrypted_block = words_to_block(encrypted_words)
    return encrypted_block

def main(flag):
    pad_flag = flag+b'\x00'*(16-len(flag)%16)
    block_length = len(pad_flag)//16
    nonce = int.from_bytes(secrets.token_bytes(12),'big')
    assert block_length <= 2**32
    counter = [int.to_bytes((nonce<<32) + i,16,'big') for i in range(0,block_length)]
    key = secrets.token_bytes(16)
    encrypted_counter = [twofish_encrypt(i,key) for i in counter]
    encrypted_flags = [int.from_bytes(encrypted_counter[i],'big') ^ (int.from_bytes(pad_flag,'big')>>(16*8)*(block_length-1-i))&0xffffffffffffffffffffffffffffffff for i in range(0,block_length)]
    print("nonce = ", nonce)
    print("encrypted_flags = ", encrypted_flags)

if __name__ == '__main__':    
    flag = b"TSGCTF{__REDUCTED__}"
    main(flag)

問題文は次のようになっています。

Flagを暗号化するために、鍵が128bitの場合のtwofishという暗号を自分で実装してみたよ。NumPyを使うのは初めてだったけど、とても便利だね!

ところで、公式サイトの Test Vectors に載ってる Known Answer Test と暗号化の結果が一致しないけどどうしてだろう。

twofishというブロック暗号が実装されていますが、実装に間違いがあるようです。フラグはCTRモードで暗号化されています。

nonceを固定し、keyを変えたときの暗号文の変化を観察してみると、不思議なことに、keyの2文字目以降を変更しても暗号文が変わらないことが推測できます。

def main(flag, key):
    pad_flag = flag+b'\x00'*(16-len(flag)%16)
    block_length = len(pad_flag)//16
    # nonce = int.from_bytes(secrets.token_bytes(12),'big')
    nonce = 18639088674531619804203553158
    assert block_length <= 2**32
    counter = [int.to_bytes((nonce<<32) + i,16,'big') for i in range(0,block_length)]
    # key = secrets.token_bytes(16)
    encrypted_counter = [twofish_encrypt(i,key) for i in counter]
    encrypted_flags = [int.from_bytes(encrypted_counter[i],'big') ^ (int.from_bytes(pad_flag,'big')>>(16*8)*(block_length-1-i))&0xffffffffffffffffffffffffffffffff for i in range(0,block_length)]
    # print("nonce = ", nonce)
    print("encrypted_flags = ", encrypted_flags)

if __name__ == '__main__':    
    flag = b"TSGCTF{__REDUCTED__}"
    main(flag, b'a' + b'a'*15)
    main(flag, b'a' + b'b'*15)

python3 encrypt.py
encrypted_flags =  [290626269617722010694582424448868702133, 188985550652166884715879952474676365533]
encrypted_flags =  [290626269617722010694582424448868702133, 188985550652166884715879952474676365533]

よって、keyの2文字目以降は好きに固定し、1文字目のみ全ての文字を試せばよいです。CTRモードなので、encrypted_counter をXORすることで復号できます。

from Crypto.Util.number import *

nonce = 18639088674531619804203553158
encrypted_flags = [136566763988814260123977728391695169870, 297854733988125490212154919002758942167, 140286143861115781298750245081274386093, 267780198301748450281498233524628586631, 67891782595602432915140903440966332185, 27833795440965705923198634284529559150, 75239374091619069386173206358307312436, 155895086707931827255209248461881439022, 168571968627802622229088996983467487220, 258118042758062906462047523793633475289]

def decrypt(k):
    block_length = len(encrypted_flags)
    counter = [int.to_bytes((nonce<<32) + i,16,'big') for i in range(0,block_length)]
    key = bytes([k]) + b'a'*15
    encrypted_counter = [twofish_encrypt(i,key) for i in counter]
    
    ans = b''
    for i in range(len(encrypted_flags)):
        v = bytes_to_long(encrypted_counter[i]) ^ encrypted_flags[i]
        ans += long_to_bytes(v)
    if b'TSGCTF' in ans:
        print(ans)
        
for k in range(256):
    decrypt(k)
# TSGCTF{P3ople_li|<e_w4$+3,_I_|<|\|o\/\/._If_I_wa$_g0i|\|g_t0_ac+u4lly_use_i+,_I_shoul|)_not_h4ve_i|\/|ple|\/|e|\|ted_+|-|3_(i|*he|2_0|\|_|\/|`/_own.}