この記事は新歓ブログリレー2019 45日目の記事です。

traPへの入部について

今日から一週間入部期間が始まります。traPに入部したい方は是非お越しください。

場所

4/22(月),4/23(火),4/25(火)
S516 17:00～

4/24(水)
S516 13:30～

4/26(金)
S516 15:30～16:30 （17:00～新歓パーティの為早めに来てください）

準備するもの

• 部費2000円
• アカウント名（部内では基本的にアカウント名で呼ばれます）
• スマホ等のインターネット環境

この機会を逃しても入部は可能ですが、担当者と予定を合わせないといけないので面倒です。是非この機会にお越しください。
お待ちしています！

本編

18Bのeiyaです。プログラミングとCTFをやっていますと断言したい今日この頃です。
CPCTF 2019のスコアサーバーとフロントの改造と、Pwn1000点分と、fast_fibonacci,passcodeを担当しました。今回はfast_fibonacciを使って、CTFの為の機械語読解の解説をします。

問題について

300点としては難しく、解ける人はノーヒントで解けるけど、解けない人はずっと解けないという問題になっていました。ヒントを使って解いた人はいませんでした。

問題

fib(1)=fib(2)=1
binary

注：そのまま実行するとSegmentation fault (core dumped)と表示されるか、何も表示されず実行が終了もしない、のどちらかになると思いますが、それが正常です。

ファイルはここからダウンロードできます

環境

このバイナリはLinuxで動くので、Linuxの環境を用意しましょう。（mac持ってないので分からないですが、macでも動くならmacでも良いかもしれない）
バイナリを読むためのデバッガは、radare2,gdb,IDAと色々ありますが、今回はgdbを使います。
（僕はgdbのgdb-pedaという拡張を使っています。telescopeが便利。今回はgdbのコマンドしか使わないようにします。）

問題解析

まずは、ファイルを実行してみましょう。

$wget https://trap.jp/content/images/2019/04/fast_fibonacci
$chmod +x ./fast_fibonacci
$./fast_fibonacci
Segmentation fault (コアダンプ)

途中で異常終了してしまい、最後まで実行できませんでした。悲しいですね。

gdbで中身を見てみましょう。disas 関数名で、その関数の中身が見れます。C言語のプログラムはmainから始まるので取り合えずdisas mainすると良いでしょう。

$gdb fast_fibonacci
gdb-peda$disas main
   0x0000078d <+ 0>:	lea    ecx,[esp+0x4]
   0x00000791 <+ 4>:	and    esp,0xfffffff0
   0x00000794 <+ 7>:	push   DWORD PTR [ecx-0x4]
   0x00000797 <+10>:	push   ebp
   0x00000798 <+11>:	mov    ebp,esp
   0x0000079a <+13>:	push   ecx
   0x0000079b <+14>:	sub    esp,0x14
   0x0000079e <+17>:	call   0x7d6 <__x86.get_pc_thunk.ax>
   0x000007a3 <+22>:	add    eax,0x1831
   0x000007a8 <+27>:	sub    esp,0xc
   0x000007ab <+30>:	push   0x53e691
   0x000007b0 <+35>:	call   0x56d <fib>
   0x000007b5 <+40>:	add    esp,0x10
   0x000007b8 <+43>:	mov    DWORD PTR [ebp-0xc],eax
   0x000007bb <+46>:	sub    esp,0xc
   0x000007be <+49>:	push   DWORD PTR [ebp-0xc]
   0x000007c1 <+52>:	call   0x5b8 <decode>
   0x000007c6 <+57>:	add    esp,0x10
   0x000007c9 <+60>:	mov    eax,0x0
   0x000007ce <+65>:	mov    ecx,DWORD PTR [ebp-0x4]
   0x000007d1 <+68>:	leave  
   0x000007d2 <+69>:	lea    esp,[ecx-0x4]
   0x000007d5 <+72>:	ret  

callの部分に注目しましょう。これは、他の関数を呼び出す処理です。関数名は、処理の内容を示している（いて欲しい）ので、コメントが無いバイナリファイルの中で、コメント代わりになります。
__x86.get_pc_thunk.axとfibとdecodeという関数を呼び出していることが分かります。
このうち、明らかになんか綺麗じゃない関数名の、__x86.get_pc_thunk.axはコンパイラが勝手に埋め込んでいる関数呼び出しなので気にしないことにします。（ここはフィーリングで。何度かやると慣れてきます）

ここまでで分かったことで疑似コードを書くとこんな感じになります。

int main()
{
...
fib(...);
...
decode(...);
}

