/************************************************************************
 * Bruteforce-Algorithmus fuer Strings beliebiger Laenge		*
 * Wie bei allen Bruteforce-Algorithmen steigt der 			*
 * Rechenaufwand exponentiell nach folgender Formel: 			*
 * Maximal benoetigte Durchlaeufe fuer einen String der Laenge length =	*
 * 	alphabet^length							*
 * Bsp: Alphabet (Klein- u Grossbuchstaben) + Ziffern 0-9 = 62 Zeichen	*
 * => es existieren:							*
 * 	62^1 = 62 		Strings der Laenge 1 			*
 * 	62^2 = 3844 		Strings der Laenge 2 			*
 * 	62^3 = 238328 		Strings der Laenge 3 			*
 * 	62^4 = 14776336 	Strings der Laenge 4 			*
 * 	62^5 = 916132832 	Strings der Laenge 5 			*
 * 	62^6 = 56800235584 	Strings der Laenge 6 			*
 * 	62^7 = 3521614606208	Strings der Laenge 7 			*
 * 									*
 * Erweitert um die Moeglichkeit, zu einer gegebenen md5-Pruefsumme	*
 * den zugehörigen String zu ermitteln. Aufgrund der o.g. Gruende ist 	*
 * dies nur fuer kurze Strings sinnvoll.				*
 * Auf einem Pentium 4, 3,2 GHz wurden ca 3,3 Millionen Hashes/Sekunde	*
 * abgearbeitet.							*
 * Hierfuer wird eine Implementierung des md5-Algorithmus von 		*
 * Ulrich Drepper verwendet, wie es den Dateien md5.c, md5.h		*
 * und md5_loc.h entnommen werden kann!					*	
 *									*
 * 2008-02-26:								*
 * 		 Erweiterung um Threads; Laufzeit wird dadurch idR	*
 * 		 verkuerzt						*
 *									*
 * 	Author: Haui, contact haui45@web.de				*
 * 									*	
 * Bugs: -die Angabe der Durchlaeufe stimmt nur für kurze Strings und	*
 * 	  da u.U. auch nicht. ;-)					*
 * 	 -ab ca 4 Milliarden Durchlaeufen gibt es einen Ueberlauf.	*
 * 	  								*
 *									*
 *									*
 * **********************************************************************/


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <pthread.h>
#include "md5.h"

/*paramter-struct for brute()*/
struct thread_data{
	int stringlength;
	char *getme;
	int begin;
	int last;
};

static char *zeichen = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 ";
static unsigned int count = 0;

void *brute(void *my_data){
	struct thread_data *data;
	data = (struct thread_data *) my_data;
	char *getme= data->getme;		/*gesuchter hash*/
	int begin= data->begin;			/*startzeichen*/
	int last= data->last;			/*endzeichen*/
	int stringlength = data->stringlength;	/*maximale stringlaenge*/
	int anzahl =(int)strlen(zeichen);	/*laenge des "alphabets"*/
	int helparray[(int)stringlength];	/*positionsarray*/
	char string[(int)stringlength+1];	/*string der zeichenfolge die wir gerade probieren*/
	char end[(int)stringlength+1];	/*endzeichen*/
	int i=0;	/*laufvariable*/
	int start = 0;	/*counter...siehe anfangskommentar*/
	int k=0;	/*laufvariable*/
	int a;	/*strcmp...*/
	unsigned char md5sum[MD5_SIZE];	
	char summe[33];
	/*initialisierung des strings und des hilfsarrays*/
	for(i=0;i<(int)stringlength;i++){
		if (i==0){
			helparray[i]=begin;
			string[i]=zeichen[(int)begin];
			end[i]=zeichen[(int)last];
		}
		else{
			helparray[i]=0;
			string[i]=zeichen[0];
			end[i]=zeichen[anzahl-1];
		}	
	}
	/*strings mussen mit '\0' abgeschlossen werden :D*/
	string[(int)stringlength] = '\0';
	end[(int)stringlength] = '\0';

	/*eigentliche bruteforceschleife*/
	while(1){
		count++;
		for(i=0;i<(int)stringlength;i++){
			string[i] = zeichen[helparray[i]];
		}
		md5_buffer(string, (unsigned int)strlen(string), md5sum);
		md5_sig_to_string(md5sum, summe, 33);
		if ((int)getme[0] == (int)summe[0]){
			a = strcmp((char*)getme, summe);
			/*success :-)*/
			if(a==0){
				printf("gesuchter String: \"%s\"\n Durchlaeufe: %d\n", string, count);
				exit(0);
			}
		}
		
		if((int)string[0] == (int)end[0]){
			a=strcmp(string,end);
			if(a==0) return NULL;
		}
		for (i=(int)stringlength-1;i>=0;i--){
			if(helparray[i]==anzahl-1){
				continue;
			}
			helparray[i]++;
			for(k=(int)stringlength;k>i;k--){
				helparray[k]=0;
			}
			break;
		}
		start++;
	}
}





int main(int argc, char **argv){
	int j;
	int maxlength;
	size_t alphabet = strlen(zeichen);
	pthread_t p1, p2;
	struct thread_data thread1, thread2;
	int half = (int)alphabet / 2;
	if (argc!=3 ){
		printf("Falsche Anzahl an Parametern!\nVerwendung:\n\t\tuser@host ~ $ ./brute maximallaenge md5-hash\n");
		 printf("Beispiel:\t ./brute 5 7215ee9c7d9dc229d2921a40e899ec5f\n");
		exit(2);
	}
	/*check argv[1]*/
	for (j=0; j<(int)strlen(argv[1]); j++){
		if((int)argv[1][j] < 0x30 || (int)argv[1][j]> 0x39){
			printf("Parameter %s keine Zahl!\n", argv[1]);
			exit(1);
		}
	}
	/*check argv[2] simple*/
	if (strlen(argv[2]) != 32){
		printf("Keine md5-Hash!\n");
		exit(1);
	}
	/*check argv[2] extended*/
	for (j=0; j<32 ; j++){
		if((int)argv[2][j]<0x30 || 
			(((int)argv[2][j] > 0x39) && ((int)argv[2][j] < 0x61)) ||
				argv[2][j] > 0x66){
			printf("Kein md5-Hash! Hash darf nur aus Ziffern und den Kleinbuchstaben a-f bestehen!\n");
			exit(1);
		}
	}
		maxlength=atoi(argv[1]);

		thread1.begin = 0;	/*Startzeichen thread1*/
		thread1.last=half-1;	/*Stopzeichen thread1*/
		thread1.getme=argv[2];	/*gesuchter hash*/
		
		thread2.begin = half;
		thread2.last=(int)alphabet-1;
		thread2.getme=argv[2];

	for(j=1;j<=maxlength;j++){
		/*maximale laenge der strings auf j setzen*/
		thread1.stringlength = j;
		thread2.stringlength = j;

		pthread_create(&p1, NULL, brute, (void *)&thread1);
		pthread_create(&p2, NULL, brute, (void *)&thread2);

		pthread_join(p1, NULL);
		pthread_join(p2, NULL);
		
	}
	 printf("string nicht gefunden :(\n");
	return 0;
}
