Challenge RE #3

Introduction

In the following posts I'll be explaining the solutions that I manage to do of the Challenge RE. Given that the author with all intention didn't published the solutions, and here I am ... publishing the solution for one 😁. In my defense many times we get stuck solving a given problem and it's totally ok to see the solution and learn from it. Before looking at the solution, please try by yourself you will feel way better when you solve it by yourself. In case you don't want to see the whole solution I warn you from know that this blog contains the solution for Challenge 3.

Problem

The statement of the problem can be found in this link. I also recommend you to check the book Reverse Engineering For Beginners from the same author.

Solution

:

Analizing the assembly code we can notice a pattern in the code,

    mov edx, edi
    shr edx
    or  edx, edi

    mov eax, edx
    shr eax, 2
    or  eax, edx

    mov edx, eax
    shr edx, 4
    or  edx, eax

    mov eax, edx
    shr eax, 8
    or  eax, edx

    mov edx, eax
    shr edx, 16
    or  edx, eax

This code basiccaly it's iterating on powers of 2 and performing the following operations.

a = (a >> (1 << i)) | a

where j = 0, 1, 2, 3, 4. In case you are kind of lost, 1 << i, basically computes the ith power of 2.

Taking this into consideration it's straight forward to translate this snippet of assembly code in the following way.

int i = 0;
for (i = 0; i<= 4; i++) 
    a = (a >> (1 << i)) | a;

The other part of the assembly code consist on a multiplication and a right shift bitwise operation. Which can be translated as follows:

a = (a * 0x4badf0d) >> 26;

The whole assembly code can be translated into the following code in C. Now if we perform several iterations calling this function we can see what it's the output we receive from it. Let's call this function 100 times, and analize the output, because right now we have yes the code but no idea what this produce.

#include <stdio.h>

int v[64]=
    { -1,31, 8,30, -1, 7,-1,-1, 29,-1,26, 6, -1,-1, 2,-1,
      -1,28,-1,-1, -1,19,25,-1, 5,-1,17,-1, 23,14, 1,-1,
       9,-1,-1,-1, 27,-1, 3,-1, -1,-1,20,-1, 18,24,15,10,
      -1,-1, 4,-1, 21,-1,16,11, -1,22,-1,12, 13,-1, 0,-1 };

int f(unsigned a)
{
    unsigned i = 0;
    for (i = 0; i <= 4; i++) {
        a = (a >> (1 << i)) | a;
    }

    a = (a * 0x4badf0d) >> 26;

    return v[a];
}

int main()
{
    int i = 0;
    for (i = 1; i < 100; i++) {
        printf("%d\n", f(i));
    }
}

This code produce the following sequence:

31
30
30
29
29
29
29
28
28
28
28
28
28
28
28
27
27
27
27
27
27
27
27
27
27
27
27
27
27
27
27
26
...

We receive

31 => 1 time, 30 => 2 times, 29 => 4 times, 28 => 8 times, 27 => 16 times, etc...

Looking at this you can get an idea that we are receiving something like this

For 1st number in the sequence we get 31
For 2nd and 3rd in the sequence we get 30 = 31 - 1
For 4th, 5th, 6th, and 7th in the sequence we get 29 = 31 - 2
...

So the values that we are using to substract to 31 form the following sequence:

0 1 1 2 2 2 2 3 3 3 3 3 3 3 3 ...

Now the question is, how do I guess which sequence this corresponds to? Well, browsing you can find amazing websites, like it's the case for The Online Encyclopedia Of Integer Sequences. Searching the sequence on this website you get that this sequence is not other than floor(log2(n)).
Then our desired sequence formula it's basically 31 - floor(log2(n)). How can we be sure about this? The first test that we can perform it's against our own code in this way:

#include <math.h>

...

int g(unsigned a)
{
    return 31 - ((int) (log(a) / log(2)));
}

...

int main()
{
    int i = 0;
    for (i = 1; i < 100; i++) {
        if (g(i) != f(i))
            printf("DIFFERS ON INDEX: %d\n", i);
    }
}

Okay, at least 100 elements of the sequence match, that's good. We can assume now this challenge as solved.