深入理解计算机系统(CS:APP) - Bomb Lab详解

Bomb Lab

实验代码见GitHub

简介

BombLab是CS:APP中对应第三章内容:程序的机器级表示的lab。主要内容为提供一个二进制对象文件bomb,当运行时,它会要求用户输入六个字符串,如果其中的任何一个不正确,炸弹就会爆炸,输出一行错误信息并向计分服务器提交(自学所用的材料不会向服务器提交信息,但这不代表我们可以随意让炸弹爆炸),学生必须通过反汇编和逆向工程来找到六个正确的字符串来解除自己的炸弹(理论上每个人的炸弹答案都不同,但自学材料的答案都是一样的,本文针对的是自学材料)。

所用工具

objdump-用于反汇编二进制对象文件

VS Code-用于查看反汇编后的结果与文本文件的编写

gdb-用于运行时单步调试与查看运行时内存与寄存器信息

解题过程

前期

由于之前没有接触过类似的逆向工程问题,拿到问题以后第一时间很难马上开始解决。所以先查看我们能看到的文件信息。

目录中提供了一个bomb.c文件,文件内容十分简单,有一份非常有趣的LISENCE:

/***

* Dr. Evil’s Insidious Bomb, Version 1.1

* Copyright 2011, Dr. Evil Incorporated. All rights reserved.

*

* LICENSE:

*

* Dr. Evil Incorporated (the PERPETRATOR) hereby grants you (the

* VICTIM) explicit permission to use this bomb (the BOMB). This is a

* time limited license, which expires on the death of the VICTIM.

* The PERPETRATOR takes no responsibility for damage, frustration,

* insanity, bug-eyes, carpal-tunnel syndrome, loss of sleep, or other

* harm to the VICTIM. Unless the PERPETRATOR wants to take credit,

* that is. The VICTIM may not distribute this bomb source code to

* any enemies of the PERPETRATOR. No VICTIM may debug,

* reverse-engineer, run “strings” on, decompile, decrypt, or use any

* other technique to gain knowledge of and defuse the BOMB. BOMB

* proof clothing may not be worn when handling this program. The

* PERPETRATOR will not apologize for the PERPETRATOR’s poor sense of

* humor. This license is null and void where the BOMB is prohibited

* by law.

***/

接下来的部分就是main函数,从主函数中我们可以看到整个程序的结构与输入方式:可以从标准输入或文件中读取,一行作为一题的解,解出一个问题以后可以进入下一个问题,注意到返回前的一段注释:

​ /* Wow, they got it! But isn’t something… missing? Perhaps

​ * something they overlooked? Mua ha ha ha ha! */

暗示了我们隐藏问题的存在,除此之外再也没有任何关于这个炸弹的信息。

下面我们使用objdump命令将炸弹文件反汇编出来:

1
objdump -d bomb > bomb.asm

然后通过VS Code来查看反汇编的结果,VS Codex86 and x86_64 Assembly这个插件可以高亮汇编,看起来会舒服许多。

反汇编出来的代码有近六千行,但是因为有符号表的存在,说明保留了调试所需的信息,我们可以通过gdb进行单步调试来查看程序的运行过程。

在使用gdb 的时候,我们可以加上-tui命令并用layout asm命令切换到汇编指令模式,就可以在调试的时候查看对应的汇编代码了。界面如下:

可以看到地址0x400da0就是main函数的地址。

一直向下查看,我们就可以看到C文件中出现的initialize_bomb函数,然后就到了phase_1函数,我们可以推测这个函数就是判断是否通过的核心函数。

这时候就要用到gdb的指令了,在汇编模式下的指令与普通模式有一些不同。我们可以使用ni(next instruction)和si(step into)来实现普通模式下的单步向下执行与步入操作。

打断点需要使用b <func_name>b *<address>来进行比如我们可以看到调用phase_1函数的call指令的地址是0x400e3a,所以我们可以使用b phase_1b *0x400e3a来打断点的,这两条命令有一点不同就在于断在地址会停在地址 上也就是call指令的位置,断在函数名会进入函数中,相当于再进行了一次si操作。

断点停后有可能出现字符重叠的情况,我们可以使用refresh命令刷新界面。

