2019-12-22に開催されたSECCONの国際決勝に、hiww, h_noson, st98ともにHarekazeとして参加しました。(昨年は国内決勝に参加してました。)
お疲れ様でした。11位でした pic.twitter.com/lfESEQxZ3L
— h_noson (@h_noson) 2019年12月22日
順位はあまり振るわず、14チーム中11位でしたが、個人的には問題4の"box"のattackフラグを全部回収できたので大満足です。ということで、問題4の私なりの解き方についてまとめておきます。
"box"問題概要
今回は6つ大問がありましたが、そのうちの4問目でした。問題としては、stripされたx86バイナリと、それに特定の入力を与えた際の分岐トレース結果が配布されるので、同一の分岐トレースが得られるような入力をみつける、というものです。
……あれ？この話前にも聞いたことがありますね。そうです、今年の予選では、完全に同様の形式の問題(follow-me)が出されていたのでした。
ということで、あとはやるだけです。
Attackフラグとしては、box1から4と名付けられた4つの問題がダウンロードできるので、それを解いて入力をAPIに投げるとフラグが得られます。
Defenceフラグとしては、box1に類似した問題が1時間ごとに出され、それをその時間内に解いてAPIに投げるとチームのtokenを設置できるのですが、ちょっと厳しかったので諦めました（後述）。
では、box1から4まで順に見ていきましょう。
box1
入力形式の特定
とりあえず普通のLinuxバイナリなので実行してみます。
$ ./box usage: ./box formula
なるほど…式を引数で渡すんですね。
$ ./box '1+3' error: unhandled char '+'
うーん、だめですね。じゃああれかな、予選の時と同じ入力形式なのかな？
./box '1,3,+' error: unhandled char ','
違うみたい…。（ここから試行錯誤することしばらく。）
$ ./box '' error: stack is empty $ ./box '0' error: stack is empty $ ./box '00' error: stack is empty $ ./box '000' error: stack is empty $ ./box '0000' 0
あー…なるほど？（さらにしばらく試行錯誤して。）
$ ./box '00010002a' 3 $ ./box '00010002b' -1 $ ./box '00010002c' 2 $ ./box '00010002d' 1 $ ./box '00010002e' 2 $ ./box '00010002f' 5 $ ./box '00010002g' error: unhandled char 'g'
なるほど、演算子はa-fなんですね。（なぜアセンブリを読まないのか（つかれてたので））。
トレースをみてみる
$ cat box.trace
[
{"event": "image_load", "image_name": "***/box1", "image_id": 1, "base_addr": "0x557a93890000", "image_size": "0x135f"},
{"event": "image_load", "image_name": "/lib64/ld-linux-x86-64.so.2", "image_id": 2, "base_addr": "0x7fb95ac8c000", "image_size": "0x26c23"},
{"event": "image_load", "image_name": "[vdso]", "image_id": 3, "base_addr": "0x7ffc905a6000", "image_size": "0x100a"},
{"event": "image_load", "image_name": "/lib/x86_64-linux-gnu/libc.so.6", "image_id": 4, "base_addr": "0x7fb9464a4000", "image_size": "0x3f0adf"},
{"event": "branch", "inst_addr": "0x557a9389064e", "branch_taken": true},
{"event": "branch", "inst_addr": "0x557a93890ed4", "branch_taken": false},
{"event": "branch", "inst_addr": "0x557a938907f5", "branch_taken": true},
{"event": "branch", "inst_addr": "0x557a93890786", "branch_taken": true},
{"event": "branch", "inst_addr": "0x557a93890ef4", "branch_taken": false},
{"event": "branch", "inst_addr": "0x557a938906b0", "branch_taken": true},
{"event": "branch", "inst_addr": "0x557a93890690", "branch_taken": true},
{"event": "branch", "inst_addr": "0x557a93890e3f", "branch_taken": true},
{"event": "branch", "inst_addr": "0x557a938906c0", "branch_taken": true},
...
]
こんな感じでJSONが書かれています。 base_addrは最初の要素に書いてあるので、ちゃんとやるなら引き算をすれば、適当にするなら下4桁をとればファイル内のアドレスになりそうです。 というわけで、objdumpと照らし合わせればすべてわかりそう…でもせっかくトレーサーのソースも与えられているし、あとのことも考えるとトレーサーの環境を用意した方がよくない？という気持ちになったので用意することに。
トレーサーの環境構築
問題で配布されているファイルの中には、トレース出力を得るために使ったトレーサーのソースも含まれていました。なので、これを実行したいのですが、これはIntel Pinというライブラリに依存しているので、適当にPinのソースコードを落としてきてビルドします。そして、Pinを用いたサンプルコードのディレクトリに行って、サンプルのうちひとつをコピーし、それのソースとMakefileを書き換えて、トレーサーのライブラリファイルをビルドしました。
/path/to/pin/source/tools/branchtrace $ ls branchtrace.cpp branchtrace.out debugtrace.cpp makefile makefile.rules obj-intel64 /path/to/pin/source/tools/branchtrace $ ls obj-intel64/ branchtrace.o branchtrace.so
このbranchtrace.soというのがトレーサーになります。
トレーサーの実行
branchtrace.soを直接実行することはできないので、pinを介して呼び出します。以下のような感じで。
q4/box1$ /path/to/pin/pin -t /path/to/pin/source/tools/branchtrace/obj-intel64/branchtrace.so -- ./box '00010002a'
3
q4/box1$ cat branchtrace.out | head -n 7
[
{"event": "image_load", "image_name": "/vagrant/seccon2019df/q4/box1/box", "image_id": 1, "base_addr": "0x55aa08e61000", "image_size": "0x135f"},
{"event": "image_load", "image_name": "/lib64/ld-linux-x86-64.so.2", "image_id": 2, "base_addr": "0x7f4f2c012000", "image_size": "0x26c23"},
{"event": "image_load", "image_name": "[vdso]", "image_id": 3, "base_addr": "0x7fff31bb3000", "image_size": "0x100a"},
{"event": "image_load", "image_name": "/lib/x86_64-linux-gnu/libc.so.6", "image_id": 4, "base_addr": "0x7f4f1782a000", "image_size": "0x3f0adf"},
{"event": "branch", "inst_addr": "0x55aa08e6164e", "branch_taken": true},
{"event": "branch", "inst_addr": "0x55aa08e61ed4", "branch_taken": false},
できましたね！
結果を整形する
pinの出力してくれるtrace結果はまあまあ綺麗なのですが、各分岐のアドレスがイメージ内の相対ではないので、配布されたものと手元では値が異なり比較が面倒です。
ということで、ささっとスクリプトを書いて整形してくれるようにしましょう。私はNodejsが好きな変人なのでnodejsで書いたprint.jsがこちら。
const fs = require('fs');
const filename = process.argv[2];
const parseTrace =
(fileName) => {
const trace = JSON.parse(fs.readFileSync(fileName, 'utf-8'));
const base_addr = parseInt(trace[0].base_addr, 16);
const branches = trace.filter(e => (e.inst_addr != undefined)).map(e => {
if (e.event === 'call') {
return {
'addr': (parseInt(e.inst_addr, 16) - base_addr).toString(16),
'target': (parseInt(e.target_addr, 16) - base_addr).toString(16)
};
}
return {
'addr': (parseInt(e.inst_addr, 16) - base_addr).toString(16),
'taken': e.branch_taken
};
});
return branches;
}
const print =
(branches) => {
for (var i = 0; i < branches.length;) {
const b = branches[i];
var count = 0;
while (i < branches.length && branches[i].addr == b.addr &&
branches[i].taken == b.taken) {
count++;
i++;
}
console.log(`${JSON.stringify(b)} * ${count}`);
}
console.log(branches.length);
}
const branches = parseTrace(filename);
print(branches);
最初のほうでは気づかなかったのですが、同じ分岐をぐるぐる回る際もけっこうあって、それを *Nと表示した方がわかりやすかったので、そうしていたりします。（色々適当に工夫しながらできあがった完成形。）
また、あとのほうでjmp ccだけでなくcallも出てきたので、それにも一応対応してます。
実行するとこんな感じです。
q4/box1$ node print.js box.trace | head -n 5
{"addr":"64e","taken":true} * 1
{"addr":"ed4","taken":false} * 1
{"addr":"7f5","taken":true} * 1
{"addr":"786","taken":true} * 1
{"addr":"ef4","taken":false} * 1
よいよい、みやすくなった。
入力と分岐の対応関係を調べる
本当ならファジングなり、静的解析でツールを使うなり、ちゃんとやったほうが早いと思うのですが、私はobjdumpしかわからないので、バイナリのobjdumpを横においておきながら、入力と分岐を変化させて、トレーサーをぶん回しながら、どういう挙動をしているのか調べます。
メモの断片:
XXXXYYYYa
{"addr":"ddc","taken":true},
{"addr":"bac","taken":false},
{"addr":"bb6","taken":false},
{"addr":"964","taken":true},
{"addr":"964","taken":true},
{"addr":"a21","taken":true},
{"addr":"a31","taken":true},* Y+1 times
{"addr":"9c4","taken":true},
{"addr":"bf5","taken":true},
00020001b
{"addr":"ddc","taken":true},
{"addr":"bac","taken":false},
{"addr":"bb6","taken":true},
{"addr":"bfe","taken":false},
{"addr":"964","taken":true},
{"addr":"964","taken":true},
{"addr":"9c4","taken":true},
{"addr":"c3d","taken":true},
00200010c
{"addr":"ddc","taken":true},
{"addr":"bac","taken":false},
{"addr":"bb6","taken":true},
{"addr":"bfe","taken":true},
{"addr":"c46","taken":false},
{"addr":"964","taken":true},
{"addr":"964","taken":true},
{"addr":"a5c","taken":true},
{"addr":"a82","taken":true},
{"addr":"a94","taken":true}, // opR + 1
{"addr":"9c4","taken":true},
{"addr":"c85","taken":true},
なるほど、結局のところ
XXXXYYYYa -> XXXX+YYYY XXXXYYYYb -> XXXX-YYYY XXXXYYYYc -> XXXX*YYYY XXXXYYYYd -> min(XXXX, YYYY) XXXXYYYYe-> max(XXXX, YYYY)
という感じの逆ポーランド記法電卓なんですねー（X, Yは数字） あと、addとmulでは、右辺の値に対応して、途中の分岐の呼ばれる数が変わるんですねーということがわかりました。
ということで、適当に合いそうな入力を考えて、トレース……よし、合っていそう。では、投げましょう。私はこんな入力をえらびました。
001000000012ce0010a0000b
わーい！次にいきましょうー
box2
なんだ楽勝じゃん、次もどうせ入力が違うだけなのでは？と思ったのですが
$ ./box usage: ./box input
どうも入力はformura、つまり式ではないようです。色々入れてみましょう。
$ ./box hoge _t $ ./box hogehoge #^L8 $ ./box hogehogehoge ɿAV $ ./box hogehogehogefuga @%Zyr $ ./box hogehogehogefugassssssssssssssssssssssssss -2"qC $ ./box hogehogehogefugasssssssssssssssssssssssssssssssssssssss N?sG>*AA^8>PwvƴP $ ./box hogehogehogefugassssssssssssssssssssssssssssssssssssssssssss z:R Rc-OgGOx
おお？なんか印字不能な文字を出してくるときもありますね。それに、入力と出力の対応も不明です。困った。 とりあえずobjdump...と。
8c9: c6 45 e0 27 movb $0x27,-0x20(%rbp)
8cd: c6 45 e1 51 movb $0x51,-0x1f(%rbp)
8d1: c6 45 e2 90 movb $0x90,-0x1e(%rbp)
8d5: c6 45 e3 79 movb $0x79,-0x1d(%rbp)
8d9: c6 45 e4 66 movb $0x66,-0x1c(%rbp)
8dd: c6 45 e5 b7 movb $0xb7,-0x1b(%rbp)
8e1: c6 45 e6 25 movb $0x25,-0x1a(%rbp)
8e5: c6 45 e7 61 movb $0x61,-0x19(%rbp)
8e9: c6 45 e8 45 movb $0x45,-0x18(%rbp)
8ed: c6 45 e9 63 movb $0x63,-0x17(%rbp)
8f1: c6 45 ea c3 movb $0xc3,-0x16(%rbp)
8f5: c6 45 eb f8 movb $0xf8,-0x15(%rbp)
8f9: c6 45 ec f4 movb $0xf4,-0x14(%rbp)
8fd: c6 45 ed 96 movb $0x96,-0x13(%rbp)
901: c6 45 ee a5 movb $0xa5,-0x12(%rbp)
905: c6 45 ef 2e movb $0x2e,-0x11(%rbp)
909: 48 8b 85 00 ff ff ff mov -0x100(%rbp),%rax
910: 48 8b 40 08 mov 0x8(%rax),%rax
914: 48 89 85 18 ff ff ff mov %rax,-0xe8(%rbp)
91b: 48 8b 85 18 ff ff ff mov -0xe8(%rbp),%rax
922: 48 89 c7 mov %rax,%rdi
925: e8 86 fd ff ff callq 6b0 <strlen@plt>
なんか16回movしてそのあとstrlenしている…16という数字があやしいな？
と思いながらトレースをしていたところ、以下の事実を発見した。
$ node trace.js ./box '0' | tail -n 1 821 $ node trace.js ./box '0123' | tail -n 1 821 $ node trace.js ./box '0123456789abcdef' | tail -n 1 821 $ node trace.js ./box '0123456789abcdefg' | tail -n 1 1535 $ node trace.js ./box '0123456789abcdefghi' | tail -n 1 1535 $ node trace.js ./box '0123456789abcdef0123456789abcdef' | tail -n 1 1535 $ node trace.js ./box '0123456789abcdef0123456789abcdef0' | tail -n 1 2249
ここでtrace.jsは、私が適当に書いたトレーサーをラップするスクリプトで、最後にトレースの総分岐数が出てくるのですが、なぜか入力が16文字増えるごとに段階的に分岐数が増える。しかも、トレース結果をみると、同じ分岐回数なら、分岐の内容は一切変わっていない。
16文字の境界を超えるごとに、分岐数は1535-821 == 2249 - 1535 == 714増えるから、つまるところ16*N+1以上16*N+16文字(N >=0)の入力を与えた時、その総分岐数は821+N*714になるというわけです。
さて、与えられたtraceの総分岐数は8675であったから、この式で逆算すると(8675-821)/714 => 11となるわけです。おお、まじか、ぴったり整数じゃん！（ここで嬉しい気分になる。）
というわけで、気軽に16*11+16 => 192文字のファイルを生成して送りつけました。わーい！
box3
box2がさくっと終わったので、どんどんやっていこうーとなった流れで到達したbox3は、めっちゃ楽しかった。だって
$ ./box usage: ./box filename
と出たので、適当にtouchしたファイルを食べさせたら
./box empty.txt [!] Not implemented: code=0 EAX = 00000000 ECX = 00000000 EDX = 00000000 EBX = 00000000 ESP = 00007c00 EBP = 00007c00 ESI = 00000000 EDI = 00000000 EIP = 00007c00
見慣れたレジスタ名が出てきたんですもの。しかも、0x7c00!!!!!（この嬉しさを理解したい方は30日でできるOS自作入門かIntel SDMでも読んでおいてください。）
これは十中八九エミュレーターだろう、と思ったので、早速NOPを食べさせると
$ echo '90' | xxd -r -p > nop.bin $ ./box nop.bin [!] Not implemented: code=0 EAX = 00000000 ECX = 00000000 EDX = 00000000 EBX = 00000000 ESP = 00007c00 EBP = 00007c00 ESI = 00000000 EDI = 00000000 EIP = 00007c01
たしかにさっきより1バイト進んでから死んでますね。やったね！
どんな命令が実装されているのか特定する
そうきたら、あとはこの子の実装状況と動作のようすを解明してあげるだけです。 最初は、Intel SDM Vol.2のopcode表をみて適当にあたりをつけていたのですが、あまりにもきつかったので方針転換しました。
幸運にもNOPが実装されていることはわかったので、NOPの数を変えてトレースしてみましょう。
トレース結果は長いのですが、着目すべき点はただ一つ: call命令のトレース結果だけです。私のprint.jsでは、call命令の場合はtargetというメンバを記録するようにしているので、それでgrepをかけます。
$ echo '90' | xxd -r -p > nop1.bin
$ echo '90 90' | xxd -r -p > nop2.bin
$ node trace.js ./box nop1.bin | grep target
{"addr":"3b2d","target":"2e44"} * 1
$ node trace.js ./box nop2.bin | grep target
{"addr":"3b2d","target":"2e44"} * 1
{"addr":"3b2d","target":"2e44"} * 1
なるほど…つまるところ、+0x2e44のところがNOPの命令を処理しているようですね。
どうしてcall命令にのみ着目すればいいのかというと、たいていのCPUエミュレータは、動作を高速にするために、入力された命令のバイトを配列の添字として、関数ポインタの配列にアクセスして各処理を呼び出すからです。（作ってみるとわかるこの気持ち。）
というわけで、call命令のtargetを見れば、どの命令が実行されているのかわかりそうですね。
では、求めるべきトレース結果から、どの命令が使われているか抽出してみましょう。とりあえずcall命令だけを抜き出してみると、
$ node print.js box.trace | grep target
{"addr":"3b2d","target":"2ebd"} * 1
{"addr":"3b2d","target":"2ebd"} * 1
{"addr":"3b2d","target":"2159"} * 1
{"addr":"3b2d","target":"28fd"} * 1
{"addr":"3b2d","target":"1ead"} * 1
{"addr":"3b2d","target":"2389"} * 1
{"addr":"3b2d","target":"317d"} * 1
{"addr":"3b2d","target":"2159"} * 1
{"addr":"3b2d","target":"28fd"} * 1
{"addr":"3b2d","target":"1ead"} * 1
{"addr":"3b2d","target":"2389"} * 1
{"addr":"3b2d","target":"317d"} * 1
{"addr":"3b2d","target":"2159"} * 1
{"addr":"3b2d","target":"28fd"} * 1
{"addr":"3b2d","target":"1ead"} * 1
{"addr":"3b2d","target":"2389"} * 1
{"addr":"3b2d","target":"317d"} * 1
{"addr":"3b2d","target":"2159"} * 1
{"addr":"3b2d","target":"28fd"} * 1
{"addr":"3b2d","target":"1ead"} * 1
{"addr":"3b2d","target":"2389"} * 1
{"addr":"3b2d","target":"317d"} * 1
{"addr":"3b2d","target":"2159"} * 1
{"addr":"3b2d","target":"28fd"} * 1
{"addr":"3b2d","target":"1ead"} * 1
{"addr":"3b2d","target":"2389"} * 1
{"addr":"3b2d","target":"317d"} * 1
{"addr":"3b2d","target":"2159"} * 1
{"addr":"3b2d","target":"28fd"} * 1
{"addr":"3b2d","target":"3269"} * 1
おー、やはりindirectなcall命令は1箇所しかないんですね。で、このtargetの一意なリストは以下です。
$ node print.js box.trace | grep target | cut -d \" -f 8 | sort | uniq 1ead 2159 2389 28fd 2ebd 317d 3269
さて、ここからどうやって命令オペコードを知ればよいでしょうか。
さきほど言ったように、このエミュレータは命令オペコードをテーブルの添字にすることで関数ポインタを得て、それをcallしているはずです。 では、そのテーブルはどこにあるのか…objdumpをみるとあやしいところを見つけました。
340b: 55 push %rbp
340c: 48 89 e5 mov %rsp,%rbp
340f: 48 83 ec 10 sub $0x10,%rsp
3413: ba 00 08 00 00 mov $0x800,%edx
3418: be 00 00 00 00 mov $0x0,%esi
341d: 48 8d 3d 7c 2c 20 00 lea 0x202c7c(%rip),%rdi # 2060a0 <__cxa_finalize@plt+0x2055f0>
3424: e8 f7 d5 ff ff callq a20 <memset@plt>
3429: 48 8d 05 7d ea ff ff lea -0x1583(%rip),%rax # 1ead <__cxa_finalize@plt+0x13fd>
3430: 48 89 05 71 2c 20 00 mov %rax,0x202c71(%rip) # 2060a8 <__cxa_finalize@plt+0x2055f8>
3437: 48 8d 05 0c eb ff ff lea -0x14f4(%rip),%rax # 1f4a <__cxa_finalize@plt+0x149a>
343e: 48 89 05 7b 2c 20 00 mov %rax,0x202c7b(%rip) # 2060c0 <__cxa_finalize@plt+0x205610>
3445: 48 8d 05 02 ec ff ff lea -0x13fe(%rip),%rax # 204e <__cxa_finalize@plt+0x159e>
344c: 48 89 05 c5 2c 20 00 mov %rax,0x202cc5(%rip) # 206118 <__cxa_finalize@plt+0x205668>
3453: 48 8d 05 62 ec ff ff lea -0x139e(%rip),%rax # 20bc <__cxa_finalize@plt+0x160c>
345a: 48 89 05 87 2d 20 00 mov %rax,0x202d87(%rip) # 2061e8 <__cxa_finalize@plt+0x205738>
3461: 48 8d 05 f1 ec ff ff lea -0x130f(%rip),%rax # 2159 <__cxa_finalize@plt+0x16a9>
3468: 48 89 05 f9 2d 20 00 mov %rax,0x202df9(%rip) # 206268 <__cxa_finalize@plt+0x2057b8>
346f: 48 8d 05 8b ed ff ff lea -0x1275(%rip),%rax # 2201 <__cxa_finalize@plt+0x1751>
3476: 48 89 05 fb 2d 20 00 mov %rax,0x202dfb(%rip) # 206278 <__cxa_finalize@plt+0x2057c8>
347d: 48 8d 05 25 ee ff ff lea -0x11db(%rip),%rax # 22a9 <__cxa_finalize@plt+0x17f9>
3484: 48 89 05 f5 2d 20 00 mov %rax,0x202df5(%rip) # 206280 <__cxa_finalize@plt+0x2057d0>
348b: 48 8d 05 89 ee ff ff lea -0x1177(%rip),%rax # 231b <__cxa_finalize@plt+0x186b>
3492: 48 89 05 ef 2d 20 00 mov %rax,0x202def(%rip) # 206288 <__cxa_finalize@plt+0x2057d8>
3499: c7 45 fc 00 00 00 00 movl $0x0,-0x4(%rbp)
何やらばんばんleaして代入してますね。しかも、関数のアドレスっぽいです。もう少し下の方をみると
3677: 48 8d 05 c6 f7 ff ff lea -0x83a(%rip),%rax # 2e44 <__cxa_finalize@plt+0x2394>
367e: 48 89 05 9b 2e 20 00 mov %rax,0x202e9b(%rip) # 206520 <__cxa_finalize@plt+0x205a70>
NOP命令だとわかっている、0x2e44の関数ポインタを代入しているところをみつけました！ どうもこのテーブルの先頭は、ソースの流れ的に
341d: 48 8d 3d 7c 2c 20 00 lea 0x202c7c(%rip),%rdi # 2060a0 <__cxa_finalize@plt+0x2055f0>
曰く0x2060a0のようです。では、この予想が正しいか調べてみましょう。
- NOPのオペコードは0x90
- NOPの関数ポインタはオフセット0x206520に格納されている
- ポインタの大きさは8bytes
- 関数ポインタのテーブルは0x2060a0から始まっている？
関数ポインタのテーブルをop_tableとしたとき、
op_table[0x90] == <+0x2e44のアドレス>
になっていてほしいわけです。これはつまり
*(op_table + 8 * 0x90) == <+0x2e44のアドレス>
というのと等価ですから、格納されるべきアドレスは、テーブルの先頭op_tableから8 * 0x90 == 1152離れているはずです。op_tableを0x2060a0とすれば、その結果は…
0x2060a0 + 8 * 0x90 => 0x206520
ビンゴ！NOPの関数ポインタが代入されているアドレスと一致しますね！！
というわけで、これでテーブルを生成するコードで各関数がテーブルのどのオフセットに格納されているか調べれば、対応するオペコードがわかりそうです。
…とりあえず、テーブル内の各オフセットと対応するオペコードはスクリプトでさくっと生成しました。
[ [ '2060a8', '1' ], [ '2060c0', '4' ], [ '206118', 'f' ], [ '2061e8', '29' ], [ '206268', '39' ], [ '206278', '3b' ], [ '206280', '3c' ], [ '206288', '3d' ], [ '2063e0', '68' ], [ '2063f0', '6a' ], [ '206420', '70' ], [ '206428', '71' ], [ '206430', '72' ], [ '206438', '73' ], [ '206440', '74' ], [ '206448', '75' ], [ '206460', '78' ], [ '206468', '79' ], [ '206480', '7c' ], [ '206490', '7e' ], [ '206498', '7f' ], [ '2064b8', '83' ], [ '2064e0', '88' ], [ '2064e8', '89' ], [ '2064f0', '8a' ], [ '2064f8', '8b' ], [ '206508', '8d' ], [ '206520', '90' ], [ '2066b8', 'c3' ], [ '2066d8', 'c7' ], [ '2066e8', 'c9' ], [ '206708', 'cd' ], [ '2067c0', 'e4' ], [ '2067e0', 'e8' ], [ '2067e8', 'e9' ], [ '2067f8', 'eb' ], [ '206800', 'ec' ], [ '206810', 'ee' ], [ '206840', 'f4' ], [ '206898', 'ff' ] ]
そして、あとはobjdumpの結果とIntel SDM Vol.2をじーっと見つめると…
1ead -> 2060a8 -> 0x01 -> ADD Ev,Gv 2159 -> 206268 -> 0x39 -> CMP Ev,Gv 2389 -> INC r32 28fd -> 206498 -> 0x7f -> JNLE / JG 2ebd -> -> mov r32, imm32 317d -> 2067f8 -> 0xeb -> short Jb 3269 -> 206840 -> 0xf4 -> HLT
はい！
incとmovに関しては、オペコード内にレジスタがエンコーディングされている（つまり、複数のオペコードが同じ操作を表現する）ので、バイナリ中でもループを回して代入されていました。なのでちょっと歯抜けです。(INCとかがオフセットいくつで実装されているかを調べたりして突き止めた。)
さて、あとはprint.jsを拡張して、トレース結果からオペコードを表示してみるか…となったんですが
PROLOGUE
mov r32, imm32
mov r32, imm32
CMP Ev,Gv
{"addr":"bdf","taken":false} * 1
{"addr":"be6","taken":true} * 1
{"addr":"a20","taken":true} * 1
{"addr":"c7d","taken":true} * 1
{"addr":"cbf","taken":true} * 1
{"addr":"cd6","taken":true} * 1
{"addr":"d0e","taken":true} * 1
{"addr":"13a1","taken":false} * 1
{"addr":"13bc","taken":true} * 1
{"addr":"1cb5","taken":false} * 1
{"addr":"1cca","taken":true} * 1
{"addr":"1cf1","taken":true} * 1
{"addr":"1d2d","taken":false} * 1
{"addr":"1d41","taken":true} * 1
{"addr":"1e86","taken":true} * 1
{"addr":"1d67","taken":true} * 1
{"addr":"21f8","taken":true} * 1
JNLE / JG
ADD Ev,Gv
INC r32
...
INC r32
short Jb
CMP Ev,Gv
{"addr":"bdf","taken":false} * 1
{"addr":"be6","taken":true} * 1
{"addr":"a20","taken":true} * 1
{"addr":"c7d","taken":true} * 1
{"addr":"cbf","taken":true} * 1
{"addr":"cd6","taken":true} * 1
{"addr":"d0e","taken":true} * 1
{"addr":"13a1","taken":false} * 1
{"addr":"13bc","taken":true} * 1
{"addr":"1cb5","taken":true} * 1
{"addr":"1cf1","taken":true} * 1
{"addr":"1d2d","taken":true} * 1
{"addr":"1e86","taken":true} * 1
{"addr":"1d67","taken":true} * 1
{"addr":"21f8","taken":true} * 1
JNLE / JG
JNLE / JG taken
HLT->END
444
これはCMP Ev, Gvの分岐列だけベタで、あとは命令の名前で表示してみたんですが、なぜか微妙に長さが違います。考えられるのは…演算結果によって分岐が変わるということです。 CMP命令は、引き算の結果に合わせてフラグレジスタを設定しますから、いかにもありそうなかんじです。また、分岐命令についても分岐列の長さが1命令程度変動する時があり、これは分岐が行われたか否かを示しているようでした。 というわけで、うまくつじつまを合わせるとこんな感じのアセンブリ列をバイナリにして食べさせてあげたトレース結果を投げると（長い）フラグが降ってきました。うれしいね！
.intel_syntax noprefix mov eax, 1 mov ebx, 5 cmp eax, ebx jg out add ecx, edx inc eax jmp a a: cmp edx, ebx jg out # false add ecx, edx inc eax jmp b b: cmp edx, ebx jg out # false add ecx, edx inc eax jmp d d: cmp edx, ebx jg out # false add ecx, edx inc eax jmp e e: cmp eax, ebx jg cccc cccc: add ecx, edx inc eax jmp g g: cmp ebx, edx jg out # true add ecx, edx inc eax jmp f f: out: hlt
コンパイルとバイナリの抽出は以下のような感じで。（out.binがおいしいバイナリです。）
gcc -m16 -c -o test.o test.S && objcopy -O binary test.o out.bin
さあ、次もいきましょう！！
box4
さて、次は何かな、と思ったら
$ md5sum box3/box box4/box d8614ad07b9efbb87a6049bd7b5da1c7 box3/box d8614ad07b9efbb87a6049bd7b5da1c7 box4/box
同じバイナリじゃないですか！やったね、スクリプトが流用できるよ！
追加の命令列を特定
2c33 -> 2064e8 -> 0x89 -> MOV Ev,Gv 23e7 -> -> DEC r32 24c3 -> -> POP r32 251a -> 2063e0 -> 0x68 -> PUSH lz 2645 -> 206440 -> 0x74 -> JZ/JE 2695 -> 206448 -> 0x75 -> JNZ/JNE 3144 -> 2067e8 -> 0xe9 -> JMP near Jz
かんたんだね！
print.jsを拡張
- 分岐のtaken/not taken
- OF（オーバーフローフラグ）の表示を追加
Parser for SECCON 2019 final q4 box4
このスクリプトを、与えられたトレース結果に適用すると、こんなかんじの出力が得られます。
$ node print.js box.trace PROLOGUE PUSH imm32 PUSH imm32 PUSH imm32 PUSH imm32 POP r32 POP r32 DEC r32 ZF=false OF=false MOV r/m32,r32 ADD Ev,Gv DEC r32 ZF=false OF=false JNZ/JNE JNZ/JNE taken? ADD Ev,Gv DEC r32 ZF=true OF=false JNZ/JNE CMP Ev,Gv ZF=false JZ/JE JMP near Jz POP r32 DEC r32 ZF=false OF=false MOV r/m32,r32 ADD Ev,Gv DEC r32 ZF=true OF=false JNZ/JNE CMP Ev,Gv ZF=false JZ/JE JMP near Jz POP r32 DEC r32 ZF=false OF=false MOV r/m32,r32 ADD Ev,Gv DEC r32 ZF=false OF=false JNZ/JNE JNZ/JNE taken? ADD Ev,Gv DEC r32 ZF=false OF=false JNZ/JNE JNZ/JNE taken? ADD Ev,Gv DEC r32 ZF=true OF=false JNZ/JNE CMP Ev,Gv ZF=true JZ/JE JZ/JE taken HLT->END 613
もうほとんどアセンブリだね！
入力バイナリを錬成
メモ書き込みですがこんな感じでとけた。
.intel_syntax noprefix //PUSH lz //PUSH lz //PUSH lz //PUSH lz .byte 0x68, 0x02, 0x00, 0x00, 0x00 .byte 0x68, 0x02, 0x00, 0x00, 0x00 .byte 0x68, 0x02, 0x00, 0x00, 0x00 .byte 0x68, 0x02, 0x00, 0x00, 0x00 //POP r32 //POP r32 //DEC r32 ZF=false : r32 != 1 //MOV Ev,Gv //ADD Ev,Gv //DEC r32 ZF=false : r32 != 1 //JNZ/JNE //JNZ/JNE taken? pop edx // edx = 1 pop esi // esi = 1 dec edx // op != 0 mov ecx,edx add edx,eax dec esi jne fake fake: //ADD Ev,Gv //DEC r32 ZF=true : r32 == 1 //JNZ/JNE //CMP Ev,Gv ZF=false //JZ/JE //JMP near Jz add ecx,ecx dec esi // op should be 1 jnz c c: cmp eax,ecx jz d .byte 0xe9, 0x00, 0x00, 0x00, 0x00 d: //POP r32 //DEC r32 ZF=false //MOV Ev,Gv //ADD Ev,Gv //DEC r32 ZF=true //JNZ/JNE pop ebx dec ebx mov ecx,ebx add edi,ecx dec ebx jne e e: //CMP Ev,Gv ZF=false //JZ/JE //JMP near Jz cmp eax,ecx jz p .byte 0xe9, 0x00, 0x00, 0x00, 0x00 p: //POP r32 //DEC r32 ZF=false //MOV Ev,Gv //ADD Ev,Gv //DEC r32 ZF=false //JNZ/JNE //JNZ/JNE taken pop ebx dec ebx mov ecx,ecx add edi,ecx dec edi jne q q: //ADD Ev,Gv //DEC r32 ZF=false //JNZ/JNE //JNZ/JNE taken add edi,ecx dec edi jnz m m: //ADD Ev,Gv //DEC r32 ZF=true //JNZ/JNE add ecx,ecx dec ebx jne n n: //CMP Ev,Gv ZF=true //JZ/JE //JZ/JE taken cmp eax,eax jz s s: //HLT->END hlt
あれ、Defenceポイントはどうしたの？
box1のvariantってことだったので、演算子とかは一緒かなと思っていたのですが、完全に変わっていたのでつらかった。自動化するにはちゃんとファジングとかデコンパイラを活用する必要がありそうだなあという気持ちになりました。強くなりたいです。
他に何をやりましたか？
MimuraのフラッシュをダンプしてFATを読む試みをしたりした。でもうまくいかなかった。st98さんが実機を持って帰ったので朗報を期待している。
Bad mouseをst98さんが解いてくれたのだが、実機を持っていなかったようなので、去年かどこかで配られたのを家に置いてあった私が代わりに実行しました。 マウスが動いてフラグが塗られるのは楽しかった。しかし、待ち時間が長かった…（st98さん曰く、もっとwaitを短くできたらしいのでそうするといいと思います。）
以下、塗られたフラグの実際の画像です。
まとめ
問題4はめっちゃ楽しかった。作問者の友利奈緒さん、いい問題をありがとうございます！
坂井さんの問題は、ちょっとやる気が出なかったです。私のバイナリ鍛錬が足りないのも要因ですが、単純にあまり問題がおもしろくなかったのと、ディフェンスポイントの入りかたにゲーム性がないなどの問題もあったと私は思います。来年はアーキの数で殴るタイプではない、面白く解けるマルチアーキテクチャ問題を期待しています…。
とはいえ、全体的には楽しめたのでよかったです。SECCONはSECCONなので！と私は思っています。
運営のみなさま、ありがとうございました。
