5
$\begingroup$

Double hashing can surely provide more security than only one layer of hashing but does that necessarily mean it is more collision resistant? This question in a more mathematical form: If $H$ is a collision resistant hash function, is $H\circ H\colon\;x\mapsto H(H(x))$ still collision resistant?

$\endgroup$
1
  • 3
    $\begingroup$ What specific threat do you expect to mitigate by hashing twice? $\endgroup$ Dec 2, 2014 at 19:47

1 Answer 1

13
$\begingroup$

Yes. Let $H$ be a collision resistant hash function and assume that one can find a collision $(x,y)$ for $H\circ H$, that is, $x$ and $y$ with $x\neq y$ and $H(H(x))=H(H(y))$. Consider the results $H(x)$ and $H(y)$ of applying $H$ once to both inputs. Then either

  • $H(x)=H(y)$, hence $(x,y)$ is a collision for $H$; or
  • $H(x)\neq H(y)$, hence $(H(x),H(y))$ is a collision for $H$.

Therefore, obtaining a collision for $H\circ H$ allows an attacker to derive a collision for $H$, showing the claim.


What could suffer is the output distribution of $H\circ H$ as opposed to $H$, that is, even if $H$ is uniformly distributed on the set of all bit strings $\{0,1\}^\ast$, the distribution of $H\circ H$ may be arbitrarily bad. For instance, when $H$ is not bijective on its image (which is the usual case), there are always hash values that are not in $H\circ H$'s image while others may have lots of preimages. However, this doesn't break collision resistance in the cryptographic sense, as outlined above.

$\endgroup$
2
  • $\begingroup$ Hi. About the collision probability, $P_c[H]$, in optimal hashes (eg. SHA1), it increases with double hash? That is, $P_c[H\circ H] > P_c[H]$ ? $\endgroup$ Apr 20, 2018 at 23:40
  • $\begingroup$ If you preefer to comment as an other question, see crypto.stackexchange.com/q/58542/42893 $\endgroup$ Apr 21, 2018 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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