The Cracking of MasterKey v1.02/1.05

by

CASIMIR

Parts C & D

Caz presents : the Cracking of MasterKey v1.02/1.05 by Ph. MELLERET

Table of contents:

Abstract
What do i need?
Target's description

PART A. REVERSING OF MASTERKEY
     A1. Input handling
     A2. Building of K1
     A3. Building of K2
     A4. Building of K3
     A5. Final cmp
     A6. Monitoring Registry 

PART B. BREAKING OF MASTERKEY
     B1. General constraints
     B2. Splitting
         B21. Validity of splits
         B22. Sorting splits
     B3. Isolated column(s)
     B4. Modulo (K2 -> K3)
     B5. Solving method
         B51. Exhaustive search
         B52. Optimization and main algorithm
         B53. Password check

PART C. BATCH FILE FOR REGISTRY'S KEY EXPORT

PART D. 'C' SOURCE FOR CRACKER

PART C. BATCH FILE FOR REGISTRY'S KEY EXPORT

This MS-DOS batch exports encrypted password from Registry, then it launches the Cracker. ********************************************************************************

@echo off

echo.
echo *********** MasterKey encryption cracker by Casimir ***********
echo This batch file extracts MasterKey encrypted key from Registry.
echo The key is stored in file crkmstrk.txt under current directory.
echo Then cracker crkmstrk.exe is launched in order to decrypt key.
echo. 

@regedit /E crkmstrk.txt "HKEY_USERS\.Default\Software\Kruptos Solutions\MkStarter\Security"
if not exist crkmstrk.txt goto bug
crkmstrk.exe
goto done

:bug
echo.
echo WARNING : encrypted key not found in Registry !!!
echo Search string "MkStarter" in Registry,  
echo then edit key's location (regedit /E crkmstrk.txt "xxxxxx") in this file.
echo.

:done
echo done
********************************************************************************


PART D. 'C' SOURCE FOR CRACKER

Once compiled, this C source (crkmstrk.cpp) produces a MS-DOS executable (crkmstrk.exe). Enjoy!

********************************************************************************
#include <stdio.h>
#include <math.h>
#include <io.h>
#include <stdlib.h>
#include <conio.h>
#include <fcntl.h>
#include <string.h>
#include <alloc.h>
#include <dos.h>
#include <errno.h>
#include <time.h>

/****************************************************************************/
/********************************* GLOBALS **********************************/
/****************************************************************************/

int pwd_len;             //password's length
const int pwd_len_min=5;
const int pwd_len_max=10;
const int char_min=0x20; //SPACE
const int char_max=0x7F; //
int exh_search=0;        //0 => do not perform exhaustive search , 1 => do it

int *tmp_orig,*tmp_dest;


//structure for splits
struct split_struct {
       int K1[3][4];    //K1[0][0]=K1oe_n0, K1[0][1]=K1oe_n1...K1[2][3]=K1e_n3
       int isolated[4]; //isolated[i]=1 => isolated column i
       int valid;       //0 => invalid split , 1 => valid split
       int size_K1[3];  //size_K1[0/1/2]=number of not-null K1oe_ni/K1o_ni/k1e_ni
       int size_split;  //size_split=(size_K1[0]+size_K1[1]+size_K1[2])
       };

struct split_struct *split;

//structure for system to solve
struct sys_struct {
       //Password sub-structure
       int PWD_nb;         //number of characters in password
       int PWD_fixed_nb;   //number of characters fixed
       int PWD_fixed[pwd_len_max];     //which characters are fixed...
       int PWD_fixed_val[pwd_len_max]; //...with which values
       int PWD_found_nb;   //number of characters found (fixed+computed)
       int PWD_found[pwd_len_max];     //which characters are found...
       int PWD_found_val[pwd_len_max]; //...with which values

       //K1oe = K1o + K1e
       int K1_found[3]; //K1_found[0/1/2]=1/1/1 if K1oe/K1o/K1e found
       unsigned long K1_found_val[3]; //values of K1oe/K1o/K1e

       //3 squared sums
       int PWD_SQ_nb[3]; //PWD_SQ_nb[0/1/2]=nb of odd+even/odd/even chars
       int PWD_SQ[3][pwd_len_max]; //PWD_SQ[0/1/2]=01234.../13.../24...
       int PWD_SQ_found_nb[3]; //number of characters found (fixed+computed)
       int PWD_SQ_found[3][pwd_len_max];     //which characters are found...
       int PWD_SQ_found_val[3][pwd_len_max]; //...with which values

       //9 (12) "line" equations    [K1oe/K1o/K1e][lin 0/1/2]
       int LIN_pos_nz_lin[3][3]; //positions of not-null equations in
				 // K1oe/K1o/K1e
       int LIN_nz_lin[3][3];     //list of not-null equations
       int LIN_nz_nb[3];     //number of not-null equations
       int LIN_nz_pwd[3][3]; //list of PWD's chars from not-null equation(s)
			     //char(s) from null equation(s) are not listed
       int LIN_found_nb[3];  //number of equation(s) solved
       int LIN_found[3][3];  //which PWD's characters are found...
       int LIN_pwd_found_val[3][3]; //...with which values
       int LIN_K1_found_val[3][3];  //values found for K1oe_bi/K1o_bi/K1e_bi

       //3 (4) "column" equations [col 0/1/2][K1oe/K1o/K1e]
       int COL_pos_nz_col[3][3]; //positions of not-null K1oe_bi/K1o_bi/K1e_bi
			         //in columns 0/1/2
       int COL_nz_nb[3]; //number of not-null K1oe_bi/K1o_bi/K1e_bi in cols
       int COL_nz_pwd[3][3]; //list of PWD's chars for each column
       int COL_found_nb[3]; //number of K1oe_bi/K1o_bi/K1e_bi found in cols
       int COL_found[3][3]; //which PWD's characters are found...
       int COL_pwd_found_val[3][3]; //...with which values
       int COL_K1_found_val[3][3];  //values found for K1oe_bi/K1o_bi/K1e_bi
       int COL_split[3][3]; //current split display by [col 0/1/2][lin 0/1/2]
       int COL_lin[3][3];

       } sys;

int K3_len;
int *K3;
int *K2_str_min,*K2_str;
int K2[3][3];
int split_order[6*6*6]; //order in which we try splits
//FILE *logfile;

/****************************************************************************/
/******************************** PROTOTYPES ********************************/
/****************************************************************************/

int Carry_left(int,int [4],int [4]);
int Carry_right(int,int [4]);
void Fill_split(int,int,unsigned *);
void Fill_size(int);
void Stats(int);
void Select_split(int);
void Fill_pwd_ext(int,int,int **);
void Copy_found(int);
void Init_system(int,int *);
void Update_system(int);
int Progress(int);
void Fill_dependency(int);
int Next_shift(int,int *,int **);
int Next_order(int,int **,int *,int **);
void Calc_K1(int,int,int,int);
void Calc_PWD_SQ(int,int);
void Calc_LIN_K1_found_val(int,int,int,int);
void Calc_LIN_pwd_found_val(int,int,int);
void Calc_COL_K1_found_val(int,int,int,int,int);
void Calc_COL_pwd_found_val(int,int,int);
int Next_fixed_val(int,int **);
void Init_K2(int,int);
int Next_K2(int,int);
int Check_pwd(int,int);
void Hi_folks(void);
void Wait_keyboard(void);
void Print_pwd(int,int *);
void Read_key(int,int *,int **);
int Open_key_file(char *);
void Order_split(int,const int,int *,int *);

