Each 512-bit block of SHA256 takes an initialization vector (IV) and message schedule and returns a digest. Knowing the message schedule and resulting digest, is it feasible to reverse the algorithm to find the IV?
My intuition tells me no because the IV is added to the working variables immediately before returning the digest, causing a dependency on the IV at both the beginning and end of the algorithm. Is this correct?
If we how to recover the previous state of SHA-256 with less than $2^{254}$ expected effort (as measured by number of hash compression operations), then we can find SHA-256 preimages with less than $2^{256}$ expected effort, and hence would be a weakening in the expected SHA-256 cryptographical strength.
Here's how this works; suppose that we can find the previous state with expected effort $M < 2^{254}$. Then, what we do is select two blocks (with appropriate SHA-256 padding in place for a 56 - 119 byte hash), and find the previous state for those two blocks from the target state; expected effort $2M < 2^{255}$.
Then, we would try various initial 64 byte blocks, and compute a forward hash compression operation on them (using the standard IV); we "win" if the resulting state is either of the previous states from the previous step. If we assume that the SHA-256 hash compression functions acts like a random number, then the probability of any guess of the initial block would succeed with probability $2^{-255]$; hence this takes an expected $2^{255}$ hash compression operations.
If we find a match, we can immediately construct a message (consisting of the initial block that won, along with the final block that matched it) that SHA-256 hashes to the target value.
Total expected effort: $2M + 2^{255} < 2^{256}$
Notes:
Obviously, if $M$ is significantly less than $2^{254}$, then we'd generate considerably more than 2 final blocks and intermediate states.
I did skip over the point that it's possible that there is no intermediate state that is mapped to the final state via the message block we chose. This would decrease the limit that $M$ can be somewhat...
SHA-256 Uses Merkle-Damgard Construction (MD). The $IV$ is used only at the beginning. The IV is fixed if you apply the NIST standard2.
Now, someone is not applying the standard, and you have the message $m$, $h=H_{SHA-256}(IV,m)$, and you want to find the $IV$.
Secure hash functions, are one-way, not only because of the large input size that shrink into smaller size but also they have non-linear parts, like the $\wedge$ SHA256 compression function. So, you can't invert.
