[CSAPP]炸彈實驗室

一起來拆炸彈！

離上個 Data Lab 已經過去了兩個學期，終於想起來也有時間做 CSAPP 的實驗了。這次的實驗叫 Bomb Lab，故事背景是 Dr.Evil 設計了一款炸彈，只有正確輸入六條字符串才能拆除，我們需要通過逆向工程，反匯編炸彈的可執行文件來破解出能拆除炸彈的六條字符串。

實驗概覽#

實驗資料可以在 CMU 網站上獲取：https://csapp.cs.cmu.edu/3e/labs.html

壓縮包中總共有三個文件

.
├── README    
├── bomb      // 炸彈可執行文件
└── bomb.c    // 炸彈部分源代碼

我們先查看bomb.c文件

hkybb

從中可以看出炸彈的大致工作過程：

讀取一行字符串
使用phase_i函數判斷輸入是否合法

那麼只要研究每個phase函數的驗證過程就可以反推出字符串內容了

使用objdump -d bomb > bomb.s來獲得炸彈的反匯編文件

4hxfc

使用tmux左側來進行 GDB 調試，右側查看匯編代碼

接下來，讓我們開始拆彈！

Phase_1#

phase_1 的匯編代碼如下

2wf9q

string_not_equal 接受 edi、esi 兩個字符串指針輸入，比較兩個字符串，若兩個字符串相等 eax 輸出 0

所以phase_1的作用是比較輸入字符串和存在 0x402400 的字符串是否相等，然後使用 test 判斷輸出是否為 0，若為零則通過，否則調用explode_bomb

所以我們的答案就是 0x404200 處的字符串，使用 GDB 查看

aul0o

關於 GDB 的用法，可以參考這份 CMU 手冊https://csapp.cs.cmu.edu/2e/docs/gdbnotes-x86-64.pdf

tips.Evil 允許你使用文件輸入:./bomb <file>，來避免每次嘗試拆彈時繁瑣的重複輸入

讓我們來試一下拆解第一個炸彈，首先在answer.txt中寫下剛剛獲得的字符串

sx06g

第一個字符串已經通過啦

ud239

Phase_2#

phase_2 匯編代碼如下

4st2b

這個函數比前一個要長不少，同時也調用了read_six_numbers，還有很多的分支跳轉指令

  400efe:	48 83 ec 28          	sub    $0x28,%rsp
  400f02:	48 89 e6             	mov    %rsp,%rsi
  400f05:	e8 52 05 00 00       	call   40145c <read_six_numbers>

在棧上分配 0x28 的空間，將六個數字存入棧中

  400f0a:	83 3c 24 01          	cmpl   $0x1,(%rsp)
  400f0e:	74 20                	je     400f30 <phase_2+0x34>
  400f10:	e8 25 05 00 00       	call   40143a <explode_bomb>

如果第一個數字不是 1，炸彈爆炸

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

rbx指向最後一個數字的後一位，若已經讀取到此處代表六個數字都處理完，判斷結束

通過以上分析，第二個字符串需要符合以下要求

由 6 個數字組成
第一個數字為 1
從第 2 個開始每個數字都為前面的兩倍

所以字符串為1 2 4 8 16 32

Phase_3#

phase_3 的匯編代碼如下

h3g6b

可以發現其中有很多有規律的跳轉語句，並且開頭有一個sscanf，那麼前面出現的 0x4025cf 存儲的應該就是讀取的格式，使用 GDB 打印查看

h2i7l

可以看出我們輸入的字符串應該是兩個數字

  400f6a:	83 7c 24 08 07       	cmpl   $0x7,0x8(%rsp)
  400f6f:	77 3c                	ja     400fad <phase_3+0x6a>

0x8(%rsp)是第一個數字，如果它大於 7 則跳轉至炸彈爆炸

  400f71:	8b 44 24 08          	mov    0x8(%rsp),%eax
  400f75:	ff 24 c5 70 24 40 00 	jmp    *0x402470(,%rax,8)
  400f7c:	b8 cf 00 00 00       	mov    $0xcf,%eax
  400f81:	eb 3b                	jmp    400fbe <phase_3+0x7b>
  400f83:	b8 c3 02 00 00       	mov    $0x2c3,%eax
  400f88:	eb 34                	jmp    400fbe <phase_3+0x7b>
  400f8a:	b8 00 01 00 00       	mov    $0x100,%eax
  400f8f:	eb 2d                	jmp    400fbe <phase_3+0x7b>
  400f91:	b8 85 01 00 00       	mov    $0x185,%eax
  400f96:	eb 26                	jmp    400fbe <phase_3+0x7b>
  400f98:	b8 ce 00 00 00       	mov    $0xce,%eax
  400f9d:	eb 1f                	jmp    400fbe <phase_3+0x7b>
  400f9f:	b8 aa 02 00 00       	mov    $0x2aa,%eax
  400fa4:	eb 18                	jmp    400fbe <phase_3+0x7b>
  400fa6:	b8 47 01 00 00       	mov    $0x147,%eax
  400fab:	eb 11                	jmp    400fbe <phase_3+0x7b>

