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

****************** ENABLING THE BACKDOOR .... **********************

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

Author : j!m

Date : 10-24-2001

Target : All the software you can download at www.gregorybraun.com !!

Tools : Softice, borland C,

INTRODUCTION

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

Gregory Braun is a shareware author, you can find and download on his site all the progs he has done.

Maybe you can find some interesting things may be not, i have downloaded crypto3.6 (file crypto) and FxEdit (hex editor).

My first goal was to devise a keygen for these pieces of software.

I achieved this task easily and i will not give you here all the details of the operation since

the interest is somewhere else (sorry, no ASM this time!).

In this essay, we are going to reverse the key generation scheme used in the products in order to create

some valid keys but also to enable a strange feature included in all Braun's softwa

re: a magic password that automatically

registers the programs!!

Ok, here we go now,

THE KEYGEN SCHEME

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

Very simple:

The valid key is the decimal representation of the number computed by:

H(name) + H(organization) + Product_key

Where H is an Hash function implemented in the same way in all the products, only the product_key differs and is

included in the exe file.

the C implementation of the Hash function is given here (i let you play with softice...;-)

<------------------ Listing 1: the H function ------------------------>

int hashval(char *s) {

unsigned char table1[54] = {

0x23,0x73,0x65,0x72,0x42,0x26,0x6E,0x7A,0x7C,0x6D,

0x66,0x4D,0x31,0x2F,0x35,0x28,0x21,0x73,0x64,0x24,

0x4D,0x71,0x2E,0x7B,0x73,0x5D,0x2B,0x73,0x46,0x6A,

0x74,0x4B,0x70,0x7A,0x53,0x64,0x74,0x7A,0x6F,0x58,

0x71,0x6D,0x62,0x5E,0x41,0x6C,0x40,0x64,0x76,0x3A,

0x73,0x3F,0x78,0x2F};

unsigned char table2[54] = {

0x7C,0x62,0x21,0x70,0x7A,0x2A,0x6C,0x73,0x3B,0x72,

0x6E,0x7C,0x6C,0x66,0x24

,0x76,0x69,0x5E,0x41,0x78,

0x70,0x65,0x29,0x72,0x78,0x35,0x61,0x69,0x63,0x26,

0x39,0x2F,0x32,0x6D,0x35,0x6C,0x73,0x69,0x34,0x40,

0x30,0x64,0x6D,0x5A,0x77,0x39,0x34,0x63,0x6D,0x71,

0x70,0x66,0x68,0x77};

unsigned int i,l,c,a,b;

l = strlen(s);

c = 0;

for (i=0; i<l; i++) {

a = table2[i];

b = table1[i+l];

a *= b;

a *= (i+1);

b = s[i];

a *= b;

c += a;

}

return(c);

}

<----------------------------------------------------------------->

As an example, i give you the product_key of the tools i've downloaded:

crypto3.6: 0xC69AA96C | 0x378 (| is a logic OR ;-))

FxEdit : 0xFEDAADEF | 0x378

So you can now make a keygen for these tools if you want!!

During my investigations i have found two curious tests, just before the serial validation.

i found something like this:

if H(name) = 0x119A792

register the program to Gregory Braun/Software Design!!!

else

if H(name) = 0x0D5FCE3C

... do something !

else

compute val

id_key = H(name) + H(organization) + product_key

if serial entered = valid_key

register to name/organization

else

bad serial

end if

end if

end if

it looks like there is a 'magic' password that automatically register the program!, no need of a serial!!

I decided to find this 'magic' value!!

HOW TO DO THAT?

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

It would be fine to find a function H' such that H'(H(name)) = name !!

So all we'll have to to is to compute H'(0x119A792) to get the right name to enter!

If the H function is well designed, such H' doesn't exist but maybe H is not well designed...

So, i looked deep into the H function in order to find a non-ierative form of the function

First thing to notice: the calculated Hash depends on the length of the string.

if i compute H for a one character string the function returns:

H = table2[0]*table1[1]*1*P[0]

if i compute H for a two characters string the function returns:

H = table2[0]*table1[2]*1*

