From ffdcd44d54560f8d56e344580d9eb7839d5fdf8f Mon Sep 17 00:00:00 2001 From: Navan Chauhan Date: Wed, 4 Oct 2023 15:21:13 -0600 Subject: added phase 5 --- Content/posts/2023-10-04-bomb-lab.md | 204 +++++++++++++++++++++++++++++++++- docs/feed.rss | 201 +++++++++++++++++++++++++++++++++- docs/index.html | 4 +- docs/posts/2023-10-04-bomb-lab.html | 205 +++++++++++++++++++++++++++++++++-- docs/posts/index.html | 4 +- 5 files changed, 600 insertions(+), 18 deletions(-) diff --git a/Content/posts/2023-10-04-bomb-lab.md b/Content/posts/2023-10-04-bomb-lab.md index 6a84d9e..d235186 100644 --- a/Content/posts/2023-10-04-bomb-lab.md +++ b/Content/posts/2023-10-04-bomb-lab.md @@ -1,10 +1,10 @@ --- date: 2023-10-04 13:12 -description: Introduction, Phases 1-3 of Bomb Lab for CSCI 2400 Lab - 2 +description: Introduction, Phases 1-4 of Bomb Lab for CSCI 2400 Lab - 2 tags: gdb, reverse-engineering, c++, csci2400, assembly --- -# Bomb Lab Phases 1-3 +# Bomb Lab Phases 1-4 ## Introduction @@ -453,3 +453,203 @@ Breakpoint 1, 0x0000555555555638 in phase_3 () Continuing. Halfway there! ``` + +## Phase 4 + +``` +jovyan@jupyter-nach6988:~/lab2-bomblab-navanchauhan/bombbomb$ gdb -ex 'break phase_4' -ex 'break explode_bomb' -ex 'run' -args ./bomb sol.txt +GNU gdb (Ubuntu 12.1-0ubuntu1~22.04) 12.1 +Copyright (C) 2022 Free Software Foundation, Inc. +License GPLv3+: GNU GPL version 3 or later +This is free software: you are free to change and redistribute it. +There is NO WARRANTY, to the extent permitted by law. +Type "show copying" and "show warranty" for details. +This GDB was configured as "x86_64-linux-gnu". +Type "show configuration" for configuration details. +For bug reporting instructions, please see: +. +Find the GDB manual and other documentation resources online at: + . + +For help, type "help". +Type "apropos word" to search for commands related to "word"... +Reading symbols from ./bomb... +Breakpoint 1 at 0x17d3 +Breakpoint 2 at 0x1d4a +Starting program: /home/jovyan/lab2-bomblab-navanchauhan/bombbomb/bomb sol.txt +[Thread debugging using libthread_db enabled] +Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1". +Welcome to my fiendish little bomb. You have 6 phases with +which to blow yourself up. Have a nice day! +Phase 1 defused. How about the next one? +That's number 2. Keep going! +Halfway there! +test string + +Breakpoint 1, 0x00005555555557d3 in phase_4 () +(gdb) disas phase_4 +Dump of assembler code for function phase_4: +=> 0x00005555555557d3 <+0>: endbr64 + 0x00005555555557d7 <+4>: sub $0x18,%rsp + 0x00005555555557db <+8>: lea 0x8(%rsp),%rcx + 0x00005555555557e0 <+13>: lea 0xc(%rsp),%rdx + 0x00005555555557e5 <+18>: lea 0x1bba(%rip),%rsi # 0x5555555573a6 + 0x00005555555557ec <+25>: mov $0x0,%eax + 0x00005555555557f1 <+30>: call 0x5555555552e0 <__isoc99_sscanf@plt> + 0x00005555555557f6 <+35>: cmp $0x2,%eax + 0x00005555555557f9 <+38>: jne 0x555555555802 + 0x00005555555557fb <+40>: cmpl $0xe,0xc(%rsp) + 0x0000555555555800 <+45>: jbe 0x555555555807 + 0x0000555555555802 <+47>: call 0x555555555d4a + 0x0000555555555807 <+52>: mov $0xe,%edx + 0x000055555555580c <+57>: mov $0x0,%esi + 0x0000555555555811 <+62>: mov 0xc(%rsp),%edi + 0x0000555555555815 <+66>: call 0x555555555799 + 0x000055555555581a <+71>: cmp $0x2,%eax + 0x000055555555581d <+74>: jne 0x555555555826 + 0x000055555555581f <+76>: cmpl $0x2,0x8(%rsp) + 0x0000555555555824 <+81>: je 0x55555555582b + 0x0000555555555826 <+83>: call 0x555555555d4a + 0x000055555555582b <+88>: add $0x18,%rsp + 0x000055555555582f <+92>: ret +End of assembler dump. +(gdb) +``` + +Again, `gdb` has marked the string being passed to `scanf` + +``` +(gdb) x/1s 0x5555555573a6 +0x5555555573a6: "%d %d" +``` + +Okay, so this time we are supposed to enter 2 numbers. + +``` + 0x00005555555557f6 <+35>: cmp $0x2,%eax + 0x00005555555557f9 <+38>: jne 0x555555555802 +``` + +Checks if there were 2 values read from calling `scanf`, if not -> jump to `` which calls ``. + +``` + 0x00005555555557fb <+40>: cmpl $0xe,0xc(%rsp) + 0x0000555555555800 <+45>: jbe 0x555555555807 +``` + +Compare `0xe` (14 in Decimal) and value stored at `$rsp` + `0xc` bytes (Decimal 12). If this condition is met (<= 14), jump to ``. If not, then explode bomb. + +``` +... + 0x0000555555555807 <+52>: mov $0xe,%edx + 0x000055555555580c <+57>: mov $0x0,%esi + 0x0000555555555811 <+62>: mov 0xc(%rsp),%edi + 0x0000555555555815 <+66>: call 0x555555555799 + 0x000055555555581a <+71>: cmp $0x2,%eax + 0x000055555555581d <+74>: jne 0x555555555826 + 0x000055555555581f <+76>: cmpl $0x2,0x8(%rsp) + 0x0000555555555824 <+81>: je 0x55555555582b + 0x0000555555555826 <+83>: call 0x555555555d4a +``` + +* ` 0x0000555555555815 <+66>: call 0x555555555799 ` calls another function called `func4` +* The returned value is compared with `0x2`, if they are not equal then the program jumps to call ``. This tells us that `func4` should return 2. + +Let us look into `func4` + +``` +(gdb) disas func4 +Dump of assembler code for function func4: + 0x0000555555555799 <+0>: endbr64 + 0x000055555555579d <+4>: sub $0x8,%rsp + 0x00005555555557a1 <+8>: mov %edx,%ecx + 0x00005555555557a3 <+10>: sub %esi,%ecx + 0x00005555555557a5 <+12>: shr %ecx + 0x00005555555557a7 <+14>: add %esi,%ecx + 0x00005555555557a9 <+16>: cmp %edi,%ecx + 0x00005555555557ab <+18>: ja 0x5555555557b9 + 0x00005555555557ad <+20>: mov $0x0,%eax + 0x00005555555557b2 <+25>: jb 0x5555555557c5 + 0x00005555555557b4 <+27>: add $0x8,%rsp + 0x00005555555557b8 <+31>: ret + 0x00005555555557b9 <+32>: lea -0x1(%rcx),%edx + 0x00005555555557bc <+35>: call 0x555555555799 + 0x00005555555557c1 <+40>: add %eax,%eax + 0x00005555555557c3 <+42>: jmp 0x5555555557b4 + 0x00005555555557c5 <+44>: lea 0x1(%rcx),%esi + 0x00005555555557c8 <+47>: call 0x555555555799 + 0x00005555555557cd <+52>: lea 0x1(%rax,%rax,1),%eax + 0x00005555555557d1 <+56>: jmp 0x5555555557b4 +``` + +This looks like a recursive function :( (I hate recursive functions) + +Let's annotate the instructions. + +``` +endbr64 +sub $0x8,%rsp // subtract 8 bytes from the stack pointer +mov %edx,%ecx // Move the value in register %edx to %ecx +sub %esi,%ecx // Subtract the value in %esi from %ecx +shr %ecx // Right shift the value in %ecx by one bit (dividing the value by 2) +add %esi,%ecx // Add the value in %esi to %ecx +cmp %edi,%ecx // Compare +ja 0x5555555557b9 // If %ecx > %edi -> jump to instruction at offset +32 +mov $0x0,%eax // Move 0 to %eax +jb 0x5555555557c5 // If %ecx < %edi -> jump to instruction at offset +44. +add $0x8,%rsp // add 8 bytes to the stack pointer +ret // return +lea -0x1(%rcx),%edx // LEA of $rxc - 1 into $edx +call 0x555555555799 // Call itself +add %eax,%eax // Double the value in %eax +jmp 0x5555555557b4 // jump to the instruction at offset +27 +lea 0x1(%rcx),%esi +call 0x555555555799 +lea 0x1(%rax,%rax,1),%eax // LEA of %rax * 2 + 1 into $eax +jmp 0x5555555557b4 +``` + +We can either try to compute the values by hand, or write a simple script in Python to get the answer. + +``` +def func4(edi, esi=0, edx=20): + ecx = (edx - esi) // 2 + esi + if ecx > edi: + return 2 * func4(edi, esi, ecx - 1) + elif ecx < edi: + return 2 * func4(edi, ecx + 1, edx) + 1 + else: + return 0 + +for x in range(10): + if func4(x) == 2: + print(f"answer is {x}") + break +``` + +Running this code, we get: `answer is 5` + +Okay, so we know that the number needed to be passed to `func4` is 5. But, what about the second digit? + +If we go back to the code for ``, we can see that: + +``` + 0x000055555555581f <+76>: cmpl $0x2,0x8(%rsp) + 0x0000555555555824 <+81>: je 0x55555555582b +``` + +The value at `$rsp+8` should be equal to 2. So, let us try passing `5 2` as our input. + +``` +... +Phase 1 defused. How about the next one? +That's number 2. Keep going! +Halfway there! +5 2 + +Breakpoint 1, 0x00005555555557d3 in phase_4 () +(gdb) continue +Continuing. +So you got that one. Try this one. +``` + diff --git a/docs/feed.rss b/docs/feed.rss index a6fc5d7..b212d4e 100644 --- a/docs/feed.rss +++ b/docs/feed.rss @@ -4,8 +4,8 @@ Navan's Archive Rare Tips, Tricks and Posts https://web.navan.dev/en - Wed, 04 Oct 2023 14:39:04 -0000 - Wed, 04 Oct 2023 14:39:04 -0000 + Wed, 04 Oct 2023 15:21:02 -0000 + Wed, 04 Oct 2023 15:21:02 -0000 250 @@ -3212,14 +3212,14 @@ logger.info("rdkit-{} installation finished!".format(rdkit.__version__)) https://web.navan.dev/posts/2023-10-04-bomb-lab.html - Bomb Lab Phases 1-3 + Bomb Lab Phases 1-4 - Introduction, Phases 1-3 of Bomb Lab for CSCI 2400 Lab - 2 + Introduction, Phases 1-4 of Bomb Lab for CSCI 2400 Lab - 2 https://web.navan.dev/posts/2023-10-04-bomb-lab.html Wed, 04 Oct 2023 13:12:00 -0000 - Bomb Lab Phases 1-3 + Bomb Lab Phases 1-4

