Need help reversing string-to-key routine [Archive]

View Full Version : Need help reversing string-to-key routine

philpem

December 31st, 2003, 16:12

Hi,
I'm currently trying to write my first "real" keygen. The algorithm - FWICT - takes the username, produces an intermediate code (i-code). Next, it generates another i-code based on the key (a 4-character Base 18 code) and compares the two i-codes. If both i-codes match, the key is considered to be valid.
Now - this is no real problem - I've converted the code to C and it works fine for code checking. What I'd like to do is convert the i-code from the username into the 4-character key. The code that generates the i-code for the key is as follows:

Code:



unsigned int StrToWord(char *inp)

{

  const char conversion[] = "BCDFGJKLMPQRSTVWXZ";

  char input[10];

  int loop;

  signed long r0;

  unsigned long r1, r5;

  char *pdest;



  strcpy(input, inp);

  r5 = 0;



  for (loop = 4; loop>0; loop--)

  {

    pdest = strchr(conversion, inp[loop-1]);

    r0 = pdest - conversion;

    r1 = (unsigned long) ((loop << 3) - loop);

    r0 = r0 - r1;

    while (r0 < 0) r0 += 0x12;



    r1 = r5 + (r5 << 3);

    r5 = r0 + (r1 << 1);

  }

  return (unsigned int)(r5 & 0xFFFF);

}

Can anyone tell me how I might be able to reverse this part of the algorithm into an "i-code to key" routine? Code would be nice, but I'd prefer some form of "OK, this does [x], so turn it into [y] because [z]" type text, i.e. a basic tutorial.
I suppose I could write a brute-force key generator, but I'm not too keen on that idea (the quickest way is not always the best - bruteforcers are too slow IMO).

Thanks.

mmk

January 1st, 2004, 02:42

First thing I noticed was that there's a bug in your loop. If the character inp[loop-1] is not in the set {BCDFGJKLMPQRSTVWXZ} strchr() will return NULL. This will make the i-code depend on the offset of conversion[] which is most likely not a thing you would want or each new compile of the keygen could generate different i-codes. I assume that was a bug and assume that inp only contains characters in conversion[].

First thing to do is to write the algorithm in the least amount of operations to make it easier to understand. The main loop has been re-written:

Code:

#define asc2bas18(c) indexof("BCD..", c) // Returns 0-17

  for (int i = 4; i > 0; i--)

    r5 = 18*r5 + ((asc2bas18(inp[i-1]) - i*7) % 18);

What this loop does is converting a 4-digit base 18 number in ASCII to binary in reverse order and subtracting each base 18 digit. Change base to 18 and you have a ASCII hex to bin (in reverse order with subtraction of each digit) conversion loop. Nothing special. Each base 18 digit occupies log2(18) ~= 4.17 bits, so 4 of them occupy 16.7 bits.

Assume that r5 = BQGZ(base18) & 0xffff. How do we reverse this? It's simple really. If you can write bin to base 16 ASCII then you can reverse this. Since your function ends with masking off the highest 16 bits, the last 0.7 bits can be anything, so assume they're zero.

Code:

for (int i = 1; i <= 4; i++)

{

  // We have r5 = 18*r5 + ((asc2bas18(inp[i-1]) - i*7) % 18) and want to get rid of 18*r5. Use modulo

  outp[i-1] = r5 % 18;

  // We have (asc2bas18(inp[i-1]) - i*7) % 18) and want to get rid of i*7

  outp[i-1] = (outp[i-1] + i*7) % 18;

  // We have asc2bas18(inp[i-1]) and want to get rid of asc2bas18()

  outp[i-1] = base18_to_ascii(outp[i-1]);

  r5 /= 18;

}

Hope this helps. It's possible that there's a small mistake someplace because I didn't check this code. Fixing the bugs is an exercise to the reader. :-)

And why do you even bother making such a small hash, and not even a particularly good one? Use MD5, SHA1 or some other real hash and no-one can reverse your password except by brute-force.

philpem

January 3rd, 2004, 16:12

Quote:

[Originally Posted by mmk]
The main loop has been re-written:

Code:
#define asc2bas18(c) indexof("BCD..", c) // Returns 0-17
for (int i = 4; i > 0; i--)
r5 = 18*r5 + ((asc2bas18(inp[i-1]) - i*7) % 18);

The logic looks good, but for some reason the code won't work. Maybe it's just my compiler being strange (what's new?)

Quote:

[Originally Posted by mmk]

Code:
for (int i = 1; i <= 4; i++)
{
// We have r5 = 18*r5 + ((asc2bas18(inp[i-1]) - i*7) % 18) and want to get rid of 18*r5. Use modulo
outp[i-1] = r5 % 18;
// We have (asc2bas18(inp[i-1]) - i*7) % 18) and want to get rid of i*7
outp[i-1] = (outp[i-1] + i*7) % 18;
// We have asc2bas18(inp[i-1]) and want to get rid of asc2bas18()
outp[i-1] = base18_to_ascii(outp[i-1]);
r5 /= 18;
}

Hope this helps. It's possible that there's a small mistake someplace because I didn't check this code. Fixing the bugs is an exercise to the reader. :-)

Wow - that works great - thanks, mmk

Quote:

[Originally Posted by mmk]
And why do you even bother making such a small hash, and not even a particularly good one? Use MD5, SHA1 or some other real hash and no-one can reverse your password except by brute-force.

This isn't from my code - I bought a computer program second-hand, but it had someone else's name on it. I just wanted it to have my name on it, as opposed to the previous owner's name. I contacted the author before doing this - he gave me the go-ahead and said something about losing the keygenerator and having to resurrect his computer.
Anyway, I've been using an SHA1 key with 1024-bit RSA crypto, with the result stored in a keyfile with plenty of checksums and redundant bytes (which aren't really redundant but are a total pig to calculate if you don't know the algorithm). Take a look at CDRWIN's protection - one of the checks fails and it writes bad CDRs - if another one fails, you get an antipiracy warning - etc.
Anyway - must go now - don't want to reveal too many of my secrets

Later.