⛳

Crew CTF 2024 脆弱Writeup

2024/08/07に公開

Python

cryptography

CTF

tech

Crew CTF 2024をチーム「脆弱エンジニア(full_weak_engineer)」で参加してきました。
19位でした！

なお、asusnの得点は0点です（stdout川花火大会の動画制作に没頭してしまったため）

チームメンバーが強いね！！！

チームメンバーのWriteup

振り返り

解きたかった問題を解説してきます。

4ES (crypto)

問題

AES_AES_AES_AES!という文字列にAESを4回施す。
各キーは、crew_AES*4=$!?の14文字の中から3文字選んで生成されるハッシュである。

#!/usr/bin/env python3

from hashlib import sha256
from random import choices

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad


with open('flag.txt', 'rb') as f:
    FLAG = f.read().strip()

chars = b'crew_AES*4=$!?'
L = 3

w, x, y, z = (
    bytes(choices(chars, k=L)),
    bytes(choices(chars, k=L)),
    bytes(choices(chars, k=L)),
    bytes(choices(chars, k=L)),
)

k1 = sha256(w).digest()
k2 = sha256(x).digest()
k3 = sha256(y).digest()
k4 = sha256(z).digest()

print(w.decode(), x.decode(), y.decode(), z.decode())

pt = b'AES_AES_AES_AES!'
ct = AES.new(k4, AES.MODE_ECB).encrypt(
         AES.new(k3, AES.MODE_ECB).encrypt(
             AES.new(k2, AES.MODE_ECB).encrypt(
                 AES.new(k1, AES.MODE_ECB).encrypt(
                     pt
                 )
             )
         )
     )

key = sha256(w + x + y + z).digest()
enc_flag = AES.new(key, AES.MODE_ECB).encrypt(pad(FLAG, AES.block_size))

with open('output.txt', 'w') as f:
    f.write(f'pt = {pt.hex()}\nct = {ct.hex()}\nenc_flag = {enc_flag.hex()}')

pt = 4145535f4145535f4145535f41455321
ct = edb43249be0d7a4620b9b876315eb430
enc_flag = e5218894e05e14eb7cc27dc2aeed10245bfa4426489125a55e82a3d81a15d18afd152d6c51a7024f05e15e1527afa84b

解法

全探索しようとしても、(14^3)^4 = 2,744^4 = 56,693,912,375,296 通りで終わらない。（マシンパワーで7時間かけて解いた人はいたが）

4回の暗号化の結果を比較するのは大変だが、2回の暗号化と2回の復号の結果を照らし合わせることで、ループを減らすことができる。
k1, k2での暗号化 → 2,744^2 = 7,529,536 通り
k3, k4での復号 → 2,744^2 = 7,529,536 通り

Meet-in-the-Middle Attackという攻撃手法らしい。

参考：他の人のwriteup

これと自分が途中まで書いていたものを組み合わせてコードを書きました。
1つ目のfor文の間に p1 = AES.new(k1, AES.MODE_ECB).encrypt(pt) を挟むことによって、毎回AESやらずに済むので少しは速くなっているはず。

from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from itertools import product

pt = bytes.fromhex('4145535f4145535f4145535f41455321')
ct = bytes.fromhex('edb43249be0d7a4620b9b876315eb430')
enc_flag = bytes.fromhex('e5218894e05e14eb7cc27dc2aeed10245bfa4426489125a55e82a3d81a15d18afd152d6c51a7024f05e15e1527afa84b')

chars = b'crew_AES*4=$!?'
L = 3
possible_keys = [bytes(p) for p in product(chars, repeat=L)]

def meet_in_the_middle_attack(pt, ct, possible_keys):
    encrypt_dict = {}
    decrypt_dict = {}

    total_keys = len(possible_keys)
    
    print("Start Encryption Phase...")
    count = 0
    for w in possible_keys:
        k1 = sha256(w).digest()
        p1 = AES.new(k1, AES.MODE_ECB).encrypt(pt)
        for x in possible_keys:
            k2 = sha256(x).digest()
            p2 = AES.new(k2, AES.MODE_ECB).encrypt(p1)
            encrypt_dict[p2] = (w, x)

            count += 1
            if count % 10000 == 0:
                print(f"Encryption Phase: {count}/{total_keys**2}")

    print("Start Decryption Phase...")
    count = 0
    for z in possible_keys:
        k4 = sha256(z).digest()
        c4 = AES.new(k4, AES.MODE_ECB).decrypt(ct)
        for y in possible_keys:
            k3 = sha256(y).digest()
            c3 = AES.new(k3, AES.MODE_ECB).decrypt(c4)
            decrypt_dict[c3] = (y, z)

            count += 1
            if count % 10000 == 0:
                print(f"Decryption Phase: {count}/{total_keys**2}")
    
    print("Find matching values...")
    for v in encrypt_dict:
        if v in decrypt_dict:
            w, x = encrypt_dict[v]
            y, z = decrypt_dict[v]
            return w, x, y, z
        
    return None, None, None, None

w, x, y, z = meet_in_the_middle_attack(pt, ct, possible_keys)

if w is not None:
    key = sha256(w + x + y + z).digest()
    flag = unpad(AES.new(key, AES.MODE_ECB).decrypt(enc_flag), AES.block_size)
    print(flag.decode())
