Bomblab

针对自学材料的bomblab解题过程。

phase_1

disas phase_1查看对应函数的汇编代码，发现其将0x402400作为第二个参数传入strings_not_equal 函数，如果该函数返回值为0,函数结束，否则引爆炸弹。

因此，合理推测其是在比较输入的字符串和0x402400处的字符串，通过在gdb中输入x/s 0x402400查看该处的字符串得到答案。

phase_2

从汇编代码中看见了“read_six_numbers"，推测第二个字符串为6个数字。

cmpl $0x1,(%rsp) 那段说明第一个数得是1，否则会引爆炸弹

如果第一个数是1，之后的代码跳转到的位置将rsp中值复制给eax并翻倍，并和下一个数字比较，如果相等则rbx更新为下一个数字的地址，并比较是否比完了六个数字。

翻译成c代码大概是在做下面的事

int x = 1;
for (int i = 0; i < 6; i++) {
    if (x != a[i]) explode_bomb();
    x = x * 2;
}

因此答案是1 2 4 8 16 32

phase_3

%eax比1大时炸弹不会被引爆

第四个参数和第三个参数被设为了M[R[rsp]+12]和M[R[rsp]+8]处的值，第二个参数被设为了0x4025cf，eax被设为0,

用x/s 0x4025cf发现对应的字符串是%d %d， 推测之后的callq 400bf0输入了两个int

eax储存的是函数的返回值，sscanf的返回值是成功读入的数字个数。

重新在gdb中运行程序，在phase_3输入两个整数（我输入的是1和4）

读入少于两个整数将引爆炸弹。

否则跳转到400f6a，判断M[R[rsp]+8]位置上的数是否比7大，若是，跳转到400fad引爆炸弹，否则将M[R[rsp]+8]上的数复制到eax中，跳转至0x402470(, %rax, 8)指向的位置上的值所储存的位置（间接跳转），其会根据不同的rax中存的值进行跳转。而rax中的值此时就是eax中的值，即读入的第一个数字（可以通过x/32b $rsp验证）。可以通过gdb的”p/x *地址“命令查看该地址的值，看看程序将会跳转到哪里。如果第一个输入的整数为1,那么这里显示的值为0x400fb9，说明程序将会跳转到该位置。

观察代码的对应位置，其将0x137存入eax，并与第二个参数进行比较，这段代码说明若第一个参数为1,第二个参数就得是0x137，即十进制下的311.

phase_4

前半段代码和上一题一样，还是读入两个整数，如果sscanf返回值不等于2就引爆炸弹。随后是将第一个读入的数和0xe比，小于等于则跳转，否则引爆炸弹。跳转后edx，esi，edi的值分别被设为了0xe，0，第一个读入的值，随后调用函数func4。

func4开头将eax设为0xe，并复制进ecx，随后将ecx逻辑右移31位（等于0），加到eax上（此时eax应仍为0xe），随后sar %eax表示将eax算数右移一位（00....1111->00..0111）。接下来将%ecx设为R[rax]+R[rsi]，并比较ecx和edi的值，在小于等于时跳转至0x400ff2，否则将%edx设为R[rcx]-1，并递归调用func4。在调用完成后将eax中的值翻倍并跳转至函数结束。

0x400ff2处执行的操作为：将eax设为0并比较ecx和edi的值，在大于等于时跳转至函数结束，否则将esi设为R[rcx]+1并递归调用func4,随后将eax设为R[rax]+R[rax]+1并退出。

将func4翻译成c代码如下

si = 0;
dx = 15;
di = read();
//di是第一个读入的值
int func4() {
    int ax = dx;
    ax -= si;
    int cx = ax;
    ax += cx >> 31;
    ax >>= 1;
    cx = ax + si;
    if (cx <= di) {
        ax = 0;
        if (cx >= di) {
            return ax;
        } else {
            si = cx+1;
            ax = 2*func4()+1;
        }
    } else {
        dx = cx - 1;
        ax = 2*func4();
        return ax;
    }
}

随后回到phase_4,其剩余的代码在判断func4的返回值是否为0，若非0将会引爆炸弹。因此上述 c语言代码的返回值ax应为0，问题转为确定di的值使得ax为0.