/****************************************************************************/
/********************************* MAIN *************************************/
/****************************************************************************/

void main()
{
int i,j,k,l,z,hit,split_o;
int cur_split; //current split
int pwd_found; //1=>pwd found    0=>pwd not found
int fixed_nb;  //number of pwd's char(s) we need to fix in order to solve
	       //the system (the lower the better)
int best_fixed_nb; //lowest number
int best_sys_found; //1=>we found a system with best_fixed_nb=1
const int pwd_ext_len=12;   // 3 sub-keys of 4 bytes each
const int nb_combi=6;
const int nb_combi_bits=nb_combi*4;
const int nb_split=(nb_combi*nb_combi*nb_combi);
int nb_split_ok;
int fn; //file handle
//time_t time_start; // chrono

char *key_file="crkmstrk.txt";

unsigned combi[nb_combi_bits]={0,1,0,0,
			       1,1,0,0,
			       0,0,1,0,
			       1,0,1,0,
			       0,1,1,0,
			       1,1,1,0};


int *pwd_ext;
int *order,*fixed_order,*fixed_val;
int *shift_max,*shift_cur;


tmp_orig=(int *)malloc(sizeof(int)*pwd_len_max);
tmp_dest=(int *)malloc(sizeof(int)*pwd_len_max);

pwd_ext=(int *)malloc(sizeof(int)*pwd_ext_len);
order=(int *)malloc(sizeof(int)*pwd_len_max);
fixed_order=(int *)malloc(sizeof(int)*pwd_len_max);
fixed_val=(int *)malloc(sizeof(int)*pwd_len_max);
shift_max=(int *)malloc(sizeof(int)*pwd_len_max);
shift_cur=(int *)malloc(sizeof(int)*pwd_len_max);

K3=(int *)malloc(sizeof(int)*9);
K2_str_min=(int *)malloc(sizeof(int)*9);
K2_str=(int *)malloc(sizeof(int)*9);

split=(struct split_struct *)malloc(sizeof(split_struct)*nb_split);


Hi_folks();

//open key file from Registry
fn=Open_key_file(key_file);

//read encrypted key from file
Read_key(fn,&K3_len,&K3);

//log file
//logfile=fopen("crkmstrk.log", "w+");

//create splits
Fill_split(nb_split,nb_combi,combi);

//select valid splits
Select_split(nb_split);

//compute splits' sizes
Fill_size(nb_split);

//compute splits' dependency
Fill_dependency(nb_split);

//order splits
Order_split(K3_len,nb_split,&nb_split_ok,split_order);


/***********   MAIN LOOP   ***********/
//time_start=time(NULL); //start chrono
//each split
for(split_o=0;split_o<nb_split_ok;split_o++)
 {
 cur_split=split_order[split_o];
 printf("\nsplit %3d of %3d ",split_o+1,nb_split_ok);
 //fprintf(logfile,"\nsplit %3d of %3d ",split_o+1,nb_split_ok);
 //fflush(logfile);
 //printf("[[%3.0lfs]]",difftime(time(NULL),time_start));
 //fprintf(logfile,"[[%3.0lfs]]",difftime(time(NULL),time_start));
 //fflush(logfile);
 //each pwd_len
 for(pwd_len=pwd_len_min;pwd_len<=pwd_len_max;pwd_len++)
  {
  printf(".");
  //fprintf(logfile,".");
  //fflush(logfile);
  //printf("[%3.0lfs]",difftime(time(NULL),time_start));
  //fprintf(logfile,"[%3.0lfs]",difftime(time(NULL),time_start));
  //fflush(logfile);
  Fill_pwd_ext(pwd_len,pwd_ext_len,&pwd_ext);

  //init order
  for(i=0;i<pwd_len;i++) order[i]=i;

  //init shift
  for(i=0,j=(pwd_len-1);i<pwd_len;i++,j--) {shift_max[i]=j; shift_cur[i]=0;}

  best_sys_found=0;
  best_fixed_nb=pwd_len;

  do
   {//each order
   Init_system(cur_split,pwd_ext);
   pwd_found=0;
   do
    {//each P[i]
    for(j=0;j<pwd_len;j++)
     {//look for a still unknown P[i], and fix it
     i=order[j];
     if(!sys.PWD_found[i])
      {
      sys.PWD_fixed[i]=1; sys.PWD_fixed_nb++;
      sys.PWD_found[i]=1; sys.PWD_found_nb++;
      break;
      }
     }

    do
     {
     Copy_found(cur_split);
     Update_system(cur_split);
     } while(Progress(cur_split)); //loop until no more P[i] found

    if(sys.PWD_found_nb==sys.PWD_nb) pwd_found=1;
    } while(!pwd_found);
   fixed_nb=sys.PWD_fixed_nb;
   if(fixed_nb<best_fixed_nb)
    {//keep this order
    best_fixed_nb=fixed_nb;
    for(k=0,l=0;k<pwd_len;k++)
     {
     if(sys.PWD_fixed[k]) {fixed_order[l]=k; l++;}
     }
    if(best_fixed_nb==1) best_sys_found=1;
    }
   } while((!best_sys_found) &&
	   (!Next_order(pwd_len,&order,shift_max,&shift_cur)));

  //now we solve best system found
  exh_search=1;

  //each combi of K2
  Init_K2(K3_len,cur_split);
  do
   {
   for(i=0;i<best_fixed_nb;i++) {fixed_val[i]=char_min;}
   pwd_found=0;
   do
    {
    Init_system(cur_split,pwd_ext);
    for(i=0;i<best_fixed_nb;i++)
     {
     j=fixed_order[i];
     sys.PWD_fixed_val[j]=fixed_val[i];
     sys.PWD_fixed[j]=1; sys.PWD_fixed_nb++;
     sys.PWD_found[j]=1; sys.PWD_found_nb++;
     sys.PWD_found_val[j]=sys.PWD_fixed_val[j];
     }
    do
     {
     Copy_found(cur_split);
     Update_system(cur_split);
     } while(Progress(cur_split)); //loop until no more P[i] found
    //tests
    if(Check_pwd(pwd_len,cur_split)) Print_pwd(pwd_len,sys.PWD_found_val);

    } while((!pwd_found) && (Next_fixed_val(best_fixed_nb,&fixed_val)));
   } while(Next_K2(K3_len,cur_split));

  }//each pwd_len
 }//each split
}

/****************************************************************************/
/******************************* FUNCTIONS **********************************/
/****************************************************************************/

/****************************************************************************/
/* Check if password found is the good one                                  */
/* return 1 if password OK, else return 0                                   */
int Check_pwd(int pwd_len,int cur_split)
{
int i,j,k,l;
unsigned long tmp,coef,sub_key[3],sub_key_coef[3][3];

//compute K1oe, K1o and K1e
for(i=0;i<3;i++)
   {
   sub_key[i]=0;
   for(j=0;j<sys.PWD_SQ_nb[i];j++)
      {
      k=sys.PWD_SQ[i][j];
      tmp=sys.PWD_found_val[k];
      tmp*=tmp;
      sub_key[i]+=tmp;
      }
   }

//we must have: P[i] + K1oe_bi = K2oe_bi  (ditto K1o and K1e)
for(i=0;i<3;i++)
   {
   for(j=0,l=0;j<3;j++)
      {
      if(split[cur_split].K1[i][j])
	 {
	 coef=sub_key[i];
	 coef=coef << (24-(j*8));
	 coef=coef >> 24;
	 sub_key_coef[i][j]=coef;
	 k=sys.LIN_nz_pwd[i][l];
	 tmp=(sys.PWD_found_val[k]+sub_key_coef[i][j]);
	 if((tmp!=K2[i][l]) && (tmp!=(K2[i][l]+0x100))) return(0); //no good
	 l++;
	 }
      }
   }

//we must have: K1oe = K1o + K1e
if(sub_key[0]!=(sub_key[1]+sub_key[2])) return(0); //no good

//we must have PWD's ASCII characters between 0x20 (Space) and 0x7F ()
for(i=0;i<pwd_len;i++)
   {
   if((sys.PWD_found_val[i]<0x20) ||
      (sys.PWD_found_val[i]>0x7F))   return(0); //no good
   }

return(1); //ok
}

