13

I just read some code that applies a series of transformations to a 4 byte integer. I'm curious to know if the following function is invertible.

f(y) = y^(y>>11)

A general doubt I have, is the thought process involved when trying to find the inverse functions whenever a series of instructions are given. Do you have a methodology for approaching these kinds of problems?

4
  • 1
    Your function is mathematically invertible (in the sense that its left-inversion exists) because it is a monotonic function, but I do not know that the left-inversion is computable or not. In a more strict case, if y is stored in 4 bytes and f(y) is stored in less than 4 bytes then this function is not invertible because of the pigeon-hole principle. Jan 3, 2014 at 11:41
  • In general, the computation of an arbitrary sequence of instructions is not invertible because much information is lost along the execution of these instructions. Jan 3, 2014 at 11:48
  • @tathanhdinh In general perhaps, but many functions are specifically designed to be invertible, such as the type blah is asking about here.
    – Antimony
    Jan 3, 2014 at 15:50
  • At worst, since the y space is limited (4 byte int) you can do an exhaustive search on f(y) Jan 10, 2014 at 0:34

4 Answers 4

14

A good way to quickly find if a function f() has an inverse or not, is trying to find two elements of the initial domain x and y such that x!=y and f(x)==f(y).

If such couple of elements exist, you cannot distinguish them in the target domain of f and, thus, a reverse function cannot be built.

Looking at your example: f(x) = x^(x>>11), we can split the resulting bit vector into three parts (a first clear part from b31 to b21, a second Xored part with the first part (and thus that can be recovered) from b20 to b10, and a last third part that can be recovered with the clear text of the second part from b9 to b0):

x = (b31, ..., b0)

f(x) = (b31, ..., b21, b20^b31, b19^b30, ..., b10^b21, b9^b20, ..., b0^b11) 
         clear part   |      xored with clear part    | xored with previous part

So, in fact, no information is lost and a reversed function can be built from this. Here is a pseudo code explaining the principle of this reverse function:

g(x)
{
   /* Get the clear part */
   y = (x >> 20);

   /* Unmask the second part */
   z = ((x << 11) >> 21) ^ y;

   /* Unmask the third part */
   t = ((x << 22) >> 22) ^ z;

   /* Reassembling the whole thing */
   return (y << 20 + z << 11 + t);
  }