下面把断点打在phase_1函数之后就可以使用r命令来运行指令了,程序会提示我们输入字符串,这个时候因为我们打了断点不用担心炸弹会爆炸,可以随意输入。执行后程序会停在phase_1函数的位置,我们可以看到函数内部的情况。

下面就可以根据函数内部的逻辑来解决炸弹了。

代码来自objdump -d反汇编出来的代码,与gdb的汇编模式下看到的代码是一样的。

主函数

主函数代码比较长,只贴我们需要分析的关键部分。

1
2
400e32:	e8 67 06 00 00       	callq  40149e <read_line>
400e37: 48 89 c7 mov %rax,%rdi

第一句调用了read_line函数,我们可以转到函数入口地址40149e去查看read_line的代码(事实上一开始我也这么做了),但是会发现代码中包含了许多对系统库函数的调用,仔细分析的难度比较大并且没有必要。从提供的C代码与函数名称,我们可以推测出这个函数的作用是读取一行输入。根据返回值一般存放在rax中的约定,rax中应该就是读入的数据的地址,第二句中我们把这个值复制到了rdi中。

1
2
400e3a:	e8 a1 00 00 00       	callq  400ee0 <phase_1>
400e3f: e8 80 07 00 00 callq 4015c4 <phase_defused>

接下来两句分别开始调用phase_1phase_defused,下面的五个阶段也是上面这样的模式。

阶段一

1
2
3
4
5
6
7
8
9
0000000000400ee0 <phase_1>:
400ee0: 48 83 ec 08 sub $0x8,%rsp
400ee4: be 00 24 40 00 mov $0x402400,%esi
400ee9: e8 4a 04 00 00 callq 401338 <strings_not_equal>
400eee: 85 c0 test %eax,%eax
400ef0: 74 05 je 400ef7 <phase_1+0x17>
400ef2: e8 43 05 00 00 callq 40143a <explode_bomb>
400ef7: 48 83 c4 08 add $0x8,%rsp
400efb: c3 retq

阶段一的代码比较短,第二行中把一个地址给了esi,接下来调用了strings_not_equal这个函数,我们可以跳到函数入口地址查看这个函数。

1
2
3
40133c:	48 89 fb             	mov    %rdi,%rbx
40133f: 48 89 f5 mov %rsi,%rbp
401342: e8 d4 ff ff ff callq 40131b <string_length>

函数中这两行分别把rdi rsi的值复制到了rbxrbp,然后调用了string_length,这个时候就不用去看string_length函数了,我们可以直接猜测出rbxrbp就是函数的参数。那么可以说明rdi rsi就是给string_not_equal的函数,那么string_not_equal的返回值是什么呢?

看到string_not_equal返回后的5、6两句,测试了eax的值,在eax等于0时就跳转到400ef7,如果不为0,那么会继续向下执行,下面一句是调用explode_bomb函数,不用说这一定是触发炸弹的函数,所以我们需要令string_not_equal的返回值为0,那么从名字判断,我们需要令两个字符串相等,两个字符串之前说过存放在rdirsi中,rdi是我们读入的字符串,而rsi中存放的是400ee4复制的0x402400,这个时候用gdb去查看该地址中存放的字符串比较方便:

这串字符就是第一阶段的答案。

阶段二

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
400efc:	55                   	push   %rbp
400efd: 53 push %rbx
400efe: 48 83 ec 28 sub $0x28,%rsp
400f02: 48 89 e6 mov %rsp,%rsi
400f05: e8 52 05 00 00 callq 40145c <read_six_numbers>
400f0a: 83 3c 24 01 cmpl $0x1,(%rsp)
400f0e: 74 20 je 400f30 <phase_2+0x34>
400f10: e8 25 05 00 00 callq 40143a <explode_bomb>
400f15: eb 19 jmp 400f30 <phase_2+0x34>
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 callq 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>
400f30: 48 8d 5c 24 04 lea 0x4(%rsp),%rbx
400f35: 48 8d 6c 24 18 lea 0x18(%rsp),%rbp
400f3a: eb db jmp 400f17 <phase_2+0x1b>
400f3c: 48 83 c4 28 add $0x28,%rsp
400f40: 5b pop %rbx
400f41: 5d pop %rbp
400f42: c3 retq

