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.

なんかよく分からん文字列が出力された.

gdb を使って, main を逆アセンブルする.

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 が得られた.

参考文献