Monday, 19 October 2015

Reversing Shift-XOR operation

Reversing Shift-XOR operation (when XORed with the same value)

The random number generator Mersenne Twister uses 624 internal states, each 32 bits, to generate the random numbers. If the internal states are known then the random numbers can be predicted. The major step involved in obtaining the random number from the internal states are a series of shift-XOR operations. If these operations are inverted, then the internal states can be found from the random numbers.

'>>' is the right shift operator (adds zeros to the left/MSB side) and '<<' is the left shift operator. '^' is the XOR operator.

Below the process involved in reversing a right shift-XOR operation is explained.

Let n = 3008349343, the shift value is 10 and (n ^ n >> 10) = 3009615726.
In binary :
10110011010011111100010010011111      n
00000000001011001101001111110001      n >> 10
10110011011000110001011101101110      n ^ n >> 10

From the above operations we can see the first 'shift'(=10 here) number of bits remain the same as it is XORed with 0's. Let us consider compartments of size 10; for a 32 bit number we have 3 compartments of size 10 and one of size 2.

The shifting operation and the reversing of the shift is diagrammatically represented in the figure below.

Thus, given the value 3009615726 and the shift value 10, we can reverse the shift-XOR operation to obtain 3008349343.

The same approach can be adopted for any shift value and for reversing the left shift-XOR operation also. The compartments size vary depending on the shift value.

The code for reversing the shift-XOR operations: