13 January 2008

Starcraft CD-key algorithm explained


Fig. 1 - Invalid key


Fig. 2 - Valid key


Fig. 3 - Success!

Requirements:
1. Ollydbg
2. Starcraft CD v1.0
3. Knowledge of x86 assembly langauage and hexadecimal


I began by opening the INSTALL.EXE with Ollydbg (it took some time because of the size of the file). After setting some breakpoints and tracing through the code I eventually found the algorithm.
Here is the code with comments:

0040F8DE | >B8 03000000 MOV EAX,3
0040F8E3 | .33D2 XOR EDX,EDX

0040F8E5 |> 8A0C32 /MOV CL,BYTE PTR DS:[EDX+ESI]; Take left most unprocessed number.
0040F8E8 |. 80F9 30 |CMP CL,30; Checks if inputted character is a number
0040F8EB |. 7C 53 |JL SHORT INSTALL.0040F940; if not then give error message.
0040F8ED |. 80F9 39 |CMP CL,39
0040F8F0 |. 7F 4E |JG SHORT INSTALL.0040F940; Same as above.
0040F8F2 |. 0FBEC9 |MOVSX ECX,CL; Stores the number in ECX in hexadecimal.
0040F8F5 |. 8D3C00 |LEA EDI,DWORD PTR DS:[EAX+EAX]
0040F8F8 |. 83E9 30 |SUB ECX,30; Converts the number to decimal.
0040F8FB |. 33F9 |XOR EDI,ECX
0040F8FD |. 03C7 |ADD EAX,EDI
0040F8FF |. 42 |INC EDX
0040F900 |. 83FA 0C |CMP EDX,0C; Is EDX=12?
0040F903 |.^72 E0 \JB SHORT INSTALL.0040F8E5; Keep on doing this for the 12 numbers.
0040F905 |. 33D2 XOR EDX,EDX; EDX=0
0040F907 |. B9 0A000000 MOV ECX,0A; ECX=10
0040F90C |. F7F1 DIV ECX; EAX is divided by ECX and the remainder is put into DL.
0040F90E |. 0FBE46 0C MOVSX EAX,BYTE PTR DS:[ESI+C]; EAX=last number of CD-key
0040F912 |. 0FBED2 MOVSX EDX,DL; EDX=whatever DL was
0040F915 |. 83C2 30 ADD EDX,30; This converts the number in EDX into hex.
0040F918 |. 3BC2 CMP EAX,EDX; Is EAX=EDX?
0040F91A |. 74 1C JE SHORT INSTALL.0040F938; Go here if CD-key is valid.
0040F91C |. 8B4C24 10 MOV ECX,DWORD PTR SS:[ESP+10]
0040F920 |. 51 PUSH ECX
0040F921 |. 68 59020000 PUSH 259
0040F926 |. 68 58020000 PUSH 258
0040F92B |. E8 A034FFFF CALL INSTALL.00402DD0


Example: Determine X to make 1111-11111-111X a valid key?
EAX0=3
ECXn= nth digit of serial number
EDI
n=(EAXn-1 * 2) XOR ECXn
EAXn=EDIn + EAXn-1
n=1 EDI1=7, EAX1=A
n=2 EDI2=15, EAX2=1F
. . .
n=12 EDI12=12EBDD, EAX12=1C61CB
1C61CB (hex) = 1860043 (decimal). Divide by A (hex) or 10 (decimal)and the remainder is 3. So X=3. Valid key is 1111-11111-1113


Discussion:
Fortunately, the file is not packed (I am in the process of learning how to unpack). This program is an example of when serial fishing does not work. The key is 13 digits long (formatted as: XXXX-XXXXX-XXXX) with the first 12 digits starting from the left being used to determine the 13th digit. If the 13th digit is correct then installation proceeds else there is an error message. If one where to "lose" the CD-key, then it is possible to randomly put in the first 12 digits while trying all digits 0 through 9 for the 13th one.
For example:
1234-56789-1231 - incorrect!
1234-56789-1232 - incorrect!
1234-56789-1233 - incorrect!
1234-56789-1234 - correct! (this one is floating around on the Internet)
The algorithm is quite simple and I was able to calculate a valid key with nothing more than a piece of paper, pen, and trusty TI-36X Solar calculator. Sadly, I don't have much experience in programming or know any language like C++ but I bet someone reading this can quickly code a keygen.

UPDATE - 08JUNE2008
I took an introductory class on C++ programming but I am too tired at the moment to think of the a keygen code, instead I'll post the code in TI-89 BASIC which will ask you for the first 12 digits.

Draft
sckeygen()
Prgm
3->eax
0->edx
Request "serial: ", s
s->g
Lbl top
expr(left(g,1))->ecx
shift(g,1)->g
eax*2 xor ecx->edi
eax+edi->eax
edx+1->edx
If edx=12 Then
remain(eax,10)->a
Disp expr(s)*string(a)
Else
Goto top
EndIf
EndPrgm

The above keygen has some rough edges that still need to be smoothed out. The one below will randomly generate digits 1 through 12.

FINAL
sckeygen()
Prgm
3->eax
0->edx
""->s
For i,1,12
string(remain(rand(10),10))-&s>s
EndFor
s->g
Lbl top
expr(left(g,1))->ecx
shift(g,1)->g
eax*2 xor ecx->edi
eax+edi->eax
edx+1->edx
If edx=12 Then
remain(eax,10)->a
Disp mid(s,1,4)&"-"&mid(s,5,5)&"-"&mid(s,10,3)&string(a)
Else
Goto top
EndIf
EndPrgm


C++ Source code



// SC_keygen.cpp : main project file.

#include "stdafx.h"
#include <iostream>

#include <iso646.h>
#include <stdlib.h>
#include <ctime>
#include <vector>
using namespace std;

void
generate(vector<int>& s, int& x, int& d)
{


//Stores random digits 0-9 in a vector
for (int i = 0; i < 12; i++)
{


s[i] = rand() % 10;
}


//Main algorithm
for(int i = 0; i < 12; i++)
{


d = (2 * x) xor s[i];

x = x + d;
}

x = x % 10;

for
(int i = 0; i < 12; i++)
{


if
(i==4)
{

cout << '-' << s[i];
}


else if
(i==9)
{

cout << '-' << s[i];
}


else
cout<<s[i];
}

cout << x;
x=3;

d=0;
}

int
main()
{

srand(static_cast<int>(time(0)));

vector<int> serial(12);
int
eax = 3;

int
edi = 0;
int
a;
bool
no_quit = true;


cout << "Starcraft CD keygen\n";
generate(serial,eax,edi);

do

{

cout << "\nGenerate another one? (yes=1/no=0)";
cin >> a;

if
(a==1) generate(serial,eax,edi);

else
no_quit=false;
}

while
(no_quit);
return
0;
}


2 comments:

Snoopy said...

i've written the keygen in javascript, and you should do it 'cause is fast and not need big stuff to compile.

There is:

//Algorithm found by TAKINGSOFTWAREAPART
//javascript code by Snoopyhack
var x = 3;
var c = 0;
var keyString = '';
while(c < 12){
var ran = Math.floor(Math.random()*10);
x += (2 * x) ^ ran;
if((c == 4) || (c == 9)){
keyString += '-';
}
keyString += ran;
c++;
}
x = x % 10;
keyString += x;
document.write(keyString);

mishapsconundrum said...

I know this is a rather old post, but im extremely intrested in a compiled version