Let $H: M \to T\ $ be a collision resistant hash function. Which of the following is collision resistant: $ 1.H'(m) = H(m \big\| m)$

$2.H'(m) = H(m) \big\| H(0)$

$3.H'(m) = H(m) \oplus H(m)$

$4.H'(m) = H(H(m))$

$5.H'(m) = H(0)$

$6.H'(m) = H(|m|)$

$7.H'(m) = H(m)[0,\ldots,31] $ (i.e. output the first 32 bits of the hash)

Is the answer functions 1, (2) and 4?


1 Answer 1

  1. looks like it it is collision resistant, as hashes the message "twice"
  2. Is collision resistant, as a part of the digest is collision resistant.
  3. Is always $0$, so not collision resistant
  4. Collision resistant, as it hashes the message twice and outputs a valid hash of a valid message (the hash of the message)
  5. Always the same. Not collision resistant
  6. Always the same for messages of the same length. Not collision resistant.
  7. Depends on your definition of collision resistant. By itself it's a subset of a collision resistant hash function it is collision resistant if the subset is large enough. So from a theoretical point of view there's no faster attack than brute-force to find a collision, making it a collision resistant 32-bit hash function. From a practical point of view or if you consider it a n-bit hash function with n the digestsize of $H$ it's not collision resistand as one can find one with $2^{16}$ hash function calls.

So the answer is 1,2,4 and maybe 7.

  • $\begingroup$ 7 is not collision resistant. Even removing a single bit can cause your function to become non-collision resistant. As an example, let $G$ be a collision resistant hash-function. Then $H(m\Vert b) = G(m)\Vert b$ is also collision resistant, however cutting away the last bit gives a trivial attack. (any pair of messages that differ only in the last bit collide) $\endgroup$
    – Maeher
    May 17, 2015 at 12:05
  • $\begingroup$ @Maeher, so you're telling me that SHA-224 (uses the 224 leftmost bits of the SHA-256 output) is not collision resistant, because this is meant to be the exact same case here. (with lower numbers) $\endgroup$
    – SEJPM
    May 17, 2015 at 12:14
  • $\begingroup$ All I'm saying is that collision resistance does not follow in general. There can of course be instances of $H$ where $H'$ is collision resistant. It just doesn't follow in general. I.e., the collision resistance of SHA-224 does not follow from the assumption that SHA-256 is collision resistant. However we assume a lot more about SHA-256 than just collision resistance. $\endgroup$
    – Maeher
    May 17, 2015 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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