🗂

Crew CTF 2024 Crypt writeup

2024/08/05に公開

CTF

tech

初writeup…ども…
なかなか書く機会がなかったのでお試しで書いてみます。

Crew CTF 2024にfull_weak_engineerで参加、結果19位でした！
メンバーさんが強かった！

では本題のwriteup。

4ES(Crypto)

#!/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

まず最初に上記のPythonファイルとoutput.txtファイルが渡される。
これを解きflagの入手を目指す。

生成AIを駆使し、単純に総当たりするプログラムを生成してもらう。

プログラムが動いた…！

しかしあまりにも時間がかかりすぎる。

そこで、問題の趣旨に従って効率よく復号するプログラムを生成するように誘導する。
誘導の結果、ある攻撃が有効であることが分かった。

(以下原文ママ)

分割統治法 (Meet-in-the-Middle Attack)
AESのように多段階の暗号化では、分割統治法（Meet-in-the-Middle Attack）を使うことで攻撃が効率化できる場合があります。この手法は、中間状態を探索することで鍵の探索空間を減少させます。

暗号化の前半と後半を分ける。
前半部分の暗号化結果を保存する。
後半部分の復号結果を保存する。
前半と後半の結果を比較する。

上記の攻撃を実装してもらったコードが以下である。
(なお実行時間が少しかかる＆CPU負荷が高めなので注意）

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

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

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

def encrypt_stage1(w, x):
    k1 = sha256(w).digest()
    k2 = sha256(x).digest()
    mid_pt = AES.new(k2, AES.MODE_ECB).encrypt(AES.new(k1, AES.MODE_ECB).encrypt(pt))
    return (mid_pt, w, x)

def decrypt_stage2(y, z):
    k3 = sha256(y).digest()
    k4 = sha256(z).digest()
    mid_ct = AES.new(k3, AES.MODE_ECB).decrypt(AES.new(k4, AES.MODE_ECB).decrypt(ct))
    return (mid_ct, y, z)

def find_matching_keys(stage1_results, stage2_results):
    stage1_dict = {res[0]: (res[1], res[2]) for res in stage1_results}
    stage2_dict = {res[0]: (res[1], res[2]) for res in stage2_results}

    for mid in stage1_dict:
        if mid in stage2_dict:
            w, x = stage1_dict[mid]
            y, z = stage2_dict[mid]
            key = sha256(w + x + y + z).digest()
            cipher = AES.new(key, AES.MODE_ECB)
            flag = unpad(cipher.decrypt(enc_flag), AES.block_size)
            return w, x, y, z, flag
    return None

if __name__ == "__main__":
    pool = mp.Pool(mp.cpu_count())

    # Stage 1: Encrypt first half
    stage1_args = [(bytes(w), bytes(x)) for w in product(chars, repeat=L) for x in product(chars, repeat=L)]
    stage1_results = pool.starmap(encrypt_stage1, stage1_args)

    # Stage 2: Decrypt second half
    stage2_args = [(bytes(y), bytes(z)) for y in product(chars, repeat=L) for z in product(chars, repeat=L)]
    stage2_results = pool.starmap(decrypt_stage2, stage2_args)

    pool.close()
    pool.join()

    # Find matching keys
    result = find_matching_keys(stage1_results, stage2_results)
    if result:
        w, x, y, z, flag = result
        print(f"Found matching w, x, y, z: {w.decode()}, {x.decode()}, {y.decode()}, {z.decode()}")
        print(f"Flag: {flag.decode()}")
    else:
        print("No matching keys found")

説明文は以下である(同様に原文ママ)

説明
Stage 1: 前半部分の暗号化を実行し、中間結果を保存します。encrypt_stage1関数は、wとxの組み合わせから中間結果を計算します。
Stage 2: 後半部分の復号を実行し、中間結果を保存します。decrypt_stage2関数は、yとzの組み合わせから中間結果を計算します。
find_matching_keys: Stage 1とStage 2の結果を比較し、一致する中間結果を持つ組み合わせを見つけます。その組み合わせから最終的な鍵を計算し、フラグを復号します。

生成されたPythonファイルを実行し、無事flagを入手した。
Flag: crew{m1tm_at74cK_1s_g0lD_4nd_py7h0n_i5_sl0w!!}
(↑なおpython is slow!!って言われてるからPython以外で解く想定の問題だったかもしれない)

welcome問等を除き、今回解けたのはこの問題のみである。
Pwnなども取り組んだが解けなかったので次回以降に期待したい(遠い目）

4ES(Crypto)

Discussion