进入phase_2函数,观察它的代码,可以发现第5行调用了一个名为read_six_numbers这个函数,顾名思义,这个函数的作用应该是从输入中读取6个数字,那么问题来了,这6个数字是怎么返回的呢?我们注意到第4行中把rsp的值复制给了rsi,我们可以猜测这个函数是使用栈来返回读入的结果。

当然只是猜测是不行的,我们需要用实验去验证我们的想法,我们在输入文件中设置1 2 3 4 5 6这一行输入,然后将断点打在*400f0a这个函数刚返回的位置(注意输入中应该含有第一阶段的答案,不然炸弹就炸在第一阶段了)。运行停在断点之后查看栈中的内容:

我们打出了rsp开始32字节的内容,发现栈中依次存放了输入的6个数,之后就是返回的地址。那么我们可以确定读取的数值就是依次存放在栈中的。

接下来看第6、7、8行,它将rsp中存放的值与1进行比较,如果相等则跳过第8行的引爆代码,说明我们需要输入的第一个数为1 。再看跳转到的位置(19、20行)将rsp+0x4rsp+0x18的值分别存放到了rbxrbp。下一行又进行了一次跳转,来到了第10行,第10行将rbx的地址减4中存放的内容复制到了eax中,rbx的地址减4也就意味着与rsp相等,它的值也就是第一个读入的值。下一行将eax的值乘二,接下来将乘二后的值与rbx也就是第二个值进行比较,如果相同则跳过引爆代码。上面这一系列操作总结起来就是如果第二个值是第一个值的两倍则不引爆。

再往下就是把rbx的值加上4,因为一个int占4个字节,也就是把rbx指向了下一个读入的值。下一步将rbxrbp的值进行比较,回想rbp的值为的rsp+0x18也就是 rsp+24,指向6个int值之后的位置,所以与它进行比较就是判断是否到达临界条件。如果没有到达临界条件,则跳到上一段中比较的部分继承进行。看到这里,我们已经可以判断出phase_2的要求是读入的6个数第一个数必为1,而后面的数字都是前面一个数字的两倍。

所以阶段2的答案为1 2 4 8 16 32.

阶段三

阶段三的代码比较长,我们分开来看:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
0000000000400f43 <phase_3>:
400f43: 48 83 ec 18 sub $0x18,%rsp
400f47: 48 8d 4c 24 0c lea 0xc(%rsp),%rcx
400f4c: 48 8d 54 24 08 lea 0x8(%rsp),%rdx
400f51: be cf 25 40 00 mov $0x4025cf,%esi
400f56: b8 00 00 00 00 mov $0x0,%eax
400f5b: e8 90 fc ff ff callq 400bf0 <__isoc99_sscanf@plt>
400f60: 83 f8 01 cmp $0x1,%eax
400f63: 7f 05 jg 400f6a <phase_3+0x27>
400f65: e8 d0 04 00 00 callq 40143a <explode_bomb>
400f6a: 83 7c 24 08 07 cmpl $0x7,0x8(%rsp)
400f6f: 77 3c ja 400fad <phase_3+0x6a>
400f71: 8b 44 24 08 mov 0x8(%rsp),%eax
400f75: ff 24 c5 70 24 40 00 jmpq *0x402470(,%rax,8)

第3、4两行将rsp+0xcrsp+0x8的值分别给rcxrdx,下一行将一个地址值复制给了esi,接着将eax置为0,下一步调用了库函数sscanf,我们想到sscanf中的参数中需要一个格式化字符串,那么esi中的这个地址值就很有可能存放了这个字符串,我们同样使用gdb在运行时查看这个字符串:

可以看到这就是格式化字符串,读入的是两个整型值。这两个值存放在哪里呢?我们想到之前把rsp+0xcrsp+0x8的值分别给rcxrdx,这是两个地址值,我们可以用之前的方法验证栈中存放的确实是我们读入的这两个值。

下面第8行将eax与1进行比较,eax一般用于存放函数返回值,而sscanf 的返回值是成功读入的数值个数,也就是说这几行将成功读入的个数与1进行比较,如果大于1则跳过引爆的代码。

下面第11行将rsp+0x8中存放的值与0x7进行比较,如果大于0x7则跳到400fad的位置,我们看这个地址的指令:

