saotake’s blog

-竿竹-

(DEFCON2016Qual) baby:re

バイナリが渡されてそれを解析する問題。

バイナリを実行すると、var0~var12の13個の数字の入力を求められる。適当に入力すると、「Wrong」と表示されてプログラムが終了。正しい13個の数字を解析して見つけるのが問題の趣旨。

> ./baby-re
Var[0]: 1
Var[1]: 2
Var[2]: 3
Var[3]: 4
Var[4]: 5
Var[5]: 6
Var[6]: 7
Var[7]: 8
Var[8]: 1
Var[9]: 2
Var[10]: 3
Var[11]: 4
Var[12]: 5
Wrong
> 

 

バイナリ系の問題はツールが重要(だと思っているの)ですが、

最近の流行通り、64bitELFなので、IDA Pro(フリー版)が使えません。

30分で解けるならhopperトライアル版がおすすめですが、

30分では解けそうにないので、radare2を使用しました。

IDAのようなグラフ表示GUIも備えていて、

TUCTFのIRCでは、「IDAよりすごい」という話になっていました。

 

公式サイト様:radare

 

詳細な使い方は述べませんが、以下のように今回は使いました。

 

■起動する

> r2 baby-re

 

■解析をさせる(画面上は変化なし)

[0x004005d0]> aa
[0x004005d0]> 

 

■コードを表示する(VIみたいにプロンプト上でグラフィカル操作するモード)

[0x004005d0]> V

