[C++] MD5-Cracker, warum so langsam?

Hi


Ich hab mich mal daran versucht, einen MD5-Cracker zu schreiben ( ja ich weiß es gibt schon sehr viele davon, ich machs nur um besser C++ zu können ;))


Jedenfalls bekomm ich immer nur 140k Hashes/Sek hin, andere Cracker jedoch sehr viel mehr.

Was an meinem Code bremst aus?
Was könnte ich verbessern?


Vielen Dank im voraus


(AMD 64 X2 5600+)
Kompiler: SSE2, Beste Optimierung
 
ich hab jetzt nicht wirklich lust darauf, das durchzuschauen, aber ein paar allgemeine Tipps kann ich geben:
1. Profiler benutzen. Bekanntermaßen werden 80% der Laufzeit in 20% des Codes verbracht (in diesem fall ists wohl noch extremer ;) ), benutze den Profiler, um herauszufinden, was wie viel Laufzeit verbraucht und wo es zu optimieren gilt.
2. benutze so wenig dynamischen Speicher wie möglich. Falls du viele kleine Objekte anlegst, erwäge einen sog. Memory-Pool (google).
3. Benutze Referenzen, statt Objekte zu kopieren.

Mehr kann ich dir im Moment nicht sagen :)
 
Benutze keine Funktionen sondern mache so viel wie möglich inline, verwende Optimierungsparameter für Speed beim Compiler.
Lass dir den Assemblercode für den Compiler anzeigen.
 
Hmm okay ich hab alle funktionen inline gemacht,
und LTProf(kA ob der gut ist, hab ihn einfach mal genommen) meint das GetModuleFileNameA sehr lange brauch und KiFastSystemCallRet auch...
Screenie

Wie kann ich jetzt herausfinden, welche stellen langsam sind?

Oder gibt es bessere Profiler die ihr mir empfehlen könnt?


Thx
 
Ich meine, da sind 3 stellen, wo man einsparen könnte.

1. in deiner Hauptschleife hast du nen strlen drin, was nicht sonderlich fix ist u 2. du zählst wieter indem du nen substr aus dem charset appendest. das ist auch nicht besonders schnell.
3. beim hashen wird die eingabe auf ne länge kongruent zu 478 mod 512 gepadded. Diese arbeit muss beim brutefoorcen nicht jedesmal gemacht werden.

Du solltest also versuchen deinen stringcounter so zu verbessern, dass er einfach auf einem buffer zählt, anstatt ständig implizit copy-ctors aufzurufen.

Evtl. auch mal andere md5-implementierungen testen. Ich hatte damals glaub diese hier benutzt http://sourceforge.net/project/showfiles.php?group_id=42360 und damit ca. 1M keys/s auf nem athtlon xp 2400+ gehabt.

(4. Ich weiß nicht, ob es so gut ist, dass processnext recursive aufgerufen wird)

EDIT:

Wie kann ich jetzt herausfinden, welche stellen langsam sind?

In der winapi gibts ne Funktion namens QueryPerformanceCounter(), mit der man auch kurze Zeiten recht genau messen kann. Die hat mir schon oft geholfen. Ich weiß leider nicht, wie das pendant beim pinguin heißt.
 
