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$
  • 2
    $\begingroup$ What specific threat do you expect to mitigate by hashing twice? $\endgroup$ – Stephen Touset Dec 2 '14 at 19:47
11
$\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$
  • $\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$ – Peter Krauss Apr 20 '18 at 23:40
  • $\begingroup$ If you preefer to comment as an other question, see crypto.stackexchange.com/q/58542/42893 $\endgroup$ – Peter Krauss Apr 21 '18 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.