Csapp2-bomblab

CSAPP: bomblab

正好最近在学逆向，这里是基于 [ida] 以及硬怼汇编的 [bomblab]，不得不说，汇编看起来确实头疼，但是找到答案的过程非常有成就感。

以下为 [bomb.c] 文件，用 [chatgpt] 作了翻译，很有趣的实验场景，cmu的教授幽默感十足（实验过程中发现了一些小彩蛋），赛博拆弹😜。

bomblab前置知识以及所需准备

做前须知：

关于汇编：

类型 语法 例子 备注
常量 符号$ 开头 $-42, $0x15213 一定要注意十进制还是十六进制
寄存器 符号 % 开头 %esi, %rax 可能存的是值或者地址
内存地址 括号括起来 (%rbx), 0x1c(%rax), 0x4(%rcx, %rdi, 0x1) 括号实际上是去寻址的意思 
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
/***************************************************************************

 * 邪恶博士的阴险炸弹，版本 1.1
 * 版权所有 2011，邪恶博士公司。保留所有权利。
   *
 * 许可证：
   *
 * 邪恶博士公司（即肇事者，PERPETRATOR）特此授予你（即受害者，VICTIM）
 * 明确许可使用此炸弹（即炸弹，BOMB）。这是一个限时许可，
 * 在受害者死亡时失效。
 * 肇事者不对受害者的任何损害、挫败感、精神错乱、暴突眼、
 * 腕管综合症、失眠或其他伤害负责。除非肇事者想要因此获得荣誉。
 * 受害者不得向肇事者的敌人分发此炸弹的源代码。
 * 任何受害者不得调试、逆向工程、运行 "strings" 命令、
 * 反编译、解密或使用任何其他技术来获取炸弹的知识并拆除炸弹。
 * 处理此程序时不得穿戴防爆衣。
 * 肇事者不会为自己糟糕的幽默感道歉。
 * 在炸弹被法律禁止的地方，本许可证无效。
   ***************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include "support.h"
#include "phases.h"

/* 

 * 备忘录：记得删除这个文件，这样我的受害者们就不会知道发生了什么，
 * 这样他们都会在一次极其恶毒的爆炸中炸飞。——邪恶博士
 */

FILE *infile;

int main(int argc, char *argv[])
{
    char *input;
/* 备忘录：记得把这个炸弹移植到 Windows，并给它加上一个
 * 炫酷的图形界面（GUI）。 */
/* cry的吐槽:最后还是忘了加，留在官网的环境依然是在linux上的 */
/* 如果没有参数，炸弹会从标准输入读取输入行。 */
if (argc == 1) {  
infile = stdin;
} 

/* 如果提供了一个参数 <file>，炸弹会从 <file> 读取输入，
 * 直到文件结束，然后切换到标准输入。
 * 这样，随着你拆除每个阶段的炸弹，你可以将其拆除代码
 * 添加到 <file> 中，避免重复输入。 */
else if (argc == 2) {
if (!(infile = fopen(argv[1], "r"))) {
    printf("%s: 错误：无法打开 %s\n", argv[0], argv[1]);
    exit(8);
}
}

/* 你不能用超过 1 个命令行参数来调用炸弹程序。 */
else {
printf("用法: %s [<输入文件>]\n", argv[0]);
exit(8);
}

/* 执行各种秘密操作，使炸弹更难拆除。 */
initialize_bomb();

printf("欢迎来到我的邪恶小炸弹。你有 6 关要过，\n");
printf("否则就会炸飞自己。祝你好运！\n");

/* 嗯…… 六个阶段一定比一个阶段更安全！ */
input = read_line();             /* 读取输入                 */
phase_1(input);                  /* 运行第一阶段               */
phase_defused();                 /* 可恶！他们竟然破解了！
			      * 让我看看他们是怎么做到的。 */
printf("第一阶段已拆除。来试试下一个吧？\n");

/* 第二阶段更难。没人能弄清楚
 * 该怎么拆除…… */
input = read_line();
phase_2(input);
phase_defused();
printf("这是第二关。继续努力！\n");

/* 我猜到目前为止还是太简单了。
 * 一些更复杂的代码会让人困惑。 */
input = read_line();
phase_3(input);
phase_defused();
printf("已经完成一半了！\n");

/* 哦，是吗？那么，你的数学能力如何？
 * 试试这个辣手的问题吧！ */
input = read_line();
phase_4(input);
phase_defused();
printf("这个你也解开了。试试这个吧。\n");

/* 在内存中绕来绕去，我们会停在哪？炸弹会爆炸！ */
input = read_line();
phase_5(input);
phase_defused();
printf("干得好！继续下一个……\n");

/* 这一阶段永远不会被使用，因为没人能通过前面的阶段。
 * 但以防万一，让这一关特别难。 */
input = read_line();
phase_6(input);
phase_defused();

/* 哇，他们竟然破解了！但是不是少了点什么……？
 * 也许有什么被他们忽略了？哈哈哈哈哈！ */

return 0;
}

初步读完程序我们大致知道有6个阶段(当然，邪恶博士显然是藏不住话的人，这种喜欢给提示的反派真是老套，我们会在接下来找出他的 [secret_phase] 来嘲笑他)。

好吧，让我们开始拆弹吧。

Phase 1：

直接汇编硬怼：

用 [objdump] 反汇编锁定到 [.text] 的 [phase_1] 段。

phase1

让我们逐行分析，栈指针下移，[sub] 在这里分配了8字节的空间，[mov] 则是将 [rsi] 的低32位赋值，而[callq] 则是调用了位于401338的函数，这个函数名一看就是判断字符串是否相等，[je] 则代表如果相等则跳转到 [phase1 + 0x17]， 这里正好是add的值，就跳过了引爆炸弹阶段，所以我们只需要找到对应的字符串即可，选择在 [phase_1] 打完断点后一行行看 [rsi] 中所存储的值。后续的 [add] 则释放空间。

于是得到

1
Border relations with Canada have never been better.

怎么有点夹带私货的感觉？

令人感到讽刺的是 10多年后，[Trump] 声称 [Canada] 即将成为美国的第51个州，这下边界问题彻底解决了，就是有点地狱笑话…

ida：

做静态分析怎么能少得了 [ida]，虽然明确要求了我不用逆向工程，但我就用。

打开 [ida],找到 [phase_1] 直接反编译，得到

一目了然😎

