picoCTF 2018: be-quick-or-be-dead-2
問題
問題文
As you enjoy this music even more, another executable be-quick-or-be-dead-2 shows up. Can you run this fast enough too? You can also find the executable in /problems/be-quick-or-be-dead-2_2_7e92e9cc48bad623da1c215c192bc919.
Hints
Can you call stuff without executing the entire program?
What will the key finally be?
問題概要
x64 の ELFファイルが与えられる.
解答例
指針
- 頑張って解析する
解説
まずは file コマンドにかける.
$ file be-quick-or-be-dead-2 be-quick-or-be-dead-2: setgid ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=a6670d34bc3d40dbbfd48cf8da5450cf4633ada7, not stripped
x64 の ELF ファイルだと分かった.
次に実際にプログラムを実行してみる.
$ ./be-quick-or-be-dead-2 Be Quick Or Be Dead 2 ===================== Calculating key... You need a faster machine. Bye bye.
なんかよく分からん文字列が出力された.
set disassembly-flavor intel とすると, Intel記法で表示してくれる.
$ gdb -q be-quick-or-be-dead-2 Reading symbols from be-quick-or-be-dead-2...(no debugging symbols found)...done. (gdb) set disassembly-flavor intel (gdb) start Temporary breakpoint 1 at 0x400863 Starting program: /problems/be-quick-or-be-dead-2_2_7e92e9cc48bad623da1c215c192bc919/be-quick-or-be-dead-2 Temporary breakpoint 1, 0x0000000000400863 in main () (gdb) disas main Dump of assembler code for function main: 0x000000000040085f <+0>: push rbp 0x0000000000400860 <+1>: mov rbp,rsp => 0x0000000000400863 <+4>: sub rsp,0x10 0x0000000000400867 <+8>: mov DWORD PTR [rbp-0x4],edi 0x000000000040086a <+11>: mov QWORD PTR [rbp-0x10],rsi 0x000000000040086e <+15>: mov eax,0x0 0x0000000000400873 <+20>: call 0x400821 <header> 0x0000000000400878 <+25>: mov eax,0x0 0x000000000040087d <+30>: call 0x40077a <set_timer> 0x0000000000400882 <+35>: mov eax,0x0 0x0000000000400887 <+40>: call 0x4007ce <get_key> 0x000000000040088c <+45>: mov eax,0x0 0x0000000000400891 <+50>: call 0x4007f9 <print_flag> 0x0000000000400896 <+55>: mov eax,0x0 0x000000000040089b <+60>: leave 0x000000000040089c <+61>: ret End of assembler dump. (gdb)
print_flag というありがたい関数があるのでそこへ処理を飛ばしてみる.
(gdb) jump *main+45 Continuing at 0x40088c. Printing flag: ▒n▒▒U▒,▒▒~▒_▒;▒P▒9▒▒y▒)▒o▒;▒U▒ ▒U▒ [Inferior 1 (process 2722) exited normally]
flag は得られなかった. 直前にある get_key という関数を先に呼ぶ必要があると推測し, そこへ処理を飛ばしてみる.
(gdb) start Temporary breakpoint 2 at 0x400863 Starting program: /problems/be-quick-or-be-dead-2_2_7e92e9cc48bad623da1c215c192bc919/be-quick-or-be-dead-2 Temporary breakpoint 2, 0x0000000000400863 in main () (gdb) jump *main+35 Continuing at 0x400882. Calculating key...
今度も Calculationg key... という表示されるだけで flag は得られなかった.
真面目にプログラムを解析していく.
print_flag を逆アセンブルしてみる.
(gdb) disas print_flag Dump of assembler code for function print_flag: 0x00000000004007f9 <+0>: push rbp 0x00000000004007fa <+1>: mov rbp,rsp 0x00000000004007fd <+4>: mov edi,0x4009e0 0x0000000000400802 <+9>: call 0x400530 <puts@plt> 0x0000000000400807 <+14>: mov eax,DWORD PTR [rip+0x2008b3] # 0x6010c0 <key> 0x000000000040080d <+20>: mov edi,eax 0x000000000040080f <+22>: call 0x400696 <decrypt_flag> 0x0000000000400814 <+27>: mov edi,0x601080 0x0000000000400819 <+32>: call 0x400530 <puts@plt> 0x000000000040081e <+37>: nop 0x000000000040081f <+38>: pop rbp 0x0000000000400820 <+39>: ret End of assembler dump.
0x6010c0 番地の key という変数を引数としてとり, decrypt_flag を実行している.
最初, print_flag に処理を飛ばしたとき, 正しい flag が得られなかったのは key が正しくなかったからだと推測できる.
次におそらく key を得るための関数である get_key を逆アセンブルしてみる.
(gdb) disas get_key Dump of assembler code for function get_key: 0x00000000004007ce <+0>: push rbp 0x00000000004007cf <+1>: mov rbp,rsp 0x00000000004007d2 <+4>: mov edi,0x4009b8 0x00000000004007d7 <+9>: call 0x400530 <puts@plt> 0x00000000004007dc <+14>: mov eax,0x0 0x00000000004007e1 <+19>: call 0x40074b <calculate_key> 0x00000000004007e6 <+24>: mov DWORD PTR [rip+0x2008d4],eax # 0x6010c0 <key> 0x00000000004007ec <+30>: mov edi,0x4009cb 0x00000000004007f1 <+35>: call 0x400530 <puts@plt> 0x00000000004007f6 <+40>: nop 0x00000000004007f7 <+41>: pop rbp 0x00000000004007f8 <+42>: ret End of assembler dump.
内部で calculate_key を実行し, 返ってきた値を key に代入している.
calculate_key を逆アセンブルしてみる.
(gdb) disas calculate_key Dump of assembler code for function calculate_key: 0x000000000040074b <+0>: push rbp 0x000000000040074c <+1>: mov rbp,rsp 0x000000000040074f <+4>: mov edi,0x402 0x0000000000400754 <+9>: call 0x400706 <fib> 0x0000000000400759 <+14>: pop rbp 0x000000000040075a <+15>: ret End of assembler dump.
0x402 を引数として fib という関数に渡している.
fib を逆アセンブルしてみる.
(gdb) disas fib Dump of assembler code for function fib: 0x0000000000400706 <+0>: push rbp 0x0000000000400707 <+1>: mov rbp,rsp 0x000000000040070a <+4>: push rbx 0x000000000040070b <+5>: sub rsp,0x28 0x000000000040070f <+9>: mov DWORD PTR [rbp-0x24],edi 0x0000000000400712 <+12>: cmp DWORD PTR [rbp-0x24],0x1 0x0000000000400716 <+16>: ja 0x400720 <fib+26> 0x0000000000400718 <+18>: mov eax,DWORD PTR [rbp-0x24] 0x000000000040071b <+21>: mov DWORD PTR [rbp-0x14],eax 0x000000000040071e <+24>: jmp 0x400741 <fib+59> 0x0000000000400720 <+26>: mov eax,DWORD PTR [rbp-0x24] 0x0000000000400723 <+29>: sub eax,0x1 0x0000000000400726 <+32>: mov edi,eax 0x0000000000400728 <+34>: call 0x400706 <fib> 0x000000000040072d <+39>: mov ebx,eax 0x000000000040072f <+41>: mov eax,DWORD PTR [rbp-0x24] 0x0000000000400732 <+44>: sub eax,0x2 0x0000000000400735 <+47>: mov edi,eax 0x0000000000400737 <+49>: call 0x400706 <fib> 0x000000000040073c <+54>: add eax,ebx 0x000000000040073e <+56>: mov DWORD PTR [rbp-0x14],eax 0x0000000000400741 <+59>: mov eax,DWORD PTR [rbp-0x14] 0x0000000000400744 <+62>: add rsp,0x28 0x0000000000400748 <+66>: pop rbx 0x0000000000400749 <+67>: pop rbp 0x000000000040074a <+68>: ret End of assembler dump.
関数名からも推測できるようにフィボナッチ数列の第n項を再帰的に求めているっぽい.
再帰によるフィボナッチ数の計算は指数時間のアルゴリズムであることが知られている.
この程度なら gdb だけでも解析できそうだが楽をするためにリバースエンジニアリングツールである Ghidra を使ってみた.
以下が Ghidra によって fib をデコンパイルした結果である.
ulong fib(uint uParm1)
{
int iVar1;
int iVar2;
uint local_1c;
local_1c = uParm1;
if (1 < uParm1) {
iVar1 = fib((ulong)(uParm1 - 1));
iVar2 = fib((ulong)(uParm1 - 2));
local_1c = iVar2 + iVar1;
}
return (ulong)local_1c;
}
フィボナッチ数列の 0x402 項目の下位 32 bit を求める.
#!/usr/bin/env python3 def fib(a): L = [0, 1] for i in range(a): L += [ L[-1] + L[-2] ] return L[a] print( fib(0x402) & 2**32-1 )
- 実行結果
$ python fib.py 4144667480
print_flag が実行される直前に breakpoint を仕掛け, 処理をそこへ飛ばす.
(gdb) b *main+45 Breakpoint 3 at 0x40088c (gdb) jump *main+45 Continuing at 0x40088c. Breakpoint 3, 0x000000000040088c in main () (gdb) disas Dump of assembler code for function main: 0x000000000040085f <+0>: push rbp 0x0000000000400860 <+1>: mov rbp,rsp 0x0000000000400863 <+4>: sub rsp,0x10 0x0000000000400867 <+8>: mov DWORD PTR [rbp-0x4],edi 0x000000000040086a <+11>: mov QWORD PTR [rbp-0x10],rsi 0x000000000040086e <+15>: mov eax,0x0 0x0000000000400873 <+20>: call 0x400821 <header> 0x0000000000400878 <+25>: mov eax,0x0 0x000000000040087d <+30>: call 0x40077a <set_timer> 0x0000000000400882 <+35>: mov eax,0x0 0x0000000000400887 <+40>: call 0x4007ce <get_key> => 0x000000000040088c <+45>: mov eax,0x0 0x0000000000400891 <+50>: call 0x4007f9 <print_flag> 0x0000000000400896 <+55>: mov eax,0x0 0x000000000040089b <+60>: leave 0x000000000040089c <+61>: ret End of assembler dump.
key が格納されているメモリの値を書き換える.
(gdb) set {int}0x6010c0=4144667480
(gdb) c
Continuing.
Printing flag:
picoCTF{the_fibonacci_sequence_can_be_done_fast_7e188834}
[Inferior 1 (process 672716) exited normally]
flag が得られた.