Introduction

@@ -3648,6 +3648,197 @@ Breakpoint 1, 0x0000555555555638 in phase_3 () Continuing. Halfway there! + +

Phase 4

+ +
jovyan@jupyter-nach6988:~/lab2-bomblab-navanchauhan/bombbomb$ gdb -ex 'break phase_4' -ex 'break explode_bomb' -ex 'run' -args ./bomb sol.txt 
+GNU gdb (Ubuntu 12.1-0ubuntu1~22.04) 12.1
+Copyright (C) 2022 Free Software Foundation, Inc.
+License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
+This is free software: you are free to change and redistribute it.
+There is NO WARRANTY, to the extent permitted by law.
+Type "show copying" and "show warranty" for details.
+This GDB was configured as "x86_64-linux-gnu".
+Type "show configuration" for configuration details.
+For bug reporting instructions, please see:
+<https://www.gnu.org/software/gdb/bugs/>.
+Find the GDB manual and other documentation resources online at:
+    <http://www.gnu.org/software/gdb/documentation/>.
+
+For help, type "help".
+Type "apropos word" to search for commands related to "word"...
+Reading symbols from ./bomb...
+Breakpoint 1 at 0x17d3
+Breakpoint 2 at 0x1d4a
+Starting program: /home/jovyan/lab2-bomblab-navanchauhan/bombbomb/bomb sol.txt
+[Thread debugging using libthread_db enabled]
+Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
+Welcome to my fiendish little bomb. You have 6 phases with
+which to blow yourself up. Have a nice day!
+Phase 1 defused. How about the next one?
+That's number 2.  Keep going!
+Halfway there!
+test string
+
+Breakpoint 1, 0x00005555555557d3 in phase_4 ()
+(gdb) disas phase_4
+Dump of assembler code for function phase_4:
+=> 0x00005555555557d3 <+0>:     endbr64 
+   0x00005555555557d7 <+4>:     sub    $0x18,%rsp
+   0x00005555555557db <+8>:     lea    0x8(%rsp),%rcx
+   0x00005555555557e0 <+13>:    lea    0xc(%rsp),%rdx
+   0x00005555555557e5 <+18>:    lea    0x1bba(%rip),%rsi        # 0x5555555573a6
+   0x00005555555557ec <+25>:    mov    $0x0,%eax
+   0x00005555555557f1 <+30>:    call   0x5555555552e0 <__isoc99_sscanf@plt>
+   0x00005555555557f6 <+35>:    cmp    $0x2,%eax
+   0x00005555555557f9 <+38>:    jne    0x555555555802 <phase_4+47>
+   0x00005555555557fb <+40>:    cmpl   $0xe,0xc(%rsp)
+   0x0000555555555800 <+45>:    jbe    0x555555555807 <phase_4+52>
+   0x0000555555555802 <+47>:    call   0x555555555d4a <explode_bomb>
+   0x0000555555555807 <+52>:    mov    $0xe,%edx
+   0x000055555555580c <+57>:    mov    $0x0,%esi
+   0x0000555555555811 <+62>:    mov    0xc(%rsp),%edi
+   0x0000555555555815 <+66>:    call   0x555555555799 <func4>
+   0x000055555555581a <+71>:    cmp    $0x2,%eax
+   0x000055555555581d <+74>:    jne    0x555555555826 <phase_4+83>
+   0x000055555555581f <+76>:    cmpl   $0x2,0x8(%rsp)
+   0x0000555555555824 <+81>:    je     0x55555555582b <phase_4+88>
+   0x0000555555555826 <+83>:    call   0x555555555d4a <explode_bomb>
+   0x000055555555582b <+88>:    add    $0x18,%rsp
+   0x000055555555582f <+92>:    ret    
+End of assembler dump.
+(gdb) 
+
+ +

