この大会は2021/8/13 22:30(JST)~2021/8/15 22:30(JST)に開催されました。
今回もチームで参戦。結果は210点で604チーム中120位でした。
自分で解けた問題をWriteupとして書いておきます。
Sanity Check (Misc)
Discordに入り、#generalチャネルのトピックを見ると、フラグが書いてあった。
inctf{welcome_t0_inctf_internationals_2021}
Right Now Generator (Crypto)
暗号処理の概要は以下の通り。
・pad = 0xDEADC0DE ・sze = 64 ・mod = 2**64の次の素数 ・obj = RNG(128ビットランダム整数) ・128ビットランダム整数(最上位は1) ・seed = gen_seed(val=128ビットランダム整数) ・ret = [val % mod] ・val >>= 64 ・63回以下繰り返し ・val = pow(i ^ ret[i] ^ pad, 3, mod) ・retに(val % mod)を追加 ・val >>= sze ・retを返す。 ・wrap() ・out1: 64個のobj.next()の16進数16バイトの配列の連結 ・out2: 64個のobj.next()の16進数16バイトの配列の連結 ・cip: out1から生成したkeyでAES-CBC暗号 →暗号化データとivを返す ・cipにout2を追加 ・cip(暗号化データ, iv, out2)を出力 ◇RNG.next() ・a, b, c, d: seed[ctr^i](i=0~3) ・k: ctrが奇数の場合1、偶数の場合2 ・a, b, c, d = (k*a-b)%mod, (b-c)%mod, (c-d)%mod, (d-a)%mod ・ctr += 1 ・ctrが64の場合、wrap()を実行 ・aを返す。 ◇RNG.wrap() ・hsze = 32 ・64回以下繰り返し ・r1 = seed[i] ・r2 = seed[(i+32)%64] ・seed[i] = ((r1^pad)*r2)%mod ・ctr = 0
ctr = 63の場合 a, b, c, d = seed[63], seed[62], seed[61], seed[60] a = (seed[63] - seed[62]) % mod b = (seed[62] - seed[61]) % mod c = (seed[61] - seed[60]) % mod d = (seed[60] - seed[63]) % mod out2[63] = (seed[63] - seed[62]) % mod ctr = 62の場合 a, b, c, d = seed[62], seed[63], seed[60], seed[61] a = (2 * seed[62] - seed[63]) % mod b = (seed[63] - seed[60]) % mod c = (seed[60] - seed[61]) % mod d = (seed[61] - seed[62]) % mod out2[62] = (2 * seed[62] - seed[63]) % mod
簡単な連立方程式となるので、算出するための式は簡単に書ける。
seed[63] = (out2[63] * 2 + out2[62]) % mod seed[62] = (out2[63] + out2[62]) % mod : ||<< これでout2を生成する前まで戻せる。wrapも順に戻せるか見てみる。 >|| i = 63の場合 r1 = seed[63] r2 = seed[31] seed[63] = ((seed[63] ^ pad) * seed[31]) % mod →seed[63] = ((seed[63] * inverse(seed[31], mod)) % mod) ^ pad :
wrapも順に戻せば、out1を復元することができる。あとは鍵を生成し、AES-CBC復号すれば、フラグが得られる。
#!/usr/bin/python3 import hashlib, gmpy2, pickle from Crypto.Cipher import AES from Crypto.Util.Padding import unpad from Crypto.Util.number import * class RNG(): pad = 0xDEADC0DE sze = 64 mod = int(gmpy2.next_prime(2**sze)) def __init__(self, seed_val, seed=None): if seed == None: assert seed_val.bit_length() == 64*2, "Seed is not 128 bits!" self.seed = self.gen_seed(seed_val) self.wrap() else: self.seed = seed self.ctr = 0 def gen_seed(self, val): ret = [val % self.mod] val >>= self.sze for i in range(self.sze - 1): val = pow(i ^ ret[i] ^ self.pad, 3, self.mod) ret.append(val % self.mod) val >>= self.sze return ret def wrap(self, pr=True): hsze = self.sze//2 for i in range(self.sze): r1 = self.seed[i] r2 = self.seed[(i+hsze)%self.sze] self.seed[i] = ((r1^self.pad)*r2)%self.mod self.ctr = 0 def next(self): a, b, c, d = (self.seed[self.ctr^i] for i in range(4)) mod = self.mod k = 1 if self.ctr%2 else 2 a, b, c, d = (k*a-b)%mod, (b-c)%mod, (c-d)%mod, (d-a)%mod self.ctr += 1 if self.ctr==64: self.wrap(pr=False) return a pad = 0xDEADC0DE sze = 64 mod = int(gmpy2.next_prime(2**sze)) with open('enc.pickle', 'rb') as f: data = pickle.load(f) cip = bytes.fromhex(data['cip']) iv = bytes.fromhex(data['iv']) leak = data['leak'] out2 = [int(leak[i:i+16], 16) for i in range(0, len(leak), 16)] seed = [-1] * 64 for i in range(63, -1, -1): if i % 2 == 1: seed[i] = (out2[i] * 2 + out2[i^1]) % mod else: seed[i] = (out2[i] + out2[i^1]) % mod for i in range(63, -1, -1): r1 = seed[i] r2 = seed[(i + 32) % 64] seed[i] = ((r1 * inverse(r2, mod)) % mod) ^ pad obj = RNG(0, seed=seed) out1 = ''.join([format(obj.next(), '016x') for i in range(64)]) key = hashlib.sha256(bytes.fromhex(out1)).digest()[:16] cipher = AES.new(key, AES.MODE_CBC, iv) flag = unpad(cipher.decrypt(cip), 16).decode() print(flag)
inctf{S1mpl3_RN65_r_7h3_b35t!_b35e496b4d570c16}
Lost Baggage (Crypto)
暗号処理の概要は以下の通り。
・pvkey, pbkey = gen_key(FLAGのビット数) ・b = gen_inc_list(FLAGのビット数) ・b = [(16ビットランダム整数+5)の次の素数] ・bの要素数がFLAGのビット数になるまで以下繰り返し ・val: ランダム16ビット整数 ・bの数列の合計+val以上になる素数をbに追加 →bは超増加数列になる。 ・bを返す。 ・q: bの最後の要素 ・ランダム8ビット整数の回数だけ以下繰り返し ・q: qの2倍の次の素数 ・r: bの最後の要素 + ランダム128ビット整数 ・pb = [(r*i)%q for i in b] ・(b, r, q), pbを返す。 ・cip = encrypt(FLAG, pbkey) ・msg: FLAGの2進数表記 ・msgの各ビットで、1だった場合に対応するpbkeyの値を合計する。 →この合計値を返す。
Merkle-Hellmanナップサック暗号になっていることがわかるので、LLLを使って復号する。
#!/usr/bin/sage import pickle from Crypto.Util.number import long_to_bytes def is_valid_vector(b): if b[0] != 0: return False for i, x in enumerate(b): if i != 0 and abs(x) != 1: return False return True with open('enc.pickle', 'rb') as f: data = pickle.load(f) cip = data['cip'] pbkey = data['pbkey'] matrix_size = len(pbkey) + 1 m_list = [ [0 for _ in range(matrix_size)] for _ in range(matrix_size) ] for i in range(matrix_size - 1): m_list[i][0] = pbkey[i] m_list[i][i+1] = 2 m_list[matrix_size - 1][i+1] = -1 m_list[matrix_size - 1][0] = - cip llled = Matrix(ZZ, m_list).LLL() flag_vecs = [] for basis in llled: if is_valid_vector(basis): flag_vecs.append(basis) for v in flag_vecs: bin_flag = '' for _bit in reversed(v[1:]): c = ("1" if _bit == 1 else "0") bin_flag = bin_flag + c flag = long_to_bytes(int(bin_flag, 2)).decode() print(flag)
inctf{wr5_m4_b4g?}