md5 attack: brute force 1/3 time faster than traditional hash brute forcing

["Slythers Bro" <slythers () gmail com>]

/*
MD5 recomputation proof of concept
coded by overdose
slythers () gmail com

maybe need modification for big endian
bcc32 -O2 -6 fuckmd5.cpp

E:\UnxUtils\usr\local\wbin>cat t.txt
dcvgc
E:\UnxUtils\usr\local\wbin>md5sum.exe t.txt
1c66bd6cc55e538103360ae67e5291c9 *t.txt

E:\UnxUtils\usr\local\wbin>
E:\FUCKMD5>bcc32 -O2 md5bf.cpp

Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000
Borland
md5bf.cpp:

Warning W8066 md5bf.cpp 350: Unreachable code in function main(int,char *
*)
Warning W8004 md5bf.cpp 351: 'compteur' is assigned a value that is never
used i
n function main(int,char *
*)
Warning W8004 md5bf.cpp 330: 'ii' is assigned a value that is never used in
func
tion main(int,char *
*)
Turbo Incremental Link 5.00 Copyright (c) 1997, 2000
Borland


E:\FUCKMD5>md5bf.exe1c66bd6cc55e538103360ae67e5291c9
MD5 recomputation proof of concept coded by overdose/slythers () gmail com
irc.worldnet.net#mwa
fuckmd5.exehash
pass de 5
lettres
pass found :
dcvgc


E:\FUCKMD5>

*/

#include <iostream.h>

#define CAR_CHAINE
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

static unsigned char PADDING[64] = {
 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
};

#define UINT4 unsigned int
/* F, G and H are basic MD5 functions: selection, majority, parity */
#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))
#define I(x, y, z) ((y) ^ ((x) | (~z)))

/* ROTATE_LEFT rotates x left n bits */
#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
#define ROTATE_RIGHT(x, n) (((x) >> (n)) | ((x) << (32-(n))))

/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4 */
/* Rotation is separate from addition to prevent recomputation */
#define FF(a, b, c, d, x, s, ac) \
 {(a) += F ((b), (c), (d)) + (x) + (unsigned int)(ac); \
  (a) = ROTATE_LEFT ((a), (s)); \
  (a) += (b); \
 }
#define GG(a, b, c, d, x, s, ac) \
 {(a) += G ((b), (c), (d)) + (x) + (unsigned int)(ac); \
  (a) = ROTATE_LEFT ((a), (s)); \
  (a) += (b); \
 }
#define HH(a, b, c, d, x, s, ac) \
 {(a) += H ((b), (c), (d)) + (x) + (unsigned int)(ac); \
  (a) = ROTATE_LEFT ((a), (s)); \
  (a) += (b); \
 }
#define II(a, b, c, d, x, s, ac) \
 {(a) += I ((b), (c), (d)) + (x) + (unsigned int)(ac); \
  (a) = ROTATE_LEFT ((a), (s)); \
  (a) += (b); \
 }

//hehe
#define RHH(a, b, c, d, x, s, ac) \
 {(a) -= b; \
  (a) = ROTATE_RIGHT ((a), (s)); \
  (a) -= H ((b), (c), (d)) + (x) + (unsigned int)(ac); \
 }
#define RII(a, b, c, d, x, s, ac) \
 {(a) -= (b); \
  (a) = ROTATE_RIGHT ((a), (s)); \
  (a) -= I ((b), (c), (d)) + (x) + (unsigned int)(ac); \
 }


 /* Round 1 */
#define S11 7
#define S12 12
#define S13 17
#define S14 22

 /* Round 2 */
#define S21 5
#define S22 9
#define S23 14
#define S24 20

 /* Round 3 */
#define S31 4
#define S32 11
#define S33 16
#define S34 23

 /* Round 4 */
#define S41 6
#define S42 10
#define S43 15
#define S44 21


