DEF CON CTF Qualifier 2019(redacted-puzzle)

こんにちは。今年のDEFCON Qualifierのwriteupです。CTF初心者の方にも参考にしてもらえるよう、試行錯誤した過程も含めて記事にしてみました。

DEF CON当日、若干遅れて会社に到着した私は、pwnは若者達に任せて、年配者(?)でも何か出来そうな問題がないか探していたところ、redacted-puzzleという問題を見つけました。早速、与えられたgifファイルを開いてみます。

いかにも閃き系っぽい問題だと思ったので、コレにしようと心に誓いました。

gifファイルの解析

まずは、真っ黒な画像から何か情報を得たいです。お絵かきソフトで開いて、適当な色で塗りつぶししたり、ペイントしたりしますが、全く画像に変化がありません。パレットがおかしいのかな？ つぎに、画像をバイナリエディタで開きます。

仕様はGIF89a。もう少し中身を見ていきます。

GIF Headerの後に、Application Extension(赤枠21FF)があり、Graphic Control Extension(青枠21F9)とImage Block(緑枠2C)が交互に連続している。間違いなく、GIFアニメーションのファイルと確信し、Image Blockの数から35フレームあると分かる。パレットが怪しいので、GIF HeaderのGlobal Color Tableに該当するバイナリを適当な値でいじってみる。

保存して画像を開いてみると。。。下記のような中央の図形が素早く変化するアニメーションが画面に現れた。

アニメーションを眺めていると、中央の図は、8角形の幾つかの頂点を結んだ多角形、または2つの頂点を結ぶ線、または特定の1つの頂点であることがわかった。図形は全部で35枚ある。さらに、画像下部には、FLAG ALPHABETとかいう、いかにもな32文字。CTFに携わる人なら、全員がピンとくるであろう、8角形の頂点を8bitのゼロイチに置き換えてみることにします。GIFアニメを見て置き換えるのは大変なので、画像処理ソフトでレイヤ分割して、目測でゼロイチに置き換えます。ちなみに、画像は、1フレーム毎にわずかに左に回転しているので、注意が必要です。

各フレームの図形の頂点をゼロイチに置き換えて、（いまや私の業務上のメインツールになりつつある）エクセルでまとめたものがこちら。

試されるエスパー力

各フレームをbit列にする際、どの頂点を最初にするかでbitの並びが変わるので、8通りのパターンがある（正確には回転方向を考慮すると16通り）という、気持ち悪さを感じつつも、とりあえず、1フレーム目の図形の左上を頂点0として、時計回りに並べてみた。ここまで来たら、FLAG ALPHABETと紐づけて、法則を見つけてフラグを導けば終わり。楽勝！と、思っていました。しかし、ここから何時間も泥沼にハマる事になるのです。。。。

16進数にしたり、アスキーコードに変換したり色々試してみる。2時間ほど格闘したけれど、糸口すら見つけられない。

こういう時は、発想を切り替えることが定石です。問題タイトルに「puzzle」とあるとおり、これは、幾つかのフレームを組みあわせて8角形を作る（正確には8つの頂点をすべて1にする）パズルなのではないか？と思いつきます。例えば、上の図のオレンジ色で示した３つのフレームは、ビット毎に足し算するといずれの頂点も1が1つだけ存在する組み合わせです。この組み合わせを全て洗い出せば、何か糸口がつかめるかもしれません。これなら、前述の8パターンの全てで同じ結果になるので、bit列を開始する頂点の位置や、回転方向にとらわれること無く、気持ち悪さも払しょく出来ます。フラグへの匂いがします。机上でこの組み合わせを探すのは大変なので、pythonで適当にコードを組みました。

text["10001100","01100011","11100100","01000110","10000101","00111101","01000010","10011000","11100000","11110100","10000000","00101101","01110010","00011100","00001000","10100101","11010111","01101110","10100110","10010001","10111100","10000100","10000001","10111001","11010100","00111011","11001110","11110010","00011110","10011101","11001001","11000111","01100101","00011110","10011111"]
m_list = []
#3つの図形を組み合わせて全ての頂点が1となる組み合わせを探す
#ただし、各頂点は、いずれかの図形のうち1つだけが1であり、残りは0であること
for b in range(35):
    for c in range(35):
        for d in range(35):
            kain = bin(int(text[b],2) ^ int(text[c],2) ^ int(text[d],2))
            if kain == bin(0b11111111):
                chk = int(text[b],2) & int(text[c],2) & int(text[d],2)
                if chk == 0:
                    print("11111111 Matched!! b={}, c={}, d={} ".format(b,c,d))
                    tmp_list = [b,c,d]
                    tmp_list.sort()
                    m_list.append(tmp_list)
ans_list = set(list(map(tuple,m_list))) #重複は排除したリスト内タプルを再生成
print("Answer = {}".format(ans_list))

結果は、(1,10,13)フレーム、(4,12,14)フレーム、(5,6,10)フレームの組み合わせの3通りしかありませんでした。このたった３通りから、フラグをどうやって導くのか？直観的にこの解法は違うと思いました。

