How does this reverse-engineered algorithm work?

Question

The actual algorithm function is:

output[i] = ( (129 * input[i]) XOR input[i-1]) % 256 //input[-1] = 0

There are several solutions to this. The one that is usually done is along the lines of:

var output = [0, 129, 3, 129, 7, 129, 3, 129, 15, 129, 3, 129, 7, 129, 3, 129];
var outputToInputArray = function(array) {
  var input = [];
  var outputToInput = function(dig, lastInput) {
    var current = dig;

    while(true) {
      if (!((current ^ lastInput) % 129)) {
        return (current ^ lastInput)/129;
      }
      current += 256;
    }
  }

  for(var i = 0; i < output.length; i++) {
    input.push(outputToInput(output[i], i>0 ? input[i-1] : 0));
  }

  return input;
}

console.log(outputToInputArray(output));

However, I just came accorss:

output = [0, 129, 3, 129, 7, 129, 3, 129, 15, 129, 3, 129, 7, 129, 3, 129]
var input = [];
for(var i =0; i < output.length; i++) {
    lastInput = input.length < 1 ? 0 : input[i-1];
    input.push(((output[i] ^ lastInput) * 129) % 256);
}
console.log(input);

The idea to follow when asked to reverse a function is to algebraically reverse the function. However, the second solution seems to simplify the reversed function in a way that should not be mathematically valid! But it works! Please help!

P.S. Expected output is [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

Answer 1

Note: after writing up this answer, I re-read the answer by qxz, and realized that everything covered here is also covered in qxz's answer. But I've decided to post this anyways, since a slightly different format may be helpful to some.

To understand why this works, all you have to do is compute

y = (129 * x) % 256;  

for each x between 0 and 255. Start with the even numbers

for ( x = 0; x < 256; x += 2 ) {
    y = (129 * x) % 256; 
    console.log(y);
}

The output is

  0   0
  2   2
  4   4
  6   6
  8   8
 10  10
 12  12
 14  14
... ...

In other words, even numbers aren't changed when you multiple by 129 modulo 256.

The output for the odd numbers is

  1 129
  3 131
  5 133
  7 135
  9 137
 11 139
... ...
125 253
127 255
129   1
131   3
133   5
... ...

In other words, multiplying by 129 modulo 256 is the same as adding 128 to the number modulo 256. So when you do it twice you get the original number back: (x + 128 + 128) % 256 = x

The rest of the formula really doesn't have any effect on this. Modulo 256 drops any bits above bit 7, keeping the lower 8 bits. The XOR has no effect on the bits above bit 7, it simply inverts some of the lower 8 bits. Thus there's no interaction between the XOR and the modulo 256. The XOR only affects the lower 8 bits, and the modulo only affects the upper bits.

Which means that when reversing the calculation, you can do the XOR first to get the lower 8 bits back. And then multiplying by 129 modulo 256 either does nothing (if the number is even) or it adds 128 modulo 256 (if the number is odd). Either way, you get the original number back.

Answer 2

First of all, your "hash function" isn't really a hash function in the traditional sense. A hash function usually takes an input (which could be of variable size, such as a string) and transforms it into a single value of a fixed number of bits. This type of function cannot really be reversed, because many bits of data are lost in the conversion; you can't reconstruct 100 bits from 4 bits.

Your function transforms a list of bytes into another equal-length list of bytes. It looks like it takes the current input, runs it through the function x => (x*129)%256, and then xors it with the previous input.

The function f(x) = (x*129) % 256 is the interesting part. If the input is even, the output is the same number. If the input is odd, the output is the input with bit 7 (the 127ths place) inverted. (Try plugging in a few values yourself.) Thus, f(x) is it's own inverse; f(f(x)) == x.

Therefore, the whole "hash function" can be inverted like so:

• xor the current hash value with the previous input value, or 0 if the first one
• run the result through the f(x) function to invert the f(x) when the value was calculated
• repeat for each value

... which is what that last snippet of yours does. I'm not sure about the first one.