Taking half of a X bits hash key as secure as using a X/2 bit hash function?

Question

This question comes from a (nitpicking) comment by me in this SO question.

I said that using the half of the output from a 256 bit hash function is worse than using a 128 bit hash function. My reasoning is that the contract of the 256 bit function takes into account the full length output so you can find more collisions in the first half of the 256 bits output than you would in a 128 bit hash function.

As I saw here Is truncating a SHA512 hash to the first 160 bits as secure as using SHA1? that that could not be applied to SHA so I was wrong there but in a more broad scenario, does it provides the same security taking the half of the output from an X bit hash function than using a X/2 hash function?

Answer 1

It is unlikely that a secure X-bit hash function's X/2-bit truncation would not be X/2-bit secure.

For example, suppose you have a faster than $2^{128}$ second preimage attack on the 128-bit truncation of a 256-bit hash. Then you can run that attack $2^{128}$ times and expect to find a second preimage for some value of the full 256-bit hash, so that hash does not have 256-bit second preimage resistance (at least for some definitions of second preimage resistance).

However, the same argument does not apply to collision resistance: even if you can get a collision for the first half you need $2^{X/2}$ such pairs before you expect a collision in the second half. The birthday bound does not apply because you cannot compare different first-half collisions to each other.

(Collision resistance of the whole hash does put a bound on the multicollision resistance of the first half. If you had a $2^{X/4}$-collision in the first half, you would expect a collision among them in the second half.)

So theoretically it could be easy to find a collision for the first half, but no easier than brute force to find a collision for the whole. However, because real world hash functions use the same function to derive the whole hash value, any weakness affecting only the first half would be unlikely.

For Merkle-Damgård hashes in particular, a truncated hash means you actually have a wide-pipe construction, which has some advantages over an untruncated hash of the same length. So you would expect e.g. SHA-512/256 to be at least as strong, if not stronger than SHA-256.