csapp bomb_lab

bomb lab

初见bomb

A “binary bomb” is a program provided to students as an object code file. When run, it prompts the user to type in 6 different strings. If any of these is incorrect, the bomb “explodes,” printing an error message and logging the event on a grading server. Students must “defuse” their own unique bomb by disassembling and reverse engineering the program to determine what the 6 strings should be. The lab teaches students to understand assembly language, and also forces them to learn how to use a debugger. It’s also great fun. A legendary lab among the CMU undergrads.

二进制炸弹，每一个phase都是最喜欢的一集。

概览：

每一个phase在bomb.c中结构都类似，那么我们便可以使用gdb对每一个phase进行反汇编。

1
2
3

input = read_line();             /* Get input                   */
   phase_1(input);                  /* Run the phase               */
   phase_defused();                 /* Drat!  They figured it out!

输入传入phase_1，若成功返回则拆弹成功。

phase_1

Dump of assembler code for function phase_1:
   0x0000000000400ee0 <+0>:     sub    $0x8,%rsp
   0x0000000000400ee4 <+4>:     mov    $0x402400,%esi
   0x0000000000400ee9 <+9>:     call   0x401338 <strings_not_equal>
   0x0000000000400eee <+14>:    test   %eax,%eax
   0x0000000000400ef0 <+16>:    je     0x400ef7 <phase_1+23>
   0x0000000000400ef2 <+18>:    call   0x40143a <explode_bomb>
   0x0000000000400ef7 <+23>:    add    $0x8,%rsp
   0x0000000000400efb <+27>:    ret
End of assembler dump.

根据函数名字，不难看出我们只需要得到0x402400处的字符串便能返回成功。

直接获取0x402400处的值：x/s 0x402400

1 2	`(gdb) x/s 0x402400 0x402400: "Border relations with Canada have never been better."`

phase_1解除成功。

1	`Phase 1 defused. How about the next one?`

phase_2

反汇编：

Dump of assembler code for function phase_2:
   0x0000000000400efc <+0>:     push   %rbp
   0x0000000000400efd <+1>:     push   %rbx
   0x0000000000400efe <+2>:     sub    $0x28,%rsp
   0x0000000000400f02 <+6>:     mov    %rsp,%rsi
   0x0000000000400f05 <+9>:     call   0x40145c <read_six_numbers>

第5行中，将栈顶指针传给rsi作为read_six_numbers的参数

Dump of assembler code for function read_six_numbers:
   0x000000000040145c <+0>:     sub    $0x18,%rsp
   0x0000000000401460 <+4>:     mov    %rsi,%rdx
   0x0000000000401463 <+7>:     lea    0x4(%rsi),%rcx
   0x0000000000401467 <+11>:    lea    0x14(%rsi),%rax
   0x000000000040146b <+15>:    mov    %rax,0x8(%rsp)
   0x0000000000401470 <+20>:    lea    0x10(%rsi),%rax
   0x0000000000401474 <+24>:    mov    %rax,(%rsp)
   0x0000000000401478 <+28>:    lea    0xc(%rsi),%r9
   0x000000000040147c <+32>:    lea    0x8(%rsi),%r8
   0x0000000000401480 <+36>:    mov    $0x4025c3,%esi
   0x0000000000401485 <+41>:    mov    $0x0,%eax
   0x000000000040148a <+46>:    call   0x400bf0 <__isoc99_sscanf@plt>
   0x000000000040148f <+51>:    cmp    $0x5,%eax
   0x0000000000401492 <+54>:    jg     0x401499 <read_six_numbers+61>
   0x0000000000401494 <+56>:    call   0x40143a <explode_bomb>
   0x0000000000401499 <+61>:    add    $0x18,%rsp
   0x000000000040149d <+65>:    ret
End of assembler dump.

对上述内容做简单梳理

栈空间	指令	注
rsi+14	lea 0x14(%rsi),%rax	mov %rax,0x8(%rsp)
rsi+10	lea 0x10(%rsi),%rax	mov %rax,(%rsp)
rsi+c	lea 0xc(%rsi),%r9
rsi+8	lea 0x8(%rsi),%r8
rsi+4	lea 0x4(%rsi),%rcx
rsi	mov %rsi,%rdx
rsp+8	rsi+14
rsp	rsi+10

输入的6个数字所在的位置就分别是：R[%rsp] R[%rsp+0x8] %rsi %rsi+0x4 %rsi+0x8 %rsi+0xc

返回phase_2函数后，利用栈顶指针调用就是： %rsp %rsp+0x4 %rsp+0x8 %rsp+0xc %rsp+0x10 %rsp+0x14

指令执行到0x401480，上图中加载的指令的栈空间

此时遇到一个内存地址0x4025c3 查看

1 2	`(gdb) x/s 0x4025c3 0x4025c3: "%d %d %d %d %d %d"`

看phase_2剩余部分。

   0x0000000000400f0a <+14>:    cmpl   $0x1,(%rsp)
   0x0000000000400f0e <+18>:    je     0x400f30 <phase_2+52>
   0x0000000000400f10 <+20>:    call   0x40143a <explode_bomb>
   0x0000000000400f15 <+25>:    jmp    0x400f30 <phase_2+52>
   0x0000000000400f17 <+27>:    mov    -0x4(%rbx),%eax
   0x0000000000400f1a <+30>:    add    %eax,%eax
   0x0000000000400f1c <+32>:    cmp    %eax,(%rbx)
   0x0000000000400f1e <+34>:    je     0x400f25 <phase_2+41>
   0x0000000000400f20 <+36>:    call   0x40143a <explode_bomb>
   0x0000000000400f25 <+41>:    add    $0x4,%rbx
   0x0000000000400f29 <+45>:    cmp    %rbp,%rbx
   0x0000000000400f2c <+48>:    jne    0x400f17 <phase_2+27>
   0x0000000000400f2e <+50>:    jmp    0x400f3c <phase_2+64>
   0x0000000000400f30 <+52>:    lea    0x4(%rsp),%rbx
   0x0000000000400f35 <+57>:    lea    0x18(%rsp),%rbp
   0x0000000000400f3a <+62>:    jmp    0x400f17 <phase_2+27>
   0x0000000000400f3c <+64>:    add    $0x28,%rsp
   0x0000000000400f40 <+68>:    pop    %rbx
   0x0000000000400f41 <+69>:    pop    %rbp
   0x0000000000400f42 <+70>:    ret
End of assembler dump.

第二行，判断(%rsp)是否为1，不相等则引爆。
循环规律，后一个数是前一个数的2倍，可得答案：1 2 4 8 16 32

1	`That's number 2. Keep going!`

phase_3

Dump of assembler code for function phase_3:   
   0x0000000000400f43 <+0>:     sub    $0x18,%rsp
   0x0000000000400f47 <+4>:     lea    0xc(%rsp),%rcx
   0x0000000000400f4c <+9>:     lea    0x8(%rsp),%rdx
   0x0000000000400f51 <+14>:    mov    $0x4025cf,%esi
   0x0000000000400f56 <+19>:    mov    $0x0,%eax
   0x0000000000400f5b <+24>:    call   0x400bf0 <__isoc99_sscanf@plt>
   0x0000000000400f60 <+29>:    cmp    $0x1,%eax
   0x0000000000400f63 <+32>:    jg     0x400f6a <phase_3+39>
   0x0000000000400f65 <+34>:    call   0x40143a <explode_bomb>
   0x0000000000400f6a <+39>:    cmpl   $0x7,0x8(%rsp)
   0x0000000000400f6f <+44>:    ja     0x400fad <phase_3+106>
   0x0000000000400f71 <+46>:    mov    0x8(%rsp),%eax
   0x0000000000400f75 <+50>:    jmp    *0x402470(,%rax,8)
   0x0000000000400f7c <+57>:    mov    $0xcf,%eax
   0x0000000000400f81 <+62>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f83 <+64>:    mov    $0x2c3,%eax
   0x0000000000400f88 <+69>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f8a <+71>:    mov    $0x100,%eax
   0x0000000000400f8f <+76>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f91 <+78>:    mov    $0x185,%eax
   0x0000000000400f96 <+83>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f98 <+85>:    mov    $0xce,%eax
   0x0000000000400f9d <+90>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f9f <+92>:    mov    $0x2aa,%eax
   0x0000000000400fa4 <+97>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400fa6 <+99>:    mov    $0x147,%eax
   0x0000000000400fab <+104>:   jmp    0x400fbe <phase_3+123>
   0x0000000000400fad <+106>:   call   0x40143a <explode_bomb>
   0x0000000000400fb2 <+111>:   mov    $0x0,%eax
   0x0000000000400fb7 <+116>:   jmp    0x400fbe <phase_3+123>
   0x0000000000400fb9 <+118>:   mov    $0x137,%eax
   0x0000000000400fbe <+123>:   cmp    0xc(%rsp),%eax
   0x0000000000400fc2 <+127>:   je     0x400fc9 <phase_3+134>
   0x0000000000400fc4 <+129>:   call   0x40143a <explode_bomb>
   0x0000000000400fc9 <+134>:   add    $0x18,%rsp
   0x0000000000400fcd <+138>:   ret
End of assembler dump.

查看0x4025cf的内容

1 2	`(gdb) x/s 0x4025cf 0x4025cf: "%d %d"`

受第二题启发，我们可以知道输入就在rsp+8和rsp+c
第10行说明第一个输入不能大于7
第十六行假设第一个输入为1，查看0x402478，

(gdb) x/x 0x402478
0x402478:       0xb9
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

  0xb9=311

  答案 1 311

## phase_4

#### 反汇编phase_4

```assembly
Dump of assembler code for function phase_4:
   0x000000000040100c <+0>:     sub    $0x18,%rsp
   0x0000000000401010 <+4>:     lea    0xc(%rsp),%rcx  #第二个输入存在0xc(%rsp)
   0x0000000000401015 <+9>:     lea    0x8(%rsp),%rdx  #第一个输入存在0x8(%rsp)
   0x000000000040101a <+14>:    mov    $0x4025cf,%esi
   0x000000000040101f <+19>:    mov    $0x0,%eax
   0x0000000000401024 <+24>:    call   0x400bf0 <__isoc99_sscanf@plt>
   0x0000000000401029 <+29>:    cmp    $0x2,%eax
   0x000000000040102c <+32>:    jne    0x401035 <phase_4+41> #输入数量不为2直接爆
   0x000000000040102e <+34>:    cmpl   $0xe,0x8(%rsp)
   0x0000000000401033 <+39>:    jbe    0x40103a <phase_4+46> #若第一个参数>14，爆
   0x0000000000401035 <+41>:    call   0x40143a <explode_bomb>
   0x000000000040103a <+46>:    mov    $0xe,%edx #%edx=0xe
   0x000000000040103f <+51>:    mov    $0x0,%esi #esi=0x0
   0x0000000000401044 <+56>:    mov    0x8(%rsp),%edi #%edi=0x8(%rsp)
   0x0000000000401048 <+60>:    call   0x400fce <func4>
   0x000000000040104d <+65>:    test   %eax,%eax
   0x000000000040104f <+67>:    jne    0x401058 <phase_4+76> #func4返回值为0才不爆
   0x0000000000401051 <+69>:    cmpl   $0x0,0xc(%rsp) #第二个输入为0才不爆
   0x0000000000401056 <+74>:    je     0x40105d <phase_4+81>
   0x0000000000401058 <+76>:    call   0x40143a <explode_bomb>
   0x000000000040105d <+81>:    add    $0x18,%rsp
   0x0000000000401061 <+85>:    ret
End of assembler dump.

反汇编func4

int func4 ( int edi, int esi, int edx ) 返回值放在 eax

注释为初始情况下第一次的情况

Dump of assembler code for function func4:
   0x0000000000400fce <+0>:     sub    $0x8,%rsp
   0x0000000000400fd2 <+4>:     mov    %edx,%eax #%eax=%edx
   0x0000000000400fd4 <+6>:     sub    %esi,%eax #%eax=%edx-%esi=0xe
   0x0000000000400fd6 <+8>:     mov    %eax,%ecx #%ecx=%eax=0xe
   0x0000000000400fd8 <+10>:    shr    $0x1f,%ecx #%ecx=(%eax>>31)
   0x0000000000400fdb <+13>:    add    %ecx,%eax #%eax=(%eax>>31)
   0x0000000000400fdd <+15>:    sar    %eax #右移一位 %eax=((%eax>>31)>>1) %eax=0x7
   0x0000000000400fdf <+17>:    lea    (%rax,%rsi,1),%ecx #ecx=%rax+%rsi=0x7
   0x0000000000400fe2 <+20>:    cmp    %edi,%ecx #0x7-x1
   0x0000000000400fe4 <+22>:    jle    0x400ff2 <func4+36> #edi>=ecx时跳转
   0x0000000000400fe6 <+24>:    lea    -0x1(%rcx),%edx #此处的条件是ecx>edi，
   0x0000000000400fe9 <+27>:    call   0x400fce <func4> #调用func4（edi,esi,ecx-1）
   0x0000000000400fee <+32>:    add    %eax,%eax #返回结果2*func4（edi,esi,ecx）
   0x0000000000400ff0 <+34>:    jmp    0x401007 <func4+57>
   0x0000000000400ff2 <+36>:    mov    $0x0,%eax #此处的条件是ecx<=edi，eax=0 
   0x0000000000400ff7 <+41>:    cmp    %edi,%ecx #ecx-edi=0x7-x1
   0x0000000000400ff9 <+43>:    jge    0x401007 <func4+57> #edi<=ecx跳转
   0x0000000000400ffb <+45>:    lea    0x1(%rcx),%esi  
   0x0000000000400ffe <+48>:    call   0x400fce <func4> #调用func4(edi,esi+1,edx)
   0x0000000000401003 <+53>:    lea    0x1(%rax,%rax,1),%eax #返回2*func4(edi,esi+1,edx)+1
   0x0000000000401007 <+57>:    add    $0x8,%rsp
   0x000000000040100b <+61>:    ret
End of assembler dump.

C语言代码实现func4

int func4 ( int edi, int esi, int edx ) //初始值:edi=x1,esi=0x0,edx=0xe
{// 返回值为eax
    eax = edx - esi;  //3、4行
    eax = (eax + (eax >> 31)) >> 1;  //5-8行
    ecx = eax + exi;  //9行
    if(edi < ecx) 
        return  2 * func4(edi, esi, edx - 1); //14行
    else if (edi > ecx)
        return  2 * func4(edi, esi + 1, edx) + 1; //21行
    else
        return  0;
}

发现x=7直接满足条件

答案7 0

phase_5

Dump of assembler code for function phase_5:
   0x0000000000401062 <+0>:     push   %rbx
   0x0000000000401063 <+1>:     sub    $0x20,%rsp #32字节栈帧
   0x0000000000401067 <+5>:     mov    %rdi,%rbx #输入存放在%rbx中
   0x000000000040106a <+8>:     mov    %fs:0x28,%rax  
   0x0000000000401073 <+17>:    mov    %rax,0x18(%rsp) #fs段偏移0x28存放到%rsp+0x18
   0x0000000000401078 <+22>:    xor    %eax,%eax #eax置0
   0x000000000040107a <+24>:    call   0x40131b <string_length> 
   0x000000000040107f <+29>:    cmp    $0x6,%eax #比较长度是否为6，不为6直接爆炸
   0x0000000000401082 <+32>:    je     0x4010d2 <phase_5+112>
   0x0000000000401084 <+34>:    call   0x40143a <explode_bomb>
   0x0000000000401089 <+39>:    jmp    0x4010d2 <phase_5+112>
   0x000000000040108b <+41>:    movzbl (%rbx,%rax,1),%ecx #%ecx=%ebx+%rax
   0x000000000040108f <+45>:    mov    %cl,(%rsp)
   0x0000000000401092 <+48>:    mov    (%rsp),%rdx
   0x0000000000401096 <+52>:    and    $0xf,%edx #截断取最后四位
   0x0000000000401099 <+55>:    movzbl 0x4024b0(%rdx),%edx
   0x00000000004010a0 <+62>:    mov    %dl,0x10(%rsp,%rax,1) dl低4位到rsp+rax+10
   0x00000000004010a4 <+66>:    add    $0x1,%rax
   0x00000000004010a8 <+70>:    cmp    $0x6,%rax #%rax作为计数器
   0x00000000004010ac <+74>:    jne    0x40108b <phase_5+41>
   0x00000000004010ae <+76>:    movb   $0x0,0x16(%rsp)
   0x00000000004010b3 <+81>:    mov    $0x40245e,%esi
   0x00000000004010b8 <+86>:    lea    0x10(%rsp),%rdi
   0x00000000004010bd <+91>:    call   0x401338 <strings_not_equal>
   0x00000000004010c2 <+96>:    test   %eax,%eax
   0x00000000004010c4 <+98>:    je     0x4010d9 <phase_5+119>
   0x00000000004010c6 <+100>:   call   0x40143a <explode_bomb>
   0x00000000004010cb <+105>:   nopl   0x0(%rax,%rax,1)
   0x00000000004010d0 <+110>:   jmp    0x4010d9 <phase_5+119>
   0x00000000004010d2 <+112>:   mov    $0x0,%eax 
   0x00000000004010d7 <+117>:   jmp    0x40108b <phase_5+41>
   0x00000000004010d9 <+119>:   mov    0x18(%rsp),%rax
   0x00000000004010de <+124>:   xor    %fs:0x28,%rax
   0x00000000004010e7 <+133>:   je     0x4010ee <phase_5+140>
   0x00000000004010e9 <+135>:   call   0x400b30 <__stack_chk_fail@plt>
   0x00000000004010ee <+140>:   add    $0x20,%rsp
   0x00000000004010f2 <+144>:   pop    %rbx
   0x00000000004010f3 <+145>:   ret
End of assembler dump.

0x4024b0处：maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?

+41到+74的代码使用gpt转换后

void phase_5(const char* rbx) {
    int rax = 0;
    int rsp_value;
    while (rax != 6) {
        char ecx = rbx[rax];
        *(char*)(&rsp_value) = ecx;
        int rdx = rsp_value;
        rdx &= 0xf;
        int edx = *(char*)(0x4024b0 + rdx);
        *(char*)(&rsp_value + rax + 0x10) = edx;
        rax += 1;
    }
}

退出循环时，%rsp+10处以此存储着6个字符

继续看+76后的代码

查看0x40245e

字符串：flyers

调用strings_not_equal函数，判断栈上的六个字符是否与这个字符串的相等。

我们能够知道，这六个字符是通过我们输入的字符的ascii码的低4位作为索引，查找maduiersnfotvbyl这个i部分的字符。

在maduiersnfotvbyl中，f为第9位，l第15位，y第14位，e第5位，r第6位，s第7位。

即我们输入的字符，其ascii码的低4位依次是1001,1111,1110,0101,0110,0111。

即答案为ionuvw

phase_6

0x00000000004010f4 <+0>:     push   %r14
0x00000000004010f6 <+2>:     push   %r13
0x00000000004010f8 <+4>:     push   %r12
0x00000000004010fa <+6>:     push   %rbp
0x00000000004010fb <+7>:     push   %rbx
0x00000000004010fc <+8>:     sub    $0x50,%rsp
0x0000000000401100 <+12>:    mov    %rsp,%r13
0x0000000000401103 <+15>:    mov    %rsp,%rsi
0x0000000000401106 <+18>:    call   0x40145c <read_six_numbers>

调用read_six_numbers函数，参考phase_2

rsp处存放6个数字

0x000000000040110b <+23>:    mov    %rsp,%r14
0x000000000040110e <+26>:    mov    $0x0,%r12d
0x0000000000401114 <+32>:    mov    %r13,%rbp
0x0000000000401117 <+35>:    mov    0x0(%r13),%eax
0x000000000040111b <+39>:    sub    $0x1,%eax
0x000000000040111e <+42>:    cmp    $0x5,%eax
0x0000000000401121 <+45>:    jbe    0x401128 <phase_6+52> #输入[r13]-1<=5跳转
0x0000000000401123 <+47>:    call   0x40143a <explode_bomb> #输入[r13]-1>5直接爆
0x0000000000401128 <+52>:    add    $0x1,%r12d 
0x000000000040112c <+56>:    cmp    $0x6,%r12d 
0x0000000000401130 <+60>:    je     0x401153 <phase_6+95> #跳出循环
0x0000000000401132 <+62>:    mov    %r12d,%ebx
0x0000000000401135 <+65>:    movslq %ebx,%rax
0x0000000000401138 <+68>:    mov    (%rsp,%rax,4),%eax  
0x000000000040113b <+71>:    cmp    %eax,0x0(%rbp) #输入[r12d]与输入[r13]比较  
0x000000000040113e <+74>:    jne    0x401145 <phase_6+81> #不相等跳转
0x0000000000401140 <+76>:    call   0x40143a <explode_bomb> #两数字相等才爆
0x0000000000401145 <+81>:    add    $0x1,%ebx
0x0000000000401148 <+84>:    cmp    $0x5,%ebx
0x000000000040114b <+87>:    jle    0x401135 <phase_6+65>
0x000000000040114d <+89>:    add    $0x4,%r13
0x0000000000401151 <+93>:    jmp    0x401114 <phase_6+32>

这一部分对输入的要求

不大于6
互不相同

0x0000000000401153 <+95>:    lea    0x18(%rsp),%rsi
0x0000000000401158 <+100>:   mov    %r14,%rax
0x000000000040115b <+103>:   mov    $0x7,%ecx
0x0000000000401160 <+108>:   mov    %ecx,%edx #edx=7
0x0000000000401162 <+110>:   sub    (%rax),%edx 
0x0000000000401164 <+112>:   mov    %edx,(%rax) #
0x0000000000401166 <+114>:   add    $0x4,%rax
0x000000000040116a <+118>:   cmp    %rsi,%rax
0x000000000040116d <+121>:   jne    0x401160 <phase_6+108>

这一part简单的c语言转换

1
2
3

rsi=0x18(%rsp)
for(rax=%r14,rax<rsi,rax++)
 {num[rax]=7-n[rax]；} //假设输入数组名为n，变换后的为num

可以看到这一part主要是对输入进行了简单的变换

0x000000000040116f <+123>:   mov    $0x0,%esi
0x0000000000401174 <+128>:   jmp    0x401197 <phase_6+163>
0x0000000000401176 <+130>:   mov    0x8(%rdx),%rdx
0x000000000040117a <+134>:   add    $0x1,%eax
0x000000000040117d <+137>:   cmp    %ecx,%eax
0x000000000040117f <+139>:   jne    0x401176 <phase_6+130>
0x0000000000401181 <+141>:   jmp    0x401188 <phase_6+148>
0x0000000000401183 <+143>:   mov    $0x6032d0,%edx
0x0000000000401188 <+148>:   mov    %rdx,0x20(%rsp,%rsi,2) #rsp=rsp+rsi*2+0x20
0x000000000040118d <+153>:   add    $0x4,%rsi #rsi+=0x4
0x0000000000401191 <+157>:   cmp    $0x18,%rsi 
0x0000000000401195 <+161>:   je     0x4011ab <phase_6+183> #rsi=0x18跳转
0x0000000000401197 <+163>:   mov    (%rsp,%rsi,1),%ecx #ecx=rsp+rsi=num[rsi]
0x000000000040119a <+166>:   cmp    $0x1,%ecx  #ecx<=1跳转
0x000000000040119d <+169>:   jle    0x401183 <phase_6+143>
0x000000000040119f <+171>:   mov    $0x1,%eax #num[rsi]>1
0x00000000004011a4 <+176>:   mov    $0x6032d0,%edx
0x00000000004011a9 <+181>:   jmp    0x401176 <phase_6+130>

+163: ecx=num[rsi]
+166:如果num[0]=1跳转

+143:查看0x6032d0内存空间

(gdb) x/24x 0x6032d0
0x6032d0 <node1>:       0x0000014c      0x00000001      0x006032e0      0x00000000
0x6032e0 <node2>:       0x000000a8      0x00000002      0x006032f0      0x00000000
0x6032f0 <node3>:       0x0000039c      0x00000003      0x00603300      0x00000000
0x603300 <node4>:       0x000002b3      0x00000004      0x00603310      0x00000000
0x603310 <node5>:       0x000001dd      0x00000005      0x00603320      0x00000000
0x603320 <node6>:       0x000001bb      0x00000006      0x00000000      0x00000000

不难发现这是一个 链表结构 第一列是数值，第二列序号，第三列是下一个节点的地址

+148~+161: node[2]=node[1]->next
+171:num[rsi]>1时，eax=1,edx=0x6032d0，然后跳转
+130:rdx=rdx+0x8,eax++,eax!=ecx则一直循环
当ecx=eax时，rsp=node[num[i]]

至此我们可以发现，这一部分的操作是将指针移动到node[num[i]]处，即栈空间的依次存放着node[num[0]]~node[num[6]]。

此时栈空间的情况如下表所示

栈地址	内容
rsp+0x48	node[num[5]]
rsp+0x40	node[num[4]]
rsp+0x38	node[num[3]]
rsp+0x30	node[num[2]]
rsp+0x28	node[num[1]]
rsp+0x20	node[num[0]]
rsp+0x14	num[5]
rsp+0x10	num[4]
rsp+0xc	num[3]
rsp+0x8	num[2]
rsp+0x4	num[1]
rsp	num[0]

0x00000000004011ab <+183>:   mov    0x20(%rsp),%rbx #rax=node[num[0]]
0x00000000004011b0 <+188>:   lea    0x28(%rsp),%rax #node[num[1]]
0x00000000004011b5 <+193>:   lea    0x50(%rsp),%rsi 
0x00000000004011ba <+198>:   mov    %rbx,%rcx #rcx=rbx=node[num[0]]
0x00000000004011bd <+201>:   mov    (%rax),%rdx #rdx= node[num[1]]
0x00000000004011c0 <+204>:   mov    %rdx,0x8(%rcx)
0x00000000004011c4 <+208>:   add    $0x8,%rax
0x00000000004011c8 <+212>:   cmp    %rsi,%rax
0x00000000004011cb <+215>:   je     0x4011d2 <phase_6+222>
0x00000000004011cd <+217>:   mov    %rdx,%rcx
0x00000000004011d0 <+220>:   jmp    0x4011bd <phase_6+201>

这一部分将链表按栈内节点的位置顺序重新排列

0x00000000004011d2 <+222>:   movq   $0x0,0x8(%rdx)
0x00000000004011da <+230>:   mov    $0x5,%ebp
0x00000000004011df <+235>:   mov    0x8(%rbx),%rax
0x00000000004011e3 <+239>:   mov    (%rax),%eax
0x00000000004011e5 <+241>:   cmp    %eax,(%rbx)
0x00000000004011e7 <+243>:   jge    0x4011ee <phase_6+250>
0x00000000004011e9 <+245>:   call   0x40143a <explode_bomb>
0x00000000004011ee <+250>:   mov    0x8(%rbx),%rbx
0x00000000004011f2 <+254>:   sub    $0x1,%ebp
0x00000000004011f5 <+257>:   jne    0x4011df <phase_6+235>
0x00000000004011f7 <+259>:   add    $0x50,%rsp
0x00000000004011fb <+263>:   pop    %rbx
0x00000000004011fc <+264>:   pop    %rbp
0x00000000004011fd <+265>:   pop    %r12
0x00000000004011ff <+267>:   pop    %r13
0x0000000000401201 <+269>:   pop    %r14
0x0000000000401203 <+271>:   ret

rbx指向node[num[0]]，eax指向node[num[1]]，如果rbx<eax，爆炸，即node[i]对的值应该在栈中递减
根据node的值排序：node[3]>node[4]>node[5]>node[6]>node[1]>node[2]，即对应num[0]=3,num[1]=4,num[2]=5,num[3]=6,num[4]=1,num[5]=2
但前一部分中，需要对输入的进行变换（n=7-num）才能得到num，所以最终答案是：4 3 2 1 6 5

1	`Congratulations! You've defused the bomb!`

至此bomb lab的6个phase全部完成。

One more thing…

在bomb.c的最后有一段注释

1 2	`/* Wow, they got it! But isn't something... missing? Perhaps * something they overlooked? Mua ha ha ha ha! */`

查看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       	call   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       	call   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       	call   400b10 <puts@plt>
401621:	bf 20 25 40 00       	mov    $0x402520,%edi
401626:	e8 e5 f4 ff ff       	call   400b10 <puts@plt>
40162b:	b8 00 00 00 00       	mov    $0x0,%eax
401630:	e8 0d fc ff ff       	call   401242 <secret_phase>
401635:	bf 58 25 40 00       	mov    $0x402558,%edi
40163a:	e8 d1 f4 ff ff       	call   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       	call   400b30 <__stack_chk_fail@plt>
401654:	48 83 c4 78          	add    $0x78,%rsp
401658:	c3                   	ret

发现在 phase_defused中会调用secret_phase

1 2	`(gdb) x/s 0x402619 0x402619: "%d %d %s"`

1 2	`(gdb) x/s 0x402622 0x402622: "DrEvil"`

不难猜测应该是在某个两个数字的后面加上一个字符串DrEvil

经尝试发现在第四个答案后添加指定字符串可进入隐藏关

1 2	`Curses, you've found the secret phase! But finding it and solving it are quite different...`

