Thursday, August 21, 2008

Jim~ SpaghettiMe Dissected...:P

Ah! finally the wait is over my tut for Jim~'s SpaghettiMe is finally published; one of the trickiest crackmes i ever faced. A brief over view of the recursion that is used to calculate the serial and how to reverse it.

private int[] overloaded(int[] chr)
{
if (chr.Length <= 1) { return chr;
}
int num = chr[chr.Length - 1];
int[] numArray = new int[chr.Length - 1];
for (int i = 0; i < (chr.Length - 1); i++)
{
numArray[i] = (num + chr[i]) % 0xff;
}
return this.overloaded(numArray);
}

Ok what this function does is that it compresses the int array that it recieves by one element and finally returns a value when the array length becomes == 1. This can be better explained with an example:
suppose that an array of 4 elements is passed onto the function then
array[4]{103,8,6,8} //array[4] refers to an array of 4 elements similarly array[3] an array with 3 elements
array[3] after recursion will be
array[3]{(103+8),(8+8),(6+8)) ==== {111,16,14}
array[2]{(111+14),(16+14)} ==== {125,30}
and finally
array[1]{125+30} ==== {155}
Thus this value that is returned sd be equal to that generated from name.

To reverse it we can simply create an array of 2 elements and keep on expanding it till it becomes 30 elements long. Now one might ask why 30 elements :P this is simply bcoz the seiral is 40 chars long and a base 64 string 40 chars long has a byte array of 30 elements. Now the first element of the array is the one that is calculated from the name and the other is 255. why 255 bcoz the compression is carried out this way suppose if 155 is calculated from name then our initialised array will be array[2]{155,255} which when compressed according to the code numArray[i] = (num + chr[i]) % 0xff; will be (155+255)%255 = 155 simple aint it. So the code that serves our purpose is

private int[] overload(int[] chr)
{
int num;
Random random = new Random();
if (chr.Length >= 30)
{
return chr;
}
int maxValue = chr[chr.Length - 1];
maxValue = random.Next(1, maxValue);
int[] numArray = new int[chr.Length + 1];
numArray[chr.Length] = maxValue;
for (num = 0; num < chr.Length; num++)
{
numArray[num] = ((0xff + chr[num]) - maxValue) % 0xff;
}
return this.overload(numArray);
}
the random number is used to subtarct it from the existing elements of the array and to include it as the incremented element of the new array. 0xff is added so as to avoid -ve numbers.

Now to look at the recursion that is used to calculate the necessary number from name


private int overloaded(int num)
{
if (num > 0)
{
if ((num % 2) == 0)
{
return (3 + this.overloaded((int) (num - 1)));
}
return (this.overloaded((int) (num - 1)) - 2);
}
if (num >= 0)
{
return 0x539;
}
if ((num % 2) == 0)
{
return (3 + this.overloaded((int) (num + 1)));
}
return (this.overloaded((int) (num + 1)) - 2);
}
Of course its not easy to understand what goes on inside this recursion. An easy way to understand it wd be to rip this code and try to see the result by passing different numbers to it.

A table to show what happens when i passed some numbers to it:

0 == 1337

1 == 1335

2 == 1338

3 == 1336

4 == 1339

5 == 1337

this much was enough for me to understand what was happening. For even numbers it was returning (num/2)+1337 and for odd numbers it was returning ((num-1)/2)+1335. The same was also true for -ve numbers. So this can easily be done with the following code:


private int overloadedint(int num)
{
if (num > 0)
{
if (num == 0)
{
return 0x539;
}
if ((num % 2) == 0)
{
return ((num / 2) + 0x539);
}
return (((num - 1) / 2) + 0x537);
}
num *= -1;
if (num == 0)
{
return 0x539;
}
if ((num % 2) == 0)
{
return ((num / 2) + 0x539);
}
return (((num - 1) / 2) + 0x537);
}
Hu? So i guess over all it was a very interesrting crackme. I look forward to seeing some more such crackmes from Jim~ n also that i will be writing some crackmes in the same line.....

No comments: