Log in

View Full Version : How to "reverse" this algo???

yaa
May 1st, 2004, 19:48
Hello,

I'd need some help in reversing this algo. But apart this specific piece of code I'd like to understand how to approach similar mathematical problems.

Here is the algorithm:

Code:


// num1 gets loaded with the decimal equivalent of a 16 hex digits string

ulong num1;



uint num2 = ((uint) (num1 >> 48));



if (num2 != 51712)

{

    return false;

}



uint num3 = (((uint) (num1 >> 16)) & -1);



if ((num3 % 10007) != 0)

{

    return false;

}



uint num4 = ((uint) (num1 & ((long) 65535)));

uint num5 = ((num2 + (num3 >> 16)) + (num3 & 65535));

num5 = ((num5 * 7) & 65535);



if (num4 != num5)

{

    return false;

}


What I need to obtain is obviously the value of num1.
How would you approach such a problem??? I have written a brute force app but solving it this way does not satisfy me.


yaa
disavowed
May 1st, 2004, 20:31
Code:


uint num2 = ((uint) (num1 >> 48));

 

if (num2 != 51712)

{

return false;

}
This implies that num1 = 0xCA00???? (?'s mean unknowns)


Code:


uint num3 = (((uint) (num1 >> 16)) & -1);

 

if ((num3 % 10007) != 0)

{

return false;

}
this is impossible... num3 = 0x0000CA00, and num3 % 10007 = 1677. it can never equal 0.

can someone else verify that i'm not doing my math wrong?
r4g3
May 1st, 2004, 20:43
which lame shareware app uses this as serial algo ? ye but its 4.30am and appearently ive got nothing better to do all the job for smbd else
btw since when ulong is defined as long long ?
oki anywayz this is very simplistic. "0123456789ABCDEF"
num2 is the highest 16bits == 4 hex digits of input and those are 5171d == 0xCA00, so "0123" -> "CA00"
num3 is the "456789AB" part. num3 = ((rand()*rand())%429197)*10007; here rand()*rand() for bigger number
num5 is generaly "0123" + "4567" + "89AB", *7 and take lowest 4 nibbles/nipples of it.
num4 = num5.
sooo finaly.

unsigned long bla = ((rand()*rand()*rand()*rand())%429197)*10007;
unsigned long chk = ((0xCA00 + (bla >> 16) + bla & 0xFFFF)*7) & 0xFFFF;
printf ( "CA00%08X%04X", bla, chk );

any mistakes ?
r4g3
May 1st, 2004, 20:44
Quote:
// num1 gets loaded with the decimal equivalent of a 16 hex digits string
... and those shifts > 32

so yep disa, he surely doesnt know how to write "unsigned __int64"
oki gotta go sleep, cuz my keyboard aint no pillow ...
doug
May 1st, 2004, 20:59
I think r4g3 is correct.

yaa, this algorithm is short so there's not problem writing a set of equations ('constraints') in terms of the bits of num1 (64bits number)

num2=num1>>48
num2=0xCA00
num3=(num1)>>16
num3%10007 != 0 ; this is the same as writing num3= k*10007, (k is anything u want.)
num4=num1& 0xFFFF ; bits 0-15 of num1.
....

so lines 1 says: num2 is the high 16 bits of num1, line 2 completes by giving you that value: 0xCA00.
so you have Bits[48-63] = 0xCA00

num4 is bits 0-15 of num1.. this is compared to the final value of num5.

write out final equation:
num4 = num5
Bits[0-15] = WORD[ 0xCA00 + Bits[32-47] + Bits[16-31] ] *7
==>
Bits[0-15] = WORD[ 0xCA00 + High16[k*10007] + Low16[k*10007] ] *7

1. you choose k
2. you find Bits[0-15]
3. you concatenate the expression: Bits[48-63] Bits[47-32] Bits[16-31] Bits [0-15]

if you know how to solve simple systems of equations.. this algorithm shouldn't be a problem for you.

edit: when I write WORD[...] it means you take bits 0-15 and chop off the rest. Same for Low16. High16 meant to take bits 16-31 of a 32bits number.
disavowed
May 2nd, 2004, 12:45
Quote:
[Originally Posted by r4g3]so yep disa, he surely doesnt know how to write "unsigned __int64"
ahh.. i was wondering about that 48-bit shift