Reversing a hash of known hashing algorithm

I am sure this is a very easy thing to do but I am not sure how to go about solving a problem like this, So there is this hash function which operates on a message which is in the form of a byte array (each element is 8 bits long):

digest [i] = ( (129 * message[i]) XOR message[i-1]) % 256


The value of message[-1] is 0.

Now, I have a few samples :

message = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
digest = [0, 129, 3, 129, 7, 129, 3, 129, 15, 129, 3, 129, 7, 129, 3, 129]


Now I have noticed a few things, $129_{10} = 1000\;0001_2$ and multiplying it with a number greater than 128, does not change the lower 8 bits at all, except 255 and multiplying it with a number less than 128 does not change the lower 8 bits if it is even, and for odd, the $8^{th}$ bit is one rest is same. First, is this observation correct?

Second, how can one go about reverse engineering a hash function like this, so that given a digest, you can find out the message? Don't give me a direct solution, I am looking for an explanation and algorithmic way of doing it.

Thanks.

EDIT Another piece of information is that the length of message and digest is always 16 (bytes).

• Suggest using message[i+1], then define message[0] = 0 as your initial state. – user9070 Mar 22 '16 at 22:50

The i'th byte of the digest is a function of this byte of the message, and the previous byte.

So, to recover the original message from the digest, we just work our ways across the message, recovering each byte in succession.

First, we need to recover the first byte of the message. Because there is no previous byte of the message, the formula for the digest simplifies to:

digest[0] = ( (129 * message[0] ) % 256.


Question: since we know the value digest[0], how can we recover message[0],

Next, assume we know the first i bytes of the message, and now we're attempting to recover message[i]. We know the formula:

digest[i] = ( (129 * message[i]) XOR message[i-1]) % 256


And we know the values digest[i] and message[i-1]; how can we use this to recover message[i]?

One hint that may simplify things: if we have $A = 129 * B % 256$, then we also have $B = 129 * A % 256$; that's because $129 * 129 = 1 \pmod{256}$

• Your first formula is setting digest[0] to zero. It should be % 256 instead of % 129, shouldn't ? – Hilder Vitor Lima Pereira Mar 23 '16 at 11:41