Decode starcraft key (clean python & Lisp versions included)

[netytan]

I had the pleasure of porting the functions for decoding the starcraft key a while ago to Python to Lisp for anyone using these languages it could be handy so I'll post them here – I'm not sure that this is the right place for them however, if it's not could a kind mod please put them in the appropriate place.

There was a lot of redundancy in other versions of this function (which apparently were translated directly from ASM) which I have since removed so the code is much less convoluted. For anyone familiar with this function It's turns out that the whole of the first loop can be ignored entirely and the second loop can be replaced by the sequence: 8, 10, 4, 5, 7, 1, 11, 3, 9, 2, 0, 6

Both functions take a string of 13 numeric digits and return the appropriately decoded key string.

Python

Code Select Expand

def decodeStarcraftKey(key):
    arrayKey = list(key)
    n = 11
    v = 0x13AC9741
    for i in (8, 10, 4, 5, 7, 1, 11, 3, 9, 2, 0, 6):
        c = int(key[i])
        if c < 7:
            c = v & 0xFF & 7 ^ c
            v >>= 3
            print c
        else:
            c = n & 1 ^ c
            print c
        arrayKey[n] = c
        n = n - 1
    return ''.join(map(str, arrayKey))


Lisp (well commented )

Code Select Expand

(defun decode-helper (list v n rest)
  "This a helper function for use with decode-starcraft-key function below."
  (if (consp list)
    (let ((c (car list)))
      ;;; binds the first value of 'list to 'c if there are anymore items
      ;;; to be processed.
      (if (< c 7)
        ;;; Checks to see if 'c is less than 7 then calls decode-helper
    ;;; recursively on 'list to collect the new values of 'c in 'rest.
        (decode-helper (cdr list)
                       (ash v -3)
               (- n 1)
               (cons (digit-char (logxor (logand v 7) c))
                 rest))

        ;;; Else if 'c is more than 7 call decode-helper recursively on the
        ;;; the character list and collects the new value of 'c in 'rest.
        (decode-helper (cdr list)
               v
               (- n 1)
               (cons (digit-char (logxor (logand n 1) c))
                 rest))))
                 
    ;; Returns the accumulated values calculated above in reverse order.
    (reverse rest)))

