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，即解完最后的炸弹。