1
400fad:	e8 88 04 00 00       	callq  40143a <explode_bomb>

引爆炸弹。

下面的两行比较关键:第13行将rsp+0x8中存放的值复制入eax,第14行进行一个跳转,跳转到的地址为0x402470(,%rax,8),这就是一个典型的switch语句的实现:直接跳转到索引*位移的指令位置。

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
x = 0
400f7c: b8 cf 00 00 00 mov $0xcf,%eax
400f81: eb 3b jmp 400fbe <phase_3+0x7b>
x = 2
400f83: b8 c3 02 00 00 mov $0x2c3,%eax
400f88: eb 34 jmp 400fbe <phase_3+0x7b>
x = 3
400f8a: b8 00 01 00 00 mov $0x100,%eax
400f8f: eb 2d jmp 400fbe <phase_3+0x7b>
x = 4
400f91: b8 85 01 00 00 mov $0x185,%eax
400f96: eb 26 jmp 400fbe <phase_3+0x7b>
x = 5
400f98: b8 ce 00 00 00 mov $0xce,%eax
400f9d: eb 1f jmp 400fbe <phase_3+0x7b>
x = 6
400f9f: b8 aa 02 00 00 mov $0x2aa,%eax
400fa4: eb 18 jmp 400fbe <phase_3+0x7b>
x = 7
400fa6: b8 47 01 00 00 mov $0x147,%eax
400fab: eb 11 jmp 400fbe <phase_3+0x7b>

400fad: e8 88 04 00 00 callq 40143a <explode_bomb>
400fb2: b8 00 00 00 00 mov $0x0,%eax
400fb7: eb 05 jmp 400fbe <phase_3+0x7b>
x = 1
400fb9: b8 37 01 00 00 mov $0x137,%eax
400fbe: 3b 44 24 0c cmp 0xc(%rsp),%eax
400fc2: 74 05 je 400fc9 <phase_3+0x86>

400fc4: e8 71 04 00 00 callq 40143a <explode_bomb>
400fc9: 48 83 c4 18 add $0x18,%rsp
400fcd: c3 retq

上面的代码已经加了注释,假设读入的第一个数为x,看到所有分支最后都跳转到了400fbe这行判断中,将eax中的值与rsp+0xc也就是我们读入的第二个数进行判断,如果相等的话跳过引爆代码。

而每个分支都将一个数复制到了eax中,也就是说我们只要根据不同的第一个参数的值读入对应的第二个参数就可以了,所以我们可以随意选择一个x值,这里我选择x=1,对应的第二个参数为0x137换成十进制是311,所以第3阶段的(一个)答案为:

1 311

阶段四

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
000000000040100c <phase_4>:
40100c: 48 83 ec 18 sub $0x18,%rsp
401010: 48 8d 4c 24 0c lea 0xc(%rsp),%rcx
401015: 48 8d 54 24 08 lea 0x8(%rsp),%rdx
40101a: be cf 25 40 00 mov $0x4025cf,%esi
40101f: b8 00 00 00 00 mov $0x0,%eax
401024: e8 c7 fb ff ff callq 400bf0 <__isoc99_sscanf@plt>
401029: 83 f8 02 cmp $0x2,%eax
40102c: 75 07 jne 401035 <phase_4+0x29>
40102e: 83 7c 24 08 0e cmpl $0xe,0x8(%rsp)
401033: 76 05 jbe 40103a <phase_4+0x2e>
401035: e8 00 04 00 00 callq 40143a <explode_bomb>
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 callq 400fce <func4>
40104d: 85 c0 test %eax,%eax
40104f: 75 07 jne 401058 <phase_4+0x4c>

前面的代码比较熟悉,同样是调用了sscanf函数,我们查看格式字符串:

也是读入两个参数存放在rcxrdx中。

同样对读入参数的个数进行了判断,要求成功读入参数的个数等于两个,第11、12行要求输入的第一个参数小于0xe

接下来把0xe赋给edx、0x0赋给esirsp+0x8的值赋给edi。接下来调用了func4函数。

在去查看func4函数的代码之前,我们先查看函数返回后的代码,了解我们需要的结果。第17、18行测试了eax的值如果不为0,就跳转到引爆代码。

