# Is this hash function almost XOR universal?

Consider this hash function:

The key $K$ is $2^n$ bits. The message $M$ is divided into $2^n$ bit blocks. Arithmetic is performed modulo $2^{n+1}$. The hash is defined by:

• $H_0 = 1$.
• $H_{i+1} = (2M_i + H_i)\times (2K + 1)$ where K is a (secret) hash key.
• Output $H' = \frac{H_{|M|/2^n}}2$

Is this hash (the iterative one) almost-XOR-universal?

Is this hash almost-XOR-universal?

No.

Consider the two 1 block messages $M = \{0\}$ and $M' = \{2^{n-1}\}$.

We have:

$$H(M) = ((2\cdot 0 + 1)(2K+1) \bmod 2^{n+1}) /2 = K$$

and

$$H(M') = ((2\cdot 2^{n-1} + 1)(2K+1) \bmod 2^{n+1})/ 2 = K + 2^{n-1} \bmod 2^n$$

As $H(M) \oplus H(M') = 2^{n-1}$ has a nontrivial probability of being true, $H$ is not almost-XOR-universal.

Similar logic (using the two messages $\{0, 2^{n-1}\}$ and $\{2^{n-1}, 0\}$) will show that $H$ isn't even almost-universal.