这里的secret_phase便是暗雷

0000000000401242 <secret_phase>:
401242:	53                   	push   %rbx
401243:	e8 56 02 00 00       	call   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       	call   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       	call   40143a <explode_bomb>
40126c:	89 de                	mov    %ebx,%esi
40126e:	bf f0 30 60 00       	mov    $0x6030f0,%edi
401273:	e8 8c ff ff ff       	call   401204 <fun7>
401278:	83 f8 02             	cmp    $0x2,%eax
40127b:	74 05                	je     401282 <secret_phase+0x40>
40127d:	e8 b8 01 00 00       	call   40143a <explode_bomb>
401282:	bf 38 24 40 00       	mov    $0x402438,%edi
401287:	e8 84 f8 ff ff       	call   400b10 <puts@plt>
40128c:	e8 33 03 00 00       	call   4015c4 <phase_defused>
401291:	5b                   	pop    %rbx
401292:	c3                   	ret

在第13 14行后，调用了fun7函数，其中有两个参数，esi和edi,esi是输入，edi是一个内存地址
第16行，返回值与2比较，相等则成功，即目标：使fun7返回2.

0000000000401204 <fun7>:
  401204:	48 83 ec 08          	sub    $0x8,%rsp
  401208:	48 85 ff             	test   %rdi,%rdi #rdi是0则跳出
  40120b:	74 2b                	je     401238 <fun7+0x34>
  40120d:	8b 17                	mov    (%rdi),%edx
  40120f:	39 f2                	cmp    %esi,%edx #rdi->val<=esi
  401211:	7e 0d                	jle    401220 <fun7+0x1c>
  401213:	48 8b 7f 08          	mov    0x8(%rdi),%rdi
  401217:	e8 e8 ff ff ff       	call   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       	call   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                   	ret

