Date: Thu, 24 Aug 2006 12:02:01 +0100
From: "Edward Pearson" <Ed@...tyitservices.co.uk>
To: <full-disclosure@...ts.grok.org.uk>
Subject: RE: md5 attack: brute force 1/3 time faster
	thantraditional hash brute forcing

Every heard of rainbow tables? Brute forcing MD5 is stoneage now.

________________________________

From: full-disclosure-bounces@...ts.grok.org.uk [mailto:full-disclosure-bounces@...ts.grok.org.uk] On Behalf Of Slythers Bro
Sent: 23 August 2006 09:30
To: full-disclosure@...ts.grok.org.uk
Subject: [Full-disclosure] md5 attack: brute force 1/3 time faster thantraditional hash brute forcing

 

/*
 MD5 recomputation proof of concept
 coded by overdose
 slythers@...il.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.exe 1c66bd6cc55e538103360ae67e5291c9                           
 MD5 recomputation proof of concept coded by overdose/slythers@...il.com irc.worldnet.net #mwa                                                                   
 fuckmd5.exe hash                                                                
 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@...il.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;
}


Content of type "text/html" skipped

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

Powered by blists - more mailing lists