その後、当初の誓いを破り他の問題に浮気をしつつ、やっぱりこの問題が忘れられずに戻ってくるという状況が数時間続きました。大会も終盤に差し掛かりました。ファーストカテゴリ？のそれぞれの問題の正解チーム数を見ると、redacted-puzzleは比較的正解チーム数が少ないようで、実はこの問題は単純ではなく、私の凝り固まった脳では解けないのではないか？とネガティブ思考になりつつあります。。。。

やっと見つけた

フラグの形式は、OOO{xxx......xxxx}と開示されています。ということは、最初の3文字は同じ文字で、4文字目に異なる文字が出現するパターンがどこかにあるはずです。FLAG ALPHABETは32文字です。つまり5bitです。1フレーム1文字とするならば、5bitの文字を表す列と、3bitの何らかの制御を表す列に分かれているのではないか？と仮定してみます。仮に制御を表す3bitがフラグ文字の順序を表すのであれば、一見、ランダムに見えるbit列の中に、同じ文字3つが連続するパターンが見いだせるのではないか、と思いました。そこで、ためしに、頂点0を先頭とする1フレームの最初の5bitを赤枠で囲ってみると...

あ!!! 3つの連続する文字が見えました。どうやら私の仮定は外れましたが、結果が出せれば良いんです。皆さんには見えましたか？（ぜひ、この点だけは、ご自身の目で見つけてみて下さい）ちなみに、フラグの最後の文字は必ず"}"(FLAG ALPHABETでは31番目つまり"11111")ですので、すかさず、35フレーム目の最後に目をやると...

勝利を確信すると同時に、たまたま頂点0を先頭に持ってきたラッキーを噛み締めます。頂点0がbit列の先頭であることは明白でしたが、一応、8パターンの全てで、5bitずつに区切り、FLAG ALPHABETに変換するコードを書くと...

text = ["10001100","01100011","11100100","01000110","10000101","00111101","01000010","10011000","11100000","11110100","10000000","00101101","01110010","00011100","00001000","10100101","11010111","01101110","10100110","10010001","10111100","10000100","10000001","10111001","11010100","00111011","11001110","11110010","00011110","10011101","11001001","11000111","01100101","00011110","10011111"]
table = "+-=ABCDEFGHIJKLMNOPQRSTUVWXYZ_{}"
rot_text = [[0]*35 for i in range(35)]
BITCNT = 8 #8角形
#ローテートシフト関数
def rol(n):
    tmp = ""
    for i in range(BITCNT):
        if BITCNT-1 == i:
            tmp = tmp + n[0]
        else:
            tmp = tmp + n[i+1]
    return tmp
#ローテートシフトした８パターンの組を生成
for m in range(0,8):
    k = 0
    if 0 == m: #rot_text[0]はtextそのまま
        for k in range(35):
            rot_text[0][k] = text[k]
    else:  #rot_text[1]以降は1bitずつローテートシフトして生成
        for k in range(35):
            rot_text[m][k] = rol(rot_text[m-1][k])
for i in range(BITCNT):
    print("頂点{}: {}".format(i,rot_text[i]))
print("\n")
#繋げたbitを5bit毎に分割してtableに一致する文字に変換して結合
for n in range(BITCNT):
    bit_str = ""
    ans = ""
    cnt = 0
    for l in range(35):
        bit_str = bit_str + rot_text[n][l]
    for i in range(56):
        tmp = bit_str[cnt:cnt+5]
        ans = ans + table[int(tmp,2)]
        cnt=cnt+5
    print("頂点{}: {}".format(n,ans))

結果はこのようになりました。

頂点0: OOO{FORCES-GOVERN+TUBE+FRUITGROUP=FALLREMEMBERWEATHER}
頂点1: AEAJQA+IMH=AANMG+CKLFL+NGLUVQGAMBBNDZGLXL{HM-YPLEZRM-}
頂点2: DHDWDDFT{NBTC+{Q+HXJPZ-+PWMYQDPD{FG+KWPQNZT{ATBZMWH{A{
頂点3: JNKPLJOJBGJF-E+ORWEV=+CT}EDKJJZRP+WQKDYCYGMZEJGV}=UZEZ
頂点4: W+YBZW=VXJPFPAPM-AG=MNJ+IG{{JXNWWKB-ODXKTMT=}VLWQO{CKVMW
頂点5: PCTGWPCNRB-DEB{==PR+V-TQJYS-PP{FA+KZXJ}JSNQEEZHWN}Q
頂点6: BMJAQBI-G{F=JL-B-CWV-V=KEXWUHIBCZNT+YOSWXWYW-YELIVSQ-}E
頂点7: FXVUBF{=QVNRVZAXF=IAPANBXISQLR{FIW-J-UAHQSQUPA{LZQOYBA{M

やはり頂点0からで正解のようです。これ、bit列の開始を頂点0以外で考えた人は、かなり辛い戦いだったんじゃないかな（いきなり余裕を見せ始める）、と思いつつ、フラグを入力して得点をGET。slack上で仲間たちからの拍手が嬉しかったです。