This started as a comment to CodeinChaos's answer, but did not fit. I'm trying to regurgitate, in layman's terms, my understanding of the consequences on $\operatorname{SHA-256d}$ of the paper he quotes: Yevgeniy Dodis, Thomas Ristenpart, John Steinberger, Stefano Tessaro: To Hash or Not to Hash Again? (In) differentiability Results for H2 and HMAC, in proceedings of Crypto 2012.
This paper does NOT imply that we could determine with sizable advantage over a random choice whether a black box with $256$-bit input and output is a Random Oracle, or implements $\operatorname{SHA-256d}$, using $2^{64}$ queries to that black box, without knowing the initialization value used by $\operatorname{SHA-256}$ (we assume it is replaced by a random $256$-bit value), and using much less computational work than necessary to break $\operatorname{SHA-256}$ with sizable probability. In other words, $\operatorname{SHA-256d}$ remains a secure Pseudo Random Function in that standard definition of the term. That's proven by the standard argument: a distinguisher (in that definition) able to break $\operatorname{SHA-256d}$ can be turned into one able to break $\operatorname{SHA-256}$ with only twice as much queries.
Nevertheless, the paper shows that we can devise protocols involving a hash where using $\operatorname{SHA-256}$ is safe; but using $\operatorname{SHA-256d}$ is entirely unsafe (with negligible effort, not $2^{64}$). An example is this protocol designed to provide mutual proof that each party has made some minimum number of evaluations of some $256$-bit hash function $H$ (note: Alice performs the odd steps, and the next even step is performed by Bob with roles reversed):
- Alice draws a random $256$-bit $A_0$ and sends it to Bob, together with the minimum number $k_A\in[2^8..2^{18}]$ of evaluations of $H$ that she wants Bob to perform;
- Bob draws a random $256$-bit $B_0$ and sends it to Alice, together with the minimum number $k_B\in[2^8..2^{18}]$ of evaluations of $H$ that he wants Alice to perform;
- Alice sets $\hat B_0$ and $\hat k_B$ to what she got at step 2., and terminates the protocol with failure if $\hat k_B>2^{18}$;
- Bob sets $\hat A_0$ and $\hat k_A$ to what he got at step 1., and terminates the protocol with failure if $\hat k_A>2^{18}$;
- Alice repeats for $j=1\dots\max(k_A,\hat k_B)$:
- If $A_{j-1}=B_0$, terminate the protocol with failure;
- compute $A_j=H(A_{j-1})$;
- compute $\hat B_j=H(\hat B_{j-1})$;
- Bob repeats for $j=1\dots\max(k_B,\hat k_A)$:
- If $B_{j-1}=A_0$, terminate the protocol with failure;
- compute $B_j=H(B_{j-1})$;
- compute $\hat A_j=H(\hat A_{j-1})$;
- Alice sends $\hat B_{\hat k_B}$ to Bob;
- Bob sends $\hat A_{\hat k_A}$ to Alice;
- If what Alice got at step 8. is different from $A_{k_A}$, she terminates the protocol with failure; else she declares success;
- If what Bob got at step 7. is different from $B_{k_B}$, he terminates the protocol with failure; else he declares success.
When $H$ is $\operatorname{SHA-256}$, this protocol is safe for both Alice and Bob. However if $H$ is $\operatorname{SHA-256d}$, defined as $x\mapsto \operatorname{SHA-256}(\operatorname{SHA-256}(x))$, there is a simple "mirror" attack for Bob:
- at step 2., Bob computes and sends $B_0=\operatorname{SHA-256}(A_0)$ and $k_B=k_A-1$ where $A_0$ and $k_A$ is what he got at step 1.; this will pass the test performed by Alice at step 3.; and pass the tests she performs at step 5., with about the same negligible odds of failure as if Bob had chosen $B_0$ at random;
- at step 8., Bob computes and sends $\operatorname{SHA-256}(\hat B_{\hat k_B})$ where $\hat B_{\hat k_B}$ is what he got at step 7.; this will always pass the test Alice performs at step 9.!!
This strategy allows Bob to apparently perform his duties with computational effort about a single evaluation of $\operatorname{SHA-256d}$, by circumventing the tests performed by Alice at step 5., which intend was to prevent Bob from choosing $B_0$ as one of the $A_j$ so that most of his work could in fact be done by Alice.
The paper (and the above example, which is inspired from the paper) implies that with a definition of indifferentiability from a Random Oracle sufficiently strong to support a security proof of certain protocols (in particular: mutual proof-of-work protocols) under the assumption that a hash used by this protocol is secure, indifferentiability of $H^2:x\mapsto H^2(x)=H(H(x))$ does not follow from indifferentiability of $H$.
That shows in particular that the definition of a practically secure hash as a random public member of a Pseudo-Random Function Familly characterized by: "even a computationally unbounded adversary can not distinguish, with constant positive advantage over a random choice, if a black box with $n$-bit output implements a random member of the family, or a RO, with a number of queries to the black box polynomial in $n$" (or: "asymptotically less than the birthday bound $O(n^{1/2})$" ) is NOT a measure of security suitable for proving practical security of such protocols.
The paper proceeds to show that $\bar H(x)=H(H'(x))$ where $H'$ is a variant of $H$, is indifferentiable from RO, assuming $H$ and $H'$ are, under a definition of indifferentiability suitable for that goal.
One way of seeing this is that the composition of two random members of a PRFF is secure, but the composition of twice the same random member is not secure w.r.t. an adversary with access to an oracle implementing that random member, which is unavoidable in practice.
Update: although BitCoin involves proof-of-work using a hash, and $\operatorname{SHA-256d}$, I would be extremely surprised if there was some devastating attack due to the use of that hash.
SHA-256d(x)
asSHA-256(SHA-256(0^512 || x))
instead. $\endgroup$