查看0x6030f0处的内容

(gdb) x/500x 0x06030f0
0x6030f0 <n1>:  0x24    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x6030f8 <n1+8>:        0x10    0x31    0x60    0x00    0x00    0x00    0x00    0x00
0x603100 <n1+16>:       0x30    0x31    0x60    0x00    0x00    0x00    0x00    0x00
0x603110 <n21>: 0x08    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603118 <n21+8>:       0x90    0x31    0x60    0x00    0x00    0x00    0x00    0x00
0x603120 <n21+16>:      0x50    0x31    0x60    0x00    0x00    0x00    0x00    0x00
0x603130 <n22>: 0x32    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603138 <n22+8>:       0x70    0x31    0x60    0x00    0x00    0x00    0x00    0x00
0x603140 <n22+16>:      0xb0    0x31    0x60    0x00    0x00    0x00    0x00    0x00
0x603150 <n32>: 0x16    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603158 <n32+8>:       0x70    0x32    0x60    0x00    0x00    0x00    0x00    0x00
0x603160 <n32+16>:      0x30    0x32    0x60    0x00    0x00    0x00    0x00    0x00
0x603170 <n33>: 0x2d    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603178 <n33+8>:       0xd0    0x31    0x60    0x00    0x00    0x00    0x00    0x00
0x603180 <n33+16>:      0x90    0x32    0x60    0x00    0x00    0x00    0x00    0x00
0x603190 <n31>: 0x06    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603198 <n31+8>:       0xf0    0x31    0x60    0x00    0x00    0x00    0x00    0x00
0x6031a0 <n31+16>:      0x50    0x32    0x60    0x00    0x00    0x00    0x00    0x00
0x6031b0 <n34>: 0x6b    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x6031b8 <n34+8>:       0x10    0x32    0x60    0x00    0x00    0x00    0x00    0x00
0x6031c0 <n34+16>:      0xb0    0x32    0x60    0x00    0x00    0x00    0x00    0x00
0x6031d0 <n45>: 0x28    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x6031d8 <n45+8>:       0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x6031e0 <n45+16>:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x6031f0 <n41>: 0x01    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x6031f8 <n41+8>:       0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603200 <n41+16>:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603210 <n47>: 0x63    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603218 <n47+8>:       0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603220 <n47+16>:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603230 <n44>: 0x23    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603238 <n44+8>:       0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603240 <n44+16>:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603250 <n42>: 0x07    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603258 <n42+8>:       0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603260 <n42+16>:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603270 <n43>: 0x14    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603278 <n43+8>:       0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603280 <n43+16>:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603290 <n46>: 0x2f    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x603298 <n46+8>:       0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x6032a0 <n46+16>:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x6032b0 <n48>: 0xe9    0x03    0x00    0x00    0x00    0x00    0x00    0x00
0x6032b8 <n48+8>:       0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x6032c0 <n48+16>:      0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00

