5
$\begingroup$

I was reading some guy's description of the SHA-256 algorithm and I noticed that the basic operations it uses appear trivial to reverse: addition, rotate bits, etc. When I say "reverse" I don't mean retrieving the exact input used to generate the hash, I mean finding some input which generates the same hash (finding a collision). I would like to understand why this is actually difficult.

Preimage resistance: For a given h in the output space of the hash function, it is hard to find any message x with H(x)=h. Source

Here is an general explanation for why a function can be easy to calculate in one way, but very difficult to reverse (calculate the other way). What in particular gives SHA-256 this property? If someone tried to generate a hash collision, which obstacles would they face?

SHA-256 diagram from Wikimedia commons

The initial values for A-H are predetermined in the algorithm. The actual input comes from W. In this sense the "initial state" can be thought of as a combination of user input and predetermined values. Does this contribute to the difficulty in finding collisions? If the initial values for A-H could be any arbitrary values, would it be trivial to find hash collisions?

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ $A \oplus B = C$. Say $C = 1$, what is the value of $A$ and $B$? Now you can find both combinations, but for much larger circuits executed multiple times (multiple rounds, in other terms) this gets much harder. $\endgroup$
    – Maarten Bodewes ♦
    Aug 7, 2016 at 21:22
  • 1
    $\begingroup$ possibly related/interesting question/answers $\endgroup$
    – Ella Rose
    Aug 8, 2016 at 2:25

1 Answer 1

Reset to default
8
$\begingroup$

You appear to be thinking "the output of the round function appears to be a simple function of the previous round, and a word from the message; why can't we select message words to steer the output to whatever we wanted".

Well, there's something missing in the simple description you gave; message expansion. The W inputs are not just directly taken from the input message; the first 16 are, but the other 48 are linear functions of the input message. If you modify one input word, you necessarily modify a number of the W inputs; this effectively stops this simple steering strategy, as tweaking one W input (to get a desired state) will necessarily modify others (which will modify the state you're trying to set up).

This doesn't prove the SHA-256 is secure (SHA-1 does the same sort of message expansion, and we know that's weak); however it does show that this approach doesn't appear to be fruitful.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Note: The message expansion function in SHA2 family, is not linear but is a non-linear transformation, which is reason why same attacks which work against SHA1 dont work for SHA2. $\endgroup$
    – rapadura
    Jan 22, 2019 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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