Reverse function

Question

I have been trying to reverse a quite simple looking function. the function is presented in assembly: (Argument is loaded into AX)

AND AX, 0xFFFE (round down to even number)
MUL AX (Multiply AX by AX ; the result is represented as DX:AX)
XOR AX,DX

The function can be described as: H(X) = F(X & 0xFFFE); F(X) = ((X * X) mod 2^16) xor ((X * X) div 2^16)

Calculated all of the values from 1 to 2^16 and plotted on matlab in order to "see" some function.

Can anyone help me find an answer to this? (when given y what is the argument x). It might be that for some values there is more than one answer, so narrowing it down is my goal.

Thanks, Or.

Answer 1

It's a hash function.
You can't reverse a hash function, because the whole point of it is that it's a one way function.
The multiply is clearly reversible, it's the xor that's not. By combining the low and high part of the multiplication you lose information.

As you can see in the plot there are some white spaces, because there are 2^16 spaces in that plot that means there are also different input values that hash to the same value.
This is common in a hash function.

The only way to 'reverse' it is to build a lookup table that translates output values into possible input values. However you will find that for every output values that be 1 or more input values.

An even number x an even number is always a multiple of 4.
So the low 2 bits are always 0, ergo the low 2 bits of the result are bits 16+17 of the multiplication.
Bits 2..15 are a mix of bits 2..15 xor bits 18..31.
A quick simulation shows 24350 unique outputs ergo on average 1.34 0.34 duplicates for every input value, not bad.
The maximum number of collisions is 6, but most numbers don't collide.

For all those numbers that don't collide you can uniquely lookup your input value in the lookup table (all this disregarding odd input values obviously).