picoCTF2018: be-quick-or-be-dead-1

CTF Reversing picoCTF2018 Baby

問題

問題文

You find this when searching for some music, which leads you to be-quick-or-be-dead-1. Can you run it fast enough? You can also find the executable in /problems/be-quick-or-be-dead-1_3_aeb48854203a88fb1da963f41ae06a1c.

問題概要

  • x64のELFファイルが与えられる.

解答例

指針

  • gdb 等のデバッガで解析する

解説

wget で Download

$ wget --no-check-certificate https://2018shell.picoctf.com/static/f825b5db114de1d3f811961b54f9cfb1/be-quick-or-be-dead-1

file コマンドにかける.

$ file be-quick-or-be-dead-1
be-quick-or-be-dead-1: 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]=964fafdb7917666756318df97478ea539c4a3725, not stripped

実行権限を付与して実行.

$ chmod +x be-quick-or-be-dead-1
$ ./be-quick-or-be-dead-1
Be Quick Or Be Dead 1
=====================

Calculating key...
You need a faster machine. Bye bye.

gdb で main を逆アセンブル.

$ gdb -q ./be-quick-or-be-dead-1
Reading symbols from ./be-quick-or-be-dead-1...(no debugging symbols found)...done.
(gdb) set disassembly-flavor intel
(gdb) start
Temporary breakpoint 1 at 0x40082b
Starting program: /home/kira/work/pico/be-quick-or-be-dead-1

Temporary breakpoint 1, 0x000000000040082b in main ()
(gdb) disas
Dump of assembler code for function main:
   0x0000000000400827 <+0>:     push   rbp
   0x0000000000400828 <+1>:     mov    rbp,rsp
=> 0x000000000040082b <+4>:     sub    rsp,0x10
   0x000000000040082f <+8>:     mov    DWORD PTR [rbp-0x4],edi
   0x0000000000400832 <+11>:    mov    QWORD PTR [rbp-0x10],rsi
   0x0000000000400836 <+15>:    mov    eax,0x0
   0x000000000040083b <+20>:    call   0x4007e9 <header>
   0x0000000000400840 <+25>:    mov    eax,0x0
   0x0000000000400845 <+30>:    call   0x400742 <set_timer>
   0x000000000040084a <+35>:    mov    eax,0x0
   0x000000000040084f <+40>:    call   0x400796 <get_key>
   0x0000000000400854 <+45>:    mov    eax,0x0
   0x0000000000400859 <+50>:    call   0x4007c1 <print_flag>
   0x000000000040085e <+55>:    mov    eax,0x0
   0x0000000000400863 <+60>:    leave
   0x0000000000400864 <+61>:    ret
End of assembler dump.

main内で, header, set_timer, get_key, print=flag という関数が呼ばれていることが分かった.

gdb で header を逆アセンブル.

(gdb) disas header
Dump of assembler code for function header:
   0x00000000004007e9 <+0>:     push   rbp
   0x00000000004007ea <+1>:     mov    rbp,rsp
   0x00000000004007ed <+4>:     sub    rsp,0x10
   0x00000000004007f1 <+8>:     mov    edi,0x4009c0
   0x00000000004007f6 <+13>:    call   0x400530 <puts@plt>
   0x00000000004007fb <+18>:    mov    DWORD PTR [rbp-0x4],0x0
   0x0000000000400802 <+25>:    jmp    0x400812 <header+41>
   0x0000000000400804 <+27>:    mov    edi,0x3d
   0x0000000000400809 <+32>:    call   0x400520 <putchar@plt>
   0x000000000040080e <+37>:    add    DWORD PTR [rbp-0x4],0x1
   0x0000000000400812 <+41>:    mov    eax,DWORD PTR [rbp-0x4]
   0x0000000000400815 <+44>:    cmp    eax,0x14
   0x0000000000400818 <+47>:    jbe    0x400804 <header+27>
   0x000000000040081a <+49>:    mov    edi,0x4009d6
   0x000000000040081f <+54>:    call   0x400530 <puts@plt>
   0x0000000000400824 <+59>:    nop
   0x0000000000400825 <+60>:    leave
   0x0000000000400826 <+61>:    ret
End of assembler dump.

header 文字列を出力しているだけっぽい.

set_timer を逆アセンブル.

(gdb) disas set_timer
Dump of assembler code for function set_timer:
   0x0000000000400742 <+0>:     push   rbp
   0x0000000000400743 <+1>:     mov    rbp,rsp
   0x0000000000400746 <+4>:     sub    rsp,0x10
   0x000000000040074a <+8>:     mov    DWORD PTR [rbp-0xc],0x1
   0x0000000000400751 <+15>:    mov    esi,0x400723
   0x0000000000400756 <+20>:    mov    edi,0xe
   0x000000000040075b <+25>:    call   0x400570 <__sysv_signal@plt>
   0x0000000000400760 <+30>:    mov    QWORD PTR [rbp-0x8],rax
   0x0000000000400764 <+34>:    cmp    QWORD PTR [rbp-0x8],0xffffffffffffffff
   0x0000000000400769 <+39>:    jne    0x400789 <set_timer+71>
   0x000000000040076b <+41>:    mov    esi,0x3b
   0x0000000000400770 <+46>:    mov    edi,0x400928
   0x0000000000400775 <+51>:    mov    eax,0x0
   0x000000000040077a <+56>:    call   0x400540 <printf@plt>
   0x000000000040077f <+61>:    mov    edi,0x0
   0x0000000000400784 <+66>:    call   0x400580 <exit@plt>
   0x0000000000400789 <+71>:    mov    eax,DWORD PTR [rbp-0xc]
   0x000000000040078c <+74>:    mov    edi,eax
   0x000000000040078e <+76>:    call   0x400550 <alarm@plt>
   0x0000000000400793 <+81>:    nop
   0x0000000000400794 <+82>:    leave
   0x0000000000400795 <+83>:    ret

