4

I recently work on an algorithm that encrypt some data with 8 byte length. I worked hard and I successful to get this algorithm, but I need decryption of this algorithm. How I can invert it?

I guess this is a hash algorithm and I can't invert it. but I want to make sure about that.

int tmp1 = 0;
int tmp2 = 0;
unsigned short int _array_1[8]={0};
unsigned short int _array_out[8]={0};

for(int j = 0 ; j <5; j++)
        tmp1 = tmp1 * 0x40 + _array_1[j];
    for(int j = 5; j<8; j++)
        tmp2 = (tmp2 << 5) + _array_1[j];
    for (int j = 0 ; j<4; j++)
        _array_1[j] = (tmp1 >> 8*j ) & 0xFFFF ;
    for (int j = 4 ; j<6; j++)
        _array_1[j] = (tmp2 >> 8*(j-4) ) & 0xFFFF ;
    _array_1[6] = 0;
    _array_1[7] = 0;

    _array_out [0] = (get_diff (_array_1[1],0x1A)) * (get_diff (_array_1[4],0x9C));
    _array_out [1] = (get_diff (_array_1[1],0x9C)) * (get_diff (_array_1[4],0x2E));
    _array_out [2] = (get_diff (_array_1[5],0x1A)) * (get_diff (_array_1[2],0x9C));
    _array_out [3] = (get_diff (_array_1[5],0x9C)) * (get_diff (_array_1[2],0x2E));
    _array_out [4] = (get_diff (_array_1[3],0x1A)) * (get_diff (_array_1[0],0x9C));
    _array_out [5] = (get_diff (_array_1[3],0x9C)) * (get_diff (_array_1[0],0x2E));

And

uint8_t get_diff(uint8_t a, uint8_t b)
{
    uint8_t result =0;
    result = (a> b )?  (a-b) : (b-a);
    return result;
}

Edited:
According to the lan comment I edited my question and some data such as tmp1 and tmp2 added.
Also, I will present an example as instance.
Example
Input = 0x01, 0x05, 0x00, 0x0C, 0x1B, 0x14, 0x18, 0x1A
Output = 0xAE, 0xF4, 0x48, 0x6A, 0x99, 0x81
Thanks.

2
  • If you working on IDA. You can flip up or down around the encryption algorithm, to check if there's the decryption algorithm.
    – hunter
    Jan 21 at 1:53
  • As it stands, your "answer" is more of a commentary. Please post again after providing more context to make it an answer.
    – 0xC0000022L
    Jan 23 at 0:17
3

Non-Invertibility (1)

It's definitely not invertible.

To see this you only need to consider the contents of tmp1 after 2 iterations of the first loop.

Let's unroll these 2 iterations (and, for simplicity of exposition only, assume tmp1 was zero on entry to the loop.) This gives -

tmp1 = _array_1[ 0 ] * 64 + _array_1[ 1 ];

The values of the first two input values are being 'overlapped' meaning that there are multiple sets of values of these that produce the same value for tmp1 after these 2 iterations.

e.g.

_array_1[ 0 ] = 0, _array_1[ 1 ] = 64 => tmp1 = 64
_array_1[ 0 ] = 1, _array_1[ 1 ] =  0 => tmp1 = 64

Since the first 2 iterations of the loop are the only place these first two inputs values are used, the information lost here cannot be being recovered elsewhere so we know that it's not possible to invert.


Non-Invertibility (2)

Separately, if we knew the output data was being treated as bytes too, then you don't even need to look at the mathematical details of the algorithm to understand the un-invertibility.

Instead, the observation that there's 8 bytes of input but only 6 bytes of output is enough to prove it. This is because each possible output will be produced by, on average, 65536 different inputs so you can't go the other way.


Algorithm to find a single valid set of input values

To make your example work in the forward direction, I have had to assume that the the code you've shown is wrong and the types of your input and output arrays are exactly 8-bit (here unsigned char) not unsigned short.

On this basis and given that you say you'd be happy with any arbitrary single solution of the (multiple-valued) inverted algorithm a given output, you can try this -

unsigned char in[] = { 0xAE, 0xF4, 0x48, 0x6A, 0x99, 0x81 };
unsigned char out[8];

brute_force_bifactor( in[0], in[1], &out[1], &out[4] );
brute_force_bifactor( in[2], in[3], &out[5], &out[2] );
brute_force_bifactor( in[4], in[5], &out[3], &out[0] );

int tmp1 = 0;
int tmp2 = 0;
for( int j = 0; j < 4; ++j )
    tmp1 |= out[j] << 8 * j;
for( int j = 4; j < 6; ++j )
    tmp2 |= out[j] << 8 * (j - 4);

/* the following lines are one of many possible ways of splitting tmp1 & tmp2 that successfully invert the algorithm */
for( int j = 0; j < 5; ++j )
    out[j] = (tmp1 >> 6 * (4 - j)) & 0x3F;
for( int j = 5; j < 8; ++j )
    out[j] = (tmp2 >> 5 * (7 - j)) & 0x1F;

with

void brute_force_bifactor( unsigned char a, unsigned char b, unsigned char* px, unsigned char* py )
{
    /* this returns the first pair of values x & y that satisfy the inversion criteria */
    for( int x = 0; x < 256; ++x )
    {
        for( int y = 0; y < 256; ++y )
        {
            if( ((abs( x - 0x1A ) * abs( y - 0x9C )) & 0xFF) != a ) continue;
            if( ((abs( x - 0x9C ) * abs( y - 0x2E )) & 0xFF) != b ) continue;
            *px = x;
            *py = y;
            return;
        }
    }
    exit( 1 );
}

It might be possible improve this brute_force_bifactor function using some clever maths, but as it's at most 65k iterations of the inner loop it's very fast anyway.

4
  • Thanks lan, I agree with you. That was my initial thought. But I was hoping for a solution. So, have you any suggestion to solve this problem for me? Even if the output had multi answer.
    – Unicornux
    Jan 21 at 7:03
  • 1
    The algorithm is sufficiently simple that this might be possible. However your code is not complete enough for this purpose. You'd need to clear about the type and initial.values of tmp1 & tmp2. You'd also need to be sure about the size of the elements of the input and output values. You've defined then as (at least) 16 bits, but you say only 8 bits are used for the input and are silent on the output.
    – Ian Cook
    Jan 21 at 12:16
  • @Unicornux If the input values are static and your custom implementation is equivalent to the shown method you could try to build a input/output map so you could reverse the function at least for certain values (for brute-forcing the input space the input is unfortunately a bit too large...).
    – Robert
    Jan 21 at 13:55
  • @lan Thanks lan. You right, I edited my question. Thanks.
    – Unicornux
    Jan 23 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.