Again, gdb has marked the string being passed to scanf

+ +
(gdb) x/1s 0x5555555573a6
+0x5555555573a6: "%d %d"
+
+ +

Okay, so this time we are supposed to enter 2 numbers.

+ +
   0x00005555555557f6 <+35>:    cmp    $0x2,%eax
+   0x00005555555557f9 <+38>:    jne    0x555555555802 <phase_4+47>
+
+ +

Checks if there were 2 values read from calling scanf, if not -> jump to <phase_4+47> which calls <explode_bomb>.

+ +
   0x00005555555557fb <+40>:    cmpl   $0xe,0xc(%rsp)
+   0x0000555555555800 <+45>:    jbe    0x555555555807 <phase_4+52>
+
+ +

Compare 0xe (14 in Decimal) and value stored at $rsp + 0xc bytes (Decimal 12). If this condition is met (<= 14), jump to <phase_4+52>. If not, then explode bomb.

+ +
...
+   0x0000555555555807 <+52>:    mov    $0xe,%edx
+   0x000055555555580c <+57>:    mov    $0x0,%esi
+   0x0000555555555811 <+62>:    mov    0xc(%rsp),%edi
+   0x0000555555555815 <+66>:    call   0x555555555799 <func4>
+   0x000055555555581a <+71>:    cmp    $0x2,%eax
+   0x000055555555581d <+74>:    jne    0x555555555826 <phase_4+83>
+   0x000055555555581f <+76>:    cmpl   $0x2,0x8(%rsp)
+   0x0000555555555824 <+81>:    je     0x55555555582b <phase_4+88>
+   0x0000555555555826 <+83>:    call   0x555555555d4a <explode_bomb>
+
+ +
    +
  • 0x0000555555555815 <+66>: call 0x555555555799 <func4> calls another function called func4
    • +
  • The returned value is compared with 0x2, if they are not equal then the program jumps to call <explode_bomb>. This tells us that func4 should return 2.
    • +
