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?
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ What specific threat do you expect to mitigate by hashing twice? $\endgroup$– Stephen TousetDec 2, 2014 at 19:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
$\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