所以我们的目标是返回时eax的值为0.下面进入func4函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
0000000000400fce <func4>:
400fce: 48 83 ec 08 sub $0x8,%rsp
400fd2: 89 d0 mov %edx,%eax
400fd4: 29 f0 sub %esi,%eax
400fd6: 89 c1 mov %eax,%ecx
400fd8: c1 e9 1f shr $0x1f,%ecx
400fdb: 01 c8 add %ecx,%eax
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

这段代码之中我们调用了func4,这是一个递归的过程,像之间那样直接分析比较困难,这里我们就将这个代码逆向为C语言再来分析,下面是逆向出的C语言代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
int fun(int a1, int a2, int x){
int b = (a1 - a2) >> 31;
int result = ((a1-a2) + b) >> 1;
b = result + a2;
if(b == x) return 0;
if(b < x) {
result = fun(a1, b + 1, x);
return result * 2 + 1;
}else{
result = fun(b - 1, a2, x);
return result * 2;
}
}

这里的a1`a2初始值分别为之前的0xe0x0`。我们可以直接写个测试程序来跑出能返回0的输入值:

1
2
3
4
5
6
7
8
9
int main(void){
for(int i = 0; i <= 0xe; i++){
if(fun(0xe,0,i) == 0){
printf("%d\n",i) ;
return 0;
}
}
return 0;
}

得出允许的值有0 1 3 7.

回到phase_4的代码:

1
2
3
4
5
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

第1、2行将输入的第二个参数与0进行比较,如果不为0就引爆炸弹。所以输入的第二个参数必为0。

综上我们得出(一个)答案为:

0 0

阶段五

后面的阶段难度开始加大,我们分部分进行分析:

1
2
3
4
5
6
7
0000000000401062 <phase_5>:
401062: 53 push %rbx
401063: 48 83 ec 20 sub $0x20,%rsp
401067: 48 89 fb mov %rdi,%rbx
40106a: 64 48 8b 04 25 28 00 mov %fs:0x28,%rax
401071: 00 00
401073: 48 89 44 24 18 mov %rax,0x18(%rsp)

第4行把输入的地址rdirbx,第5、7行则是在栈中压入了一个哨兵变量。

1
2
3
4
5
401078:	31 c0                	xor    %eax,%eax
40107a: e8 9c 02 00 00 callq 40131b <string_length>
40107f: 83 f8 06 cmp $0x6,%eax
401082: 74 4e je 4010d2 <phase_5+0x70>
401084: e8 b1 03 00 00 callq 40143a <explode_bomb>

第1行清空了eax,第2行中调用了string_length,我们想到之前的把输入放入rbx这个动作,可以推测这个函数是为了统计输入字符的个数,并存放在了eax中。

下面将eax的值与0x6进行比较,等于则进行跳转避免引爆炸弹。我们进入跳转到的位置:

1
2
4010d2:	b8 00 00 00 00       	mov    $0x0,%eax
4010d7: eb b2 jmp 40108b <phase_5+0x29>

eax置为0后进行跳转。

继续进入跳转到的位置:

1
2
3
4
5
6
7
8
9
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
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>

第1行中movzbl命令将从rbx(输入)开始的rax位置的一个字节赋给ecx的低16位。

接下来的两行先把cl中的值(上一步得到)复制到rsp处,再将rsp中的值复制到rdx中,第4行使用掩码0xfedx的低4位。到这里我们总结一下上面的操作:取读入的字符串中rax位置处的字符,再取它的低4位放在edx中。

下面第5行中,将地址0x4024b0+rdx中的一个字节放入edx的低16位中。第6行将这16位复制到了rsp+0x10+rax的位置中。

接下来把rax加1,我们从前面可以看出来这个rax起的是一个索引的作用。第 8行与6进行比较,如果不等于6则跳到第1行重复这个过程。

在这段之中,循环一共进行了6次,分别读取了输入的6个字符,记录这个6个字符的低6位作为索引rdx,从0x4024b0+rdx的位置复制一个字节到rsp+0x10开始的6字节中。结束之后,rsp+0x10开始存放了6个字符。

1
4010ae:	c6 44 24 16 00       	movb   $0x0,0x16(%rsp)