else:
    print('Not found')

crew{m1tm_at74cK_1s_g0lD_4nd_py7h0n_i5_sl0w!!}

Read between the lines (crypto)

問題

flag.txtのi番目の文字のbyteとしての値個分i+0x1337という値を追加したencoded_flag というリストがある。
それに対して、sum(pow(m, e, n) for m in encoded_flag) % n を計算した結果が与えられる。

#!/usr/bin/env python3

from random import shuffle
from Crypto.Util.number import getPrime


with open('flag.txt', 'rb') as f:
    FLAG = f.read().strip()

assert len(FLAG) < 100

encoded_flag = []

for i, b in enumerate(FLAG):
    encoded_flag.extend([i + 0x1337] * b)

shuffle(encoded_flag)

e = 65537
p, q = getPrime(1024), getPrime(1024)
n = p * q
c = sum(pow(m, e, n) for m in encoded_flag) % n

with open('output.txt', 'w') as f:
    f.write(f'{n = }\n{e = }\n{c = }\n')

n = 11570808501273498927205104472079357777144397783547577003261915477370622451850206651910891120280656785986131452685491947610185604965099812695724757402859475642728712507339243719470339385360489167163917896790337311025010411472770004154699635694228288241644459059047022175803135613130088955955784304814651652968093606122165353931816218399854348992145474578604378450397120697338449008564443654507099674564425806985914764451503302534957447420607432031160777343573246284259196721263134079273058943290282037058625166146116257062155250082518648908934265839606175181213963034023613042840174068936799861096078962793675747202733
e = 65537
c = 7173375037180308812692773050925111800516611450262181376565814072240874778848184114081029784942289615261118103256642605595499455054072839201835361613983341298973366881719999836078559255521052298848572778824157749016705221745378832156499718149327219324078487796923208917482260462508048311400560933782289383624341257636666638574026084246212442527379161504510054689077339758167386002420794571246577662116285770044542212097174474572856621921237686119958817024794843805169504594110217925148205714768001753113572920225449523882995273988088672624172009740852821725803438069557080740459068347366098974487213070886509931010623

解法

a[i] = pow(i + 0x1337, e, n)
b[i] = FLAG[i]
として、以下になるようなb(0<b<128)を解ければいいのかなって思いついたものの、それを実装する力がなかった。

a_0 b_0 + a_1 b_1 + a_2 b_2 + ... + k n -c = 0

作者の解説

方針はあっていて、LLLのアルゴリズムを使って、ノルムが小さい解を求めることができる。
これにより、(0<b<128)という制約を満たせるらしい。

この問題では、Matrixは以下のようになる。

\begin{pmatrix} (0 + \mathtt{0x1337})^e & (1 + \mathtt{0x1337})^e & \dots & (N - 1 + \mathtt{0x1337})^e & n & -c \\ 1 & 0 & \dots & 0 & 0 & 0 \\ 0 & 1 & \dots & 0 & 0 & 0 \\ \vdots & & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & 0 & 0 \\ 0 & 0 & \dots & 0 & 1 & 0 \\ 0 & 0 & \dots & 0 & 0 & R \\ \end{pmatrix} \cdot \begin{pmatrix} b_0 \\ b_1 \\ \vdots \\ b_{N - 1} \\ k \\ 1 \\ \end{pmatrix} = \begin{pmatrix} 0 \\ b_0 \\ b_1 \\ \vdots \\ b_{N - 1} \\ k \\ R \\ \end{pmatrix}

SageMathをpythonから使うことで、以下のようにシンプルに解くことができる。(作者の解説より引用)

from sage.all import Matrix

with open('output.txt') as f:
    exec(f.read())

N = 100
cts = [pow(m + 0x1337, e, n) for m in range(N)]

R = 2 ** 1024
M = Matrix([
    [*cts, n, -c],
    *[[0] * i + [1] + [0] * (len(cts) - i + 1) for i in range(len(cts))],
    [0] * len(cts) + [0, R]
])

L = M.T.LLL()
assert L[-1][0] == 0 and L[-1][-1] == R
res = L[-1][1:-1]

print(L[-1])

flag = [v for v in res if v != 0]
print(bytes(flag).decode())

crew{D1d_y0u_3xp3cT_LLL_t0_b3_h1Dd3n_b3tw3en_th3_l1n3s???}

ちなみに、解L[-1]は以下のようになるが、k = 0なの？

(0, 99, 114, 101, 119, 123, 68, 49, 100, 95, 121, 48, 117, 95, 51, 120, 112, 51, 99, 84, 95, 76, 76, 76, 95, 116, 48, 95, 98, 51, 95, 104, 49, 68, 100, 51, 110, 95, 98, 51, 116, 119, 51, 101, 110, 95, 116, 104, 51, 95, 108, 49, 110, 51, 115, 63, 63, 63, 125, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216)

おわりに

チーム「脆弱エンジニア(full_weak_engineer)」では、SECCON CTF決勝進出を目指してCTFに参加しています！

チームでCTFをやりたいメンバーを常に募集していますので、YouTubeの概要欄にあるDiscordリンクから、気軽にご参加ください！

Pwn担当大歓迎（切実）（定期）

チームメンバーのWriteup

振り返り

4ES (crypto)

問題

解法

Read between the lines (crypto)

問題

解法

おわりに

Discussion