To generate every possible hash would be ... impractical.
To work backwards from any given hash is also incredibly labor intensive.
Of the two, which is less impossible? Why?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ If you can generate a table of all preimage/hash combinations you can lookup the hash. Therefore working backwards is at least as easy as generating this table. Most likely easier (with algebraic solutions). This is a variation on the classical brute-force argument: if no structural weaknesses are known the algorithm has the complexity associated with brute-forcing all possible combinations. $\endgroup$– eckesJul 9, 2017 at 18:50
-
$\begingroup$ @eckes Damnit, that's the answer I came up with as well. I was honestly hoping I'd missed something. Thanks. $\endgroup$– That GuyJul 9, 2017 at 19:00
-
$\begingroup$ Well, it's an answer. Even more specific arguments won't have a different outcome. The only answer which would be more relevant is the news about SHA-2 being broken :) $\endgroup$– eckesJul 9, 2017 at 19:02
-
$\begingroup$ @eckes I totally agree with you, I really just hoped we were both wrong. Long live SHA256. $\endgroup$– That GuyJul 9, 2017 at 20:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
The latter is the less impossible.
Actually it's not at all mathematically impossible to invert SHA-256. There's no natural law saying we can't, it's just as you rightly point out, a bit hard at the moment. However that current difficulty does not preclude us doing it in the future. A practical quantum computer, an IPhone10 or some breakthrough in analysis might enable us to simply invert the hash. All of MD5, SHA-0 and ~65 rounds of SHA-1 have been compromised, not counting recently published SHA-1 collisions.
As for generating all 10^77 possible SHA-256 outputs, we can perform all sorts of mathematical estimates of the resources required. There's an excellent question along similar lines here. In summary, we can't with our available physical resources. Ever. (There is an interesting issue here in that there may not actually be 10^77 or 2^256 actual outputs, as the hash function may not be surjective. This is discussed here.)
Hence the former is impossible whilst the latter is currently difficult. Your question is very similar to one regarding Impossibility vs implaussiblity.
answered Jul 9, 2017 at 22:10
-
$\begingroup$ So, if inversion is the less impossible of the two, does that make SHA256 susceptible to MitM attacks? Or is it more than one could accomplish in a single lifetime? $\endgroup$– That GuyJul 9, 2017 at 22:20
-
3$\begingroup$ For what definition of inverted is it that MD5, SHA-0 have been inverted? By this account MD5 is still practically safe from preimage attacks. $\endgroup$– fgrieu ♦Jul 9, 2017 at 22:54
-
$\begingroup$ Let's say the input to the cryptographic hash is longer than the output, how do you recover the lost bits? In general there are many subtle ways to loose information on purpose such as mod and overflow, how would that be addressed in a reversing function? $\endgroup$– zaphJul 10, 2017 at 2:27
-
$\begingroup$ In that last paragraph, "currently difficult" is an understatement: working backwards from any given MD5 hash was never done (other by guessing the input from a small set), and we can at best outline a currently infeasible plan for how it could be done. SHA-256 is to MD5 what the ocean is to a drop of water (metaphorically; actual ratio is much larger), thus working backwards from any given SHA-256 hash is even more out of reach. That said, I second your assessment. $\endgroup$– fgrieu ♦Jul 10, 2017 at 5:21
-
$\begingroup$ @zaph: in a hashing context, it can be said that a hash is reversed when some input giving a desired hash is found, even if it is not the input that generated the hash in the first place. $\endgroup$– fgrieu ♦Jul 10, 2017 at 10:34