Can we calculate the "previous hash value" in the SHA256 compression function with a known message block and final hash?

Question

Suppose we have a $512$-bit (or $512\times n$ bit) message that we'd like to hash using SHA-256. I've looked at the implementation, and from what I understand, after padding, there will be a total of $2$ (or $n+1$) message "blocks" that are fed into the function, with the last block being completely padding. The last message block in this scenario is completely known, it should begin with the "1" bit that marks the beginning of the padding, followed by a bunch of zeros, followed by the message size in bits.

So now, let's say we hash the message. If we follow the chain, the first "hash value" is known, it's the $H_0$ of SHA-256 which is the following (from wikipedia):

h0 = 0x6a09e667   h1 = 0xbb67ae85   h2 = 0x3c6ef372   h3 = 0xa54ff53a
h4 = 0x510e527f   h5 = 0x9b05688c   h6 = 0x1f83d9ab   h7 = 0x5be0cd19

But for every subsequent execution of the compression function, the values above will be changed. My question is, since we know the final message block, can we compute the intermediate hash right before the last hash $H_n$ using just the final message block (which is fully known), and the output final hash $H_{n+1}$?

Answer 1

Can we compute the intermediate hash $H_n$ using just the fully known final message block, and the final hash output $H_{n+1}$?

No, that's computationally infeasible. The only known way to find $H_n$ is when we know all (or enough of) the message, which allows to directly compute $H_n$ in the forward direction (or use brute force search of a small unknown fraction of the message, validating a guess by checking if the final $H_{n+1}$ matches).

The reason we can not compute $H_n$ is that the Davies-Meyer round function $(H_n,M_n)\mapsto H_{n+1}$ restricted to fixed known $M_n$ is computationally difficult to invert.

That follows from its construction as $H_{n+1}\gets E(\text{key}\gets M_n, \text{block}\gets H_n)\boxplus H_n$ where $E$ is a public block cipher and $\boxplus$ is a group operation¹ on $\{0,1\}^{256}$ (256-bit bitstrings).

If some fairy told us the output $X$ of $E(\text{key}\gets M_n, \text{block}\gets H_n)$, and since we know $M_n$ and $H_{n+1}$, we could find $H_n$ in two ways:

• by using the decryption function $D$ matching $E$, with $H_n\gets D(\text{key}\gets M_n, \text{block}\gets X)$
• by inverting $X\boxplus H_n\mapsto H_{n+1}$ to find $H_n$ from the known $H_{n+1}$ and the $X$ given by the fairy.

But we have no fairy, and there is no known way out of this chicken-and-egg problem. That's even provable under a model of $E$ as an ideal cipher. That's by design of the Davies-Meyer round function.

Also: it is likely that for a sizable fraction of the final hash $H_{n+1}$ and message size (equivalently, values of $M_n$ ), the known relation $H_{n+1}=E(\text{key}\gets M_n, \text{block}\gets H_n)\boxplus H_n$ leaves several possible values for $H_n$.

---

¹ $\boxplus$ happens to be addition of 256-bit bitstrings ignoring carry bit between blocks of 32 bits.