/****************************************************************************/
/* We know that each byte K3oe_bi from K3oe (K3o and K3e ditto) is obtained */
/* like this:                                                               */
/* K3oe_bi = (K2oe_bi modulo 5E) + 20                                       */
/* So, to recover K2oe_bi (K2o_bi and K2e_bi ditto):                        */
/* K3oe_bi - 20 = K2oe_bi%5E                                                */
/* Problem: we don't know how many times modulo 5E is applied to K2oe_bi.   */
/* So we obtain:                                                            */
/* K2oe_bi = K3oe_bi - 20 + j*5E    , with j = 0, 1, ..., n                 */
/* We init K2 with minimal values (j=0 => K2oe_bi = K3oe_bi - 20)           */
void Init_K2(int K3_len,int cur_split)
{
int i,j,k,l;

for(i=0;i<K3_len;i++)
   {
   K2_str_min[i]=(K3[i]-0x20);
   K2_str[i]=K2_str_min[i];
   }

for(i=0,k=0;i<3;i++)
   {
   for(j=0,l=0;j<3;j++)
      {
      if(split[cur_split].K1[i][j])
	 {
	 K2[i][l]=K2_str_min[k];
	 l++;
	 k++;
	 }
      }
   }
}

/****************************************************************************/
/* We have: K2oe_bi = K3oe_bi - 20 + j*5E    , with j = 0, 1, ..., n        */
/* (K2o_bi and K2e_bi ditto)                                                */
/* In order to try every possible K2, we increment j as long as K2oe_bi<100 */
/* If K2oe_bi>=100 then we reset it to minimal value (j=0)                  */
/* Return 1 if ok, else return 0 (no K2 to try)                             */
int Next_K2(int K3_len,int cur_split)
{
int i,j,k,l,tmp;


for(i=(K3_len-1);i>=0;i--)
   {
   tmp=(K2_str[i]+0x5E);
   if(tmp<0x100)
      {
      K2_str[i]=tmp;
      for(i=0,k=0;i<3;i++)
	 {
	 for(j=0,l=0;j<3;j++)
	    {
	    if(split[cur_split].K1[i][j])
	       {
	       K2[i][l]=K2_str[k];
	       l++;
	       k++;
	       }
	    }
	 }
      return(1);
      }
   else
      {
      K2_str[i]=K2_str_min[i];
      }
   }
return(0); //no more combi to try => stop
}

/****************************************************************************/
/* K1 is composed of 3 sub-keys of 4 bytes each: K1oe, K1o and K1e          */
/* Here we compute one of these sub-keys                                    */
void Calc_K1(int loc,int sub_key,int cur_split)
{
int i,j;
unsigned long sq,tmp;

//sub_key=0 => K1oe
//        1 => K1o
//        2 => K1e
switch(loc)
   {
   case 1 :
   //compute sum of squared pwd's characters
   sys.K1_found_val[sub_key]=0;
   for(i=0;i<sys.PWD_SQ_nb[sub_key];i++)
      {
      sq=sys.PWD_SQ_found_val[sub_key][i];
      sq*=sq;
      sys.K1_found_val[sub_key]+=sq;
      }
   break;

   case 2 :
   //K1oe = K1oe_b0 + 100*K1oe_b1 + 10000*K1oe_b2
   //K1o  = K1o_b0  + 100*K1o_b1  + 10000*K1o_b2
   //K1e  = K1e_b0  + 100*K1e_b1  + 10000*K1e_b2
   sys.K1_found_val[sub_key]=0;
   for(i=0;i<3;i++)
      {
      if(split[cur_split].K1[sub_key][i])
	 {
	 j=sys.LIN_pos_nz_lin[sub_key][i];
	 if(i==0) sys.K1_found_val[sub_key]+=sys.LIN_K1_found_val[sub_key][j];
	 else if(i==1)
	    {
	    tmp=(0x100*sys.LIN_K1_found_val[sub_key][j]);
	    tmp=tmp << 16;
	    tmp=tmp >> 16;
	    sys.K1_found_val[sub_key]+=tmp;
	    }
	 else
	    {
	    tmp=(0x10000*sys.LIN_K1_found_val[sub_key][j]);
	    tmp=tmp << 8;
	    tmp=tmp >> 8;
	    sys.K1_found_val[sub_key]+=tmp;
	    }
	 }
      }
   break;

   case 3 :
   if(sub_key==0)
      {//K1oe=K1o+K1e
      sys.K1_found_val[sub_key]=sys.K1_found_val[1];
      sys.K1_found_val[sub_key]+=sys.K1_found_val[2];
      }
   else if(sub_key==1)
      {//K1o=K1oe-K1e
      sys.K1_found_val[sub_key]=sys.K1_found_val[0];
      sys.K1_found_val[sub_key]-=sys.K1_found_val[2];
      }
   else
      {//K1e=K1oe-K1o
      sys.K1_found_val[sub_key]=sys.K1_found_val[0];
      sys.K1_found_val[sub_key]-=sys.K1_found_val[1];
      }
   break;
   }
}

/****************************************************************************/
/* Compute 1 byte from K1 (K1oe_bi, K1o_bi or K1e_bi)                       */
void Calc_LIN_K1_found_val(int loc,int sub_key,int lin)
{
int pwd_char,col;
unsigned long tmp;

//sub_key=0 => K1oe
//        1 => K1o
//        2 => K1e
switch(loc)
   {
   case 1 :
   //extract 1 byte from sub_key
   //K1oe = K1oe_b0 + 100*K1oe_b1 + 10000*K1oe_b2
   //K1o  = K1o_b0  + 100*K1o_b1  + 10000*K1o_b2
   //K1e  = K1e_b0  + 100*K1e_b1  + 10000*K1e_b2
   tmp=sys.K1_found_val[sub_key];
   col=sys.LIN_nz_lin[sub_key][lin];
   tmp=tmp << (24-(col*8));
   tmp=tmp >> 24;
   sys.LIN_K1_found_val[sub_key][lin]=tmp;
   break;

   case 2 :
   //K1oe_bi = K2oe_bi - pwd_char (+100 if pwd_char > K2oe_bi)
   pwd_char=sys.LIN_pwd_found_val[sub_key][lin];
   if(pwd_char<=K2[sub_key][lin]) sys.LIN_K1_found_val[sub_key][lin]=(K2[sub_key][lin]-pwd_char);
   else sys.LIN_K1_found_val[sub_key][lin]=(0x100+K2[sub_key][lin]-pwd_char);
   break;
   }
}