非常简单的判断逻辑，机器反编译就是比人肉反编译好用啊(

Phase 2:

直接汇编硬怼：

发现阶段2开始代码开始变长了，于是输出文件放到 [vscode] 上面去看。

phase2

这里有着很多跳转指令，估计是个循环，在处理循环前，我们看看前面发生了什么。

    1. push %rbp , push %rbx 两者均为被调用者保存寄存器，在循环递归中都很常见，这里我们也可以看到尾部 pop %rbx 和 pop %rbp 还原了最开始存储的值，这里值得注意的是，汇编中 pop 是弹出栈顶的值，并将其赋值给其后紧接的寄存器。如果习惯了 cpp stl 中栈的 pop 语法，可能会搞错。
    2. sub 将栈指针向下移动28字节，为局部变量分配出了空间。
    3. mov %rsp, %rsi 将栈顶指针的值赋给rsi
    4. 开始调用一个名为 的函数，顾名思义，下列操作应该就是跟读取6个数字有关。
    5. cmpl 比较1与rsp内存中指向的值的大小
    6. je 如果相等则跳转到400f30

到这里为止开始发生跳转，我们尝试还原 je 之后的程序，在此之前，随便测试一组输出，观察寄存器中存储值的变化，选择最为简朴的（1，2，3，4，5，6）和一组（2，3，4，5，6，7）。

分别为各个引爆程序处打上断点，我们会发现在经过 [read_six_numbers] 函数后，rsp连续的地址中存储了我们输入的值，（1，2，3，4，5，6）这组数会在 400f20 处引爆，而（2，3，4，5，6，7）则在 400f10 处引爆，两者的区别在于首位不为1，只有首位为1才会进入循环逻辑，对应cmpl的那串指令，循环中的炸弹判断则在 400f20 处判断。

于是我们可以还原循环了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#跳转阶段
jmp 400f30<phase_2+0x34> #跳转到lea处，在这里将rsp上的第一个数赋值给rbx（rbx毕竟叫做基址指针，我们用它来遍历循环）
#准备阶段
lea 0x4(%rsp),%rbx       #赋值中
lea 0x4(%rbp),%rbp       #终止逻辑，看下面循环阶段的cmp即可知，当rbx相等时即跳转结束
#循环阶段
mov -0x4(%rbx), %eax     # 从前一个数字地址读取值
add %eax, %eax           # 计算前一个数字的两倍
cmp %eax, (%rbx)         # 比较当前数字是否等于前一个数字的两倍
je  400f25               # 如果相等，继续循环
callq 40143a             # 如果不相等，爆炸
add $0x4, %rbx           # 移动到下一个数字
cmp %rbp, %rbx           # 检查是否到达第六个数字
jne 400f17               # 如果未到达第六个数字，继续循环
#结束
#最后几个指令均是在收拾“残局”

所以函数的逻辑就是一个简单的指数函数😥，是的，你在cpp中两行就能敲完的代码变成了这样。

答案为:

1
1,2,4,8,16,32

ida：

ida给出的反汇编函数

我们可以清楚的看到 [ida] 给出的反汇编函数执行了我们上述的逻辑，但令人感到困惑的是13行的代码2**((_DWORD *)v2-1)到底在干吗，这里需要复习cpp中的知识，(DWORD *)设置的是一个 [double word] 双字，4字节的指针（其实我很无语字这个设定，字节就字节非要搞这些出来），括号外的第一个 *表解引用指针，即读取存储的值，而第二个则是代表通俗的乘法，至于这里的 -1 注意是在做指针地址运算，即指向前一个地址，再将取地址的值乘2。然后就是循环再循环了。

相较于硬怼汇编，清晰明了不少。当然，如果直接用 [ida] 确实也会失去bomblab的原本意义，这里作为用汇编做完的对比验证。

Phase 3：

直接汇编硬怼

phase3

放眼一看，全是跳转指令,并且跳转到结束后到同一地址，基本可以确定是 [switch] 语句格式，可以参考书p159~162的内容，以及注意到 [callq] 调用的是 [__isoc99_sscanf@plt]，这里说明调用了c标准库中的 [sscanf] 函数，并且是动态链接方式。看到前两行的 [mov]，注意到0x4025cf的值传递给了 [eax]，运行时 x/s 查看可发现，存储的是”%d,%d”，所以读入的是两个 int 型的数。这里 [eax] 设为 0 可能意味着 没有使用 SSE 浮点参数，即 [sscanf] 只处理整数/字符类型。弄清楚上面发生的事后，我们看下面跳转指令的执行逻辑。

先随便输入一组数据 (1,2)，发现在 [eax] 中存储返回值 0x2，代表我们输入了两个参数。满足 [jg] 跳转指令后开始运行。这下回头看开头的 %rcx 与 %rdx，即存储了我们输入的值。

这也对应了

  • 在 x86-64 ABI 调用惯例中，函数的参数存放在以下寄存器中：
  1. %rdi - sscanf 的第一个参数（字符串输入）
  2. %rsi - sscanf 的第二个参数（格式化字符串）
  3. %rdx - sscanf 的第三个参数（第一个输入变量的地址）
  4. %rcx - sscanf 的第四个参数（第二个输入变量的地址）

接下来开始跳转，第一条 [ja] 指令（这里是比较无符号数的），这里是比较 [rdx] 中存储的第一个参数与7的大小，相当于我们的第一个参数必须在 0~7 之间才会继续跳转，否则跳转到 400fad 引起爆炸，而之后的 [mov] 将 [rdx] 中的值赋给 [eax]。

接下来的 [jmpq] 充当了 [switch] 选择的角色，根据 [eax] 中存储的值决定跳转的目标。

值得注意的是，0x402470存储的是跳转表的基地址，而eax * 8取偏移量相当于在表中选择位置，这里的 * 则取出了跳转表中的地址

而对应的 case 可以转化为下表：

注意，这玩意儿不要想当然的0就对应第一个jump，1就对应第二个

实际上用 x/16a 打印出来的表长这样：

1
2
3
4
0x402470:       0x400f7c <phase_3+57>   0x400fb9 <phase_3+118>
0x402480:       0x400f83 <phase_3+64>   0x400f8a <phase_3+71>
0x402490:       0x400f91 <phase_3+78>   0x400f98 <phase_3+85>
0x4024a0:       0x400f9f <phase_3+92>   0x400fa6 <phase_3+99>
1
2
3
4
5
6
7
8
9
eax	跳转地址	赋值        对应十进制
0	400f7c	eax = 0xcf       207
1	400fb9	eax = 0x137      311
2	400f83	eax = 0x2c3      707
3	400f8a	eax = 0x100      256     
4	400f91	eax = 0x185      389
5	400f98	eax = 0xce       206
6	400f9f	eax = 0x2aa      682
7	400fa6	eax = 0x147      327

而最后的 [cmp] 则是比较我们经过 [switch] 后得到的 [eax] 与我们输入的第二个参数是否相等，相等即满足，开始收拾“残局”。所以我们可以得到 7 组答案。

即：

1
2
3
4
5
6
7
8
0 207
1 311
2 707
3 256
4 389
5 206
6 682
7 327

ida：

又到了我最喜欢的 [ida] 反汇编环节，让我们打开然后反汇编一看。

秒了（

逻辑十分清晰，非常清楚的列出来根据第一个参数选择，然后返回对应值，甚至把对应10进制也计算了出来…从这里我们可以看出，在最开始输入 [sscanf] 函数时，我们可以输入多个参数，但最终生效的也只有前两个。所以 sscanf 函数给了我们的Dr.Evil博士可乘之机。

Phase 4：

phase 3 与 4 之间夹杂了一个 func4 段，由于暂时不知道这是干嘛的，也懒得研究，我们先略过直接研究phase 4。

直接汇编硬怼：

phase 4

发现 phase 4 与 phase 3 前面部分近乎一模一样，那我们可以直接跳过前面的调用分析，很快锁定我们需要输入（%d,%d)，毕竟调用的位置都是相同的0x4025cf…接下来看函数逻辑部分。

先将我们输入的两个值传入 [sscanf] 将返回的值存储 [eax] 中，如果参数的个数不为2则直接引爆炸弹。在此之后比较第一个参数与 14 的大小，如果参数小于等于 14 则跳转到 40103a 的赋值语句上，否则引爆炸弹。

将 [edx] 赋值为14，[esi] 赋值为0，同时将我们输入的第一个参数的值赋给 [edi]。然后就开始调用我们神秘的 [func 4] 函数了。在这之后就是检验 [func 4] 返回的 [eax] 是否为0。

test %eax, %eax 是一种常见的位运算指令，它的作用是检查 eax 的值是否为 0 ，但不会改变 eax 的值。而跳转指令，像类似 [jne] （Jump if Not Equal / Zero Flag 未置位） 这种，本质上比较的是标志位上的值，这里 [eax] 为0的话，ZF 便会置1，从而接着进行比较，否则爆炸。

了解了这些，我们就可以看看 [func4] 到底是想干嘛了。

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
#将调用前做的准备工作也放到这里面来一起看，这三个寄存器大概率就是我们将传入func4函数中的参数
  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
0000000000400fce <func4>:
  400fce:	48 83 ec 08          	sub    $0x8,%rsp   #分配8字节空间
  400fd2:	89 d0                	mov    %edx,%eax   #eax = edx
  400fd4:	29 f0                	sub    %esi,%eax   #eax = eax - esi
  400fd6:	89 c1                	mov    %eax,%ecx   #ecx = eax 
  400fd8:	c1 e9 1f             	shr    $0x1f,%ecx  
  400fdb:	01 c8                	add    %ecx,%eax   #eax = eax + ecx,修正
  400fdd:	d1 f8                	sar    %eax        #配合修正
  400fdf:	8d 0c 30             	lea    (%rax,%rsi,1),%ecx #二分区间
  400fe2:	39 f9                	cmp    %edi,%ecx   #比较
  400fe4:	7e 0c                	jle    400ff2 <func4+0x24>
  400fe6:	8d 51 ff             	lea    -0x1(%rcx),%edx
  400fe9:	e8 e0 ff ff ff       	callq  400fce <func4>  #递归
  400fee:	01 c0                	add    %eax,%eax
  400ff0:	eb 15                	jmp    401007 <func4+0x39>
  400ff2:	b8 00 00 00 00       	mov    $0x0,%eax
  400ff7:	39 f9                	cmp    %edi,%ecx
  400ff9:	7d 0c                	jge    401007 <func4+0x39>
  400ffb:	8d 71 01             	lea    0x1(%rcx),%esi
  400ffe:	e8 cb ff ff ff       	callq  400fce <func4>  #递归
  401003:	8d 44 00 01          	lea    0x1(%rax,%rax,1),%eax
  401007:	48 83 c4 08          	add    $0x8,%rsp   #还原栈
  40100b:	c3                   	retq

