Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Suppose I have two hash functions, of which neither (or only one) is collision resistant, and I want to create a new hash function by taking the bitwise exclusive or (XOR) of the results of those two functions.
Is it possible for this new function to be collision resistant? I suppose not, but I'm not sure why.
The answer to your edited question is "yes, it is possible".
As a trivial example, let $H$ be an ideal $k$-bit hash function. Due to the existence of the generic birthday attack, $H$ provides only about $k/2$ bits of collision resistance — that is, an attack can, on average, find a collision after about $2^{k/2}$ hash function evaluations. Denote the output of $H$, given the input $x$, as $$H(x) = (b_1(x), b_2(x), b_3(x), \dotsc, b_k(x)),$$ where $b_i$ denotes the $i$-th bit of the output.
Now define the $k$-bit hash functions $$H_L(x) = (b_1(x), b_2(x), b_3(x), \dotsc, b_{k/2}(x), 0, 0, \dotsc, 0)$$ and $$H_R(x) = (0, 0, \dotsc, 0, b_{k/2+1}(x), b_{k/2+2}(x), \dotsc, b_k(x)).$$
That is, $H_L$ is the same as $H$, except that the last $k/2$ bits of the output are replaced by zeros, and $H_R$ is the same as $H$ except that the first $k/2$ bits are replaced by zeros.
Now, clearly, either of $H_L$ or $H_R$ alone only provides $k/4$ bits of collision resistance. If, say $k = 128$, then $H$ may still be considered practically collision-resistant (effort to break = $2^{64}$), but finding collisions for $H_L$ or $H_R$ would be trivial (effort to break = $2^{32}$).
However, by construction, $H_L(x) \oplus H_R(x) = H(x)$. Thus, the hash function obtained by XORing the outputs of $H_L$ and $H_R$ is identical to, and thus equally strong as, the original hash $H$.
That said, this doesn't necessarily mean that the XOR of two hash function always has better collision resistance than the original hashes — in fact, it's easy to construct examples where the collision resistance of the XORed hashes is worse than that of either original hash. (For a simple example, let $H$ be a collision-resistant hash, and let $H_A = H_B = H$. The either of $H_A$ or $H_B$ alone is collision-resistant, but $H_A(x) \oplus H_B(x) = 0$ for all $x$!)
More to the point, for real-world hash functions, it depends on why and how the collision resistance of the original hashes is compromised. In some cases, XORing two hashes might improve their collision resistance; in other cases, it might not, or it might even make it worse.
To add some more perspective to this: this question has been studied quite extensively in the context of hash function combiners. A combiner is simply a function that gets (black-box) access to two hash functions and implements a new hash function. The question there is: does a combiner with "short output" exist that is robust for collision resistant hash functions? Here robust means that the combiner should be collision resistant if at least one of the two input functions is. Short in this context means that the combiner's output length is more than super-logarithmically shorter than the combined output of the two input hash functions. Your XOR example falls into this category, as the output is only $n$ bits, in contrast to $2n$ bits for the concatenation combiner (assuming the two input hash functions have $n$-bit outputs).
In a 2008 Crypto paper by Pietrzak it was shown that no such combiner exists that is good for "arbitrary" input functions, where good is defined as "collisions on the combiner can be reduced to collisions on both input functions".
To sum up, the XOR can work for specific functions. However, there can be situations where you start with two perfectly collision resistant functions and end up with a function that is not secure.