/****************************************************************************/
/* Let P[i] = character i from password, we have:                           */
/* K1oe = P[0]^2 + P[1]^2 + ... + P[i]^2 + ... + P[n]^2                     */
/* If we know every character but P[i], then we can compute P[i]:           */
/* P[i] = square root of (K1oe - P[0]^2 - P[1]^2 - ... - P[n]^2)            */
/* ditto with K1o and K1e                                                   */
void Calc_PWD_SQ(int sub_key)
{
int i;
unsigned long pp,sum2=0,cumul=0;

//sub_key=0 => K1oe
//        1 => K1o
//        2 => K1e
for(i=0;i<sys.PWD_SQ_nb[sub_key];i++)
   {
   if(sys.PWD_SQ_found[sub_key][i])
      {
      sum2=sys.PWD_SQ_found_val[sub_key][i];
      sum2*=sum2;
      cumul+=sum2;
      }
   }
pp=(sys.K1_found_val[sub_key]-cumul);

for(i=0;i<sys.PWD_SQ_nb[sub_key];i++)
   {
   if(!sys.PWD_SQ_found[sub_key][i])
      {
      sys.PWD_SQ_found_val[sub_key][i]=sqrt(pp);
      }
   }
}

/****************************************************************************/
/* Let P[i] = character i from password, we have:                           */
/* P[i] + K1oe_bi = K2oe_bi                                                 */
/* so if we know K1oe_bi and K2oe_bi then we can compute P[i]:              */
/* P[i] = K2oe_bi - K1oe_bi (+100 if K1oe_bi > K2oe_bi)                     */
void Calc_LIN_pwd_found_val(int sub_key,int lin)
{
int tmp;

//sub_key=0 => K1oe
//        1 => K1o
//        2 => K1e
tmp=sys.LIN_K1_found_val[sub_key][lin];
if(tmp<=K2[sub_key][lin])
   {
   sys.LIN_pwd_found_val[sub_key][lin]=(K2[sub_key][lin]-tmp);
   }
else sys.LIN_pwd_found_val[sub_key][lin]=(0x100+K2[sub_key][lin]-tmp);

}

/****************************************************************************/
/* Compute 1 byte from K1 (K1oe_bi, K1o_bi or K1e_bi)                       */
void Calc_COL_K1_found_val(int loc,int sub_key,int col,int lin)
{
int i,j,a,b,c,pwd,coef2;
unsigned long coef;

//sub_key=0 => K1oe
//        1 => K1o
//        2 => K1e
switch(loc)
   {
   case 1 :
   //extract 1 byte from sub_key
   //K1oe = K1oe_b0 + 100*K1oe_b1 + 10000*K1oe_b2
   //K1o  = K1o_b0  + 100*K1o_b1  + 10000*K1o_b2
   //K1e  = K1e_b0  + 100*K1e_b1  + 10000*K1e_b2
   j=sys.COL_pos_nz_col[col][sub_key];
   coef=sys.K1_found_val[sub_key];
   coef=coef >> (24-(col*8));
   coef=coef << 24;
   sys.COL_K1_found_val[col][j]=coef;
   break;

   case 2 :
   //K1oe_bi = K2oe_bi - pwd_char (+100 if pwd_char > K2oe_bi)
   i=sys.COL_lin[col][lin];
   j=sys.LIN_pos_nz_lin[i][col];
   pwd=sys.COL_pwd_found_val[col][lin];
   if(pwd<=K2[i][j]) sys.COL_K1_found_val[col][lin]=(K2[i][j]-pwd);
   else sys.COL_K1_found_val[col][lin]=(0x100+K2[i][j]-pwd);
   break;

   case 3:
   //if column i isolated: K1oe_bi = (K1o_bi + K1e_bi) modulo 100
   a=b=c=coef2=0;
   for(i=0;i<sys.COL_nz_nb[col];i++)
      {
      if(sys.COL_found[col][i])
	 {
	 j=sys.COL_pos_nz_col[col][i];
	 if(sys.COL_lin[col][j]==0)
	    a=sys.COL_K1_found_val[col][i];
	 else if(sys.COL_lin[col][j]==1)
	    b=sys.COL_K1_found_val[col][i];
	 else
	    c=sys.COL_K1_found_val[col][i];
	 }
      }

   for(i=0;i<sys.COL_nz_nb[col];i++)
      {
      if(!sys.COL_found[col][i])
	 {
	 j=sys.COL_pos_nz_col[col][i];
	 if(sys.COL_lin[col][j]==0) coef=(b+c);
	 else if(sys.COL_lin[col][j]==1) coef2=(a-c);
	 else coef2=(a-b);

	 if (coef2<0x00)   coef2+=0x100;
	 if (coef2>=0x100) coef2-=0x100;
	 sys.COL_K1_found_val[col][i]=coef2;
	 break;
	 }
      }

   break;
   }
}


/****************************************************************************/
/* Let P[i] = character i from password, we have:                           */
/* P[i] + K1oe_bi = K2oe_bi                                                 */
/* so if we know K1oe_bi and K2oe_bi then we can compute P[i]:              */
/* P[i] = K2oe_bi - K1oe_bi (+100 if K1oe_bi > K2oe_bi)                     */
void Calc_COL_pwd_found_val(int loc,int sub_key,int col)
{
int i,j,k,coef;

//sub_key=0 => K1oe
//        1 => K1o
//        2 => K1e

switch(loc)
   {
   case 1:
   j=sys.COL_pos_nz_col[col][sub_key];
   coef=sys.COL_K1_found_val[col][j];
   i=sys.COL_lin[col][j];
   k=sys.LIN_pos_nz_lin[i][col];
   if(coef<=K2[i][k]) sys.COL_pwd_found_val[col][j]=(K2[i][k]-coef);
   else sys.COL_pwd_found_val[col][j]=(0x100+K2[i][k]-coef);
   break;

   case 2:
   for(i=0;i<sys.COL_nz_nb[col];i++)
      {
      if(sys.COL_found[col][i]==0)
	 {
	 coef=sys.COL_K1_found_val[col][i];
	 k=sys.COL_lin[col][i];
	 j=sys.LIN_pos_nz_lin[k][col];
	 if(coef<=K2[k][j]) sys.COL_pwd_found_val[col][i]=(K2[k][j]-coef);
	 else sys.COL_pwd_found_val[col][i]=(0x100+K2[k][j]-coef);
	 break;
	 }
      }
   break;
   }

}


/****************************************************************************/
/* Some password's character(s) must be fixed in order to compute remaining */
/* characters.                                                              */
/* Let PWD_fixed_nb=number of character(s) to fix, since each character P[i]*/
/* takes a value between char_min and char_max, we have:                    */
/* (char_max-char_min+1)^(PWD_fixed_nb) combinations to try out.            */
/* Let char_min=20, char_max=7F, PWD_fixed_nb=3 (we fix P[i], P[j], P[k]):  */
/*               P[i] P[j] P[k]                                             */
/* combi     0:  20   20   20                                               */
/* combi     1:  20   20   21                                               */
/* ...                                                                      */
/* combi D8000:  7F   7F   7F                                               */
/* This function intends to compute the next combi                          */
/* Return 1 if succesfull, 0 otherwise                                      */
int Next_fixed_val(int PWD_fixed_nb,int **fixed_val)
{
int i;

for(i=PWD_fixed_nb-1;i>=0;i--) //backward
   {
   if((*fixed_val)[i]<char_max)
      {// OK, character i can be changed
      (*fixed_val)[i]++;
      return(1); //OK
      }
   else {(*fixed_val)[i]=char_min;} //reset
   }
return(0); //no more combi to try => failed
}

