owned this note
owned this note
Published
Linked with GitHub
# CS:APP Bomb Lab
## 背景知識
### 環境安裝
從[這裡](https://hansimov.gitbook.io/csapp/labs/labs-overview)安裝好後，進行解壓縮:
```
$ tar xvf bomb.tar
```
### 文件結構
```
- bomb.c
- bomb
- README.md
```
* `bomb.c`: 主程式的 C 文件
* `bomb`: 可執行檔，要使用 `gdb` 對其調適以及反彙編
* `READMED.md`: 說明題目文件
### 實驗原理
原始的 `bomb.c` 的主函式如下:
```cpp
int main(int argc, char *argv[])
{
char *input;
...
/* Do all sorts of secret stuff that makes the bomb harder to defuse. */
initialize_bomb();
printf("Welcome to my fiendish little bomb. You have 6 phases with\n");
printf("which to blow yourself up. Have a nice day!\n");
/* Hmm... Six phases must be more secure than one phase! */
input = read_line(); /* Get input */
phase_1(input); /* Run the phase */
phase_defused(); /* Drat! They figured it out!
* Let me know how they did it. */
printf("Phase 1 defused. How about the next one?\n");
/* The second phase is harder. No one will ever figure out
* how to defuse this... */
input = read_line();
phase_2(input);
phase_defused();
printf("That's number 2. Keep going!\n");
```
可以看到在每個題裡面都會先讀取一行字串，將這個字串傳入 `phase_n` 函式裡面經過一些比較，若字串輸入正確，就代表拆彈成功，若是輸入錯誤則炸彈就會爆炸。
而 `phase_n` 函式裡面的程式我們是看不到的，因此只能透過反彙編工具以及 `gdb` 來取得他的組合語言，進而分析要拆彈的字串是什麼。一共有 `phase_1` 到 `phase_6` ，6 個題目。
### 實驗準備
先透過以下命令來獲取整個 `bomb` 的反彙編:
```
$ objdump -d bomb > bomd.txt
```
### GDB 命令
這邊列舉一些 `gdb` 的命令方便查閱:
* 啟動 gdb
```
$ gdb bomb
```
* 設置斷點，(run 之前就要設置好，不然會被炸彈炸爛:cry:)
```
$ break phase_1
```
* 開始執行
```
$ run
```
* 顯示目前的彙編程式
```
$ disas
```
* 看目前 breakpoint/display/register 的狀態
```
$ info break/display/register...
```
* 印出指定暫存器
```
$ print %rsp
```
* 每次執行一步
```
$ stepi
```
* 獲取 gdb 幫助
```
$ help
```
* 離開 gdb
```
$ quit
```
### x86_64 組語
* 語法操作
| 操作型態 | 語法 | 例子 |
| -------- | -------- | -------- |
| 暫存器| 以 `$` 開頭 | `%rsp`, `%rax` |
| 常數| 以 `$` 開頭 | `$416`, `$0x20` |
| 記憶體地址| 以 `()` 刮起 | `($rdi)`, `0x20(%r8)` |
* 常見操作
| 語法 | 作用 |
| -------- | -------- |
| `OP A B` | B op A |
| `mov A B` | B = A |
| `cmp A B` | B - A |
| `test A B` | B & A |
| `call adress` | 函式調用 |
| `ret` | 函式返回 |
| `lea 4(%rdx, %rbx, 2), %rdx` | rdx = 4 + rdx + 2*rbx |
## `phase_1`
輸入 `gdb bomb` 進入 gdb，接著在第一題設置斷點 `break phase_1`，透過 `disas` 來獲得函式的組合語言，如下:
```cpp=
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
```
* 堆疊指針減 8
* 將常數 `0x402400` 傳入 `%esi`
* 呼叫 `strings_not_equal` 函式
* 檢查回傳值是否為 1
* 若是 1 則跳去堆疊指針加 8，並回傳
* 若是 0 則炸彈爆炸
所以我們可以知道重點是 `strings_not_equal` 函式的比較，所以將他的組合語言抓出來看:
```cpp=
0000000000401338 <strings_not_equal>:
401338: 41 54 push %r12
40133a: 55 push %rbp
40133b: 53 push %rbx
40133c: 48 89 fb mov %rdi,%rbx
40133f: 48 89 f5 mov %rsi,%rbp
401342: e8 d4 ff ff ff call 40131b <string_length>
401347: 41 89 c4 mov %eax,%r12d
40134a: 48 89 ef mov %rbp,%rdi
40134d: e8 c9 ff ff ff call 40131b <string_length>
401352: ba 01 00 00 00 mov $0x1,%edx
401357: 41 39 c4 cmp %eax,%r12d
40135a: 75 3f jne 40139b <strings_not_equal+0x63>
40135c: 0f b6 03 movzbl (%rbx),%eax
40135f: 84 c0 test %al,%al
401361: 74 25 je 401388 <strings_not_equal+0x50>
401363: 3a 45 00 cmp 0x0(%rbp),%al
401366: 74 0a je 401372 <strings_not_equal+0x3a>
401368: eb 25 jmp 40138f <strings_not_equal+0x57>
40136a: 3a 45 00 cmp 0x0(%rbp),%al
40136d: 0f 1f 00 nopl (%rax)
401370: 75 24 jne 401396 <strings_not_equal+0x5e>
401372: 48 83 c3 01 add $0x1,%rbx
401376: 48 83 c5 01 add $0x1,%rbp
40137a: 0f b6 03 movzbl (%rbx),%eax
40137d: 84 c0 test %al,%al
40137f: 75 e9 jne 40136a <strings_not_equal+0x32>
401381: ba 00 00 00 00 mov $0x0,%edx
401386: eb 13 jmp 40139b <strings_not_equal+0x63>
401388: ba 00 00 00 00 mov $0x0,%edx
40138d: eb 0c jmp 40139b <strings_not_equal+0x63>
40138f: ba 01 00 00 00 mov $0x1,%edx
401394: eb 05 jmp 40139b <strings_not_equal+0x63>
401396: ba 01 00 00 00 mov $0x1,%edx
40139b: 89 d0 mov %edx,%eax
40139d: 5b pop %rbx
40139e: 5d pop %rbp
40139f: 41 5c pop %r12
4013a1: c3 ret
```
已經知道前面將 常數 `0x402400` 傳入 `%esi`，所以我們要關心的地方就是有關 rsi 暫存器的操作。
* 第 6 行，`%rbp = %rsi`
* 第 17 行，比較記憶體位置 `(%rbp)` 和 `%al` 來判斷是不是一樣的字串
所以最終知道記憶體位置 `0x402400` 所儲存的字串就是要比較的字串，可以透過以下兩種方式來獲取其資訊:
```cpp
(gdb) print (char *) 0x402400
$1 = 0x402400 "Border relations with Canada have never been better."
(gdb) x/s 0x402400
0x402400: "Border relations with Canada have never been better."
```
最後重新取啟動 gdb，設置新斷點 `break phase_2`，並輸入上面字串後，phase_1 就通過啦。
:::info
獲得一個題目的答案後，必須要設置下個題目的斷點，否則炸彈會爆炸。
:::
嘗試將 phase_1 寫成原始的 C 語言程式：
```cpp
void phase_1(char *output)
{
if (!strings_not_equal(output, "Border relations with Canada \\
have never been better."))
explode_bomb();
return;
}
```
## `phase_2`
和上面一樣的操作，這邊不重寫一遍了。
```cpp=
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>
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
```
試著跟著程式的流程走一遍，並將其寫成 C 語言風格:
```cpp
phase_2()
{
0x400f02:
rsi = rsp
read_six_numbers()
if (rsp != 1)
explode_bomb()
0x400f30:
rbx = *(4 + rsp)
rbp = *(24 + rsp)
0x400f17:
do {
eax = *(rbx - 4)
eax *= 2
if (rbx != eax)
explode_bomb()
rbx += 4
} while (rbx == rbp)
}
```
可是我們不知道 `read_six_numbers` 函式到底對暫存器做了什麼，將其組合語言抓出來看:
```cpp=
000000000040145c <read_six_numbers>:
40145c: 48 83 ec 18 sub $0x18,%rsp
401460: 48 89 f2 mov %rsi,%rdx
401463: 48 8d 4e 04 lea 0x4(%rsi),%rcx
401467: 48 8d 46 14 lea 0x14(%rsi),%rax
40146b: 48 89 44 24 08 mov %rax,0x8(%rsp)
401470: 48 8d 46 10 lea 0x10(%rsi),%rax
401474: 48 89 04 24 mov %rax,(%rsp)
401478: 4c 8d 4e 0c lea 0xc(%rsi),%r9
40147c: 4c 8d 46 08 lea 0x8(%rsi),%r8
401480: be c3 25 40 00 mov $0x4025c3,%esi
401485: b8 00 00 00 00 mov $0x0,%eax
40148a: e8 61 f7 ff ff call 400bf0 <__isoc99_sscanf@plt>
40148f: 83 f8 05 cmp $0x5,%eax
401492: 7f 05 jg 401499 <read_six_numbers+0x3d>
401494: e8 a1 ff ff ff call 40143a <explode_bomb>
401499: 48 83 c4 18 add $0x18,%rsp
40149d: c3 ret
```
它在第 13 行呼叫 `__isoc99_sscanf@plt` ，從名子可以看出他是掃描的函式，有了上一題的經驗，我們知道第 11 行的常數記憶體地址是關鍵，所以使用以下:
```cpp
(gdb) print (char *)0x4025c3
$1 = 0x4025c3 "%d %d %d %d %d %d"
```
所以推斷說它將我們的輸入字串放入 `%rsi`，然後利用 `sscanf` 將上面格式的數字存放到堆疊中，一個整數為 4 bytes ，所以從 sp 0 ~ 24 ，十六進制則是 sp 0 ~ 0x18。而這也代表我們要輸入的字串應該是上面字串格式，也就是要輸入 6 個數字，中間要有空白。
---
* `read_six_numbers` 函式結束後，馬上就是判斷堆疊指標指向的第一個數字是否為 1 ，若不是則馬上爆炸。因此得知第一個數字為 1。
* 接著設置了 `%rbx` 堆疊指標加 4，也就是輸入的第二個數字，`%rbp`堆疊指標加 24，也就是輸入的最後一個數字。
* 進入 `do_while` 迴圈，會先將 `rbx` 減 4 的記憶體資料取出，第一次執行就是將第一個數字取出，在將其乘以 2，接著就是比較這兩個數有沒有相等。若不相等則爆炸，相等則將 `rbx` 加四，直到和 `rbp` 相等。
這邊的操作其實就是判斷數組是不是等比級數，而公比為 2。透過 `rbx` 作為記憶體位置的走訪變數，每次移動一個數字就是加 4，`eax` 為前一個數組的數值，比較前後是否是兩倍差，結束條件就是當 `rbx` 走訪到最後一個數組。
那結果其實就很清楚了，條件如下。
* 第一個數字必須是 1
* 數組要是等比級數，公比為 2
* 有 6 個數字
要輸入的字串必為 `"1 2 4 8 16 32"`
一樣我們嘗試將其翻譯成 C 語言型態:
```cpp
void phase_2(char *output)
{
int arr[6];
read_six_numbers(output, arr);
if (arr[0] != 1)
explode_bomb();
for (int i = 1; i < 6; i++) {
int tmp = arr[i - 1] * 2;
if (tmp != arr[i])
explode_bomb();
}
return;
}
```
## `phase_3`
```cpp=
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
```
### 掃描數字
```cpp=
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>
```
印出組語來看發現和上題架構類似，馬上檢查第 3 行的 `0x4025cf` 記憶體位置，第 5 行就呼叫了 `sscanf` 函式說明其掃描輸入的兩個字串。再根據第 1, 2 得知，sscanf 會將掃描的兩個數字分別存放在堆疊指標 `rsp + 8` 和 `rsp + 12` 。
```cpp
(gdb) print (char *)0x4025cf
$1 = 0x4025cf "%d %d"
```
### 第一個數字範圍
```cpp=
0x0000000000400f6a <+39>: cmpl $0x7,0x8(%rsp)
0x0000000000400f6f <+44>: ja 0x400fad <phase_3+106>
```
第 11 行將輸入的第一個數字取出比較，若大於 7 ，則炸彈爆炸。
### switch 比較
```cpp=
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
```
第一行將第一個數字放入 `%rax`，第二行使用間接跳轉，根據 `%rax` 的值選擇跳轉到哪裡。這實際上就是 switch 條件分支操作，編譯器會生成一個跳轉表(jump table)，而我們可以使用 gdb 來取得這個跳轉表。
```cpp
(gdb) x/64xb 0x402470
0x402470: 0x7c 0x0f 0x40 0x00 0x00 0x00 0x00 0x00
0x402478: 0xb9 0x0f 0x40 0x00 0x00 0x00 0x00 0x00
0x402480: 0x83 0x0f 0x40 0x00 0x00 0x00 0x00 0x00
0x402488: 0x8a 0x0f 0x40 0x00 0x00 0x00 0x00 0x00
0x402490: 0x91 0x0f 0x40 0x00 0x00 0x00 0x00 0x00
0x402498: 0x98 0x0f 0x40 0x00 0x00 0x00 0x00 0x00
0x4024a0: 0x9f 0x0f 0x40 0x00 0x00 0x00 0x00 0x00
0x4024a8: 0xa6 0x0f 0x40 0x00 0x00 0x00 0x00 0x00
```
從第 2 行知道基底位置是 `0x402470` ，每 8 個 byte 是一個地址長度，又知道第一個數字的範圍為 0 ~ 7 一共 8 個數。所以我們一共要看 $8\times 8=64$ 個 bytes。
| 數字 1 | 跳到的地址 | 對應的數字 2(dec)
| -------- | -------- | -------- |
| 0 | `0x400f7c` | 207 |
| 1 | `0x400fb9` | 311 |
| 2 | `0x400f83` | 707 |
| 3 | `0x400f8a` | 256 |
| 4 | `0x400f91` | 389 |
| 5 | `0x400f98` | 206 |
| 6 | `0x400f9f` | 682 |
| 7 | `0x400fa6` | 327 |
### 最終比較
```cpp=
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
```
根據這些地址可以看到，都是將特定數字放入 `$rax`，第 1 行和第二個數字比較是否相等，不相等則會爆炸。
因此本題要輸入的值就是上表中對應到的數字 1 和數字 2的字串。
```
0 207
1 311
2 707
3 256
4 389
5 206
6 682
7 327
```
### C 語言反彙編
```cpp
void phase_3(char *output)
{
int x, y;
if(sscanf(output, "%d %d", &x, &y) <= 1)
explode_bomb();
if (x > 7)
explode_bomb();
int n;
switch (x) {
case 0:
n = 207;
case 1:
n = 311;
case 2:
n = 707;
case 3:
n = 256;
case 4:
n = 389;
case 5:
n = 206;
case 6:
n = 682;
case 7:
n = 327;
}
if (y != n)
explode_bomb();
return;
}
```
## `phase_4`
```cpp=
Dump of assembler code for function phase_4:
=> 0x000000000040100c <+0>: sub $0x18,%rsp
0x0000000000401010 <+4>: lea 0xc(%rsp),%rcx
0x0000000000401015 <+9>: lea 0x8(%rsp),%rdx
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>
0x000000000040102e <+34>: cmpl $0xe,0x8(%rsp)
0x0000000000401033 <+39>: jbe 0x40103a <phase_4+46>
0x0000000000401035 <+41>: call 0x40143a <explode_bomb>
0x000000000040103a <+46>: mov $0xe,%edx
0x000000000040103f <+51>: mov $0x0,%esi
0x0000000000401044 <+56>: mov 0x8(%rsp),%edi
0x0000000000401048 <+60>: call 0x400fce <func4>
0x000000000040104d <+65>: test %eax,%eax
0x000000000040104f <+67>: jne 0x401058 <phase_4+76>
0x0000000000401051 <+69>: cmpl $0x0,0xc(%rsp)
0x0000000000401056 <+74>: je 0x40105d <phase_4+81>
0x0000000000401058 <+76>: call 0x40143a <explode_bomb>
0x000000000040105d <+81>: add $0x18,%rsp
0x0000000000401061 <+85>: ret
```
前半部的架構和上一題一樣，知道是要掃描兩個數字。
```cpp
(gdb) print (char *)0x4025cf
$1 = 0x4025cf "%d %d"
```
### 第一個數字範圍
```cpp
0x000000000040102e <+34>: cmpl $0xe,0x8(%rsp)
0x0000000000401033 <+39>: jbe 0x40103a <phase_4+46>
```
若是第一個數字大於 14 ，而這邊使用的是 `jbe` 也就是無號數操作，因此第一個數的範圍應該是 $0\leq n_{1}\leq 14$。
### `func4`
進入 `func4` 函式前設置 3 個參數，將這三個暫存器先取個變數:
| | `%edx`(j) | `%esi`(i) | `%edi`(n) |
| -------- | -------- | -------- |-------- |
| 初始呼叫值 | 14 | 0 | 第一個數字|
```cpp=
Dump of assembler code for function func4:
=> 0x0000000000400fce <+0>: sub $0x8,%rsp
0x0000000000400fd2 <+4>: mov %edx,%eax
0x0000000000400fd4 <+6>: sub %esi,%eax
0x0000000000400fd6 <+8>: mov %eax,%ecx
0x0000000000400fd8 <+10>: shr $0x1f,%ecx
0x0000000000400fdb <+13>: add %ecx,%eax // ?
0x0000000000400fdd <+15>: sar %eax
0x0000000000400fdf <+17>: lea (%rax,%rsi,1),%ecx
0x0000000000400fe2 <+20>: cmp %edi,%ecx
0x0000000000400fe4 <+22>: jle 0x400ff2 <func4+36>
0x0000000000400fe6 <+24>: lea -0x1(%rcx),%edx
0x0000000000400fe9 <+27>: call 0x400fce <func4>
0x0000000000400fee <+32>: add %eax,%eax
0x0000000000400ff0 <+34>: jmp 0x401007 <func4+57>
0x0000000000400ff2 <+36>: mov $0x0,%eax
0x0000000000400ff7 <+41>: cmp %edi,%ecx
0x0000000000400ff9 <+43>: jge 0x401007 <func4+57>
0x0000000000400ffb <+45>: lea 0x1(%rcx),%esi
0x0000000000400ffe <+48>: call 0x400fce <func4>
0x0000000000401003 <+53>: lea 0x1(%rax,%rax,1),%eax
0x0000000000401007 <+57>: add $0x8,%rsp
0x000000000040100b <+61>: ret
```
* line 3: `%eax = j`
* line 4: `j = j - i`
* line 5: `%ecx = j - i`
* line 6: 將 `(j - i)` 右移 31 位，取出符號數
* line 8: 計算 `%ecx` = $\frac{j-i}{2}$
* line 9: 計算 `%ecx` = $\frac{j-i}{2}+i=\frac{j+i}{2}$
* line 10, 11: 比較計算出來的值有沒有比 n 小
接下來的分支判斷用以下 C 語言呈現:
```cpp
/* args: i: %esi, j: %edi, n: %edi */
int func4(int i, int j, int n)
{
int avg = (i + j) / 2; // 7
if (avg <= n) {
if (avg >= n) {
return 0;
}
else {
return (2 * func4(avg + 1, j, n)) + 1;
}
}
else {
return 2 * func4(i, avg - 1, n);
}
}
```
這是基於二分搜尋所設計的，判斷 i, j 平均值和 n 的大小，來做遞迴操作。但這邊不會引爆炸彈。
回到 `phase_4` 函式，第 17,18 行用來測試回傳數是否為 0
* `test %eax,%eax`: 相同暫存器做 AND，若為 0，ZF 置 1，若不為 0 ，ZF 置 0
* `jne` : 不相等跳轉，實際上就是取 `~ZF`
我們知道 `i = 0, j = 14, 0 <= n <= 14` ，所以有 15 種組合，只要測試這 15 個數怎樣會回傳 0 就可以了。
* 測試程式
```cpp
#include <stdio.h>
int func4(int i, int j, int n)
{
int avg = (i + j) / 2; // 7
if (avg <= n) {
if (avg >= n) {
return 0;
}
else {
return (2 * func4(avg + 1, j, n)) + 1;
}
}
else {
return 2 * func4(i, avg - 1, n);
}
}
int main(void)
{
int i = 0, j = 14;
for (int n = 0; n <= 14; n++) {
printf("n = %d, func4 = %d\n", n, func4(i, j, n));
}
return 0;
}
```
* 結果
```
n = 0, func4 = 0
n = 1, func4 = 0
n = 2, func4 = 4
n = 3, func4 = 0
n = 4, func4 = 2
n = 5, func4 = 2
n = 6, func4 = 6
n = 7, func4 = 0
n = 8, func4 = 1
n = 9, func4 = 1
n = 10, func4 = 5
n = 11, func4 = 1
n = 12, func4 = 3
n = 13, func4 = 3
n = 14, func4 = 7
```
所以第一個數字必須是 0, 1, 3, 7 。
```cpp=
0x0000000000401051 <+69>: cmpl $0x0,0xc(%rsp)
0x0000000000401056 <+74>: je 0x40105d <phase_4+81>
0x0000000000401058 <+76>: call 0x40143a <explode_bomb>
```
而第二個數字則是由上面所示，必須是 0 ，因此本題的答案為
```
0 0
1 0
3 0
7 0
```
## `phase_5`
```cpp=
Dump of assembler code for function phase_5:
=> 0x0000000000401062 <+0>: push %rbx
0x0000000000401063 <+1>: sub $0x20,%rsp
0x0000000000401067 <+5>: mov %rdi,%rbx
0x000000000040106a <+8>: mov %fs:0x28,%rax
0x0000000000401073 <+17>: mov %rax,0x18(%rsp)
0x0000000000401078 <+22>: xor %eax,%eax
0x000000000040107a <+24>: call 0x40131b <string_length>
0x000000000040107f <+29>: cmp $0x6,%eax
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
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)
0x00000000004010a4 <+66>: add $0x1,%rax
0x00000000004010a8 <+70>: cmp $0x6,%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
```
### 輸入字串長度
呼叫 `string_length` 函式來取得輸入字串的長度。若是不等於 6 則炸彈爆炸。
```cpp
0x000000000040107a <+24>: call 0x40131b <string_length>
0x000000000040107f <+29>: cmp $0x6,%eax
0x0000000000401082 <+32>: je 0x4010d2 <phase_5+112>
0x0000000000401084 <+34>: call 0x40143a <explode_bomb>
```
### 迴圈
可以看到第 10, 11 行是自加 1 在判斷是否等於 6 跳回原本位置，代表這是一個從 0 到 6 執行 6 次的迴圈。
而回圈裡做的事就是本題的精隨。`rax` 為迴圈計數器，`rbx` 存放輸入字串的記憶體位置。
* line 4: 在輸入字串的記憶體位置為基底加上迴圈計數器大小，當計數器變大時，就會更改取得的數字，以字串 `abcdef` 為例，存放在基底為 `0x6038c0` 的位置。
* `0x6038c0 + 0`: 抓出 `0x64636261`
* `0x6038c0 + 1`: 抓出 `0x65646362`
* `0x6038c0 + 2`: 抓出 `0x66656463`
* 以此類推
```cpp
(gdb) x/6b 0x6038c0
0x6038c0 <input_strings+320>: 0x61 0x62 0x63 0x64 0x65 0x66
```
* line 5, 6: 透過堆疊將得到的字串放到 `rdx` 中。
* line 7: 和 `0xf` 做 AND，就是取出最低的 byte 。
* line 8: 將取出的最低 byte 加上 `0x4024b0`的記憶體位置放入 `rdx`。先來看看這個位置有什麼
```cpp
(gdb) print (char *) 0x4024b0
$8 = 0x4024b0 <array> "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"
```
* line 9: 將從其放入 `rsp + 0x10 + rax` 的記憶體位置
會發現這一系列操作非常的繞，但仔細想一下就會發現其實這就是陣列的操作而已，我們可以寫成 C 語言風格:
```cpp
char *sys_str[16] = "maduiersnfotvbyl";
for (int i = 0; i == 6; i++) {
my_str[i] = sys_str[output[i] & 0xF];
}
```
因為組合語言不支持記憶體對記憶體的訪存，因此都需要先抓出來給暫存器再放進去記憶體裡。
而這一段的意思就是每一次迴圈都會抓出輸入字串的 ASCII 碼的低 4 位元，若輸入是 `output = "abcdef"`，則每次取出的索引值就是
| 字元 | ASCII(hex) | index | `sys_str[index]`|
| -------- | -------- | -------- | -------- |
| `a` | `0x61` | `0x1` | `a`
| `b` | `0x62` | `0x2` | `d`
| `c` | `0x63` | `0x3` | `u`
| `d` | `0x64` | `0x4` | `i`
| `e` | `0x65` | `0x5` | `e`
| `f` | `0x66` | `0x6` | `r`
也就是說最後 `my_str = "aduier"`。
```cpp=
0x00000000004010d2 <+112>: mov $0x0,%eax
0x00000000004010d7 <+117>: jmp 0x40108b <phase_5+41>
...
0x000000000040108b <+41>: movzbl (%rbx,%rax,1),%ecx
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)
0x00000000004010a4 <+66>: add $0x1,%rax
0x00000000004010a8 <+70>: cmp $0x6,%rax
0x00000000004010ac <+74>: jne 0x40108b <phase_5+41>
```
### 字串檢查
```cpp=
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>
```
觀察後面發現呼叫 `strings_not_equal` ，因此一如既往的取檢查第 1 行 `0x40245e` 記憶體位置存放的字串。
```cpp
(gdb) print (char *) 0x40245e
$9 = 0x40245e "flyers"
```
因此我們知道剛剛的字串就是要和 "flyers" 是一樣的，所以可以將剛剛那個表反過來推：
<------------------------------------------------------------------------------------------
| 字元 | ASCII(hex) | index | `sys_str[index]`|
| -------- | -------- | -------- | -------- |
| `i` | `0x69` | `0x9` | `f`
| `o` | `0x6F` | `0xF` | `l`
| `n` | `0x6E` | `0xE` | `y`
| `e` | `0x65` | `0x5` | `e`
| `f` | `0x66` | `0x6` | `r`
| `g` | `0x67` | `0x7` | `s`
當然因為 ASCII code 的特性，答案也可以是大寫的:
```
ionefg
IONEFG
```
## `phase_6`
這題是最難的一題，我們慢慢看。
```cpp=
Dump of assembler code for function 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>
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>
0x0000000000401123 <+47>: call 0x40143a <explode_bomb>
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)
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>
0x0000000000401153 <+95>: lea 0x18(%rsp),%rsi
0x0000000000401158 <+100>: mov %r14,%rax
0x000000000040115b <+103>: mov $0x7,%ecx
0x0000000000401160 <+108>: mov %ecx,%edx
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>
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)
0x000000000040118d <+153>: add $0x4,%rsi
0x0000000000401191 <+157>: cmp $0x18,%rsi
0x0000000000401195 <+161>: je 0x4011ab <phase_6+183>
0x0000000000401197 <+163>: mov (%rsp,%rsi,1),%ecx
0x000000000040119a <+166>: cmp $0x1,%ecx
0x000000000040119d <+169>: jle 0x401183 <phase_6+143>
0x000000000040119f <+171>: mov $0x1,%eax
0x00000000004011a4 <+176>: mov $0x6032d0,%edx
0x00000000004011a9 <+181>: jmp 0x401176 <phase_6+130>
0x00000000004011ab <+183>: mov 0x20(%rsp),%rbx
0x00000000004011b0 <+188>: lea 0x28(%rsp),%rax
0x00000000004011b5 <+193>: lea 0x50(%rsp),%rsi
0x00000000004011ba <+198>: mov %rbx,%rcx
0x00000000004011bd <+201>: mov (%rax),%rdx
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
```
可以看到整個函式非常地長，因此要拆成幾個部份來看。在第 10 行讀取 6 個數字已經在前面出現過了，就不多講了。
### Part 1
```cpp
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>
0x0000000000401123 <+47>: call 0x40143a <explode_bomb>
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)
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>
```
讀取六個數字出來後(`0x40110b <+23>`)，可以看到是對讀取的數字做某些操作，然後迴圈回去。因此我們嘗試寫出簡單的程式邏輯:
```cpp
+23:
r14 = rsp
r12d = 0
+32:
rsi = r13 (rsp)
rax = M[r13]
rax -= 1
if (rax > 5)
bomb
r12d += 1
if (r12d == 6)
jump to (+95)
rbx = r12d
+65:
rax = rbx
rax = M[rsp + 4 * rax]
if (rax == M[rsp])
bomb
rbx += 1
if (rbx <= 5)
jump to 65
else
r13 += 4
jump to 32
```
因此可以看出這出迴圈的樣子，所以改寫成以下樣子。其中 `i` 就是 `r12d`，`j` 是 `rbx`。
```cpp
for (int i = 0; i < 6; i++) {
int num = arr[i];
if ((num - 1) > 5)
explode_bomb();
for (int j = i + 1; j <= 5; j++) {
if (arr[j] == num)
explode_bomb();
}
}
```
觀察上面程式會發現，每個輸入的數字 `N - 1` 不能大於 5，且輸入的 6 個數字不能有重複的。
:::info
編譯器通常會盡可能的重複利用暫存器，和程式語言的變數想法常常會有出入，因此需要記得暫存器的前因後果會比較好的理解組合語言。
:::
### Part 2
```cpp
0x0000000000401153 <+95>: lea 0x18(%rsp),%rsi
0x0000000000401158 <+100>: mov %r14,%rax
0x000000000040115b <+103>: mov $0x7,%ecx
0x0000000000401160 <+108>: mov %ecx,%edx
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>
0x000000000040116f <+123>: mov $0x0,%esi
0x0000000000401174 <+128>: jmp 0x401197 <phase_6+163>
```
我一樣將其寫成以下型態，可以看到它會把輸入的 6 個數字全部變成 `7 - N` 。
```cpp
int *last_addr = (arr + 6);
int *curr_addr = (arr);
while (curr_addr != last_addr) {
*curr_addr = 7 - *curr_addr;
curr_addr += 4;
}
```
### Part 3
```cpp
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)
0x000000000040118d <+153>: add $0x4,%rsi
0x0000000000401191 <+157>: cmp $0x18,%rsi
0x0000000000401195 <+161>: je 0x4011ab <phase_6+183>
0x0000000000401197 <+163>: mov (%rsp,%rsi,1),%ecx
0x000000000040119a <+166>: cmp $0x1,%ecx
0x000000000040119d <+169>: jle 0x401183 <phase_6+143>
0x000000000040119f <+171>: mov $0x1,%eax
0x00000000004011a4 <+176>: mov $0x6032d0,%edx
0x00000000004011a9 <+181>: jmp 0x401176 <phase_6+130>
```
我們還是一樣把它轉成好看的樣子:
```cpp
for (esi = 0; rsi != 0x18; rsi += 4) {
ecx = *(rsp + rsi);
if (ecx <= 1) { // branch <+143>
edx = 0x6032d0;
}
else { // branch <+171>
edx = 0x6032d0;
for (eax = 1; eax != ecx; eax++) {
rdx = *(rdx + 8);
}
}
*(rsp + rsi * 2 + 0x20) = rdx; // 第一次 rcx=7-1=6 rdx指向node6 rsp+0x20 = node6
}
```
* `rsi` 作為計數器，迴圈執行 6 次
* `ecx` 為第 n 個數字
* 判斷第 n 個數字是否小於等於 1，已知輸入數字範圍為 $0\leq n\leq 6$，而 Part 2 又將數字變成 `7 - n` ，因此只有當輸入是 6 時會進入第一個分支，其他則進入第二個分支。
* 若小於等於 1，將記憶體位置 `0x6032d0` 給 `edx`
* 若大於 1，也會將記憶體位置 `0x6032d0` 給 `edx`。但會多跑一個迴圈，我們知道這個分支只有輸入為 $1\leq n\leq 5$ 的情況才會進入，換算成 `ecx` 就是 $6\leq ecx\leq 2$ ，而這也作為這個迴圈的計數次數。迴圈裡面執行的是以這個地址基底每次加 8 取出值，但根本看不出個所以來，因此需要將這個地址相關的值抓出來看。
* 使用 `print *(int *)0x6032d0`:
| 記憶體地址 | Value | Type |
| -------- | -------- | -------- |
| `0x6032d0` | 332 | Value |
| `0x6032d8` | `0x6032e0` | address |
| `0x6032e0` | 168 | Value |
| `0x6032e8` | `0x6032f0` | address |
| `0x6032f0` | 924 | Value |
| `0x6032f8` | `0x603300` | address |
| `0x603300` | 691 | Value |
| `0x603308` | `0x603310` | address |
| `0x603310` | 477 | Value |
| `0x603318` | `0x603320` | address |
| `0x603320` | 443 | Value |
仔細觀察就發現這就是鍊結串列的操作，`0x6032d8` 存放著 `0x6032e0` 地址，也就是 `168` 的地址，嘗試寫成以下程式碼:
```cpp
typedef struct S linked_list;
struct S {
int N;
linked_list *next;
};
...
linked_list *my_list;
for (int eax = 1; eax != ecx; eax++) {
my_list = my_list->next;
}
```
所以現在可以來窮舉所有的可能了。因為 `eax` 初始化為 1，因此每次迴圈只會跑 `ecx - 1` 次。
| 輸入數字 | `ecx` | 得出的 `rdx` |
| -------- | -------- | -------- |
| 1 | 6 | 443 |
| 2 | 5 | 477 |
| 3 | 4 | 691 |
| 4 | 3 | 924 |
| 5 | 2 | 168 |
| 6 | 1 | 332 |
最後把值放入堆疊裡面，繼續下一個輸入數字。注意到它儲存在堆疊的 `rsp + 32 + 2 * rsi` ，而 `rsi` 為 4 的倍數，所以存放的是以 8 為倍數，原因當然是因為這個是一個結構體。
### Part 4
```cpp
0x00000000004011ab <+183>: mov 0x20(%rsp),%rbx
...
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>
```
一樣變成好看的樣子:
```cpp
for (ebp = 0x5; ebp != 0x1; ebp--)
{
rax = *(rbx + 0x8);
eax = *rax;
if (*rbx < eax)
explode_bomb();
rbx = *(rbx + 0x8);
}
```
* `ebp` 作為迴圈計數器，一共執行 4 次
* `rbx` 每次取出目前 index 的值 ，對應到先輸入的值
* `eax` 每次取出下一個 index 的值
* 若是目前的值小於下一個的值，則炸彈爆炸，反之則將 `rbx` 指向下一個值
因此可以理解成我們要的是一個從大到小的數列。我們再根據上面表格:
| 輸入數字 | `ecx` | 得出的 `rdx` |
| -------- | -------- | -------- |
| 1 | 6 | 443 |
| 2 | 5 | 477 |
| 3 | 4 | 691 |
| 4 | 3 | 924 |
| 5 | 2 | 168 |
| 6 | 1 | 332 |
可以得到，若是想讓最後一列是以大到小的方式排列，輸入值要是 `4 3 2 1 6 5`。這也就是本題最後的答案了。
## 完整答案
```
answer1:
Border relations with Canada have never been better.
answer2:
1 2 4 8 16 32
answer3:
0 207
1 311
2 707
3 256
4 389
5 206
6 682
7 327
answer4:
0 0
1 0
3 0
7 0
answer5:
ionefg
IONEFG
answer6:
4 3 2 1 6 5
```
全部輸入成功後，就會得到成功訊息。
```
Welcome to my fiendish little bomb. You have 6 phases with
which to blow yourself up. Have a nice day!
Border relations with Canada have never been better.
Phase 1 defused. How about the next one?
1 2 4 8 16 32
That's number 2. Keep going!
0 207
Halfway there!
0 0
So you got that one. Try this one.
ionefg
Good work! On to the next...
4 3 2 1 6 5
Congratulations! You've defused the bomb!
```
Google Drive
Gist
Clipboard
Sign in with Wallet
