読者です 読者をやめる 読者になる 読者になる

ヾノ*>ㅅ<)ノシ帳

技術ブログに見せかけて、ジャンル制限のないふりーだむなブログです。

CSAW CTF 2016 Quals - deedeedee (Rev150) writeup

2016/10/17〜18の2日間開催されたCSAW CTF 16 Qualsに参加しました。 結果はやる気を疑われるレベルの点数でしたが、本番が終わった今日はinterestingな問題を解き直していました。 今回は執筆時点で運営以外のwriteupが上がってない deedeedee (Reversing 150 pts.) という問題のWriteupを書きます。

おことわり:僕はD言語もconstexprもよく知りません。基本feelingで読みました><

問題

Wow! I can run code at compile time! That's a pretty cool way to keep my flags secret. Hopefully I didn't leave any clues behind...

配布ファイルなど

Your hexencoded, encrypted flag is: 676c60677a74326d716c6074325f6c6575347172316773616c6d686e665f68735e6773385e345e3377657379316e327d
I generated it at compile time. :)
Can you decrypt it for me?

第一印象

  • ユーザー入力の余地がない
    • angrとかの出番はまず無さそう
  • flagがバイナリに無く、encryptはコンパイル時計算によるもの
    • よく見るとencryptされた文字列っぽいものはある(当然)
  • コンパイル時計算といえはc++
    • 実際はD言語のtempleteとかmixin

→無理ゲーでは?

方針

CTFの問題は、ブルートフォースが必要だとしても、必ず開催期間内に解けるようになっているので、 ちゃんとバイナリを読んだ上で負いきれない部分をブルートフォースするようにしますかね。 enrypt()がどのようにされたのかというヒントがバイナリに残っていないと解けないと思うので、 バイナリに残っている関数を丁寧に見たほうが良さそうです。

あと、最初はc++で書かれてるのかな(例のconstexpr?)と思いましたが、運営のgitリポジトリを見る限りD言語で書かれてますねソースコードと思考過程が全く辿れないwriteupが公開されてるので解析の手がかりに使いたいと思います。

以下、readelf -hです。

% reedelf -h deedeedee
ELF ヘッダ:
  マジック:  7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 
  クラス:                            ELF64
  データ:                            2 の補数、リトルエンディアン
  バージョン:                        1 (current)
  OS/ABI:                            UNIX - System V
  ABI バージョン:                    0
  型:                                EXEC (実行可能ファイル)
  マシン:                            Advanced Micro Devices X86-64
  バージョン:                        0x1
  エントリポイントアドレス:          0x44ccf0
  プログラムの開始ヘッダ:            64 (バイト)
  セクションヘッダ始点:              850408 (バイト)
  フラグ:                            0x0
  このヘッダのサイズ:                64 (バイト)
  プログラムヘッダサイズ:            56 (バイト)
  プログラムヘッダ数:                10
  セクションヘッダ:                  64 (バイト)
  セクションヘッダサイズ:            34
  セクションヘッダ文字列表索引:      31

はい、x86_64〜😇

解析ヾノ*>ㅅ<)ノシ

IDA Proを持っているほど強いチームでもないし、かと言ってobjdump+Sublime Text+readelf+grepでは太刀打ちできる量ではないです。 仕方ないので、今日Hopper v3を買いました。 そこそこいい線いってるデコンパイラが付いてます(実は数日前からデモ版で試していました)。 アセンブリの画面では引数を格納している命令の横にそうと分かるようなコメントがつくのもいい感じです。

(割と丁寧に書きます。あと、割とreadelfをゴリ押しします)

main関数は、Your hexencoded, encrypted flag is が出る関数を探せばいいです。 今回は Dmain というラベルがついていました。
(解いた後にスクショを撮ったので、書き込みがある点はご了承くだされ)
# 一般にD言語のmain関数には _Dmain というシンボルがつくのかな?

f:id:katc:20160919234323p:plain

Dmainにはマングルされたザ可読性ゼロを体現したかのような関数がありました。 そのような関数はどんどんオレオレデマングルしていきました。
# deedeedee.d を持っているので、ある程度自信を持ってできました><

