Full Disclosure mailing list archives
RE: md5 attack: brute force 1/3 time faster thantraditional hash brute forcing
From: "Edward Pearson" <Ed () unityitservices co uk>
Date: Thu, 24 Aug 2006 12:02:01 +0100
Every heard of rainbow tables? Brute forcing MD5 is stoneage now. ________________________________ From: full-disclosure-bounces () lists grok org uk [mailto:full-disclosure-bounces () lists grok org uk] On Behalf Of Slythers Bro Sent: 23 August 2006 09:30 To: full-disclosure () lists 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 () 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.exe 1c66bd6cc55e538103360ae67e5291c9 MD5 recomputation proof of concept coded by overdose/slythers () gmail 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 () 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/
Current thread:
- md5 attack: brute force 1/3 time faster than traditional hash brute forcing Slythers Bro (Aug 23)
- RE: md5 attack: brute force 1/3 time faster thantraditional hash brute forcing Edward Pearson (Aug 24)
- Re: md5 attack: brute force 1/3 time faster thantraditional hash brute forcing Denis Jedig (Aug 24)
- RE: md5 attack: brute force 1/3 time faster thantraditional hash brute forcing Edward Pearson (Aug 24)