次はcall 0x56d <fib>の直前の、pushを見てみましょう。これはスタックに値を追加する操作です。ここで追加された値が、次のcallで関数の引数として渡される値になります。
このあたりの動作はこのサイトが分かりやすいです。x86 アセンブラ 関数呼び出し等のワードで検索すると他にもいろいろと出てきます。ちなみにこの後も細かい動作をかなり省略しますが気になったら自分で調べてください。
ここでは、fibの引数に0x53e691を入れていることが分かります。（ちなみに0x53e691は10進表記で5498513で、僕のtwitterアカウントの部分列です）

次にfibの中身を見てみましょう。

gdb-peda$disas fib
Dump of assembler code for function fib:
   0x0000056d <+ 0>:	push   ebp
   0x0000056e <+ 1>:	mov    ebp,esp
   0x00000570 <+ 3>:	push   ebx
   0x00000571 <+ 4>:	sub    esp,0x4
   0x00000574 <+ 7>:	call   0x7d6 <__x86.get_pc_thunk.ax>
   0x00000579 <+12>:	add    eax,0x1a5b
   0x0000057e <+17>:	cmp    DWORD PTR [ebp+0x8],0x2
   0x00000582 <+21>:	jg     0x58b <fib+30>
   0x00000584 <+23>:	mov    eax,0x1
   0x00000589 <+28>:	jmp    0x5b3 <fib+70>
   0x0000058b <+30>:	mov    eax,DWORD PTR [ebp+0x8]
   0x0000058e <+33>:	sub    eax,0x1
   0x00000591 <+36>:	sub    esp,0xc
   0x00000594 <+39>:	push   eax
   0x00000595 <+40>:	call   0x56d <fib>
   0x0000059a <+45>:	add    esp,0x10
   0x0000059d <+48>:	mov    ebx,eax
   0x0000059f <+50>:	mov    eax,DWORD PTR [ebp+0x8]
   0x000005a2 <+53>:	sub    eax,0x2
   0x000005a5 <+56>:	sub    esp,0xc
   0x000005a8 <+59>:	push   eax
   0x000005a9 <+60>:	call   0x56d <fib>
   0x000005ae <+65>:	add    esp,0x10
   0x000005b1 <+68>:	add    eax,ebx
   0x000005b3 <+70>:	mov    ebx,DWORD PTR [ebp-0x4]
   0x000005b6 <+73>:	leave  
   0x000005b7 <+74>:	ret   

call <fib>が二つありますね。フィボナッチ数列で再帰が二つと言えばとても実行に時間がかかることで有名なアレですね。知らなかったら覚えましょう。本番で知らなかった場合でも、ググれば出てくるので頑張りましょう。CTFではグーグルは友達です。

int fib(int n)
{
	if (n <= 2) { return 1; }
	return fib(n - 1) + fib(n - 2);
}

fib(1)=fib(2)=1に気を付けてください。
ちなみに、戻り値が32bit整数(int)であることは、eax等のe..系しか使ってないことからわかります。

ここまでで分かったことで疑似コードを書くとこんな感じになります。

int fib(int n)
{
	if (n <= 2) { return 1; }
	return fib(n - 1) + fib(n - 2);
}
int main()
{
...
fib(0x53e691);
...
decode(...);
}

これでSegmentation fault (コアダンプ)となった理由が分かりましたね。
fibの再帰が深すぎて、スタックオーバーフローしています。ulimitというものを使うとスタックサイズを増やして、正常に実行することが出来ますが、どちらにせよ計算に時間がかかりすぎて、生きている間には終わりそうにありません。

取り合えずdecodeの処理を見てみれば不正が出来るかもしれません。
mainのdecode呼び出し前の処理を見てみましょう

0x000007b0 <+35>:	call   0x56d <fib>
0x000007b5 <+40>:	add    esp,0x10
0x000007b8 <+43>:	mov    DWORD PTR [ebp-0xc],eax
0x000007bb <+46>:	sub    esp,0xc
0x000007be <+49>:	push   DWORD PTR [ebp-0xc]
0x000007c1 <+52>:	call   0x5b8 <decode>

実は関数の戻り値は、eaxに入っています。（詳しくはさっきの関数呼び出しについてのサイトを見てね）
addは加算です。一つ目の変数に、二つ目の値を足す操作です。
movは代入です。一つ目の変数に、二つ目の値を代入します。
subは減算です。一つ目の変数から二つ目の値を引く操作です。
（厳密には変数とレジスタが違ったりとか色々する）
espはスタックの管理に使うレジスタなのでとりあえず気にしないことにします。
fib(0x53e691)の戻り値のeaxを、DWORD PTR [ebp-0xc]に移してから、decodeの引数として渡しているようです。
次はdecodeの処理を見てみましょう。

