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

****************** 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!...