The idea of a cryptographic hash of a plaintext password is that you cannot 'reverse' or 'decrypt' the hash and in this way recover the original plaintext. One can only attempt to recover the plaintext password by trying many plaintexts and compare the resulting hashes to this hash (for example by regular brute forcing, dictionary attacks or by using rainbow tables). It is however possible to reverse part of the hash in such a way that a smaller part of the cryptographic algorithm has to be performed. The amount of steps that can be reversed, depends on the algorithm used. At least for MD5 an unlikely large amount of steps can be reversed. Several people have been working on reversing this algorithm and implementing these techniques into brute forcers. For example the GPU powered brute forcer BarsWF gains much speed because of the reversed steps.
There is this one guy, Sc00bz, who actually wrote about reversing MD5 in detail, providing enough information for one to go and implement the reversing steps into for example a brute forcer. Later on he even provided some code snippets to work with.
I already got the idea of reversing and reversed a few steps of SHA-1 in shabr. With SHA-1 however you can't reverse many steps:
When you normally hash a plaintext password with SHA-1, the last part is to add initial values:
context->Intermediate_Hash[0] += A;
context->Intermediate_Hash[1] += B;
context->Intermediate_Hash[2] += C;
context->Intermediate_Hash[3] += D;
context->Intermediate_Hash[4] += E;
A, B, C, D, E are defined as:
A = 0x67452301;
B = 0xEFCDAB89;
C = 0x98BADCFE;
D = 0x10325476;
E = 0xC3D2E1F0;
As you already know the last values of the 'Intermediate_Hash' you are looking for, you can just as well subtract these values before starting with brute forcing all those combinations. In this way, you don't have to calculate this last part for every plaintext you hash.
Previous to this part the actual SHA-1 steps are calculated. Let's look at the final step:
SHA1_STEP_ROUND4( B, C, D, E, A, W[79])
with:
SHA1_STEP_ROUND4(a, b, c, d, e, x)
e = e + ROTATE_LEFT(a,5) + F_60_79(b,c,d) + x + K;
b = SSE_ROTATE(b,30);
If you want to know the values of A-E before this step, you do the reverse of what you see here. So you subtract when there was an add, you rotate right when there was a rotate left:
REVERSE_SHA1_STEP_ROUND4(a, b, c, d, e, x)
e = e - ROTATE_RIGHT(a,5) - F_60_79(b,c,d) - x - K;
b = ROTATE_RIGHT(b,30);
There are some unknowns here, we don't know 'x', so we can't even fully reverse this last step. We can however pre-calculate most of this step, which saves time. You just need to do something like 'e = e + x' in the last step of the hashing code. You can do something similar with the 2 previous steps, but you'll have more unknown values, so you can reverse a smaller part of the step. Also don't forget that you only need to check 1 of 5 parts of the hash most of the time, so you only calculate the last steps when you have an early match. You can look at my code in shabr to see it implemented (the reversing slightly different then what you see here, but the idea is the same).
Now the fun starts when you think about reversing MD4 or MD5... where with SHA-1 you start with unknown values in the last steps straight away, with MD4 and MD5 you can go back many steps when you keep part of your plaintext equal. For a detailed explanation of how this is done for MD5 you can read the writings of Sc00bz I mentioned at the beginning:
Sc00bz @ freerainbowtables forum
More explanation from Bars and from Sc00bz, including code snippets
I implemented these ideas in an MD5 brute forcer, and fairly easily I could apply the same ideas to MD4 and make an NTLM brute forcer. I'll release these tools including source code in the upcoming days. While BarsWF beats my code by FAR, as far as I know mine is now the fastest open source MD5 SSE2 brute forcer ;) And the NTLM brute forcer might be the fastest around for CPU's (just because Bars or x4d3 didn't make a CPU version yet I guess) :)
(I should really try and seriously learn to interlace SSE2 one day...)
