[CSAPP]BombLab - CedricXu

一起来拆炸弹！

离上一个 Data Lab 已经过去了两个学期，终于想起来也有时间做 CSAPP 的实验了。这次的实验叫 Bomb Lab，故事背景是 Dr.Evil 设计了一款炸弹，只有正确输入六条字符串才能拆除，我们需要通过逆向工程，反汇编炸弹的可执行文件来破解出能拆除炸弹的六条字符串。

实验概览#

实验资料可以在 CMU 网站上获取：https://csapp.cs.cmu.edu/3e/labs.html

压缩包中总共有三个文件

.
├── README    
├── bomb      // 炸弹可执行文件
└── bomb.c    // 炸弹部分源代码

我们先查看bomb.c文件

hkybb

从中可以看出炸弹的大致工作过程：

读取一行字符串
使用phase_i函数判断输入是否合法

那么只要研究每个phase函数的验证过程就可以反推出字符串内容了

使用objdump -d bomb > bomb.s来获得炸弹的反汇编文件

4hxfc

使用tmux左侧来进行 GDB 调试，右侧查看汇编代码

接下来，让我们开始拆弹！

Phase_1#

phase_1 的汇编代码如下

2wf9q

string_not_equal 接受 edi、esi 两个字符串指针输入，比较两个字符串，若两个字符串相等 eax 输出 0

所以phase_1的作用是比较输入字符串和存在 0x402400 的字符串是否相等，然后使用 test 判断输出是否为 0，若为零则通过，否则调用explode_bomb

所以我们的答案就是 0x404200 处的字符串，使用 GDB 查看

aul0o

关于 GDB 的用法，可以参考这份 CMU 手册https://csapp.cs.cmu.edu/2e/docs/gdbnotes-x86-64.pdf

tips.Evil 允许你使用文件输入:./bomb <file>，来避免每次尝试拆弹时繁琐的重复输入

让我们来试一下拆解第一个炸弹，首先在answer.txt中写下刚刚获得的字符串

sx06g

第一个字符串已经通过啦

ud239

Phase_2#

phase_2 汇编代码如下

4st2b

这个函数比前一个要长不少，同时也调用了read_six_numbers，还有很多的分支跳转指令

  400efe:	48 83 ec 28          	sub    $0x28,%rsp
  400f02:	48 89 e6             	mov    %rsp,%rsi
  400f05:	e8 52 05 00 00       	call   40145c <read_six_numbers>

在栈上分配 0x28 的空间，将六个数字存入栈中

  400f0a:	83 3c 24 01          	cmpl   $0x1,(%rsp)
  400f0e:	74 20                	je     400f30 <phase_2+0x34>
  400f10:	e8 25 05 00 00       	call   40143a <explode_bomb>

如果第一个数字不是 1，炸弹爆炸

  400f17:	8b 43 fc             	mov    -0x4(%rbx),%eax
  400f1a:	01 c0                	add    %eax,%eax
  400f1c:	39 03                	cmp    %eax,(%rbx)
  400f1e:	74 05                	je     400f25 <phase_2+0x29>
  400f20:	e8 15 05 00 00       	call   40143a <explode_bomb>

如果下一个数字不是当前数字的两倍，炸弹爆炸

  400f25:	48 83 c3 04          	add    $0x4,%rbx
  400f29:	48 39 eb             	cmp    %rbp,%rbx
  400f2c:	75 e9                	jne    400f17 <phase_2+0x1b>
  400f2e:	eb 0c                	jmp    400f3c <phase_2+0x40>

rbx指向最后一个数字的后一位，若已经读取到此处代表六个数字都处理完，判断结束

通过以上分析，第二个字符串需要符合以下要求

由 6 个数字组成
第一个数字为 1
从第 2 个开始每个数字都为前面的两倍

所以字符串为1 2 4 8 16 32

Phase_3#

phase_3 的汇编代码如下

h3g6b

可以发现其中有很多有规律的跳转语句，并且开头有一个sscanf，那么前面出现的 0x4025cf 存储的应该就是读取的格式，使用 GDB 打印查看

h2i7l

可以看出我们输入的字符串应该是两个数字

  400f6a:	83 7c 24 08 07       	cmpl   $0x7,0x8(%rsp)
  400f6f:	77 3c                	ja     400fad <phase_3+0x6a>

0x8(%rsp)是第一个数字，如果它大于 7 则跳转至炸弹爆炸

  400f71:	8b 44 24 08          	mov    0x8(%rsp),%eax
  400f75:	ff 24 c5 70 24 40 00 	jmp    *0x402470(,%rax,8)
  400f7c:	b8 cf 00 00 00       	mov    $0xcf,%eax
  400f81:	eb 3b                	jmp    400fbe <phase_3+0x7b>
  400f83:	b8 c3 02 00 00       	mov    $0x2c3,%eax
  400f88:	eb 34                	jmp    400fbe <phase_3+0x7b>
  400f8a:	b8 00 01 00 00       	mov    $0x100,%eax
  400f8f:	eb 2d                	jmp    400fbe <phase_3+0x7b>
  400f91:	b8 85 01 00 00       	mov    $0x185,%eax
  400f96:	eb 26                	jmp    400fbe <phase_3+0x7b>
  400f98:	b8 ce 00 00 00       	mov    $0xce,%eax
  400f9d:	eb 1f                	jmp    400fbe <phase_3+0x7b>
  400f9f:	b8 aa 02 00 00       	mov    $0x2aa,%eax
  400fa4:	eb 18                	jmp    400fbe <phase_3+0x7b>
  400fa6:	b8 47 01 00 00       	mov    $0x147,%eax
  400fab:	eb 11                	jmp    400fbe <phase_3+0x7b>

