🐊

# WaniCTF 2024 Writeup [Crypto全完]

2024/06/23に公開

めちゃめちゃ楽しかったです。学びもあってすごくいい回でした。

# beginners_rsa [530 solves]

Do you know RSA?

chall.py
from Crypto.Util.number import *

p = getPrime(64)
q = getPrime(64)
r = getPrime(64)
s = getPrime(64)
a = getPrime(64)
n = p*q*r*s*a
e = 0x10001

FLAG = b'FLAG{This_is_a_fake_flag}'
m = bytes_to_long(FLAG)
enc = pow(m, e, n)
print(f'n = {n}')
print(f'e = {e}')
print(f'enc = {enc}')

n = 317903423385943473062528814030345176720578295695512495346444822768171649361480819163749494400347
e = 65537
enc = 127075137729897107295787718796341877071536678034322988535029776806418266591167534816788125330265


n が小さいので素因数分解ができます。SageMath Onlineで素因数分解しました。

from Crypto.Util.number import *

n = 317903423385943473062528814030345176720578295695512495346444822768171649361480819163749494400347
e = 65537
enc = 127075137729897107295787718796341877071536678034322988535029776806418266591167534816788125330265

p = 9953162929836910171
q = 11771834931016130837
r = 12109985960354612149
s = 13079524394617385153
a = 17129880600534041513

phi = (p-1)*(q-1)*(r-1)*(s-1)*(a-1)

d = pow(e, -1, phi)

m = pow(enc, d, n)

print(long_to_bytes(m))


FLAG{S0_3a5y_1254!!}

# beginners_aes [453 solves]

AES is one of the most important encryption methods in our daily lives.

chall.py
# https://pycryptodome.readthedocs.io/en/latest/src/cipher/aes.html
from Crypto.Cipher import AES
from os import urandom
import hashlib

key = b'the_enc_key_is_'
iv = b'my_great_iv_is_'
key += urandom(1)
iv += urandom(1)

cipher = AES.new(key, AES.MODE_CBC, iv)
FLAG = b'FLAG{This_is_a_dummy_flag}'
flag_hash = hashlib.sha256(FLAG).hexdigest()

enc = cipher.encrypt(msg)

print(f'enc = {enc}') # bytes object
print(f'flag_hash = {flag_hash}') # str object

