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.

Answer 1

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:

1. Count the times it reads from the array
2. 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.

Answer 2

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