P[0] + table2[1]*table1[3]*2*P[1]

if i compute H for a three characters string the function returns:

H = table2[0]*table1[3]*1*P[0] + table2[1]*table1[4]*2*P[1] + table2[2]*table1[5]*3*P[2]

Let's call each hash function Hi(P) (i = length of string to hash, P is the password string, P[j] are the characters)

if I compute H for a 'i' characters string the function returns:

Hi = table2[0]*table1[i]*1*P[0] + table2[1]*table1[i+1]*2*P[1] + ... + table2[i-1]*table1[2i-1]*i*P[i-1]

woow!!

As you can see (but maybe not!) the values in front of P[j] are constants for a given Hi.

So i have precomputed them, and here comes the coefficients for the 21 first Hi:

H1 : 14260

H2 : 12524,22344

H3 : 14136,12936,3762

H4 : 38184,7448,10890,54656

H5 : 4712,21560,12078,55552,66490

H6 : 13640,23912,12276,48832,62220,19404

H7 : 15128,24304,10791,45696,46970,12348,35532

H8 : 15376,21364,10098,34496,29890,11844,40068,36800

H9 : 13516,19992,7623,21952,28670,13356,30240,30360,61065

H10: 12648,15092,4851,21056

,32330,10080,24948,105800,53100,41040

H11: 9548,9604,4653,23744,24400,8316,86940,92000,19116,87780,136730

H12: 6076,9212,5247,17920,20130,28980,75600,33120,40887,128820,55660,183024

H13: 5828,10388,3960,14784,70150,25200,27216,70840,60003,52440,148830,171120,130572

H14: 6572,7840,3267,51520,61000,9072,58212,103960,24426,140220,139150,138384,60372,164220

H15: 4960,6468,11385,44800,21960,19404,85428,42320,65313,131100,112530,63984,161460,99960,57240

H16: 4092,22540,9900,16128,46970,28476,34776,113160,61065,106020,52030,171120,98280,151368,62640,141600

H17: 14260,19600,3564,34496,68930,11592,92988,105800,49383,49020,139150,104160,148824,165648,40500,211456,217770

H18: 12400,7056,7623,50624,28060,30996,86940,85560,22833,131100,84700,157728,162864,107100,60480,230336,148155,169200

H19: 4464,15092,11187,20608,75030,28980,70308,39560,61065,79800,128260,172608,105300,159936,65880,156704,178500,196272,150670

H20:

9548,22148,4554,55104,70150,23436,32508,105800,37170,120840,140360,111600,157248,174216,44820,

188800,207060,206424,137085,211200

H21:

14012,9016,12177,51520,56730,10836,86940,64400,56286,132240,90750,166656,171288,118524,54000,219008,217770,187812,108680,271200,256368

for example, if you want to compute the Hash of a five letter word, you have to use H5:

H5=4712*P[0] + 21560*P[1] + 12078*P[3] + 55552*P[4] + 66490*P[5] where P[0..5] are the five password letters.

AND NOW?

********

We have to find the password such that Hi(P) = 0x119A792 and it seems that Hi' will be very, very hard to find.

The tasks seems awfull since the password could be any length so we don't know which Hi has been used to compute this magic value...

We have to solve H1 = 0x119A792, H2 = 0x119A792, H3 = 0x119A792, ...

This kind of equations are called 'Diophantine linear equations', and are very well known from mathematicians and

cryptographers.

Solving these kind of equations is possible but will ask you advanced mathematics and you will have to read (and understand!) some papers like 'An algorithm for solving a

diophantine equation with lower and upper bounds on the variables' by Karen Aardal, Arjen K. Lenstra, Cor Hurkens!!! or/and mastering Maple!

very, very difficult problem...what can i do since i can't find H' easily?

Two things:

Either a dictionnary or a brute force attack upon the hash function, the dictionnary attack is very easy to implement and should work...if the password is a word you can find in a dictionnary!

To do a brute force i have to test all the combinations of characters of arbitrary length since i don't know the password length and its composition, this is an incredible amount of words!!

It's totally impossible to do.

