# Given a SHA-256 message block, is it possible to undo the transformation of the internal state?

Consider the transformation described in section 6.2 of RFC4634 ("US Secure Hash Algorithms (SHA and HMAC-SHA)"). Given the message block M(i), and hence the message schedule W, as well as the output of the block function H(i), how hard should I expect computing H(i-1) to be?

Interestingly, the 64 "rounds" are easily reversible for this set of knowns and unknowns, but the final addition makes using this fact not trivial.

• Do you still wonder after reading on the Davies-Meyer construction of One-Way Functions? – fgrieu Jan 2 at 17:18
• @fgrieu My claim; mining... – kelalaka Jan 2 at 17:20
• @fgrieu After reading that section three times, I still don't understand what you're hinting at. As far as I can see, this being possible would not damage any security requirements of hashing functions. – user64720 Jan 2 at 17:28
• @kelalaka I don't see how this could be useful for mining -- the goal there is to find the message, and that's been studied thoroughly already. – user64720 Jan 2 at 17:36
• There were a mining people tried to revers the hash algorithm. The first target for a hash function should be finding collisions not finding the pre-image see [Joux's paper]{iacr.org/archive/crypto2004/31520306/multicollisions.pdf} – kelalaka Jan 2 at 17:42

Such an 'unappend' operation would reduce the time taken to generate preimages from $$2^{256}$$ to $$2^{129}$$ hash compression operations (assuming that the unappend operation is as cheap as the forward hash compression operation). This would be done via a meet-in-the-middle attack, where in the most straight-forward implementation, you generate one list of $$2^{128}$$ intermediate states (from $$2^{128}$$ prefixes), and you generate a second list of $$2^{128}$$ intermediate states (from $$2^{128}$$ postfixes; starting from the target hash, you use the unappend operation), and search for a common value in the two lists.