Inverting functions HOWTO

Question

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?

Answer 1

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);
  }

Answer 2

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.

Answer 3

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.

Answer 4

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.