Tuts 4 You ## Recommended Posts Having this code:

```int BruteForceFunction(void * BruteWayPtr)
{
int BruteWay = *(int*)BruteWayPtr;
printf("Brute way = %d\r\n", BruteWay);
time_t _tm = time(NULL);
struct tm * curtime = localtime (&_tm);
printf("start time %s\r\n", asctime(curtime));

KnowSum = 0;
unsigned int A = 1;
unsigned int B = 2;
unsigned int C = 3;
unsigned int D = 4;
unsigned int M = {0x11111111, 0x22222222, 0x33333333, 4, 5, 0, 0, 0x33333333};  // 7FFFFFFF max int
unsigned int Mn;
unsigned int F = 0;  // {0x1, 0x2, 0x3, 4, 5, 0, 0, 0x92222222};
unsigned int B_a;
// {0x11111111, 0x22222222, 0x33333333, 4, 5, 0, 0, 9999};
// {0x1, 0x2, 0x3, 4, 5, 0, 0, 0xFFFFFFFE}; - takes lot of time also 0xEFFFFFFE
printf("Initial values:\n");
printf("A = %d\n", A);
printf("B = %d\n", B);
printf("C = %d\n", C);
printf("D = %d\n\n", D);

for (int i=0;i<8;i++)
{
printf("i = %d\n", i);
F = C xor (B or (not D));  // first time we calculate the operation in F
// F = B[i-1] xor (B[i] or (not B[i-2]))
printf("Operation F = %d\n", F);
printf("M[%d] = %d\n", i, M[i]);

unsigned int known_sum = A+M[i];
printf("A+M[i] = %d\n", known_sum);

F = F+A+M[i];  // A = B[i-3]
printf("F = %d\n", F);
printf("A = %d\n", A);
printf("B = %d\n", B);
printf("C = %d\n", C);
printf("D = %d\n", D);

if ((i-3)>=0)
{
if (A!=B_a[i-3])  // A value is lost!!!
printf("IMPOSSIBLE!!!\n");
}

if ((i-2)>=0)
{
if (D!=B_a[i-2])
printf("IMPOSSIBLE!!!\n");
}

if ((i-1)>=0)
{
if (C!=B_a[i-1])
printf("IMPOSSIBLE!!!\n");

}

A = D;
D = C;
C = B;

B_a[i] = B;
printf("B[%d] = %d\n", i, B);

printf("F bef. rotate = %d\n", F);
unsigned int lr_val = leftrotate(F, s[i]);
printf("lr_val = %d\n", lr_val);
printf("B bef = %d\n", B);

B = B + lr_val;
printf("B after = %d\n\n", B);
}

printf("Final values:\n");
printf("A = %d\n", A);
printf("B = %d\n", B);
printf("C = %d\n", C);
printf("D = %d\n\n", D);

unsigned int lr_values_1 = B-C;  // lr_value for last round
printf("lr_values_1= %d\n", lr_values_1);

unsigned int lr_values_2 = C-D;  // lr_value for ante-last round
printf("lr_values_2= %d\n", lr_values_2);

unsigned int lr_values_3 = D-A;  // lr_value for ante-ante-last round
printf("lr_values_3= %d\n", lr_values_3);

unsigned int F_1 = rightrotate(lr_values_1, s[8-1]);
printf("F_1= %d\n", F_1);
unsigned int F_2 = rightrotate(lr_values_2, s[8-2]);
printf("F_2= %d\n", F_2);
unsigned int F_3 = rightrotate(lr_values_3, s[8-3]);
printf("F_3= %d\n", F_3);

int B_old1 = B-lr_values_1;  // B
// C = D and D = A;
int F_x1 = D xor (B_old1 or (not A));  // operation on last round
int know_sum1 = F_1-F_x1;

printf("A[%d]+M[%d] = %d \n\n", 8-1, 8-1, know_sum1);

// where A is B computed at the end of i = 3 = round 4:
// that means that A depends on M, M, M and M
// in this specific case we have 8 dword of messages and only 4 dwords of hash
// so 8*4 = 32 bytes of message over 4*4 = 16 bytes of hash
// as result we have many 32 bytes messages which would generate same hash!!!
// How we proceed: we choose (random) M, M, M and M
// and we calculate M, M, M and M

unsigned int Ban;

// Just initial values of A, B, C, D:
unsigned int An = 1;
unsigned int Bn = 2;
unsigned int Cn = 3;
unsigned int Dn = 4;

for (int i=0;i<1;i++)  // compute Ban
{
F = Cn xor (Bn or (not Dn));
F = F+An+Mn[i];

An = Dn;
Dn = Cn;
Cn = Bn;

Ban[i] = Bn;
Bn = Bn + leftrotate(F, s[i]);

// B is calculated only from intial values!!!
// B depends on M
// B depends on B and M
// ....
}

// Just initial values of A, B, C, D:
An = 1;
Bn = 2;
Cn = 3;
Dn = 4;

unsigned int F1,F2,F3,F_x4;
unsigned int dif1_div, dif2_div, dif3_div, dif4_div;

// -----------------------------------------
printf("\nThird way: random M, M, M and M\n");
printf("Calculated M, M, M and M\n");

Mn = 4;
Mn = 5;
Mn = 0;
Mn = 0;

// Ban is known
Ban = B_old1;
Ban = Ban-lr_values_2;  // B_old2
Ban = Ban-lr_values_3;  // B_old3

// We make some M and M substractions making calculations like if M=0 and M=0
// For original MD5 these are not needed!!!
unsigned int lr_values_2_Clean = lr_values_2-leftrotate(M, s);
unsigned int lr_values_3_Clean = lr_values_3-leftrotate(M, s);

// The final value after adding operation, A and M[i]
unsigned int F_2_Clean = rightrotate(lr_values_2_Clean, s);
unsigned int F_3_Clean = rightrotate(lr_values_3_Clean, s);

// We clean final C (Ban) by substracting leftrotate(M, s) and leftrotate(M, s)
unsigned int Ban7_Clean = Ban-leftrotate(M, s)-leftrotate(M, s);
unsigned int Ban6_Clean = Ban7_Clean-lr_values_2_Clean;
unsigned int Ban5_Clean = Ban6_Clean-lr_values_3_Clean;

unsigned int F_1_Clean = Ban6_Clean xor (Ban7_Clean or (not A));  // operation on last round
unsigned int F1_Clean_mul = leftrotate(F_1_Clean, s);
unsigned int F1_mul = leftrotate(F_x1, s);

unsigned int B_final = B-(F1_mul-F1_Clean_mul)-(Ban-Ban7_Clean);
// lr_values_1_Clean depends on M
unsigned int lr_values_1_Clean = lr_values_1-(F1_mul-F1_Clean_mul);
F_1 = rightrotate(lr_values_1_Clean, s[8-1]);  // i = 7;
F_x1 = Ban6_Clean xor (Ban7_Clean or (not A));  // operation on last round
know_sum1 = F_1-F_x1;
printf("B+M = %d \n", know_sum1);  // B and M relations
// B is computed from M, M and M

unsigned int lr_val1_bak = 0;
unsigned int Ban1Test = 0;
unsigned int lr_val2_bak = 0;
unsigned int Ban2Test;
unsigned int lr_val3_bak = 0;
unsigned int Ban3Test = 0;

int IsFound = 0;
// The trick is to substract from know_sum1 the Ban
unsigned int know_sum1_B0 = (Cn xor (Bn or (not Dn)))+An;
unsigned int MultiPly = leftrotate(know_sum1_B0, s)+Bn;  // Bn is just B initial value
unsigned int know_sum1_NoB0F = know_sum1-MultiPly;
// i=1: A = 4, 3, 2 = D, C, B =>
know_sum1_NoB0F -= leftrotate(Dn, s);  // i = 1
know_sum1_NoB0F -= leftrotate(Cn, s);  // i = 2
know_sum1_NoB0F -= leftrotate(Bn, s);  // i = 3

know_sum1_NoB0F -= leftrotate(Mn, s);  // i = 3
printf("knowSum NoB0 = %d \n", know_sum1_NoB0F);

// Just initial values of A, B, C, D:
unsigned int Al = 1;
unsigned int Bl = 2;
unsigned int Cl = 3;
unsigned int Dl = 4;

unsigned int F_x4_Orig = 0;
unsigned int Lr_value_4_New = 0;
unsigned int F4_Hot = 0;

// lr_values_1_Clean - last round: i = 7

// on ante-last round:
F_2 = _rotr(lr_values_2_Clean, s);  // i = 6
F_3 = _rotr(lr_values_3_Clean, s);  // i = 5

F1 = (Cn xor (Bn or (not Dn)))+An;
int Count = 0;

/* From the sum result: Ban+Mn = know_sum1:
Mn start value = know_sum1 and they are two options:
A. substract 1 and gows until at zero
B. add 1 and gows until at int max value
Sometimes A. find a value is seconds; sometimes B.
*/

//Mn7Val1 = total;
Mn=know_sum1;
KnowSum = know_sum1;

while (Mn!=0)
{
if (BruteWay==1)
{
M7Brute1 = Mn;
Mn--;
}
else
{
M7Brute2 = Mn;
Mn++;
}

Ban = know_sum1-Mn;

// on ante-last round i = 6:
Ban = F_2-(A xor (Ban6_Clean or (not Ban)));  // since Mn=0

// on round i = 5:
Ban = F_3-(Ban xor (Ban5_Clean or (not Ban)));  // since Mn=0

// On round i = 4:
F_x4 = (Ban xor (Ban or (not Ban)));
F_x4_Orig = _rotr(Ban5_Clean-Ban, s);
Ban = F_x4_Orig-F_x4-Mn;  // Mn is known

// On round i = 3:
dif4_div = _rotr(Ban-Ban, s);
F4_Hot = (Ban xor (Ban or (not Ban)))+Bn;
if (Mn!=(dif4_div-F4_Hot)) continue;  // sanity check for round with i=3

// Calculation of Mn-Mn (messages)
dif1_div = _rotr(Ban-Ban, s);
Mn = dif1_div-F1;

lr_val1_bak = leftrotate(F1, s);
Ban1Test = Ban+lr_val1_bak;
if (Ban!=Ban1Test)
{
printf("WTF!!!\n");
Count++;
continue;
}
*/

dif2_div = _rotr(Ban-Ban, s);
F2 = (Bn xor (Ban or (not Cn)))+Dn;  // 	F = C xor (B or (not D));

Mn = dif2_div-F2;

/*
lr_val2_bak = leftrotate(F2, s);
Ban2Test = Ban+lr_val2_bak;
if (Ban!=Ban2Test)
{
printf("WTF!!!\n");
Count++;
continue;
}
*/

dif3_div = _rotr(Ban-Ban, s);
F3 = (Ban xor (Ban or (not Bn)))+Cn;
Mn = dif3_div-F3;

/*
lr_val3_bak = leftrotate(F3, s);
Ban3Test = Ban+lr_val3_bak;
if (Ban!=Ban3Test)
{
printf("WTF!!!\n");
Count++;
continue;
}
*/

// Just initial values:
Al = 1;
Bl = 2;
Cl = 3;
Dl = 4;

for (int j=0;j<8;j++)
{
F = Cl xor (Bl or (not Dl));
F = F+Al+Mn[j];
Al = Dl;
Dl = Cl;
Cl = Bl;
Bl = Bl + _rotl(F, s[j]);

}

if ((Al!=A)||(Bl!=B)||(Cl!=C)||(Dl!=D))
{
continue;
}
else
{
IsFound = 1;
break;
}

}

time_t _tm_end = time(NULL);
curtime = localtime (&_tm_end);
printf("end time %s", asctime(curtime));

double dif = difftime (_tm_end,_tm);
printf ("Elapsed time is %.2lf seconds.\n", dif );

if (IsFound==1)
{  	// We finnaly have M, M, M values
printf("Brute way = %d\r\n", BruteWay);
printf("M = %d \n", Mn);
printf("M = %d \n", Mn);
printf("M = %d \n", Mn);
printf("M = %d \n", Mn);
return 1;
}
else
{
printf("Failed to find M value!!!\n");
return 0;
}

}

```

