Try   HackMD

Bomb Lab 解題嘗試

contributed by <afcidk,potter903p>

預備知識

打開README 資料內有提示到之 useful tools :

ARM Assembly Basics

實驗流程

說明影片

phase_0

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 - Page 14 of 33)

在 gdb 裡印出該區塊的內容,因為我們知道比對的會是字串,直接印出來就好。

(gdb) x/s $r1
0x8b2c:	"help"

phase_1

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

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

  • 第一部份

    ​​​​0x0000885a <+42>:	mov	r3, r0
    ​​​​0x0000885c <+44>:	cmp	r3, #4
    

    在呼叫完 sscanf 後,會檢查 r0 (回傳值) 是否等於 4 。對照 sscanf man page,得知回傳值是成功配對且指派 (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) x/s $r1
    ​​​​0x8bc8:	"%d %d %d %d"
    

    因此只要輸入任意 4 個數字就可以通過第一部份

  • 第二部份

    ​​​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 40 0 10 0 都會是可以通過的輸入。

phase_3

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) 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.
    ​​​0x000088be <+46>: ldr r3, [r7, #12] ​​​0x000088c0 <+48>: cmp r3, #40 ; 0x28 ​​​0x000088c2 <+50>: beq.n 0x88ce <phase_3+62>
  2. b = b + c
    ​​​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>
  3. 比較 b 和 c
    ​​​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 90 0 7 都可以通過。

phase_4

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) x/s 0x8be0
0x8be0:	"%d"

發現只需要輸入一個數字,這個數字會被指派到 $r7+12

接下來看到第 16 行,程式把 $r7+12 的內容放到 $r0 裡面當做參數,並呼叫 fun4

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

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

    ​​​​0x000088f2 <+14>: movs r3, #1 ​​​​0x000088f4 <+16>: b.n 0x8904 <fun4+32>

    $r3 指派成 1 ,再跳到區塊 5.

  3. 參數不等於 0 (遞迴呼叫前)

    ​​​​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 (遞迴呼叫後)

    ​​​​0x00008900 <+28>: mov r3, r0 ​​​​0x00008902 <+30>: lsls r3, r3, #1

    取回上一次遞迴回傳值,再將他左移 1 位元

  5. 離開 fun4

    ​​​​0x00008904 <+32>: mov r0, r3

    結束遞迴流程,回傳 $r0

理解了上面五個區塊,可以發現 fun4 的作用是回傳 1<<x,其中 x 是輸入的數字。

回到 phase_4 區塊,發現會檢查回傳值 和 1024 是否相等

0x0000893a <+46>: mov r3, r0 0x0000893c <+48>: cmp.w r3, #1024 ; 0x400 0x00008940 <+52>: beq.n 0x8946 <phase_4+58>

得知我們輸入的數字需要是 10 ,因為

210=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 後五行指令。

參考資料