From 6b57097c8fd34e86658a7b8e8ac3080c23c462b4 Mon Sep 17 00:00:00 2001 From: Navan Chauhan Date: Wed, 4 Oct 2023 16:59:12 -0600 Subject: adding phase 6 --- docs/posts/2023-10-04-bomb-lab.html | 242 ++++++++++++++++++++++++++++++++++-- 1 file changed, 229 insertions(+), 13 deletions(-) (limited to 'docs/posts') diff --git a/docs/posts/2023-10-04-bomb-lab.html b/docs/posts/2023-10-04-bomb-lab.html index 28ce317..26c1e53 100644 --- a/docs/posts/2023-10-04-bomb-lab.html +++ b/docs/posts/2023-10-04-bomb-lab.html @@ -636,20 +636,22 @@ 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(15): # We can limit to 14
-   if func4(x) == 2:
-      print(f"answer is {x}")
-      break
+

+
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(15): # We can limit to 14
+   if func4(x) == 2:
+      print(f"answer is {x}")
+      break
 

+

 
 
Running this code, we get: answer is 5

 
@@ -800,6 +802,220 @@ Good work!  On to the next...
 
 
Phase 6

 
+
Good work!  On to the next...
+test string
+
+Breakpoint 1, 0x0000555555555899 in phase_6 ()
+(gdb) disas phase_6
+Dump of assembler code for function phase_6:
+=> 0x0000555555555899 <+0>:     endbr64 
+   0x000055555555589d <+4>:     push   %r15
+   0x000055555555589f <+6>:     push   %r14
+   0x00005555555558a1 <+8>:     push   %r13
+   0x00005555555558a3 <+10>:    push   %r12
+   0x00005555555558a5 <+12>:    push   %rbp
+   0x00005555555558a6 <+13>:    push   %rbx
+   0x00005555555558a7 <+14>:    sub    $0x68,%rsp
+   0x00005555555558ab <+18>:    lea    0x40(%rsp),%rax
+   0x00005555555558b0 <+23>:    mov    %rax,%r14
+   0x00005555555558b3 <+26>:    mov    %rax,0x8(%rsp)
+   0x00005555555558b8 <+31>:    mov    %rax,%rsi
+   0x00005555555558bb <+34>:    call   0x555555555d97 <read_six_numbers>
+   0x00005555555558c0 <+39>:    mov    %r14,%r12
+   0x00005555555558c3 <+42>:    mov    $0x1,%r15d
+   0x00005555555558c9 <+48>:    mov    %r14,%r13
+   0x00005555555558cc <+51>:    jmp    0x555555555997 <phase_6+254>
+   0x00005555555558d1 <+56>:    call   0x555555555d4a <explode_bomb>
+   0x00005555555558d6 <+61>:    jmp    0x5555555559a9 <phase_6+272>
+   0x00005555555558db <+66>:    add    $0x1,%rbx
+   0x00005555555558df <+70>:    cmp    $0x5,%ebx
+   0x00005555555558e2 <+73>:    jg     0x55555555598f <phase_6+246>
+   0x00005555555558e8 <+79>:    mov    0x0(%r13,%rbx,4),%eax
+   0x00005555555558ed <+84>:    cmp    %eax,0x0(%rbp)
+   0x00005555555558f0 <+87>:    jne    0x5555555558db <phase_6+66>
+   0x00005555555558f2 <+89>:    call   0x555555555d4a <explode_bomb>
+   0x00005555555558f7 <+94>:    jmp    0x5555555558db <phase_6+66>
+   0x00005555555558f9 <+96>:    mov    0x8(%rsp),%rdx
+   0x00005555555558fe <+101>:   add    $0x18,%rdx
+   0x0000555555555902 <+105>:   mov    $0x7,%ecx
+   0x0000555555555907 <+110>:   mov    %ecx,%eax
+   0x0000555555555909 <+112>:   sub    (%r12),%eax
+   0x000055555555590d <+116>:   mov    %eax,(%r12)
+   0x0000555555555911 <+120>:   add    $0x4,%r12
+   0x0000555555555915 <+124>:   cmp    %r12,%rdx
+   0x0000555555555918 <+127>:   jne    0x555555555907 <phase_6+110>
+   0x000055555555591a <+129>:   mov    $0x0,%esi
+   0x000055555555591f <+134>:   mov    0x40(%rsp,%rsi,4),%ecx
+   0x0000555555555923 <+138>:   mov    $0x1,%eax
+   0x0000555555555928 <+143>:   lea    0x3d01(%rip),%rdx        # 0x555555559630 <node1>
+--Type <RET> for more, q to quit, c to continue without paging--
+   0x000055555555592f <+150>:   cmp    $0x1,%ecx
+   0x0000555555555932 <+153>:   jle    0x55555555593f <phase_6+166>
+   0x0000555555555934 <+155>:   mov    0x8(%rdx),%rdx
+   0x0000555555555938 <+159>:   add    $0x1,%eax
+   0x000055555555593b <+162>:   cmp    %ecx,%eax
+   0x000055555555593d <+164>:   jne    0x555555555934 <phase_6+155>
+   0x000055555555593f <+166>:   mov    %rdx,0x10(%rsp,%rsi,8)
+   0x0000555555555944 <+171>:   add    $0x1,%rsi
+   0x0000555555555948 <+175>:   cmp    $0x6,%rsi
+   0x000055555555594c <+179>:   jne    0x55555555591f <phase_6+134>
+   0x000055555555594e <+181>:   mov    0x10(%rsp),%rbx
+   0x0000555555555953 <+186>:   mov    0x18(%rsp),%rax
+   0x0000555555555958 <+191>:   mov    %rax,0x8(%rbx)
+   0x000055555555595c <+195>:   mov    0x20(%rsp),%rdx
+   0x0000555555555961 <+200>:   mov    %rdx,0x8(%rax)
+   0x0000555555555965 <+204>:   mov    0x28(%rsp),%rax
+   0x000055555555596a <+209>:   mov    %rax,0x8(%rdx)
+   0x000055555555596e <+213>:   mov    0x30(%rsp),%rdx
+   0x0000555555555973 <+218>:   mov    %rdx,0x8(%rax)
+   0x0000555555555977 <+222>:   mov    0x38(%rsp),%rax
+   0x000055555555597c <+227>:   mov    %rax,0x8(%rdx)
+   0x0000555555555980 <+231>:   movq   $0x0,0x8(%rax)
+   0x0000555555555988 <+239>:   mov    $0x5,%ebp
+   0x000055555555598d <+244>:   jmp    0x5555555559c4 <phase_6+299>
+   0x000055555555598f <+246>:   add    $0x1,%r15
+   0x0000555555555993 <+250>:   add    $0x4,%r14
+   0x0000555555555997 <+254>:   mov    %r14,%rbp
+   0x000055555555599a <+257>:   mov    (%r14),%eax
+   0x000055555555599d <+260>:   sub    $0x1,%eax
+   0x00005555555559a0 <+263>:   cmp    $0x5,%eax
+   0x00005555555559a3 <+266>:   ja     0x5555555558d1 <phase_6+56>
+   0x00005555555559a9 <+272>:   cmp    $0x5,%r15d
+   0x00005555555559ad <+276>:   jg     0x5555555558f9 <phase_6+96>
+   0x00005555555559b3 <+282>:   mov    %r15,%rbx
+   0x00005555555559b6 <+285>:   jmp    0x5555555558e8 <phase_6+79>
+   0x00005555555559bb <+290>:   mov    0x8(%rbx),%rbx
+   0x00005555555559bf <+294>:   sub    $0x1,%ebp
+   0x00005555555559c2 <+297>:   je     0x5555555559d5 <phase_6+316>
+   0x00005555555559c4 <+299>:   mov    0x8(%rbx),%rax
+   0x00005555555559c8 <+303>:   mov    (%rax),%eax
+   0x00005555555559ca <+305>:   cmp    %eax,(%rbx)
+--Type <RET> for more, q to quit, c to continue without paging--
+   0x00005555555559cc <+307>:   jge    0x5555555559bb <phase_6+290>
+   0x00005555555559ce <+309>:   call   0x555555555d4a <explode_bomb>
+   0x00005555555559d3 <+314>:   jmp    0x5555555559bb <phase_6+290>
+   0x00005555555559d5 <+316>:   add    $0x68,%rsp
+   0x00005555555559d9 <+320>:   pop    %rbx
+   0x00005555555559da <+321>:   pop    %rbp
+   0x00005555555559db <+322>:   pop    %r12
+   0x00005555555559dd <+324>:   pop    %r13
+   0x00005555555559df <+326>:   pop    %r14
+   0x00005555555559e1 <+328>:   pop    %r15
+   0x00005555555559e3 <+330>:   ret    
+End of assembler dump.
+(gdb) 
+