/****************************************************************************/
/* In order to recover Pwd, we fix some Pwd's characters, then remaining    */
/* characters can be calculated. Characters can be fixed in various orders: */
/* For instance we can fix P[0], then P[1], then P[2], then ... But we can  */
/* also fix P[2], then P[1], then P[0], then... There are (pwd's length!)   */
/* distinct orders to try out.                                              */
/* This function intends to build next order to be tried out.               */
/* Return 0 if succesfull, 1 otherwise                                      */
int Next_order(int pwd_len,int **order,int *shift_max,int **shift_cur)
{
int i,j,k,cur_len,pos_orig,pos_dest;
//int *tmp_orig,*tmp_dest;

if(Next_shift(pwd_len,shift_max,shift_cur)) return(1); //no more order to try

//tmp_orig=(int *)malloc(sizeof(int)*pwd_len);
//tmp_dest=(int *)malloc(sizeof(int)*pwd_len);

//init
for(i=0;i<pwd_len;i++) {(*order)[i]=i; tmp_orig[i]=(*order)[i];}

for(i=0;i<(pwd_len-1);i++)
   {
   cur_len=(pwd_len-i);
   for(j=0;j<cur_len;j++)
      {
      pos_orig=(i+j);
      pos_dest=(i+((j+(*shift_cur)[i])%cur_len));
      tmp_dest[pos_dest]=tmp_orig[pos_orig];
      }
   for(k=0;k<pwd_len;k++) tmp_orig[k]=tmp_dest[k];
   }

for(k=0;k<pwd_len;k++) (*order)[k]=tmp_dest[k];

//free(tmp_orig);
//free(tmp_dest);

return(0); //OK
}

/****************************************************************************/
/* Let pwd_len=Pwd's length, we perform (pwd_len-1) permutations on order[i]*/
/* First permutation applies on whole order, second permutation on whole    */
/* order less first character, third one on whole order less (first and     */
/* second character), ... Some permutation can let order unchanged          */
/* Once every permutation done, we obtain order[i+1]                        */
/* For instance, with pwd_len=5: initial order=order[0] = {0 1 2 3 4}       */
/* permutation:  <   0   >        <  1  >          < 2 >            <3>     */
/*    order[0]:  0 1 2 3 4      0 1 2 3 4      0 1 2 3 4      0 1 2 3 4     */
/*    order[1]:                                               0 1 2 4 3     */
/*    order[2]:                                0 1 4 2 3      0 1 4 2 3     */
/*    order[3]:                                               0 1 4 3 2     */
/*     ...                                                                  */
/* Return 0 if succesfull, 1 otherwise                                      */
int Next_shift(int pwd_len,int *shift_max,int **shift_cur)
{
int i;

for(i=(pwd_len-2);i>=0;i--)
   {
   if((*shift_cur)[i]==shift_max[i]) (*shift_cur)[i]=0;
   else
      {
      (*shift_cur)[i]++;
      return(0); //OK
      }
   }

return(1); //no good
}

/****************************************************************************/
/* We know that: K1oe = K1o + K1e. A byte "column" (for a same indice i:    */
/* K1oe_bi, K1o_bi and K1e_bi) can be "isolated" or not from other columns. */
/* A column i is isolated if we ALWAYS have: Kloe_bi = K1o_bi + K1e_bi,     */
/* no matter values of K1oe_bi, K1o_bi and K1e_bi. This means that column i */
/* can not receive a carry from column i-1. For instance:                   */
/*                                                                          */
/* K1oe = 6958AD   -->  K1oe_b0 = AD , K1oe_b1 = 58 , K1oe_b2 = 69          */
/* K1o  = 3117B0   -->  K1o_b0  = B0 , K1o_b1  = 17 , K1o_b2  = 31          */
/* K1e  = 3840FD   -->  K1e_b0  = FD , K1e_b1  = 40 , K1e_b2  = 38          */
/*                                                                          */
/* -column 0 can not receive a carry because there is no other column on    */
/* its left-side. So we have: K1oe_b0 =  K1o_b0 + K1e_b0                    */
/* This gives us one more equation to help us to recover pwd.               */
/*                                                                          */
/* -columns 1 and 2 can receive a carry from the left, for instance we have */
/* K1oe_b1 <> K1o_b0 + K1e_b0  , so we can't use them.                      */
void Fill_dependency(int nb_split)
{
int i,j,col;

for(i=0;i<nb_split;i++)
   {
   if(split[i].valid)
      {//no need to compute dependency of bad splits
      for(col=0;col<3;col++)
	 {//each col
	 if(Carry_left(col,split[i].K1[2],split[i].K1[1]))
	 split[i].isolated[col]=0;      //dependency
	 else split[i].isolated[col]=1; //independency
	 }
      }
   }
}

/****************************************************************************/
/* return 1 if new password's character(s) found, else 0                    */
int Progress(int cur_split)
{
int i,j,sub_key,col;
int PWD_found_nb_before;

//sub_key=0 => K1oe
//        1 => K1o
//        2 => K1e

PWD_found_nb_before=sys.PWD_found_nb;

//examine squared equations
for(sub_key=0;sub_key<3;sub_key++)
   {
   for(i=0;i<sys.PWD_SQ_nb[sub_key];i++)
      {
      j=sys.PWD_SQ[sub_key][i];
      if((!sys.PWD_found[j]) && (sys.PWD_SQ_found[sub_key][i]))
	 {
	 if(exh_search) sys.PWD_found_val[j]=sys.PWD_SQ_found_val[sub_key][i];
	 sys.PWD_found[j]=1;
	 sys.PWD_found_nb++;
	 }
      }
   }

//examine line equations
for(sub_key=0;sub_key<3;sub_key++)
   {
   for(i=0;i<sys.LIN_nz_nb[sub_key];i++)
      {
      j=sys.LIN_nz_pwd[sub_key][i];
      if((!sys.PWD_found[j]) && (sys.LIN_found[sub_key][i]))
	 {
	 if(exh_search) sys.PWD_found_val[j]=sys.LIN_pwd_found_val[sub_key][i];
	 sys.PWD_found[j]=1;
	 sys.PWD_found_nb++;
	 }
      }
   }

//examine column equations
for(col=0;col<3;col++)
   {
   if(split[cur_split].isolated[col])
      {
      for(i=0;i<sys.COL_nz_nb[col];i++)
	 {
	 j=sys.COL_nz_pwd[col][i];
	 if((!sys.PWD_found[j]) && (sys.COL_found[col][i]))
	    {
	    if(exh_search) sys.PWD_found_val[j]=sys.COL_pwd_found_val[col][i];
	    sys.PWD_found[j]=1;
	    sys.PWD_found_nb++;
	    }
	 }
      }
   }

if(sys.PWD_found_nb>PWD_found_nb_before) return(1);
else return(0);
}

