HarekazeCTF 2019 writeup
大学のサークルでチームを組んで参加しました。
もはや毎度のことですが、難しすぎて全然解けません。
一応、cryptoの100点問題だけ解けはしたのですが、かなりゴリ押しだったのでちょっとアレです。正攻法を知りたい。
「正攻法じゃなくても頑張れば解けるんや!」ということで、総当たりとエスパーでflagをゲットするかなり強引なwriteupです。
## 追記 ##
作問者の方がリプで正攻法を教えてくれました。ありがとうございます。
作問者です。フラグが不適切でした…すいません。
— ゆうけむ (@ykm_kn) 2019年5月19日
正攻法ですが、実はただの行列計算なので逆行列を得ることが目的となります。(det(m2) != 0 なので逆行列が存在します。
長くなるのでスクショでまとめさせていただきました pic.twitter.com/CJTsL1Imbu
ONCE UPON A TIME [Crypto: 100]
問題文
Now!! Let the games begin!!
- problem.py
- result.txt
flagを暗号化するpythonのプログラムと、暗号化されたflagが入っているテキストファイルが渡されます。
writeup
何はともあれまずはファイルの中身を確認してみます。
Encrypted Flag: ea5929e97ef77806bb43ec303f304673de19f7e68eddc347f3373ee4c0b662bc37764f74cbb8bb9219e7b5dbc59ca4a42018
さっぱり分かりません。
problem.pyはこんな感じ。
kinokoやらtakenokoやら可愛らしい関数がありました。
私はぱっと見で流れを追うことを諦めて総当たりすることにしたのですが、この時点では何の手掛かりもなく、馬鹿正直に実行すると数十億通りもあるので絶対に終わりません。
ということで、まずは諸々の変数を出力することにしました。
結構重要な手掛かりだったのが、encrypt関数内のmk変数でした。
mkの中身はまぁ、暗号化されたflagです。mkはリストになっていて、暗号化されたflagが小分けにして入っています。
flagは10文字で1セットになっていました。
ea5929e97e f77806bb43 ec303f3046 73de19f7e6 8eddc347f3 373ee4c0b6 62bc37764f 74cbb8bb92 19e7b5dbc5 9ca4a42018
そしてflagの中身に色々な値をセットして試行した結果、result.txtの末尾にある「9ca4a42018」が「%%%%%」であることが判明しました。
この「%」はpad25関数によって生成されるもので、flagとして与えられた文字列の末尾に「%」が (flagの文字数) % 25 個付け加えられます。
この時点で、result.txt の文字数から察するに、flag長は26文字以上45文字以下であることが確定します。
また、末尾から2つ目のセットが「9ca4a42018」ではなく「19e7b5dbc5」となっていることから「%」以外の文字が含まれていることが分かります。
つまり、flag長が41文字以上45文字以下であることが確定します。
後の話ですが、flagの文字数は大して重要な情報ではありませんでした。
私の力ではこれぐらいの情報しか集められませんでしたが、チームメイトの意見を聞いたところ、encrypt関数内のg変数が1のときだけ正常な暗号文になるらしいとのことでした。
実際に確認してみると、確かにそのようでした。
以下は一番最初に総当たりしたときのデータで、長いやつがg=0、短いやつがg=1です。
aaaaa,0a0a0a0a0a1818181818ccccccccccececececece0e0e0e0e0 aaaab,40f4f5d122 aaaac,41f8fad427 aaaad,0a0a0a0a0d1818181818ccccccccd5ecececec03e0e0e0e0e3 aaaae,430509da31
g=1に固定したところ、次のようになりました。
aaaaa,3ff0f0ce1d aaaab,40f4f5d122 aaaac,41f8fad427 aaaad,420104d72c aaaae,430509da31
これはもう確定ですね。
次の段階として、総当たりする文字を絞るために、過去のHarekazeCTFのflagとしてあり得る文字を確認してみました。
まぁ、いっぱいありますよね。
0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ !_-?,.%
もはや諦め半分で、この文字たちで総当たりすることにします。
1時間くらい回して確認してみると、なんと2セット判明していました。
1ook_,73de19f7e6 3y3s_,ec303f3046
これをflagに当てはめてみると次のようになります。※ * は不明な文字
HarekazeCTF{**********3y3s_1ook_*************************}
ここからエスパータイムです。
「ググったら何か分かるんじゃね?」ということでチームメイトたちと期待しつつ検索してみると、「make your eyes look」という英文が多く見られました。
CTFにおけるflagでは英単語をそのまま使わずに数字や記号で当て字にすることが多いので、そのあたりを考慮しつつ手動で当てはめてみると、「y0ur_」がヒットしました。
HarekazeCTF{*****y0ur_3y3s_1ook_*************************}
さらに色々推測していると、後輩がgoogleのサジェストでボヘミアンラプソディではないかと教えてくれました。
これまでに判明した「your eyes look」にボヘミアンラプソディを合わせて検索してみると、もう確定でした。
Queenの”Bohemian Rhapsody”という曲の歌詞に以下の一文があります。
Open your eyes, look up to the skies and see
ここから総当たりする文字をかなり絞ることができます。
Ozyxwvutsrqponmlkjihgfedcba0123456789_%
総当たりの結果。
1ook_,73de19f7e6 3y3s_,ec303f3046 y0ur_,f77806bb43 up_t0,8eddc347f3 ski3s,62bc37764f s33%%,19e7b5dbc5 _th3_,373ee4c0b6 _4nd_,74cbb8bb92 Op3n_,ea5929e97e
これらを繋げます。
HarekazeCTF{Op3n_y0ur_3y3s_1ook_up_t0_th3_ski3s_4nd_s33%%}
末尾の%は文字数が足りないときに勝手に補われる文字なので、これを削除すればflagの完成です。
HarekazeCTF{Op3n_y0ur_3y3s_1ook_up_t0_th3_ski3s_4nd_s33}
プログラム
大会中に作成したプログラムを少し改造して、実行すると少しずつフラグが完成する気持ちの良いプログラムを載せておきます。
※30分ぐらい掛かります