+
+
Again, we see the familiar read_six_digits function.

+
+
Let us analyse this function in chunks:

+
+
   0x00005555555558bb <+34>:    call   0x555555555d97 <read_six_numbers>
+   0x00005555555558c0 <+39>:    mov    %r14,%r12
+   0x00005555555558c3 <+42>:    mov    $0x1,%r15d
+   0x00005555555558c9 <+48>:    mov    %r14,%r13
+   0x00005555555558cc <+51>:    jmp    0x555555555997 <phase_6+254>
+

+
+
    
+
  1. Read six numbers
    2. 
+
  2. Initialise Registers:
+2.1. mov %r14,%r12: %r14 should be pointing to the location of the stack where the numbers were read into. This address is copied onto %r12
+2.2. mov $0x1,%r15d: The value 1 is moved into %r15 register (probably acting like a counter)
+2.3. mov %r14,%r13: The value is also copied to %r13
    3. 
+
  3. Jump to start of loop:
    4. 
+

+
+
   0x0000555555555997 <+254>:   mov    %r14,%rbp
+   0x000055555555599a <+257>:   mov    (%r14),%eax
+   0x000055555555599d <+260>:   sub    $0x1,%eax
+   0x00005555555559a0 <+263>:   cmp    $0x5,%eax
+   0x00005555555559a3 <+266>:   ja     0x5555555558d1 <phase_6+56>
+