让人感到困惑的是 shr 等指令是在干什么。我们将前半截详细分解下

1
2
3
4
5
6
7
400fd2:  89 d0              mov    %edx, %eax   # eax = edx
400fd4:  29 f0              sub    %esi, %eax   # eax = edx - esi
400fd6:  89 c1              mov    %eax, %ecx   # ecx = eax
400fd8:  c1 e9 1f           shr    $0x1f, %ecx  # ecx = eax >> 31 (提取符号)
400fdb:  01 c8              add    %ecx, %eax   # eax = eax + ecx
400fdd:  d1 f8              sar    %eax         # eax = eax / 2 (算术右移)
400fdf:  8d 0c 30           lea    (%rax,%rsi,1), %ecx # ecx = eax + esi

提取符号位那里在 datalab 中也有比较多的运用。那么我们是在干吗呢，注意到 [eax] 现在是 [(edx-esi)/2]，所以 [ecx = (edx + esi)/2] (其实这里应该还要看正负值，因为ecx在这里可能为1或0，这里就涉及到了二分算法中的取整)，所以我们似乎是在二分，看到下面的递归更加坚信了这个判断。

我们先来看看为什么这里能修正，这里我用了 gpt 给出的解释和示例，相当于复习了一遍二分。

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
为什么 +1 能修正？
主要目标
该操作的目的是 为了在除以 2 之前，对负数进行向上取整的修正。因为 算术右移 (SAR) 在处理负数时，会向下取整，但我们希望的是 向零取整（或更接近实际数学意义上的 floor((a - b) / 2)）。
例子分析
(1) 正数情况
假设 eax = 6，esi = 2，edx = 10：
eax = edx - esi = 10 - 2 = 8
shr $0x1f, %ecx  →  ecx = 0  (因为 8 的符号位是 0)
eax = eax + ecx  →  eax = 8 + 0 = 8
sar %eax         →  eax = 8 / 2 = 4  (正常除法)
没问题，正确得到 (10 - 2) / 2 = 4。
(2) 负数情况
假设 eax = -7，esi = 10，edx = 3：
eax = edx - esi = 3 - 10 = -7
shr $0x1f, %ecx  →  ecx = 1  (因为 -7 的符号位是 1)
eax = eax + ecx  →  eax = -7 + 1 = -6
sar %eax         →  eax = -6 / 2 = -3  (向下取整)
正确得到 (3 - 10) / 2 = -3（向零取整）。
(3) 负数但偶数
假设 eax = -8：
eax = -8
shr $0x1f, %ecx  →  ecx = 1
eax = eax + ecx  →  eax = -8 + 1 = -7
sar %eax         →  eax = -7 / 2 = -3
此时，(-8 / 2 = -4)，但 -7 / 2 = -3，这个调整稍微向上取整了，让结果更接近数学上 (a - b) / 2。

那么确定好区间后，二分的下一步显然是比较与目的值的大小，然后重新确定区间的端点值，接下来就是分析汇编是如何实现该思路的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
400fe2:	39 f9                	cmp    %edi,%ecx
400fe4:	7e 0c                	jle    400ff2 <func4+0x24>
400fe6:	8d 51 ff             	lea    -0x1(%rcx),%edx
400fe9:	e8 e0 ff ff ff       	callq  400fce <func4>
400fee:	01 c0                	add    %eax,%eax
400ff0:	eb 15                	jmp    401007 <func4+0x39>
400ff2:	b8 00 00 00 00       	mov    $0x0,%eax
400ff7:	39 f9                	cmp    %edi,%ecx
400ff9:	7d 0c                	jge    401007 <func4+0x39>
400ffb:	8d 71 01             	lea    0x1(%rcx),%esi
400ffe:	e8 cb ff ff ff       	callq  400fce <func4>
401003:	8d 44 00 01          	lea    0x1(%rax,%rax,1),%eax
401007:	48 83 c4 08          	add    $0x8,%rsp
40100b:	c3                   	retq

根据二分模型，我们可以根据上面分析的内容确定 [edx] 存储右端点，而 [esi] 存you储左端点，这里的 [cmp] 比较 [edi] 与[ecx] 的大小，显然，当前的 [ecx] 存储的就是区间的中点值，经过比较后，如果 [ecx] 小于等于 [edi] 则跳转到 400ff2 而 400ff2 下面的 [cmp] 则根据 [ecx] 如果大于等于 [edi]则跳转到还原栈指针阶段。显然只有当 [ecx] = [edi] 才会到 401007。这里是结束的逻辑。

那么如果不满足小于等于的话，我们回到 400fe6 这行，会发现 [edx] 也就是我们的右端点，会加载成当前的 [rcx-1] 也就是 [中点 - 1] 的值。同理，位于 400ffb 这行的则是则是将左端点 [esi] 加载成 [中点+1]。至此我们理清了二分的逻辑。

所以 [func4] 函数是让我们在 0~14 这个区间内查找 [rdx]，即我们输入的第一个参数。那我们输入的第二个参数在哪里呢。

1
2
3
4
5
6
7
40104d:	85 c0                	test   %eax,%eax
40104f:	75 07                	jne    401058 <phase_4+0x4c>
401051:	83 7c 24 0c 00       	cmpl   $0x0,0xc(%rsp)
401056:	74 05                	je     40105d <phase_4+0x51>
401058:	e8 dd 03 00 00       	callq  40143a <explode_bomb>
40105d:	48 83 c4 18          	add    $0x18,%rsp
401061:	c3                   	retq

我们可以看到最后还存在一个比较 [cmpl] 是 0 与 0xc(%rsp)的比较。而0xc(%rsp) 在这之前并没有参与过其余运算，所以我们的第二个参数需要保证为 0。

而第一个参数必须得满足在递归中能使返回的 [eax] 为 0。

1
2
40104d:	85 c0                	test   %eax,%eax
40104f:	75 07                	jne    401058 <phase_4+0x4c>

而根据 [func4] 函数的逻辑，查找的值在：

如果输入值小于当前中间点 ecx：

递归搜索左半区间 [esi, ecx-1]，返回 0。

如果输入值大于当前中间点 ecx：

递归搜索右半区间 [ecx+1, edx]，并返回 2*递归返回值 + 1。

故我们所以可行的答案为：

1
2
3
4
0 0
1 0
3 0
7 0

而phase_4函数本身实现的是二叉搜索树的功能，左0右1将树的路径转化为了二进制表达。

例如：

我们注意 eax的计算：

  • 左子树返回 0，不会修改 eax
  • 右子树返回 2 * eax + 1，不断累加

这等价于：

  • 把左子树看成 0
  • 把右子树看成 1
  • 递归过程中，我们构造出一条 从根节点到 edi 的路径，并把它转化为一个二进制数。