接下来一行在rsp+0x16的位置也就是6个字符之后置上一个0x0也就是终止符\0

1
2
3
4
5
6
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>
4010c6: e8 6f 03 00 00 callq 40143a <explode_bomb>

接下来将0x40245e这个地址赋给esi,把rsp+0x10这个地址赋给rdi,接下来调用strings_not_equal这个函数,之前的经验告诉我们esirdi就是要比较的两个字符串的首地址。如果两个字符串不相同就引爆炸弹。

我们先看0x40245e位置的字符串:

这就是我们应该构造并存放在rsp+0x10处的字符串。

接下来再查看我们复制到rsp中的字符来源也就是0x4024b0开始的字符:

可以看到我们需要的字符flyers的索引分别为9 15 14 5 6 7。这个索引就是我们输入的字符的低4位,那我们只要找到低4位分别是以上数值的字符就可以了。

所以阶段5的(一个)答案为:

ionefg

阶段六

阶段六可以说是最复杂的一个阶段,同样一步步分析:

1
2
3
4
5
6
7
8
9
10
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>

读入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
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>

前面是一系列的赋值操作,第5行将eax减1,eax中的值是rsp位置存放的值。第6、7两行将减一以后的值与5进行比较,小于等于5则跳过引爆代码。也就是说rsp中存放的第一个数必须小于等于6.

之前将r12d置为0,第9行中将r12d的值增加1,下一行与6进行比较,如果相等则跳入下一个阶段。

第12行中把r12d中的值复制给了ebx,下一步又赋给了rax,接下来的一行movrsp+rax*4中的值(也就是第rax+1个读入的int值)给了eax

下一步将eax中的值与rbp地址指向的值进行比较,如果不相同则跳过引爆代码。说明这两个值需要不同,再接下来将ebx中的值加1,再与5进行比较,如果小于等于5则跳到第13行中,更新rax的值,再去从栈中取下一个新的int值和rbp中的进行比较。到这里我们可以看出,从13行到20行相当于一个内循环,从r12d开始,到5结束,不断地取栈中的值与rbp的值比较,也就是要求rbp之后的值需要与rbp不同。

第21、22行则是外循环,它更新了r13的值,令r13指向下一个int值。跳到第3行用r13的值更新rbp的值,也就是把比较的对象向后移一个。同样要求该值小于等于5。后面再进行内循环比较之后的值。

这里我们就可以明白这段代码的作用:限制读入的6个数必须小于等于6并且互不相等。

1
2
3
4
5
6
7
8
9
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>

第1行中将rsp+0x18的值赋给rsi

第2行将r14的值赋给raxr14的值是之前保存的rsp

第3行将0x7赋给ecx,第4行又将ecx复制给edx

下一步将edx减去rax存放的地址指向的值,接下来又将edx的值赋回rax存放的地址指向的值。

第7行将rax的值加4,也就是指向了下一个int值,接着与之前设定的rsi进行的比较,如果不相等则重复这个过程。rsi实际上指向的是6个int值之后的位置,作为一个标记使用。

这段代码总结起来就是将栈中的6个值(假设为x)变为7-x。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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归零,然后跳到第14行处执行。

第14行中从rsp+rsi的位置(也就是栈中我们读入的位置)取出一个数赋给ecx,接下来对取出的这个值进行判断,如果它小于等于1则跳到第9行处。

我们在这里假设这个数确实小于等于1。到第9行,将一个地址值赋给了edx,接下来将edx的值赋给了rsp+2*rsi+0x20的地址指向的值,这里我们可以知道rsi起到的是索引的作用,下面一行将rsi增加4,说明从rsp+0x20开始存放8个字节的数据。再将rsi的值与0x18作比较,说明整个过程要进行6次。接下来又到了第14行将下一个int值给rcx

那么如果rcx的值不小于等于1,继续往下走,第18行将0x1赋给eax,19行将0x6032d0这个地址赋给edx,接下来跳转到了第3行。第3-6行的代码是一起的,也是理解这个过程的关键。

首先第3行的命令,把edx+0x8地址指向的值赋给了edx,这步操作一开始比较难以理解,我们需要先看看edx的初始状态是什么样的,使用gdb在运行时查看内存:

