Why Might XOR's Lead to Hash Functions Lacking 2nd Pre-image Resistance? My hash function is as follows:


Cut the string in half (assume even length of 2m)
XOR's the two halves together
Take the result of the XOR and pass it to a function (a one-to-one and "onto" function) that simply does:


$f: \{0, 1\}^m \rightarrow \{0, 1\}^m$

I'm being asked to prove why this hashing strategy is not second pre-image resistant (though it is pre-image resistant) but I'm getting hung up.

I know a 2nd pre-image means finding $x' \neq x$ s.t. $h(x') = h(x).$

I also know that different strings can result in the same XOR:

$1010 \oplus 1111 = 0101$ and so does $0000 \oplus 0101.$

I think I'm just lacking complete understanding of the concept.  Thank you in advance for your help.
Well, if you construct what you described you basically create a function $f: \{0,1\}^{2m} \rightarrow \{0,1\}^m$.

As you correctly pointed out these two strings give the same when xor'ed. So the messages $10101111$ and $00000101$ will result in the same xor and hence will get mapped to the same hash, resulting in a second preimage as you found two $x,x'$ with $x\neq x' \wedge h(x)=h(x')$.

Now let's see what happens if $x$ is fixed:

Assuming you're given a value $x \in \{0,1\}^{2m}$ for which you want to to construct $x'\in\{0,1\}^{2m}$ with $x \neq x' \wedge h(x) = h(x')$.
Now observe that $x_1 \oplus x_2 = x_1' \oplus x_2'$ (with $x_1, x_2$ being the first and second half of $x$) will give the same hash $h(x_1 \oplus x_2)=h(x_1'\oplus x_2')$.
Now for a given $x=x_1||x_2$ one can easily construct $x'=x_1'||x_2'$ by using the equation $x_1 \oplus x_2 \oplus x_1' = x_2'$ so one can arbitrarily choose half of the second preimage and can then compute the other half. As $x_1' \in \{0,1\}^m$ this yields $2^m$ second pre-images for any given $x$.