New SHA2 meet-in-the-middle optimization
#1
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
Reply
#2
THANK YOU atom for taking your time and implementing this in even less than a day!
Reply
#3
(08-20-2016, 09:43 PM)atom Wrote: As of my knowledge, this is the first time this optimization is used in any hashcracking program.

FWIW we've had this optimization is JtR for a year or so, albeit only in our CPU code yet (not sure why). It was brought up back then by Aleksey Cherepanov in http://www.openwall.com/lists/john-dev/2015/09/23/1.
Reply
#4
Quote:FWIW we've had this optimization is JtR for a year or so, albeit only in our CPU code yet (not sure why). It was brought up back then by Aleksey Cherepanov in http://www.openwall.com/lists/john-dev/2015/09/23/1.

True, I just wrote it because I didn't find the optimization in the kernels/sha256_kernel.cl source - it wasn't there.
Reply
#5
Was already wondering why nobody came up with this before. - Bad luck for me + well done, Aleksey! In any case +1 for atom implementing it !!
Reply