/****************************************************************************/
/* Perform initialisation of system to solve                                */
void Init_system(int cur_split,int *pwd_ext)
{
int i,j,sub_key,col;

//sub_key=0 => K1oe
//        1 => K1o
//        2 => K1e

sys.PWD_nb=pwd_len;
sys.PWD_fixed_nb=0;
sys.PWD_found_nb=0;
for(i=0;i<pwd_len;i++)
   {
   sys.PWD_fixed[i]=0;
   sys.PWD_found[i]=0;
   }

for(sub_key=0;sub_key<3;sub_key++) {sys.K1_found[sub_key]=0;}

sys.PWD_SQ_nb[0]=pwd_len;
sys.PWD_SQ_found_nb[0]=0;
for(i=0;i<sys.PWD_SQ_nb[0];i++)
   {
   sys.PWD_SQ[0][i]=i;
   sys.PWD_SQ_found[0][i]=0;
   }

sys.PWD_SQ_nb[1]=floor(pwd_len/2);
sys.PWD_SQ_found_nb[1]=0;
for(i=0,j=1;i<sys.PWD_SQ_nb[1];i++,j+=2)
   {
   sys.PWD_SQ[1][i]=j;
   sys.PWD_SQ_found[1][i]=0;
   }

sys.PWD_SQ_nb[2]=(pwd_len-sys.PWD_SQ_nb[1]);
sys.PWD_SQ_found_nb[2]=0;
for(i=0,j=0;i<sys.PWD_SQ_nb[2];i++,j+=2)
   {
   sys.PWD_SQ[2][i]=j;
   sys.PWD_SQ_found[2][i]=0;
   }

for(sub_key=0;sub_key<3;sub_key++)
   {
   sys.LIN_nz_nb[sub_key]=split[cur_split].size_K1[sub_key];
   sys.LIN_found_nb[sub_key]=0;
   for(i=0,j=0;i<3;i++)
      {
      if(split[cur_split].K1[sub_key][i])
	 {
	 sys.LIN_pos_nz_lin[sub_key][i]=j;
	 sys.LIN_nz_lin[sub_key][j]=i;
	 sys.LIN_nz_pwd[sub_key][j]=pwd_ext[(4*sub_key)+i];
	 j++;
	 }
      sys.LIN_found[sub_key][i]=0;
      }
   }

for(col=0;col<3;col++)
   {
   if(split[cur_split].isolated[col])
      {
      sys.COL_split[col][0]=split[cur_split].K1[0][col];
      sys.COL_split[col][1]=split[cur_split].K1[1][col];
      sys.COL_split[col][2]=split[cur_split].K1[2][col];
      sys.COL_nz_nb[col]=0;
      sys.COL_found_nb[col]=0;

      j=0;
      sys.COL_found[col][0]=0;
      sys.COL_found[col][1]=0;
      sys.COL_found[col][2]=0;
      if(sys.COL_split[col][0])
	 {
	 sys.COL_nz_pwd[col][j]=pwd_ext[0+col]; sys.COL_nz_nb[col]++;
	 sys.COL_pos_nz_col[col][0]=j; sys.COL_lin[col][j]=0;
	 j++;
	 }
      if(sys.COL_split[col][1])
	 {
	 sys.COL_nz_pwd[col][j]=pwd_ext[4+col]; sys.COL_nz_nb[col]++;
	 sys.COL_pos_nz_col[col][1]=j; sys.COL_lin[col][j]=1;
	 j++;
	 }
      if(sys.COL_split[col][2])
	 {
	 sys.COL_nz_pwd[col][j]=pwd_ext[8+col]; sys.COL_nz_nb[col]++;
	 sys.COL_pos_nz_col[col][2]=j; sys.COL_lin[col][j]=2;
	 j++;
	 }
      }
   }

}

/****************************************************************************/
/* Examine the whole set of equations and try to compute some password's    */
/* character(s), some sub_keys, ...                                         */
void Update_system(int cur_split)
{
int i,j,sub_key,col;

//sub_key=0 => K1oe
//        1 => K1o
//        2 => K1e

//try to calculate K1oe,K1o and/or K1e
for(sub_key=0;sub_key<3;sub_key++)
   {
   if(sys.PWD_SQ_found_nb[sub_key]==sys.PWD_SQ_nb[sub_key])
      {//use squared equations
      if(exh_search) {Calc_K1(1,sub_key,cur_split);}
      sys.K1_found[sub_key]=1;
      }
   else if(sys.LIN_found_nb[sub_key]==sys.LIN_nz_nb[sub_key])
      {//use line equations
      if(exh_search) {Calc_K1(2,sub_key,cur_split);}
      sys.K1_found[sub_key]=1;
      }
   }

//try to calculate K1oe,K1o and/or K1e
if(sys.K1_found[0] && sys.K1_found[2])
   {//K1o=K1oe-K1e
   if(exh_search) {Calc_K1(3,1,cur_split);}
   sys.K1_found[1]=1;
   }
if(sys.K1_found[2] && sys.K1_found[1])
   {//K1oe=K1o+K1e
   if(exh_search) {Calc_K1(3,0,cur_split);}
   sys.K1_found[0]=1;
   }
if(sys.K1_found[1] && sys.K1_found[0])
   {//K1e=K1oe-K1o
   if(exh_search) {Calc_K1(3,2,cur_split);}
   sys.K1_found[2]=1;
   }

for(sub_key=0;sub_key<3;sub_key++)
{
if(sys.K1_found[sub_key])
   {
   for(i=0;i<sys.LIN_nz_nb[sub_key];i++)
      {
      if(exh_search)
	 {
	 Calc_LIN_K1_found_val(1,sub_key,i);//compute K1oe_bi K1o_bi or K1e_bi
	 Calc_LIN_pwd_found_val(sub_key,i); //compute P[i]
	 }
      sys.LIN_found[sub_key][i]=1;
      }
   sys.LIN_found_nb[sub_key]=sys.LIN_nz_nb[sub_key];

   if((sys.PWD_SQ_nb[sub_key]-sys.PWD_SQ_found_nb[sub_key])==1)
      {
      if(exh_search) {Calc_PWD_SQ(sub_key);}
      for(i=0;i<sys.PWD_SQ_nb[sub_key];i++)
	 {
	 sys.PWD_SQ_found[sub_key][i]=1;
	 }
      sys.PWD_SQ_found_nb[sub_key]=sys.PWD_SQ_nb[sub_key];
      }

   for(col=0;col<3;col++)
      {
      if((split[cur_split].isolated[col]) && (sys.COL_split[col][sub_key]))
	 {
	 j=sys.COL_pos_nz_col[col][sub_key];
	 if(!sys.COL_found[col][j])
	    {
	    if(exh_search)
	       {
	       Calc_COL_K1_found_val(1,sub_key,col,col);
	       Calc_COL_pwd_found_val(1,sub_key,col);
	       }
	    sys.COL_found[col][j]=1;
	    sys.COL_found_nb[col]++;
	    }
	 }
      }
   }
}

for(col=0;col<3;col++)
   {
   if(split[cur_split].isolated[col])
      {
      if((sys.COL_nz_nb[col]-sys.COL_found_nb[col])==1)
	 {
	 if(exh_search)
	    {
	    Calc_COL_K1_found_val(3,0,col,0);
	    Calc_COL_pwd_found_val(2,0,col);
	    }
	 for(i=0;i<sys.COL_nz_nb[col];i++)
	    {
	    sys.COL_found[col][i]=1;
	    }
	 sys.COL_found_nb[col]=sys.COL_nz_nb[col];
	 }
      }
   }

}