inline unsigned int FastRecompute(UINT4 *buf, UINT4 *in)
{
UINT4 a = 0x67452301, b = 0xefcdab89, c = 0x98badcfe, d = 0x10325476;
d = buf[3] - d;
c = buf[2] - c;
b = buf[1] - b;
a = buf[0] - a;

RII ( b, c, d, a, in[ 9], S44, 3951481745); /* 64 */
RII ( c, d, a, b, in[ 2], S43,  718787259); /* 63 */
RII ( d, a, b, c, in[11], S42, 3174756917); /* 62 */
RII ( a, b, c, d, in[ 4], S41, 4149444226); /* 61 */
RII ( b, c, d, a, in[13], S44, 1309151649); /* 60 */
RII ( c, d, a, b, in[ 6], S43, 2734768916); /* 59 */
RII ( d, a, b, c, in[15], S42, 4264355552); /* 58 */
RII ( a, b, c, d, in[ 8], S41, 1873313359); /* 57 */
RII ( b, c, d, a, in[ 1], S44, 2240044497); /* 56 */
RII ( c, d, a, b, in[10], S43, 4293915773); /* 55 */
RII ( d, a, b, c, in[ 3], S42, 2399980690); /* 54 */
RII ( a, b, c, d, in[12], S41, 1700485571); /* 53 */
RII ( b, c, d, a, in[ 5], S44, 4237533241); /* 52 */
RII ( c, d, a, b, in[14], S43, 2878612391); /* 51 */
RII ( d, a, b, c, in[ 7], S42, 1126891415); /* 50 */
RII ( a, b, c, d, in[ 0], S41, 4096336452); /* 49 */

RHH ( b, c, d, a, in[ 2], S34, 3299628645); /* 48 */
RHH ( c, d, a, b, in[15], S33,  530742520); /* 47 */
RHH ( d, a, b, c, in[12], S32, 3873151461); /* 46 */
RHH ( a, b, c, d, in[ 9], S31, 3654602809); /* 45 */
return ((0x1fff & a) | ( (0x1fff & d) << 16));

}

inline bool FastTransform (UINT4 *buf, UINT4 *in, UINT4 lhash1,UINT4 lhash2)
{
 UINT4 a = buf[0], b = buf[1], c = buf[2], d = buf[3];

 /* Round 1 */
 FF ( a, b, c, d, in[ 0], S11, 3614090360); /* 1 */
 FF ( d, a, b, c, in[ 1], S12, 3905402710); /* 2 */
 FF ( c, d, a, b, in[ 2], S13,  606105819); /* 3 */
 FF ( b, c, d, a, in[ 3], S14, 3250441966); /* 4 */
 FF ( a, b, c, d, in[ 4], S11, 4118548399); /* 5 */
 FF ( d, a, b, c, in[ 5], S12, 1200080426); /* 6 */
 FF ( c, d, a, b, in[ 6], S13, 2821735955); /* 7 */
 FF ( b, c, d, a, in[ 7], S14, 4249261313); /* 8 */
 FF ( a, b, c, d, in[ 8], S11, 1770035416); /* 9 */
 FF ( d, a, b, c, in[ 9], S12, 2336552879); /* 10 */
 FF ( c, d, a, b, in[10], S13, 4294925233); /* 11 */
 FF ( b, c, d, a, in[11], S14, 2304563134); /* 12 */
 FF ( a, b, c, d, in[12], S11, 1804603682); /* 13 */
 FF ( d, a, b, c, in[13], S12, 4254626195); /* 14 */
 FF ( c, d, a, b, in[14], S13, 2792965006); /* 15 */
 FF ( b, c, d, a, in[15], S14, 1236535329); /* 16 */

 /* Round 2 */
 GG ( a, b, c, d, in[ 1], S21, 4129170786); /* 17 */
 GG ( d, a, b, c, in[ 6], S22, 3225465664); /* 18 */
 GG ( c, d, a, b, in[11], S23,  643717713); /* 19 */
 GG ( b, c, d, a, in[ 0], S24, 3921069994); /* 20 */
 GG ( a, b, c, d, in[ 5], S21, 3593408605); /* 21 */
 GG ( d, a, b, c, in[10], S22,   38016083); /* 22 */
 GG ( c, d, a, b, in[15], S23, 3634488961); /* 23 */
 GG ( b, c, d, a, in[ 4], S24, 3889429448); /* 24 */
 GG ( a, b, c, d, in[ 9], S21,  568446438); /* 25 */
 GG ( d, a, b, c, in[14], S22, 3275163606); /* 26 */
 GG ( c, d, a, b, in[ 3], S23, 4107603335); /* 27 */
 GG ( b, c, d, a, in[ 8], S24, 1163531501); /* 28 */
 GG ( a, b, c, d, in[13], S21, 2850285829); /* 29 */
 GG ( d, a, b, c, in[ 2], S22, 4243563512); /* 30 */
 GG ( c, d, a, b, in[ 7], S23, 1735328473); /* 31 */
 GG ( b, c, d, a, in[12], S24, 2368359562); /* 32 */

 /* Round 3 */
 HH ( a, b, c, d, in[ 5], S31, 4294588738); /* 33 */
 HH ( d, a, b, c, in[ 8], S32, 2272392833); /* 34 */
 HH ( c, d, a, b, in[11], S33, 1839030562); /* 35 */
 HH ( b, c, d, a, in[14], S34, 4259657740); /* 36 */
 HH ( a, b, c, d, in[ 1], S31, 2763975236); /* 37 */
 HH ( d, a, b, c, in[ 4], S32, 1272893353); /* 38 */
 HH ( c, d, a, b, in[ 7], S33, 4139469664); /* 39 */
 HH ( b, c, d, a, in[10], S34, 3200236656); /* 40 */
 HH ( a, b, c, d, in[13], S31,  681279174); /* 41 */
 if( (a & 0x1fff) != lhash1)
  return 0;
 HH ( d, a, b, c, in[ 0], S32, 3936430074); /* 42 */
 if( (d & 0x1fff) != lhash2)
  return 0;
 HH ( c, d, a, b, in[ 3], S33, 3572445317); /* 43 */
 HH ( b, c, d, a, in[ 6], S34,   76029189); /* 44 */
 HH ( a, b, c, d, in[ 9], S31, 3654602809); /* 45 */
 HH ( d, a, b, c, in[12], S32, 3873151461); /* 46 */
 HH ( c, d, a, b, in[15], S33,  530742520); /* 47 */
 HH ( b, c, d, a, in[ 2], S34, 3299628645); /* 48 */

 /* Round 4 */
 II ( a, b, c, d, in[ 0], S41, 4096336452); /* 49 */
 II ( d, a, b, c, in[ 7], S42, 1126891415); /* 50 */
 II ( c, d, a, b, in[14], S43, 2878612391); /* 51 */
 II ( b, c, d, a, in[ 5], S44, 4237533241); /* 52 */
 II ( a, b, c, d, in[12], S41, 1700485571); /* 53 */
 II ( d, a, b, c, in[ 3], S42, 2399980690); /* 54 */
 II ( c, d, a, b, in[10], S43, 4293915773); /* 55 */
 II ( b, c, d, a, in[ 1], S44, 2240044497); /* 56 */
 II ( a, b, c, d, in[ 8], S41, 1873313359); /* 57 */
 II ( d, a, b, c, in[15], S42, 4264355552); /* 58 */
 II ( c, d, a, b, in[ 6], S43, 2734768916); /* 59 */
 II ( b, c, d, a, in[13], S44, 1309151649); /* 60 */
 II ( a, b, c, d, in[ 4], S41, 4149444226); /* 61 */
 II ( d, a, b, c, in[11], S42, 3174756917); /* 62 */
 II ( c, d, a, b, in[ 2], S43,  718787259); /* 63 */
 II ( b, c, d, a, in[ 9], S44, 3951481745); /* 64 */

 buf[0] += a;
 buf[1] += b;
 buf[2] += c;
 buf[3] += d;
 return 1;
}