+
+
    
+
  1. Initialise register and point to first number in sequence
    2. 
+
  2. Adjust number(s):
+2.1. mov (%r14),%eax -> load the current number in the sequence
+2.2. sub $0x1,%eax -> decrement number by 1
    3. 
+
  3. Validation
+3.1. cmp $0x5,%eax: This compares the adjusted value in %eax with 5.
+3.2. ja 0x5555555558d1 <phase_6+56>: jump if given value is > 5 or < 0
    4. 
+

+
+
=> All numbers should be between 1 and 6.

+
+
   0x00005555555559a9 <+272>:   cmp    $0x5,%r15d
+   0x00005555555559ad <+276>:   jg     0x5555555558f9 <phase_6+96>
+

+
+
This checks if the value stored in %r15 is > 5, if it is then it jumps somewhere else. This validates our assumption that %r15 is acting as a counter.

+
+
   0x00005555555559b3 <+282>:   mov    %r15,%rbx
+   0x00005555555559b6 <+285>:   jmp    0x5555555558e8 <phase_6+79>
+

+
+
Let us jump to +79

+
+
   0x00005555555558e8 <+79>:    mov    0x0(%r13,%rbx,4),%eax
+   0x00005555555558ed <+84>:    cmp    %eax,0x0(%rbp)
+   0x00005555555558f0 <+87>:    jne    0x5555555558db <phase_6+66>
+   0x00005555555558f2 <+89>:    call   0x555555555d4a <explode_bomb>
+   0x00005555555558f7 <+94>:    jmp    0x5555555558db <phase_6+66>
+

+
+
This section deals with checking if all the numbers in the sequence are unique or not. Thus, we need to ensure out 6 digits are unique

+
+
   0x00005555555558db <+66>:    add    $0x1,%rbx // Increments by 1
+   0x00005555555558df <+70>:    cmp    $0x5,%ebx 
+   0x00005555555558e2 <+73>:    jg     0x55555555598f <phase_6+246> // Jump if > 5 (Loop iterations are complete)
+   0x00005555555558e8 <+79>:    mov    0x0(%r13,%rbx,4),%eax 
+   0x00005555555558ed <+84>:    cmp    %eax,0x0(%rbp)
+   0x00005555555558f0 <+87>:    jne    0x5555555558db <phase_6+66> // Again, check if the number being seen is unique
+

+
+
Now we know that the numbers are unique, between 1-6 (inclusive).

+
+
After stepping through the instructions, we can also see that the numbers are being transformed:
+* By subtracting it from 7 (mov $0x7,%ecx followed by sub (%r12),%eax)
+* This effectively maps the numbers as follows: 1 to 6, 2 to 5, 3 to 4, 4 to 3, 5 to 2, and 6 to 1.

+
+
Let us try to figure out what 0x0000555555555928 <+143>:   lea    0x3d01(%rip),%rdx        # 0x555555559630 <node1> is:

+
+
(gdb) x/30wx 0x555555559630
+0x555555559630 <node1>: 0x000000d9      0x00000001      0x55559640      0x00005555
+0x555555559640 <node2>: 0x000003ab      0x00000002      0x55559650      0x00005555
+0x555555559650 <node3>: 0x0000014f      0x00000003      0x55559660      0x00005555
+0x555555559660 <node4>: 0x000000a1      0x00000004      0x55559670      0x00005555
+0x555555559670 <node5>: 0x000001b3      0x00000005      0x55559120      0x00005555
+0x555555559680 <host_table>:    0x555573f5      0x00005555      0x5555740f      0x00005555
+0x555555559690 <host_table+16>: 0x55557429      0x00005555      0x00000000      0x00000000
+0x5555555596a0 <host_table+32>: 0x00000000      0x00000000
+(gdb) x/30wx 0x555555559120
+0x555555559120 <node6>: 0x000002da      0x00000006      0x00000000      0x00000000
+0x555555559130: 0x00000000      0x00000000      0x00000000      0x00000000
+0x555555559140 <userid>:        0x61767861      0x38383535      0x00000000      0x00000000
+0x555555559150 <userid+16>:     0x00000000      0x00000000      0x00000000      0x00000000
+0x555555559160 <userid+32>:     0x00000000      0x00000000      0x00000000      0x00000000
+0x555555559170 <userid+48>:     0x00000000      0x00000000      0x00000000      0x00000000
+0x555555559180 <userid+64>:     0x00000000      0x00000000      0x00000000      0x00000000
+0x555555559190 <userid+80>:     0x00000000      0x00000000
+(gdb) 
+

+
+
It appears that this is a linked list. With roughly the following structure:

+
+

+
struct node {
+    int value;
+    int index;
+    struct node *next;
+};
+

+

+
+
Let us convert the values into decimal

+
 	
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.

 	
-- 
cgit v1.2.3