enc = b'\x16\x97,\xa7\xfb_\xf3\x15.\x87jKRaF&"\xb6\xc4x\xf4.K\xd77j\xe5MLI_y\xd96\xf1$\xc5\xa3\x03\x990Q^\xc0\x17M2\x18' flag_hash = 6a96111d69e015a07e96dcd141d31e7fc81c4420dbbef75aef5201809093210e  key と iv について、考えうるものが 65536 ( = 256 \times 256) 通りしかない。全て試す。 # https://pycryptodome.readthedocs.io/en/latest/src/cipher/aes.html from Crypto.Util.Padding import pad from Crypto.Cipher import AES from os import urandom import hashlib key = b'the_enc_key_is_' iv = b'my_great_iv_is_' key += urandom(1) iv += urandom(1) cipher = AES.new(key, AES.MODE_CBC, iv) FLAG = b'FLAG{This_is_a_dummy_flag}' flag_hash = hashlib.sha256(FLAG).hexdigest() msg = pad(FLAG, 16) enc = cipher.encrypt(msg) print(f'enc = {enc}') print(f'flag_hash = {flag_hash}')  # replacement [431 solves] No one can read my diary! from secret import cal import hashlib enc = [] for char in cal: x = ord(char) x = hashlib.md5(str(x).encode()).hexdigest() enc.append(int(x, 16)) with open('my_diary_11_8_Wednesday.txt', 'w') as f: f.write(str(enc))  my_diary_11_8_Wednesday.txt は省略。 全ての 1 文字に対して md5.hexdigest() した結果を事前に求めておけばよい。 cs = [] # my_diary_11_8_Wednesday.txt の内容 ms = [] for c in cs: for i, h in enumerate(hs): if c == h: ms.append(i) print(''.join(chr(x) for x in ms))  # Wednesday, 11/8, clear skies. This morning, I had breakfast at my favorite cafe. Drinking the freshly brewed coffee and savoring the warm buttery toast is the best. Changing the subject, I received an email today with something rather peculiar in it. It contained a mysterious message that said "This is a secret code, so please don't tell anyone. FLAG{13epl4cem3nt}". How strange! # # Gureisya  FLAG{13epl4cem3nt} # Easy calc [95 solves] 😆 chall.py import os import random from hashlib import md5 from Crypto.Cipher import AES from Crypto.Util.number import long_to_bytes, getPrime FLAG = os.getenvb(b"FLAG", b"FAKE{THIS_IS_NOT_THE_FLAG!!!!!!}") def encrypt(m: bytes, key: int) -> bytes: iv = os.urandom(16) key = long_to_bytes(key) key = md5(key).digest() cipher = AES.new(key, AES.MODE_CBC, iv=iv) return iv + cipher.encrypt(m) def f(s, p): u = 0 for i in range(p): u += p - i u *= s u %= p return u p = getPrime(1024) s = random.randint(1, p - 1) A = f(s, p) ciphertext = encrypt(FLAG, s).hex() print(f"{p = }") print(f"{A = }") print(f"{ciphertext = }")  f(s, p) は（値を知っていたとしても、p がデカすぎて）愚直に求められないので、どうにかして計算できないかを考える。 f の中身を追っていく。 (1-s)f(s, p) は初項 s, 公比 s の等比数列の総和と等しいことが分かる。 すなわち A \equiv \frac{s(1-s^p)}{(1-s)^2} \pmod p ここで、フェルマーの小定理を思い出すと、 s^p \equiv 1 \pmod p であるから、 A \equiv \frac{s}{1-s} \pmod p となり、これと合致する s を計算すればよい solve_s.sage p = 108159532265181242371960862176089900437183046655107822712736597793129430067645352619047923366465213553080964155205008757015024406041606723580700542617009651237415277095236385696694741342539811786180063943404300498027896890240121098409649537982185247548732754713793214557909539077228488668731016501718242238229 A = 60804426023059829529243916100868813693528686280274100232668009387292986893221484159514697867975996653561494260686110180269479231384753818873838897508257692444056934156009244570713404772622837916262561177765724587140931364577707149626116683828625211736898598854127868638686640564102372517526588283709560663960 F = GF(p) R.<s> = PolynomialRing(F) numerator = s denominator = (1 - s) polynomial = numerator - A * denominator roots = polynomial.roots() for root, multiplicity in roots: print(f"s = {root}")  solve.py p = 108159532265181242371960862176089900437183046655107822712736597793129430067645352619047923366465213553080964155205008757015024406041606723580700542617009651237415277095236385696694741342539811786180063943404300498027896890240121098409649537982185247548732754713793214557909539077228488668731016501718242238229 A = 60804426023059829529243916100868813693528686280274100232668009387292986893221484159514697867975996653561494260686110180269479231384753818873838897508257692444056934156009244570713404772622837916262561177765724587140931364577707149626116683828625211736898598854127868638686640564102372517526588283709560663960 ciphertext = '9fb749ef7467a5aff04ec5c751e7dceca4f3386987f252a2fc14a8970ff097a81fcb1a8fbe173465eecb74fb1a843383' s = 1687413597309293800744215069073564700111464906280803472827126056011788534089081297767956072498777988960765236816249236506915467068679173946738276390422326894133097728262062079690201267739279447117445097896824910096682450843424480831170129071861123241366800056648768192097429858942658575325552357170973141110 import os from hashlib import md5 from Crypto.Cipher import AES from Crypto.Util.number import * def decrypt(c: bytes, key: int) -> bytes: iv = c[:16] ciphertext = c[16:] key = long_to_bytes(key) key = md5(key).digest() cipher = AES.new(key, AES.MODE_CBC, iv=iv) decrypted = cipher.decrypt(ciphertext) return decrypted m = decrypt(bytes.fromhex(ciphertext), s) print(m)  FLAG{Do_the_math396691ba7d7270a} # dance [85 solves] step by step chall.py from mycipher import MyCipher import hashlib import datetime import random isLogged = False current_user = '' d = {} def make_token(data1: str, data2: str): sha256 = hashlib.sha256() sha256.update(data1.encode()) right = sha256.hexdigest()[:20] sha256.update(data2.encode()) left = sha256.hexdigest()[:12] token = left + right return token def main(): print('Welcome to the super secure encryption service!') while True: print('Select an option:') print('1. Register') print('2. Login') print('3. Logout') print('4. Encrypt') print('5. Exit') choice = input('> ') if choice == '1': Register() elif choice == '2': Login() elif choice == '3': Logout() elif choice == '4': Encrypt() elif choice == '5': print('Goodbye!') break else: print('Invalid choice') def Register(): global d username = input('Enter username: ') if username in d: print('Username already exists') return dt_now = datetime.datetime.now() minutes = dt_now.minute sec = dt_now.second print(minutes, sec) data1 = f'user: {username}, {minutes}:{sec}' data2 = f'{username}'+str(random.randint(0, 10)) d[username] = make_token(data1, data2) print('Registered successfully!') print('Your token is:', d[username]) return def Login(): global isLogged global d global current_user username = input('Enter username: ') if username not in d: print('Username does not exist') return token = input('Enter token: ') if d[username] != token: print('Invalid token') return isLogged = True current_user = username print(f'Logged in successfully! Hi {username}!') return def Logout(): global isLogged global current_user isLogged = False current_user = '' print('Logged out successfully!') return def Encrypt(): global isLogged global current_user if not isLogged: print('You need to login first') return token = d[current_user] sha256 = hashlib.sha256() sha256.update(token.encode()) key = sha256.hexdigest()[:32] nonce = token[:12] cipher = MyCipher(key.encode(), nonce.encode()) plaintext = input('Enter plaintext: ') ciphertext = cipher.encrypt(plaintext.encode()) print('username:', current_user) print('Ciphertext:', ciphertext.hex()) return if __name__ == '__main__': main()  username = 'gureisya' ciphertext = '061ff06da6fbf8efcd2ca0c1d3b236aede3f5d4b6e8ea24179'  MyCipher 等は省略。共通鍵暗号の一種だった。 data1 = f'user: {username}, {minutes}:{sec}' data2 = f'{username}'+str(random.randint(0, 10))  の部分に着目すると、key や nonce などを生成している data1, data2 としてありうるパターンが 36000 通りしかないことが分かるため、すべて試す。 solve.py from mycipher import MyCipher import hashlib import datetime import random username = 'gureisya' ciphertext = bytes.fromhex('061ff06da6fbf8efcd2ca0c1d3b236aede3f5d4b6e8ea24179') def make_token(data1: str, data2: str): sha256 = hashlib.sha256() sha256.update(data1.encode()) right = sha256.hexdigest()[:20] sha256.update(data2.encode()) left = sha256.hexdigest()[:12] token = left + right return token for minutes in range(60): for sec in range(60): for n in range(10): data1 = f'user: {username}, {minutes}:{sec}' data2 = f'{username}'+str(random.randint(0, 10)) token = make_token(data1, data2) sha256 = hashlib.sha256() sha256.update(token.encode()) key = sha256.hexdigest()[:32] nonce = token[:12] cipher = MyCipher(key.encode(), nonce.encode()) plaintext = cipher.encrypt(ciphertext) if plaintext.startswith(b'FLAG'): print(plaintext)  FLAG{d4nc3_l0b0t_d4nc3!!} # speedy [60 solves] I made a super speedy keystream cipher!! chall.py from cipher import MyCipher from Crypto.Util.number import * from Crypto.Util.Padding import * import os s0 = bytes_to_long(os.urandom(8)) s1 = bytes_to_long(os.urandom(8)) cipher = MyCipher(s0, s1) secret = b'FLAG{'+b'*'*19+b'}' pt = pad(secret, 8) ct = cipher.encrypt(pt) print(f'ct = {ct}')  cipher.py from Crypto.Util.number import * from Crypto.Util.Padding import * def rotl(x, y): x &= 0xFFFFFFFFFFFFFFFF return ((x << y) | (x >> (64 - y))) & 0xFFFFFFFFFFFFFFFF class MyCipher: def __init__(self, s0, s1): self.X = s0 self.Y = s1 self.mod = 0xFFFFFFFFFFFFFFFF self.BLOCK_SIZE = 8 def get_key_stream(self): s0 = self.X s1 = self.Y sum = (s0 + s1) & self.mod s1 ^= s0 key = [] for _ in range(8): key.append(sum & 0xFF) sum >>= 8 self.X = (rotl(s0, 24) ^ s1 ^ (s1 << 16)) & self.mod self.Y = rotl(s1, 37) & self.mod return key def encrypt(self, pt: bytes): ct = b'' for i in range(0, len(pt), self.BLOCK_SIZE): ct += long_to_bytes(self.X) key = self.get_key_stream() block = pt[i:i+self.BLOCK_SIZE] ct += bytes([block[j] ^ key[j] for j in range(len(block))]) return ct  8 文字ごとにブロック暗号で暗号化しているようだ。 また、flag の長さはパディングも含めると 28 であり、 get_key_stream() は系4回行われていることが分かる。 そして、毎ラウンドの X についてはわかっている。 どうにかしてそれぞれの key を求めたい。 1回目について、最終的な XX_{after} とし、self.X = (rotl(s0, 24) ^ s1 ^ (s1 << 16)) & self.mod について式を追ってみると、以下の図のような計算を行っていることが分かる。 X_{after} さえわかれば、S_1 の下位 2 バイトが復元可能 S_1 の下位 2 バイトさえわかれば、 S_1 の下位 4 バイトが復元可能 というように、順番に 2 バイトずつ求めることができる。 肝心の X_{after} は次のラウンドの X であるため、以上から求めることができた。 最後の 8 バイトについては上のアルゴリズムだと求められないが、}\x07\x07\x07\x07\x07\x07\x07 なのが事前にわかっているため、心配する必要は無い。 solve.py from Crypto.Util.number import * ct = b'"G:F\xfe\x8f\xb0<O\xc0\x91\xc8\xa6\x96\xc5\xf7N\xc7n\xaf8\x1c,\xcb\xebY<z\xd7\xd8\xc0-\x08\x8d\xe9\x9e\xd8\xa51\xa8\xfbp\x8f\xd4\x13\xf5m\x8f\x02\xa3\xa9\x9e\xb7\xbb\xaf\xbd\xb9\xdf&Y3\xf3\x80\xb8' def rotl(x, y): x &= 0xFFFFFFFFFFFFFFFF return ((x << y) | (x >> (64 - y))) & 0xFFFFFFFFFFFFFFFF def get_key(X: int, nxt_X: int): X_rot24 = rotl(X, 24) S1_0 = (X_rot24 & 0x000000000000FFFF)^(nxt_X & 0x000000000000FFFF) S1_1 = (X_rot24 & 0x00000000FFFF0000)^(nxt_X & 0x00000000FFFF0000)^(S1_0 << 16) S1_2 = (X_rot24 & 0x0000FFFF00000000)^(nxt_X & 0x0000FFFF00000000)^(S1_1 << 16) S1_3 = (X_rot24 & 0xFFFF000000000000)^(nxt_X & 0xFFFF000000000000)^(S1_2 << 16) S1_new = S1_0 + S1_1 + S1_2 + S1_3 S1 = S1_new^X sum = (X+S1) & 0xFFFFFFFFFFFFFFFF key = [] for _ in range(8): key.append(sum & 0xFF) sum >>= 8 return key pt = b'' for i in range(0, 48, 16): X = bytes_to_long(ct[i:i+8]) nxt_X = bytes_to_long(ct[i+16:i+24]) key = get_key(X, nxt_X) block = ct[i+8:i+16] pt += bytes([block[j] ^ key[j] for j in range(8)]) pt += b'}' print(pt)  FLAG{x013_ro74te_5hif7!!} # Many Xor Shift [29 solves] はるか昔の記憶 Memories of long long ago. chall.py FLAG = b'FAKE{XXXXXXXXXXXXXXXXXXXXXX}' N = 7 M = 17005450388330379 WORD_SIZE = 32 WORD_MASK = (1 << WORD_SIZE) - 1 def encrypt(m): state = [int.from_bytes(m[i:i+4]) for i in range(0, len(m), 4)] assert len(state) == N def xor_shift(): nonlocal state t = state[0] ^ ((state[0] << 11) & WORD_MASK) for i in range(N-1): state[i] = state[i+1] state[-1] = (state[-1] ^ (state[-1] >> 19)) ^ (t ^ (t >> 8)) for _ in range(M): xor_shift() return state print("N = ", N) print("M = ", M) print("WORD_SIZE = ", WORD_SIZE) print("state = ", encrypt(FLAG))  N = 7 M = 17005450388330379 WORD_SIZE = 32 state = [1927245640, 871031439, 789877080, 4042398809, 3950816575, 2366948739, 935819524]  M 回 特殊な xor_shift を行っている。xor_shift は、あるタイミングの状態が分かれば、それを基に復元をすることができる。 state を列ベクトルとみなし、操作がどのような行列になっているかを考える。 例えば、以下の操作を考えてみる。 for i in range(N-1): state[i] = state[i+1]  これは、以下のような行列で表すことができる。 {state}^\prime = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix} \times {state} 同様に、xor_shift についても、各要素の i ビット目をもった 224 \times 224 行列を用意することで、構築することができる（ややこしいので詳細は実装を見てほしい） これで行列を準備することができた。逆行列をかけることによって、1 回状態を戻すことができる。 M 回状態を戻す必要があるので M 乗する必要があるが、これは繰り返し二乗法を用いることで高速に計算できる。 solve.sage N = 7 M = 17005450388330379 WORD_SIZE = 32 state = [1927245640, 871031439, 789877080, 4042398809, 3950816575, 2366948739, 935819524] import numpy as np V = np.matrix([[0] for j in range(N*WORD_SIZE)]) for j in range(N): for k in range(WORD_SIZE): V[WORD_SIZE*j + k] = state[j] >> k & 1 A = np.zeros((N*WORD_SIZE, N*WORD_SIZE)) # shift for i in range((N-1)*WORD_SIZE): A[i][i+WORD_SIZE] += 1 # 0 for i in range(WORD_SIZE): A[(N-1)*WORD_SIZE+i][i] = 1 for i in range(11, WORD_SIZE, 1): A[(N-1)*WORD_SIZE+i][i-11] = 1 for i in range(8, WORD_SIZE, 1): A[(N-1)*WORD_SIZE+i-8][i] = 1 for i in range(11, WORD_SIZE, 1): A[(N-1)*WORD_SIZE+i-8][i-11] = 1 # 6 for i in range(WORD_SIZE): A[(N-1)*WORD_SIZE+i][(N-1)*WORD_SIZE+i] = 1 for i in range(19, WORD_SIZE, 1): A[(N-1)*WORD_SIZE+i-19][(N-1)*WORD_SIZE+i] = 1 MS = MatrixSpace(GF(2), N*WORD_SIZE, N*WORD_SIZE) A = MS(A) def power(a, k): ret = np.identity(N*WORD_SIZE) ret = MS(ret) while k: if k & 1: ret = ret * a a = a * a k >>= 1 return ret inv_A = A^(-1) inv = power(inv_A, M) begin_state_v = inv*V begin_state = [0 for _ in range(N)] for i in range(N): for j in range(WORD_SIZE): if begin_state_v[i*WORD_SIZE + j]: begin_state[i] += 1 << j from Crypto.Util.number import * print(b''.join(long_to_bytes(x) for x in begin_state))  FLAG{m47r1x_!n_8inary_w0rld} # uf [14 solves] 🙄 chall.py import os from secrets import randbits from Crypto.Util.number import bytes_to_long FLAG = os.environb.get(b"FLAG", b"FAKE{THIS_IS_DUMMY_FLAG}") m = bytes_to_long(FLAG) assert m.bit_length() >= 512 def encrypt(m: int, n: int = 512) -> int: x = 0 for i in range(n): x <<= 1 x += m * randbits(1) if i >= n // 2: x ^= randbits(1) return x X = [encrypt(m) for _ in range(4)] print(X)  output.txt [6643852762092641655051592752286380661448697120839285262713138738793179330857521051418707355387198243788554658967735136760757552410466512939791351078152197994352930016306075464400264019640466277732596022216246131141036813931972036259910390741311141390889450882074162723823607552591155184799627590418587536982033939537563823, 4495106960532238798978878322218382764459613684889887356979907395021294655849239390809608204284927849117763119933285899077777162943233437728643056322845118660545730870443735090094400144586494098834221418487123653668703665085461676013454922344247818407399456870636622800919629442727075235809213114639237367651539678560390951, 7622226387024225267485603541284038981214490586915816777231024576546652676746968149372915915975325662783469952634025859954515971134032563991925283958708572235632178937041656690377178266198211581176947491463237398083133658483056792368618417698027992083481412961301906342594056438180675328433412539805240307255787971167535638, 1149407465454162408488208063367931363888120160126632926627929705372269921465081968665764846439238807939361247987642326885758277171318666479752274577607727935160689442316433824450832192798328252739495913920016290902086534688608562545166349970831960156036289570935410160077618096614135121287858428753273136461851339553609896]  m を足すか足さないかし、1ビットシフト」を 512 回行っているうえに、下位 256 ビットはぐちゃぐちゃにされている。 m を足すか足さないかし、1ビットシフト」だけならば、最大公約数を計算することによって m を復元できる。 そういえば、誤差込みでの計算が得意な LLL というアルゴリズムがあることを思い出し、いろいろ調査してみると、Approximate Common Divisor Problem というものがあることを知る。今回の問題と合致しているので、これを使ってみる。 頑張って紹介されている論文を見たりしながら、行列を作って計算させた。 solve.py x = [6643852762092641655051592752286380661448697120839285262713138738793179330857521051418707355387198243788554658967735136760757552410466512939791351078152197994352930016306075464400264019640466277732596022216246131141036813931972036259910390741311141390889450882074162723823607552591155184799627590418587536982033939537563823, 4495106960532238798978878322218382764459613684889887356979907395021294655849239390809608204284927849117763119933285899077777162943233437728643056322845118660545730870443735090094400144586494098834221418487123653668703665085461676013454922344247818407399456870636622800919629442727075235809213114639237367651539678560390951, 7622226387024225267485603541284038981214490586915816777231024576546652676746968149372915915975325662783469952634025859954515971134032563991925283958708572235632178937041656690377178266198211581176947491463237398083133658483056792368618417698027992083481412961301906342594056438180675328433412539805240307255787971167535638, 1149407465454162408488208063367931363888120160126632926627929705372269921465081968665764846439238807939361247987642326885758277171318666479752274577607727935160689442316433824450832192798328252739495913920016290902086534688608562545166349970831960156036289570935410160077618096614135121287858428753273136461851339553609896] rho = 256 x_zero = x[0] K = 1 << (rho+1) M = matrix([ [K, x[0], x[1], x[2], x[3]], [0, -x_zero, 0, 0, 0], [0, 0, -x_zero, 0, 0], [0, 0, 0, -x_zero, 0], [0, 0, 0, 0, -x_zero], ]) A = M.LLL() guess_m = [] for i in range(5): q_zero = A[i][0] // K if q_zero == 0: continue r_zero = x_zero % q_zero p = (x_zero-r_zero) // q_zero p = abs(p) guess_m.append(p) from Crypto.Util.number import * for x in guess_m: print(long_to_bytes(x))  FLAG{hope_this_chal_is_not_automatically_solved_by_AI_c14ef1732e87a6c} 初めて LLL を使った問題が解けて、とっても嬉しい。 # Cheat Code [44 solves] チートがあれば何でもできる You can do anything with cheats. server.py from hashlib import sha256 import os from secrets import randbelow from secret import flag, cheat_code import re challenge_times = 100 hash_strength = int(os.environ.get("HASH_STRENGTH", 10000)) def super_strong_hash(s: str) -> bytes: sb = s.encode() for _ in range(hash_strength): sb = sha256(sb).digest() return sb cheat_code_hash = super_strong_hash(cheat_code) print(f"hash of cheat code: {cheat_code_hash.hex()}") print("If you know the cheat code, you will always be accepted!") secret_number = randbelow(10**10) secret_code = f"{secret_number:010d}" print(f"Find the secret code of 10 digits in {challenge_times} challenges!") def check_code(given_secret_code, given_cheat_code): def check_cheat_code(given_cheat_code): return super_strong_hash(given_cheat_code) == cheat_code_hash digit_is_correct = [] for i in range(10): digit_is_correct.append(given_secret_code[i] == secret_code[i] or check_cheat_code(given_cheat_code)) return all(digit_is_correct) given_cheat_code = input("Enter the cheat code: ") if len(given_cheat_code) > 50: print("Too long!") exit(1) for i in range(challenge_times): print(f"=====Challenge {i+1:03d}=====") given_secret_code = input("Enter the secret code: ") if not re.match(r"^\d{10}$", given_secret_code):
print("Wrong format!")
exit(1)
if check_code(given_secret_code, given_cheat_code):
print("Correct!")
print(flag)
exit(0)
else:
print("Wrong!")
print("Game over!")