根據第一個數字選擇第二個數字，類似於switch語句，假設第一個數字是 0，跳轉到 * 0x02470，用 GDB 查看一下這個地方存了什麼

qv677

發現跳轉到 0x400f7c，% eax=0xcf，即 207

  400fbe:	3b 44 24 0c          	cmp    0xc(%rsp),%eax
  400fc2:	74 05                	je     400fc9 <phase_3+0x86>
  400fc4:	e8 71 04 00 00       	call   40143a <explode_bomb>

判斷第二個數字是否與 % eax 相等，不相等則炸彈爆炸

所以這個字符串的一種形式是0 207，根據第一個數字的不同，第二個數字還有其他不同取值

Phase_4#

phase_4 的匯編代碼如下

4gwzt

可以看到除了同樣調用了sscanf，還調用了func4這一函數

老樣子，還是先看一下sscanf接收的格式

yis7d

可以看到還是兩個數字

  40102e:	83 7c 24 08 0e       	cmpl   $0xe,0x8(%rsp)
  401033:	76 05                	jbe    40103a <phase_4+0x2e>
  401035:	e8 00 04 00 00       	call   40143a <explode_bomb>

且第一個數字要小於等於 14 (0xe)

  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       	call   400fce <func4>

將 14，0 和第一個數字作為參數傳入func4，接下來我們來分析func4中發生了什麼

jp6wb

其中有兩個分支跳轉，還有兩次遞歸引用，我們猜測它是一個類似對分查找的程序，嘗試把它寫成 C 格式

int func4(int i, int j, int target) {
    int mid = ((i - j + ((i - j) >> 31)) >> 1) + j;
    if (mid == target) {
        return 0;
    } else if (mid < target) {
        return 2 * func4(i, mid + 1, target) + 1;
    } else {
        return 2 * func4(mid - 1, j, target);
    }
}

為了使輸出為 0，我們只需要一直向左找，而從不找到mid右側，輸入i=14，j=0，所以第一個數字可能的取值為7、3、1、0

  401051:	83 7c 24 0c 00       	cmpl   $0x0,0xc(%rsp)
  401056:	74 05                	je     40105d <phase_4+0x51>
  401058:	e8 dd 03 00 00       	call   40143a <explode_bomb>

最後檢查第二個數字是否為零，所以這個字符串可以取3 0

Phase_5#

phase_5 的匯編代碼內容

8dfcd

我們看到這其中有兩個字符串常量0x4024b0和0x40245e我們用 GDB 看看它們都是什么

17fa2

"maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you"

"flyers"

我淺淺推測：第一條應該是一個字典，因為在使用時有偏移量0x4024b0(%rdx)；第二條是目標字符串，傳入 <string_not_equal> 比較用戶輸入的字符串通過字典翻譯過後是否與目標相同

在這樣的假設基礎上，仔細觀察通過字典翻譯的過程：

  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

其中%cl是%ecx寄存器的低 8 位，將其再與上 0xf，就是取低四位，所以再翻譯時取字符字節的低四位作為偏移量！

那麼 "flyers" 對應字典偏移量為 "9 15 14 5 6 7"，可以寫一個 python 腳本來生成一些符合要求的字符串

spell = [9, 15, 14, 5, 6, 7]

for offset in range(8):
    result = "".join(chr(num + 16 * offset) for num in spell)
    print(f"Offset {offset * 16} : {result}")

運行結果：

ryghc

所以第五個字符串可以是 IONEFG，看来猜测是正确的，我们并没有仔细逐句阅读汇编代码就得到了答案

Phase_6#

這個函數的長度明顯較之前長了許多，我在這裡放上最重要的一部分代碼

upap4

我簡要說明一下這段代碼在幹什麼，就不細致分析了，感興趣的讀者可以自行下載源碼查看

在內存中存有一個鏈表

rcr1i

首先讀入 6 個數字，且範圍在 1-6 之間

然後將這 6 個數字對 7 求補，也就是i=7-i

以數字i為索引，尋找鏈表的第i個結點，將指向這個結點的指針入棧

通過棧中節點的順序重寫每個節點的nextnode指針，使鏈表結點順序符合棧中順序

最後檢查鏈表中結點的data是否降序

想要使結點中數字降序排序，順序應當是3 4 5 6 1 2，對 7 求補後為4 3 2 1 6 5這就是我們要求的字符串了

拆彈成功#

至此，拆除炸彈所需的 6 個字符串都被我們求出來了，寫入answer.txt中

h0218

運行./bomb answer.txt，得到

ed5zn

雖然這個 lab 對於真正的逆向工程來說屬於 hello world 水平，但是讓我熟悉了 x86-64 匯編和 GDB 基本指令

總的來說這是一個很有意思的實驗，根本停不下來