void aide();
void ReadSignature(UINT4 *buf,char *sign);
unsigned char HexValue(char h);

int main(int argc , char *argv[])
{
UINT4 in[16];
UINT4 buf[4] , bufres[4];
UINT4 littlehash1,littlehash2;
unsigned char wesh[64];
unsigned char chaine[] = CAR_CHAINE;
//bool cracked = 0;
unsigned int i, ii,l,longueur,tmp,compteur;
aide();
if(argc < 2)
 exit(0);
//on lit le hash en parametre
ReadSignature(buf,argv[1]);

//initialisation
bufres[0] = 0x67452301;
bufres[1] = 0xefcdab89;
bufres[2] = 0x98badcfe;
bufres[3] = 0x10325476;
memset(in,0x00,sizeof(UINT4)*16);
memset(wesh,0x00,64);
wesh[0] = 1;
wesh[1] = 1;
wesh[2] = 1;
wesh[3] = 1;
wesh[4] = 0;
in[14] = 4 << 3;
in[0] = chaine[wesh[1]-1];
in[0] |= chaine[wesh[2]-1] << 8 ;
in[0] |= chaine[wesh[3]-1] << 16;
in[1] = 0x80;
longueur = 4;
tmp = FastRecompute(buf,in);
in[0] |= chaine[wesh[0]-1] << 24 ;
littlehash1 = (tmp & 0x1fff);
littlehash2 = ((tmp>>16) & 0x1fff);
compteur =0;
do{
 //debug
 /*if(compteur == 2000000)
 {
 cout <<"trying :
"<<chaine[wesh[1]-1]<<chaine[wesh[2]-1]<<chaine[wesh[3]-1]<<chaine[wesh[0]-1];
   for(i = 4; i < longueur;i++)
    cout <<chaine[wesh[i]-1];
   cout <<endl;
   compteur = 0;
 }
 compteur++;*/
 //on check si le hash est bon
 if(FastTransform(bufres,in,littlehash1,littlehash2))
 {
  if(!memcmp(bufres,buf,sizeof(UINT4)*4))
  {
   cout <<"pass found :
"<<chaine[wesh[1]-1]<<chaine[wesh[2]-1]<<chaine[wesh[3]-1]<<chaine[wesh[0]-1];
   for(i = 4; i < longueur;i++)
    cout <<chaine[wesh[i]-1];
   cout <<endl;
   return 0;
  }
  cout << "false positif"<<endl;
  bufres[0] = 0x67452301;
  bufres[1] = 0xefcdab89;
  bufres[2] = 0x98badcfe;
  bufres[3] = 0x10325476;
 }

 //on incremente
 if(wesh[0] == (sizeof(CAR_CHAINE)-1))
 {
  for(l =0; wesh[l] == (sizeof(CAR_CHAINE)-1);l++)
   wesh[l] = 1;
  //nouvelle longueur
  if(!wesh[l])
  {
   in[14] = (l+1) << 3;
   cout <<"pass de "<<dec<<(l+1)<<" lettres"<<endl;
   longueur = l+1;
   wesh[l] = 1;
  }
  else
   wesh[l]++;
  in[0] = chaine[wesh[1]-1] ;
  in[0] |= chaine[wesh[2]-1] << 8 ;
  in[0] |= chaine[wesh[3]-1] << 16;
  //chaine est unsigned sinon ca peut faire gayzé avec les valeurs negatif
  for (i = 1, ii = 4; (ii+4) <= longueur ; i++, ii += 4)
  {
   in[i] = (((UINT4)chaine[wesh[ii+3]]) << 24) |
              (((UINT4)chaine[wesh[ii+2]]) << 16) |
              (((UINT4)chaine[wesh[ii+1]]) << 8) |
              ((UINT4)chaine[wesh[ii]]);
  }

  tmp = 0;
  in[i] = 0x00;
  switch(longueur %4)
  {
   case 3:
    in[i] |= chaine[wesh[ii]-1] << tmp;
    ii++;
    tmp += 8;
   case 2:
    in[i] |= chaine[wesh[ii]-1] << tmp;
    ii++;
    tmp += 8;
   case 1:
    in[i] |= chaine[wesh[ii]-1] << tmp;
    ii++;
    tmp += 8;
   case 0:
    in[i] |= 0x80 << tmp;
    break;

  }
  // on recompute
  tmp = FastRecompute(buf,in);
  in[0] |= chaine[wesh[0]-1] << 24 ;
  littlehash1 = (tmp & 0x1fff);
  littlehash2 = ((tmp>>16) & 0x1fff);
 }
 else
 {
  wesh[0]++;
  in[0] = (in[0] & 0x00ffffff) | (chaine[wesh[0]-1] << 24);
 }

}while(1);
return 0;
}

