2
$\begingroup$

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.

|improve this question
$\endgroup$
  • 2
    $\begingroup$ Do you still wonder after reading on the Davies-Meyer construction of One-Way Functions? $\endgroup$ – fgrieu Jan 2 at 17:18
  • $\begingroup$ @fgrieu My claim; mining... $\endgroup$ – kelalaka Jan 2 at 17:20
  • $\begingroup$ @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. $\endgroup$ – user64720 Jan 2 at 17:28
  • $\begingroup$ @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. $\endgroup$ – user64720 Jan 2 at 17:36
  • $\begingroup$ 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} $\endgroup$ – kelalaka Jan 2 at 17:42
2
$\begingroup$

No, this 'unappend' operation is effectively infeasible for the SHA-256 hash compression operation; there is no known way that is less expensive than brute force.

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.

|improve this answer
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.