Optimized hash routines needed!

PowerBlade · **Posted:** 16 Nov 2008, 00:43

If you got some optimized hashroutines (md4, des etc), feel free to post the source code below.

We already have a optimized MD5 hash routine, but we still need for MD4 and DES.

neinbrucke · **Joined:** 30 Mar 2008, 15:37 **Posts:** 847

how about a reduction function as well?

PowerBlade · **Posted:** 16 Nov 2008, 00:58

The reason i want the MD4 and DES function is so i can scrap the libeay32.dll file

Bitweasil · **Joined:** 02 Aug 2008, 08:09 **Posts:** 214

neinbrucke wrote:

how about a reduction function as well?

Change the reduction function, you invalidate all generated tables. Enjoy that.

My MD4 is just a single stage of the RFC implementation with unused inputs hardwired to 0. Nothing fancy.

neinbrucke · **Joined:** 30 Mar 2008, 15:37 **Posts:** 847

it will not invalidate generated tables, it will only speed up future tables. and a new rcrack would be needed, but that's not a problem, as this project already needs another rcrack(i).

mleo2003 · **Joined:** 19 Sep 2008, 04:42 **Posts:** 15

While I don't have an implementation to show, I have some questions about the use of DES: why are you using the full DES, any way? If all you need is LM hashing, take a DES code, and pull out the bits you don't need for just hashing. I have studied OpenSSL's implementation, and have tried to look over John the Ripper's code for it as well. Here are a few things I would suggest for your version:

1. Since the same "secret" is used as the message to be encrypted with DES over and over, and since the first thing that is done to any message is to run it through IP (more info found here), instead of redoing that same thing over and over, just do it once, and store those results in the function. Granted, that was only a few instructions at the start of every LM hash, but any speed benefit is still a benefit.

2. In most DES versions, key scheduling is done separately from the actual encryption, due to the same key schedule being able to decrypt a message as well. In our given situation, we'll NEVER decrypt the message, we already know what the message will be every time. It makes more sense to do the key scheduling within the same loop as it is applied to the bits needed and avoid more unneeded loops.

3. As a final optimization, I think I figured out the "FastLM" hash that Cain & Abel uses. The last step of DES, after mixing the key with the message, is to run that result through an inverse set of steps that undoes what 1. above did. This is to help make decrypting an almost identical operation to encrypting, and makes code a lot more simple to work with. If we skip that last step, we reduce it by just a few more functions. Now, how would you crack these hashes? Simple, when the program is given an LM hash, simply run it through the first IP, and then use that result as the key to start looking up the hash in the table.

That's about all I have found playing around with it. I actually have a function with all this already done to it, written in C, if anyone wants to see it. It wouldn't take but a small modification to make it a true LM function, just including those last few steps to reverse the IP applied to it.

I've been thinking lately of trying to get John the Ripper's version of DES (bitslice DES) and applying similar ideas to it, and compare speeds with the version I have now. I just haven't figured out that version yet, but I'm getting closer. If someone else had a fast DES implementation, that they understood, they could easily apply the above steps to it to get a faster LM function than normally allowed.

Sc00bz · **Joined:** 03 Dec 2007, 11:37 **Posts:** 725