初始时，在进入第一个if之前cx和ax的值为7, 若cx==di，程序将直接返回0, 因此第一个数输入7合法。

随后比较第二个输入的数和0的值，若相等将返回，否则会引爆炸弹。因此第二个数为0.

phase_5

%fs:28 是在通过段寻址从内存中读入金丝雀（canary）值，在本题中可以暂时无视。

继续向下看得知，输入的字符串长为6，底下的跳转到0x40108b部分是一个循环执行了六次，每次操作时会将读入的一个字符存入rdx中，并取其低4位作为edx的值。随后将M[R[%rdx]+0x4024b0]的值的低32位作为%edx的新值。0x4024b0处的字符串是"maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"。

那么这个程序做的是：读入一个长为6的字符串，将每个字母变为0x4024b0向后移动该字母ascii码的低4位对应的字母，最终要变成目标字符串“flyers”。对应的偏移量分别为“9 15 14 5 6 7”，对着ascii码表构造字符串即可。我构造的是“IONEFG”

phase_6

看见汇编代码里的read_six_numbers，说明本题输入的是六个整数

在调用read_six_numbers()之后，通过‘x/32b $rsp’命令知，读入的六个整数被存放在%rsp到0x18(%rsp)之间（每四个字节存一个数）

此时%r13中存放的值为栈顶值，其指向的地址存放的是读入的第一个整数。接下来的语句将该整数复制到%eax中，将其减1并与5比大小。若该整数大于5,则会引爆炸弹。

随后程序将%r12d（初始值为0） 加1后与6比大小，在等于6时跳转至401153，否则将%ebx设为%r12d，将%rax设为%ebx，将%eax设为M[%rsp + 4*%rax]，即第%rax+1个读入的整数，将其与M[%rbp]比较，若相等则会引爆炸弹。否则将%ebx加1后与5比较，在小于等于5时跳转回“将%rax设为%ebx"那一步骤，否则继续。

上面一段对应的部分（到40114b）翻译成c代码如下

int a[6];
int r13 = 0;
_401114:
if (a[r13] - 1 > 5) explode_bomb();
int bp = r13;
int i = 0;
while (i < 6) {
    i++;
    if (i == 6) {
        goto _401153;
    }
    bx = i;
_401135:
    ax = bx;
    ax = a[ax];
    if (ax != a[bp]) {
        bx++;
        if (bx <= 5) {
            goto _401135;
        } else {
            r13++;
            goto _401114; 
        }
    } else {
        explode_bomb();
    }
}

不难看出，程序是在检查输入的六个整数是否全部小于等于6，且两两不同。如果有重复元素，就会引爆炸弹。

接下来看401153处的代码，这段代码将读入的六个整数进行转换，假设读入的数字为x，那么在执行完这段代码后x将被改为7-x。即原先输入的6个数在这里变成了7与其自身的差

随后，esi被设为0，跳转至401197：将ecx设为M[R[rsp]+R[rsi]]，比较其与1的大小，若ecx小于等于1，跳转至401183；否则，eax被设为1，edx被设为0x6032d0，跳转回401176：将rdx设为M[rdx+8]处的值，将eax加1和ecx比大小，若不等于ecx则跳转回401176，否则跳转至401188。

观察到0x6032d0这个东西，用x查看发现标签node1​，猜想这是某种数据结构，多试几次发现一共有node1到node6 6个标签，每个node对应16个字节。

用x/24dw 0x6032d0打出来发现，每个node存有16字节的数据，再用x/24xw 0x6032d0可以发现第9个字节开始的数据是下一个node的地址

其中nodei的第5个字节到第8个字节为第i个输入的整数，因此node翻译成c代码长这样

struct node {
    int x;
    int input_data;
    node *nxt;
}

发现上面这三个元素已经吃满16个字节了，因此第四个值也许是属于*nxt的，实际上只有3个值。

而gdb显示这六个node的x值依次为332， 168， 924， 691， 477， 443，

把内存中那些地址的值画出来可以帮助理解，写成c语言(先逐行翻译成带goto的c语言)大概长这样:

esi = 0;
goto _401197;
_401176:
rdx = M[rdx + 8];//rdx是指向node的指针，+8是跳转到下一个node
eax++;	//如果是从401197跳转过来的，eax此时必为2
if (eax != ecx) {
    goto _401176;
} else goto _401188;
_401183:
edx = 0x6032d0;
_401188:
M[rsp+2*rsi + 32] = rdx;//把当前结点（第ecx个node）地址存入M[rsp+2*rsi+32]
rsi += 4;
if (rsi == 24) {
    goto _4011ab;
}
_401197:
ecx = M[rsp + rsi];	//rsi从0开始，每次+4，即遍历输入的6个整数（已经和7取过补了）
if (ecx <= 1) {	//原先这个数>=6（现在是<=1的），根据之前的过程只可能是输入的6时跳转至401183
    goto _401183;
} else {
    eax = 1;
    edx = 0x6032d0;
    goto _401176;
} 
_4011ab:
rbx = M[rsp + 32];//当前结点的地址
rax = rsp + 40;
rsi = rsp + 80;//一共6个
rcx = rbx;
_4011bd:
rdx = M[rax];//下一个结点的地址
M[rcx+8] = rdx;
rax += 8;
if (rax == rsi) goto _4011d2;
rcx = rdx;	
goto _4011bd;
_4011d2:
M[rdx+8] = 0;//这里是链表的最后一个结点的，把它指向下一个结点的指针值设为0
ebp = 5;
_4011df:
rax = M[rbx+8];
eax = M[rax];
if (M[rbx] >= eax) goto _4011ee;//按照输入的排列排序后，当前结点的x值必须不小于下一个结点
else explode_bomb();
_4011ee:
rbx = M[rbx+8];
ebp--;
if (ebp) goto _4011df;

按照上述注释分析出，程序按照输入的排列与7取补后得到的排列对6个node进行排序，使得排序后x值依次递减。

因此4 3 2 1 6 5 合法

secret_phase

先看该函数对应的汇编源码

查man得strtol是将输入的字符串转成长整型的函数，因此rax中为输入的字符串表示的数字，rax-1要小于等于0x3e8 （即1000），否则炸弹会被引爆。随后edi=0x6030f0并调用fun7。

fun7在rdi为0时直接返回-1，否则edx=M[rdi]，当edx<=esi时跳转至401220，否则rdi=M[rdi+8]并递归调用fun7，随后将eax翻倍并return。

401220处，将eax设为0，在esi等于edx时return，否则rdi=M[rdi+16]并递归调用fun7，随后eax=2*rax+1并返回。

fun7写成c代码是这样的

//si是输入的数
long long fun7() {
    if (di == 0) {
        return -1;
    }
    dx = M[di];
    if (dx <= si) {
        ax = 0;
        if (dx == si) 
            return ax;
        di = M[di+16];
        ax = fun7();
        ax = 2 * ax + 1;
        return ax;
    } else {
        di = M[di + 8];
        ax = fun7();
        ax = 2 * ax;
        return ax;
    }
}

在gdb中查看0x6030f0附近的数据如下

0x6030f0 <n1>:  0x0000000000000024      0x0000000000603110
0x603100 <n1+16>:       0x0000000000603130      0x0000000000000000
0x603110 <n21>: 0x0000000000000008      0x0000000000603190
0x603120 <n21+16>:      0x0000000000603150      0x0000000000000000
0x603130 <n22>: 0x0000000000000032      0x0000000000603170
0x603140 <n22+16>:      0x00000000006031b0      0x0000000000000000
0x603150 <n32>: 0x0000000000000016      0x0000000000603270
0x603160 <n32+16>:      0x0000000000603230      0x0000000000000000
0x603170 <n33>: 0x000000000000002d      0x00000000006031d0
0x603180 <n33+16>:      0x0000000000603290      0x0000000000000000
0x603190 <n31>: 0x0000000000000006      0x00000000006031f0
0x6031a0 <n31+16>:      0x0000000000603250      0x0000000000000000
0x6031b0 <n34>: 0x000000000000006b      0x0000000000603210
0x6031c0 <n34+16>:      0x00000000006032b0      0x0000000000000000
0x6031d0 <n45>: 0x0000000000000028      0x0000000000000000
0x6031e0 <n45+16>:      0x0000000000000000      0x0000000000000000
0x6031f0 <n41>: 0x0000000000000001      0x0000000000000000
0x603200 <n41+16>:      0x0000000000000000      0x0000000000000000
0x603210 <n47>: 0x0000000000000063      0x0000000000000000
0x603220 <n47+16>:      0x0000000000000000      0x0000000000000000
0x603230 <n44>: 0x0000000000000023      0x0000000000000000
0x603240 <n44+16>:      0x0000000000000000      0x0000000000000000
0x603250 <n42>: 0x0000000000000007      0x0000000000000000
0x603260 <n42+16>:      0x0000000000000000      0x0000000000000000
0x603270 <n43>: 0x0000000000000014      0x0000000000000000
0x603280 <n43+16>:      0x0000000000000000      0x0000000000000000
0x603290 <n46>: 0x000000000000002f      0x0000000000000000
0x6032a0 <n46+16>:      0x0000000000000000      0x0000000000000000
0x6032b0 <n48>: 0x00000000000003e9      0x0000000000000000
0x6032c0 <n48+16>:      0x0000000000000000      0x0000000000000000
0x6032d0 <node1>:       0x000000010000014c      0x00000000006032e0
0x6032e0 <node2>:       0x00000002000000a8      0x00000000006032f0

