New SHA2 meet-in-the-middle optimization

[atom]

Just wanted to note here about the following commit on GitHub:

https://github.com/hashcat/hashcat/commi...8a51d95501

This implement a meet-in-the-middle optimization for SHA2, which means it will work on SHA224, SHA256, SHA384 and SHA512 for single-hash cracking sessions. As of my knowledge, this is the first time this optimization is used in any hashcracking program. Credits for the Idea go to jodler303 here on the hashcat forum.

Due to how it works, it's not limited to BF as with MD4/MD5. It will work on all attack-modes in single-hash cracking sessions. Currently it's implemented in hashcat for SHA256 only. I'll add the optimization for SHA384 and SHA512 later.

Typical SHA2 rounds code here:

Code:

        for (i = 0; i < 64; ++i) {
                t1 = h + EP1(e) + CH(e,f,g) + k[i] + m[i];
                t2 = EP0(a) + MAJ(a,b,c);
                h = g;
                g = f;
                f = e;
                e = d + t1;
                d = c;
                c = b;
                b = a;
                a = t1 + t2;
        }

In single-hash we first subtract the initial values from the state buffer in the (a, b, c, d, e, f, g, h) 32 bit buffers. We can do this since we're in the first transform call. 

Now if you take a look at the code above you can see how that t2 uses values only that we have in the final hash (just moved from a to b, b to c and c to d). The important thing is that it does not depend on the message (the password), stored in m[i] here.

In other words, we can calculate t2 with this:

Code:

  t2 = EP0(b) + MAJ(b,c,d);

Now that we have t2, we can also reverse t1, because of this:

Code:

  a = t1 + t2;

So we simply do:

Code:

  t1 = a - t2;

Now that we have t1, we can reverse to the full step. Code looks like this:

Code:

  a = b;
  b = c;
  c = d;
  d = e - t1;
  e = f;
  f = g;
  g = h;
  h = 0;

We can't know "h", because it's value is been dropped with every step. Otherwise this would need only 1 STEP to test for a valid m[i] or do even better things :)

Anyway, we can still make use of this. We can repeat the above block for 4 times, because that's where "h" is not required to know. At this point we have a valid value for "d" in step 60. However, this value was originaly calulated 3 steps before, so we end up in a value we can test at step 57. Only if it maches we continue to step 64.

--
atom