2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Could you provide us the source of the question? $\endgroup$ – kelalaka Feb 22 at 21:46
  • $\begingroup$ Somehow, you need to break the 64 round compression function that can be thought as a simple block cipher. $\endgroup$ – kelalaka Feb 22 at 22:08
  • 1
    $\begingroup$ CAUTION: According to this late comment, it is considered a variant of SHA-256 with removal of the additions modulo $2^{32}$ at the end of each round. This entirely changes the outcome! $\endgroup$ – fgrieu Feb 23 at 14:29
2
$\begingroup$

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.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Thank you very much for your reply. Here, it is assumed that one does not consider an addition mod $2^{32}$ at the end of the algorithm link, that is, the components of the vector $(h_{0}^{64},h_{1}^{64},...,h_{7}^{64})$ are those of the last round output ($h' := g, g' := f, f' := e, e' := d \boxplus temp1, d' := c, c' := b, b' := a, a' := temp1 \boxplus temp2$). $\endgroup$ – Daniil Feb 23 at 14:01
  • $\begingroup$ Yes, for every output it is easy to find IV values but in my case only a part of the output is constrained. For clarification, let us consider an example for which $h_{7}^{0}$ is unknown (denote it $x$) and choose the output value $h_{0}^{64}(h_{7}^{0})$ that depends on unknown $h_{7}^{0}$. (to be cont'd) $\endgroup$ – Daniil Feb 23 at 17:14
  • $\begingroup$ One requires $h_{0}^{64}(h_{7}^{0})$ to have value C (a constant, say, $2^{32}-1$), so $G^{64}(h_{0}^{0},h_{1}^{0},...,x)=(C,h_{1}^{64},...,h_{7}^{64})$ is required (I want to find such an x that gives $h_{0}^{64}(x)=C$, no matter what values of $h_{1}^{64}(x),h_{2}^{64}(x),h_{3}^{64}(x),h_{4}^{64}(x),h_{5}^{64}(x),h_{6}^{64}(x),h_{7}^{64}(x)$ are). $\endgroup$ – Daniil Feb 23 at 17:14
  • $\begingroup$ If I find $G^{-64}(C,\tilde{h}_{1}^{64},...,\tilde{h}_{7}^{64})=(\tilde{h}_{0}^{0},\tilde{h}_{1}^{0},...,x^{*})$ for arbitrary $\tilde{h}_{1}^{64},...,\tilde{h}_{7}^{64}$, in general, $(\tilde{h}_{0}^{0},\tilde{h}_{1}^{0},...,\tilde{h}_{6}^{0})$ will not concide with $(h_{0}^{0},h_{1}^{0},...,h_{6}^{0})$ $\endgroup$ – Daniil Feb 23 at 17:42
  • $\begingroup$ @Daniil: Hopefully, I now consider the partial knowledge on output, which I had missed initially. If some of your comments are obsolete (and if you can, I'm not sure of that), you may want to remove them. $\endgroup$ – fgrieu Feb 23 at 17:54

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.