この大会は2023/11/4 16:00(JST)～2023/11/5 16:00(JST)に開催されました。
今回もチームで参戦。結果は552点で560チーム中51位でした。
自分で解けた問題をWriteupとして書いておきます。
Sanity Check (Warmup)
Discordに入り、#readmeチャネルのメッセージを見ると、フラグが書いてあった。
TSGCTF{G3n3r@t1v3_@I_4lways_c0mes_up_w1th_b3tt3r_punchl1n3s_th@n_m3!}
Complicated Function (Crypto)
pの最小値は2**1023、最大値は2**1024。pの範囲の中央値を取りながら、qを算出し、p*qの値からNに近づくよう範囲を狭めていく。p, qの値がわかったら、通常通り復号すればよい。
#!/usr/bin/env python3 from math import isqrt, sin, ceil def q_from_p(p): return isqrt(p**2 + p * (2**512 - 6) + ceil(isqrt(p) * sin(p))) + 2**1023 with open('output.txt', 'r') as f: params = f.read().splitlines() N = int(params[0].split(' ')[-1]) c = int(params[1].split(' ')[-1]) e = 0x10001 p_min = 2**1023 p_max = 2**1024 while True: p = (p_min + p_max) // 2 q = q_from_p(p) diff = N - p * q if diff == 0: break elif diff > 0: p_min = p else: p_max = p assert p * q == N phi = (p - 1) * (q - 1) d = pow(e, -1, phi) m = pow(c, d, N) flag = m.to_bytes((m.bit_length() - 1) // 8 + 1, 'big').decode() print(flag)
TSGCTF{From which angle did you solve this, binary search or convergence of f(p)-p?}
Unique Flag (Crypto)
暗号処理の概要は以下の通り。
・p, q: 1024ビット素数
・N = p * q
・e = 0x10001
・flagの長さは33バイト
・flag_header: flagの先頭7バイト(='TSGCTF{')
・flag_content: flagの先頭7バイト以降末尾1バイト以前の文字列
・flag_footer: flagの末尾1バイト(='}')
・flag_contentは同じ文字は使われていない。
・c_list: flagの各文字のASCIIコード(byte)について、pow(byte, e, N)の配列
・clues: c_listの末尾を除く配列の各値(x)と、先頭を除く配列の各値(y)でx * y % Nの配列
・cluesをソートする。
・N, e, cluesを出力1文字ずつ、前の文字との組み合わせで条件を満たすものを探していく。
#!/usr/bin/env python3 with open('output.txt', 'r') as f: params = f.read().splitlines() N = int(params[0].split(' = ')[1]) e = int(params[1].split(' = ')[1]) clues = eval(params[2].split(' = ')[1]) chars = [bytes([c]) for c in range(32, 127)] chars.remove(b'{') chars.remove(b'}') flag_header = b'TSGCTF{' for i in range(len(flag_header) - 1): x = pow(flag_header[i], e, N) y = pow(flag_header[i + 1], e, N) c = x * y % N assert c in clues clues.remove(c) flag_contents = [b'{'] for i in range(len(flag_header), 33): tmp_flag_contents = [] for content in flag_contents: x = pow(content[-1], e, N) for code in range(33, 127): if bytes([code]) in content: continue y = pow(code, e, N) c = x * y % N if c in clues: tmp_flag_contents.append(content + bytes([code])) flag_contents = tmp_flag_contents for flag_content in flag_contents: flag = (flag_header + flag_content[1:]).decode() print(flag)
TSGCTF{OK,IsTHi5A_un1qUe-flag?XD}
Streamer (Crypto)
鍵は16バイトで、flagとXORしている。
flagは以下のような構成。
TSGCTF{XXXX...XXXX@<16バイトのbase64文字列>}
→TSGCTF{XXXX...XXXX@YYYYYYYYYYYYYYYYYYYYYY==}ブロック構成は以下のようなイメージ。
0123456789abcdef
TSGCTF{XXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
:
XXXXXXXXXXXXXXXX
XXXXXX@YYYYYYYYY
YYYYYYYYYYYYY==}これからわかる範囲で、XOR鍵を算出し、復号する。
0123456789abcdef
TSGCTF{******n63 0
|2_+|-|******_th 1
e_saf3|******4`/ 2
_8e_as_******_4$ 3
_you_us******_a| 4
*pr0|*r******|\\| 5
cry|*+i******i$_ 6
ci|*|-|******4_0 7
ne_+i|\\******a|) 8
_ra+h3|******4|\\ 9
|_a_s+r******ph3 10
r,_but_******ins 11
3(u|2e_******e_i 12
t_us3s_******|\\/ 13
|e_r4nd******83r 14
$_re|*3******y._ 15
enjoy_h******:-) 16
-:)-:)@******Xid 17
RLICfdh******==} 1810ブロック目の10-12バイト目は"_ci"またはそのリート文字であると推測し、復号する。さらに16ブロック目の7-9バイト目は"aha"またはそのリート文字であると推測し、復号する。
#!/usr/bin/env python3 from output import * import hashlib import base64 flag_header = b'TSGCTF{' flag_footer = b'==}' key = [-1] * 16 for i in range(len(flag_header)): key[i] = flag_header[i] ^ cipher[i] for i in range(len(flag_footer)): key[i+13] = flag_footer[i] ^ cipher[flag_length - 3 + i] flag = b'' for i in range(len(cipher)): if key[i % 16] != -1: flag += bytes([cipher[i] ^ key[i % 16]]) else: flag += b'*' print('[+] flag:', flag) ## guess1 ## key[10] = ord('_') ^ cipher[16 * 10 + 10] key[11] = ord('(') ^ cipher[16 * 10 + 11] key[12] = ord('i') ^ cipher[16 * 10 + 12] flag = b'' for i in range(len(cipher)): if key[i % 16] != -1: flag += bytes([cipher[i] ^ key[i % 16]]) else: flag += b'*' print('[+] flag:', flag) ## guess2 ## key[7] = ord('a') ^ cipher[16 * 16 + 7] key[8] = ord('h') ^ cipher[16 * 16 + 8] key[9] = ord('a') ^ cipher[16 * 16 + 9] flag = b'' for i in range(len(cipher)): if key[i % 16] != -1: flag += bytes([cipher[i] ^ key[i % 16]]) else: flag += b'*' flag_content = flag[7:-26] flag_hash = hashlib.md5(flag_content).digest() assert base64.b64encode(flag_hash) == flag[-25:-1] print('[*] flag:', flag)
復号結果は以下の通り。
[+] flag: b'TSGCTF{******n63|2_+|-|******_the_saf3|******4`/_8e_as_******_4$_you_us******_a|*pr0|*r******|\\|cry|*+i******i$_ci|*|-|******4_0ne_+i|\\******a|)_ra+h3|******4|\\|_a_s+r******ph3r,_but_******ins3(u|2e_******e_it_us3s_******|\\/|e_r4nd******83r$_re|*3******y._enjoy_h******:-)-:)-:)@******XidRLICfdh******==}'
[+] flag: b'TSGCTF{***_l0n63|2_+|-|***la6_the_saf3|***+_m4`/_8e_as_***\\|g_4$_you_us***|\\|_a|*pr0|*r***3_3|\\|cry|*+i***_Thi$_ci|*|-|***i$_4_0ne_+i|\\***_|*a|)_ra+h3|***|-|4|\\|_a_s+r***_(iph3r,_but_***i$_ins3(u|2e_***ause_it_us3s_***_$4|\\/|e_r4nd***num83r$_re|*3***|)ly._enjoy_h***ha_:-)-:)-:)@***6sQXidRLICfdh***+IA==}'
[*] flag: b'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==}'\\のエスケープを解除する。
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==}
Survey (Cooldown)
アンケートに答えたら、フラグが表示された。
TSGCTF{Thank_you_for_your_participation!}