+ +

Let us look into func4

+ +
(gdb) disas func4
+Dump of assembler code for function func4:
+   0x0000555555555799 <+0>:     endbr64 
+   0x000055555555579d <+4>:     sub    $0x8,%rsp
+   0x00005555555557a1 <+8>:     mov    %edx,%ecx
+   0x00005555555557a3 <+10>:    sub    %esi,%ecx
+   0x00005555555557a5 <+12>:    shr    %ecx
+   0x00005555555557a7 <+14>:    add    %esi,%ecx
+   0x00005555555557a9 <+16>:    cmp    %edi,%ecx
+   0x00005555555557ab <+18>:    ja     0x5555555557b9 <func4+32>
+   0x00005555555557ad <+20>:    mov    $0x0,%eax
+   0x00005555555557b2 <+25>:    jb     0x5555555557c5 <func4+44>
+   0x00005555555557b4 <+27>:    add    $0x8,%rsp
+   0x00005555555557b8 <+31>:    ret    
+   0x00005555555557b9 <+32>:    lea    -0x1(%rcx),%edx
+   0x00005555555557bc <+35>:    call   0x555555555799 <func4>
+   0x00005555555557c1 <+40>:    add    %eax,%eax
+   0x00005555555557c3 <+42>:    jmp    0x5555555557b4 <func4+27>
+   0x00005555555557c5 <+44>:    lea    0x1(%rcx),%esi
+   0x00005555555557c8 <+47>:    call   0x555555555799 <func4>
+   0x00005555555557cd <+52>:    lea    0x1(%rax,%rax,1),%eax
+   0x00005555555557d1 <+56>:    jmp    0x5555555557b4 <func4+27>
+
+ +