% readelf -s deedeedee| egrep "(hexencode|writeln)"
   264: 000000000044e370   148 FUNC    GLOBAL DEFAULT   13 _D9deedeedee9hexencodeFAy
  2544: 00000000004734e8   227 FUNC    WEAK   DEFAULT   13 _D3std5stdio16__T7writeln
  3012: 0000000000472f78   161 FUNC    WEAK   DEFAULT   13 _D3std5stdio20__T7writeln
  2442: 000000000044e370   148 FUNC    GLOBAL DEFAULT   13 _D9deedeedee9hexencodeFAy
  4240: 0000000000472f78   161 FUNC    WEAK   DEFAULT   13 _D3std5stdio20__T7writeln
  5269: 00000000004734e8   227 FUNC    WEAK   DEFAULT   13 _D3std5stdio16__T7writeln

Your なんちゃらが表示された直後にHEXエンコードされたencrypted flagが表示されます。 hexencodeと名づけた関数の返り値がそれのようなので、hexencodeの中身を追っていきます。

000000000044e439         mov        rdi, qword [ds:rdx+rbx]                     ; argument "length" for method hexencode
000000000044e43d         mov        rdx, qword [ds:rdx+rbx+8]                   ; set flag to $rdx
000000000044e442         mov        rsi, rdx                                    ; argument "flag" for method hexencode
000000000044e445         call       hexencode

…結果を先に言うと、encrypted flagは.rodata0x49f775に入っているのでhexencodeを見る価値は無いです。
コンパイル時計算したって問題が言ってるんですから仕方ないですね。

                     byte_format:
000000000049f770         db         "%02x", 0                                   ; XREF=hexencode+89
000000000049f775         db         "gl`gzt2mql`t2_leu4qr1gsalmhnf_hs^gs8^4^3wesy1n2}", 0
                     _TMP2:
000000000049f7a6         db         "Your hexencoded, encrypted flag is: ", 0   ; XREF=_Dmain+12
                     _TMP3:
000000000049f7cb         db         "I generated it at compile time. :)", 0     ; XREF=_Dmain+85
                     _TMP4:
000000000049f7ee         db         "Can you decrypt it for me?", 0             ; XREF=_Dmain+103
                     _TMP11:

ここでチートで、deedeedee.dを見て、encrypt()とそれの呼び出し先がバイナリに残っているとflagを求められると考えます。 安全策でreadelfで先にencryptを探します。

% readelf -s deedeedee| egrep "encrypt"
   847: 000000000044cde0  5515 FUNC    GLOBAL DEFAULT   13 _D9deedeedee7encryptFNaNf
  3527: 000000000044cde0  5515 FUNC    GLOBAL DEFAULT   13 _D9deedeedee7encryptFNaNf

次は、Hopperで見てみます。

