CrewCTF 2024 Writeup

2024/08/03(~48h)に行われた海外のCTF大会にチームで出場しました。(Team Name: FCS_Zunndamons, User Name: HydrangeA)(順位: 121/575)

今回、cryptoメインで解答に挑戦しました. Crypto1問を解答できたため、その解答の軌跡を残せればと思います.

何かの参考になれば幸いです。

解答した問題

• (Crypto) 4ES

環境

• Windows 11 Home 22H2
• WSL2 Ubuntu 22.04

(Crypto) 4ES

AES is very robust, but let's quadruple its power!
dist.zip

dist内のファイルは以下の通りです.
4ES.py

#!/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()}')

output.txt

pt = 4145535f4145535f4145535f41455321
ct = edb43249be0d7a4620b9b876315eb430
enc_flag = e5218894e05e14eb7cc27dc2aeed10245bfa4426489125a55e82a3d81a15d18afd152d6c51a7024f05e15e1527afa84b

AES暗号(ブロック暗号)を用いてFlagを暗号化しているようです. AES暗号の秘密鍵は、変数charsを基に3文字分のランダムなバイト列(w,x,y,z)を4つ生成し、そのバイト列をすべて加算したものをsha256でハッシュしてdigestした値となっています。

AES暗号はブロック暗号であるため、共通鍵暗号となります。つまり暗号化に使われた鍵と同じものを推測できれば正しく復号することが可能になります。そのためまずは秘密鍵を求められるかに焦点を置くことが望ましいと考え、話を進めます。

秘密鍵の構成はsha256(w+x+y+z).digestであるため、構成要素w,x,y,zが分かれば求められます。w,x,y,zはbytes(choices(chars, k=L))であるため、charsに含まれる文字列から重複ありでL文字選んだものが与えられます。今回はL=3であるため、

$len(chars{)}^L={14}^3=2744$通りの文字列が考えられます。ここで、この組み合わせ数で総当たりできるかどうか考えてみます。

w,x,y,zそれぞれが2744通りの組み合わせをとりうるため、

${2744}^4=56693912375296$を全探索できれば解けます。ただし、コンテスト中に解き切ることは困難です。

唐突ですが、与えられた情報pt, ctがflagのAES暗号化に一切かかわっていないことにお気づきでしょうか(この情報を基に解けと言わんばかりの情報っぽい)。一度

$pt,ct$について見ていきましょう。

とある平文ptに対してAES暗号を4回適応した結果が暗号文ctとなっています。その暗号化に使われる秘密鍵はw,x,y,zをそれぞれsha256でハッシュした値k1,k2,k3,k4となっています。
この暗号化に関しても、w,x,y,zの組み合わせを総当たりすれば解けそうで、先ほど導出した

$56693912375296$通りを解く必要があるように感じます。
わざわざ濁しているので、結論を言うと工夫すれば総当たりの回数を減らすことができます。ではどうするか。

今回pt, ctが与えられており、AES暗号(ないし共通鍵暗号)の特徴から、同じ秘密鍵を用いれば元の平文に復号することが可能です(より具体的にはAES暗号内のdecrypt関数を動かします)。そのため、ptをk1,k2で暗号化した値と、ctをk4,k3で復号した値が合致することになります。この考えにより、それぞれの組み合わせ数は

${2744}^2=7529536$通りとなり、総当たり回数が大幅に削減されます。

この方針を採用した解答の手順は以下となります。

1. w,x,y,zがとりうる値の組み合わせをすべて列挙して配列に落とし込む
2. ptに対して、1で作成した配列から
   $k1,k2$を選びAES暗号化を行い、配列に落とし込む
3. ctに対して1で作成した配列から
   $k4,k3$を用いたAES復号を行い、2で作成した配列の中から合致する文が存在するかチェックする。
4. 存在した場合、2,3で用いられたk1,k2,k3,k4に対応するw,x,y,zを基にsha256(w+x+y+z).digestを計算し、flag_encに対してAES復号を行う

以上により、問題を解くことが出来ます。

補足1: 半分全列挙というアルゴリズム(テクニック?)があります。ぜひ検索してみてください。

crew{m1tm_at74cK_1s_g0lD_4nd_py7h0n_i5_sl0w!!}

感想

ブロック暗号の問題に慣れてきていることもあり、必要な思考と不要な思考を切り分けて考えながら解くことが出来たと感じています。また、著者が競技プログラミングをかじっていたこともあり、高速な計算をプログラミングに落とし込むことに抵抗が低かったことも(大きな)要因であったと思います。正直暗号っぽさのある問題では無かったようにも感じましたね...

まとめ

この大会以前にも何度か海外のCTF大会に参加していましたが、ことごとく惨敗してwriteupすらかけない状態が続いていました。特にRSAの問題が来るとめったに解けない。2番目に解かれていたCryptoの問題もRSA。今回も解けず。対してブロック暗号の正答率は割と高い。アルゴリズムに物言わせて数学ができないという悲しい現実。次こそはRSAの問題を解きたい！と強く思いました。
最後まで読んでいただきありがとうございました。