1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ At first, I thought that, by using different arguments I can directly show, however, when I tried to say more than cannot, I've noticed that, The IV and first message part, maybe the message, plays different roles in the compression function. So, simply replacing IV with the message didn't work. $\endgroup$ – kelalaka Sep 26 '18 at 18:50
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ If someone uses a nonstandard IV, then they aren't using SHA-256... $\endgroup$ – poncho Sep 26 '18 at 17:44
  • $\begingroup$ Right, but the IV for each block is the digest of the previous blocks. So, I'm asking if knowing the plaintext and digest from the last block allows us to get the digest of the previous blocks, not knowing their plaintext. $\endgroup$ – Joel Sep 26 '18 at 17:50
  • 2
    $\begingroup$ @Joel: Terminology difference; I consider only the starting state of SHA-256 to be the "IV" (Initial Vector); not the intermediate states the hash achieves after processing a 512 bit block of data (and kelalaka's second sentence assumes the same). This doesn't invalidate the question, which I would phase as "can we reconstruct the previous state of the SHA-256 hash when we don't know the previous input..." $\endgroup$ – poncho Sep 26 '18 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.