8
  • I am far from being sure of what I say... So, critics and raising contradiction in my reasoning are more than welcome.
    – perror
    Jan 3, 2014 at 14:06
  • Argh, I think we miss one or two bits of information as the first clear text part is only 10-bits long and the second and third parts are 11-bits long... Be careful with this solution I might have been wrong when building bit's index.
    – perror
    Jan 3, 2014 at 14:36
  • The only problem I can see is if the integer is signed and not unsigned. It isn't specified in the question. If it is signed the resulting b31 will be 0 independently of the original value of b31 which leads to data loss. For the unsigned case this method can be generalized all the way up to a shift of 1 bit, which is actually easier to illustrate. If you formulate your each of your bitvector elements as an equation system it becomes quite easy to see why this works. Unless I'm missing something. I haven't verified your code. Jan 3, 2014 at 14:42
  • Thanks for looking at it ! (the pseudo-code is only here to give an idea of the decoding method, it shouldn't be trusted).
    – perror
    Jan 3, 2014 at 14:45
  • 1
    No problem, I think your approach of reformulating as a bitvector, trying to formulate equations for each bit and then inverting the equation system is generally the way to go about solving these types of things. Jan 3, 2014 at 15:02
8

Perror already covered this particular case, but here are some general principles for inverting similar functions.

Note: all of this assumes the integer is either unsigned, or it is signed using two's complement and using unsigned shifts. In Java, two's complement is guaranteed. In C/C++, it is not guaranteed, but it's almost always the case in practice, and you can check the compiled assembly to be sure.

A sequence of transformations involving xor and bitshifts can be thought of as a linear (or affine if there are constants) transformation on a vector in (GF2)^32. Essentially, you have a 32 element vector of numbers mod 2, and since xor is addition mod 2, and you are multiplying it by a matrix.

So the transformation is invertible iff the matrix is invertible. Luckily this is usually the case. A function of the form x ^ (x >>> n) with n > 0 is a lower triangular matrix and hence invertible. Likewise, x ^ (x << n) is an upper triangular matrix and so also invertible. Since the product of invertible matrices is invertible, any sequence of such transformations will also be invertible.

Note that a signed shift (>> in Java) is not necessarily invertible.

As for actually inverting it, the easiest way (though not necessary the fastest) is to simply calculate the transformation matrix entries, then perform Guassian elimination (no rounding errors in a finite field).

You'll often see other operations mixed in as well. Addition and multiplication can be thought of as operations in the ring modulo 2^32. With two's complement, it doesn't matter whether you're using signed or unsigned numbers. Addition by a constant is simple: just subtract the constant. Multiplication by any odd constant is also invertible: just multiply by the multiplicative modular inverse. You can find code to calculate this online, or just take pow(c, (2**31)-1, 2**32) if you're doing Python.

Multiplication by an even constant loses information, so it cannot be fully inverted. Likewise, a combination of additions with the same effect won't be either. For example x + x is not invertible, since it's equivalent to x * 2. x + (x<<4) is invertible, because it is equivalent to x * 17.

Due to the fact that the composition of affine transformation is also affine, you can save time by just multiplying through all such operations and then inverting it in a single step.

Bitwise ands and ors always lose information except in the trivial case, so they won't be invertible. But usually they are used to select part of the information for combination in a lossless manner, so the overall expression is still invertible. For example x ^ ((x & 555) * 4) is invertible even though two of the individual components of the expression are noninvertible operations.

A couple other things you might see. Operations in GF(2^32) are basically the same as regular addition and multiplication except there's no carry. This is typically used in CRCs. Addition (which is just xor) and multiplication by any nonzero number are invertible, using the same technique as before.

Substitution boxes (or sboxes) - these are designed to be invertible, but normally don't have any particular structure. Typically these are expressed as a table lookup, with a precomputed table for the inverse as well. If not, you can always make your own inverse table, assuming the inputs aren't too big.

2
  • I like this answer - if only you had left out that last comment ;)
    – Till
    Jan 3, 2014 at 22:48
  • @Till Sorry, I'll remove it.
    – Antimony
    Jan 4, 2014 at 2:13
5

I try to give a very superficial answer for your question because I am quite sure that there are other treatments for this problem.

Mathematically, the function f(y) = y^(y >> 11) is invertible in the sense that the left-inversion, namely a function g so that y = g(f(y)) exists, because f is an injective function. However that does not mean we can easily find the inversion function because it may be uncomputable, namely in this case we cannot give an algorithm calculating g. Practically, there may exist some computable methods to "approximate" it (maybe abstract interpretation ?).

In a more strict case (but maybe more practical), if the value of y is stored in 4 bytes and the value of f(y) is stored in less than 4 bytes then the function is trivally not invertible because of the pigeon-hole principle. Moreover, the computation of an arbitrary sequence of instructions is not invertible in general because of the information-lost along the execution, to see that we can consider an example (in pseudo-assembly code)

f(y) = 
 mov eax, y
 xor eax, eax
 return eax

then f(y) is not invertible because the output is always 0 regardless of the input. However if we can store some "state values" (i.e. not only the output and the instruction sequence) along the execution of instructions then the inversion is possible, this idea has been proposed everywhere, e.g. in GDB Reverse Debugging or in this paper.

Edit: I got a mistake here because I thought ^ is an exponentation (so I doubt that the inversion is uncomputable in the general case) but in fact it is bitwise exclusive.

2
  • -1. The inverse is easily computed.
    – Antimony
    Jan 3, 2014 at 15:24
  • You are absolutely right, the answer of @perror shows that clearly. In fact, when giving a response for the answer above, I thought that the operator ^ is exponentiation (so I doubt that it is uncomputable in general) but in fact it is bitwise exclusive. Jan 3, 2014 at 15:36
2

this python functions works for any value:

def f_inv(x):
    mask= (1<<11) - 1
    a= []
    while x>0:
        a.append(x&mask)
        x >>= 11
    if not a:
       return 0
    z= a.pop()
    while a:
        z= (z<<11) | ((z&mask)^a.pop())

    return z

the trick is to split the number in 11 bit chunks, then starting with the highest keep xorring with the previous (higher) chunk. and or everything together.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.