This looks like a recursive function :( (I hate recursive functions)

+ +

Let's annotate the instructions.

+ +
endbr64
+sub $0x8,%rsp  // subtract 8 bytes from the stack pointer
+mov %edx,%ecx  // Move the value in register %edx to %ecx
+sub %esi,%ecx  // Subtract the value in %esi from %ecx
+shr %ecx       // Right shift the value in %ecx by one bit (dividing the value by 2)
+add %esi,%ecx  // Add the value in %esi to %ecx
+cmp %edi,%ecx  // Compare
+ja 0x5555555557b9 <func4+32> // If %ecx > %edi -> jump to instruction at offset +32
+mov $0x0,%eax  // Move 0 to %eax
+jb 0x5555555557c5 <func4+44> // If %ecx < %edi -> jump to instruction at offset +44.
+add $0x8,%rsp  // add 8 bytes to the stack pointer
+ret            // return
+lea -0x1(%rcx),%edx // LEA of $rxc - 1 into $edx
+call 0x555555555799 <func4> // Call itself
+add %eax,%eax  // Double the value in %eax
+jmp 0x5555555557b4 <func4+27> // jump to the instruction at offset +27
+lea 0x1(%rcx),%esi
+call 0x555555555799 <func4>
+lea 0x1(%rax,%rax,1),%eax // LEA of %rax * 2 + 1 into $eax 
+jmp 0x5555555557b4 <func4+27>
+
+ +

We can either try to compute the values by hand, or write a simple script in Python to get the answer.

+ +
def func4(edi, esi=0, edx=20):
+    ecx = (edx - esi) // 2 + esi
+    if ecx > edi:
+        return 2 * func4(edi, esi, ecx - 1)
+    elif ecx < edi:
+        return 2 * func4(edi, ecx + 1, edx) + 1
+    else:
+        return 0
+
+for x in range(10):
+   if func4(x) == 2:
+      print(f"answer is {x}")
+      break
+
+ +

Running this code, we get: answer is 5

+ +

Okay, so we know that the number needed to be passed to func4 is 5. But, what about the second digit?

+ +

If we go back to the code for <phase_4>, we can see that:

+ +
   0x000055555555581f <+76>:    cmpl   $0x2,0x8(%rsp)
+   0x0000555555555824 <+81>:    je     0x55555555582b <phase_4+88>
+
+ +

The value at $rsp+8 should be equal to 2. So, let us try passing 5 2 as our input.

+ +
...
+Phase 1 defused. How about the next one?
+That's number 2.  Keep going!
+Halfway there!
+5 2
+
+Breakpoint 1, 0x00005555555557d3 in phase_4 ()
+(gdb) continue
+Continuing.
+So you got that one.  Try this one.
+
]]> diff --git a/docs/index.html b/docs/index.html index 0b21d00..1f0b9d2 100644 --- a/docs/index.html +++ b/docs/index.html @@ -59,9 +59,9 @@
    -
  • Bomb Lab Phases 1-3
    • +
  • Bomb Lab Phases 1-4
      • -
    • Introduction, Phases 1-3 of Bomb Lab for CSCI 2400 Lab - 2
      • +
    • Introduction, Phases 1-4 of Bomb Lab for CSCI 2400 Lab - 2
    • Published On: 2023-10-04 13:12
    • Tags: diff --git a/docs/posts/2023-10-04-bomb-lab.html b/docs/posts/2023-10-04-bomb-lab.html index c401a99..886c264 100644 --- a/docs/posts/2023-10-04-bomb-lab.html +++ b/docs/posts/2023-10-04-bomb-lab.html @@ -6,16 +6,16 @@ - Bomb Lab Phases 1-3 + Bomb Lab Phases 1-4 - - - - - + + + + + @@ -54,7 +54,7 @@
      -

      Bomb Lab Phases 1-3

      +

      Bomb Lab Phases 1-4

      Introduction

      @@ -482,6 +482,197 @@ Breakpoint 1, 0x0000555555555638 in phase_3 () (gdb) continue Continuing. Halfway there! + + +

      Phase 4

      + +
      jovyan@jupyter-nach6988:~/lab2-bomblab-navanchauhan/bombbomb$ gdb -ex 'break phase_4' -ex 'break explode_bomb' -ex 'run' -args ./bomb sol.txt 