我们可以从这个信息中看出,其实它就是一个链表的结构,首先名字就是node给了提示,再者每一个node中偏移8个字节中储存的都是下一个节点的地址,那么前面8个字节自然就是节点储存的数据。

我们再回过头来看第3行的代码,就不难理解这个操作就是我们常用的p = p -> next,也就是指向下一个节点。

第4行把eax增1,再将eaxecx进行比较,如果不等就再跳到第3步指向链表下一个节点,那么可以看出这4行代码的作用就是从edx这个初始位置开始向后移动ecx-1次,第7行跳过了第9行,把edx赋给了rsp+0x20开始的第rsi个8字节的位置。如果rsi达到0x18则跳出这部分代码。

我们整理一下这个过程,其实就是依次从栈中读取存放的6个数放入rcx,再根据rcx的值找到链表中对应的节点,把节点的地址放入rsp+0x20开始的对应位置中。

1
2
3
4
5
6
7
8
9
10
11
12
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)

这段代码前三行分别将rsp+0x20地址指向值、rsp+0x28的值、rsp+0x50的值赋给了rbxraxrsi。第4行将rbx复制到rcx中,第5行将raxrsp+0x20)中存放的地址复制入rdx,第6行将这个数据赋给了rcx(也就是rbx*(rsp+0x20))节点的指针域。下一步将rax增加8,指向栈中的下一个位置。再与rsi这个临界地址进行比较,如果rax超出末端则跳出这段代码到第12行的位置。

下面把rdx中存放的地址值赋给rcx,跳转到第5行重复过程。

仔细分析,这个过程其实就是按照链表节点在栈中的位置重新将链表连接起来。

最后跳出的第12行则是把新的表尾的指针域赋为NULL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

第2行将ebp赋上0x5,第三行中rbx的值是之前的rsp+0x20,那么rbx+0x8这个地址中存放的值就是下一个节点的地址,赋给了rax

第4行将rax代表的节点的数据取出放入eax,再与rbx代表的节点的数据的值的低4位进行比较,如果前一个节点的数据的低4字节大于等于后一个节点的,则跳过引爆代码。

第8行又是熟悉的操作:使rbx指向下一个节点。

第9、10行减小ebp这个循环变量再进行判断,保证循环进行5次。

也就是说,我们需要使新的链表中前一个节点存放的数据值的低4字节都大于后一个节点的。

弄清楚了过程,下面就可以开始反推答案了:

先找到正确的链表节点排列,根据图:

数据由大到小的排列依次是3 4 5 6 1 2

由于有一步x = 7 - x,所以倒推回来的答案应该是:

4 3 2 1 6 5

秘密阶段

在之前C代码的暗示以及我们查看汇编代码的过程中都可以猜测出有一个秘密阶段的存在,secret_phase的代码就在phase_6后的func7之后。第一个问题是我们如何进入secret_phase

这里可以用一个简单的方法,直接在反汇编代码中搜索secret_phase的入口地址,很快就可以发现在每个阶段的phase_x之后都有一行phase_defused,就在这个函数里面存在callq secret_phase的代码。

我们就开始分析这个phase_defused

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

可以看到第7行将函数num_input_strings的返回值与6进行比较,如果不等于6则的直接跳过中间代码到达最后的结束部分。

从函数名我们可以推测这个函数的作用的是检测读取的字符串的数量,当读取了6个字符串时,就不会跳过中间的代码。我们继续看中间的代码:

第9到14行又是熟悉的sscanf调用过程,我们已经知道esi指向的是格式化字符串的首地址,我们先来查看它的内容:

读取两个整数和一个字符串。

有所不同的是在12行之后又有一行给edi赋上了一个地址值,我们之前所有阶段中edi的值都是来自于我们read_line的地址,想到sscanf 参数中确实存在一个输入,我们可以推测这个edi中存放的是我们读取位置的首地址。

那么我们就可以在运行时查看这个地址的内容,看是从哪里进行读取的:

首先符号表告诉我们这段数据的名字叫做input_strings也就是我们输入的字符串,那么这个地址上的0 0代表的应该就是我们的第4行输入。两个整型数字正好与格式化字符串也是匹配的。现在我们知道,应该在这两个0之后再追加一个字符串作为输入。

