Is double hashing collision resistant?

Question

Double Hashing can surely provides more security than only 1 layer of hashing, but does that necessarily mean it is more collision resistant? This question in a more math form: If H is a collision resistant hash function, is H(H(x)) for some x still collision resistant?

Answer 1

In fact it may even be worse for collision resistance because the output of the inner H is limited.

For example take function H which maps from {0,1}ⁿ → {0,1}ⁿ. (We restrict x to {0,1}ⁿ to make it easier to see.) Let's say the there are a, b from {0,1}ⁿ and c = H(a) = H(b). Which means H(c) = H(H(a)) = H(H(b)). When you have a collision in the first transformation, you can't unmake it.

If you don't have a collision in {0,1}ⁿ then the second transformation perform the same way.

Since we usually talk about hash functions as {0,1}^* → {0,1}ⁿ there are bound to be collisions in the first transformation and the second transformation may make it even worse.

Answer 2

In principle, the resulted hash function H(H(x)) is either less or equally collision resistant because

1. For the hash function H(x), for in each N unique pre-image lets assume there is one collision. which means there are two hashes being similar and H(H(x)) will not make it different.
2. For the hash function H(x), for in each N unique pre-image lets assume there is one collision. this will be true for H(H(x)) as well because H(H(x)) is nothing but H(fixed length strings). This makes there is more chances of collision.