この大会は2025/6/14 9:00(JST)～2025/6/16 9:00(JST)に開催されました。
今回もチームで参戦。結果は269点で1090チーム中196位でした。
自分で解けた問題をWriteupとして書いておきます。
Sanity Check (misc)
問題にフラグが書いてあった。
.;,;.{it_seems_you_started_this_ctf_'sane'._Lets_see_if_you_can_end_it_as_sane_as_you_started.}
Success (rev)
フラグの各文字のASCIIコードについて、条件がたくさんコードとして記載されている。z3でこの条件を満たすものを探す。
#!/usr/bin/env python3 from z3 import * x = [BitVec('x%d' % i, 8) for i in range(39)] s = Solver() s.add(x[37] * x[15] == 3366) s.add(x[8] + x[21] == 197) s.add(x[8] * x[13] == 9215) s.add(x[0] * x[3] == 2714) s.add(x[3] + x[21] == 159) s.add(x[1] * x[20] == 5723) s.add(x[6] | x[37] == 105) s.add(x[11] * x[7] == 11990) s.add(x[29] & x[25] == 100) s.add(x[16] | x[29] == 127) s.add(x[20] - x[6] == -8) s.add(x[21] + x[20] == 197) s.add(x[2] + x[36] == 77) s.add(x[35] * x[11] == 3630) s.add(x[4] * x[3] == 2714) s.add(x[35] ^ x[6] == 72) s.add(x[25] + x[24] == 221) s.add(x[14] * x[36] == 3465) s.add(x[15] - x[11] - 148 == -156) s.add(x[37] + x[17] == 138) s.add(x[1] ^ x[38] == 70) s.add(x[9] + x[29] == 212) s.add(x[30] - x[10] == 7) s.add(x[10] + x[33] == 206) s.add(x[7] * x[15] == 11118) s.add(x[28] * x[14] * 55 == 641025) s.add(x[7] | x[4] | 216 == 255) s.add(x[24] + x[4] == 151) s.add(x[2] * x[30] == 4928) s.add(x[5] + x[22] == 224) s.add(x[18] | x[36] == 127) s.add(x[13] + x[34] == 195) s.add(x[9] | x[17] == 111) s.add(x[12] * x[9] == 10403) s.add(x[25] ^ x[27] == 23) s.add(x[13] ^ x[34] == 59) s.add(x[18] + x[31] == 200) s.add(x[17] + x[32] == 213) s.add(x[2] * x[12] == 4444) s.add(x[24] * x[31] == 11025) s.add(x[5] * x[0] == 5658) s.add(x[10] + x[32] + 228 == 441) s.add(x[35] * x[0] == 1518) s.add(x[30] | x[8] == 113) s.add(x[28] - x[34] == 11) s.add(x[26] * x[14] == 9975) s.add(x[31] * x[22] == 10605) s.add(x[26] * x[32] * 239 == 2452140) s.add(x[28] * x[38] == 13875) s.add(x[18] + x[16] == 190) s.add(x[27] + x[26] + 96 == 290) s.add(x[22] - x[38] == -24) s.add(x[33] + x[5] == 224) s.add(x[19] * x[16] == 10355) s.add(x[27] + x[1] == 158) s.add(x[33] + x[12] == 202) s.add(x[19] * x[23] == 10355) r = s.check() assert r == sat m = s.model() flag = '' for i in range(39): flag += chr(m[x[i]].as_long()) print(flag)
.;,;.{imagine_if_i_made_it_compiled!!!}
saas (crypto)
サーバの処理概要は以下の通り。
・p, q: 512ビット素数(4で割って3余る素数) ・n = p * q ・e = 0x10001 ・以下繰り返し ・l: 数値入力(n未満) ・f(l)を表示 ・[-1 or 1] * pow(l, (p + 1) // 4, p)) * pow(q, -1, p) * q + [-1 or 1]* pow(x, (q + 1) // 4, q)) % q * pow(p, -1, q) * p) % n ・例外発生の場合、繰り返し終了 ・m: 0以上n-1以下ランダム整数 ・mを表示 ・s: 数値入力(n未満) ・pow(s, e, n)がmと一致する場合、フラグを表示
fはRabin暗号の暗号文から復号した平文4つのうち1つを返す関数。4つの平文は以下の構成になっている。
x % p = a or p - a x % q = b or p - b
つまり、この4パターンを入手し和を取れば、pまたはqで割り切れ、nがわかれば、p, qを算出できる。またこの4パターンを2乗したものの差分はすべてnで割った余りが同じことから、差分はnの倍数になる。このことからnを算出することができる。
あとはmを復号した値を入力すれば、フラグが得られる。
#!/usr/bin/env python3 import socket import itertools from Crypto.Util.number import * def recvuntil(s, tail): data = b'' while True: if tail in data: return data.decode() data += s.recv(1) e = 0x10001 skt = socket.socket(socket.AF_INET, socket.SOCK_STREAM) skt.connect(('smiley.cat', 34987)) l = 1234567890 fs = [] while True: data = recvuntil(skt, b'>>> ') print(data + str(l)) skt.sendall(str(l).encode() + b'\n') data = recvuntil(skt, b'\n').rstrip() print(data) f = int(data) if f not in fs: fs.append(f) if len(fs) == 4: break n_diffs = [] pq_sums = [] for x in itertools.combinations(fs, 2): n_diff = x[0]**2 - x[1]**2 if n_diff < 0: n_diff = - n_diff n_diffs.append(n_diff) pq_sum = x[0] + x[1] pq_sums.append(pq_sum) n = n_diffs[0] for i in range(1, len(n_diffs)): n = GCD(n, n_diffs[i]) print('[+] n:', n) for pq_sum in pq_sums: p = GCD(n, pq_sum) if p != n and p > 1: q = n // p break assert isPrime(p) and isPrime(q) assert p * q == n print('[+] p:', p) print('[+] q:', q) data = recvuntil(skt, b'>>> ') print(data) skt.sendall(b'\n') data = recvuntil(skt, b'\n').rstrip() print(data) m = int(data.split(' ')[-1]) phi = (p - 1) * (q - 1) d = inverse(e, phi) s = pow(m, d, n) data = recvuntil(skt, b'>>> ') print(data + str(s)) skt.sendall(str(s).encode() + b'\n') flag = recvuntil(skt, b'\n').rstrip() print('[*] flag:', flag)
実行結果は以下の通り。
>>> 1234567890
127722842213254781586758118684092238397393185259276147993025398605525862184256373296403848636462229709741964536718951797518422802798598464901547686908419039576878935261246456642814164465894139537321215407347584868502171742909965330104192907434951104657421937230523031700997087197322067669408662927234080437793
>>> 1234567890
127722842213254781586758118684092238397393185259276147993025398605525862184256373296403848636462229709741964536718951797518422802798598464901547686908419039576878935261246456642814164465894139537321215407347584868502171742909965330104192907434951104657421937230523031700997087197322067669408662927234080437793
>>> 1234567890
127722842213254781586758118684092238397393185259276147993025398605525862184256373296403848636462229709741964536718951797518422802798598464901547686908419039576878935261246456642814164465894139537321215407347584868502171742909965330104192907434951104657421937230523031700997087197322067669408662927234080437793
>>> 1234567890
78664478740681499692319087595291919473817744878657053483957455528162675465817222772526318856207718627945389036576053127711744514115305494457036853261234963319426526119075184517636156361235338700510427537683625632948320110267596806842012629732807313873138356547580413510434477487107717879787420003156106874774
>>> 1234567890
78664478740681499692319087595291919473817744878657053483957455528162675465817222772526318856207718627945389036576053127711744514115305494457036853261234963319426526119075184517636156361235338700510427537683625632948320110267596806842012629732807313873138356547580413510434477487107717879787420003156106874774
>>> 1234567890
20408450663577306220960565505123811029757564073724874383459511493607715510879570689633900800809074993374468940597444998025412356056751961234998661366523679746576089933167638972870446340151040652890354912831658344078833754931042605332603199166587992105449744499222633903353009914547121268208633834038948184316
>>> 1234567890
127722842213254781586758118684092238397393185259276147993025398605525862184256373296403848636462229709741964536718951797518422802798598464901547686908419039576878935261246456642814164465894139537321215407347584868502171742909965330104192907434951104657421937230523031700997087197322067669408662927234080437793
>>> 1234567890
20408450663577306220960565505123811029757564073724874383459511493607715510879570689633900800809074993374468940597444998025412356056751961234998661366523679746576089933167638972870446340151040652890354912831658344078833754931042605332603199166587992105449744499222633903353009914547121268208633834038948184316
>>> 1234567890
127722842213254781586758118684092238397393185259276147993025398605525862184256373296403848636462229709741964536718951797518422802798598464901547686908419039576878935261246456642814164465894139537321215407347584868502171742909965330104192907434951104657421937230523031700997087197322067669408662927234080437793
>>> 1234567890
78664478740681499692319087595291919473817744878657053483957455528162675465817222772526318856207718627945389036576053127711744514115305494457036853261234963319426526119075184517636156361235338700510427537683625632948320110267596806842012629732807313873138356547580413510434477487107717879787420003156106874774
>>> 1234567890
127722842213254781586758118684092238397393185259276147993025398605525862184256373296403848636462229709741964536718951797518422802798598464901547686908419039576878935261246456642814164465894139537321215407347584868502171742909965330104192907434951104657421937230523031700997087197322067669408662927234080437793
>>> 1234567890
127722842213254781586758118684092238397393185259276147993025398605525862184256373296403848636462229709741964536718951797518422802798598464901547686908419039576878935261246456642814164465894139537321215407347584868502171742909965330104192907434951104657421937230523031700997087197322067669408662927234080437793
>>> 1234567890
78664478740681499692319087595291919473817744878657053483957455528162675465817222772526318856207718627945389036576053127711744514115305494457036853261234963319426526119075184517636156361235338700510427537683625632948320110267596806842012629732807313873138356547580413510434477487107717879787420003156106874774
>>> 1234567890
20408450663577306220960565505123811029757564073724874383459511493607715510879570689633900800809074993374468940597444998025412356056751961234998661366523679746576089933167638972870446340151040652890354912831658344078833754931042605332603199166587992105449744499222633903353009914547121268208633834038948184316
>>> 1234567890
69466814136150588115399596593924129953333004454343968892527454570970902229318721213511430581063586075171044440740343667832090644740044931679509495013707756004028499075338911098048454444809841489701142782495617579632685387573411128594783476868731782889733325182165252093915619624761471057829876758116921747335
[+] n: 148131292876832087807718684189216049427150749333001022376484910099133577695135943986037749437271304703116433477316396795543835158855350426136546348274942719323455025194414095615684610806045180190211570320179243212581005497841007935436796106601539096762871681729745665604350097111869188937617296761273028622109
[+] p: 12994863769080445444956473863693438014393267441883615652557349834273542929427594116294599753100607393407058517000679280000153703736049646154634417358353271
[+] q: 11399218607377081506878251793659642361763796476173610996370248132946849766826824305608308057473070214093635307637733305584406945506580266026695494652544779
>>>
m = 138493488194585558083953817230565762236813958181169796808795590463157957874931271307355745502031794178451229114514256866106939506487143844690822167628866196957522738182388444235061690030499408912921869018459839415042592915774886456248300860069628291212293385227375134618185112299349503194909738987760057729173
>>> 99374095421206923683714405213892497296558223891898043656557296501409629024479597016208401618833626219781276289405194145693597103870453980802480326399350941538646247982770356398130461356675532670154224569254989694290378744673507997031138134003417272424449963478938587556637939524368485448889980480117162874942
[*] flag: .;,;.{squares_as_a_service_est_like_the_dawn_of_time}
.;,;.{squares_as_a_service_est_like_the_dawn_of_time}
never enough (crypto)
暗号化処理の概要は以下の通り。
・danger = 624*32 ・given = [] ・key = "" ・danger // 20 - 16回、以下繰り返し ・x: ランダム32ビット整数 ・keyにx % 2**12を文字列として結合 ・given: x >> 12を追加 ・key = key[:100] ・key: keyのsha256ダイジェスト ・givenを出力 ・flagを"\x00"でパディングし、keyでAES ECBモード暗号化したものを16進数表記で出力
Mersenne Twsiterの問題。givenは982個の情報がある。下12ビットが欠落しているので、関係する値の間で総当たりする。
乱数をr0～r981とすると、以下のようになる。
・r0の最上位ビットはわかっている。 ・r1の最上位ビット以外の値とr397の値がわかっていれば、r624の値がわかる。 ・r624の上位20ビットが合っているものを探す。
つまりブルートフォースのケーズは2**24である。乱数の1個目だけは特定できないため、AES暗号の復号を行い、フラグの形式になるものを探す。
#!/usr/bin/env python3 from Crypto.Cipher import AES from hashlib import sha256 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 def temper(st): y = st y ^= y >> 11 y ^= (y << 7) & 0x9d2c5680 y ^= (y << 15) & 0xefc60000 y ^= y >> 18 return y def get_st624(st0, st1, st397): n = st0 & 0x80000000 n += st1 & 0x7fffffff st = st397 ^ (n >> 1) if n % 2 != 0: st ^= 0x9908b0df return st def get_st624_0(st1, st397): st_list = [] for x in [0, 0x80000000]: n = x + (st1 & 0x7fffffff) st = st397 ^ (n >> 1) if n % 2 != 0: st ^= 0x9908b0df st_list.append(st) return st_list danger = 624 * 32 with open('out.txt', 'r') as f: params = f.read().splitlines() given = eval(params[0]) enc_flag = bytes.fromhex(params[1]) rnd = [-1] * (danger // 20 - 16 - 624) rnd[0] = given[0] << 12 key_without_head = '' for i in range(danger // 20 - 16 - 624): r0 = rnd[i] st0 = untemper(r0) r1_part = given[i + 1] << 12 r397_part = given[i + 397] << 12 found = False for j in range(2**12): r1 = r1_part + j st1 = untemper(r1) for k in range(2**12): r397 = r397_part + k st397 = untemper(r397) if i == 0: st624_list = get_st624_0(st1, st397) for st624 in st624_list: if temper(st624) >> 12 == given[i + 624]: found = True rnd[i + 1] = r1 key_without_head += str(r1 % 2**12) break else: r624 = get_st624(st0, st1, st397) if temper(r624) >> 12 == given[i + 624]: found = True rnd[i + 1] = r1 key_without_head += str(r1 % 2**12) if found: break if found: break if len(key_without_head) >= 100: break print('[+] key part:', key_without_head) for i in range(2**12): key = str(i) + key_without_head key = key[:100] key = sha256(key.encode()).digest() cipher = AES.new(key, AES.MODE_ECB) flag = cipher.decrypt(enc_flag) if flag.startswith(b'.;,;.{'): flag = flag.rstrip(b'\x00').decode() print('[*] flag:', flag) break
実行結果は以下の通り。
[+] key part: 122034203256216122924163875116925356934163689349935828615933987262515679539414703525201051123827853062
[*] flag: .;,;.{never_enough_but_you_gotta_just_make_more_or_something_idk_im_not_a_motivational_speaker_but_you_get_the_idea}
.;,;.{never_enough_but_you_gotta_just_make_more_or_something_idk_im_not_a_motivational_speaker_but_you_get_the_idea}