[0x004005d0 752 baby-re]> x @ entry0
- offset - 0 1 2 3 4 5 6 7 8 9 A B C D E F 0123456789ABCDEF
0x004005d0 31ed 4989 d15e 4889 e248 83e4 f050 5449 1.I..^H..H...PTI
0x004005e0 c7c0 f029 4000 48c7 c180 2940 0048 c7c7 ...)@.H...)@.H..
0x004005f0 e725 4000 e897 ffff fff4 660f 1f44 0000 .%@.......f..D..
0x00400600 b85f 3060 0055 482d 5830 6000 4883 f80e ._0`.UH-X0`.H...
0x00400610 4889 e576 1bb8 0000 0000 4885 c074 115d H..v......H..t.]
0x00400620 bf58 3060 00ff e066 0f1f 8400 0000 0000 .X0`...f........
0x00400630 5dc3 0f1f 4000 662e 0f1f 8400 0000 000

 

 

GUI(ローカルWebサーバ)を起動(もう一回Vを押します)

[0x004005d0]> V

※最新のradare2-webuiだと、起動方法が異なるようです。

f:id:saotake:20160521230723p:plain

 

スクリーンショットではわかりませんが、

ブラウザ上とは思えないくらいとても高機能です。

 

 

さて、肝心な問題の中身ですが、radare2でmain関数(sym.main)を追うと、

「sym.CheckSolution」という関数で入力値のチェックを行っていることがわかります。

 

■Radare2(Web)での操作

・「]」ボタンを押すか、マウスで左へスワイプ(?)して、「ListElements」画面を表示。

・functionsを選択して、sym.main関数へ飛ぶ

・上から順番に見る。

※トップメニューの「Graph-Basicblocks」を選択すれば、IDAのようなグラフビューにもできます。

 

f:id:saotake:20160521231412p:plain

 

0x004028e0でsym.CheckSolution()を呼び出した後、0以外の場合、

0x0040292cでフラグの表示を行っていることがわかります。

(なお、デバッガで強制的にフラグ表示部分にjumpしても、フラグは得られません)

 

次に、CheckSolution()の中身を見ていきます。

■Radare2(Web)での操作

・「]」ボタンを押すか、マウスで左へスワイプ(?)して、「ListElements」画面を表示。

・functionsを選択して、sym.CheckSolution()関数へ飛ぶ

 

慣れていないのですごく悩みましたが、

CUIでユーザが入力した値Var0~Var12は、(rbp-0x2b8)以降に書かれているアドレスの場所に保存されています。

逆に、(rbp-0x00)~(rbp-0x2b0)のアドレスは、CheckSolution()のローカル変数です。また、計算後の値は毎回同じなので、「定数」と考えてよいです。

CheckSolutionの前半部分は、やたら面倒な計算が続きますが、すべてこのローカル変数の初期化(難読化)ですので、いったん飛ばすことにします。

肝心なユーザ入力値(rbp-0x2b8)が参照されるのは、CheckSolution()の後半の、0x0040155eからです。

f:id:saotake:20160521232039p:plain

ここからは同じような計算式がずっと続いていて、以下のような等式を評価しています。

ローカル変数00*ユーザ入力値0 + ローカル変数01*ユーザ入力値1 + ・・・=定数1

ローカル変数10*ユーザ入力値0 + ローカル変数11*ユーザ入力値1 + ・・・=定数2

・・・(合計13個の式を評価)

13このユーザ入力(Var0~Var12)に対して、ローカル変数(毎回同じ値になるので定数と見なせる)が13×13個(左辺)、定数が13個(右辺)で、式が13個です。

すでに忘れかけた高校数学の知識によると、これは13元の連立方程式です。連立方程式は以下の式で解けますから、ローカル変数さえ決まれば、式を満たすユーザ入力値は簡単に計算できます。(近似逆行列とか難しい話は忘れました)

AX=B (A,Bは定数、Xが未知)

ならば、

X=inv(A)*B

 ここで、ローカル変数A,Bは、CheckSolution()の前半で複雑に計算されており、コードを追うのはすごく厳しいですが、毎回同じ計算結果になるので、デバッガを使ってローカル変数初期化完了後にメモリの値をみてやればいいです。具体的には、前述のユーザ入力値の参照が行われる0x0040155e付近で止めればOKです。

ついでにgdbの使い方の復習。調べたいローカル変数のアドレスは、[rbp-0x10]~[rbp-0x2b0]です。

 

■起動

> gdb baby-re

 (gdb

 

■ブレイクポイント設置

(gdb) b *0x0040155e

Breakpoint 1 at 0x40155e

 

■デバッガモードでプログラム起動

(gdb) r
Starting program: /home/user/Desktop/baby-re
Var[0]: 1
Var[1]: 2
Var[2]: 1
Var[3]: 2
Var[4]: 1
Var[5]: 2
Var[6]: 1
Var[7]: 2
Var[8]: 1
Var[9]: 2
Var[10]: 1
Var[11]: 2
Var[12]: 1

Breakpoint 1, 0x000000000040155e in CheckSolution ()

 

■メモリ内のローカル変数の情報を見る

(gdb) x $rbp-0x2b0
0x7fffffffdc00: 0x0000926d
(gdb) x $rbp-0x2ac
0x7fffffffdc04: 0x00005475
(gdb) x $rbp-0x10
0x7fffffffdea0: 0x00001c92
(gdb

 

これでローカル変数A,Bの値も調べられましたので、後は、

AX=B

X=inv(A)*B

 を満たすXを計算して、見つけてやるだけです。逆行列inv(A)は、MatlabでもMathematicaでもエクセルでも簡単に計算できます。

 

なお、説明的には以上なのですが、実際にとこうとすると、「ローカル変数*入力値」の13*13=169項目が、それぞれプラスだったりマイナスだったりとバラバラになっていて、それがハードコーディングされています。なので、全項目についてプラスするのかマイナスするのかを、コードを読まなければダメです。実質これが一番面倒でした。

> /baby-re
Var[0]: 77
Var[1]: 97
Var[2]: 116
Var[3]: 104
Var[4]: 32
Var[5]: 105
Var[6]: 115
Var[7]: 32
Var[8]: 104
Var[9]: 97
Var[10]: 114
Var[11]: 100
Var[12]: 33
The flag is: Math is hard!