# Is the XOR of hashes a good hash function?

### Definitions:

Let $$h$$ be a hash function with output size $$n$$ bytes. Suppose the file $$F$$ can be divided into chunks of size $$n$$ bytes $$F=f_0+f_1+\dots +f_i$$ where the operator "$$+$$" stands for concatenation (in real situations it is always possible to pad the file).

Is it safe, or is it collision resistant, to use the following hash function $$H$$?

$$H(F)=h(f_0)\oplus h(f_1) \oplus \dots \oplus h(f_i)$$

### Motivation:

Suppose we have two files $$F$$ and $$G$$, then:

$$H(F+G)=H(F) \oplus H(G).$$

In other words, this hash function $$H$$ is a homomorphic hash. It would be great if $$H$$ inherits all properties from $$h$$.

• Related question here. Sorry for the long read, it is not about homomorphic properties, but the answer explains why the result is not collision resistant. Combining hashes to form a new hash seems to be a relatively expensive operation if the result needs to be collision resistant, hence hash trees. Commented Jul 16 at 9:47
• Using a XOR operation encodes the idea that order doesn't matter and that you only care about items that are included an odd number of times. So it would be entirely appropriate to use a XOR of hashes in the context of an unordered set, where each item is guaranteed to appear at most once. However, I don't think its much appropriate for any other uses.
– Akh
Commented Jul 18 at 1:29
• See the NIST's Tuple hash Commented Jul 21 at 11:52

This hash function $$H$$ can be broken (collisions & second preimages can be found) in polynomial time. Here I am assuming that the number of "chunks" (number of terms in the xor) is variable, so in particular it can equal the number of output bits in the hash. If instead the number of "chunks" is fixed then the other answer here describes the best-known attack, which still does not leave much hope for this construction.

See this answer and also the original source, a paper by Bellare & Micciancio (see appendix A).

I may be missing something, but it seems to me like your construction is trivially not collision resistant.

In particular, for arbitrary blocks $$x_0 \neq x_1$$, each of size $$n$$ bytes

$$H(x_0 + x_1) = h(x_0) \oplus h(x_1) = h(x_1) \oplus h(x_0) = H(x_1 + x_0)$$

thus producing a collision.

• This also applies to second preimage.
– iBug
Commented Jul 17 at 19:22

An answer from real life: I was computing a hash for a tuple (p, q) as hash(p) xor hash(q). This worked fine for years until a user applied it to a dataset in which p was equal to q about 90% of the time (think p = list price, q = discounted price), which meant that 90% of the tuples had a hash code of zero. (This was a hash used for indexing, not for cryptographic purposes.)

• I saw that practice at least in "Fluent Python". There must be some straightforwardly better generic construction by now. Commented Jul 17 at 12:24
• Thanks for your testmony, I fell better knowing I am not the only one that made this mistake. At least I do not did it in production cryptographic environment. Commented Jul 17 at 14:53
• @DannyNiu: Python updated their documentation several years ago to remove the recommendation of using bitwise XOR, and replaced it with hash((p, q)), which ultimately runs this code. Commented Jul 17 at 16:20
• @Kevin it seems still problematic since one needs delimeters, and this is why NIST specially designed the Tuple Hash so that people don't make mistakes blindly. Commented Jul 21 at 11:50
• @kelalaka: It's not supposed to be a cryptographic-strength hash. It's supposed to be fast. See this reference for more information. For example, Python hard-codes hash(1) == 1 and the same for most other small integers, so that a dictionary with small integer keys uses perfect hashing. Commented Jul 21 at 19:02

This kind of additive combination is vulnerable to Generalized Birthday style of attacks, as proposed by Wagner and worked on by others. If you have an $$\ell-$$ fold sum $$h(f_1)\oplus h(f_2) \oplus \cdots \oplus h(f_{\ell})=z$$ where $$z \in \{0,1\}^d$$ you can use a divide and conquer recursive attack to find a pre-image of $$z$$ with time and memory complexity essentially of the order $$\widetilde{O}(2^{d/(1+\lfloor \log_2 \ell \rfloor)})$$ where the notation $$\widetilde{O}$$ hides logarithmic factors. For a related question see here

Edit: As in the other answer, if the number of terms is equal to the number of bits the attack is polynomial time.