/****************************************************************************/
/* If a pwd's character P[i] was found, we must copy it into lines, columns */
/* and squared equations so solving can progress                            */
void Copy_found(int cur_split)
{
int i,j,sub_key,col;

//squared equations
for(sub_key=0;sub_key<3;sub_key++)
   {
   for(i=0;i<sys.PWD_SQ_nb[sub_key];i++)
      {
      j=sys.PWD_SQ[sub_key][i];
      if((!sys.PWD_SQ_found[sub_key][i]) && (sys.PWD_found[j]))
	 {
	 sys.PWD_SQ_found[sub_key][i]=1;
	 if(exh_search) sys.PWD_SQ_found_val[sub_key][i]=sys.PWD_found_val[j];
	 sys.PWD_SQ_found_nb[sub_key]++;
	 }
      }
   }

//line equations
for(sub_key=0;sub_key<3;sub_key++)
   {
   for(i=0;i<sys.LIN_nz_nb[sub_key];i++)
      {
      j=sys.LIN_nz_pwd[sub_key][i];
      if((!sys.LIN_found[sub_key][i]) && (sys.PWD_found[j]))
	 {
	 sys.LIN_found[sub_key][i]=1;
	 if(exh_search)
	    {
	    sys.LIN_pwd_found_val[sub_key][i]=sys.PWD_found_val[j];
	    Calc_LIN_K1_found_val(2,sub_key,i);
	    }
	 sys.LIN_found_nb[sub_key]++;
	 }
      }
   }

//column equations
for(col=0;col<3;col++)
   {
   if(split[cur_split].isolated[col])
      {
      for(i=0;i<sys.COL_nz_nb[col];i++)
	 {
	 j=sys.COL_nz_pwd[col][i];
	 if((!sys.COL_found[col][i]) && (sys.PWD_found[j]))
	    {
	    sys.COL_found[col][i]=1;
	    if(exh_search)
	       {
	       sys.COL_pwd_found_val[col][i]=sys.PWD_found_val[j];
	       Calc_COL_K1_found_val(2,sub_key,col,i);
	       }
	    sys.COL_found_nb[col]++;
	    }
	 }
      }
   }

}

/****************************************************************************/
/* build an extended password. e.g: pwd_len=5 , pwd_ext_len=12:             */
/* pwd_ext = 0 1 2 3 4 0 1 2 3 4 0 1                                        */
/*           <---  pwd_ext_len  --->                                        */
void Fill_pwd_ext(int pwd_len,int pwd_ext_len,int **pwd_ext)
{
int i;

for(i=0;i<pwd_ext_len;i++) (*pwd_ext)[i]=fmod(i,pwd_len);
}

/****************************************************************************/
/* return 1 if a carry can come from column(s) on left side of current col  */
/* return 0 otherwise                                                       */
int Carry_left(int col_cur_pos,int c[4],int b[4])
{
int i;
int col_11_found=0;
int col_11_pos;

//look for col 1+1 on left side of current col
for(i=0;i<col_cur_pos;i++)
   {
   if(c[i] && b[i]) {col_11_found=1; col_11_pos=i; break;}
   }

if(!col_11_found) {return(0); /*no good*/}

//look for col 0+0 between col 1+1 and current col
for(i=col_11_pos;i<col_cur_pos;i++)
   {
   if((!c[i]) && (!b[i])) {return(0); /*no good*/}
   }

return(1); //ok
}

/****************************************************************************/
/* return 1 if a carry exists on right side of current column               */
/* return 0 otherwise                                                       */
int Carry_right(int col_cur_pos,int a[4])
{
int i;


for(i=(col_cur_pos+1);i<3;i++)
   {
   if(a[i]) return(1); //ok
   }
return(0); //no good
}

/****************************************************************************/
/* split's size = number of not-null byte(s) in K1oe                        */
/*               +    ''             ''         K1o                         */
/*               +    ''             ''         K1e                         */
void Fill_size(int nb_split)
{
int i,j,sub_key;

//sub_key=0 => K1oe
//        1 => K1o
//        2 => K1e
for(i=0;i<nb_split;i++)
   {
   if(split[i].valid)
      {//no need to compute size of bad splits
      for(sub_key=0;sub_key<3;sub_key++) {split[i].size_K1[sub_key]=0;}
      for(j=0;j<3;j++)
	 {
	 if(split[i].K1[0][j]) split[i].size_K1[0]++;
	 if(split[i].K1[1][j]) split[i].size_K1[1]++;
	 if(split[i].K1[2][j]) split[i].size_K1[2]++;
	 }
      split[i].size_split=(split[i].size_K1[0]
			  +split[i].size_K1[1]
			  +split[i].size_K1[2]);
      }
   }
}

/****************************************************************************/
/* Only 1 number out of 100 ends with a null byte, so splits with null      */
/* byte(s) are less likely than others. We order splits by decreasing       */
/* frequency: {1110} first, then {0110}, ..., {0010}, so the most likely    */
/* splits are tried first.                                                  */
void Order_split(int K3_len,const int nb_split,int *nb_split_ok,
		 int *split_order)
{
int i,j,k,tmp_sum,tmp_pos,nb_ok;
int *split_pos,*split_sum;

split_pos=(int *)malloc(sizeof(int)*nb_split);
split_sum=(int *)malloc(sizeof(int)*nb_split);

nb_ok=0;
for(i=0;i<nb_split;i++)
   {
   if( (split[i].valid) && (split[i].size_split==K3_len) )
      {
      split_pos[nb_ok]=i;
      split_sum[nb_ok]=0;
      for(j=0;j<3;j++)
	 {
	 for(k=0;k<3;k++)
	    {
	    if(split[i].K1[j][k]) split_sum[nb_ok]+=k;
	    }
	 }
      nb_ok++;
      }
   }

//order (Bubble Sort)
for(i=1;i<nb_ok;i++)
   {
   for(j=0;j<i;j++)
      {
      if(split_sum[i]<split_sum[j])
	 {
	 tmp_sum=split_sum[i];
	 tmp_pos=split_pos[i];
	 split_sum[i]=split_sum[j];
	 split_pos[i]=split_pos[j];
	 split_sum[j]=tmp_sum;
	 split_pos[j]=tmp_pos;
	 }
      }
   }

for(i=0;i<nb_ok;i++) split_order[i]=split_pos[i];
*nb_split_ok=nb_ok;

}

/****************************************************************************/
/* for info only: for each split's size, display number of valid splits     */
void Stats(int nb_split)
{
int i,j;
int nb_split_ok=0;
int nb[10];

for(i=0;i<nb_split;i++)
   {
   if(split[i].valid) nb_split_ok++;
   }
printf("\nsplits   : %d",nb_split);
printf("\nsplits ok: %d",nb_split_ok);

//size=3,4,5,6,7,8,9
for(i=0;i<10;i++) nb[i]=0;
for(i=0;i<nb_split;i++)
   {
   if(split[i].valid)
      {
      nb[split[i].size_split]++;
      if(split[i].K1[0][0] && split[i].K1[0][1] && !split[i].K1[0][2] &&
	 split[i].K1[1][0] && split[i].K1[1][1] && !split[i].K1[1][2] &&
	 split[i].K1[2][0] && split[i].K1[2][1] && !split[i].K1[2][2])
	 printf("[%d]",i);
      }
   }
for(i=0;i<10;i++) printf("\nTaille %d : %d",i,nb[i]);

}