(defun decode-starcraft-key (key)
  "This function decodes a 13 digit key for starcraft game on battle.net"
  (concatenate 'string (reverse
      (cons
          (char key 12)    ; Adds the last character of key onto the end.
          (decode-helper
              ;; Produces a list of numbers from 'key using the positions
              ;; passed to map.
              (mapcar (lambda (i) (digit-char-p (char key i)))
                  '(8 10 4 5 7 1 11 3 9 2 0 6))
               #X13AC9741 11 ())))))


To illustrate this compare the Python above to a previous Python version I found based directly on the C:

Code Select Expand

def DecodeStarcraftKey(key):
   arrayKey = list(key)
   v = 3
   for i in range(12):
       n = int(arrayKey[i])
       n ^= (v * 2)
       v += n
   v = 194
   for i in range(11, -1, -1):
       if(v < 7):
           break
       c = arrayKey[i]
       n = v % 12
       v -= 17
       arrayKey[i] = arrayKey[n]
       arrayKey[n] = c
   v = 0x13AC9741
   for i in range(11, -1, -1):
       c = arrayKey[i]
       if(ord(c) < 55):
           c2 = v & 0xFF
           c2 &= 7
           c2 ^= int(c)
           v >>= 3
           arrayKey[i] = c2
       elif(ord(c) < 65):
           c2 = i
           c2 &= 1
           c2 ^= int(c)
           arrayKey[i] = c2
   return ''.join(map(str, arrayKey))

I hope this is of some use to someone out there, if only as a template for cleaning up other versions of the code; god forbid there are other similarly messy translations of other battle.net stuff out there.


Take care,

Mark.

[Zakath]

Very nice. Always good to see people experimenting with new ways to do things.

[Banana fanna fo fanna]

...or pushing a hidden Lisp agenda!

[netytan]

...or pushing a hidden Lisp agenda!

Or just sharing high quality code banana . So some of that code is Lisp. If you don't wana use it don't .

[shout]

For the sake of comparison, I will share my C++ code. Note this hasnt been tested before. I kinda cleaned it up from the C version netytan was talking about.

h file:

Code Select Expand


#pragma once

class sckey
{
public:
sckey(PCSTR key);
~sckey(void);
DWORD getPublic();
DWORD getPrivate();
DWORD getProduct();
private:
inline void swap(DWORD a, DWORD b);
inline void shuffle();
inline void final();

PSTR key;
};


cpp file:

Code Select Expand


#include "windows.h"
#include ".\sckey.h"

sckey::sckey(PCSTR cdkey)
{
if (strlen(cdkey) != 13)
//do error stuff
this->key = (PSTR)malloc(strlen(cdkey));
memset(this->key, 0, strlen(cdkey));
memcpy(this->key, cdkey, strlen(cdkey));
shuffle();
final();
}

DWORD sckey::getPrivate()
{
DWORD p = 0;
PCHAR t = (PCHAR)malloc(10);
memset(t, 0, 10);
memcpy(t, &key[2], 7);
sscanf(t, "%u", &p);
free(t);
return p;
}

DWORD sckey::getProduct()
{
DWORD p = 0;
PCHAR t = (PCHAR)malloc(10);
memset(t, 0, 10);
memcpy(t, &key[9], 2);
sscanf(t, "u%", &p);
free(t);
return p;
}

DWORD sckey::getPublic()
{
DWORD p = 0;
PCHAR t = (PCHAR)malloc(10);
memset(t, 0, 10);
memcpy(t, key, 2);
sscanf(t, "%u", &p);
free(t);
return p;
}

sckey::~sckey(void)
{
free(this->key);
}

inline void sckey::swap(DWORD a, DWORD b)
{
CHAR t = this->key[a];
this->key[a] = this->key[b];
this->key[b] = t;
}

inline void sckey::shuffle()
{
DWORD pos = 0x0B;

for (DWORD i = 0xC2; i >= 7; i -= 0x11)
this->swap(pos--, i % 0x0C);
}

inline void sckey::final()
{
DWORD hash = 0x13AC9741;
for (int i = 0; i < 11; i++) {
BYTE t = key[i];
if (key[i] <= '7') {
t = (BYTE)(hash & 7 ^ key[i]);
hash >>= 3;
}
else if (key[i] <= 'A')
t = i & 1 ^ this->key[i];
key[i] = t;
}
}


[MyndFyre]

Has anyone done any independent testing on this?  ($t0rm?  You're a Python geek)

[netytan]

Not to be offensive to the venerable Shout but can i cite this as an argument against OO . If your talking about my code then I don't know but Yegg tested them – personally I know nothing about this Battle.Net thing but code above works perfectly from what I've been told, and removed a lot of arbitrary computation*.

Take care,

Mark.

*With a set of constants the application of a function/operator will result in the same results; this enables you to remove the computation from the program and replace if with those constants.

[MyndFyre]

*With a set of constants the application of a function/operator will result in the same results; this enables you to remove the computation from the program and replace if with those constants.

That's true, but we preserve handling code for '/' and '^' in CheckRevision code now "just in case" Battle.net decides one day to use those operators.  Typically the same strategy is used in these kinds of cases; constants can get outdated.  Algorithms, however, generally stay the same, even across versions.

[netytan]

*With a set of constants the application of a function/operator will result in the same results; this enables you to remove the computation from the program and replace if with those constants.

That's true, but we preserve handling code for '/' and '^' in CheckRevision code now "just in case" Battle.net decides one day to use those operators.  Typically the same strategy is used in these kinds of cases; constants can get outdated.  Algorithms, however, generally stay the same, even across versions.

Not so, you can't change the constants without changing the algorithm because their values are determined by it. The fact this part of the algorithm generated a constant access order means we can remove the computation completely there-by giving the computer less work to do.

If the algorithm were to change then it would yield the wrong results regardless of if you used constants or used the current algorithm to generate them each time – thats just how it works, you have to role with the punches. Write good code now and if it changes write good code again. Leaving things open incase one day things do change means you'll never have anywhere near optimal code .

Maybe I misunderstood.

Ah well, take care mynd .

Mark.

[shout]

Not to be offensive to the venerable Shout but can i cite this as an argument against OO

How could you use this as an argument against OO? This is an alpha version of the code--freshly coded, all I know is that it compiles. I don't know if it runs through without crashing.

If I were to do this in C, I would need have a pointer to the key being modified for each of the functions, which would have to be kept track of by whoever uses it. I also think it is cleaner than having tons of pointers to basic types floating around in my code.

I know the getP* functions are not ideal, ATM I don't care.

Is the trade from 'arbitrary' to address computations really all that bad? We need side-by-side comparisons for this.

EDIT:

I did some testing on this.

Output from testing.exe:

Code Select Expand


OLD METHOD
Calculating key 1 time...
Calculatiion took 0 tick(s).
Calculating key 1000000 times...
Calculation took 1311 tick(s).
NEW METHOD
Calculating key 1 time...
Calculation took 0 ticks(s).
Calculating key 1000000 times...
Calculation took 1591 tick(s).
Calculations complete.


More runs of testing.exe:

Code Select Expand


OLD  NEW
1345 1672
1296 1734
1265 1671
1624 2137
1344 1718
1407 1705


Here is the decoding code I used:

Code Select Expand


void calculate(PSTR key)
{
DWORD hash = 0x13AC9741;
DWORD index[] = {8, 10, 4, 5, 7, 1, 11, 3, 9, 2, 0, 6};
for (int i = 0; i < 11; i++)
{
BYTE t = key[index[i]];
if (key[i] <= '7') {
t = (BYTE)(hash & 7 ^ key[index[i]]);
hash >>= 3;
}
else if (key[i] <= 'A')
t = i & 1 ^ key[index[i]];
key[index[i]] = t;
}
}

inline void swap(PSTR key, DWORD a, DWORD b)
{
CHAR t = key[a];
key[a] = key[b];
key[b] = t;
}

void shuffle(PSTR key)
{
DWORD pos = 0x0B;

for (DWORD i = 0xC2; i > 7; i -= 0x11)
swap(key, pos--, i % 0x0C);
}

void final(PSTR key)
{
DWORD hash = 0x13AC9741;
for (int i = 0; i < 11; i++) {
BYTE t = key[i];
if (key[i] <= '7') {
t = (BYTE)(hash & 7 ^ key[i]);
hash >>= 3;
}
else if (key[i] <= 'A')
t = i & 1 ^ key[i];
key[i] = t;
}
}


The old way is marginally faster and uses marginally less memory. The new one is much cleaner. I would say it depends on your style of coding for this particular bit.

[UserLoser]

Code Select Expand


void DecodeNumericCdKey(const char *CdKey, DWORD *pProduct, DWORD *pPublic, DWORD *pPrivate)
{
char *CopyCdKey = new char[strlen(CdKey)+1]; strcpy(CopyCdKey, CdKey);
unsigned int ScrambleTable[] = { 8, 10, 4, 5, 7, 1, 11, 3, 9, 2, 0, 6 };
unsigned int KeyPos = (sizeof(ScrambleTable) / 4) - 1;
DWORD HashKey = 0x13AC9741;
char KeyVal = 0;

for(unsigned int i = 0; i < (sizeof(ScrambleTable) / 4); i++) {
KeyVal = CdKey[ScrambleTable[i]];
if(KeyVal <= '7') {
KeyVal = HashKey & 7 ^ KeyVal;
HashKey >>= 3;
} else
KeyVal = KeyPos & 1 ^ KeyVal;
CopyCdKey[KeyPos] = KeyVal;
KeyPos--;
}

// Need to replace sscanf
sscanf(CopyCdKey, "%2d%7d%3d", pProduct, pPublic, pPrivate);

delete []CopyCdKey;
}


Question:  best method to replace sscanf?

[MyndFyre]

Question:  best method to replace sscanf?

From what I've heard, you're actually okay calling sscanf as long as you run a sanity check on your string (and you don't let the user decide the format string, which isn't a problem in this case). 

[netytan]

Since this thread one and the redirect may diverge in the listings at a later date I thought it prudent to post the link to what else was said here. It's been moved to an off subject forum and does diverge from the original topic so may not be what your looking for (still I don't agree with it's placement).

http://forum.valhallalegends.com/index.php?topic=14222.0

Mark.

[UserLoser]

Btw to whoever:

Code Select Expand


CHAR t = this->key[a];
this->key[a] = this->key[b];
this->key[b] = t;


Little trick:

Code Select Expand


    this->key[a] ^= this->key[b] ^= this->key[a] ^= this->key[b];