diff options
| -rw-r--r-- | Content/posts/2023-10-04-bomb-lab.md | 218 | ||||
| -rw-r--r-- | docs/feed.rss | 244 | ||||
| -rw-r--r-- | docs/posts/2023-10-04-bomb-lab.html | 242 |
3 files changed, 676 insertions, 28 deletions
diff --git a/Content/posts/2023-10-04-bomb-lab.md b/Content/posts/2023-10-04-bomb-lab.md index 98c5272..d72322f 100644 --- a/Content/posts/2023-10-04-bomb-lab.md +++ b/Content/posts/2023-10-04-bomb-lab.md @@ -611,7 +611,7 @@ 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. -``` +```python def func4(edi, esi=0, edx=20): ecx = (edx - esi) // 2 + esi if ecx > edi: @@ -778,3 +778,219 @@ Awesome! ## 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. 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. Jump to start of loop: + +``` + 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. 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. 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 + +=> 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: + +```cpp +struct node { + int value; + int index; + struct node *next; +}; +``` + +Let us convert the values into decimal diff --git a/docs/feed.rss b/docs/feed.rss index deeb637..17c12c3 100644 --- a/docs/feed.rss +++ b/docs/feed.rss @@ -4,8 +4,8 @@ <title>Navan's Archive</title> <description>Rare Tips, Tricks and Posts</description> <link>https://web.navan.dev/</link><language>en</language> - <lastBuildDate>Wed, 04 Oct 2023 15:54:23 -0000</lastBuildDate> - <pubDate>Wed, 04 Oct 2023 15:54:23 -0000</pubDate> + <lastBuildDate>Wed, 04 Oct 2023 16:58:57 -0000</lastBuildDate> + <pubDate>Wed, 04 Oct 2023 16:58:57 -0000</pubDate> <ttl>250</ttl> <atom:link href="https://web.navan.dev/feed.rss" rel="self" type="application/rss+xml"/> @@ -3801,20 +3801,22 @@ jmp 0x5555555557b4 <func4+27> <p>We can either try to compute the values by hand, or write a simple script in Python to get the answer.</p> -<pre><code>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 +<div class="codehilite"> +<pre><span></span><code><span class="k">def</span> <span class="nf">func4</span><span class="p">(</span><span class="n">edi</span><span class="p">,</span> <span class="n">esi</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">edx</span><span class="o">=</span><span class="mi">20</span><span class="p">):</span> + <span class="n">ecx</span> <span class="o">=</span> <span class="p">(</span><span class="n">edx</span> <span class="o">-</span> <span class="n">esi</span><span class="p">)</span> <span class="o">//</span> <span class="mi">2</span> <span class="o">+</span> <span class="n">esi</span> + <span class="k">if</span> <span class="n">ecx</span> <span class="o">></span> <span class="n">edi</span><span class="p">:</span> + <span class="k">return</span> <span class="mi">2</span> <span class="o">*</span> <span class="n">func4</span><span class="p">(</span><span class="n">edi</span><span class="p">,</span> <span class="n">esi</span><span class="p">,</span> <span class="n">ecx</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> + <span class="k">elif</span> <span class="n">ecx</span> <span class="o"><</span> <span class="n">edi</span><span class="p">:</span> + <span class="k">return</span> <span class="mi">2</span> <span class="o">*</span> <span class="n">func4</span><span class="p">(</span><span class="n">edi</span><span class="p">,</span> <span class="n">ecx</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">edx</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span> + <span class="k">else</span><span class="p">:</span> + <span class="k">return</span> <span class="mi">0</span> -for x in range(15): # We can limit to 14 - if func4(x) == 2: - print(f"answer is {x}") - break +<span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">15</span><span class="p">):</span> <span class="c1"># We can limit to 14</span> + <span class="k">if</span> <span class="n">func4</span><span class="p">(</span><span class="n">x</span><span class="p">)</span> <span class="o">==</span> <span class="mi">2</span><span class="p">:</span> + <span class="nb">print</span><span class="p">(</span><span class="sa">f</span><span class="s2">"answer is </span><span class="si">{</span><span class="n">x</span><span class="si">}</span><span class="s2">"</span><span class="p">)</span> + <span class="k">break</span> </code></pre> +</div> <p>Running this code, we get: <code>answer is 5</code></p> @@ -3964,6 +3966,220 @@ Good work! On to the next... <p>Awesome!</p> <h2>Phase 6</h2> + +<pre><code>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) +</code></pre> + +<p>Again, we see the familiar <code>read_six_digits</code> function.</p> + +<p>Let us analyse this function in chunks:</p> + +<pre><code> 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> +</code></pre> + +<ol> +<li>Read six numbers</li> +<li>Initialise Registers: +2.1. <code>mov %r14,%r12</code>: <code>%r14</code> should be pointing to the location of the stack where the numbers were read into. This address is copied onto <code>%r12</code> +2.2. <code>mov $0x1,%r15d</code>: The value <code>1</code> is moved into <code>%r15</code> register (probably acting like a counter) +2.3. <code>mov %r14,%r13</code>: The value is also copied to <code>%r13</code></li> +<li>Jump to start of loop:</li> +</ol> + +<pre><code> 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> +</code></pre> + +<ol> +<li>Initialise register and point to first number in sequence</li> +<li>Adjust number(s): +2.1. <code>mov (%r14),%eax</code> -> load the current number in the sequence +2.2. <code>sub $0x1,%eax</code> -> decrement number by 1</li> +<li>Validation +3.1. <code>cmp $0x5,%eax</code>: This compares the adjusted value in <code>%eax</code> with 5. +3.2. <code>ja 0x5555555558d1 <phase_6+56></code>: jump if given value is > 5 or < 0</li> +</ol> + +<p>=> All numbers should be between 1 and 6.</p> + +<pre><code> 0x00005555555559a9 <+272>: cmp $0x5,%r15d + 0x00005555555559ad <+276>: jg 0x5555555558f9 <phase_6+96> +</code></pre> + +<p>This checks if the value stored in <code>%r15</code> is > 5, if it is then it jumps somewhere else. This validates our assumption that <code>%r15</code> is acting as a counter.</p> + +<pre><code> 0x00005555555559b3 <+282>: mov %r15,%rbx + 0x00005555555559b6 <+285>: jmp 0x5555555558e8 <phase_6+79> +</code></pre> + +<p>Let us jump to +79</p> + +<pre><code> 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> +</code></pre> + +<p>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</p> + +<pre><code> 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 +</code></pre> + +<p>Now we know that the numbers are unique, between 1-6 (inclusive).</p> + +<p>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.</p> + +<p>Let us try to figure out what <code>0x0000555555555928 <+143>: lea 0x3d01(%rip),%rdx # 0x555555559630 <node1></code> is:</p> + +<pre><code>(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) +</code></pre> + +<p>It appears that this is a linked list. With roughly the following structure:</p> + +<div class="codehilite"> +<pre><span></span><code><span class="k">struct</span><span class="w"> </span><span class="nc">node</span><span class="w"> </span><span class="p">{</span><span class="w"></span> +<span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">value</span><span class="p">;</span><span class="w"></span> +<span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">index</span><span class="p">;</span><span class="w"></span> +<span class="w"> </span><span class="k">struct</span><span class="w"> </span><span class="nc">node</span><span class="w"> </span><span class="o">*</span><span class="n">next</span><span class="p">;</span><span class="w"></span> +<span class="p">};</span><span class="w"></span> +</code></pre> +</div> + +<p>Let us convert the values into decimal</p> ]]></content:encoded> </item> 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> <p>We can either try to compute the values by hand, or write a simple script in Python to get the answer.</p> -<pre><code>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 +<div class="codehilite"> +<pre><span></span><code><span class="k">def</span> <span class="nf">func4</span><span class="p">(</span><span class="n">edi</span><span class="p">,</span> <span class="n">esi</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">edx</span><span class="o">=</span><span class="mi">20</span><span class="p">):</span> + <span class="n">ecx</span> <span class="o">=</span> <span class="p">(</span><span class="n">edx</span> <span class="o">-</span> <span class="n">esi</span><span class="p">)</span> <span class="o">//</span> <span class="mi">2</span> <span class="o">+</span> <span class="n">esi</span> + <span class="k">if</span> <span class="n">ecx</span> <span class="o">></span> <span class="n">edi</span><span class="p">:</span> + <span class="k">return</span> <span class="mi">2</span> <span class="o">*</span> <span class="n">func4</span><span class="p">(</span><span class="n">edi</span><span class="p">,</span> <span class="n">esi</span><span class="p">,</span> <span class="n">ecx</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> + <span class="k">elif</span> <span class="n">ecx</span> <span class="o"><</span> <span class="n">edi</span><span class="p">:</span> + <span class="k">return</span> <span class="mi">2</span> <span class="o">*</span> <span class="n">func4</span><span class="p">(</span><span class="n">edi</span><span class="p">,</span> <span class="n">ecx</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="n">edx</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span> + <span class="k">else</span><span class="p">:</span> + <span class="k">return</span> <span class="mi">0</span> + +<span class="k">for</span> <span class="n">x</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">15</span><span class="p">):</span> <span class="c1"># We can limit to 14</span> + <span class="k">if</span> <span class="n">func4</span><span class="p">(</span><span class="n">x</span><span class="p">)</span> <span class="o">==</span> <span class="mi">2</span><span class="p">:</span> + <span class="nb">print</span><span class="p">(</span><span class="sa">f</span><span class="s2">"answer is </span><span class="si">{</span><span class="n">x</span><span class="si">}</span><span class="s2">"</span><span class="p">)</span> + <span class="k">break</span> </code></pre> +</div> <p>Running this code, we get: <code>answer is 5</code></p> @@ -800,6 +802,220 @@ Good work! On to the next... <h2>Phase 6</h2> +<pre><code>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) +</code></pre> + +<p>Again, we see the familiar <code>read_six_digits</code> function.</p> + +<p>Let us analyse this function in chunks:</p> + +<pre><code> 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> +</code></pre> + +<ol> +<li>Read six numbers</li> +<li>Initialise Registers: +2.1. <code>mov %r14,%r12</code>: <code>%r14</code> should be pointing to the location of the stack where the numbers were read into. This address is copied onto <code>%r12</code> +2.2. <code>mov $0x1,%r15d</code>: The value <code>1</code> is moved into <code>%r15</code> register (probably acting like a counter) +2.3. <code>mov %r14,%r13</code>: The value is also copied to <code>%r13</code></li> +<li>Jump to start of loop:</li> +</ol> + +<pre><code> 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> +</code></pre> + +<ol> +<li>Initialise register and point to first number in sequence</li> +<li>Adjust number(s): +2.1. <code>mov (%r14),%eax</code> -> load the current number in the sequence +2.2. <code>sub $0x1,%eax</code> -> decrement number by 1</li> +<li>Validation +3.1. <code>cmp $0x5,%eax</code>: This compares the adjusted value in <code>%eax</code> with 5. +3.2. <code>ja 0x5555555558d1 <phase_6+56></code>: jump if given value is > 5 or < 0</li> +</ol> + +<p>=> All numbers should be between 1 and 6.</p> + +<pre><code> 0x00005555555559a9 <+272>: cmp $0x5,%r15d + 0x00005555555559ad <+276>: jg 0x5555555558f9 <phase_6+96> +</code></pre> + +<p>This checks if the value stored in <code>%r15</code> is > 5, if it is then it jumps somewhere else. This validates our assumption that <code>%r15</code> is acting as a counter.</p> + +<pre><code> 0x00005555555559b3 <+282>: mov %r15,%rbx + 0x00005555555559b6 <+285>: jmp 0x5555555558e8 <phase_6+79> +</code></pre> + +<p>Let us jump to +79</p> + +<pre><code> 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> +</code></pre> + +<p>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</p> + +<pre><code> 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 +</code></pre> + +<p>Now we know that the numbers are unique, between 1-6 (inclusive).</p> + +<p>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.</p> + +<p>Let us try to figure out what <code>0x0000555555555928 <+143>: lea 0x3d01(%rip),%rdx # 0x555555559630 <node1></code> is:</p> + +<pre><code>(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) +</code></pre> + +<p>It appears that this is a linked list. With roughly the following structure:</p> + +<div class="codehilite"> +<pre><span></span><code><span class="k">struct</span><span class="w"> </span><span class="nc">node</span><span class="w"> </span><span class="p">{</span><span class="w"></span> +<span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">value</span><span class="p">;</span><span class="w"></span> +<span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">index</span><span class="p">;</span><span class="w"></span> +<span class="w"> </span><span class="k">struct</span><span class="w"> </span><span class="nc">node</span><span class="w"> </span><span class="o">*</span><span class="n">next</span><span class="p">;</span><span class="w"></span> +<span class="p">};</span><span class="w"></span> +</code></pre> +</div> + +<p>Let us convert the values into decimal</p> + <blockquote>If you have scrolled this far, consider subscribing to my mailing list <a href="https://listmonk.navan.dev/subscription/form">here.</a> You can subscribe to either a specific type of post you are interested in, or subscribe to everything with the "Everything" list.</blockquote> <script data-isso="//comments.navan.dev/" src="//comments.navan.dev/js/embed.min.js"></script> |