PDA

View Full Version : A and B = C how can I solve for B?


databus
January 9th, 2013, 14:48
I'm trying to do a keygen from crackmes.de and I'm not sure how to solve for B and for A using the AND instruction

I can do it manually with the truth table, and I can also convert it to a character array and try to solve it.

However, there has to be an easier way to do this (a way thats not overkill)

How can I solve for A if I have both B and C, and how can I solve for B if I have both C and A, using only bitwise operators? I couldn't find any formula to do this, and I know that no single operand can do it either.

Thanks

Indy
January 9th, 2013, 15:11
B(i) can have two values, if A(i) = 0.

databus
January 9th, 2013, 18:43
Quote:
[Originally Posted by Indy;94002]B(i) can have two values, if A(i) = 0.


Yes if A is 0 then B can be anything because the answer will be the same as far as I know, same vice versa.

But lets say that I have to solve a formula for AND
Let A = Multiple XOR operations
A AND 0x12345678 = 12244078

How can I find out A programically so that I can continue writing the keygen? In this specific keygen A or B will never be 0

naides
January 9th, 2013, 19:33
Answer is: You cannot.

AND is the prototype of a one way operation. If you know A and B, C is not ambiguous. But there is no inverse operation.

Example for simplicity single bit:

A & B = C
1 & 0= ? 0

but

A & B = C
? & 0= 0

A may well be 0 or 1.


If you apply this to a multi-byte number, there is no way you can deterministic-ally solve for A. Information is lost. The ONLY Boolean operation that is well behaved is XOR

databus
January 9th, 2013, 19:41
Quote:
[Originally Posted by naides;94005]Answer is: You cannot.

AND is the prototype of a one way operation. If you know A and B, C is not ambiguous. But there is no inverse operation.

Example for simplicity single bit:

A & B = C
1 & 0= ? 0

but

A & B = C
? & 0= 0

A may well be 0 or 1.


If you apply this to a multi-byte number, there is no way you can deterministic-ally solve for A. Information is lost. The ONLY Boolean operation that is well behaved is XOR


Okay, thank you. I will go about this another way.


I'm trying to get past the first check and it's this:

where s is an array of 8 uint values generated from the serial

check#1 is this:

v100 = (s[7] ^ ((s[7] ^ s[1]) & 0x6487169F))) ^ ( (s[3] ^ (s[6] ^s[3]) & 0x11258023) ^ 0x35059FC5 ) == 0x48A86FC4

The way I figure of doing this is to find the possible values of the and instructions so that it comes out to 0x48A86FC4

I've split it up like this:
s[7] = A
s[1] = B
s[3] = C
s[6] = D

(A ^ ((A ^ B) & 0x6487169F) ^ ((C ^ (D ^ C) & 0x11258023) ^ 0x35059FC5) == 0x48A86FC4

assuming X = (A ^ ((A ^ B) & 0x6487169F)
and Y = ((C ^ (D ^ C) & 0x11258023) ^ 0x35059FC5)

then X ^ Y == 0x48A86FC4

What should I look into so that I can learn how to solve these types of problems? I have a thirst for knowledge. Is boolean algebra what I'm missing? Is it possible to solve for A,B,C,D with given information?

Thanks

radix
January 10th, 2013, 05:33
Quote:
[Originally Posted by naides;94005]Answer is: You cannot.

AND is the prototype of a one way operation. If you know A and B, C is not ambiguous. But there is no inverse operation.


I agree, it's not possible to determine the original value - but it is possible to find a value for A so that A & B = C. Set A := C and you're done. You could also set A := (NOT B) OR C (which sets all bits which are cleared by the AND operation), if you want to have a diffent value for A.

There're some combinations of B and C which are not solvable, i.e. B = 2, C = 3, but it's easy to check.

radix

bilbo
January 10th, 2013, 17:10
Quote:
[Originally Posted by radix;94009]I agree, it's not possible to determine the original value - but it is possible to find a value for A so that A & B = C.

In fact, the crackme you are talking about (mopy's Simple math keygenme) was solved by MR.HAANDI using 3 degrees of randomness.
Best regards, bilbo

Maximus
January 11th, 2013, 16:58
Quote:
[Originally Posted by naides;94005]The ONLY Boolean operation that is well behaved is XOR


...NOT!

:P