Is there a way to get the original value back after this hash function?

Question

Code:

for( int i = 0; i < 0x10; i++ ) {    
   serialvar = (((magic1 * i + serialvar) << 0x10) ^ serialvar) + 0x13371337;
   serialvar = (((i * magic1 + serialvar) >> 0x10) ^ serialvar) + 0x73317331;
}

I understand that in order to reverse something, everything must be done in reverse order. However, I am confused as this is very complicated and it seems like it requires a prior value in order to reverse the current value which would otherwise be impossible to get? And we're shifting bits, so there is a possibility that values are lost forever. I.e. if forward is x + 1 then backwards is x - 1.

Now, is it possible to reverse this loop to find the unknown value serialvar if we have the final value of serialvar?

Answer 1

Contrary to the answers here, this is solvable without any bruteforcing.

The loop and addition are easy to reverse. What remains is these 2 xor operations:

serialvar ^= (magic1 * i + serialvar) << 0x10;
serialvar ^= (i * magic1 + serialvar) >> 0x10;

Let's call the 0x10 low bits the low part and the 0x10 high bits the high part.

In the first operation it's easy to see the low part is unaffected. But it's also the only part that matters in this operation, because the high part gets shifted out. So this operation is actually it's own inverse.

The second operation is a little bit more complicated. This time the high part is unaffected. You almost don't care about the low part except the case when the low parts of the addition i * magic1 + serialvar overflow and add 1 to the high part of the sum.

So this operation always takes one of these 2 forms:

serialvar ^= (i * magic1 + (serialvar & 0xFFFF0000)) >> 0x10; // no overflow
serialvar ^= (i * magic1 + (serialvar & 0xFFFF0000) + 0x10000) >> 0x10;

Now each of these forms doesn't depend on the low part of serialvar, so each of them is it's own inverse. So you can simply try both of them and verify which is correct by applying the original operation.

The full code is as follows:

serialvar = key;

// compute an inverse
for (int i = 0xF; i >= 0; --i) {
    serialvar -= 0x73317331;

    unsigned int serialvar0 = serialvar ^ ((i * magic1 + (serialvar & 0xFFFF0000)) >> 0x10);
    unsigned int serialvar1 = serialvar ^ ((i * magic1 + (serialvar & 0xFFFF0000) + 0x10000) >> 0x10);

    if (serialvar == (serialvar0 ^ ((i * magic1 + serialvar0) >> 0x10)))
        serialvar = serialvar0;
    else
        serialvar = serialvar1;

    serialvar -= 0x13371337;
    serialvar ^= (magic1 * i + serialvar) << 0x10;
}

cout << hex << serialvar << endl;

// verification
for (int i = 0; i < 0x10; i++) {
    serialvar = (((magic1 * i + serialvar) << 0x10) ^ serialvar) + 0x13371337;
    serialvar = (((i * magic1 + serialvar) >> 0x10) ^ serialvar) + 0x73317331;
}

if (serialvar == key)
    cout << "success" << endl;

There's a possibility there could be multiple inverses if both checks succeed, but I didn't look into that as it's not really necessary.

Answer 2

This function is not completely reversible without brute forcing, but you only need to "brute force" a one-bit value. I'll start by expanding the operations slightly.

for( int i = 0; i < 0x10; i++ ) {    
  serialvar ^= (magic1 * i + serialvar) << 0x10;
  serialvar += 0x13371337;
  serialvar ^= (magic1 * i + serialvar) >> 0x10;
  serialvar += 0x73317331;
}

Obviously, += is reversible by applying -= with the same value. The operand is constant, so this is trivial.

Obviously, ^= is reversible by applying ^= again with the same value. Here, though, the operand is not constant.

Starting with the first one:

serialvar ^= (magic1 * i + serialvar) << 0x10;

Because the operand is left-shifted by 16, it will only take the low 16 bits of the expression magic1 * i + serialvar, and only toggle the high 16 bits of serialvar. That's easy: after this operation, (magic1 * i + serialvar) << 0x10 still produces the exact same value.

The second one is more complicated:

serialvar ^= (magic1 * i + serialvar) >> 0x10;

This one only changes the lower 16 bits of serialvar, and only the high 16 bits of magic1 * i + serialvar are taken, but because addition works with a carry, that still depends on the low 16 bits as well. You'll get (((magic1 * i) >> 16) + (serialvar >> 16) + carry) & 0xFFFF, where carry may be either 0 or 1.

Now, this part does have the potential for data loss. If magic1 * i is 534985191, and serialvar is 50712, the result is 55803. If magic1 * i is 534985191, and serialvar is 50719, the result is also 55803. So, there are some values for which you cannot recover the original serialvar.

However, since you know carry to be either 0 or 1, you can try both possibilities. If you get a correct result with 0, and not with 1, you have your answer. If you get a correct result with 1, and not with 0, you have your answer. If you get a correct result with both 0 and 1, print an error message and exit. Since this is a specially crafted program that's supposed to be reversible, that shouldn't happen.

(Disclaimer: I'm assuming magic1 and serialvar are unsigned int, and unsigned int has 32 value bits. The program is probably not intended to be portable.)

Answer 3

These types of function are largely one-way functions. The existence on one-way functions seems intuitively impossible, but are in fact very possible. In fact, all modern cryptography relies on such functions. The way that one-way function can exist is because many values map to the same value, for example:

1234 -> abc
2345 -> cde
4567 -> abc

Ok, so now if you have abc, and are trying to back up, where do you go, 1234 or 4567? By mapping many vaules onto one, you stop people from going backwards. Modern cryptography functions do this millions of times over thousands of steps. The only way to 'reverse' the process is by guessing a starting point and hoping you land at the right end point, and even then you can't be sure you really have the right value.

Your function is a good simple example of this kind of one-way function. You can try to "brute-force" it by guessing, but you can't really just "run the process backwards".

Edit:

After looking at this function more, with the help of @hvd, it looks like this particular function might be reversible if magic1*i doesn't lead to overflow. In that case the code would look like this:

for ( int i = 15; i >= 0; i-- ) {
    serialvar -= 0x73317331;
    serialvar = ((i * magic1 + serialvar) >> 0x10) ^ serialvar; //doesn't work... carry
    serialvar -= 0x13371337;
    serialvar = ((magic1 * i + serialvar) << 0x10) ^ serialvar; //reverse by doing again
}

This would only work if magic1*i is < 2^15. If you want to account for all possible values of magic1 you would have to follow a small tree that branches once at each of the >> lines, one bit gets clipped. So a 2^16 search area, which is actually quite small.

Answer 4

Yes. There are only 4 billion values of serialvar (assuming the type, which you omit, but is implied by the context). Many of them may not even be valid serial numbers. Compute the hash over all of them until you find the one you want.