# Why Might XOR's Lead to Hash Functions Lacking 2nd Pre-image Resistance?

My hash function is as follows:

1. Cut the string in half (assume even length of 2m)
2. XOR's the two halves together
3. 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$.

• Thank you very much for both your edits (does this place support Latex?) and your contribution. I feel like I can sort of reason about these hash functions a little bit but that I don't have any real proof. Maybe it could be useful to show that for a given XOR value, there are a family of n strings that, when XOR'ed together, give that result? – jkovba Apr 28 '15 at 17:13
• @jkovba : $\;\;\;$ This place does support LaTeX. $\:$ There will be $2^m$ pairs of length-m $\hspace{1.33 in}$ strings whose XORs are the target value. $\;\;\;\;\;\;\;\;$ – user991 Apr 28 '15 at 17:32
• @jkovba Well I messed with the first edit (did $h(x) \neq h(x')$ instead of $h(x)=h(x')$), so the second followed. I extended the answer, I hope this answers your follow-up question – SEJPM Apr 28 '15 at 17:44