/****************************************************************************/
/* To indicate if a byte from K1 is null or not, we introduce variables     */
/* K1oe_n0, K1oe_n1, ... (0=> null byte , 1=> not null byte)                */
/* let split_K1oe={K1oe_n0 K1oe_n1 K1oe_n2 K1oe_n3}                         */
/*     split_K1o ={K1o_n0  K1o_n1  K1o_n2  K1o_n3 }                         */
/*     split_K1e ={K1e_n0  K1e_n1  K1e_n2  K1e_n3 }                         */
/* (k1oe,K1o,K1e) range: 0800h->F813Fh so:                                  */
/* we can NOT have: split_K1oe, split_K1o and/or split_K1e = {1 0 0 0}      */
/* we ALWAYS  have: K1oe_n3=K1o_n3=K1e_n3=0				    */
/* So 6 values are possible for split_K1oe, split_K1o and split_K1e:        */
/* {0 1 0 0} , {1 1 0 0} , {0 0 1 0} , {1 0 1 0} , {0 1 1 0} , {1 1 1 0}    */
/* we feed split structure with every combination of those 6 values:        */
/* 1ø combi: split_K1oe={0 1 0 0}  split_K1o={0 1 0 0}  split_K1e={0 1 0 0} */
/* 2ø combi: split_K1oe={0 1 0 0}  split_K1o={0 1 0 0}  split_K1e={1 1 0 0} */
/* 3ø combi: split_K1oe={0 1 0 0}  split_K1o={0 1 0 0}  split_K1e={0 0 1 0} */
/*  ...                                                                     */
/* last one: split_K1oe={1 1 1 0}  split_K1o={1 1 1 0}  split_K1e={1 1 1 0} */
void Fill_split(int nb_split,int nb_combi,unsigned *combi)
{
int i,ii,iii,pos_i,pos_ii,pos_iii,j;

i=0;
ii=0;
iii=0;
pos_i=0;
pos_ii=0;
pos_iii=0;
do
   {
   split[iii].valid=1;
   for(j=0;j<4;j++)
      {
      split[iii].K1[0][j]=combi[pos_i+j];
      split[iii].K1[1][j]=combi[pos_ii+j];
      split[iii].K1[2][j]=combi[pos_iii+j];
      }

   i++;
   if(i==(nb_combi*nb_combi))
   {i=0; pos_i+=4; pos_ii=0;}

   ii++;
   if(ii==nb_combi)
      {
      ii=0;
      if(i) pos_ii+=4;
      pos_iii=0;
      }

   iii++;
   if(i && ii) pos_iii+=4;
   } while(iii<nb_split);

}

/****************************************************************************/
/* some combinations among split structure are valid, some are not:         */
/* e.g: split_K1oe={0 1 1 0} |            K1oe={0 1 0 0} |		    */
/*      split_K1o ={0 1 0 0} | => valid   K1o ={0 0 1 0} | => invalid       */
/*      split_K1e ={0 1 1 0} |            k1e ={0 1 1 0} |                  */
/*                                                        (K1oe < (K1o+K1e))*/
/* so we must eliminate invalid combi by checking each "column":            */
/*  split_K1o   0 1 1 0                                                     */
/*             +           						    */
/*  split_K1e   0 1 0 0  						    */
/*            = =======  						    */
/*  split_K1oe  0 1 1 0  						    */
/*              | | | |  						    */
/*              c c c c  						    */
/*              o o o o  						    */
/*              l l l l  						    */
/*              0 1 2 3  						    */
void Select_split(int nb_split)
{
int i,j;

for(i=0;i<nb_split;i++)   //each split
   {
   for(j=0;j<3;j++)       //4 columns, but 4th column is always 0
      {                   //so we only check columns 0 1 2
      // 0+0=0 -> ok
      // 0+0=1 -> test
      // 1+0=0 / 0+1=0 -> test
      // 1+0=1 / 0+1+1 -> ok
      // 1+1=0 -> test
      // 1+1+1 -> ok

      //case 0+0=1
      if((!split[i].K1[2][j]) &&
	 (!split[i].K1[1][j]) &&
	 ( split[i].K1[0][j]))
	 {//carry on left side?
	 if(!Carry_left(j,split[i].K1[2],split[i].K1[1]))
	    {
	    split[i].valid=0; //invalid
	    break;
	    }
	 }

      //case 1+0=0 / 0+1=0
      if((((!split[i].K1[2][j]) && (split[i].K1[1][j])) ||
	 ((split[i].K1[2][j]) && (!split[i].K1[1][j]))) &&
	 (!split[i].K1[0][j]))
	 {//carry on left side AND on right side?
	 if(!Carry_left(j,split[i].K1[2],split[i].K1[1])
	    ||
	    !Carry_right(j,split[i].K1[0]))
	    {
	    split[i].valid=0; //invalid
	    break;
	    }
	 }

      //case 1+1=0
      if((split[i].K1[2][j]) &&
	 (split[i].K1[1][j]) &&
	 (!split[i].K1[0][j]))
	 {//carry on right side?
	 if(!Carry_right(j,split[i].K1[0]))
	    {
	    split[i].valid=0; //invalid
	    break;
	    }
	 }
      }//each col
   }//each split

}

/***********************************************************************/
void Hi_folks(void)
{
printf("\n\nYet Another Password Cracker by Caz {;-)");
printf("\n-> Target: MasterKey v1.05 by Ph. Melleret\n");
}

/***********************************************************************/
/* MasterKey's encrypted key is extracted from Registry and stored in  */
/* file crkmstrk.txt (this file must be in SAME directory as Cracker)  */
/* NB: key is stored in Registry under                                 */
/* [HKEY_USERS\.Default\Software\Kruptos Solutions\MkStarter\Security] */
/* - success : return file's handle                                    */
/* - failure : exit prg                                                */
int Open_key_file(char *key_file)
{
int fn;

// try to open file
fn=open(key_file,O_BINARY|O_RDONLY);
switch(fn)
   {
   case -1:printf("\nFILE %s NOT FOUND!",key_file);
   printf("\n->This file MUST be in SAME directory as Cracker!");
   printf("\n->Make sure you launch crkmstrk.BAT before crkmstrk.EXE!");
   Wait_keyboard(); exit(0);
   default: /*printf("\nOK, FILE FOUND")*/; return(fn);
   }
}

/***********************************************************************/
/*                   wait for key pressed                              */
void Wait_keyboard(void)
{
printf("\n");
printf("              ******************\n");
printf("              * hit any key... *\n");
printf("              ******************\n");
getch(); {/* wait until key pressed */}      //kbhit
}

/***********************************************************************/
/*                        display password                             */
void Print_pwd(int pwd_len,int *Pwd)
{
int i;

printf("\n\n ASCII sequence: ");
for(i=0;i<pwd_len;i++)
   {
   printf("[%d]",Pwd[i]);
   if((i+1)%10==0) {printf("\n            ");}
   }

printf("\n\n  PASSWORD: >>>");
for(i=0;i<pwd_len;i++)
   {
   printf("%c",Pwd[i]);
   //fprintf(logfile,"%c",Pwd[i]);
   //fflush(logfile);
   }
printf("<<< (%d characters)\n\n",pwd_len);
//fprintf(logfile,"<<< (%d characters)\n\n",pwd_len);
//fflush(logfile);
printf("(don't type >>> or <<<)\n");
}

/***********************************************************************/
/* Read encrypted key extracted from Registry. Key is stored on Access */
/* line (for instance, below key value : e=2E@r)                       */
/* REGEDIT4                                                            */
/*                                                                     */
/* [HKEY_USERS\.Default\Software\Kruptos Solutions\MkStarter\Security] */
/* "Access"="e=2E@r"                                                   */
/* @=""                                                                */
void Read_key(int fn,int *K3_len,int **K3)
{
unsigned char Buffer[200];
char *pos;
int len,i;

read(fn,Buffer,200);

//look for line with "Access" keyword
pos=strstr(Buffer,"Access");
if (pos==NULL)
   {
   printf("\nInvalid key file!\n");
   Wait_keyboard(); exit(0);
   }

//  Access"="   9 characters
pos+=9;

//compute key's length
len=0;
while((pos+len)[0]!='"') len++;
*K3_len=len;

//read key
for(i=0;i<*K3_len;i++) (*K3)[i]=pos[i];

}

********************************************************************************

Copyright October 22, 2000 by Casimir.

Here is the executable

Mail Casimir

Converted to hypertext by Joe Peschel October 22, 2000.