2015-03-23

BCTF 2015 CamlMaze命题报告及CTF题目镜像准备方法

题目

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连接服务端，可以看到如下的输出信息：

Sample:
.@._._._.
|_. |_. |
| |_. | |
| . |_. |
|_|_._. |
       $
You need to input: drdrdrdd

Challenge:
.@._._._._.         ._._._._._.
| | ._._. .#########._. | . | .####################
| | | | ._|#########| | | |_|_.####################
| |_. |_._.#########. | |_._._.####################
|_. |_._| .#########| |_._._. |####################
| ._| . |_.#########|_. |_. |_.####################
 ##################################################
 ##################################################
 ##################################################
 ##################################################
 #################### #_# # #_#####################
 ###################| |_. | | .####################
 ###################| | ._| | |####################
 ###################| |_. ._| .####################
 ###################|_. |_. |_|####################
 ###################| |_. | | .####################
 ###################. | ._| | |####################
 ###################| |_. |_._|####################
 ###################| | ._| ._.####################
 ###################._|_._._._.####################
 ###################._._._. | .##########_# # # #_#
 #######################################. | | | . |
 #######################################| | | |_| |
 #######################################. | | | . |
 #######################################|_._|_._| |
 #######################################._._._._. |
                                                 $
Hint: you need to see more to escape

Path?

解题报告

根据样例可以了解到题目希望我们提供从左上角的@到$的移动路线。而实际要求解的迷宫中很多地方被挡住了，无法看到墙壁的位置。根据提示可以知道我们应该去除迷雾，显示更多的块。

用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。

(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：

(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
3

Challenge:
Fatal error: uncaught exception
.@._._._._.         ._._._._._.                   I find your trick... I'm tamper-resistant!

执行strings bytecode可以发现文本I find your trick...说明字节码中有防篡改代码。之后有几种解题思路。

突破口(简单)：字节码字符串表示方式

./camlfwod bytecode除了列示字节码外，还会显示字节码中用到的一些常量。输出的"5\n"也在里面：

Global 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"了：

% 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这段文本是由下面代码产生的：

switch ( sub_804A79E(a2[optind]) )
{
  ......
  case -6:
    sub_8048BF1((unsigned int)"Fatal error: uncaught exception");
    return result;

然后查找返回值-6产生的源头，从函数sub_804A79E出发，追溯到函数sub_80493F9中如下部分的代码：

LABEL_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：

case 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指令：

...
0aeb: PUSH
0aec: ACCESS 1
0aee: DIVINT
0aef: RETURN
...

这段代码实际上执行了0/0，在解释器中触发了异常。

查看Caml Featherweight源码，可以发现opcode.ml(由runtime/instruct.h生成)编码了各种指令的opcode：

...
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。从命令输出中可以看到：

Challenge:
.@._._._._.                   ._._._._._.         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。

#!/usr/bin/env ruby
#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
2
3

% mkfifo /tmp/fifo
% ruby a.rb
pty: /dev/pts/12

记下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中相关代码为：

let 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：

#define _GNU_SOURCE
#include <dlfcn.h>
#include <execinfo.h>
#include <stdio.h>

#define N 10
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会显示：

malloc(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，它们是下面几行代码生成的：

output_char (if e.(x).(y) then
               if d.(x).(y) then ' ' else '_'
             else if x+1 < n then
               if e.(x+1).(y) then
                 if d.(x).(y) then ' ' else '_'
               else
                 '#'  # offset 0x086e
             else
               '#'
            );
output_char (if e.(x).(y) then
               if r.(x).(y) then '.' else '|'
             else if y+1 < n then
               if e.(x).(y+1) then
                 if r.(x).(y) then '.' else '|'
               else
                 '#'   # offset 0x0920
             else
               '#'
            );

把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 2	tce-load -wi mirrrors tcemirror.sh

我们想把题目文件复制到虚拟机里，由此应该基于Core-current.iso创建一个新的镜像，这个操作叫做Remastering TC。

# 把原镜像文件复制到 /tmp/iso
tce-load -wi mkisofs-tools
sudo mount /dev/sr0 /mnt/sr0
cp -a /mnt/sr0 /tmp/iso    # 会有权限错误，可忽略

/tmp/ext是我们需要的rootfs，把题目的服务端文件放进去，比如/tmp/ext/usr/bin/server。

再安装socat，因为不希望虚拟机启动时连外网，因此还要准备离线安装的TinyCore软件包：

1
2
3

mkdir -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里：

mkdir /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解压：

display 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：

cd /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 2	mkfs 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：

./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

% tree rootfs
rootfs
├── bin
│   └── sh
├── lib64
│   ├── ld-2.21.so
│   └── ld-linux-x86-64.so.2 -> ld-2.21.so
└── usr
    ├── bin
    │   ├── server
    │   ├── socat
    │   └── start
    └── lib
        └── libc.so.6
% du -sh rootfs
3.4M    rootfs
% cat rootfs/usr/bin/start
#!/bin/sh
exec socat tcp-l:1212,fork exec:server,setgid=1,setuid=1