Finding input for bitwise operation with known result.

Question

Considering the following situation.

x ^ (((x << 0xf) & 0xffffffff) & 0xefc60000) = y

If result y is known, is it be posible to find the unknown value of x ? If so, how can it be done? All I know that value x =< 0xffffffff

Answer 1

Yes, $x$ is uniquely determined by $y$.

Using a property of XOR, we have

$$(x << 15) \land {\rm 0xefc60000} = x \oplus y$$

where it is understood that we take everything as $32$-bit bitvectors. The lowest $15$ bits of $x << 15$ are all $0$, and so are the lowest $17$ bits of the constant ${\rm 0xefc60000}$. Therefore, the lowest $15$ bits of $x \oplus y$ must be $0$; that is to say, the lowest $15$ bits of $x$ can be directly extracted from the lowest $15$ bits of $y$.

Once the lowest $15$ bits of $x$ are known, the upper $17$ bits of $x$ can be determined by examining the upper $17$ bits of the constant and the result. If the constant ${\rm 0xefc60000}$ has a $0$ at bit $b$, then $x[b] = y[b]$. For instance, bits $15$ and $16$ of $x$ must be equal to bits $15$ and $16$ of $y$, respectively. On the other hand, if the constant has a $1$ at bit $b$, then $x[b] = y[b] \oplus x[b - 15]$. For instance, bit $17$ of $x$ equals the XOR of bit $17$ of $y$ with bit $2$ of $x$.

Answer 2

We have x^z = y or x = z ^ y, for some expression z. The lower 15 bit of z are known, so the lower 15 bit of x are known. This tells us bit 15 to 29 of z and with that we have bits 15 to 29 of x. This tells us bits 30 to 44 of z, so we have bits 30 to 44 of x and do on.

This works whenever the expression z only contains the value of x shifted left by at least one bit position, because that tells us one bit of x after the other.