不难发现这片内存空间中存着的数据是树结构的定义，其中

第一行表示其数值
第二行表示左子树的地址
第三行表示右子树的地址

那么其树结构可以用下图表示注：图中为16进制

而fun7函数的c语言版如下所示

int fun7(Tree* rdi, int esi) {
    if (!rdi)   //第3，4行
        return -1;  //19
    if (rdi->val == esi)    //13
        return 0;       //20
    else if (rdi->val < esi)        //7
        return 2 * fun7(rdi -> right, esi) + 1; //15,16
    else
        return 2 * fun7(rdi -> left, esi);  //8,9
}

反推，

想要得到2，那么一定是从左子树返回1
想要得到1，那么一定从右子树返回值返回0
返回值为0，节点值就是输入的值

2=2*fun7(8,16)

fun7(8,16)=fun7(16,16)+1=1

那么，隐藏关的答案便呼之欲出，0x16=22

1	`Wow! You've defused the secret stage!`

总结

耗时3天，总计20h，做完只觉茅塞顿开，csapp这本书相见恨晚。
各类数据结构在机器级的实现方式令我瞋目结舌。
phase_5的逻辑设计惊艳到了我，其通过输入字符的ascii码来定位字符，结构巧妙令人赞叹不已。
phase_5和secret_phase的用时最长，其复杂的循环或递归结构逻辑复杂，需要先将其转化为c语言。

CSAPP

#binary #bomb

csapp bomb_lab

http://htwzxwj.github.io/2023/09/06/csapp-bomb-lab/

作者

End0rph1n

发布于

2023年9月6日

许可协议

csapp attack_lab 上一篇