Bit slice DES with SSE2 and soon, 2010, AVX (with the 256 bit floating point instructions since you'll only need ANDPS, ANDNPS, ORPS, and XORPS).
Only problem is that you need to modify the way generation is done since bit slicing DES means that you'll be hashing several passwords at the same time.

mleo2003 · **Joined:** 19 Sep 2008, 04:42 **Posts:** 15

Hmm, seems I still have a lot to learn with bitslice...

Since you know more about it Scoobz, do you think the modifications I listed would work on bitslice DES? If nothing else, it should allow for anyone to skip over certain parts of DES, and make the encrypting/hashing faster just based on that.

Sc00bz · **Joined:** 03 Dec 2007, 11:37 **Posts:** 725

With bit slicing all of the permutations IP, FP, E, P, PC-1, PC-2, and rotates don't cost anything, which means it will do the job of 1, 2, and 3. JTR does this so there is no need to write the DES code.

Corni · **Joined:** 15 Nov 2008, 20:45 **Posts:** 34

I'm currently searching a fast MD4 Implementation in C/C++/Asm. anyone here? In case i've to bruteforce my MSCASH hash I want to use a fast implementation

Bitweasil · **Joined:** 02 Aug 2008, 08:09 **Posts:** 214

No real loss to me to post this, I suppose.

Just the reference implementation, single stage. Hardly "optimized." Though a good bit faster than libssl's MD4, as it isn't doing nearly the same amount of work.

b0-15, abcd are 32-bit unsigned integer types.

Data goes in b0 to wherever, padding bit gets set per RFC, length gets set. Remember your little endian byte ordering.

If you have a good compiler, it will optimize out unneeded registers. If not, do it manually.

Code: Select all

typedef uint32_t UINT4;

/* MD4 Defines as per RFC reference implementation */
#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
#define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))
#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
#define FF(a, b, c, d, x, s) { \
    (a) += F ((b), (c), (d)) + (x); \
    (a) = ROTATE_LEFT ((a), (s)); \
  }
#define GG(a, b, c, d, x, s) { \
    (a) += G ((b), (c), (d)) + (x) + (UINT4)0x5a827999; \
    (a) = ROTATE_LEFT ((a), (s)); \
  }
#define HH(a, b, c, d, x, s) { \
    (a) += H ((b), (c), (d)) + (x) + (UINT4)0x6ed9eba1; \
    (a) = ROTATE_LEFT ((a), (s)); \
  }
#define S11 3
#define S12 7
#define S13 11
#define S14 19
#define S21 3
#define S22 5
#define S23 9
#define S24 13
#define S31 3
#define S32 9
#define S33 11
#define S34 15
/* End MD4 Defines */


  // For the hash working space
  UINT4 b0,b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12, b13, b14, b15;

  // For the output result
  UINT4 a,b,c,d;


  b0 = 0x00000000;
  b1 = 0x00000000;
  b2 = 0x00000000;
  b3 = 0x00000000;
  b4 = 0x00000000;
  b5 = 0x00000000;
  b6 = 0x00000000;
  b7 = 0x00000000;
  b8 = 0x00000000;
  b9 = 0x00000000;
  b10 = 0x00000000;
  b11 = 0x00000000;
  b12 = 0x00000000;
  b13 = 0x00000000;
  b14 = 0x00000000;
  b15 = 0x00000000;  
  
  // LOAD DATA INTO b0 ... whatever here.   
  b0 = 0x01;  

  a = 0x67452301;
  b = 0xefcdab89;
  c = 0x98badcfe;
  d = 0x10325476;
  
  // Padding bit per RFC
  b4 = 0x00000080;
  // Length
  b14 = 128;
  

  FF (a, b, c, d, b0, S11); /* 1 */
  FF (d, a, b, c, b1, S12); /* 2 */
  FF (c, d, a, b, b2, S13); /* 3 */
  FF (b, c, d, a, b3, S14); /* 4 */
  FF (a, b, c, d, b4, S11); /* 5 */
  FF (d, a, b, c, b5, S12); /* 6 */
  FF (c, d, a, b, b6, S13); /* 7 */
  FF (b, c, d, a, b7, S14); /* 8 */
  FF (a, b, c, d, b8, S11); /* 9 */
  FF (d, a, b, c, b9, S12); /* 10 */
  FF (c, d, a, b, b10, S13); /* 11 */
  FF (b, c, d, a, b11, S14); /* 12 */
  FF (a, b, c, d, b12, S11); /* 13 */
  FF (d, a, b, c, b13, S12); /* 14 */
  FF (c, d, a, b, b14, S13); /* 15 */
  FF (b, c, d, a, b15, S14); /* 16 */

  /* Round 2 */
  GG (a, b, c, d, b0, S21); /* 17 */
  GG (d, a, b, c, b4, S22); /* 18 */
  GG (c, d, a, b, b8, S23); /* 19 */
  GG (b, c, d, a, b12, S24); /* 20 */
  GG (a, b, c, d, b1, S21); /* 21 */
  GG (d, a, b, c, b5, S22); /* 22 */
  GG (c, d, a, b, b9, S23); /* 23 */
  GG (b, c, d, a, b13, S24); /* 24 */
  GG (a, b, c, d, b2, S21); /* 25 */
  GG (d, a, b, c, b6, S22); /* 26 */
  GG (c, d, a, b, b10, S23); /* 27 */
  GG (b, c, d, a, b14, S24); /* 28 */
  GG (a, b, c, d, b3, S21); /* 29 */
  GG (d, a, b, c, b7, S22); /* 30 */
  GG (c, d, a, b, b11, S23); /* 31 */
  GG (b, c, d, a, b15, S24); /* 32 */


  /* Round 3 */
  HH (a, b, c, d, b0, S31); /* 33 */
  HH (d, a, b, c, b8, S32); /* 34 */
  HH (c, d, a, b, b4, S33); /* 35 */
  HH (b, c, d, a, b12, S34); /* 36 */
  HH (a, b, c, d, b2, S31); /* 37 */
  HH (d, a, b, c, b10, S32); /* 38 */
  HH (c, d, a, b, b6, S33); /* 39 */
  HH (b, c, d, a, b14, S34); /* 40 */
  HH (a, b, c, d, b1, S31); /* 41 */
  HH (d, a, b, c, b9, S32); /* 42 */
  HH (c, d, a, b, b5, S33); /* 43 */
  HH (b, c, d, a, b13, S34); /* 44 */
  HH (a, b, c, d, b3, S31); /* 45 */
  HH (d, a, b, c, b11, S32); /* 46 */
  HH (c, d, a, b, b7, S33); /* 47 */
  HH (b, c, d, a, b15, S34); /* 48 */

  // Finally, add initial values, as this is the only pass we make.
  a += 0x67452301;
  b += 0xefcdab89;
  c += 0x98badcfe;
  d += 0x10325476;

