この大会は2022/7/10 1:00(JST)～2022/7/11 1:00(JST)に開催されました。
今回もチームで参戦。結果は2372点で635チーム中60位でした。
自分で解けた問題をWriteupとして書いておきます。
Sanity Check (Web)
HTMLソースのコメントにフラグが書いてあった。
vsctf{v1ew_s0urc3_a_f1rst_y3ar_t3am!}
Discord (Miscellaneous)
Discordに入り、#announcementsチャネルのメッセージを見ると、フラグが書いてあった。
vsctf{w3lc0m3_t0_vsctf_2022!}
Recovery (Cryptography)
スクリプトの処理概要は以下の通り。
・validate(passwd)がTrueの場合、パスワードがフラグとなる。
・passwdの長さは49バイトでない場合、Falseを返す。
・key: passwdの末尾から1バイト飛びで、各文字のASCIIコード分"[7-9]vs"という形式の文字列を構成した配列
・gate: 固定の25個の整数配列
・gateとkeyについて、各index(=i)について以下が成り立つ。
・a = i + 1
・len(key[i]) == 3 * (gate[i] + 7 * a) // a
・hammer: passwdの2バイト目から1バイト飛びで、12個目まで以下のような構成になる。
{1: passwd[1] + passwd[25], 3: passwd[3] + passwd[27], ..., }
・hammerの各要素でpasswd[i] + passwd[i+24]を"."で結合したものをbase64エンコードしたものが
b'c3MxLnRkMy57XzUuaE83LjVfOS5faDExLkxfMTMuR0gxNS5fTDE3LjNfMTkuMzEyMS5pMzIz'と一致しない場合
Falseを返す。
・Trueを返す。まず末尾から1バイト飛びの文字については、3 * (gate[i] + 7 * a) // aを計算し、3で割ったものがASCIIコードになることを使って、復元する。次に先頭2バイトから1バイト飛びの文字については、base64デコードしたものから"."区切りで順に文字列を取り出し、復元する。あとは復元したものを交互に結合し、フラグを復元する。
#!/usr/bin/env python3 from base64 import b64decode gate = [118, 140, 231, 176, 205, 480, 308, 872, 702, 820, 1034, 1176, 1339, 1232, 1605, 1792, 782, 810, 1197, 880, 924, 1694, 2185, 2208, 2775] flag2 = '' for i in range(25): a = i + 1 code = (3 * (gate[i] + 7 * a) // a) // 3 flag2 = chr(code) + flag2 block = b'c3MxLnRkMy57XzUuaE83LjVfOS5faDExLkxfMTMuR0gxNS5fTDE3LjNfMTkuMzEyMS5pMzIz' flag1 = [''] * 24 s = b64decode(block).split(b'.') for i in range(len(s)): flag1[i] = chr(s[i][0]) flag1[i+12] = chr(s[i][1]) flag1 = ''.join(flag1) flag = '' for i in range(len(flag1)): flag += flag2[i] flag += flag1[i] flag += flag2[-1] print(flag)
vsctf{Th353_FL4G5_w3r3_inside_YOU_th3_WH0L3_T1M3}
Baby RSA (Cryptography)
公開鍵を読み取ると、以下のようになっている。
n = 52419317100235286358057114349639882093779997394202082664044401328860087685103 e = 101
nをyafuで素因数分解する。
>yafu-x64.exe "factor(52419317100235286358057114349639882093779997394202082664044401328860087685103)" -v -threads 4 07/10/22 07:20:04 v1.34.5 @ XXXX-XXXX, System/Build Info: Using GMP-ECM 6.3, Powered by GMP 5.1.1 detected Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz detected L1 = 32768 bytes, L2 = 16777216 bytes, CL = 64 bytes measured cpu frequency ~= 2894.441030 using 20 random witnesses for Rabin-Miller PRP checks =============================================================== ======= Welcome to YAFU (Yet Another Factoring Utility) ======= ======= bbuhrow@gmail.com ======= ======= Type help at any time, or quit to quit ======= =============================================================== cached 78498 primes. pmax = 999983 >> fac: factoring 52419317100235286358057114349639882093779997394202082664044401328860087685103 fac: using pretesting plan: normal fac: no tune info: using qs/gnfs crossover of 95 digits div: primes less than 10000 fmt: 1000000 iterations rho: x^2 + 3, starting 1000 iterations on C77 rho: x^2 + 2, starting 1000 iterations on C77 rho: x^2 + 1, starting 1000 iterations on C77 pm1: starting B1 = 150K, B2 = gmp-ecm default on C77 fac: setting target pretesting digits to 23.69 fac: sum of completed work is t0.00 fac: work done at B1=2000: 0 curves, max work = 30 curves fac: 30 more curves at B1=2000 needed to get to t23.69 ecm: 30/30 curves on C77, B1=2K, B2=gmp-ecm default fac: setting target pretesting digits to 23.69 fac: t15: 1.00 fac: t20: 0.04 fac: sum of completed work is t15.18 fac: work done at B1=11000: 0 curves, max work = 74 curves fac: 74 more curves at B1=11000 needed to get to t23.69 ecm: 74/74 curves on C77, B1=11K, B2=gmp-ecm default fac: setting target pretesting digits to 23.69 fac: t15: 7.17 fac: t20: 1.04 fac: t25: 0.05 fac: sum of completed work is t20.24 fac: work done at B1=50000: 0 curves, max work = 214 curves fac: 149 more curves at B1=50000 needed to get to t23.69 ecm: 149/149 curves on C77, B1=50K, B2=gmp-ecm default, ETA: 0 sec fac: setting target pretesting digits to 23.69 fac: t15: 28.45 fac: t20: 8.13 fac: t25: 0.74 fac: t30: 0.05 fac: sum of completed work is t23.72 starting SIQS on c77: 52419317100235286358057114349639882093779997394202082664044401328860087685103 ==== sieve params ==== n = 79 digits, 260 bits factor base: 34944 primes (max prime = 882967) single large prime cutoff: 75052195 (85 * pmax) allocating 7 large prime slices of factor base buckets hold 2048 elements using SSE4.1 enabled 32k sieve core sieve interval: 10 blocks of size 32768 polynomial A has ~ 10 factors using multiplier of 23 using SPV correction of 22 bits, starting at offset 41 using SSE2 for x64 sieve scanning using SSE2 for resieving 13-16 bit primes using SSE2 for 8x trial divison to 13 bits using SSE4.1 and inline ASM for small prime sieving using SSE2 for poly updating up to 15 bits using SSE4.1 for medium prime poly updating using SSE4.1 and inline ASM for large prime poly updating trial factoring cutoff at 88 bits ==== sieving in progress ( 4 threads): 35008 relations needed ==== ==== Press ctrl-c to abort and save state ==== 35775 rels found: 18827 full + 16948 from 179344 partial, (10962.98 rels/sec) sieving required 60180 total polynomials trial division touched 2821739 sieve locations out of 39439564800 QS elapsed time = 18.1073 seconds. ==== post processing stage (msieve-1.38) ==== begin with 198171 relations reduce to 50546 relations in 2 passes attempting to read 50546 relations recovered 50546 relations recovered 34267 polynomials freed 24 duplicate relations attempting to build 35751 cycles found 35751 cycles in 1 passes distribution of cycle lengths: length 1 : 18824 length 2 : 16927 largest cycle: 2 relations matrix is 34944 x 35751 (5.1 MB) with weight 1050811 (29.39/col) sparse part has weight 1050811 (29.39/col) filtering completed in 3 passes matrix is 24604 x 24668 (3.9 MB) with weight 816278 (33.09/col) sparse part has weight 816278 (33.09/col) saving the first 48 matrix rows for later matrix is 24556 x 24668 (3.2 MB) with weight 660080 (26.76/col) sparse part has weight 586096 (23.76/col) matrix includes 64 packed rows using block size 9867 for processor cache size 16384 kB commencing Lanczos iteration memory use: 2.9 MB lanczos halted after 390 iterations (dim = 24548) recovered 13 nontrivial dependencies Lanczos elapsed time = 0.8640 seconds. Sqrt elapsed time = 0.0230 seconds. SIQS elapsed time = 18.9947 seconds. pretesting / qs ratio was 0.59 Total factoring time = 30.2311 seconds ***factors found*** P39 = 283378097758180413812138939650885549231 P39 = 184980129074643957218827272858529362113 ans = 1
p - 1もq - 1もeと互いに素ではないため、通常の復号方法で復号できない。mod p, qの場合の式で、このことを前提にCRTを使いながら、復号する。
#!/usr/bin/env python3 from Crypto.PublicKey import RSA from Crypto.Util.number import * from sympy.ntheory.modular import crt c = 0x459cc234f24a2fb115ff10e272130048d996f5b562964ee6138442a4429af847 with open('pubkey.pem', 'r') as f: pub_data = f.read() pubkey = RSA.importKey(pub_data) n = pubkey.n e = pubkey.e print('[+] n =', n) print('[+] e =', e) p = 283378097758180413812138939650885549231 q = 184980129074643957218827272858529362113 assert p * q == n assert (p - 1) % e == 0 assert (q - 1) % e == 0 _lambda = p - 1 assert _lambda % e == 0 assert _lambda // e % e != 0 L = pow(2, _lambda // e, p) assert L > 1 d = inverse(e, _lambda // e) m1s = [] for i in range(e): m = pow(c % p, d, p) * pow(L, i, p) % p m1s.append(m) _lambda = q - 1 assert _lambda % e == 0 assert _lambda // e % e != 0 L = pow(2, _lambda // e, q) assert L > 1 d = inverse(e, _lambda // e) m2s = [] for i in range(e): m = pow(c % q, d, q) * pow(L, i, q) % q m2s.append(m) for m1 in m1s: for m2 in m2s: m, _ = crt([p, q], [m1, m2]) flag = long_to_bytes(m) if flag.startswith(b'vsctf{'): flag = flag.decode() print('[*] flag:', flag) break
実行結果は以下の通り。
[+] n = 52419317100235286358057114349639882093779997394202082664044401328860087685103
[+] e = 101
[*] flag: vsctf{5m411_Pr1m3_15_Un54f3!}
vsctf{5m411_Pr1m3_15_Un54f3!}
Art Final (Cryptography)
暗号処理の概要は以下の通り。
・boring_pix: Art_Final_2022.pngのデータ ・spicy_pix: 新イメージデータ初期化 ・rgba: ランダム32ビット整数を8ビットずつリトルエンディアンで分離 ・spicy_pix: boring_pixの各ピクセルのRGBAデータとrgbaとのXOR ・spicy_pixをENHANCED_Final_2022.pngに保存 ・key: ランダム16バイト文字列 ・iv: ランダム16バイト文字列 ・iv + flagをパディングしてAES-CBC暗号化し、その後base64エンコードしたものを表示
32bitランダム整数のデータがたくさん得られそうなので、Mersenne Twisterの特徴から状態を復元し、ランダム値を得られるようにすれば、AESの鍵が得られ、復号できる。
#!/usr/bin/env python3 import random from PIL import Image from Crypto.Cipher import AES from Crypto.Util.Padding import unpad from base64 import b64decode def four_to_one_int(ns): ret = 0 for n in ns[::-1]: ret *= 256 ret += n return ret def untemper(rand): rand ^= rand >> 18; rand ^= (rand << 15) & 0xefc60000; a = rand ^ ((rand << 7) & 0x9d2c5680); b = rand ^ ((a << 7) & 0x9d2c5680); c = rand ^ ((b << 7) & 0x9d2c5680); d = rand ^ ((c << 7) & 0x9d2c5680); rand = rand ^ ((d << 7) & 0x9d2c5680); rand ^= ((rand ^ (rand >> 11)) >> 11); return rand boring = Image.open('Art_Final_2022.png', 'r').convert('RGBA') boring_pix = boring.load() spicy = Image.open('ENHANCED_Final_2022.png', 'r').convert('RGBA') spicy_pix = spicy.load() N = 624 state = [] collect = True for i in range(boring.size[0] * boring.size[1]): x = i % boring.size[0] y = i // boring.size[0] rgba = tuple([bore ^ spice for bore, spice \ in zip(boring_pix[x, y], spicy_pix[x, y])]) num = four_to_one_int(rgba) if collect: state.append(untemper(num)) else: rgba2 = tuple(random.randbytes(4)) assert rgba == rgba2 if len(state) == 624: collect = False state.append(N) random.setstate([3, tuple(state), None]) enc_flag = b64decode('Tl5nK8L2KYZRCJCqLF7TbgKLgy1vIkH+KIAJv5/ILFoC+llemcmoLmCQYkiOrJ/orOOV+lwX+cVh+pwE5mtx6w==') key = bytes(random.sample(random.randbytes(16), 16)) iv = enc_flag[:AES.block_size] enc = AES.new(key, AES.MODE_CBC, iv) flag = unpad(enc.decrypt(enc_flag[AES.block_size:]), AES.block_size).decode() print(flag)
vsctf{1_gu355_R4ND0m_i5nt_tH4T_5p1cy}
Feedback Survey (Miscellaneous)
アンケートに答えたら、フラグが表示された。
vsctf{surv3y_c0mpl3t3r}
