InCTF 2021 Writeup

この大会は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?}