我们假设 func4(6, 0, 14)`：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
               7
          /         \
        3             11
      /   \         /    \
     1     5      9      13
    / \   / \    / \    /  \
   0   2 4   6 8   10 12   14
如果给二叉树加上对应返回的编号
               (0)
          /          \
       (0)            (1)
      /   \         /    \
    (0)    (1)    (2)    (3)
   /  \    /  \   /  \   /  \
 (0)  (1)(2)  (3)(4) (5)(6) (7)

ida：

显而易见的递归逻辑

由于我们的 [eax] 在一开始赋值为0，从而给整体的递归都定了调。

Phase 5:

直接汇编硬怼：

phase5

前面的 [push] 以及对于 [rbp] 和 [rsp] 的调用，与phase2很类似，可能是要开始一个循环，而接下来的两行 [mov] 则分别将 [rdi] 中的值赋给 [rbx]，这是基底指针最开始的指向，而后的 [fs 0x28] 赋值到[rax] 则是 Canary 值，用来防止栈溢出攻击（想起了新生赛中的pwn题，最后一道就和猜测 Canary 值有关)。函数尾调用的 [_stack_chk_fail@plt] 函数也是检验是否存在栈溢出攻击的，通过比较栈上存储的Canary值是否发生改动，不过这些都与本题无关，而后的 [xor] 则是清 0 [eax] 便于之后的计算。

让我们先看比较特殊的函数， 和 ，所以大概率我们需要输入一个字符串，先输入一个 test，读取下对应寄存器的值，看看发生了什么变化。

发现 [rdi] 中存储了我们的值，说明当前大概率只有我们输入的这个 test 参数：

1
2
(gdb) x/s $rdi
0x6038c0 <input_strings+320>:   "test"

然后 [cmp] 函数与返回的 [eax] 中的值做比较，不相等则爆炸。检查后发现在输入 test 的情况下返回值为4，所以这个函数人如其名，就是个检验长度的值，让我们输入另一组 crycry 来继续测试。

在 crycry 的情况下，我们会跳转到：

1
2
3
4
5
6
7
8
9
10
11
12
13
40108b <phase_5+41>   movzbl (%rbx,%rax,1),%ecx     #读取了一字节'c'进ecx
40108f:	88 0c 24             	mov    %cl,(%rsp)   #将ecx赋值给(rsp)指向位置
401092:	48 8b 14 24          	mov    (%rsp),%rdx  #rsp再赋值给rdx
401096:	83 e2 0f             	and    $0xf,%edx    #与0xf做and运算依旧为本身
#在gdb中检查当前edx的值
#(gdb) p $edx
#$1 = 99
#99是ASCII码中c对应的值
 401099:	0f b6 92 b0 24 40 00 	movzbl 0x4024b0(%rdx),%edx
 4010a0:	88 54 04 10          	mov    %dl,0x10(%rsp,%rax,1)
 4010a4:	48 83 c0 01          	add    $0x1,%rax
 4010a8:	48 83 f8 06          	cmp    $0x6,%rax
 4010ac:	75 dd                	jne    40108b <phase_5+0x29>

我们发现跳转到的这个地方正好是一个循环，在 [rax] 不等于 6 之前会一直运行下去，而中间的逻辑则是将 crycry 做一个字符串变换。变换的逻辑是将位于 0x4024b0 + [%rdx]偏移量的值赋给当前对应索引的数组。

[rbx] 作为数组的基地址，每次运行就将对应索引的值赋给 [ecx] ，我们看一看 [rbx] 中存储的是什么，同时看一下 0x4024b0 处取的偏移字符串是什么。

1
2
3
4
(gdb) x/s $rbx
0x6038c0 <input_strings+320>:   "crycry"
(gdb) x/s 0x4024b0
0x4024b0 <array.3449>:  "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"

这里的 [maduiersnfotvbyl] 恰好16个字符，正好对应了位于 401096 处的 and 操作，由于 char 类型为1字节占8位，而与 0xf 做 and 操作的话会将 char 的高四位清零，从而低4位恰好可以用作索引来选择 [maduiersnfotvbyl] 中的字符来完成我们下述的 strings_not_ equal 工作

转换成 cpp 的话大概是：

1
2
3
4
5
6
for(int rax=0; rax<6; rax++){
    ecx = array[rax];
    //中间最重要的过程是 and 0xf %edx
    //在这里我们将edx的高四位清 0 了
    array[rax] = [edx] + 0x4024b0 ;//需要注意的是这里是[edx]是取的内存中的值
}

而后续几行的汇编内容则是：

1
2
3
4
5
6
4010ae:	c6 44 24 16 00       	movb   $0x0,0x16(%rsp)
4010b3:	be 5e 24 40 00       	mov    $0x40245e,%esi
4010b8:	48 8d 7c 24 10       	lea    0x10(%rsp),%rdi
4010bd:	e8 76 02 00 00       	callq  401338 <strings_not_equal>
4010c2:	85 c0                	test   %eax,%eax
4010c4:	74 13                	je     4010d9 <phase_5+0x77>

[movb] 将 0x16(%rsp) 处赋值为 0，事实上这里是我们 array数组的末端。然后将 0x40245e 处的值赋给 esi，同样的，下面将 0x10(%rsp) 的值赋给 [rdi] ，很明显，[rdi] 和 [rsi] 通常在函数调用中作为第一和第二个参数，下面的 [strings_not_equal] 函数就是在比较这两个寄存器的内容，也是该 phase 的核心比较，再往下的汇编指令就是不重要的收尾工作了。

那么我们查看 401338 处存储的字符串。

1
2
(gdb) x/s 0x40245e
0x40245e:       "flyers"

答案呼之欲出，相当于我们输入的字符串经过循环中的变换后要得到 “flyers”。那么我们只需要将过程逆转，即可得到需要输入的字符串。

我们先将我们需要选择的字符对应索引列出来

[maduiersnfotvbyl] 

1
2
3
4
5
6
7
字符  索引   对应二进制
f     9      1001
l     15     1111
y     14     1110
e     5      0101
r     6      0110
s     7      0111

在这里我们需要一张ASCII码表来做解码工作：

ASCII

所以我们需要选取后四位分别对应: [1001] [1111] [1110] [0101] [0110] [0111] 的字符。

选取出来的字符均可成为答案：

1
2
3
4
5
6
) I i 9 Y y
/ O o ? _
. N n > ^ ~
% E e 5 U u
& F f 6 V v
' G g 7 W w

理论上答案可以取上述对应各行任意字符组合，不过我只尝试了大小写两种对应，其余要是错了本人概不负责😎。

ida：

ida

唯一需要看懂的可能就是10行的赋值语句。

(byte *) (a1+i) 对应了选取指向我们输入的字符串的一字节指针。外面再加上 * 代表取出所需字符，然后再与 0xF 进行按位与操作。

Phase 6：

直接汇编硬怼：

phase6长的令人发指😥，就不截取长图了伤害大家的眼睛了，让我们直接看清楚明了的代码块汇编（

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
00000000004010f4 <phase_6>:
  4010f4:	41 56                	push   %r14
  4010f6:	41 55                	push   %r13
  4010f8:	41 54                	push   %r12
  4010fa:	55                   	push   %rbp
  4010fb:	53                   	push   %rbx
  4010fc:	48 83 ec 50          	sub    $0x50,%rsp
  401100:	49 89 e5             	mov    %rsp,%r13
  401103:	48 89 e6             	mov    %rsp,%rsi
  401106:	e8 51 03 00 00       	callq  40145c <read_six_numbers>
  40110b:	49 89 e6             	mov    %rsp,%r14
  40110e:	41 bc 00 00 00 00    	mov    $0x0,%r12d
  401114:	4c 89 ed             	mov    %r13,%rbp
  401117:	41 8b 45 00          	mov    0x0(%r13),%eax
  40111b:	83 e8 01             	sub    $0x1,%eax
  40111e:	83 f8 05             	cmp    $0x5,%eax
  401121:	76 05                	jbe    401128 <phase_6+0x34>
  401123:	e8 12 03 00 00       	callq  40143a <explode_bomb>
  401128:	41 83 c4 01          	add    $0x1,%r12d
  40112c:	41 83 fc 06          	cmp    $0x6,%r12d
  401130:	74 21                	je     401153 <phase_6+0x5f>
  401132:	44 89 e3             	mov    %r12d,%ebx
  401135:	48 63 c3             	movslq %ebx,%rax
  401138:	8b 04 84             	mov    (%rsp,%rax,4),%eax
  40113b:	39 45 00             	cmp    %eax,0x0(%rbp)
  40113e:	75 05                	jne    401145 <phase_6+0x51>
  401140:	e8 f5 02 00 00       	callq  40143a <explode_bomb>
  401145:	83 c3 01             	add    $0x1,%ebx
  401148:	83 fb 05             	cmp    $0x5,%ebx
  40114b:	7e e8                	jle    401135 <phase_6+0x41>
  40114d:	49 83 c5 04          	add    $0x4,%r13
  401151:	eb c1                	jmp    401114 <phase_6+0x20>
  401153:	48 8d 74 24 18       	lea    0x18(%rsp),%rsi
  401158:	4c 89 f0             	mov    %r14,%rax
  40115b:	b9 07 00 00 00       	mov    $0x7,%ecx
  401160:	89 ca                	mov    %ecx,%edx
  401162:	2b 10                	sub    (%rax),%edx
  401164:	89 10                	mov    %edx,(%rax)
  401166:	48 83 c0 04          	add    $0x4,%rax
  40116a:	48 39 f0             	cmp    %rsi,%rax
  40116d:	75 f1                	jne    401160 <phase_6+0x6c>
  40116f:	be 00 00 00 00       	mov    $0x0,%esi
  401174:	eb 21                	jmp    401197 <phase_6+0xa3>
  401176:	48 8b 52 08          	mov    0x8(%rdx),%rdx
  40117a:	83 c0 01             	add    $0x1,%eax
  40117d:	39 c8                	cmp    %ecx,%eax
  40117f:	75 f5                	jne    401176 <phase_6+0x82>
  401181:	eb 05                	jmp    401188 <phase_6+0x94>
  401183:	ba d0 32 60 00       	mov    $0x6032d0,%edx
  401188:	48 89 54 74 20       	mov    %rdx,0x20(%rsp,%rsi,2)
  40118d:	48 83 c6 04          	add    $0x4,%rsi
  401191:	48 83 fe 18          	cmp    $0x18,%rsi
  401195:	74 14                	je     4011ab <phase_6+0xb7>
  401197:	8b 0c 34             	mov    (%rsp,%rsi,1),%ecx
  40119a:	83 f9 01             	cmp    $0x1,%ecx
  40119d:	7e e4                	jle    401183 <phase_6+0x8f>
  40119f:	b8 01 00 00 00       	mov    $0x1,%eax
  4011a4:	ba d0 32 60 00       	mov    $0x6032d0,%edx
  4011a9:	eb cb                	jmp    401176 <phase_6+0x82>
  4011ab:	48 8b 5c 24 20       	mov    0x20(%rsp),%rbx
  4011b0:	48 8d 44 24 28       	lea    0x28(%rsp),%rax
  4011b5:	48 8d 74 24 50       	lea    0x50(%rsp),%rsi
  4011ba:	48 89 d9             	mov    %rbx,%rcx
  4011bd:	48 8b 10             	mov    (%rax),%rdx
  4011c0:	48 89 51 08          	mov    %rdx,0x8(%rcx)
  4011c4:	48 83 c0 08          	add    $0x8,%rax
  4011c8:	48 39 f0             	cmp    %rsi,%rax
  4011cb:	74 05                	je     4011d2 <phase_6+0xde>
  4011cd:	48 89 d1             	mov    %rdx,%rcx
  4011d0:	eb eb                	jmp    4011bd <phase_6+0xc9>
  4011d2:	48 c7 42 08 00 00 00 	movq   $0x0,0x8(%rdx)
  4011d9:	00 
  4011da:	bd 05 00 00 00       	mov    $0x5,%ebp
  4011df:	48 8b 43 08          	mov    0x8(%rbx),%rax
  4011e3:	8b 00                	mov    (%rax),%eax
  4011e5:	39 03                	cmp    %eax,(%rbx)
  4011e7:	7d 05                	jge    4011ee <phase_6+0xfa>
  4011e9:	e8 4c 02 00 00       	callq  40143a <explode_bomb>
  4011ee:	48 8b 5b 08          	mov    0x8(%rbx),%rbx
  4011f2:	83 ed 01             	sub    $0x1,%ebp
  4011f5:	75 e8                	jne    4011df <phase_6+0xeb>
  4011f7:	48 83 c4 50          	add    $0x50,%rsp
  4011fb:	5b                   	pop    %rbx
  4011fc:	5d                   	pop    %rbp
  4011fd:	41 5c                	pop    %r12
  4011ff:	41 5d                	pop    %r13
  401201:	41 5e                	pop    %r14
  401203:	c3                   	retq

尝试分段分析，一口气读完这么长的汇编显然不现实。

首先将 [read_six_numbers] 函数到跳转前的准备工作截取出来，我们输入（1，2，3，4，5，6）来作为测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
4010f4:	41 56                	push   %r14
4010f6:	41 55                	push   %r13
4010f8:	41 54                	push   %r12
4010fa:	55                   	push   %rbp
4010fb:	53                   	push   %rbx
4010fc:	48 83 ec 50          	sub    $0x50,%rsp
401100:	49 89 e5             	mov    %rsp,%r13
401103:	48 89 e6             	mov    %rsp,%rsi
401106:	e8 51 03 00 00       	callq  40145c <read_six_numbers>
40110b:	49 89 e6             	mov    %rsp,%r14
40110e:	41 bc 00 00 00 00    	mov    $0x0,%r12d
401114:	4c 89 ed             	mov    %r13,%rbp
401117:	41 8b 45 00          	mov    0x0(%r13),%eax
40111b:	83 e8 01             	sub    $0x1,%eax
40111e:	83 f8 05             	cmp    $0x5,%eax
401121:	76 05                	jbe    401128 <phase_6+0x34>
401123:	e8 12 03 00 00       	callq  40143a <explode_bomb>

注意到在调用完 [read_sixe_numbers] 后，rsp 中存储了我们输入的值：

1
2
3
(gdb) x/6wd $rsp
0x7fffffffe320: 1       2       3       4
0x7fffffffe330: 5       6

于是我们开始尝试下面的跳转语句，看看它到底是在干什么。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
40110b:	49 89 e6             	mov    %rsp,%r14
40110e:	41 bc 00 00 00 00    	mov    $0x0,%r12d
401114:	4c 89 ed             	mov    %r13,%rbp
401117:	41 8b 45 00          	mov    0x0(%r13),%eax
40111b:	83 e8 01             	sub    $0x1,%eax
40111e:	83 f8 05             	cmp    $0x5,%eax
401121:	76 05                	jbe    401128 <phase_6+0x34>
401123:	e8 12 03 00 00       	callq  40143a <explode_bomb>
401128:	41 83 c4 01          	add    $0x1,%r12d 
40112c:	41 83 fc 06          	cmp    $0x6,%r12d
401130:	74 21                	je     401153 <phase_6+0x5f>
401132:	44 89 e3             	mov    %r12d,%ebx #ebx等同于for中的i
401135:	48 63 c3             	movslq %ebx,%rax
401138:	8b 04 84             	mov    (%rsp,%rax,4),%eax
40113b:	39 45 00             	cmp    %eax,0x0(%rbp)
40113e:	75 05                	jne    401145 <phase_6+0x51>
401140:	e8 f5 02 00 00       	callq  40143a <explode_bomb>
401145:	83 c3 01             	add    $0x1,%ebx
401148:	83 fb 05             	cmp    $0x5,%ebx
40114b:	7e e8                	jle    401135 <phase_6+0x41>#小于等于跳转
40114d:	49 83 c5 04          	add    $0x4,%r13  #将r13地址增加 4，对应int值的长度,又跳转回第 4 行，相当于移一位，
401151:	eb c1                	jmp    401114 <phase_6+0x20>

在4行 [mov] 结束后，[r13] 中存储了我们输入的 (1,2,3,4,5,6) 的连续地址，这得益于之前的赋值，[r13] 将当前位置传递给 [eax]。然后是一个sub 操作，比较 [eax]与 5 的大小，如果不是小于等于5则炸弹爆炸。说明我们输入的6个数字均需小于等于6。判断后跳转到 401128，将 [r12] 中的值+1，由于一开始我们将 [r12] 赋了0，合理怀疑这里起循环中计数的作用，下面的 [cmp] 则显示出循环会进行6次。这层循环如果结束会跳转到 401153。

1
2
401153:	48 8d 74 24 18       	lea    0x18(%rsp),%rsi
#可以判断这里存储在rsi中的值是0，因为0x18恰好24字节，前面的24恰好存储输入的序列

这我们一时间还摸不着头脑，所以我们先走完这遍循环再来看这一段的含义。在 [je] 判断后，将 [r12d] 赋值给 [ebx]，[ebx] 又转赠给 [rax]，所以当前的 [rax] 就等于我们常在 for 循环中见到的 i，接下来的 mov 就相当于将我们当前数组中的下一位赋值给了[eax]，因为一开始 [r13] 将地址赋给了 [rbp] 所以 [rbp] 在循环中指向对应索引的数。下一个 [cmp] 则是与当前的 [eax] 比较，这条语句相当于在告诉我们相邻的两个数不能相等，如果相等则会爆炸。

接下来是对 [ebx] 的操作，在刚才 [r12d] 赋值给了它，它现在依旧是起一个 i 的作用，这里依旧是循环6次，所以13-20行是一个循环，而3-22也是一个循环。这两个循环构成了二重循环。

让我们来试试解释下它们的行为，先从内循环13-20行开始：

1
2
3
4
5
6
7
8
401135:	48 63 c3             	movslq %ebx,%rax
401138:	8b 04 84             	mov    (%rsp,%rax,4),%eax
40113b:	39 45 00             	cmp    %eax,0x0(%rbp)
40113e:	75 05                	jne    401145 <phase_6+0x51>
401140:	e8 f5 02 00 00       	callq  40143a <explode_bomb>
401145:	83 c3 01             	add    $0x1,%ebx
401148:	83 fb 05             	cmp    $0x5,%ebx
40114b:	7e e8                	jle    401135 <phase_6+0x41>#小于等于跳转

正如我们上述所言，在单纯一个循环中实现了一个比较相邻位不等的作用。而对于整个循环中，由于 [rbp] 在该循环是不发生改变的。所以我们在第二行，遍历了整个数组，所以内循环实现的功能是检验输入序列是否存在重复。

接下来看外循环:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
401114:	4c 89 ed             	mov    %r13,%rbp
401117:	41 8b 45 00          	mov    0x0(%r13),%eax
40111b:	83 e8 01             	sub    $0x1,%eax
40111e:	83 f8 05             	cmp    $0x5,%eax
401121:	76 05                	jbe    401128 <phase_6+0x34>
401123:	e8 12 03 00 00       	callq  40143a <explode_bomb>
401128:	41 83 c4 01          	add    $0x1,%r12d 
40112c:	41 83 fc 06          	cmp    $0x6,%r12d
401130:	74 21                	je     401153 <phase_6+0x5f>
401132:	44 89 e3             	mov    %r12d,%ebx #ebx等同于for中的i
401135:	48 63 c3             	movslq %ebx,%rax
401138:	8b 04 84             	mov    (%rsp,%rax,4),%eax
40113b:	39 45 00             	cmp    %eax,0x0(%rbp)
40113e:	75 05                	jne    401145 <phase_6+0x51>
401140:	e8 f5 02 00 00       	callq  40143a <explode_bomb>
401145:	83 c3 01             	add    $0x1,%ebx
401148:	83 fb 05             	cmp    $0x5,%ebx
40114b:	7e e8                	jle    401135 <phase_6+0x41>#小于等于跳转
40114d:	49 83 c5 04          	add    $0x4,%r13  #将r13地址增加 4，对应int值的长度,又跳转回第 4 行，相当于移一位，
401151:	eb c1                	jmp    401114 <phase_6+0x20>

显然，我们的重点在前半部分，前半部分的 1~9 行，我们实现了比较序列中数时候小于6，在等于6过后我们就跳转到401153，离开了 这段二重循环。

综上，我们解构出了这段二重循环的意义比较输入序列中是否存在重复的数，并且序列中的数是否都小于6。

接下来我们从 401153 开始看起。

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
401153:	48 8d 74 24 18       	lea    0x18(%rsp),%rsi #存储的是0
401158:	4c 89 f0             	mov    %r14,%rax
40115b:	b9 07 00 00 00       	mov    $0x7,%ecx #ecx中存储7
401160:	89 ca                	mov    %ecx,%edx  #edx中存储7
401162:	2b 10                	sub    (%rax),%edx
401164:	89 10                	mov    %edx,(%rax)
401166:	48 83 c0 04          	add    $0x4,%rax
40116a:	48 39 f0             	cmp    %rsi,%rax
40116d:	75 f1                	jne    401160 <phase_6+0x6c>
40116f:	be 00 00 00 00       	mov    $0x0,%esi
401174:	eb 21                	jmp    401197 <phase_6+0xa3>
401176:	48 8b 52 08          	mov    0x8(%rdx),%rdx
40117a:	83 c0 01             	add    $0x1,%eax
40117d:	39 c8                	cmp    %ecx,%eax
40117f:	75 f5                	jne    401176 <phase_6+0x82>
401181:	eb 05                	jmp    401188 <phase_6+0x94>
401183:	ba d0 32 60 00       	mov    $0x6032d0,%edx
401188:	48 89 54 74 20       	mov    %rdx,0x20(%rsp,%rsi,2)
40118d:	48 83 c6 04          	add    $0x4,%rsi
401191:	48 83 fe 18          	cmp    $0x18,%rsi
401195:	74 14                	je     4011ab <phase_6+0xb7>
401197:	8b 0c 34             	mov    (%rsp,%rsi,1),%ecx
40119a:	83 f9 01             	cmp    $0x1,%ecx
40119d:	7e e4                	jle    401183 <phase_6+0x8f>
40119f:	b8 01 00 00 00       	mov    $0x1,%eax
4011a4:	ba d0 32 60 00       	mov    $0x6032d0,%edx
4011a9:	eb cb                	jmp    401176 <phase_6+0x82>

[rsi] 现在存储的是 0 了，而 [r14] 则继承了 [rsp] 的遗志，我们在最初时将 [rsp] 的值赋给了它，现在它又将其重新赋给了 [rax]。接下来又是一段循环，我们将其截取出来。

1
2
3
4
5
6
401160:	89 ca                	mov    %ecx,%edx  #edx中存储7
401162:	2b 10                	sub    (%rax),%edx
401164:	89 10                	mov    %edx,(%rax)
401166:	48 83 c0 04          	add    $0x4,%rax
40116a:	48 39 f0             	cmp    %rsi,%rax
40116d:	75 f1                	jne    401160 <phase_6+0x6c>

这里的大致意思很好懂，移动 [rax], 用 7 来减去 [rax] 中的值，直到序列中所有的数都减完，[rax] + 0x18 时 [rsi] 与 [rax] 就相等离开循环。所以我们输入的(1,2,3,4,5,6)在这里变成了(6,5,4,3,2,1)。

接着看下一段:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
40116f:	be 00 00 00 00       	mov    $0x0,%esi
401174:	eb 21                	jmp    401197 <phase_6+0xa3>
401176:	48 8b 52 08          	mov    0x8(%rdx),%rdx
40117a:	83 c0 01             	add    $0x1,%eax
40117d:	39 c8                	cmp    %ecx,%eax
40117f:	75 f5                	jne    401176 <phase_6+0x82>
401181:	eb 05                	jmp    401188 <phase_6+0x94>
401183:	ba d0 32 60 00       	mov    $0x6032d0,%edx
401188:	48 89 54 74 20       	mov    %rdx,0x20(%rsp,%rsi,2)
40118d:	48 83 c6 04          	add    $0x4,%rsi
401191:	48 83 fe 18          	cmp    $0x18,%rsi
401195:	74 14                	je     4011ab <phase_6+0xb7>
401197:	8b 0c 34             	mov    (%rsp,%rsi,1),%ecx
40119a:	83 f9 01             	cmp    $0x1,%ecx
40119d:	7e e4                	jle    401183 <phase_6+0x8f>#小于等于跳转
40119f:	b8 01 00 00 00       	mov    $0x1,%eax
4011a4:	ba d0 32 60 00       	mov    $0x6032d0,%edx
4011a9:	eb cb                	jmp    401176 <phase_6+0x82>

这里将 [esi] 赋值为 0 ,然后突如其来的一个跳转跳到了 401197。

1
401197:	8b 0c 34             	mov    (%rsp,%rsi,1),%ecx

显然也是一个遍历的过程。比较当前值与1的大小。按照当前输入下，[rsp] 指向的第一个数是6，我们按照逻辑模拟运行下去，跳转到 0x401183。

发现跳转过来就将一个奇怪的地址赋值给了 [edx]，查看一下：

1
2
3
4
5
6
7
8
9
10
11
(gdb) x/6wd 0x6032d0
0x6032d0 <node1>:       332     1       6304480 0
0x6032e0 <node2>:       168     2
#范围放大一点
(gdb) x/24wd 0x6032d0
0x6032d0 <node1>:       332     1       6304480 0
0x6032e0 <node2>:       168     2       6304496 0
0x6032f0 <node3>:       924     3       6304512 0
0x603300 <node4>:       691     4       6304528 0
0x603310 <node5>:       477     5       6304544 0
0x603320 <node6>:       443     6       0       0

node 的提示词更像是我们在操作一个链表。并且这个链表有6个节点，每个节点占16个字节。看来接下来我们是要对这个链表进行操作。

来看跳转到 401197 后对节点操作的这段循环：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
401176:	48 8b 52 08          	mov    0x8(%rdx),%rdx
40117a:	83 c0 01             	add    $0x1,%eax
40117d:	39 c8                	cmp    %ecx,%eax
40117f:	75 f5                	jne    401176 <phase_6+0x82>#关键节点
401181:	eb 05                	jmp    401188 <phase_6+0x94>
401183:	ba d0 32 60 00       	mov    $0x6032d0,%edx
401188:	48 89 54 74 20       	mov    %rdx,0x20(%rsp,%rsi,2) #32个字节
40118d:	48 83 c6 04          	add    $0x4,%rsi
401191:	48 83 fe 18          	cmp    $0x18,%rsi
401195:	74 14                	je     4011ab <phase_6+0xb7>
401197:	8b 0c 34             	mov    (%rsp,%rsi,1),%ecx
40119a:	83 f9 01             	cmp    $0x1,%ecx
40119d:	7e e4                	jle    401183 <phase_6+0x8f>#小于等于跳转
40119f:	b8 01 00 00 00       	mov    $0x1,%eax
4011a4:	ba d0 32 60 00       	mov    $0x6032d0,%edx
4011a9:	eb cb                	jmp    401176 <phase_6+0x82>#关键节点

将 [rsp] 当前指向的6赋值给 [ecx] 从14行开始尝试跟随循环逻辑，在第一个字符为6的情况下，我们执行不了13行的跳转指令，而是将 [eax] 赋为1，再将 node1 的值赋给 [edx]。然后跳转回 401176 节点。

在401176~40117f之间又是一个小的循环，[rdx] 的地址不断+8，直到与当前的 [ecx] 即 6 相等为止。根据输入的 转换值（1-6），取出相应的 链表节点指针 存入栈中。

而后的下一段：

1
2
3
4
5
6
4011ab: 48 8b 5c 24 20        mov    0x20(%rsp),%rbx
4011b0: 48 8d 44 24 28        lea    0x28(%rsp),%rax
4011b5: 48 8d 74 24 50        lea    0x50(%rsp),%rsi
4011ba: 48 89 d9              mov    %rbx,%rcx
4011bd: 48 8b 10              mov    (%rax),%rdx
4011c0: 48 89 51 08           mov    %rdx,0x8(%rcx)

则是将我们之前操作的链表按照我们的输入顺序进行排列。

而经过这一段后再下面的一段则是我们判断的核心逻辑：

1
2
3
4
5
4011df: 48 8b 43 08           mov    0x8(%rbx),%rax
4011e3: 8b 00                	mov    (%rax),%eax
4011e5: 39 03                	cmp    %eax,(%rbx)
4011e7: 7d 05                	jge    4011ee <phase_6+0xfa>
4011e9: e8 4c 02 00 00        callq  40143a <explode_bomb>

这里判断输出的链表是否单调递减，而根据上面我们看到的 node：

1
2
3
4
5
6
0x6032d0 <node1>:       332     1       6304480 0
0x6032e0 <node2>:       168     2       6304496 0
0x6032f0 <node3>:       924     3       6304512 0
0x603300 <node4>:       691     4       6304528 0
0x603310 <node5>:       477     5       6304544 0
0x603320 <node6>:       443     6       0       0

可以得出顺序应为 3 -> 4 -> 5 -> 6 -> 1 -> 2，但由于我们最开始的循环中将其用7减去了一次，所以我们需要还原回去。

所以答案为：

1
2
4 3 2 1 6 5
Congratulations! You've defused the bomb!

至此，我们终于完成Dr.Evil博士明面上给定的任务。

ida：

ida 中的内容也很复杂，就是从一个循环到另一个循环，没有什么参考意义，对于 phase_6，最重要的是学会分段分解来分析。这样才能将复杂的汇编剖析成寻常熟悉的语句。

彩蛋：

1、试图用 ctrl + c 退出的 cry:

well,yes:(

在做的过程中发现这段字符串存储的地址和 phase5 的存储的字符串相邻。

2、secret_phase()：

Dr Evil 博士在最后的哈哈哈哈引起了我们的注意，说明他必然有所隐瞒，让我们来寻找下他的小秘密。

进入方法：

这里我实在懒得费尽心思去找哪里可能存在的判断逻辑。于是检索了 secret_phase 关键字，发现除了在本身存在的函数段外，只有 phase_defused() 函数调用了 secret_phase。

对于对应段：

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
00000000004015c4 <phase_defused>:
  4015c4:	48 83 ec 78          	sub    $0x78,%rsp
  4015c8:	64 48 8b 04 25 28 00 	mov    %fs:0x28,%rax
  4015cf:	00 00 
  4015d1:	48 89 44 24 68       	mov    %rax,0x68(%rsp)
  4015d6:	31 c0                	xor    %eax,%eax
  4015d8:	83 3d 81 21 20 00 06 	cmpl   $0x6,0x202181(%rip)        # 603760 <num_input_strings>
  4015df:	75 5e                	jne    40163f <phase_defused+0x7b>
  4015e1:	4c 8d 44 24 10       	lea    0x10(%rsp),%r8
  4015e6:	48 8d 4c 24 0c       	lea    0xc(%rsp),%rcx
  4015eb:	48 8d 54 24 08       	lea    0x8(%rsp),%rdx
  4015f0:	be 19 26 40 00       	mov    $0x402619,%esi
  4015f5:	bf 70 38 60 00       	mov    $0x603870,%edi
  4015fa:	e8 f1 f5 ff ff       	callq  400bf0 <__isoc99_sscanf@plt>
  4015ff:	83 f8 03             	cmp    $0x3,%eax
  401602:	75 31                	jne    401635 <phase_defused+0x71>
  401604:	be 22 26 40 00       	mov    $0x402622,%esi
  401609:	48 8d 7c 24 10       	lea    0x10(%rsp),%rdi
  40160e:	e8 25 fd ff ff       	callq  401338 <strings_not_equal>
  401613:	85 c0                	test   %eax,%eax
  401615:	75 1e                	jne    401635 <phase_defused+0x71>
  401617:	bf f8 24 40 00       	mov    $0x4024f8,%edi
  40161c:	e8 ef f4 ff ff       	callq  400b10 <puts@plt>
  401621:	bf 20 25 40 00       	mov    $0x402520,%edi
  401626:	e8 e5 f4 ff ff       	callq  400b10 <puts@plt>
  40162b:	b8 00 00 00 00       	mov    $0x0,%eax
  401630:	e8 0d fc ff ff       	callq  401242 <secret_phase>
  401635:	bf 58 25 40 00       	mov    $0x402558,%edi
  40163a:	e8 d1 f4 ff ff       	callq  400b10 <puts@plt>
  40163f:	48 8b 44 24 68       	mov    0x68(%rsp),%rax
  401644:	64 48 33 04 25 28 00 	xor    %fs:0x28,%rax
  40164b:	00 00 
  40164d:	74 05                	je     401654 <phase_defused+0x90>
  40164f:	e8 dc f4 ff ff       	callq  400b30 <__stack_chk_fail@plt>
  401654:	48 83 c4 78          	add    $0x78,%rsp
  401658:	c3                   	retq   
  401659:	90                   	nop
  40165a:	90                   	nop
  40165b:	90                   	nop
  40165c:	90                   	nop
  40165d:	90                   	nop
  40165e:	90                   	nop
  40165f:	90                   	nop

我们发现它在14、15行间做了一个 [cmp] 对于 [sscanf] 函数的返回值如果不为3则直接跳转到最后，而如果为3才会进入后面的 [strings_not_equal] 的比较。

分别查看位于 12 和 17 行的地址中存储的内容，发现：

1
2
3
4
5
(gdb) x/s 0x402619
0x402619:       "%d %d %s"

(gdb) x/s 0x402622
0x402622:       "DrEvil"

所以我们需要在对应 [sscanf] 函数中的第三个参数值输入 ‘Dr.Evil’ 这个值。才能进入 [secret_phase]，放在 ida 中则是这样。

入口

切换到 secret_phase():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
0000000000401242 <secret_phase>:
  401242:	53                   	push   %rbx
  401243:	e8 56 02 00 00       	callq  40149e <read_line>
  401248:	ba 0a 00 00 00       	mov    $0xa,%edx
  40124d:	be 00 00 00 00       	mov    $0x0,%esi
  401252:	48 89 c7             	mov    %rax,%rdi
  401255:	e8 76 f9 ff ff       	callq  400bd0 <strtol@plt>
  40125a:	48 89 c3             	mov    %rax,%rbx
  40125d:	8d 40 ff             	lea    -0x1(%rax),%eax
  401260:	3d e8 03 00 00       	cmp    $0x3e8,%eax
  401265:	76 05                	jbe    40126c <secret_phase+0x2a>#小等于
  401267:	e8 ce 01 00 00       	callq  40143a <explode_bomb>
  40126c:	89 de                	mov    %ebx,%esi
  40126e:	bf f0 30 60 00       	mov    $0x6030f0,%edi
  401273:	e8 8c ff ff ff       	callq  401204 <fun7>
  401278:	83 f8 02             	cmp    $0x2,%eax
  40127b:	74 05                	je     401282 <secret_phase+0x40>
  40127d:	e8 b8 01 00 00       	callq  40143a <explode_bomb>
  401282:	bf 38 24 40 00       	mov    $0x402438,%edi
  401287:	e8 84 f8 ff ff       	callq  400b10 <puts@plt>
  40128c:	e8 33 03 00 00       	callq  4015c4 <phase_defused>
  401291:	5b                   	pop    %rbx
  401292:	c3                   	retq

让我们逐行分析 read_line 函数是因为 secret_phase没有在main中所以需要主动调用。然后就是将 [edx] 和 [esi] 分别赋值为 10 和 0，[rax] 赋值给 [rdi]。

注意到这里调用 strtol 函数，经过查询我们可以知道它对应参数的意义。

  • C 库函数 long int strtol(const char *str, char *endptr, int base) 把参数 str 所指向的字符串根据给定的 base 转换为一个长整数（类型为 long int 型），base 必须介于 2 和 36（包含）之间，或者是特殊值 0。

随便输入一个字符串“123”，发现存储在 [rax] 中，[rax] 将其赋值给 [rdi] ，执行完 strtol 函数后，重新查看，依旧存储在 [rax] 中，不过转换成了地址方式存储。第10行执行的 [cmp] 限制了我们输入的字符串转成的数要在 1000 以内。否则引爆炸弹，接下来将 [ebx] 中的值存到 [esi] 中，查看 [ebx] 可发现存储了我们输入的值。

接下来一个奇怪的内存地址移到了 [edi] 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0x6030f0 <n1>:  36      0       6304016 0
0x603100 <n1+16>:       6304048 0       0       0
0x603110 <n21>: 8       0       6304144 0
0x603120 <n21+16>:      6304080 0       0       0
0x603130 <n22>: 50      0       6304112 0
0x603140 <n22+16>:      6304176 0       0       0
0x603150 <n32>: 22      0       6304368 0
0x603160 <n32+16>:      6304304 0       0       0
0x6031f0 <n41>: 1       0       0       0
0x603200 <n41+16>:      0       0       0       0
0x603210 <n47>: 99      0       0       0
0x603220 <n47+16>:      0       0       0       0
0x603230 <n44>: 35      0       0       0
0x603240 <n44+16>:      0       0       0       0
0x603250 <n42>: 7       0       0       0
0x603260 <n42+16>:      0       0       0       0

查看后发现是一堆奇怪的节点，看起来像是树一类的指向，我们可以大概构建出这棵树：

1
2
3
4
5
6
7
      36 (n1)
     /    \
   8 (n21) 50 (n22)
  /  \    /   \
1(n41) 22(n32) 99(n47)
     \       /
     7(n42) 35(n44)

再查看下一行的 func7：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
0000000000401204 <fun7>:
  401204:	48 83 ec 08          	sub    $0x8,%rsp
  401208:	48 85 ff             	test   %rdi,%rdi
  40120b:	74 2b                	je     401238 <fun7+0x34>
  40120d:	8b 17                	mov    (%rdi),%edx
  40120f:	39 f2                	cmp    %esi,%edx
  401211:	7e 0d                	jle    401220 <fun7+0x1c>
  401213:	48 8b 7f 08          	mov    0x8(%rdi),%rdi
  401217:	e8 e8 ff ff ff       	callq  401204 <fun7>
  40121c:	01 c0                	add    %eax,%eax
  40121e:	eb 1d                	jmp    40123d <fun7+0x39>
  401220:	b8 00 00 00 00       	mov    $0x0,%eax
  401225:	39 f2                	cmp    %esi,%edx
  401227:	74 14                	je     40123d <fun7+0x39>
  401229:	48 8b 7f 10          	mov    0x10(%rdi),%rdi
  40122d:	e8 d2 ff ff ff       	callq  401204 <fun7>
  401232:	8d 44 00 01          	lea    0x1(%rax,%rax,1),%eax
  401236:	eb 05                	jmp    40123d <fun7+0x39>
  401238:	b8 ff ff ff ff       	mov    $0xffffffff,%eax
  40123d:	48 83 c4 08          	add    $0x8,%rsp
  401241:	c3                   	retq

经过 ida 分析得到(实则懒得继续汇编了，下次有空再看），fun7 函数实际上是一个二叉搜索树（BST）的查找函数，它按照如下方式递归查找目标值：

  1. 当前节点值大于目标值 → 递归进入左子树 (a1 + 8)，返回值乘 2。
  2. 当前节点值小于目标值 → 递归进入右子树 (a1 + 16)，返回值乘 2 加 1。
  3. 当前节点值等于目标值 → 返回 0（停止递归）。
  4. 如果节点为空 → 返回 -1（表示未找到）。
1
2
3
4
5
6
7
8
401278:	83 f8 02             	cmp    $0x2,%eax
40127b:	74 05                	je     401282 <secret_phase+0x40>
40127d:	e8 b8 01 00 00       	callq  40143a <explode_bomb>
401282:	bf 38 24 40 00       	mov    $0x402438,%edi
401287:	e8 84 f8 ff ff       	callq  400b10 <puts@plt>
40128c:	e8 33 03 00 00       	callq  4015c4 <phase_defused>
401291:	5b                   	pop    %rbx
401292:	c3                   	retq

所以我们想得到返回值为2的话，根据上面构建的树结构，我们只需要选择输入 22 即可。

故答案为:

1
22
1
2
Wow! You've defused the secret stage!
Congratulations! You've defused the bomb!

结束！

参考：

以下两位的实验与上述不同，参考借鉴了phase6的过程以及gdb的使用。

CSAPP Bomblab 题解 by SkyWT

更适合北大宝宝体质的 Bomb Lab 踩坑记 by Arthals

一些坑点：

[ida] 与 [gdb] 各自默认使用的语法：

  • ida：默认使用 intel 语法

    gdb： 默认使用AT&T 语法

最初使用时不太熟练，老是弄混，可以将 [gdb] 设置成 intel 语法（当然，考试估计使用 AT&T，但最近逆向的都是 windows 上的文件，实在看不习惯）

1
set disassembly-flavor intel

最后还是老老实实用AT&T做完了。

炸弹爆炸时，如果gdb在 layout asm模式下会花屏

使用ctrl + l 来清理，会回归正常，但是有些时候会回跳到main函数，也可以考虑ctrl+ x + a重启界面。但还是比较麻烦，还没有找到花屏的原因。

总结：

bomblab是一个很有意思的实验，用gdb分析以及人肉汇编的过程真的极其痛苦，尤其是对于不熟悉的人来说，但这样一行行分析出来的结果也给予人成就感，并且在做完后觉得自己有了很大的提升。

也意识到反汇编工具对于逆向工程调试的重要性，我不知道如果没有 [ida] 我该如何去面对加了壳的程序，如果单纯只用 ida 来完成bomblab的话，我觉得一个多小时就能做完，可对于刚学汇编，并且不熟悉 gdb 的我而言，这个过程是5天，虽然中间掺杂了一些其它活动，但可见bomblab本身对于初学者的难度，汇编的熟练过程任重而道远。

好了，就说这么多，下一个 lab 打算试一试 attack lab，应该跟 pwn 中的题有相似之处。

前进！😜