Binary Bomb Phase 5: What value would let the loop go through 15 times?

Question

I am currently working on defusing a binary bomb and am stuck on phase 5. As far as I could figure out, there is a loop and the index (%edx) needs to be 15 to get through the loop. However, I am stuck at the array which always returns 15 after 6 cycles, therefore leaving the first loop and comparing %edx which only gets to 6, comparing this to 15 and therefore failing.

How do i calculate the value that is needed in order for the cycle to be done 15 times? The array is: 10, 2, 14, 7, 8, 12, 15, 11, 0, 4, 1, 13, 3, 9, 6, 5

0000000000401061 <phase_5>:
  401061:   53                      push   %rbx
  401062:   48 83 ec 10             sub    $0x10,%rsp
  401066:   48 89 fb                mov    %rdi,%rbx
  401069:   e8 53 12 00 00          call   4022c1 <phase_init>
  40106e:   48 8d 4c 24 08          lea    0x8(%rsp),%rcx
  401073:   48 8d 54 24 0c          lea    0xc(%rsp),%rdx
  401078:   be 90 28 40 00          mov    $0x402890,%esi
  40107d:   48 89 df                mov    %rbx,%rdi
  401080:   b8 00 00 00 00          mov    $0x0,%eax
  401085:   e8 36 fa ff ff          call   400ac0 <__isoc99_sscanf@plt>
  40108a:   83 f8 01                cmp    $0x1,%eax
  40108d:   7f 05                   jg     401094 <phase_5+0x33>
  40108f:   e8 98 04 00 00          call   40152c <explode_bomb>
  401094:   8b 44 24 0c             mov    0xc(%rsp),%eax
  401098:   83 e0 0f                and    $0xf,%eax
  40109b:   89 44 24 0c             mov    %eax,0xc(%rsp)
  40109f:   83 f8 0f                cmp    $0xf,%eax
  4010a2:   74 30                   je     4010d4 <phase_5+0x73>
  4010a4:   b9 64 00 00 00          mov    $0x64,%ecx
  4010a9:   ba 00 00 00 00          mov    $0x0,%edx
  4010ae:   83 c2 01                add    $0x1,%edx
  4010b1:   48 98                   cltq   
  4010b3:   8b 04 85 80 26 40 00    mov    0x402680(,%rax,4),%eax
  4010ba:   29 c1                   sub    %eax,%ecx
  4010bc:   83 f8 0f                cmp    $0xf,%eax
  4010bf:   75 ed                   jne    4010ae <phase_5+0x4d>
  4010c1:   c7 44 24 0c 0f 00 00    movl   $0xf,0xc(%rsp)
  4010c8:   00 
  4010c9:   83 fa 0f                cmp    $0xf,%edx
  4010cc:   75 06                   jne    4010d4 <phase_5+0x73>
  4010ce:   3b 4c 24 08             cmp    0x8(%rsp),%ecx
  4010d2:   74 05                   je     4010d9 <phase_5+0x78>
  4010d4:   e8 53 04 00 00          call   40152c <explode_bomb>
  4010d9:   48 83 c4 10             add    $0x10,%rsp
  4010dd:   5b                      pop    %rbx
  4010de:   c3                      ret

I am sorry if the question seems stupid, but i only recently got into reverse engineering and am quite new to the whole topic. Thank you!

I tried to start behind the array position which would be 15, so I inputted 7 which allowed me to get 12 cycles. I also tried to use the position of 0 in the array which would be 8 (32/4), but without luck.

I think you need to start at the end, the `5`. That is index 15. — Jester, Feb 11 '23 at 18:51

score 2 · Answer 1 · answered Feb 11 '23 at 20:25

Full reverse engineering works bottom up.
You start by finding out what each group of instructions does and then you link the reversed operations together.