000000000044cde1         mov        rbp, rsp
000000000044cde4         sub        rsp, 0x10
000000000044cde8         mov        qword [ss:rbp+var_10], rdi                  ; arg2
000000000044cdec         mov        qword [ss:rbp+var_8], rsi                   ; arg1
000000000044cdf0         mov        rdx, qword [ss:rbp+var_8]                   ; argument "s" for method _D9deedeedee21__T3encVAyaa3_313131Z3encFNaNfAyaZAya
000000000044cdf4         mov        rax, qword [ss:rbp+var_10]
000000000044cdf8         mov        rdi, rax                                    ; argument "key" for method _D9deedeedee21__T3encVAyaa3_313131Z3encFNaNfAyaZAya
000000000044cdfb         mov        rsi, rdx                                    ; argument #2 for method _D9deedeedee21__T3encVAyaa3_313131Z3encFNaNfAyaZAya
000000000044cdfe         call       _D9deedeedee21__T3encVAyaa3_313131Z3encFNaNfAyaZAya
000000000044ce03         mov        rdi, rax                                    ; argument #1 for method _D9deedeedee21__T3encVAyaa3_323232Z3encFNaNfAyaZAya
000000000044ce06         mov        rsi, rdx                                    ; argument #2 for method _D9deedeedee21__T3encVAyaa3_323232Z3encFNaNfAyaZAya
000000000044ce09         call       _D9deedeedee21__T3encVAyaa3_323232Z3encFNaNfAyaZAya
000000000044ce0e         mov        rdi, rax                                    ; argument #1 for method _D9deedeedee21__T3encVAyaa3_333333Z3encFNaNfAyaZAya
000000000044ce11         mov        rsi, rdx                                    ; argument #2 for method _D9deedeedee21__T3encVAyaa3_333333Z3encFNaNfAyaZAya
000000000044ce14         call       _D9deedeedee21__T3encVAyaa3_333333Z3encFNaNfAyaZAya
000000000044ce19         mov        rdi, rax                                    ; argument #1 for method _D9deedeedee21__T3encVAyaa3_343434Z3encFNaNfAyaZAya
000000000044ce1c         mov        rsi, rdx                                    ; argument #2 for method _D9deedeedee21__T3encVAyaa3_343434Z3encFNaNfAyaZAya
000000000044ce1f         call       _D9deedeedee21__T3encVAyaa3_343434Z3encFNaNfAyaZAya
000000000044ce24         mov        rdi, rax                                    ; argument #1 for method _D9deedeedee21__T3encVAyaa3_353535Z3encFNaNfAyaZAya
000000000044ce27         mov        rsi, rdx                                    ; argument #2 for method _D9deedeedee21__T3encVAyaa3_353535Z3encFNaNfAyaZAya
000000000044ce2a         call       _D9deedeedee21__T3encVAyaa3_353535Z3encFNaNfAyaZAya
000000000044ce2f         mov        rdi, rax                                    ; argument #1 for method _D9deedeedee21__T3encVAyaa3_363636Z3encFNaNfAyaZAya
000000000044ce32         mov        rsi, rdx                                    ; argument #2 for method _D9deedeedee21__T3encVAyaa3_363636Z3encFNaNfAyaZAya
000000000044ce35         call       _D9deedeedee21__T3encVAyaa3_363636Z3encFNaNfAyaZAya
... snipped ...

名前がよく似ている関数をやたら呼び出しています(grepでカウントしてみたら400回callしてました←なぜ500回じゃない?)。 callの前にしていることはどれも同じです。 コンパイル時にforループ的なものが展開されたと考えればいいのでしょうか。 そうであれば最初の2つの関数の中身を見れば何をしているかを掴めそうです。

アセンブリを見てもキツイのでここでデコンパイラの出番です。 コメントは簡単に書き下したものです。合っているかは知りません。

function _D9deedeedee21__T3encVAyaa3_313131Z3encFNaNfAyaZAya {
    var_A8 = rbx;
    var_A0 = _D3std4conv9__T2toTiZ9__T2toTmZ2toFNaNfmZi(var_A8); // c (constant value)
    rax = cycle(var_40, 0x3, 0x49fa5c);             // var_40 = cycle(str(0x00313131)) (?)
    cycle_zip(var_80, arg0, arg1);                  // var_80 = (cycle(str(0x313131))).zip(s2)
    do {
            rax = Cycle_empty(var_80);              // checks if cycle returns empty
            rax = rax ^ 0x1;
            COND = rax == 0x0;
            if (COND) {
                break;
            }
            rax = Cycle_front(var_80);              // rax := (a, b)     
            _d_arrayappendcd(0x0, *(int32_t *)rax ^ *(int32_t *)(rax + 0x4) ^ var_A0 & 0xff);
                                                    // enc = a ^ b ^ c; encoded.push(enc)
            Cycle_popFront(var_80); 
    } while (true);
    rax = 0x0;
    return rax;                                     // return encoded
}

function _D9deedeedee21__T3encVAyaa3_323232Z3encFNaNfAyaZAya {
    var_A8 = rbx;
    var_A0 = _D3std4conv9__T2toTiZ9__T2toTmZ2toFNaNfmZi(var_A8); // c (constant value)
    rax = cycle(var_40, 0x3, 0x49fce2);
    cycle_zip(var_80, arg0, arg1);
    do {
            rax = Cycle_empty(var_80);
            rax = rax ^ 0x1;
            COND = rax == 0x0;
            if (COND) {
                break;
            }
            rax = Cycle_front(var_80);
            _d_arrayappendcd(0x0, *(int32_t *)rax ^ *(int32_t *)(rax + 0x4) ^ var_A0 & 0xff);
            Cycle_popFront(var_80);
    } while (true);
    rax = 0x0;
    return rax;
}