Hummm let's have a sit, it's time to go to the brain start menu!

have you said 'any length' for the password?

maybe it is not...

This exercise has a lot of constraints and now i will use my favorite method to solve difficult problems:

The relaxation!

This means that i will 'relax' some constaints to simplify the problem!

One of the constraints is the lengt

h of the password, another one is about the characters composing the password, they may be anything among 'a'...'z', 'A'...'Z', digits, special chars, i don't know what but i will do one hypothesis to simplify this last constraint:

I will assume that the password is composed of letters 'a'....'z', may be it's not true may be it is..;-)

Ascii values for a and z are: a=97, z=122, ok?

so the idea now is to minimize/maximize the Hi functions.

max value of Hi(P) is reached when all the password letters = 'z', P[0] = P[1] =...= P[i] = 122

min value of Hi(P) is reached when all the password letters = 'a', P[0] = P[1] =...= P[i] = 97

let's take the example:

H5=4712*P[0] + 21560*P[1] + 12078*P[3] + 55552*P[4] + 66490*P[5]

if P[0] = P[1] = ... = P[5] = 'z' = 122 then

H5 = 122 * ( 4712 + 21560 + 12078 + 55552 + 66490 ) = 122 * SUM(coefficients) = max H5

same thing when P[0] = P[1] = ... = P[5] = 'a' = 97, H5 = 97 * SUM(coefficients) = min H5

I have computed the sum of the coefficients for al

l Hi, in order to compute min and max values like this:

sum min val max val

H1 : 14260, 1383220, 1739720

H2 : 34868, 3382196, 4253896

H3 : 30834, 2990898, 3761748

H4 : 81178, 7874266, 9903716

H5 : 160392, 15558024, 19567824

H6 : 180284, 17487548, 21994648

H7 : 190769, 18504593, 23273818

H8 : 199936, 19393792, 24392192

H9 : 226774, 21997078, 27666428

H10 : 320945, 31131665, 39155290

H11 : 502831, 48774607, 61345382

H12 : 604676, 58653572, 73770472

H13 : 791331, 76759107, 96542382

H14 : 968215, 93916855, 118122230

H15 : 928312, 90046264, 113254064

H16 : 1120165, 108656005, 136660130

H17 : 1477141, 143282677, 180211202

H18 : 1583755, 153624235, 193218110

H19 : 1720224, 166861728, 209867328

H20 : 2060071, 199826887, 251328662

H21 : 2356213, 228552661, 287457986

H22 : 2492521, 241774537, 304087562

H23 : 2546487, 247009239, 310671414

The hash to find is TARGET1=0x119A792 = 18458514

take a look above and see w

here you can find TARGET1!!,

TARGET1 may be between min H5 and max H5 or between min H6 and max H6 and that's all.

WHAT DOES THIS MEAN?

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

it means that (with our hypothesis) TARGET1 is a 5 or 6 letters word !!

you can do the same thing for TARGET2 = 0x0D5FCE3C = 224382524, you will see that it's a very long pass phrase!!

and now all you have to do is solving the following equations:

H5 = 4712*p[0] + 21560*p[1] + 12078*p[3] + 55552*p[4] + 66490*p[5] = 18458514

and

H6 = 13640*p[0] + 23912*p[1] + 12276*p[2] + 48832*p[3] + 62220*p[4] * 19404*p[5] = 18458514

in order to find the solution!

Implement the algorithm described in the paper mentionned above and obtain the right values for p[j]!!

This is an elegant method...i'm waiting for your source code ;-)

For the guys (like me) who stopped maths to do computer programming when they were 8 we are going on with our brutal idea!!

we can know write a brute forcer that will try all the words from 'aaaaa' to 'zzzzzz',

if the length of the word we are trying is 5 we compute H5 else if it is 6 we compute H6.

LET'S DO IT NOW!

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

<------------------------------- Listing 2: C implementation of the crap above! ------------------->

//brute force attack upon gregory braun's hash function

//trying to find a collision!

//hard job ;-) done by J!M

#include <stdio.h>

#include <conio.h>

#include <string.h>