If the code is short, you can do it all in your head. If the code is not short, it's necessary to annotate the assembly listing.
This is the part that may require being used to compilers' output, in this case, however, I didn't find anything unusual so I'll just present the annotated assembly without further explanations:

  401061:   53                      push   %rbx
  401062:   48 83 ec 10             sub    $0x10,%rsp               ;Prologue
  
  401066:   48 89 fb                mov    %rdi,%rbx                ;rbx = arg1
  
  401069:   e8 53 12 00 00          call   4022c1 <phase_init>      ;phase_init();
  
  40106e:   48 8d 4c 24 08          lea    0x8(%rsp),%rcx           ;var2
  401073:   48 8d 54 24 0c          lea    0xc(%rsp),%rdx           ;var1
  401078:   be 90 28 40 00          mov    $0x402890,%esi
  40107d:   48 89 df                mov    %rbx,%rdi
  401080:   b8 00 00 00 00          mov    $0x0,%eax
  401085:   e8 36 fa ff ff          call   400ac0 <__isoc99_sscanf@plt>     ;int res = sscanf(arg1, 0x402890, &var1, &var2) 
  
  40108a:   83 f8 01                cmp    $0x1,%eax                ;if (res <= 1)
  40108d:   7f 05                   jg     401094 <phase_5+0x33>    ;   explode_bomb()
  40108f:   e8 98 04 00 00          call   40152c <explode_bomb>
  
  401094:   8b 44 24 0c             mov    0xc(%rsp),%eax
  401098:   83 e0 0f                and    $0xf,%eax
  40109b:   89 44 24 0c             mov    %eax,0xc(%rsp)           ;var1 &= 0xf;
  
  40109f:   83 f8 0f                cmp    $0xf,%eax
  4010a2:   74 30                   je     4010d4 <phase_5+0x73>    ;if (var1 == 0xf)
                                                                    ;   explode_bomb()

  4010a4:   b9 64 00 00 00          mov    $0x64,%ecx               ;int j = 100
  4010a9:   ba 00 00 00 00          mov    $0x0,%edx                ;int i = 0
                                                                    ;int n = var1
  
;loop:
  4010ae:   83 c2 01                add    $0x1,%edx                ;i++
                                        
  4010b1:   48 98                   cltq   
  4010b3:   8b 04 85 80 26 40 00    mov    0x402680(,%rax,4),%eax       
  4010ba:   29 c1                   sub    %eax,%ecx                ;k -= 0x402680[n]
  
  4010bc:   83 f8 0f                cmp    $0xf,%eax
  4010bf:   75 ed                   jne    4010ae <phase_5+0x4d>    ;if (n != 0xf) goto loop
  
  4010c1:   c7 44 24 0c 0f 00 00    movl   $0xf,0xc(%rsp)           ;var1 = 0xf
  4010c8:   00 
  4010c9:   83 fa 0f                cmp    $0xf,%edx                ;if (i != 0xf)
  4010cc:   75 06                   jne    4010d4 <phase_5+0x73>    ;   explode_bomb()
  
  4010ce:   3b 4c 24 08             cmp    0x8(%rsp),%ecx           if (k != var2)
  4010d2:   74 05                   je     4010d9 <phase_5+0x78>    ;   explode_bomb()
  
  4010d4:   e8 53 04 00 00          call   40152c <explode_bomb>
  
  4010d9:   48 83 c4 10             add    $0x10,%rsp               ;epilogue
  4010dd:   5b                      pop    %rbx
  4010de:   c3                      ret

The introduction of the variable n is maybe the only "trick" here. Such a variable is necessary since the compiler reads and writes eax in the loop body and in the first iteration eax contains the value of var1.

With these comments, it's easy to write an equivalent C program.
Note how similar the generated assembly and the original assembly listing are.

So, two numbers are read. The first is a start index and the second is an integer that we'll call diff. Basically, we have an array that is a permutation of [0..15] and given the start index the program cycles through this permutation until it found the index 15. Meanwhile it:

Count the times it reads from the array
Subtract the read items from a constant k (of initial value 100).

Finally, if the iteration count is 15 and k is diff, the bomb does not explode.

How do we find a starting index that cycles 15 times?
Well, we could simply bruteforce it but here's an algorithmic way.
Start from any index i and cycle until you reach 15. Then cycle back until you reach the number at index 15.

So, the array is:

  Index  0  1   2  3  4   5   6   7  8  9 10  11 12 13 14 15 
  Value 10, 2, 14, 7, 8, 12, 15, 11, 0, 4, 1, 13, 3, 9, 6, 5

Let's arbitrarily start from index 1, we get the sequence 1 2 14 6 15. Now going backward (which index has value 1?) we can add 10 to the left of 1, then again (which index has value 10) we can add 0 to the left of 10. The full sequence is 5 12 3 7 11 13 9 4 8 0 10 1 2 14 6 15.

You should now be able to find the start index and hence the first number to input.
The second number to input is easy to find.

UPinar · Answer 2 · 2023-02-12T05:04:17.320

This is the pseudo code that i wrote when i was solving this phase