pythonのitertoolsにもあるcycle()が出てきてるっぽいです。 暗号方面ではよく見かける書き方です。今回の場合は、flagとそれよりも短いkeyを1文字ずつxorしているように見えます。 それぞれの関数でのkeyが何であるかは .rodata を見ればすぐに分かります。法則も自明ですね。

                     _TMP75:
000000000049fa5c         dd         0x00313131  # "111", 0
... snipped ...
                     _TMP214:
000000000049fce2         dd         0x00323232  # "222", 0
                     _TMP217:
000000000049fce6         dd         0x00333333  # "333", 0
                     _TMP220:
000000000049fcea         dd         0x00343434  # "444", 0
                     _TMP223:
000000000049fcee         dd         0x00353535  # "555", 0
                     _TMP226:
000000000049fcf2         dd         0x00363636  # "666", 0
                     _TMP229:
000000000049fcf6         dd         0x00373737  # "777", 0
                     _TMP232:
000000000049fcfa         dd         0x00383838  # "888", 0
                     _TMP235:
000000000049fcfe         dd         0x00393939  # "999", 0
                     _TMP238:
000000000049fd02         db         "101010", 0  
                     _TMP241:
000000000049fd09         db         "111111", 0  
                     _TMP244:
000000000049fd10         db         "121212", 0  
                     _TMP247:
000000000049fd17         db         "131313", 0  
                     _TMP250:
000000000049fd1e         db         "141414", 0  
                     _TMP253:
... snipped ...
                     _TMP1705:
00000000004a0f0e         db         "499499499", 0  

var_A0 = _D3std4conv9__T2toTiZ9__T2toTmZ2toFNaNfmZi(var_A8); が分かりそうにないし、 0x0から0xffに収まるのは自明なのでここはブルートフォースとします。 全体で500回(?)の暗号化処理の1つ1つは次のような処理をしていると分かりました。
# a, b, c が key. flag, ??? のどれに対応するのか問題は xor の性質で排除できます。テキトーでも大丈夫そうです。

keys = [str(k) * 3 for i in range(500)]
encrypted = "gl`gzt2mql`t2_leu4qr1gsalmhnf_hs^gs8^4^3wesy1n2}"
decrypted = encrypted
for key in keys:
    c = ??? (blute-force)
    tmp = ""
    for a, b in zip(cycle(key), decrypted):
        dec = chr(ord(a) ^ ord(b) ^ ord(c))
        tmp += dec
    decrypted = tmp
return decrypted

solve.pyを書くのに十分な情報が集まりました。やったね!

solve.pyとflag

from itertools import *

"""
% ./deedeedee
Your hexencoded, encrypted flag is: 676c60677a74326d716c6074325f6c6575347172316773616c6d686e665f68735e6773385e345e3377657379316e327d
I generated it at compile time. :)
Can you decrypt it for me?
"""

keys = [str(i) * 3 for i in range(500)]
encrypted = "676c60677a74326d716c6074325f6c6575347172316773616c6d686e665f68735e6773385e345e3377657379316e327d".decode("hex")
# encrypted = "gl`gzt2mql`t2_leu4qr1gsalmhnf_hs^gs8^4^3wesy1n2}" # good known
decrypted = encrypted
for c in range(256):
    for key in keys:
        # c = ??? (blute-force)
        tmp = ""
        for a, b in zip(cycle(key), decrypted):
            dec = chr(ord(a) ^ ord(b) ^ c)
            tmp += dec
        decrypted = tmp
    if decrypted[0:5] == "flag{":
        print("0x%2x: %s" % (c, decrypted))
print("[+] brute forth done")

flag: flag{t3mplat3_met4pr0gramming_is_gr8_4_3very0n3}

結局cが偶数なら正解のflagになるみたいですが、なぜなんでしょう?

あ゛〜〜〜〜

雑感

githubの方にsuggested pointsが300-400と書いてあって、実際は150点はマジすか。鬼畜ですか…

コンパイル時計算したときに、計算結果は .rodata に入りそう、 誰にも呼ばれないはずの関数(今回はencrypt()は誰にも呼ばれていなかった)がバイナリに残る、という知見らしきものを得ました。 コンパイル時計算はRevのネタとして結構面白いですね。


なんか低得点問題でさえとっつきにくいCTFでしたね。来年は…う〜ん