Okaaay ich glaub ich hab nur die Hälfte verstanden 8o ?(

Ist die Funktion so besser?
Code:
inline void processNext(char* value, int dep, int maxdep, int threadid, int threadcount)inline void processNext(char* value, int dep, int maxdep, int threadid, int threadcount){
     if(dep==maxdep){
                    string md5 = MD5((char*)value);
                    check(md5, value);
      } else if (dep==0) {
            for(int i = threadid; i < __charsetlength; i+=threadcount){
                    char *next = new char[20];
                    char *add = new char[2]; add[0] = charset[i]; add[1] = 0;
                    strcpy( next, value );
                    strcat( next, add);
                    processNext(next, dep+1, maxdep, threadid, threadcount);
            }
      }  else {
             for(int i = 0; i < __charsetlength; i++){
                    char *next = new char[20];
                    char *add = new char[2]; add[0] = charset[i]; add[1] = 0;
                    strcpy( next, value );
                    strcat( next, add);
                    processNext(next, dep+1, maxdep, threadid, threadcount);                   
             }
      }
}

? (__charsetlength = strlen(charset.c_str()), wird ganz am Anfang definiert)

Wie komm ich von den dynamischen Arrays runter? wenn ich das = new char[...] wegmache bekomm ich eine speicherzugriffsverletzung bei strcpy.
 
Nein, das ist nicht wirklich besser. Du machst igentlich fast das gleiche wie vorher, nur, dass du es anders aufschreibst und der string jetzt auf dem heap liegt.

Zum bruteforcen reicht es aber einmal nen eingabebuffer zu reservieren und den dann immer wiederzuverwenden.

Code:
char* buf = malloc(BUF_SIZE); //buffer einmalig erzeugen
initBuf(buf,BUF_SIZE); //hier sollte der startstring in den buf geschrieben werden

for(;md5(buf) != gesuchterHash;increaseBuf(buf))
{
}

/*
increaseBuf(char*) wird hier etwas aufwendiger, da du ja nen beliebigen charset haben möchtest ich schau mal, ob ich da noch was auf meiner platte finde, was ich schnell umbauen kann.
*/

Hier hast du den string jetzt immer in buf, dessen speicher nur einmal angelegt und dann weiterverwendet wird.

EDIT:

So, ich hab noch was gefunden:
Code:
inline void incpass(char* pass)
{
	int pos = strlen(pass) - 1;
	pass[pos]++;
	while(pos >= 0)
	{
		if(pass[pos] > 'z')
		{
			pass[pos] = 'a';
			pos--;
			pass[pos]++;
		}
		else
		{
			break;
		}
	}
	if(pos < 0)// overflow -> string verlaengern
	{
		pass[strlen(pass)] = 'a';
		pass[strlen(pass) + 1] = '\0';
	}
}

Hat halt noch 3 schönheitsfehler. der erste ist das strlen() oben, was man wegmachen kann, indem man noch nen static hat, was sich die aktuelle strlen merkt. der zweite: der charset ist fix (a-z). der dritte: wenn der buf zu klein geht der speicher kaputt, sollte aber bei ner bufsize >8 bei md5 so schnell nicht passieren. Ich hoffe du kannst damit was anfangen.

Auf jedenfall dürfte das ganze damit schonmal deutlich schneller werden. was dann noch fehlt ist das padding überflüssig machen. dazu musst du die rivest-implementierung nen bisschen umbauen. das padding wird dort in glaub in MD5Update gemacht. Allerdings bringt das dann vermutlich höchstens 10% performancegewinn.
 
Okay jetzt bin ich total verwirrt.
Code:
inline void processNextAlternate(char* startpw, int tid, int tcnt){
       int __tid = tid;
       char* pwd = (char*) mempool->GetMemory( 2048 );
       printf("Thread %d Startup...",__tid+1);
       for(int i = 0; i < 2048; i++) pwd[i] = 0;
       printf("done\n");
       while(true){
            pwd = incpass(pwd);
            printf("'%s'\n",pwd);
            check(MD5(pwd),pwd);   // Hier wird pwd aus irgendeinem mir nicht erscheinbaren Grund geleert
            printf("'%s'\n",pwd);    
            }
       }

inline char * incpass(char* pass)
{
    int pos = strlen(pass) - 1;    
    pass[pos]++;
	while(pos >= 0)
	{
		if(pass[pos] > 'z')
		{
			pass[pos] = 'a';
			pos--;
			pass[pos]++;
		}
		else
		{
			break;
		}
	}
	if(pos < 0)// overflow -> string verlaengern
	{
		pass[strlen(pass)] = 'a';
		pass[strlen(pass) + 1] = '\0';
	}
	return pass;
}

inline void check(string hash, string plain){
       lts++;
     for(int i = 0; i < __lastpos; i++){
               if(!strcmp(md5s[i], hash.c_str())){
                       printf("%s found\n",plain.c_str());
                       fstream out(outfile.c_str(),ios::out | ios::app);
                       out.write( (hash+":"+plain).c_str(), strlen((hash+":"+plain).c_str()));
                       out.write("\r\n",2);
                       out.close();
                     for(int q =0; q < 32; q++)md5s[i][q] = md5s[__lastpos][q];
                     __lastpos--;
                     if(__lastpos==1) exit(-1);
                     }
             }
     }

Warum leert sich pwd? :(

Langsam bin ich echt am verzweifeln...
 
Warum der string geleert wird seh ich auf die schnelle nicht. Aber in MD5() schneidest du das letzte Zeichen ab:
Code:
what[strlen(what)-1] =0;

Bei nur einem Zeichen ist der String danach natürlich leer.

Hab in der funktion auch noch nen böses new und nen memcopy gesehen. Den ausgabebuffer musst du natürlich auch wiederverwenden, da kannst du auch wahnsinnig viel performance gewinnen. Hab zu dem new nichtmal ne freigabe gesehen. Das scheint nen speicherleck zu sein.

Warum hast du eigentlich die Signatur von void incPass(char*) in char* incpass(char*) geändert?
 
what[strlen(what)-1] =0;

Das scheint schon richtig zu sein weil die Funktion richtige ergebnisse liefert

while(true){
incpass(pwd);
pwd2 = pwd;
check(MD5((char*)pwd2),(const char*)pwd2);
}

Auch hier ändert sich pwd, obwohl check nur mit pwd2 aufgerufen wird.... iwie ist da der wurm drinne *grübel*
 
Original von AlterHacker
what[strlen(what)-1] =0;

Das scheint schon richtig zu sein weil die Funktion richtige ergebnisse liefert

while(true){
incpass(pwd);
pwd2 = pwd;
check(MD5((char*)pwd2),(const char*)pwd2);
}

Auch hier ändert sich pwd, obwohl check nur mit pwd2 aufgerufen wird.... iwie ist da der wurm drinne *grübel*

Warum sich pwd dort auch ändert ist leicht zu erklären. Dazu musst du pointer verstehen und wissen, wie arrays und strings implementiert sind. Hier mal ne zusammmenfassung:
strings sind als arrays implementiert (char string[]).
arrays verhalten sich in c/cpp wie pointer, da type a[n] <=> *((void*a) + n*sizeof(type)).

So, nun konkret auf deinen fall bezogen:
nehmen wir an der string in pwd sei "abc", dann steht irgendwo im arbeitsspeicher (zB. an 0x0000abca bis 0x0000abcd) die sequenz 'a','b','c',0x00. pwd hat den wert 0x0000abca, zeigt also auf den string im speicher. wenn du pwd2 = pwd schreibst, dann hat pwd2 auch den wert 0x0000abca. Eine Funktion die am string rummanipuliert arbeitet also auf dem gleichen speicherbereich und wenn du pwd dann wieder ausliest, hat er sich ebenfalls geändert.
 
Zurück
Oben