Given an hash H that is not collision resistant, for example 80-bit digest, if we use the following double hashing scheme: H(SHA2-256(x)).
Does this scheme increase the collision resistance?
1 Answer
$\begingroup$
$\endgroup$
5
Does this scheme increase the collision resistance?
No (at least, not if we assume that $H$ is not collision resistant because of the limited output size); the standard birthday attack (where you compute $2^{40}$ hashes, and look for a common value) still works. The only thing the initial SHA-256 does is make evaluating the hash a bit more expensive - it doesn't frustrate the attack in any other way.
And, in case you're wondering, we know how to search for such a collision without a memory that can store $2^{40}$ hashes...
-
$\begingroup$ I agree, what about inverting the scheme? For example SHA2-256(H(x))? I think that even in this case the attack simply consist in attacking the first hash with the birthday attack, so it's again 2^40 hashes. $\endgroup$– N-KJul 27, 2022 at 14:24
-
$\begingroup$ @N-K: you are correct; narrowing things anywhere to 80 bits allows a collision attack... $\endgroup$– ponchoJul 27, 2022 at 14:27
-
$\begingroup$ It doesn't even necessarily make the evaluation more expensive. If H is expensive to evaluate, it could be cheaper to evaluate SHA-256 on a long input and H only on the short hash. $\endgroup$– MaeherJul 27, 2022 at 15:31
-
$\begingroup$ I'd suggest "Not necessarily" where there is "No", because for some $H$ the answer is yes; e.g. for SHA-1 or MD5 the question's "scheme increases the collision resistance" by a factor over 1000. $\endgroup$– fgrieu ♦Jul 27, 2022 at 16:58
-
$\begingroup$ SHA-256(“80 bit hash”) is an 80 bit hash. $\endgroup$ Jul 31, 2022 at 6:22