+GNU gdb (Ubuntu 12.1-0ubuntu1~22.04) 12.1
+Copyright (C) 2022 Free Software Foundation, Inc.
+License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
+This is free software: you are free to change and redistribute it.
+There is NO WARRANTY, to the extent permitted by law.
+Type "show copying" and "show warranty" for details.
+This GDB was configured as "x86_64-linux-gnu".
+Type "show configuration" for configuration details.
+For bug reporting instructions, please see:
+<https://www.gnu.org/software/gdb/bugs/>.
+Find the GDB manual and other documentation resources online at:
+    <http://www.gnu.org/software/gdb/documentation/>.
+
+For help, type "help".
+Type "apropos word" to search for commands related to "word"...
+Reading symbols from ./bomb...
+Breakpoint 1 at 0x17d3
+Breakpoint 2 at 0x1d4a
+Starting program: /home/jovyan/lab2-bomblab-navanchauhan/bombbomb/bomb sol.txt
+[Thread debugging using libthread_db enabled]
+Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
+Welcome to my fiendish little bomb. You have 6 phases with
+which to blow yourself up. Have a nice day!
+Phase 1 defused. How about the next one?
+That's number 2.  Keep going!
+Halfway there!
+test string
+
+Breakpoint 1, 0x00005555555557d3 in phase_4 ()
+(gdb) disas phase_4
+Dump of assembler code for function phase_4:
+=> 0x00005555555557d3 <+0>:     endbr64 
+   0x00005555555557d7 <+4>:     sub    $0x18,%rsp
+   0x00005555555557db <+8>:     lea    0x8(%rsp),%rcx
+   0x00005555555557e0 <+13>:    lea    0xc(%rsp),%rdx
+   0x00005555555557e5 <+18>:    lea    0x1bba(%rip),%rsi        # 0x5555555573a6
+   0x00005555555557ec <+25>:    mov    $0x0,%eax
+   0x00005555555557f1 <+30>:    call   0x5555555552e0 <__isoc99_sscanf@plt>
+   0x00005555555557f6 <+35>:    cmp    $0x2,%eax
+   0x00005555555557f9 <+38>:    jne    0x555555555802 <phase_4+47>
+   0x00005555555557fb <+40>:    cmpl   $0xe,0xc(%rsp)
+   0x0000555555555800 <+45>:    jbe    0x555555555807 <phase_4+52>
+   0x0000555555555802 <+47>:    call   0x555555555d4a <explode_bomb>
+   0x0000555555555807 <+52>:    mov    $0xe,%edx
+   0x000055555555580c <+57>:    mov    $0x0,%esi
+   0x0000555555555811 <+62>:    mov    0xc(%rsp),%edi
+   0x0000555555555815 <+66>:    call   0x555555555799 <func4>
+   0x000055555555581a <+71>:    cmp    $0x2,%eax
+   0x000055555555581d <+74>:    jne    0x555555555826 <phase_4+83>
+   0x000055555555581f <+76>:    cmpl   $0x2,0x8(%rsp)
+   0x0000555555555824 <+81>:    je     0x55555555582b <phase_4+88>
+   0x0000555555555826 <+83>:    call   0x555555555d4a <explode_bomb>
+   0x000055555555582b <+88>:    add    $0x18,%rsp
+   0x000055555555582f <+92>:    ret    
+End of assembler dump.
+(gdb) 
+
      + +

      Again, gdb has marked the string being passed to scanf

      + +
      (gdb) x/1s 0x5555555573a6