gdb-peda$ pdisas decode
Dump of assembler code for function decode:
...
   0x000005d5 <+29>:	mov    BYTE PTR [ebp-0x38],0x7b
   0x000005d9 <+33>:	mov    BYTE PTR [ebp-0x37],0xa7
   0x000005dd <+37>:	mov    BYTE PTR [ebp-0x36],0xfa
   0x000005e1 <+41>:	mov    BYTE PTR [ebp-0x35],0xb7
   0x000005e5 <+45>:	mov    BYTE PTR [ebp-0x34],0x61
   0x000005e9 <+49>:	mov    BYTE PTR [ebp-0x33],0xd8
   0x000005ed <+53>:	mov    BYTE PTR [ebp-0x32],0x8b
   0x000005f1 <+57>:	mov    BYTE PTR [ebp-0x31],0xc0
...

movが沢山ありますね。とりあえず整理してみましょう。BYTE PTRなので、一バイト(charに相当)ずつ、どこかに代入しているようです。ebp-0xXXは引数やローカル変数を表すことが多いです。数字も大きいですし、main関数の方にはこんなに沢山のpushも無かったので、恐らくローカル変数の配列に、一文字ずつ代入しているのでしょう。関数開始後、他の処理で使う前の処理なので、初期化と思って良いでしょう。

ここまでわかったことを纏めるとこうなります。（ちょっと省略）

void decode(int key)
{
...
    char buf[44] = { (char)0x7b,(char)0xa7,(char)0xfa,(char)0xb7,(char)0x61,(char)0xd8,(char)0x8b,(char)0xc0,(char)0x44,(char)0x92,(char)0xee,(char)0x9f,(char)0x67,(char)0xb9,(char)0xe4,(char)0x93,(char)0x71,(char)0x86,(char)0xcb,(char)0x85,(char)0x69,(char)0xd8,(char)0xc9,(char)0xaf,(char)0x2a,(char)0x98,(char)0xe4,(char)0x86,(char)0x1,(char)0x99,(char)0x8c,(char)0xaf,(char)0x3,(char)0xab,(char)0xc8,(char)0xa4,(char)0x79,(char)0xca,(char)0xc6,(char)0xf0,(char)0x0,(char)0x0,(char)0x0,(char)0x0 };

}
int main()
{
...
int a = fib(0x53e691);
decode(a);
...
}

decodeの引数名keyは適当につけました。僕はコードを見ているのでkeyだと分かるだけなのですが、説明しやすいのでこのままにしました。

この数列に対してどのような操作をしているか確認しましょう。

   0x00000685 <+205>:	lea    eax,[ebp-0x38]
   0x00000688 <+208>:	mov    ecx,DWORD PTR [eax]
   0x0000068a <+210>:	lea    eax,[ebp-0x38]
   0x0000068d <+213>:	xor    ecx,DWORD PTR [ebp+0x8]
   0x00000690 <+216>:	mov    DWORD PTR [eax],ecx
   0x00000692 <+218>:	add    DWORD PTR [ebp+0x8],0x1

leaはmovに似たようなものですが、値では無くてアドレスをそのまま取る操作です。
ebp+0x8は引数keyの位置です。ebp-0x38はbuf[0]です。
この部分は

int* eax = (int*)(&buf[0])
int ecx = *eax
eax = &buf[0]
ecx ^= key
*eax = ecx
key += 0x1

で、諸々を省略すると、

(*(int*)(&buf[0])) ^= key;
key += 1;

になります。
bufをcharの配列では無くて、intの配列として扱っているので、buf[0]～buf[3]までの4要素にかけて同時にxorを取っていることが分かります。

次を見てみましょう。

   0x00000696 <+222>:	lea    eax,[ebp-0x38]
   0x00000699 <+225>:	add    eax,0x4
   0x0000069c <+228>:	mov    ecx,DWORD PTR [eax]
   0x0000069e <+230>:	lea    eax,[ebp-0x38]
   0x000006a1 <+233>:	add    eax,0x4
   0x000006a4 <+236>:	xor    ecx,DWORD PTR [ebp+0x8]
   0x000006a7 <+239>:	mov    DWORD PTR [eax],ecx
   0x000006a9 <+241>:	add    DWORD PTR [ebp+0x8],0x1

add eax,0x4が加わっているだけで、先ほどと同じですね。先のと合わせるとこうなるでしょう。

(*(int*)(&buf[0])) ^= key;
key += 1;
(*(int*)(&buf[4])) ^= key;
key += 1;

どうやら、keyを少しずつ足しながら、4要素ずつ、keyでxorを取っているようです。