#include <stdlib.h>

#include <math.h>

unsigned char table1[54] = {

0x23,0x73,0x65,0x72,0x42,0x26,0x6E,0x7A,0x7C,0x6D,

0x66,0x4D,0x31,0x2F,0x35,0x28,0x21,0x73,0x64,0x24,

0x4D,0x71,0x2E,0x7B,0x73,0x5D,0x2B,0x73,0x46,0x6A,

0x74,0x4B,0x70,0x7A,0x53,0x64,0x74,0x7A,0x6F,0x58,

0x71,0x6D,0x62,0x5E,0x41,0x6C,0x40,0x64,0x76,0x3A,

0x73,0x3F,0x78,0x2F};

unsigned char table2[54] = {

0x7C,0x62,0x21,0x70,0x7A,0x2A,0x6C,0x73,0x3B,0x72,

0x6E,0x7C,0x6C,0x66,0x24,0x76,0x69,0x5E,0x41,0x78,

0x70,0x65,0x29,0x72,0x78,0x35,0x61,0x69,0x63,0x26,

0x39,0x2F,0x32,0x6D,0x35,0x6C,0x73,0x69,0x34,0x40,

0x30,0

x64,0x6D,0x5A,0x77,0x39,0x34,0x63,0x6D,0x71,

0x70,0x66,0x68,0x77};

int main() {

unsigned int i,j,k,r,l,line_count,target,accu,coeff[25][25];

double nb_passwords;

char password[6];

//compute equations' coefficients for H5 and H6

for (i=5; i<7; i++) {

for (j=0; j<i; j++) {

coeff[i-1][j] = table2[j]*table1[i+j]*(j+1);

}

}

//define the target

target = 0x0119A792;

line_count = 0;

//BRUTE FORCE ATTACK, test all combinations of words of 5 or 6 chars, about 320 000 000 words!!

for (i=5; i<7; i++) {

nb_passwords = pow(26,i);

l = 0;

for (j=0; j<i; j++) password[j] = 'a';

while ( l < nb_passwords ) {

k = l;

j = 0;

do {

r = k % 26;

k = floor(k/26);

j++;

password[i-j] = 0x61 + r;

} while ( k > 0 );

l++;

line_count++;

if (!(line_count % 10000)) {

printf("%u passwords processed\r",line_count);

}

accu = 0;

for (j=0; j<i; j++) accu += coeff[i-1][j] * password[j];

if ( accu == target ) {

pr

intf("\nTarget FOUND! with password: %s\n",password);

}

}

}

printf("\nHalt on fire!! press any key to quit\n");

getch();

return 0;

}

<--------------------------------------------------------------------------------------------------->

After a few minutes of intensive work the little program gave me 4 answers:

'dowtt', 'vrgpx', 'zippy', 'zulqu'

I think the magic value is 'zippy' but the three other words work well !!

Because H5('zippy') = H5('dowtt') = ... = 0x119A792 !!! we found what cryptographers call 'COLLISION':

two or more things that gave the same hash value.

One quality of a well designed hash function is to be collisions resistant.

There are two kinds of resistance: strong collision avoidance and weak collision avoidance...i will not explain here

the differences between these properties..may be in another tutorial?

and now all is done!!

Enter one of these four words into the registration name and press enter: YOU ARE REGISTERED! no need of a serial.

Yes, you can

say Thanks!!!

THAT'S ALL FOLKS!

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

Question? comments? you have found another way? the second password? mail to me:

zejim@netcourrier.com

See ya

ONE LAST WORD...

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

if you have to use a hash function in your programs keep the following things in mind:

-don't use your own algorithm!! use SHA, MD4, MD5, TIGER... it exists a lot of well designed hash functions.

-if you hash something, hash something complicated and/or very long to avoid dictionnary and brute force attacks.

---------------------------------------------------------------------------------------------------------------

PS: The dictionnary attack gave me 'zippy' in a few seconds ...

PS PS: If you plan to use crypto 3.6 to protect your valuable datas, i suggest you to read casimir's papers about

gregrory braun's cryptographic implementations it should freeze you!...