Finding the IV values of SHA-256 given all message blocks

Question

Given all message blocks $w[i],i \in 0:63$ and assume that $n<128$ (arbitrary) bits $x_1,x_2,...,x_n$ of the IV values are unknown (e.g., $h_7$ bits are unknown) while other IV values coincide with those in the SHA-256 algorithm. Let $h_{i}^{j}$ denotes $i$-th hash of $j$-th round that is $$(h_{0}^{0},h_{1}^{0},...,h_{7}^{0})\overbrace{\mapsto}^{SHA256}(h_{0}^{1},h_{1}^{1},...,h_{7}^{1})\overbrace{\mapsto}^{SHA256} ...\overbrace{\mapsto}^{SHA256}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64}),$$ and $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ depends on $n$ unknown IV bits. Now let us take $n$ (arbitrary) bits $y_1,y_2,...,y_n$ of $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ and assign values to them.

Question: Is there a possibility to find $x_1,x_2,...,x_n$ giving the assigned values of $y_1,y_2,...,y_n$ faster than exhaustive search?

Remark. One can notice that for the fixed $w$ the function

$\operatorname{SHA256}_{w}^{-64}(h_{0}^{64},h_{1}^{64},...,h_{7}^{64}) = (h_{0}^{0},h_{1}^{0},...,h_{7}^{0})$ can be constructed analytically, so if all the bits of $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ are known, it is easy to obtain IV values. However, if only $n<128$ bits are assigned it is needed to find $2^{256-n}$ preimages in the worst case.

Answer 1

With the question as asked, no, there it is not possible to recover the missing part of $h_0^0,h_1^0,\ldots,h_7^0$ faster than brute force search.

The question states:

$\operatorname{SHA256}_{w}^{-64}(h_0^{64},h_1^{64},\ldots,h_7^{64})=(h_0^0,h_1^0,\ldots,h_7^0)$ can be constructed analytically

Most probably, this not even a function, because the true SHA-256 compression function $\operatorname{SHA256}_{w}$, hereafter $F$, is most probably not a bijection, hence $F^{-1}$ not a function, due to the construction of $F$ as $$\begin{align}F: \{0,1\}^{256}&\longmapsto\{0,1\}^{256}\\ h'\quad&\longrightarrow\;F(h)\;\underset{\text{def}}=\;G(h)\boxplus h\end{align}$$ where

• $h$ denotes vector $h_0,h_1,\ldots h_7$ assimilated to a 256-bit bitsring from $\{0,1\}^{256}$
• $G$ is a bijection, fully determined by the 512-bit padded message block (taken from $w$) at this compression step, and the specification of SHA-256. $G$ is essentially a 64-rounds block cipher with known sub-keys. A useful mental model of $G$ is an arbitrary bijection of the set $\{0,1\}^{256}$.
• $\boxplus$ is addition modulo $2^{32}$ of 32-bit words, a regular group operation of the set $\{0,1\}^{256}$.

Knowing $h'=G(x)\boxplus h$, we know no method to find unknown $h$ better than brute force search, and there's demonstrably no better one under the simple model of $G$ as an oracle implementing an arbitrary bijection.

If we additionally know part of $h$ [e.g. $h_7$ as in the question for the first compression step, or even $h_1,h_2\ldots,h_{7}$ ], the best that it does is simplify slightly the combinatorial problem we face, but again the best known method to solve it is essentially brute force, and demonstrably so under the random oracle model.

Therefore, even if the question was asked for a single compression step and the full output known, there's no known method to solve it more efficiently than searching the unknown input bits, with cost $\mathcal O(2^n)$. More compression steps make the situation even more hopeless.

---

This late comment introduces a radical variant with the compression function simplified to $F=G$. Now $F^{−1}$ is a function, easily computed by inverting each of the 64 rounds in $G$ in reverse order.

Wikipedia's compression main loop pseudocode:

for i from 0 to 63
    S1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
    ch := (e and f) xor ((not e) and g)
    temp1 := h + S1 + ch + k[i] + w[i]
    S0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
    maj := (a and b) xor (a and c) xor (b and c)
    temp2 := S0 + maj
    h := g        g := f        f := e 
    e := d + temp1
    d := c        c := b        b := a
    a := temp1 + temp2

can be inverted as:

for i from 63 downto 0
    S1 := (f rightrotate 6) xor (f rightrotate 11) xor (f rightrotate 25)
    ch := (f and g) xor ((not f) and h)
    S0 := (b rightrotate 2) xor (b rightrotate 13) xor (b rightrotate 22)
    maj := (b and c) xor (b and d) xor (c and d)
    temp2 := S0 + maj
    temp1 := a - temp2
    a := b        b := c        c := d
    d := e - temp1
    e := f        f := g        g := h
    h := temp1 - S1 - ch - k[i] - w[i]

Note: when going backward, S1, ch, S0, maj and temp2 are computed from different variables using otherwise the same formulas as forward; and temp1 (resp. d and h) are computed by reversing with basic algebra the formulas used to forward-compute a (resp. e and temp1).

If we knew the whole output $h^{64}$, we could efficiently walk back from it to $h^0$ with 64 evaluations of the $F^{−1}$ functions determined by the 64 known fragments of $w$, as efficiently as hashing forward. The partial knowledge of the IV would be of little help.

But in the question we only know $n$ out of 256 bits of $h^{64}$. The best attack is educated brute force as suggested in the question, with a cost of $\mathcal O(2^{\min(n,256-n)})$. This is obtained by searching unknown input bits for small $n$, and unknown output bits for large $n$. Argument: the whole chain of (modified) compression functions forms a bijection, and in the random oracle model for that the best attack is such brute force.