[rbp+64] -> firstInput int(dword)
[rbp+84] -> secondInput int(dword)

  00007ff6`9c2b24d9 mov     eax,dword ptr [rbp+64h]
  00007ff6`9c2b24dc and     eax,0Fh
  00007ff6`9c2b24df mov     dword ptr [rbp+64h],eax
  
  // get firstInput mask it with 0Fh

  00007ff6`9c2b24e5 mov     dword ptr [rbp+44h],eax
  00007ff6`9c2b24e8 mov     dword ptr [rbp+4],0
  00007ff6`9c2b24ef mov     dword ptr [rbp+24h],0
  00007ff6`9c2b24f6 cmp     dword ptr [rbp+64h],0Fh -----RETURN HERE!
  00007ff6`9c2b24fa je      bomb!phase_5+0xc4 (00007ff6`9c2b2524)
  
  if([rbp+64] == 0Fh)  //at first, [rbp+64] == firstInput 
  jmp 00007ff6`9c2b2524
  {
    00007ff6`9c2b2524 cmp     dword ptr [rbp+4],0Fh //firstLoop == 0;
    if ([rbp+4] == 0Fh)
        00007ff6`9c2b252a mov     eax,dword ptr [rbp+84h]
        00007ff6`9c2b2530 cmp     dword ptr [rbp+24h],eax
        if (secondInput == [rbp+24])
            00007ff6`9c2b2533 je      !!!!!!!!EXIT!!!!!!!!
        else
            BOMB.EXPLODE();
    else
    {
        jmp 00007ff6`9c2b2535
        BOMB.EXPLODE();
    }
  }
  else ([rbp+64] != 0Fh)
  {
  [rbp+4] = 0 //firstTime
  00007ff6`9c2b24fc mov     eax,dword ptr [rbp+4] 
  00007ff6`9c2b24ff inc     eax
  00007ff6`9c2b2501 mov     dword ptr [rbp+4],eax
  [rbp+4] == rax == 1 //firstTime
  00007ff6`9c2b2504 movsxd  rax,dword ptr [rbp+64h]
  rax == firstInput //firstTime
  00007ff6`9c2b2508 lea     rcx,[bomb!n1+0x20 (00007ff6`9c2bf1d0)]
  00007ff6`9c2b250f mov     eax,dword ptr [rcx+rax*4] 
    eax = 00007ff6`9c2bf1d0 + (rcx + firstInput * 4);
    !!! eax value depends on firstInput !!!
    switch([rbp+64])
    {
    case 0:
        eax = A;
    case 1:
        eax = 2;
    case 2:
        eax = E;
    case 3:
        eax = 7;
    case 4:
        eax = 8;
    case 5:
        eax = C;
    case 6:
        eax = F;
    case 7:
        eax = B;
    case 8:
        eax = 0;
    case 9:
        eax = 4;
    case A:
        eax = 1;
    case B:
        eax = D;
    case C:
        eax = 3;
    case D:
        eax = 9;
    case E:
        eax = 6;
    case F:
        eax = 5;
    }
    
    00007ff6`9c2b2512 mov     dword ptr [rbp+64h],eax
    
    RULE !!! 0Fh > firstInput > 0 !!!
  

    00007ff6`9c2b2518 mov     ecx,dword ptr [rbp+24h]
    // ecx == [rbp+24] == 0; //firstTime
    00007ff6`9c2b251b add     ecx,eax
    // ecx = eax; //firstTime
    00007ff6`9c2b251d mov     eax,ecx
    00007ff6`9c2b251f mov     dword ptr [rbp+24h],eax
    [rbp+24] == eax == ecx; //firstTime
    
    00007ff6`9c2b2522 jmp     bomb!phase_5+0x96 (00007ff6`9c2b24f6)
   }

First lets check our [rbp+4] value, which is 0 in the beginning. To get out from this bomb we need to make [rbp+4] = 0Fh.

We need to loop for 15 times to make [rbp+4] value from 1 to 0Fh,

With that information we understand after 15 loops our [rbp+64] needs to be 0Fh and we reassign [rbp+64] inside else block by using these two lines.

00007ff69c2b2508 488d0dc1cc0000 lea rcx,[bomb!n1+0x20 (00007ff69c2bf1d0)]

00007ff69c2b250f 8b0481 mov eax,dword ptr [rcx+rax*4]

Every memory address stores different values from 0 to 0Fh

([rcx+rax*4]) >> dd 00007ff69c2bf1d0 + 0*4 >> returns A

Second thing to check [rbp+24] needs to be equal secondInput when all other nested if statements become true. [rbp+24] changes inside outer else with these 3 lines

00007ff69c2b2518 mov ecx,dword ptr [rbp+24h]

00007ff69c2b251b add ecx,eax

00007ff69c2b251d mov eax,ecx

We basically need to give input x and get output 15 after that loop. for that we can write some code like this.

#include <iostream>
#include <vector>
#include <utility>

using vecType = std::vector<std::pair<int, int>>;

vecType returnFunc(vecType& myVec)
{
    const int nextState[16] = { 10,2,14,7,8,12,15,11,0,4,1,13,3,9,6,5 };

    for (int i = 0; i < myVec.size(); i++)
    {
        for (int j = 1; j < 16; j++)
        {
            myVec[i].first = nextState[myVec[i].first];
            myVec[i].second += myVec[i].first;
        }
    }

    return myVec;
}

int main()
{
    vecType valuesVec;
    for (int i = 0; i < 16; i++)
    {
        valuesVec.push_back(std::make_pair(i, 0));
    }
    returnFunc(valuesVec);

    for (int i = 0; i < valuesVec.size(); i++)
    {
        // i is firstInput and can not be 15 because bomb will explode.
        std::cout << i << " sent in" << '\t';
        // the value we get after 15 loops.
        std::cout << valuesVec[i].first << " comes out " << '\t';
        // secondInput
        std::cout << " secondInput " << valuesVec[i].second << '\n';
    }
}

and the result is

0 sent in       8 comes out      secondInput 120
1 sent in       10 comes out     secondInput 119
2 sent in       1 comes out      secondInput 118
3 sent in       12 comes out     secondInput 117
4 sent in       9 comes out      secondInput 116
5 sent in       15 comes out     secondInput 115
6 sent in       14 comes out     secondInput 114
7 sent in       3 comes out      secondInput 113
8 sent in       4 comes out      secondInput 112
9 sent in       13 comes out     secondInput 111
10 sent in      0 comes out      secondInput 110
11 sent in      7 comes out      secondInput 109
12 sent in      5 comes out      secondInput 108
13 sent in      11 comes out     secondInput 107
14 sent in      2 comes out      secondInput 106
15 sent in      6 comes out      secondInput 105

*Here, use my code* does not answer the question. It also imparts no information that explains why your code is the solution and the OP's post has issues. — Ken White, Feb 12 '23 at 01:50
Actually i am not saying use my code. I understand that OP has already know how to solve it but did not apply to a program, cause i said, i already did same lab. Thought he can look at the code and can say okay it is better to write some code for this problem or find a part that he misses .@KenWhite — UPinar, Feb 12 '23 at 01:53
What is this code? Something that prints the input you should use? Your answer doesn't show people how to get to this from the asm. Margaret Bloom's answer shows the logic of the bomb to be reverse-engineered, and proposes working backwards from the final input which should be much easier, not requiring N^2 assignments and additions. (For humans, scanning a short list to find a match is very fast, and I think you just have to do that N times unless the problem is more complicated than I thought.) Anyway, this calculate-homework-answer program doesn't seem good for gaining understanding. — Peter Cordes, Feb 12 '23 at 02:10
Also, stylistically, it's weird to write a big switch like that where every case assigns a constant. The normal way would be to have a constant array and do `myVec[i].first = nextstate[myVec[i].first];` or something, if you were going to apply basically the same algorithm. — Peter Cordes, Feb 12 '23 at 02:12
@PeterCordes i will check that answer and sequence and will delete this answer, — UPinar, Feb 12 '23 at 02:15
@PeterCordes i edited the code. I don't know much about big O notations yet but i think we still need to loop `N ^ 2` times for this situation or i don't understand Margaret Bloom's answer well but you can understand that with checking the pseudo code. — UPinar, Feb 12 '23 at 04:03
My point was that you probably don't need to write a program to do it. And if you do, an algorithm that a human could implement more easily would be better, e.g. searching a list repeatedly instead of adding to an element of another list. It looks like your bomb is slightly different, using `add` instead of `sub`, as well as being compiled with some optimization so it's easier to follow the asm, but yeah basically the same problem. — Peter Cordes, Feb 12 '23 at 04:11
Also, a `switch` is a very inconvenient and hard-to-read way to represent `mov eax, [rcx+rax*4]` or the OP's `mov eax, [table + rax * 4]`. Without optimization, a switch would compile to an indirect `jmp`, not just a data lookup, which makes a switch not a very good pseudo-code / reverse-engineered / decompiled representation of the asm. — Peter Cordes, Feb 12 '23 at 04:15
'Without optimization, a switch would compile to an indirect jmp, not just a data lookup, which makes a switch not a very good pseudo-code' cool. I will check that. Thank you for the information. — UPinar, Feb 12 '23 at 04:17

Binary Bomb Phase 5: What value would let the loop go through 15 times?

2 Answers2