根据第一个数字选择第二个数字，类似于switch语句，假设第一个数字是 0，跳转到 * 0x02470，用 GDB 查看一下这个地方存了什么

qv677

发现跳转到 0x400f7c，% eax=0xcf，即 207

  400fbe:	3b 44 24 0c          	cmp    0xc(%rsp),%eax
  400fc2:	74 05                	je     400fc9 <phase_3+0x86>
  400fc4:	e8 71 04 00 00       	call   40143a <explode_bomb>

判断第二个数字是否与 % eax 相等，不相等则炸弹爆炸

所以这个字符串的一种形式是0 207，根据第一个数字的不同，第二个数字还有其他不同取值

Phase_4#

phase_4 的汇编代码如下

4gwzt

可以看到除了同样调用了sscanf，还调用了func4这一函数

老样子，还是先看一下sscanf接收的格式

yis7d

可以看到还是两个数字

  40102e:	83 7c 24 08 0e       	cmpl   $0xe,0x8(%rsp)
  401033:	76 05                	jbe    40103a <phase_4+0x2e>
  401035:	e8 00 04 00 00       	call   40143a <explode_bomb>

且第一个数字要小于等于 14 (0xe)

  40103a:	ba 0e 00 00 00       	mov    $0xe,%edx
  40103f:	be 00 00 00 00       	mov    $0x0,%esi
  401044:	8b 7c 24 08          	mov    0x8(%rsp),%edi
  401048:	e8 81 ff ff ff       	call   400fce <func4>

将 14，0 和第一个数字作为参数传入func4，接下来我们来分析func4中发生了什么

jp6wb

其中有两个分支跳转，还有两次递归引用，我们猜测它是一个类似对分查找的程序，尝试把它写成 C 格式

int func4(int i, int j, int target) {
    int mid = ((i - j + ((i - j) >> 31)) >> 1) + j;
    if (mid == target) {
        return 0;
    } else if (mid < target) {
        return 2 * func4(i, mid + 1, target) + 1;
    } else {
        return 2 * func4(mid - 1, j, target);
    }
}

为了使输出为 0，我们只需要一直向左找，而从不找到mid右侧，输入i=14，j=0，所以第一个数字可能的取值为7、3、1、0

  401051:	83 7c 24 0c 00       	cmpl   $0x0,0xc(%rsp)
  401056:	74 05                	je     40105d <phase_4+0x51>
  401058:	e8 dd 03 00 00       	call   40143a <explode_bomb>

最后检查第二个数字是否为零，所以这个字符串可以取3 0

Phase_5#

phase_5 的汇编代码内容

8dfcd

我们看到这其中有两个字符串常量0x4024b0和0x40245e我们用 GDB 看看它们都是什么

17fa2

"maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you"

"flyers"

我浅浅推测：第一条应该是一个字典，因为在使用时有偏移量0x4024b0(%rdx)；第二条是目标字符串，传入 <string_not_equal> 比较用户输入的字符串通过字典翻译过后是否与目标相同

在这样的假设基础上，仔细观察通过字典翻译的过程：

  40108b:	0f b6 0c 03          	movzbl (%rbx,%rax,1),%ecx
  40108f:	88 0c 24             	mov    %cl,(%rsp)
  401092:	48 8b 14 24          	mov    (%rsp),%rdx
  401096:	83 e2 0f             	and    $0xf,%edx
  401099:	0f b6 92 b0 24 40 00 	movzbl 0x4024b0(%rdx),%edx

其中%cl是%ecx寄存器的低 8 位，将其再与上 0xf，就是取低四位，所以再翻译时取字符字节的低四位作为偏移量！

那么 "flyers" 对应字典偏移量为 "9 15 14 5 6 7"，可以写一个 python 脚本来生成一些符合要求的字符串

spell = [9, 15, 14, 5, 6, 7]

for offset in range(8):
    result = "".join(chr(num + 16 * offset) for num in spell)
    print(f"Offset {offset * 16} : {result}")

运行结果：

ryghc

所以第五个字符串可以是 IONEFG，看来猜测是正确的，我们并没有仔细逐句阅读汇编代码就得到了答案

Phase_6#

这个函数的长度明显较之前长了许多，我在这里放上最重要的一部分代码

upap4

我简要说明一下这段代码在干什么，就不细致分析了，感兴趣的读者可以自行下载源码查看

在内存中存有一个链表

rcr1i

首先读入 6 个数字，且范围在 1-6 之间

然后将这 6 个数字对 7 求补，也就是i=7-i

以数字i为索引，寻找链表的第i个结点，将指向这个结点的指针入栈

通过栈中节点的顺序重写每个节点的nextnode指针，使链表结点顺序符合栈中顺序

最后检查链表中结点的data是否降序

想要使结点中数字降序排序，顺序应当是3 4 5 6 1 2，对 7 求补后为4 3 2 1 6 5这就是我们要求的字符串了

拆弹成功#

至此，拆除炸弹所需的 6 个字符串都被我们求出来了，写入answer.txt中

h0218

运行./bomb answer.txt，得到

ed5zn

虽然这个 lab 对于真正的逆向工程来说属于 hello world 水平，但是让我熟悉了 x86-64 汇编和 GDB 基本指令

总的来说这是一个很有意思的实验，根本停不下来