# Bomb Lab 解題嘗試 contributed by <`afcidk`,`potter903p`> ## 預備知識 打開`README` 資料內有提示到之 useful tools : - [arm-linux-gnueabihf-objdump](https://manpages.debian.org/testing/binutils-arm-linux-gnueabihf/arm-linux-gnueabihf-objdump.1.en.html) - [arm-none-eabi-gdb](https://manned.org/arm-none-eabi-gdb/7308522e) [ARM Assembly Basics](https://azeria-labs.com/writing-arm-assembly-part-1/) ## 實驗流程 [說明影片](https://www.youtube.com/watch?v=LmKRahXvBAE) ### `phase_0` ```asm= Dump of assembler code for function phase_0: 0x000087d8 <+0>: push {r7, lr} 0x000087da <+2>: sub sp, #16 0x000087dc <+4>: add r7, sp, #0 0x000087de <+6>: str r0, [r7, #4] 0x000087e0 <+8>: movw r3, #35628 ; 0x8b2c 0x000087e4 <+12>: movt r3, #0 0x000087e8 <+16>: str r3, [r7, #12] 0x000087ea <+18>: ldr r0, [r7, #4] 0x000087ec <+20>: ldr r1, [r7, #12] 0x000087ee <+22>: blx 0x84c8 <strcmp@plt> 0x000087f2 <+26>: mov r3, r0 0x000087f4 <+28>: cmp r3, #0 0x000087f6 <+30>: beq.n 0x87fc <phase_0+36> 0x000087f8 <+32>: bl 0x87c0 <explode_bomb> 0x000087fc <+36>: adds r7, #16 0x000087fe <+38>: mov sp, r7 0x00008800 <+40>: pop {r7, pc} End of assembler dump. ``` 設定好斷點為 `phase_0` 後故意輸入錯誤答案 `asdf` ，gdb 提示跳到斷點位置 `0x87e4` ，接著往下看發現會先遇到 `strcmp` 再判斷是不是要執行 `explode_bomb`，因此可以猜測這個部份只是單純的比對字串而已。 觀察組合語言，發現 r0 指向我們輸入的字串，r1 則是指向答案的字串開頭。 （參考 [AAPCS, §5.1.1 - Core Registers](http://infocenter.arm.com/help/topic/com.arm.doc.ihi0042f/IHI0042F_aapcs.pdf) - Page 14 of 33） 在 gdb 裡印出該區塊的內容，因為我們知道比對的會是字串，直接印出來就好。 ```gdb (gdb) x/s $r1 0x8b2c: "help" ``` ### `phase_1` ```asm= Dump of assembler code for function phase_1: 0x00008804 <+0>: push {r7, lr} 0x00008806 <+2>: sub sp, #16 0x00008808 <+4>: add r7, sp, #0 0x0000880a <+6>: str r0, [r7, #4] 0x0000880c <+8>: movw r3, #35636 ; 0x8b34 0x00008810 <+12>: movt r3, #0 0x00008814 <+16>: str r3, [r7, #12] 0x00008816 <+18>: ldr r0, [r7, #4] 0x00008818 <+20>: ldr r1, [r7, #12] 0x0000881a <+22>: blx 0x84c8 <strcmp@plt> 0x0000881e <+26>: mov r3, r0 0x00008820 <+28>: cmp r3, #0 0x00008822 <+30>: beq.n 0x8828 <phase_1+36> 0x00008824 <+32>: bl 0x87c0 <explode_bomb> 0x00008828 <+36>: adds r7, #16 0x0000882a <+38>: mov sp, r7 0x0000882c <+40>: pop {r7, pc} End of assembler dump. ``` 同 `phase_0`，在 gdb 裡面找到 r1 指向的資料，就可以找到了。 ```gdb (gdb) x/s $r1 0x8b34: "Yea, though I walk through the valley of the shadow of death, I will fear no evil; for thou art with me: thy rod and thy staff, they comfort me." ``` ### `phase_2` ```asm= Dump of assembler code for function phase_2: 0x00008830 <+0>: push {r7, lr} 0x00008832 <+2>: sub sp, #40 ; 0x28 0x00008834 <+4>: add r7, sp, #8 0x00008836 <+6>: str r0, [r7, #4] 0x00008838 <+8>: add.w r2, r7, #12 0x0000883c <+12>: add.w r3, r7, #16 0x00008840 <+16>: add.w r1, r7, #20 0x00008844 <+20>: str r1, [sp, #0] 0x00008846 <+22>: add.w r1, r7, #24 0x0000884a <+26>: str r1, [sp, #4] 0x0000884c <+28>: ldr r0, [r7, #4] 0x0000884e <+30>: movw r1, #35784 ; 0x8bc8 0x00008852 <+34>: movt r1, #0 0x00008856 <+38>: blx 0x8540 <__isoc99_sscanf@plt> 0x0000885a <+42>: mov r3, r0 0x0000885c <+44>: cmp r3, #4 0x0000885e <+46>: beq.n 0x8864 <phase_2+52> 0x00008860 <+48>: bl 0x87c0 <explode_bomb> 0x00008864 <+52>: movs r3, #0 0x00008866 <+54>: str r3, [r7, #28] 0x00008868 <+56>: b.n 0x8876 <phase_2+70> 0x0000886a <+58>: ldr r3, [r7, #16] 0x0000886c <+60>: adds r3, #1 0x0000886e <+62>: str r3, [r7, #16] 0x00008870 <+64>: ldr r3, [r7, #28] 0x00008872 <+66>: adds r3, #1 0x00008874 <+68>: str r3, [r7, #28] 0x00008876 <+70>: ldr r3, [r7, #28] 0x00008878 <+72>: cmp r3, #9 0x0000887a <+74>: ble.n 0x886a <phase_2+58> 0x0000887c <+76>: ldr r2, [r7, #16] 0x0000887e <+78>: ldr r3, [r7, #20] 0x00008880 <+80>: cmp r2, r3 0x00008882 <+82>: beq.n 0x8888 <phase_2+88> 0x00008884 <+84>: bl 0x87c0 <explode_bomb> 0x00008888 <+88>: adds r7, #32 0x0000888a <+90>: mov sp, r7 0x0000888c <+92>: pop {r7, pc} End of assembler dump. ``` 發現有兩個 `explode_bomb`，代表我們有兩個條件需要克服才能破解 `phase_2`。 * 第一部份 ```asm 0x0000885a <+42>: mov r3, r0 0x0000885c <+44>: cmp r3, #4 ``` 在呼叫完 sscanf 後，會檢查 r0 (回傳值) 是否等於 4 。對照 [sscanf man page](https://linux.die.net/man/3/sscanf)，得知回傳值是成功配對且指派 (assign) 成功的數量。 > These functions return the number of input items successfully matched and assigned 想要得到回傳值為 4 ，我們知道要成功配對 4 個變數，因此使用 gdb 查看第二個參數（format string）為何。 > int sscanf(const char *str, const char *format, ...); ```gdb (gdb) x/s $r1 0x8bc8: "%d %d %d %d" ``` 因此只要輸入任意 4 個數字就可以通過第一部份 * 第二部份 ```asm= 0x00008864 <+52>: movs r3, #0 0x00008866 <+54>: str r3, [r7, #28] 0x00008868 <+56>: b.n 0x8876 <phase_2+70> 0x0000886a <+58>: ldr r3, [r7, #16] 0x0000886c <+60>: adds r3, #1 0x0000886e <+62>: str r3, [r7, #16] 0x00008870 <+64>: ldr r3, [r7, #28] 0x00008872 <+66>: adds r3, #1 0x00008874 <+68>: str r3, [r7, #28] 0x00008876 <+70>: ldr r3, [r7, #28] 0x00008878 <+72>: cmp r3, #9 0x0000887a <+74>: ble.n 0x886a <phase_2+58> 0x0000887c <+76>: ldr r2, [r7, #16] 0x0000887e <+78>: ldr r3, [r7, #20] 0x00008880 <+80>: cmp r2, r3 0x00008882 <+82>: beq.n 0x8888 <phase_2+88> ``` 這個部份看起來比較複雜一些，但是如果先轉換為我們熟悉的表達方式，就可以比較好理解。 ``` r3 = 0 *(r7+28) = r3 goto Start --------------Restart------------ r3 = *(r7+16) \ ++r3 | 效果等同於 *(r7+16) += 1 *(r7+16) = r3 / r3 = *(r7+28) \ ++r3 | 效果等同於 *(r7+28) += 1 *(r7+28) = r3 / ---------------Start------------- r3 = *(r7+28) if (r3 <= 9) goto Restart if (*(r7+16) == *(r7+20)) YOU_PASS else FAIL ``` 可以發現在 Restart 和 Start 之間總共跑了 10 次迴圈，其中 `*(r7+16)` 加了 10 次 1。 回頭看一開始，我們輸入的數字分別被存到 `$r7+12`，`$r7+16`，`$r7+20`，`$r7+24` 裡面。 因為最後我們比較的是 `$r7+20` 和 `$r7+16`，但是在迴圈裡面 `$r7+16` 被加上了 10，所以得到結論： 第二個數字加上 10 要等於第三個數字。 結合兩個部份，得到答案： 輸入 4 個數字，其中第二個數字加 10 要等於第三個數字。 像是 `1 -3 7 4` 和 `0 0 10 0` 都會是可以通過的輸入。 ### `phase_3` ```asm= Dump of assembler code for function phase_3: 0x00008890 <+0>: push {r7, lr} 0x00008892 <+2>: sub sp, #32 0x00008894 <+4>: add r7, sp, #8 0x00008896 <+6>: str r0, [r7, #4] 0x00008898 <+8>: add.w r2, r7, #12 0x0000889c <+12>: add.w r3, r7, #16 0x000088a0 <+16>: add.w r1, r7, #20 0x000088a4 <+20>: str r1, [sp, #0] 0x000088a6 <+22>: ldr r0, [r7, #4] 0x000088a8 <+24>: movw r1, #35796 ; 0x8bd4 0x000088ac <+28>: movt r1, #0 0x000088b0 <+32>: blx 0x8540 <__isoc99_sscanf@plt> 0x000088b4 <+36>: mov r3, r0 0x000088b6 <+38>: cmp r3, #3 0x000088b8 <+40>: beq.n 0x88be <phase_3+46> 0x000088ba <+42>: bl 0x87c0 <explode_bomb> 0x000088be <+46>: ldr r3, [r7, #12] 0x000088c0 <+48>: cmp r3, #40 ; 0x28 0x000088c2 <+50>: beq.n 0x88ce <phase_3+62> 0x000088c4 <+52>: ldr r2, [r7, #16] 0x000088c6 <+54>: ldr r3, [r7, #20] 0x000088c8 <+56>: add r3, r2 0x000088ca <+58>: str r3, [r7, #16] 0x000088cc <+60>: b.n 0x88d0 <phase_3+64> 0x000088ce <+62>: nop 0x000088d0 <+64>: ldr r2, [r7, #16] 0x000088d2 <+66>: ldr r3, [r7, #20] 0x000088d4 <+68>: cmp r2, r3 0x000088d6 <+70>: beq.n 0x88dc <phase_3+76> 0x000088d8 <+72>: bl 0x87c0 <explode_bomb> 0x000088dc <+76>: adds r7, #24 0x000088de <+78>: mov sp, r7 0x000088e0 <+80>: pop {r7, pc} End of assembler dump. ``` 感覺應該是和 `phase_2` 相似的作法，都是使用到 `sscanf`。 先把 format string 印出來看看，知道輸入應該是三個 int 型態的數字。 ```gdb (gdb) x/s 0x8bd4 0x8bd4: "%d %d %d" ``` 回頭看儲存的資料和位址分別是 r0: input r1: format string (`%d %d %d`) $r7+12: 數字 a $r7+16: 數字 b $r7+20: 數字 c 下面的 code 分成三個部份 1. 判斷 a 是不是 40，是就跳到 3. ```asm=18 0x000088be <+46>: ldr r3, [r7, #12] 0x000088c0 <+48>: cmp r3, #40 ; 0x28 0x000088c2 <+50>: beq.n 0x88ce <phase_3+62> ``` 3. b = b + c ```asm=21 0x000088c4 <+52>: ldr r2, [r7, #16] 0x000088c6 <+54>: ldr r3, [r7, #20] 0x000088c8 <+56>: add r3, r2 0x000088ca <+58>: str r3, [r7, #16] 0x000088cc <+60>: b.n 0x88d0 <phase_3+64> ``` 5. 比較 b 和 c ```asm=26 0x000088ce <+62>: nop 0x000088d0 <+64>: ldr r2, [r7, #16] 0x000088d2 <+66>: ldr r3, [r7, #20] 0x000088d4 <+68>: cmp r2, r3 0x000088d6 <+70>: beq.n 0x88dc <phase_3+76> ``` 綜合上面分析出來的三個 block，可以歸納出兩個條件 * 如果 a 等於 40， b 要等於 c。 * 如果 a 不等於 40，b 要等於 0，c 可為任意值。 滿足上面條件的輸入，像是 `40 9 9`，`0 0 7` 都可以通過。 ### `phase_4` ```asm= Dump of assembler code for function phase_4: 0x0000890c <+0>: push {r7, lr} 0x0000890e <+2>: sub sp, #16 0x00008910 <+4>: add r7, sp, #0 0x00008912 <+6>: str r0, [r7, #4] 0x00008914 <+8>: add.w r3, r7, #12 0x00008918 <+12>: ldr r0, [r7, #4] 0x0000891a <+14>: movw r1, #35808 ; 0x8be0 0x0000891e <+18>: movt r1, #0 0x00008922 <+22>: mov r2, r3 0x00008924 <+24>: blx 0x8540 <__isoc99_sscanf@plt> 0x00008928 <+28>: mov r3, r0 0x0000892a <+30>: cmp r3, #1 0x0000892c <+32>: beq.n 0x8932 <phase_4+38> 0x0000892e <+34>: bl 0x87c0 <explode_bomb> 0x00008932 <+38>: ldr r3, [r7, #12] 0x00008934 <+40>: mov r0, r3 0x00008936 <+42>: bl 0x88e4 <fun4> 0x0000893a <+46>: mov r3, r0 0x0000893c <+48>: cmp.w r3, #1024 ; 0x400 0x00008940 <+52>: beq.n 0x8946 <phase_4+58> 0x00008942 <+54>: bl 0x87c0 <explode_bomb> 0x00008946 <+58>: adds r7, #16 0x00008948 <+60>: mov sp, r7 0x0000894a <+62>: pop {r7, pc} End of assembler dump. ``` 和前面的步驟相同，先查看 format string 是什麼 ```gdb (gdb) x/s 0x8be0 0x8be0: "%d" ``` 發現只需要輸入一個數字，這個數字會被指派到 `$r7+12`。 接下來看到第 16 行，程式把 `$r7+12` 的內容放到 `$r0` 裡面當做參數，並呼叫 `fun4`。 ```asm= Dump of assembler code for function fun4: 0x000088e4 <+0>: push {r7, lr} 0x000088e6 <+2>: sub sp, #8 0x000088e8 <+4>: add r7, sp, #0 0x000088ea <+6>: str r0, [r7, #4] 0x000088ec <+8>: ldr r3, [r7, #4] 0x000088ee <+10>: cmp r3, #0 0x000088f0 <+12>: bne.n 0x88f6 <fun4+18> 0x000088f2 <+14>: movs r3, #1 0x000088f4 <+16>: b.n 0x8904 <fun4+32> 0x000088f6 <+18>: ldr r3, [r7, #4] 0x000088f8 <+20>: subs r3, #1 0x000088fa <+22>: mov r0, r3 0x000088fc <+24>: bl 0x88e4 <fun4> 0x00008900 <+28>: mov r3, r0 0x00008902 <+30>: lsls r3, r3, #1 0x00008904 <+32>: mov r0, r3 0x00008906 <+34>: adds r7, #8 0x00008908 <+36>: mov sp, r7 0x0000890a <+38>: pop {r7, pc} End of assembler dump. ``` 觀察一下 assembly code，我們拆成五個區塊比較好理解 1. **進入 `fun4`** ```asm=4 0x000088e8 <+4>: add r7, sp, #0 0x000088ea <+6>: str r0, [r7, #4] 0x000088ec <+8>: ldr r3, [r7, #4] 0x000088ee <+10>: cmp r3, #0 0x000088f0 <+12>: bne.n 0x88f6 <fun4+18> ``` 這個區塊會利用輸入的參數 (`$r0`) 判斷等一下要跳到區塊 2. 或是區塊 3. 2. **參數等於 0** ```asm=9 0x000088f2 <+14>: movs r3, #1 0x000088f4 <+16>: b.n 0x8904 <fun4+32> ``` 把 `$r3` 指派成 1 ，再跳到區塊 5. 3. **參數不等於 0 (遞迴呼叫前)** ```asm=11 0x000088f6 <+18>: ldr r3, [r7, #4] 0x000088f8 <+20>: subs r3, #1 0x000088fa <+22>: mov r0, r3 0x000088fc <+24>: bl 0x88e4 <fun4> ``` 把參數減 1 遞迴呼叫 `fun4`，回到區塊 1. 4. **參數不等於 0 (遞迴呼叫後)** ```asm=15 0x00008900 <+28>: mov r3, r0 0x00008902 <+30>: lsls r3, r3, #1 ``` 取回上一次遞迴回傳值，再將他左移 1 位元 5. **離開 `fun4`** ```asm=17 0x00008904 <+32>: mov r0, r3 ``` 結束遞迴流程，回傳 `$r0` 理解了上面五個區塊，可以發現 `fun4` 的作用是回傳 1<<x，其中 x 是輸入的數字。 回到 `phase_4` 區塊，發現會檢查回傳值 和 1024 是否相等 ```asm=19 0x0000893a <+46>: mov r3, r0 0x0000893c <+48>: cmp.w r3, #1024 ; 0x400 0x00008940 <+52>: beq.n 0x8946 <phase_4+58> ``` 得知我們輸入的數字需要是 10 ，因為 $2^{10}=1024$ ### 總結答案 綜合上面的分析，我們測試一組答案看有沒有通過 ``` Example phase 0, please type in help > help Phase 0 defused. It's your turn now, cheer up =) > Yea, though I walk through the valley of the shadow of death, I will fear no evil; for thou art with me: thy rod and thy staff, they comfort me. Phase 1 defused. > 0 0 10 0 Phase 2 defused. > 40 99 99 Phase 3 defused. > 10 Phase 4 defused. Congratulations! You've defused the bomb! ``` 通過了～ ## 小技巧~ * objdump 可以透過 `$ arm-linux-gnueabihf-objdump -d bomb > bomb_assembly` 將執行檔的 assembly code 拿出來，再分段對程式碼做分析。 * define hook-stop 每次會在程式中斷的時候執行 hook-stop 裡面 define 好的指令。 e.g. ``` (gdb) define hook-stop Redefine command "hook-stop"? (y or n) y <-- 出現這行代表有 define 過 ， Type commands for definition of "hook-stop". 按 y 會把原本的覆蓋掉 End with a line saying just "end". >x/5i $pc >end ``` 像是這樣就會在每次中斷的時候印出 pc 後五行指令。 ## 參考資料 - [ARM Architecture Reference Manual](https://www.scss.tcd.ie/~waldroj/3d1/arm_arm.pdf) - [GNU ARM Assembler Quick Reference ](http://www.ic.unicamp.br/~celio/mc404-2014/docs/gnu-arm-directives.pdf)