最後の処理を見てみましょう。

   0x00000765 <+429>:	sub    esp,0xc
   0x00000768 <+432>:	lea    eax,[ebp-0x38]
   0x0000076b <+435>:	push   eax
   0x0000076c <+436>:	mov    ebx,edx
   0x0000076e <+438>:	call   0x400 <puts@plt>
   0x00000773 <+443>:	add    esp,0x10
   0x00000776 <+446>:	nop
   0x00000777 <+447>:	mov    eax,DWORD PTR [ebp-0xc]
   0x0000077a <+450>:	xor    eax,DWORD PTR gs:0x14
   0x00000781 <+457>:	je     0x788 <decode+464>
   0x00000783 <+459>:	call   0x850 <__stack_chk_fail_local>
   0x00000788 <+464>:	mov    ebx,DWORD PTR [ebp-0x4]
   0x0000078b <+467>:	leave  
   0x0000078c <+468>:	ret    

puts@pltをebp-0x38、つまりbufを引数に呼び出しているようです。後ろの@pltはGOT overwriteというテクをするようになるとお世話になると思いますが、今はただのputsだと思っていてください。
nopは何もしない命令です。バイナリを直接書き換えるときにつじつま合わせに使うことが出来て便利です。（もちろん本来の用途ではないはず）
<+447>: mov eax,DWORD PTR [ebp-0xc]～<+459>: call 0x850 <__stack_chk_fail_local>は、スタックオーバーフローを検出するための定型文で、__から始まる名前から分かるように、コンパイラが勝手に埋め込むコードです。今回は無視しましょう。

というわけで、コードに書き起こすとこうなります。

int fib(int n)
{
	if (n <= 2) { return 1; }
	return fib(n - 1) + fib(n - 2);
}

void decode(int key)
{
    char buf[44] = { (char)0x7b,(char)0xa7,(char)0xfa,(char)0xb7,(char)0x61,(char)0xd8,(char)0x8b,(char)0xc0,(char)0x44,(char)0x92,(char)0xee,(char)0x9f,(char)0x67,(char)0xb9,(char)0xe4,(char)0x93,(char)0x71,(char)0x86,(char)0xcb,(char)0x85,(char)0x69,(char)0xd8,(char)0xc9,(char)0xaf,(char)0x2a,(char)0x98,(char)0xe4,(char)0x86,(char)0x1,(char)0x99,(char)0x8c,(char)0xaf,(char)0x3,(char)0xab,(char)0xc8,(char)0xa4,(char)0x79,(char)0xca,(char)0xc6,(char)0xf0,(char)0x0,(char)0x0,(char)0x0,(char)0x0 };

	*(int*)(buf + 0) ^= key;
	++key;
	*(int*)(buf + 4) ^= key;
	++key;
	*(int*)(buf + 8) ^= key;
	++key;
	*(int*)(buf + 12) ^= key;
	++key;
	*(int*)(buf + 16) ^= key;
	++key;
	*(int*)(buf + 20) ^= key;
	++key;
	*(int*)(buf + 24) ^= key;
	++key;
	*(int*)(buf + 28) ^= key;
	++key;
	*(int*)(buf + 32) ^= key;
	++key;
	*(int*)(buf + 36) ^= key;
	++key;
	puts(buf);
}

int main()
{
	int a = fib(0x53e691);
	decode(a);
}

後は遅い原因の、fib(0x53e691)を何とか計算してしまいましょう。フィボナッチ数列のn項目を何らかの方法で求めてしまえば良いです。ただし、int型に収まりきらないので、オーバーフローしているということに気を付けてください。
オーバーフローを考慮すると、一般項から計算したり、検索して直接値を知るよりは、フィボナッチ数列を高速に求めるコードを書いてしまった方が速いでしょう。

int fast_fibonacci(int n)
{
	int a = 1, b = 1;
	for (int i = 2; i < n; i++)
	{
		int c = b;
		b = a;
		a = b + c;
	}
	return a;
}

フィボナッチ数列は有名な問題なので、検索すればコードを見つけることが出来ると思います。ただ、これくらいのコードを自分で書けるようになっておくと便利だと思います。

fib関数を、上のfast_fibonacciに置き換えれば、ちゃんとフラグを計算できそうです。
最終的にはこうなります。
コード

お疲れさまでした。

ちなみに強い人によると、

• fibが遅い
• fib(0x53e691)を呼び出している
• fib(0x53e691)の戻り値が0xf0bbeb3dである

まで分かれば、
b main
r
set $pc=0x.....7b8(プログラムの実行位置を強制的にfibの呼び出し直後の位置(main + 43)にする。rの後にdisas mainしてアドレスを確かめると良いです。)
set $eax=0xf0bbeb3d(戻り値を偽装)
で解けるらしいです。なるほど。

明日は onkyi さんの記事です。お楽しみに！