一共有1，21，22，32，33，31，34，45，41，47，44，42，43，46，48，共1+2+4+8个这种结构，猜测这是二叉树相关的数据结构。

每个结点的三个数据(最后那个0x00...是内存对齐用的)，分别是该结点的值和其两个儿子的地址。\(n_{ij}\)的两个孩子分别是\(n_{i+1,2j-1}\)和\(n_{i+1,2j}\)

fun7中，di表示当前结点的地址，若为0表示走到了空结点，返回-1. di=M[di+16]是走向右儿子，dx是当前结点的权值。

结合上述分析可以将fun7进一步翻译为如下c代码

long long a[maxn];
int ls[maxn], rs[maxn];
long long input_data;
/*输入数据到input_data中...*/
long long fun7(int p) {
    if (p == 0) return -1;
    long long cur = a[p], res = 0;
    if (cur <= input_data) {
        res = 0;
        if (cur == input_data) {
            return res;
        }
        p = rs[p];
        res = fun7(p);
        return res * 2 + 1;
    } else {
        p = ls[p];
        res = fun7(p);
        return res * 2;
    }
}

可以很容易地看出：如果当前结点的值等于输入的值，fun7将会返回0.否则若大于当前值，fun7将会递归到当前结点的右子树中，返回右子树的答案的2倍+1，若小于当前值，则会返回左子树答案的两倍。

由于secret_phase中fun7的返回值得是2，否则炸弹会被引爆，我们需要构造能使得fun7返回2的输入数据。

如果不想构造的话可以把树建出来，写个程序枚举输入的值跑一下，看看何时能得到2。

但分析一下再构造也不难：这是一棵二叉搜索树，fun7其实是在树上查找输入的值是否存在。

首先输入的值必须得是这些结点的权值中的某一个，否则程序无论递归了几次都会返回一个负数。

假设答案存在，那么递归终点的返回值必为0。由于res是整数，通过res*2+1得到2不可能，因此答案必在1号点的左子树中。要想得到1就得是\(0\times2+1\)，因此输入应为22。

下面看看如何触发secret_phase

在汇编代码中查找secret_phase，发现其被phase_defused()函数调用，x/s查看0x402520得到字符串“But finding it and solving it are quite different...”，说明在输出该字符串之后secret_phase触发。

在gdb中单步调试，发现phase_6解完以后phase_defused函数读入了%d %d %s，两个整数和一个字符串，且0x603870存着“7 0”，表示前两个”%d”已经被输入了，我们只需要输入最后的字符串。随后0x402622被存入esi，其指向位置上的字符串为“DrEvil”。后面还有一个“strings_not_equal",可知是在字符串不相等时跳转到结尾。

要想不跳到结尾执行中间的代码，就得在输入7 0 之后输入DrEvil，恰好phase_4我选用的答案是7 0，直接试试在后面跟一个DrEvil后继续输答案，发现在执行完phase_6后我们就能看见提示了。此时输入22，即解完最后的炸弹。