37
$\begingroup$

The bitcoin wiki says:

Bitcoin is using two hash iterations (denoted SHA256^2 ie "SHA256 function squared") and the reason for this relates to a partial attack on the smaller but related SHA1 hash. SHA1's resistance to birthday attacks has been partially broken as of 2005 in O(2^64) vs the design O(2^80). While hashcash relies on pre-image resistance and so is not vulnerable to birthday attacks, a generic method of hardening SHA1 against the birthday collision attack is to iterate it twice. A comparable attack on SHA256 does not exist so far, however as the design of SHA256 is similar to SHA1 it is probably defensive for applications to use double SHA256. And this is what bitcoin does, it is not necessary given hashcash reliance on preimage security, but it is a defensive step against future cryptanalytic developments. The attack on SHA1 and in principle other hashes of similar design like SHA256, was also the motivation for the NIST SHA3 design competition which is still ongoing.

I don't understand how hashing twice would prevent a birthday attack considering that finding a collision after the first hash would trivially entail a collision after the second hash.

Is it because you have to compute the hash twice thus slowing the process down or is there a more significant reason?

$\endgroup$
  • 2
    $\begingroup$ I suppose this question is not a duplicate of yours, but they are very related. My thinking is that the bitcoin wiki is incorrect as a collision single SHA1 (or SHA256) would also be a collision on double-SHA. $\endgroup$ – mikeazo Jan 5 '17 at 16:45
  • 1
    $\begingroup$ P.S. here is the 2005 paper. $\endgroup$ – mikeazo Jan 5 '17 at 16:46
  • 2
    $\begingroup$ It doesn't help at all. Double hashing protects against length extension attacks, but as far as I know, those don't affect bitcoin anywhere. $\endgroup$ – CodesInChaos Jan 5 '17 at 17:05
52
$\begingroup$

A collision in any hash function gives a collision in a "squared" variant of the hash function. This is easy to see. If hash(x)==hash(y), then hashing the outputs will also be the same.

So the wiki entry is wrong. To see the real purpose of the double hash see this question and answers.

$\endgroup$
  • 2
    $\begingroup$ Additionally, the converse is true: if we have a collision in the "squared" variant of the hash function, we can find a collision in the base hash (either in the first or second hash). $\endgroup$ – fgrieu Apr 1 '17 at 4:58
12
$\begingroup$

Strictly speaking, hashing twice might actually increase the chances of a collision. If there is a hash collision of two outputs of the hash function then any string that has that colliding hash will be a new collision.

Actually, it's easier to give an example: For a terrible hypothetical hash function F... F("Alice") -> "aaa" F("Bob") -> "bbb" F("aaa") -> "ccc" F("bbb") -> "ccc" F(F("Alice")) == F(F("Bob"))

$\endgroup$
  • 1
    $\begingroup$ Indeed, iterating a hash $n$ times makes collisions about $n$ times as likely. Of course, $n$ times a negligibly small probability is, for any practical values of $n$, still negligible -- especially since reaching that probability also takes $n$ times as much computation. In particular, note that observing an SHA-256$^n$ collision necessarily implies observing a collision for plain SHA-256 at some stage of the iterated hashing. Since the latter isn't likely to ever happen, neither is the former. $\endgroup$ – Ilmari Karonen Jan 7 '17 at 17:28
  • $\begingroup$ @IlmariKaronen hmm, I wouldn't say it's that linear, rather it depends on a property I don't know. If a hash algorithm mapped 1:1 when hashing inputs of the length of the digest then it wouldn't increase probability. If it has a 2:1 ratio, the probability is 2^n. So for ratio of x:1 it is x^n, assuming there isn't an asymmetric cyclic property. Essentially, I said might because the odds entirely depend on the characteristics of the hash function, we can only safely say that it won't ever /decrease/ the probability. $\endgroup$ – Kaithar Jan 7 '17 at 22:23
  • $\begingroup$ The linear scaling is an approximation, but a pretty good one. If we model each iteration of the hash with a different random function, then the probability of at least one collision among $k$ inputs hashed $n$ times with a $b$-bit hash is $1-\exp(\frac12n(k^2-k) \log(1-2^{-b}))$. As long as $n(k^2-k) \ll 2^b$, this is well approximated by $\frac12n(k^2-k)2^{-b}$, and the same condition should also suffice to ensure that treating the iterations as independently random is a valid approximation (since the probability of any input occurring on two different iterations will be negligible). $\endgroup$ – Ilmari Karonen Jan 7 '17 at 23:05
  • $\begingroup$ @IlmariKaronen honestly I'm not following the math right now, but I don't see how you can get a sensible linear behaviour. Repeated iterations of the hash create a tree, hence the power scale. Also, the point I'm making about property... let's say there's two bad has functions: A () { a = bytes[-1]; for byte in bytes { a = (a+byte)%256}; return a; }; B () { a = 10101010b; for byte in bytes { a = a xor byte }; return a; }... in the case of A there's a 2:1 ratio, B is 1:1 $\endgroup$ – Kaithar Jan 10 '17 at 21:07

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.