Inverse And operation

Question

I'm trying to write a keygen to a crack me that I'm learning from and I got stuck. What happens there is pretty simple:

Let's say that I entered the password: "12121212"

XOR DWORD PTR DS:[ECX+EAX],1234567
AND BYTE PTR DS:[ECX+EAX],0E
ADD ECX,4
CMP ECX,8

As we can see, the first DWORD of the password (0x32313231, notice that x86 processors use little-endian layout) is being XORed with 0x1234567 so 0x32313231 ^ 0x1234567 results with 0x56771233. Then there is an AND operation on the first byte (0x56) of the manipulated password and 0xe which results with 0x6. After that, the program repeats the operations, this time on the second DWORD of the password.

My question is: I know I can reverse XOR but is it possible with AND operation?

Answer 1

While there's no way to know with 100% certainty what was the original value before the AND operation, you can find some possible values producing the same result, and sometimes that's enough.

Basically, for x & N = z, you can start from z and set any bits to 1 where you have are 0 in N. z itself will always work too.

For example, if we know that x & 0xE == 6, then at any of the following values of x will work: 6,7, 0x16, 0x17, 0x26, 0x27 and so on.

Answer 2

The answer is no. Unlike bitwise XOR, bitwise AND can't be reversed:

0 & 1 = 0
0 & 0 = 0

Both AND and OR are not reversible. This is in contrast to XOR and NOT operators which are reversible.