10^{10} 択を 100 回以内に当てる問題（ではなくってよ）

for i in range(10):
digit_is_correct.append(given_secret_code[i] == secret_code[i] or check_cheat_code(given_cheat_code))


わざわざ 1 回判定すればいい check_cheat_code()10 回も求めている。そして、この関数の実行に時間がかかることも考えると、サイドチャネル攻撃ができそうだと分かる（python における X or Y は、 X が True の時にわざわざ Y を見ないため、 Xが True の時は素早く実行が終わる）。

※プログラムはチームメイトに作ってもらいました。

solve.py
from pwn import *
import time

server = 'chal-lz56g6.wanictf.org'
port = 5000

def find_correct_digit(current_code, position):
fastest_time = float('inf')
correct_digit = 0
for i in range(10):
test_code = current_code[:position] + str(i) + current_code[position+1:]
conn.recvuntil(b"Enter the secret code: ")

start_time = time.time()
conn.sendline(test_code.encode())
response = conn.recvline()
elapsed_time = time.time() - start_time

if b"Correct" in response:
print(conn.recvuntil(b"}").decode())
conn.close()
return test_code, True

if elapsed_time < fastest_time:
fastest_time = elapsed_time
correct_digit = i

return current_code[:position] + str(correct_digit) + current_code[position+1:], False

code = "0000000000"
conn = remote(server, port)
print(conn.recvuntil(b"Enter the cheat code: "))
conn.sendline(b"pwn")

for position in range(10):
code, found = find_correct_digit(code, position)
print(f"{position}: {code}")
if found:
break

print(f"Found code: {code}")


FLAG{t1m!ng_a774ck_1s_f34rfu1}