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 というシンボルがつくのかな？
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は.rodataの0x49f775に入っているので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")
やっと deedeedee 解けた〜いえ〜い pic.twitter.com/0Qxib1Z9CF
— 友利奈緒ちゃん (@K_atc) September 19, 2016
真面目に解いてる．偉い． https://t.co/fqW7rl1tCu
— ふるかわ (@_N4NU_) September 19, 2016
flag: flag{t3mplat3_met4pr0gramming_is_gr8_4_3very0n3}
結局cが偶数なら正解のflagになるみたいですが、なぜなんでしょう？
あ゛〜〜〜〜
本番で解いていなかった問題を眺めていたら、deedeedeeのかなり不真面目な解き方を思いついてしまった……。
— Bono (@Bono_iPad) 2016年9月19日
deedeedee:
0x44e445でブレークして、0x44cde0にjumpすると、stack上にflagが……。
雑感
githubの方にsuggested pointsが300-400と書いてあって、実際は150点はマジすか。鬼畜ですか…
コンパイル時計算したときに、計算結果は .rodata に入りそう、
誰にも呼ばれないはずの関数（今回はencrypt()は誰にも呼ばれていなかった）がバイナリに残る、という知見らしきものを得ました。
コンパイル時計算はRevのネタとして結構面白いですね。
なんか低得点問題でさえとっつきにくいCTFでしたね。来年は…う〜ん
