40
$\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?

Improve this question
$\endgroup$
3
  • 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
    Commented Jan 5, 2017 at 16:45
  • 1
    $\begingroup$ P.S. here is the 2005 paper. $\endgroup$
    – mikeazo
    Commented Jan 5, 2017 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
    Commented Jan 5, 2017 at 17:05

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 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 ♦
    Commented Apr 1, 2017 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"))

Improve this answer
$\endgroup$
4
  • 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
    Commented Jan 7, 2017 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
    Commented Jan 7, 2017 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
    Commented Jan 7, 2017 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
    Commented Jan 10, 2017 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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