+0x5555555573a6: "%d %d"
+
      + +

      Okay, so this time we are supposed to enter 2 numbers.

      + +
         0x00005555555557f6 <+35>:    cmp    $0x2,%eax
+   0x00005555555557f9 <+38>:    jne    0x555555555802 <phase_4+47>
+
      + +

      Checks if there were 2 values read from calling scanf, if not -> jump to <phase_4+47> which calls <explode_bomb>.

      + +
         0x00005555555557fb <+40>:    cmpl   $0xe,0xc(%rsp)
+   0x0000555555555800 <+45>:    jbe    0x555555555807 <phase_4+52>
+
      + +

      Compare 0xe (14 in Decimal) and value stored at $rsp + 0xc bytes (Decimal 12). If this condition is met (<= 14), jump to <phase_4+52>. If not, then explode bomb.

      + +
      ...
+   0x0000555555555807 <+52>:    mov    $0xe,%edx
+   0x000055555555580c <+57>:    mov    $0x0,%esi
+   0x0000555555555811 <+62>:    mov    0xc(%rsp),%edi
+   0x0000555555555815 <+66>:    call   0x555555555799 <func4>
+   0x000055555555581a <+71>:    cmp    $0x2,%eax
+   0x000055555555581d <+74>:    jne    0x555555555826 <phase_4+83>
+   0x000055555555581f <+76>:    cmpl   $0x2,0x8(%rsp)
+   0x0000555555555824 <+81>:    je     0x55555555582b <phase_4+88>
+   0x0000555555555826 <+83>:    call   0x555555555d4a <explode_bomb>
+
      + +
        +
      • 0x0000555555555815 <+66>: call 0x555555555799 <func4> calls another function called func4
        • +
      • The returned value is compared with 0x2, if they are not equal then the program jumps to call <explode_bomb>. This tells us that func4 should return 2.
        • +
      + +

      Let us look into func4

      + +
      (gdb) disas func4
