Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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$.

share|improve this answer
    
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 at 17:13
1  
@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. $\;\;\;\;\;\;\;\;$ –  Ricky Demer Apr 28 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 –  SOJPM Apr 28 at 17:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.