"Weaknesses" in SHA-256d?

Question

According to this answer, "SHA-256d" was proposed in one of the Ferguson/Schneier books like so:

SHA-256d(x) = SHA-256(SHA-256(x))

Apparently, the motivation for this construction is to avoid length extension attacks.

Incidentally, SHA-256d is the hash function forming the core of Bitcoin.

According to the comment on the answer linked above, "some minor weaknesses" are known in SHA-256d. What are they?

Answer 1

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 H² 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):

1. 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;
2. 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;
3. 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}$;
4. 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}$;
5. 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})$;
6. 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})$;
7. Alice sends $\hat B_{\hat k_B}$ to Bob;
8. Bob sends $\hat A_{\hat k_A}$ to Alice;
9. If what Alice got at step 8. is different from $A_{k_A}$, she terminates the protocol with failure; else she declares success;
10. 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.

Answer 2

Distinguishing $H^2$ from a random oracle (essentially an ideal hash) is much cheaper that it should, namely $2^{64}$ for $\operatorname{SHA-256d}$. This doesn't lead to any practical attacks, but it hurts security proofs relying on indistinguishably. It is easy to avoid this problem by using distinct prefixes for the inner and outer hash, so I see little reason to use $H^2$ in practice.

Distinguishing SHA-256d from a random oracle

$\operatorname{SHA-256d}(m) = \operatorname{SHA-256}(\operatorname{SHA-256}(m))$ is an example of a $H^2(m) = H(H(m))$ construction, so all generic weaknesses of $H^2$ apply to $\operatorname{SHA-256d}$ as well.

The paper Dodis, Y., Ristenpart, T., Steinberger, J., & Tessaro, S. (2012). To Hash or Not to Hash Again? (In) differentiability Results for H² and HMAC. shows that $H(H(m))$ can be distinguished from a random oracle using $2^{n/4}$ queries.

A cheap distinguisher doesn't mean there is a practical attack. The authors of the paper state that they "are unaware of any deployed cryptographic application for which the use of H² or HMAC leads to a vulnerability.".

But if you have a security proof relying on the indistinguishably of the hash, then the security guarantees of that proof are much weaker with SHA256d instead of an ideal hash.

Avoiding the distinguisher

It is possible to avoid this attack by using two different prefixes for the inner and outer hash. HMAC uses two different keys for the inner and outer hash, leading to distinct prefixes for keys strictly shorter than the block-size. That's why one alternative for SHA-256d is using HMAC-SHA-256 with a fixed key. Another alternative is $H^2(0^d||m)$ where $d$ is the input block size of the hash.

Answer 3

The only thing that immediately comes to mind is that if you know the SHA-256d of some string X, you can compute the SHA-256d of the string SHA256(X), even without knowing anything else about X.

In some sense, this is similar to the "length extension" attack, in that it allows you, given Hash(X), compute Hash(F(X)), for some function F.

Whether this is a critical problem for your hash function depends on what you're using the hash function for. If it's in place of a Random Oracle, it might be a theoretical problem; if you're using it within a signature scheme, it's probably not an issue.