第15、16行对成功输入的数据个数进行了一个判断,如果不为3个则跳过调用secret_phase的代码。

第17-19行是对strings_not_equal的调用,我们已经知道它的两个参数分别是esiediesi被赋上了一个地址值,edi被赋上了esp+0x10,我们可以推测出edi的地址就是指向我们读入的第三个字符串的,那么需要比较的对象是什么呢?我们在运行时查看内存的内容:

这就是我们需要的第三个参数。

可以看到如果第三个参数与上面这个字符串相同的话就会调用两次puts输出提示信息,然后进入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

可以看到第3行调用了read_line函数,接着把read_line的返回值赋给了rdi,并调用了strtol函数,这个标准库函数的作用是把一个字符串转换成对应的长整型数值。返回值还是存放在rax中,第8行将rax复制给了rbx,第9行将rax减1赋给eax,第十行与0x3e8进行比较,如果这个值小于等于0x3e8就跳过引爆代码。看到这里我们可以知道我们需要再加入一行数据,它应该是一个小于等于1001的数值。

接下来将ebx赋给了esi,也就是我们一开始输入的rax值。第14行将一个地址值赋给了edi,15行调用了fun7函数。我们还是先往下了解一下我们需要得到的结果。

函数返回后令返回值eax0x2做了一个比较,如果相等则跳过引爆代码。

所以我们需要返回2。

下面查看fun7的代码:

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

第3、4两行先对我们输入的这个数作一个判断,如果等于0直接跳到第19行,返回-1,这显然不是我们想要的结果。

第5行将rdi的值读入到了edx中,第6行则将这个数与我们读入的数进行比较,如果这个数小于等于我们读入的数就跳至第12行,第12行将eax置0,再进行一次相同的比较,如果相等则跳至第20行返回。

如果不等(也就是edx小于我们读入的数),则继续向下执行第15行,这行代码有些与之前的链表跳至下一个节点类似,到这里,我们就需要查看一下rdi这个地址里存放的是怎样一种数据结构:

仔细观察可以发现这是一个二叉树的结构,每个节点第1个8字节存放数据,第2个8字节存放左子树地址,第3个8字节存放右子树位置。并且命令也有规律,naba代表层数,b代表从左至右第b个节点。

根据这个结构,我们可以把树画出来以便我们进行分析。随意找了个工具表示一下:

下面我们回到代码,现在我们知道第15行代码的作用是将rdi移到它的右子树的位置,接着调用fun7,在返回后令eax = 2 * rax + 1

如果第6行的比较中树节点的值大于我们读入的数呢?

代码会进行到第8行,令rdi移到它的左子树的位置,接下来调用fun7在返回后令eax = 2 * eax。下面跳至返回处。

总结上面的过程:edi指向一个树的节点,令edi节点的值与我们读入的值进行比较。

  • 如果两者相等:返回0
  • 如果前者大于后者:rdi移至左子树,返回2 * rax
  • 如果后者大于前者:rdi移至右子树,返回2 * rax + 1

那么我们需要返回2,应该在最后一次调用返回0,倒数第二次调用返回2 * rax + 1,第一次调用返回2 * rax。换句话说,这个数应该在第三层,比父节点大且比根结节小。观察上图,唯一的答案是:

0x16(22)


至此,炸弹全部解除:

实验小结

整个实验包括秘密部分用时九个小时,引爆了3次炸弹(一次因为错误的尝试,两次因为将ni命令错打成n)。

一开始拿到题目的时候会比较蒙,需要先去学习工具的使用与一些编译的基础知道(符号表、定址表等等)花费了一些时间。前几个阶段过于关注函数的具体实现而没有根据常识去推测一些明显函数的作用花费了一些时间。

前4个阶段都算比较简单,考查了一些常用结构在汇编中的出现形式。第5、6与秘密阶段分别考察了堆、链表、二叉树这三个数据结构在内存中的结构与汇编级的使用,受益良多。

这个实验需要细致的分析与大胆的猜测与实验验证,还需要小心操作,最重要的是耐心,面对非常晦涩的汇编代码如何一步步地弄清代码的作用很需要毅力。当然也可以通过自己写出等价的C代码来帮助自己理解。