Suppose a message $m$ is divided into blocks of length $160$ bits: $m > = M_1 || M_2 || ... || M_l$ And define $h(m) = M_1 \oplus M_2 \oplus ... \oplus M_l$

Which of the three desirable properties of a good cryptographic hash function does h satisfy? Show that it does not satisfy the other two.

Three desirable properties of a cryptographic hash function http://en.wikipedia.org/wiki/Cryptographic_hash_function#Properties

I feel like if there is only one, like the question states, it has to be the first one, preimage resistance. However, given a hash $h = 000....0$ I can find a bunch of $m$'s that could give that particular hash. Maybe since there are lots of solutions you can't pin point the specific $m$ that gave that value?

What do you think?


I believe that this is a poorly written question: such an $h$ obviously doesn't have either preimage resistance, second preimage resistance or collision resistance.

The inability to rederive the specific value of $m$ based on its hash is not an interesting property; it's pretty much true of any function which generates an output shorter than its input.

I don't know where you're getting these questions from; based on this question, I'd suggest you look elsewhere.

  • 1
    $\begingroup$ Old Exams, thanks for the confirmation of my worst fears! $\endgroup$ – Bobby S Dec 16 '11 at 17:43
  1. ⊕ is a relatively simple operation, so $h(x)$ can be calculated quickly.

  2. preimage resistant: No. Given $h(x)$, we can construct $M_1||M_2||...||M_l$ in an arbitrary manner. Since we know h(m), we have a 160 bit string of 0s and 1s. For each 0 in $h(M)$, we can assign an even number of 1s (or all 0s) to that position in the l blocks. For each 1 in $h(m)$, we can assign any odd number of 1s to that position in the l blocks.

  3. Strongly collision-free: No. We are only looking for $M_1 \nleqq M_2$ but $h(M_1) = h(M_2)$. We do not have to base this on a given h(m). So, we can arbitrarily construct $M_1||M_2||...||M_l$ for some number of blocks $l$. We could change an even number of 1s from a given position to 0, from 0 to 1, etc. and this changes the message but not the hash value.

  • 1
    $\begingroup$ Stackexchange uses markdown not latex for formatting posts. It has limited latex support for formulas enclosed in $ (mathjax). $\endgroup$ – CodesInChaos Jul 9 '16 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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