[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <8f6a58a30608230129p3eb620f7o7b441b910ae97507@mail.gmail.com>
Date: Wed, 23 Aug 2006 10:29:56 +0200
From: "Slythers Bro" <slythers@...il.com>
To: full-disclosure@...ts.grok.org.uk
Subject: md5 attack: brute force 1/3 time faster than
traditional 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.exe1c66bd6cc55e538103360ae67e5291c9
MD5 recomputation proof of concept coded by overdose/slythers@...il.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@...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