0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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...

$\endgroup$
5
  • $\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-K
    Jul 27, 2022 at 14:24
  • $\begingroup$ @N-K: you are correct; narrowing things anywhere to 80 bits allows a collision attack... $\endgroup$
    – poncho
    Jul 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$
    – Maeher
    Jul 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$
    – gnasher729
    Jul 31, 2022 at 6:22

Your Answer

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

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