4
$\begingroup$

Ferguson, Schneier and Kohno's Cryptography Engineering §5.4.2 describes a construction, $\operatorname{SHA}_d\text-X(m)$, which is just $\operatorname{SHA-\!}X(\operatorname{SHA-\!}X(0^b\mathbin\|m))$ (where $\operatorname{SHA-\!}X$ is any particular SHA-2 hash, and $0^b$ represents a full input block of zero bits).

I understand that the second hash is necessary to prevent length-extension attacks.

What I don't understand, and cannot find adequate explanation for, is the rationale for zero-prefixing the inner message $m$. The book's hand-wavy explanation is that:

Prepending the message with a block of zeros makes it so that, unless something unusual happens, the first block input to the inner hash function in $h_d$ is different than the input to the outer hash function.

But that is as far as it goes to explain the zero block.

A related but distinct question, "Understanding double hash and 0 block prepending to mitigate length extension attacks," has a partial answer from fgrieu:

If the $0^b$ in the question's construction was absent, as in $H'(m)=H(H(m))$, we'd have the property: $\forall m,H'(H(m))=H(H'(m))$. We can construct some (largely artificial) protocols which would be secure for $H$, but are insecure for $H'$ due to that property; and correspondingly, that property makes some security proofs hairy, impossible, or weaker. With $H'(m)=H(H(0^b\mathbin\|m))$, that or similar properties do not hold, which is good for simpler/stronger security proofs.

What protocols would be insecure for $\operatorname{SHA}_d\text-X'(m)=\operatorname{SHA-\!}X(\operatorname{SHA-\!}X(m))$? (To be clear: such a $\operatorname{SHA}_d\text-256'$ construction would not be susceptible to length-extension attacks, right?) Does the difference matter for any "real-world" protocols that use the $\operatorname{SHA}_d$ construction today?

Is there a good name for this property ($\forall m,H'(H(m))=H(H'(m))$) that I can search the literature for?

$\endgroup$
  • 1
    $\begingroup$ Related answer, with a protocol a protocol where $\operatorname{SHA}_d\text-X'$ is shown to be insecure but $\operatorname{SHA}_d\text-X$ is secure. $\endgroup$ – fgrieu May 16 at 17:00
  • $\begingroup$ Thanks @fgrieu, that's very helpful. $\endgroup$ – Conrad Meyer May 17 at 16:39
3
$\begingroup$

If $H(x)$ is a random oracle, then $H(H(0^b \mathbin\| x))$ is indifferentiable from a random oracle[1] (Theorem 5, p. 444; note that [1] uses the name ‘HMAC’ for this particular construction, at odds with the standard meaning of the name), but $H(H(x)) = H^2(x)$ is not[2], and there are protocols that can be exhibited (as [2] does) which are secure if instantiated with $H$ but trivially breakable if instantiated with $H^2$.

The reason that $H(H(0^b \mathbin\| x))$ works as a random oracle is essentially the domain separation of the inner hash and the outer hash: there is no string of the form $0^b \mathbin\| x$ that coincides with a string that $H(\cdot)$ could yield as an intermediate value.

The protocol in [2] that is breakable with $H^2$ but not $H$ is a mutual proof-of-work game: Two parties aim to prove to each other that they have each spent the work to compute $\hat H^n(x)$ and $\hat H^m(y)$ for some $(n, x)$ and $(m, y)$ chosen by the opposite party, and for some hash $\hat H$. When instantiated with $\hat H = H$, the protocol works; when instantiated with $\hat H = H^2$, one party can ask the other to compute $u = \hat H^n(x)$ where $x = H(y)$ and $n = m - 1$, and then return $$H(u) = H(\hat H^n(x)) = H(\hat H^n(H(y))) = \hat H^{n + 1}(y) = \hat H^m(y)$$ at a total cost of two $H$ evaluations, rather than $m$ as expected, completely destroying the protocol.

This protocol is contrived. Maybe your protocol doesn't have this affliction. But while there is a theorem that $H(H(0^b \mathbin\| x))$ is safe for all protocols, this counterexample means that you have to separately study any protocol that you consider instantiating with $H(H(x))$ to see whether $H(H(x))$ is a problem for that protocol.

The theorem serves as a free cryptographer for everyone to sign off on the use of $H(H(0^b \mathbin\| x))$; if you want to use $H(H(x))$ you have to hire a personal cryptographer of your own to review your particular use of $H(H(x))$, and cryptographers aren't cheap. If you already have a personal cryptographer (or auditor), the theorem lets them save work auditing your work and spend their time and energy on the rest of the work.

$\endgroup$
  • $\begingroup$ Thanks @Squeamish Ossifrage. My interest stems from the use of SHAd-256 in Fortuna in particular, which is used by the random device in the FreeBSD operating system. In this context, SHAd-256 is used to mix together previous state and new "entropy" to form the new state (K´ ← Hd(K || s)). I'm not sure Hd() provides any additional security over either H²() or H() in this algorithm. Especially if H() is changed from SHA-2 to any of the SHA-3 finalists. $\endgroup$ – Conrad Meyer May 17 at 17:40
  • 1
    $\begingroup$ When $H$ is SHA-224, SHA-256, or SHA-512, then if the input length is always fixed, then there is never any advantage to $H^2$ or $H(H(0^b \mathbin\| \cdot))$ over $H$. When $H$ is SHA-512/256 or any of the SHA-3 functions, there is also never any advantage to $H^2$ or $H(H(0^b \mathbin\| \cdot))$ over $H$. In the case of Fortuna, it might not make a difference—but I don't know enough details to say for sure. Either $H(H(0^b \mathbin\| \cdot))$ or SHA-3 (preferably KMAC, but SHAKE or SHA3-256 are fine too with a unique encoding of the pair of inputs) will prevent length-extension. $\endgroup$ – Squeamish Ossifrage May 17 at 17:51
  • $\begingroup$ In the Fortuna construction, $SHA_d()$ is used in two ways. One is to reseed between distinct PRNG outputs (input length is fixed). The other is to compress collected "entropy" data into pools, which are used directly to reseed. If an attacker can learn $H(x)$ from reseed, they already have Fortuna's key and the implementation is fundamentally broken. If an attacker can learn $H(x)$ of one or more of Fortuna's pools, they already have memory disclosure of secret state, i.e., impl. is fundamentally broken. I believe that makes any additional length-extension quality of $H$ a non-problem. $\endgroup$ – Conrad Meyer May 24 at 20:08

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.