jci · **Joined:** 05 Nov 2007, 01:55 **Posts:** 103

BTW, I'm currently working on a fast(er) MD5 implementation...

So far i've optimized for lens < 16, and it's about 5-7% faster than the one in rcracki (5.8M vs 5.4M) - no stack is used, no memset/memcpy, but a sh*tload defines

I would love to try and make an sse2 4-in-1 routine (1 call, 4 plains, 4 hashes returned) but it doesn't look straightforward...

BarsMonster · **Joined:** 30 Aug 2008, 20:01 **Posts:** 34

jci wrote:

BTW, I'm currently working on a fast(er) MD5 implementation...

So far i've optimized for lens < 16, and it's about 5-7% faster than the one in rcracki (5.8M vs 5.4M) - no stack is used, no memset/memcpy, but a sh*tload defines

I would love to try and make an sse2 4-in-1 routine (1 call, 4 plains, 4 hashes returned) but it doesn't look straightforward...

Make sure to compare your result to BarsWF SSE2 :-)

I bet it would show a little more than 5.8M

Sc00bz · **Joined:** 03 Dec 2007, 11:37 **Posts:** 725

BarsMonster wrote:

Make sure to compare your result to BarsWF SSE2 :-)

Pshh, you can't compare brute force to rainbow tables and expect it to be near. Brute force does 69% of an MD5 while rainbow tables need to do 100% of an MD5 (to be compatible with RainbowCrack). Also generating the next password for brute force is as simple as adding a constant while rainbow tables need to divide N times.

Sc00bz · **Joined:** 03 Dec 2007, 11:37 **Posts:** 725

Ohh right don't get me wrong it will still be fast but it'll be around 1/3 to 1/5 the speed of BarsWF SSE2.

Optimized hash routines needed!

Who is online