題目
BCTF 2015中的題目,名爲CamlMaze。向解出此題的217、PPP、Gallopsled、Dragon Sector表達祝賀。
描述:
Caml has found a foggy maze. Please direct him to find the gold.
The source code of Caml Featherweight may be helpful.
本題是字節碼逆向題,供選手下載的user.tgz包含camlfwrun(字節碼解釋器)、bytecode(字節碼,是一段客戶端程序,用我的Caml
Featherweight編譯生成)、camlfwod(用ocamlrun執行的字節碼查看器,名字來源於objdump)。和Caml
Featherweight相比,camlfwrun經過了少許修改,在解釋前會向服務端創建socket,是爲了適配交互式逆向/pwn類CTF題目,靜態編譯,已被strip -s。
名字中的Caml源於Categorical Abstract Machine Language,一個ML語言的方言。
使用./camlfwrun -s $SERVER_HOST -p $SERVER_PORT bytecode連接服務端,可以看到如下的輸出信息:
1 | Sample: |
解題報告
根據樣例可以瞭解到題目希望我們提供從左上角的@到$的移動路線。而實際要求解的迷宮中很多地方被擋住了,無法看到牆壁的位置。根據提示可以知道我們應該去除迷霧,顯示更多的塊。
用strace或調試器等方法記錄camlfwrun解釋字節碼時所用的系統調用,可以發現有以下幾個階段:
- 若干從文件描述符4讀取的
read系統調用,4是字節碼文件 - 向stdout輸出樣例信息
- 向文件描述符3(和服務端通信的socket)輸出字串
"5"和'\n' - 向文件描述符3讀入很多01字符
- 向stdout輸出Challenge信息
- 向stdin讀入(左上到右下的路徑),轉發給文件描述符3
- 從文件描述符3讀取一行字串顯示到stdout
其中第3步輸出的字串"5"和'\n'很可疑。
可以猜測這個5在和服務端的通信過程中有重要的作用(腦洞大的可以聯想到Challenge中顯示的片數也是5),自然的想法是把5改成其他數。方法是用catch syscall write和condition命令在第一次向文件描述符3執行write系統調用的地方停下來。根據Linux
x86的系統調用約定,ebx ecx
edx存放了系統調用的前三個參數,因此ecx儲存的是const void *buf。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23(gdb) cat sys write
Catchpoint 1 (syscall 'write' [4])
(gdb) cond 1 $ebx == 3
(gdb) r
Sample:
.@._._._.
|_. |_. |
| |_. | |
| . |_. |
|_|_._. |
$
You need to input: drdrdrdd
Catchpoint 1 (call to syscall write), 0xf7ffdbf0 in __kernel_vsyscall ()
(gdb) i r ebx # int fd
ebx 0x3 3
(gdb) i r ecx # const void *buf
ecx 0xffffb1ef -19985
(gdb) x/s $ecx
0xffffb1ef: "5\001"
(gdb) i r edx # size_t count
edx 0x1 1
(gdb)
可以用set {TYPE}ADDRESS修改緩衝區的值。比如把5修改成9:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22(gdb) cat sys write
Catchpoint 1 (syscall 'write' [4])
(gdb) cond 1 $ebx == 3
(gdb) r
Sample:
.@._._._.
|_. |_. |
| |_. | |
| . |_. |
|_|_._. |
$
You need to input: drdrdrdd
Catchpoint 1 (call to syscall write), 0xf7fdabf0 in __kernel_vsyscall ()
(gdb) set {char}$ecx='9'
(gdb) d
(gdb) c
Continuing.
Program received signal SIGPIPE, Broken pipe.
0xf7fdabf0 in __kernel_vsyscall ()
(gdb)
被調試進程收到了SIGPIPE,原因是交互時間太長(測試可以發現服務端允許的最長交互時間是5秒),服務端已經關閉了socket連接。因此需要快速地執行這一過程,可以用gdb的-x批量執行命令,下面的命令使用了zsh的process
substitution語法: 1
gdb -batch -x =(echo "cat sys write\ncond 1 \$ebx==3\nr\nset {char}\$ecx='9'\ndetach") --args ./camlfwrun bytecode
觀察到: 1
2
3Challenge:
Fatal error: uncaught exception
.@._._._._. ._._._._._. I find your trick... I'm tamper-resistant!
執行strings bytecode可以發現文本I find your trick...說明字節碼中有防篡改代碼。之後有幾種解題思路。
突破口(簡單):字節碼字符串表示方式
./camlfwod bytecode除了列示字節碼外,還會顯示字節碼中用到的一些常量。輸出的"5\n"也在裏面:
1
2
3
4
5
6
7Global value: 27
...
4:
header: 000002fc
tag: string
size: 1
string: 5\n
使用grep -abo 5 bytecode找出這個字串的偏移3786。
1
2% xxd -s3786 -l16 bytecode
00000eca: 350a 0202 0101 0000 0001 0100 0000 0101 5...............
把0x35(字符5)改成0x39(字符9)可以發現迷宮顯示的片數變成了9。研究Caml
Featherweight實現中runtime/str.c的文件,或者經過一些修改的試錯過程,可以發現字符串採用了類似PKCS#7的padding方式,35
0a 02 02後面的02
02是指有兩個字符是padding,不應算入字符串長度。把它改成35 32 0a
01就能把"5\n"改成"25\n"了: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18% diff -u <(./camlfwod bytecode) <(./camlfwod bytecode.5_to_25)
--- /proc/self/fd/11 2015-03-23 22:30:52.792336505 +0800
+++ /proc/self/fd/12 2015-03-23 22:30:52.795669838 +0800
@@ -1,4 +1,4 @@
-File bytecode
+File /tmp/bytecode
Executable
Length 3749
@@ -2222,7 +2222,7 @@
header: 000002fc
tag: string
size: 1
- string: 5\n
+ string: 25\n
5:
int: 0
6:
Ruby的proof-of-concept exploit可參考https://github.com/MaskRay/BCTF2015-CamlMaze/blob/master/poc.rb。
突破口(困難):去除防篡改代碼
camlfwrun在輸出I find your trick...時候,還輸出了Fatal error: uncaught exception。
兩個思路,一是反編譯camlfwrun並試圖看懂它的邏輯,二是編譯我的Caml
Featherweight得到camlfwrun,它與user.tgz裏的camlfwrun基本相同。假設選擇反編譯,可以發現Fatal error這段文本是由下面代碼產生的:
1
2
3
4
5
6switch ( sub_804A79E(a2[optind]) )
{
......
case -6:
sub_8048BF1((unsigned int)"Fatal error: uncaught exception");
return result;
然後查找返回值-6產生的源頭,從函數sub_804A79E出發,追溯到函數sub_80493F9中如下部分的代碼:
1
2
3
4
5
6
7
8
9
10
11
12
13LABEL_162:
if ( v104 )
{
v72 = v104;
v101 = *(_DWORD *)v104;
i = (int *)sub_8048E71(*(_DWORD *)(v104 + 4), 1);
i[2] = v108;
v106 = *(_DWORD *)(v104 + 8);
v104 = *(_DWORD *)(v104 + 12);
v105 = v72 + 16;
continue;
}
return -6;
下面的代碼則可能會跳轉到LABEL_162: 1
2
3
4
5
6
7
8
9
10case 0x1B:
v22 = v106;
v106 += 4;
if ( *(_DWORD *)v22 == 1 )
{
v108 = (int)&unk_804D504;
goto LABEL_162;
}
v108 = 2 * ((v108 - 1) / (*(_DWORD *)v22 - 1)) + 1;
continue;
0x1B是DIVINT指令的opcode,用./camlfwod bytecode也能找到唯一一處出現的DIVINT指令:
1
2
3
4
5
6...
0aeb: PUSH
0aec: ACCESS 1
0aee: DIVINT
0aef: RETURN
...0/0,在解釋器中觸發了異常。
查看Caml
Featherweight源碼,可以發現opcode.ml(由runtime/instruct.h生成)編碼了各種指令的opcode:
1
2
3
4
5...
let opDIVINT=27
...
let opMULINT=60
...
把bytecode文件偏移0xaee處的0x1b改成0x3c即可把DIVINT指令換成無害的MULINT指令。另外最好在write系統調用後把緩衝區恢復原狀,以免觸發其他的防篡改代碼。方法是修改完緩衝區後執行finish命令,實際系統調用執行完畢後恢復緩衝區字串的原值:gdb -batch -x =(echo "cat sys write\ncond 1 \$ebx==3\nr\nset {char}\$ecx='9'\nfin\nset {char}\$ecx='2'\ndetach") --args ./camlfwrun bytecode.DIVINT2MULINT。從命令輸出中可以看到:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27Challenge:
.@._._._._. ._._._._._. I find your trick... I'm tamper-resistant!
|_. | ._._.###################._._._._. |##########
| ._|_. | .###################._. | . | |##########
| | . | | |###################. | |_| |_.##########
|_._| |_. |###################| | | ._| .##########
| ._|_. |_._# #_# #_##########|_._| | ._|_# # #_# #
|_. . | | . |_| ._| .###################. | |_._. |
| ._|_|_._|_. | | ._|###################|_._| ._._|
| | ._._. . | | | | .###################| ._._| . |
| | ._| ._| |_._|_. .###################._|_. . |_|
|_._| ._|_. | ._. |_|###################._. |_|_. |
| . |_._. |#############################|_._._._. |
| |_._._._|#############################. | ._. | |
| |_. . | .#############################| | . |_| |
|_. | | |_.#############################._| |_. | |
| ._| | ._|#############################._._| |_._|
#######################################|_._. | . |
#######################################._. |_._| |
#######################################. |_. | ._|
#######################################|_. | | . |
#######################################._._| |_| |
#######################################| . |_._. |
#######################################._|_._. | |
#######################################._. |_._| |
#######################################._._| . | |
#######################################._._._|_. |
這裏stdout和stderr被混在一起。I find your trick...依然被輸出了,但不再導致程序中途退出,並且迷宮顯示的片數從5增加到了9。實際上DIVINT的作用僅僅是觸發異常,從而讓解釋器產生特徵文本Fatal error: uncaught exception。
我們還可以把9換成25,這樣就能看到迷宮全景了: 1
gdb -batch -x =(echo "cat sys write\ncond 1 \$ebx==3\nr\nset {char}\$ecx='2'\nset {char}(\$ecx+1)='5'\nset \$edx=2\ndetach") --args ./camlfwrun bytecode.DIVINT2MULINT
得到迷宮全景後接下來要做的事就很清晰了,我們需要編寫一段程序求解迷宮,生成urdl四個方向的路徑作爲Path?的應答。gdb不能再直接detach了,需要把迷宮信息傳遞給一個外部程序求解,得到路徑後再提供給被調試的程序(camlfwrun)。
另外一個需要注意的是camlfwrun使用putchar進行輸出,glibc的stdout接到終端設備上時是行緩衝,否則是全緩衝。camlfwrun輸出時會調用putchar,但沒有flush。因此寫exploit腳本和它交互時注意把的輸出接到pty設備。而輸入可以用簡單的進程間通信方式,比如fifo。下面是一個Ruby的POC程序a.rb,創建一個pty設備和一個fifo和被調試的camlfwrun通信,從pty設備獲取迷宮信息,計算得到路徑後輸出到fifo。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#encoding: ascii-8bit
require 'pty'
read = ->h,re,*noout {
s = ''
re = Regexp.new Regexp.quote(re) unless re.is_a? Regexp
loop do
s << h.getc
break if s =~ re
end
print s if noout.empty?
$1 ? $1 : s
}
master, slave = PTY.open
slave.close
STDERR.puts "pty: #{slave.path}"
STDOUT.reopen '/tmp/fifo', 'w'
gets # 暫停,gdb調試的程序運行後按回車
n = 25 # size of maze
read.(master, "Challenge:\r\n", true)
g = read.(master, /.*\$\r\n/, true).sub("I find your trick...", '').lines
v = {}
act = ''
STDERR.puts g
dfs = ->r, c {
return false if v[r*n+c]
v[r*n+c] = true
return true if r == n && c == n-1
4.times {|d|
rr = r+[-1,0,1,0][d]
cc = c+[0,1,0,-1][d]
next unless 0 <= rr && rr < n && 0 <= cc && cc < n || rr == n && cc == n-1 && ! v[rr*n+cc]
if rr == r ? r == -1 || g[r+1][[c,cc].max*2] != '|' : g[[r,rr].max][c*2+1] != '_'
if dfs.(rr, cc)
act << 'urdl'[d]
return true
end
end
}
false
}
dfs[-1,0]
STDERR.puts act.reverse
puts act.reverse
STDOUT.flush
begin
while l = master.gets
STDERR.write l
end
rescue Errno::EIO
end
1 | % mkfifo /tmp/fifo |
記下Ruby創建的pty設備的路徑,在另一個窗口執行gdb -batch -x =(echo "cat sys write\ncond 1 \$ebx==3\nr /tmp/a >/dev/pts/12 </tmp/fifo\nset {char}\$ecx='2'\nset {char}(\$ecx+1)='5'\nset \$edx=2\nfin\nset {char}\$ecx='5'\nset {char}(\$ecx+1)=2") --args ./camlfwrun。注意把命令中的/dev/pts/12替換成pty設備路徑。然後在ruby a.rb窗口按回車,即可看到flag。
突破口(麻煩):篡改接收到的迷宮信息
還記得有一個階段是“向文件描述符3讀入很多01字符”吧,不難發現01字符用於描述迷宮中牆和迷霧的位置。模仿服務端收發的數據可以自己僞造一個服務端,通過試錯可以解讀01串的含義。其實可以發現01串分爲三段:
- 25*25個01字符,表示各個格子的右邊是否爲牆
- 25*25個01字符,表示各個格子的下邊是否爲牆
- 25*25個01字符,表示各個格子是否被迷霧遮擋
之後再自己實現一個客戶端,根據前兩段信息繪製迷宮即可,不考慮迷霧遮擋。
但各個01串都用fast Reed-Muller
transform處理過了(server和bytecode都有這段邏輯),不容易理解這些字符的含義。能看懂Zinc字節碼理解這段邏輯、並編寫出相應客戶端也能得分。或者另外寫一段Caml
Featherweight代碼,編譯,並把這段字節碼移植進去(好比把一段C代碼和objdump出來的彙編混合編譯)。生成bytecode的client.ml中相關代碼爲:
1
2
3
4
5
6
7
8
9
10
11
12
13
14let reed_muller_transform a =
for ldm = 10 downto 1 do
let m = 1 lsl ldm in
let mh = m lsr 1 in
let rec go i j =
if j = mh then
go (i+m) 0
else if i < 1024 then (
a.(i+j+mh) <- a.(i+j) lxor a.(i+j+mh);
go i (j+1)
)
in
go 0 0
done
突破口(PPP)
https://github.com/pwning/public-writeup/blob/master/bctf2015/rev450-camlmaze/writeup.md
運行時會產生三個較大的堆對象:表示各個格子右邊是否爲牆的數組、表示各個格子下邊是否爲牆的數組、表示各個格子是否被迷霧遮擋的數組。從服務端接收到的數組是經過編碼的,但bytecode在運行時會原地把它還原,因此導出這三個堆對象即可。
數組長度爲1024(爲了fast Reed-Muller
transform,提升到最小的2的冪),每個元素爲0或1,運行時表示爲1或3(實際上是tagged
pointer,每個數\(x\)儲存爲\(2x+1\))。數組首元素前的int32是用於垃圾收集的字段,通常爲0。因此可以用這樣的正則表達式提取:/\0\0\0\0((?:[\1\3]\0\0\0){1024})/。
之後可以不停修改解碼後的這三個數組,觀察出含義。
下面給出一個列出所有分配的堆對象的方法。編輯preload.c:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
static size_t len = 0;
static void *ps[N+1];
static size_t ss[N+1];
static void *(*real_malloc)(size_t) = NULL;
__attribute__((constructor)) void init(void)
{
real_malloc = dlsym(RTLD_NEXT, "malloc");
}
void *malloc(size_t size)
{
void *ptr = real_malloc(size), *p = ptr;
size_t i = len;
for (; i > 0 && ss[i-1] < size; i--) {
ps[i] = ps[i-1];
ss[i] = ss[i-1];
}
ps[i] = p;
ss[i] = size;
if (len < N) len++;
return ptr;
}
__attribute__((destructor)) void fini(void)
{
for (size_t i = 0; i < len; i++)
fprintf(stderr, "malloc(%zd) = %p\n", ss[i], ps[i]);
}
使用gcc -std=c11 -m32 preload.c -fpic -shared -ldl -o preload.so編譯。
先用sudo sysctl kernel/randomize_va_space=0關閉ASLR,之後使用LD_PRELOAD=./preload.so ./camlfwrun bytecode運行。stderr會顯示:
1
2
3
4
5
6
7
8
9
10malloc(100012) = 0xa00b8f8
malloc(16384) = 0x804e008
malloc(16384) = 0x8052010
malloc(4108) = 0x80575c0
malloc(4108) = 0x8a6a3a0
malloc(4108) = 0x947d180
malloc(3749) = 0x8056258
malloc(116) = 0x8056018
malloc(112) = 0x80571c8
malloc(112) = 0x8057290
即長度前10大的堆對象。其中100012爲bytecode中一個緩衝區,無用;16384爲解釋器的參數棧和返回棧;4108爲三個表示迷宮的數組。
突破口(217):去除BRANCHIFNOT
bytecode中共有四處輸出字符#的地方,對應的字節碼是CONSTINT8 35,它們是下面幾行代碼生成的:
1 | output_char (if e.(x).(y) then |
把0x0845處的BRANCHIFNOT 0x086e和0x08f7處的BRANCHIFNOT 0x0920改成NOP; NOP; NOP(BRANCHIFNOT指令佔三個字節)即可顯示非最後一行或最後一列的所有迷霧格子。
服務端及選手下載的壓縮包的源文件
參見https://github.com/MaskRay/BCTF2015-CamlMaze。
server.cc生成服務端程序server。需要用socat把stdin和stdout接到客戶端的socket。server.cc的流程如下:
alarm(TIMEOUT)設置超時- 用recursive backtracking生成完美迷宮。參見完美迷宮生成算法
- 從客戶端讀取一個整數表示要顯示的迷宮片數
- in-place shuffle選出要被顯示的格子
- fast Reed-Muller tranform變換牆和迷霧
- 依次把右牆、下牆和迷霧編碼爲01串發送給客戶端
- 從客戶端讀取移動序列
- 若移動序列合法則輸出flag,否則輸出出錯信息
我的CTF題目鏡像準備方法
下面簡單提一下我準備題目鏡像的方法。
兩類,一類是完全虛擬化,製作供VirtualBox等使用的虛擬機鏡像,另一類是使用Linux container,製作供Docker等使用的文件系統鏡像。
完全虛擬化的鏡像文件
爲了減小鏡像體積,我選擇了Tiny Core Linux,http://www.tinycorelinux.net/downloads.html上的基本系統Core只有9MB。
用qemu-system-x86_64 -enable-kvm -cdrom Core-current.iso啓動虛擬機。
更換源: 1
2tce-load -wi mirrrors
tcemirror.sh
我們想把題目文件複製到虛擬機裏,由此應該基於Core-current.iso創建一個新的鏡像,這個操作叫做Remastering
TC。
1 | # 把原鏡像文件複製到 /tmp/iso |
/tmp/ext是我們需要的rootfs,把題目的服務端文件放進去,比如/tmp/ext/usr/bin/server。
再安裝socat,因爲不希望虛擬機啓動時連外網,因此還要準備離線安裝的TinyCore軟件包:
1
2
3mkdir -p /tmp/ext/tmp/optional
tce-load -w socat
cp -a /tmp/tce/optional/socat* /tmp/ext/tmp/optional/
修改/tmp/ext/opt/bootlocal.sh: 1
2
3#!/bin/sh
su tc -c 'tce-load -i socat' # 安裝本地的 /tmp/tce/optional/socat*
socat tcp-l:1212,fork exec:server,setgid=1,setuid=1
把rootfs /tmp/ext gzip壓縮後以cpio newc格式製作initramfs
myimg.gz,放到/tmp/iso/boot/,之後要把它打包到ISO裏:
1
2
3
4mkdir /tmp/ext
cd /tmp/ext
# 修改 /tmp/ext/opt/bootlocal.sh
sudo find | sudo cpio -oH newc | gzip -4 > ../myimg.gz && sudo cp ../myimg.gz /tmp/iso/boot/
syslinux的initrd命令支持多個文件,用逗號分隔即可,修改/mnt/iso/boot/isolinux/isolinux.cfg,在引導內核時註明把myimg.gz也當作initramfs解壓:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17display boot.msg
default microcore
label microcore
kernel /boot/vmlinuz
initrd /boot/core.gz,/boot/myimg.gz # 添加 myimg.gz
append loglevel=3
label mc
kernel /boot/vmlinuz
append initrd=/boot/core.gz loglevel=3
implicit 0
prompt 1
timeout 1 # 超時時間爲1/10 s
F1 boot.msg
F2 f2
F3 f3
F4 f4
構建ISO: 1
2
3
4
5cd /tmp
sudo mkisofs -l -J -r -V CamlMaze -no-emul-boot \
-boot-load-size 4 \
-boot-info-table -b boot/isolinux/isolinux.bin \
-o CamlMaze.iso iso
得到鏡像文件CamlMaze.iso。
Linux container的文件系統鏡像
爲了創建儘可能小的文件系統鏡像,只複製待運行的服務器端程序必要的動態鏈接庫。把/bin/sh依賴的動態鏈接庫複製到rootfs:
1
2mkfs rootfs
LD_TRACE_LOADED_OBJECTS=1 LD_DEBUG=libs /bin/sh |& grep -Po --color '/usr[\w/.]+' | sort -u | cpio -pdL rootfs
-p表示copy-pass
mode,讀取待複製的文件列表,複製到另一個目錄下。
-d表示自動創建目標目錄樹下不存在的目錄。
-L表示--dereference:複製軟鏈接指向的文件。
編譯一個精簡的socat,只留--enable-tcp、--enable-listen和--enable-exec,其他的特性都disable:
1
./configure CFLAGS=-Os --disable-help --disable-stdio --disable-fdnum --disable-file --disable-creat --disable-gopen --disable-pipe --disable-termios --disable-unix --disable-abstract-unixsocket --disable-ip4 --disable-ip6 --disable-rawip --disable-genericsocket --disable-socks4 --disable-socks4a --disable-proxy --disable-system --disable-pty --disable-ext2 --disable-readline --disable-openssl --disable-tun --disable-sycls --disable-filan --disable-retry --disable-libwrap
把/usr/bin/socat所需的動態鏈接庫複製到rootfs。
把rootfs保存爲Docker的image,命名爲camlmaze:
1
tar --owner=root --group=root -cf - . | sudo docker load
如果題目中需要使用其他用戶名,可能需要使用--numeric-owner,防止tar使用本機的/etc/passwd進行用戶名和id的映射。
部署時導入image: 1
sudo docker save camlmaze | xz -c9 > camlmaze.tar.xz
1 | % tree rootfs |