+Dump of assembler code for function func4:
+   0x0000555555555799 <+0>:     endbr64 
+   0x000055555555579d <+4>:     sub    $0x8,%rsp
+   0x00005555555557a1 <+8>:     mov    %edx,%ecx
+   0x00005555555557a3 <+10>:    sub    %esi,%ecx
+   0x00005555555557a5 <+12>:    shr    %ecx
+   0x00005555555557a7 <+14>:    add    %esi,%ecx
+   0x00005555555557a9 <+16>:    cmp    %edi,%ecx
+   0x00005555555557ab <+18>:    ja     0x5555555557b9 <func4+32>
+   0x00005555555557ad <+20>:    mov    $0x0,%eax
+   0x00005555555557b2 <+25>:    jb     0x5555555557c5 <func4+44>
+   0x00005555555557b4 <+27>:    add    $0x8,%rsp
+   0x00005555555557b8 <+31>:    ret    
+   0x00005555555557b9 <+32>:    lea    -0x1(%rcx),%edx
+   0x00005555555557bc <+35>:    call   0x555555555799 <func4>
+   0x00005555555557c1 <+40>:    add    %eax,%eax
+   0x00005555555557c3 <+42>:    jmp    0x5555555557b4 <func4+27>
+   0x00005555555557c5 <+44>:    lea    0x1(%rcx),%esi
+   0x00005555555557c8 <+47>:    call   0x555555555799 <func4>
+   0x00005555555557cd <+52>:    lea    0x1(%rax,%rax,1),%eax
+   0x00005555555557d1 <+56>:    jmp    0x5555555557b4 <func4+27>
+
      + +

      This looks like a recursive function :( (I hate recursive functions)

      + +

      Let's annotate the instructions.

      + +
      endbr64
+sub $0x8,%rsp  // subtract 8 bytes from the stack pointer
+mov %edx,%ecx  // Move the value in register %edx to %ecx
+sub %esi,%ecx  // Subtract the value in %esi from %ecx
+shr %ecx       // Right shift the value in %ecx by one bit (dividing the value by 2)
+add %esi,%ecx  // Add the value in %esi to %ecx
+cmp %edi,%ecx  // Compare
+ja 0x5555555557b9 <func4+32> // If %ecx > %edi -> jump to instruction at offset +32
+mov $0x0,%eax  // Move 0 to %eax
+jb 0x5555555557c5 <func4+44> // If %ecx < %edi -> jump to instruction at offset +44.
+add $0x8,%rsp  // add 8 bytes to the stack pointer
+ret            // return
+lea -0x1(%rcx),%edx // LEA of $rxc - 1 into $edx
+call 0x555555555799 <func4> // Call itself
+add %eax,%eax  // Double the value in %eax
+jmp 0x5555555557b4 <func4+27> // jump to the instruction at offset +27
+lea 0x1(%rcx),%esi
+call 0x555555555799 <func4>
+lea 0x1(%rax,%rax,1),%eax // LEA of %rax * 2 + 1 into $eax 
+jmp 0x5555555557b4 <func4+27>
+
      + +

      We can either try to compute the values by hand, or write a simple script in Python to get the answer.

      + +
      def func4(edi, esi=0, edx=20):
+    ecx = (edx - esi) // 2 + esi
+    if ecx > edi:
+        return 2 * func4(edi, esi, ecx - 1)
+    elif ecx < edi:
+        return 2 * func4(edi, ecx + 1, edx) + 1
+    else:
+        return 0
+
+for x in range(10):
+   if func4(x) == 2:
+      print(f"answer is {x}")
+      break
+
      + +

      Running this code, we get: answer is 5

      + +

      Okay, so we know that the number needed to be passed to func4 is 5. But, what about the second digit?

      + +

      If we go back to the code for <phase_4>, we can see that:

      + +
         0x000055555555581f <+76>:    cmpl   $0x2,0x8(%rsp)
+   0x0000555555555824 <+81>:    je     0x55555555582b <phase_4+88>
+
      + +

      The value at $rsp+8 should be equal to 2. So, let us try passing 5 2 as our input.

      + +
      ...
+Phase 1 defused. How about the next one?
+That's number 2.  Keep going!
+Halfway there!
+5 2
+
+Breakpoint 1, 0x00005555555557d3 in phase_4 ()
+(gdb) continue
+Continuing.
+So you got that one.  Try this one.
      If you have scrolled this far, consider subscribing to my mailing list here. You can subscribe to either a specific type of post you are interested in, or subscribe to everything with the "Everything" list.
      diff --git a/docs/posts/index.html b/docs/posts/index.html index cb1a9f4..80c9dac 100644 --- a/docs/posts/index.html +++ b/docs/posts/index.html @@ -62,9 +62,9 @@
        -
      • Bomb Lab Phases 1-3
        • +
      • Bomb Lab Phases 1-4
          • -
        • Introduction, Phases 1-3 of Bomb Lab for CSCI 2400 Lab - 2
          • +
        • Introduction, Phases 1-4 of Bomb Lab for CSCI 2400 Lab - 2
        • Published On: 2023-10-04 13:12
        • Tags: -- cgit v1.2.3