2
$\begingroup$

I am trying to find a value of X (32 bits) such that ((X XOR a)+b)<<3 = (X+c) XOR d. <<3 means shift left 3 bits. a,b,c and d are all constants which have been determined elsewhere.

However, I don't want to brute force the full 2^32 combinations. I was told solving it 3 bits by 3 bits from the MSB on the left hand side would help however this feels off to me.

Say I fix the first 3 MSB. This with the left shift that means that the 3 LSB will be fixed, leading to the next 3 bits and so on. It seems to me that fixing any 3 straight bits will end up with all of X being solved. Are 8 tries really all I need to solve this equation?

There's also the possibility that the values of a,b,c and d at the time might create an unsolvable equation too. If I don't find it within the 8 (or more tries if my above paragraph is wrong) it's safe to ditch this and try new values of a,b,c,d right?

$\endgroup$
1
$\begingroup$

Actually, you want to solve it from the LSB side.

First, solve for the 3 LSBs of X; we can see that the 3 LSBits of the left hand side of ((X XOR a)+b)<<3 = (X+c) XOR d doesn't actually depend on X (and there's no propogation anywhere from the higher order bits of X, so they can be ignored for now), so it's effectively a simple equation, easily solved.

Then, solve for the next 3 LSBs of X; again the 6 LSBits left hand side doesn't depend on those bits (it does depend on the 3 LSBits of X, but we already know those); again, that portion of X is easily solved.

So, just keep on iteration until we have all the bits of X.

One thing we can see from this process is that there is always exactly one solution for X for any (a, b, c, d) values.

$\endgroup$
  • $\begingroup$ So it's just 8 tries before i ditch for the next set of values? $\endgroup$ – watisit Mar 7 '16 at 17:47
  • $\begingroup$ Yes (except there'll always be a solution). Or, even easier, you don't need to guess; just evaluating ((((X XOR a)+b)<<3) XOR d) - c will give you the next 3 bits of X $\endgroup$ – poncho Mar 7 '16 at 18:21
  • $\begingroup$ Just to check, I do mean that the 3 MSB will affect the 3 LSB when they shift left so there is propagation isn't there and they do depend on X? $\endgroup$ – watisit Mar 8 '16 at 5:49
  • $\begingroup$ @watisit: I'm not sure what you're saying (I suspect you want check where you place negation); it's just that we know that the 3 lsbit of ((X XOR a)+b)<<3 will be 0, no matter what X is (assuming << really is 'shift left' and not 'rotate left') $\endgroup$ – poncho Mar 8 '16 at 14:54
  • $\begingroup$ It's rotate, i chose the wrong word. $\endgroup$ – watisit Mar 8 '16 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.