And creating a thread for BruteWay1 = 2:

KnowSum = 0;
mRes = timeSetEvent(10, 0, &TimerProc, 0, TIME_PERIODIC);

int BruteWay1 = 2;
if (thrd_create(&thread, BruteForceFunction, &BruteWay1) != thrd_success)

int BruteWay2 = 1;
BruteForceFunction(&BruteWay2);

What happens here is that "Brute way = 1" stacks at "99%" and is only executed after "BruteWay1 = 2" is finished.
I don't understand the reason; at start everything seems to works like it should.
The CPU usage over threads with ProcessExplorer.zip shows similar usage (~50%).
Also for other examples I've noticed that with 1 thread it took 4 seconds and with two threads it took 7 seconds;
shouldn't these values have appropriate values or even the same after all I have two CPU cores??? Maybe the printf statements are causing the other thread to always yield while one always keep printing new messages as to prevent text interleave it must wait until the end of the buffer is safe to write to and not locked, but then it just keeps ending up waiting again since the code on the first thread only yields to the second in printf which is what is blocking it.  I am not sure but it seems like this is the case here as there is no other synchronization. It doesn't have anything to do with printf statements,
I was also wrong: the program doesn't stacks at 99% is just slow, way to slow then I was expected,

Comparing speed time:

Way too humble difference, after all my CPU has two cores.

Edited by CodeExplorer (see edit history)