void aide()
{
cout <<"MD5 recomputation proof of concept coded by
overdose/slythers () gmail com irc.worldnet.net #mwa"<<endl;
cout <<"fuckmd5.exe hash"<<endl;
}

//lit en little endian
void ReadSignature(UINT4 *buf,char *sign)
{
unsigned int bitch;
unsigned int i,ii;
//unsigned sinon ca fait gayzé
unsigned char b[16];
if(strlen(sign)< 32)
{
 cout <<"bad signature"<<endl;
 exit(0);
}
for(bitch = 0;bitch < 16;bitch++)
 b[bitch] = (HexValue(sign[bitch*2]) << 4) | HexValue(sign[(bitch*2)+1]);
for (i = 0, ii = 0; i < 4; i++, ii += 4)
{
 buf[i] = (((UINT4)b[ii+3]) << 24) |
            (((UINT4)b[ii+2]) << 16) |
            (((UINT4)b[ii+1]) << 8) |
            ((UINT4)b[ii]);
}
}
unsigned char HexValue(char h)
{
if((h >= '0') && (h <= '9'))
 return (h-'0');
if((h >= 'a') && (h <= 'f'))
 return ((h-'a')+0x0a);
if((h >= 'A') && (h <= 'F'))
 return ((h-'A')+0x0a);
return 0x00;
}

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/