6
$\begingroup$

How much security does double hashing add regarding collisions and preimages? Is it helpful to iterate a hash function even more times than two?

For example, can MD5 be fixed (in practice) by applying the hash function twice (MD5(MD5(x)))? Also, Bitcoin uses SHA256(SHA256(x)). Does this add security in practice?

I understand that iterating a function many times can reduce the number of possible outputs. Also, the function might enter a cycle. Is that a problem with just a few iterations (such as two)?

(This question is not about storing passwords securely.)

$\endgroup$
  • 2
    $\begingroup$ Well, it adds a non-positive amount regarding collisions. $\;$ $\endgroup$ – user991 Aug 27 '15 at 10:06
  • $\begingroup$ @RickyDemer I have added a paragraph about that. It is my understanding that a true PRF would become weaker but a broken hash might become stronger because it is harder to "reverse" using analytical means. $\endgroup$ – boot4life Aug 27 '15 at 10:10
  • $\begingroup$ "fun" observation: If $x_1\neq x_2$ and $MD5(x_1)=y=MD5(x_2)$, then $MD5(MD5(x_1))=MD5(y)=MD5(MD5(x_2))$. $\endgroup$ – SEJPM Aug 27 '15 at 10:29
  • $\begingroup$ @SEJPM true... So there is no added resistance against collisions at all it seems because you can just find one in the basic hash function. $\endgroup$ – boot4life Aug 27 '15 at 10:47
  • 1
    $\begingroup$ You could probably still hope for some improvement on the collision side if you "double hash" as $MD5(x || MD5(x))$, where $||$ is the concatenation. At least the trivial observation on the plain double hashing doesn't apply anymore. $\endgroup$ – Calodeon Aug 27 '15 at 11:10
7
$\begingroup$

With respect to collisions, hashing twice can not increase security, because if $x$ and $x'\ne x$ collide for $H$, that is $H(x)=H(x')$, then $H(H(x))=H(H(x'))$. Otherwise said, any collision for $H$ is a collision for the double hash $H\circ H$. It is therefore trivial to exhibit collisions for $\operatorname{MD5}\circ\operatorname{MD5}$. Hence the answer to the question as worded in its title is NO.

With respect to preimage, hashing twice demonstrably does not harm security (from a preimage for $H\circ H$ one can make a preimage for $H$, simply by applying $H$), and tends to improve it for practical functions. In particular, one hypothetically able to build preimages for $\operatorname{MD5}$ only for 512-bit messages would likely have a hard time extending that to $\operatorname{MD5}\circ\operatorname{MD5}$.
Handwaving argument: if for some 128-bit $v$ one could find a 512-bit $\operatorname{MD5}\circ\operatorname{MD5}$ premiage $m$, then the easilly computed $m'=\operatorname{MD5}(m)$ would be a 128-bit $\operatorname{MD5}$ preimage of $v$, which arguably is harder to find than a 512-bit $\operatorname{MD5}$ preimage of $v$, since for a given $v$ it is expected that there are about $1$ premimage of the former kind, and about $2^{384}$ of the later.

One area where double-hashing increases security is length extension attack. $\operatorname{SHA-256}$ is trivially vulnerable to that, $\operatorname{SHA-256}\circ\operatorname{SHA-256}$ is not.

In some use cases, hashing twice can destroy security, including for common hashes; an example is given here; in summary: some proof-of-work protocol safe when using $H$ is entirely unsafe using $H\circ H$.


With usual hash functions (or ideal ones), hashing twice does not dramatically reduce the output space (it is reduced by a factor about $1-1/e\approx0.63212$); that makes accidental collision slightly less unlikely, and it is mostly immaterial in practice. It does not make collisions easier to exhibit, since the amount of invocations of $H$ expected necessary to exhibit a collision by whatever brute force method can not decrease (if it did, that would be trivially usable to exhibit collisions for $H$ at reduced cost).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! I just gathered 15 rep points and was now able to upvote your answer. Do you have any kind of further evidence or detail on how much strengthening can be achieved against preimages (assuming a kind of broken hash function like MD5)? (The collision subquestion is solved as far as I'm concerned.) $\endgroup$ – boot4life Aug 27 '15 at 14:09
  • $\begingroup$ @boot4life: see added Handwaving argument $\endgroup$ – fgrieu Aug 27 '15 at 16:19
  • $\begingroup$ That's actually quite a smart thought! Would it be fair to say that iterating the hash kind of increases the number of rounds in the hash algorithm? It's not the same thing but should be close. $\endgroup$ – boot4life Aug 27 '15 at 17:17
  • $\begingroup$ @boot4life: your justification is quite different from mine, and just as based on reasonable argument rather than proof. Indeed hashing twice makes twice as many rounds, which can increase security in some contexts; on top of that there is a major irregularity in the middle of the rounds, as we finalize the first hash, pad it, and reenter it as message for the other rounds, which arguably could help preimage security too - at least we have proof that it does not doom it! $\endgroup$ – fgrieu Aug 27 '15 at 18:12

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.