Let's say I give you the sha256 hash of my password, which I'll call X.

Now, the sha256 algorithm is a one-way function, meaning you can give it some input and get an output, but you can't get the input out of only the output. The algorithm is public, so we know how it calculates the digest of some message.

But let's say you take a look at X, and you just say "you know what, I'm going to reverse this hash". The thing I'm wondering about, is this:

Sha256 uses a function called Maj which takes 3 input words and spits out another word. The function looks like this:

int32 Maj(x, y, z){
   Return (x & y) ^ (x & z) ^ (y & z);

Now, the size of the input (96 bits) is larger then the output size (32 bits) so there are guaranteed collisions (with this function). But, if we were given an output of this function, we could very easily come up with 3 32 bit words which when fed through this function produce our desired output. Same goes for the Ch function.

What I want to say is this: if we were given an Sha256 hash, we could backtrack the inputs all the way to round one, and every time we get a message word in the compression function (again, this is just guessing the words, were not actually reversing) we store that message word until we have "reversed" all the way to round one.

This way, we have a possible message which produces our initial hash, X , if you know what I mean. Why isn't this technique used in the real world? Is it inefficient? If it IS getting used, then in which way?

  • $\begingroup$ The Maj is called 64 times in the rounds of the internal block cipher. Did you count this? And did you count the number of variables that one need to try? $\endgroup$ – kelalaka Apr 22 '20 at 11:19
  • $\begingroup$ @kelalaka I know, but how long do you think it would take then? $\endgroup$ – Ömer Enes Özmen Apr 22 '20 at 11:22
  • 5
    $\begingroup$ I think this question is essentially a duplicate of Why can't I reverse a hash to a possible input?, with SHA-256's Maj given as illustration. There are answers there. $\endgroup$ – fgrieu Apr 22 '20 at 11:24
  • $\begingroup$ Also similar ideas on SHA-1 applies here “One-Wayness” of SHA 1 $\endgroup$ – kelalaka Apr 22 '20 at 11:30
  • $\begingroup$ That link really helped me understand what giant mess this going to be, thanks $\endgroup$ – Ömer Enes Özmen Apr 22 '20 at 11:40