alarm 関数を使って, timer を設定してるっぽい.

get_key を逆アセンブルしてみる.

Dump of assembler code for function get_key:
   0x0000000000400796 <+0>:     push   rbp
   0x0000000000400797 <+1>:     mov    rbp,rsp
   0x000000000040079a <+4>:     mov    edi,0x400988
   0x000000000040079f <+9>:     call   0x400530 <puts@plt>
   0x00000000004007a4 <+14>:    mov    eax,0x0
   0x00000000004007a9 <+19>:    call   0x400706 <calculate_key>
   0x00000000004007ae <+24>:    mov    DWORD PTR [rip+0x20090c],eax        # 0x6010c0 <key>
   0x00000000004007b4 <+30>:    mov    edi,0x40099b
   0x00000000004007b9 <+35>:    call   0x400530 <puts@plt>
   0x00000000004007be <+40>:    nop
   0x00000000004007bf <+41>:    pop    rbp
   0x00000000004007c0 <+42>:    ret
End of assembler dump.

内部で, calculate_key 関数を呼んでいる. calculate_key の戻り値を 0x6010c0 番地の 変数 key に格納している.

calculate_key を逆アセンブルしてみる.

(gdb) disas calculate_key
Dump of assembler code for function calculate_key:
   0x0000000000400706 <+0>:     push   rbp
   0x0000000000400707 <+1>:     mov    rbp,rsp
   0x000000000040070a <+4>:     mov    DWORD PTR [rbp-0x4],0x6fd47e3c
   0x0000000000400711 <+11>:    add    DWORD PTR [rbp-0x4],0x1
   0x0000000000400715 <+15>:    cmp    DWORD PTR [rbp-0x4],0xdfa8fc78
   0x000000000040071c <+22>:    jne    0x400711 <calculate_key+11>
   0x000000000040071e <+24>:    mov    eax,DWORD PTR [rbp-0x4]
   0x0000000000400721 <+27>:    pop    rbp
   0x0000000000400722 <+28>:    ret
End of assembler dump.

x86/64 では, 関数の戻り値は eax レジスタに格納される. eax レジスタの値は, [rbp-0x4] であり, [rbp-0x4] の値の初期値は, 0x6fd47e3c で, 0xdfa8fc78 と等しくなるまでインクリメントされていることが分かる.

したがって, caluculate_key を単に, 0xdfa8fc78 を返すようにバイナリパッチを当てるか, あるいは gdb で, メモリの値を書き変えることでこの問題を解けそうである. なお, バイナリパッチを当てる場合は, Ghidra, IDA, Binary Ninja, Cutter などのリバースエンジニアリングフレームワークを使うのが楽だろう.

今回は後者の方法を取る.

(gdb) start
(gdb) set {int}0x6010c0=0xdfa8fc78
(gdb) jump *main+45
Continuing at 0x400854.
Printing flag:
picoCTF{why_bother_doing_unnecessary_computation_27f28e71}
[Inferior 1 (process 25475) exited normally]

ちなみに高速化をしない場合の calculate_key で回るループの回数は, \text{0xdfa8fc78} - \text{0x6fd47e3c} = 1876196924 \cong 1.88 \cdot 10^{9} であり, set_timer を呼ぶ処理を飛ばせば, 普通に計算しても大した時間がかからずに key を計算してくれるので, flag を得ることはできる.

(gdb) start
Temporary breakpoint 5, 0x000000000040082b in main ()
(gdb) disas
Dump of assembler code for function main:
   0x0000000000400827 <+0>:     push   rbp
   0x0000000000400828 <+1>:     mov    rbp,rsp
=> 0x000000000040082b <+4>:     sub    rsp,0x10

   ...
   
   0x000000000040084a <+35>:    mov    eax,0x0
   0x000000000040084f <+40>:    call   0x400796 <get_key>
   0x0000000000400855 <+45>:    mov    eax,0x0
   0x0000000000400859 <+50>:    call   0x4007c1 <print_flag>
   ...
(gdb) jump *main+35
Continuing at 0x40084a.
Calculating key...
Done calculating key
Printing flag:
picoCTF{why_bother_doing_unnecessary_computation_27f28e71}
[Inferior 1 (process 25655) exited normally]

flag: picoCTF{why_bother_doing_unnecessary_computation_27f28e71}