Kleines Bruteforce-Programm in C

[3VAD_YNCAL]

Hallo zusammen,

ich versuche zur Übung ein kleines Bruteforce-Programm zu schreiben, welches Passwörter, die mit MD5 gehasht sind, knacken soll.
Um das ganze zu beschleunigen, habe ich an Parallelisierung gedacht.
Ich muss ehrlich zugeben, dass ich mich bisher noch nicht zu sehr mit Parallelisierung auseinandergesetzt habe. Jedenfalls habe ich mich nach etwas Recherche im Internet für openmp entschieden.

Das Programm funktioniert soweit auch ganz gut. Doch bei der Erzeugung der Hashes die zum Vergleich genutzt werden sollen, wird das Ganze dann doch zu sehr ausgebremst.
Habe das Programm praktisch in zwei Variationen geschrieben.
Bei der ersten Variante werden die erzeugten Wörter direkt mit dem gesuchten Wort verglichen.
Das funktioniert wirklich sehr gut und auch sehr schnell.
Bei der zweiten Variante werden die erzeugten Wörter gehasht (MD5) und mit dem Hash des gesuchten Wortes verglichen. Funktioniert auch gut, aber dauert sehr viel länger.
Mir ist schon klar das die zweite Variante nicht so schnell sein kann wie die erste, weil die erzeugten Passwörter gehasht werden müssen.

Hier ist die Funktion, welche die Hashes erzeugt und vergleicht:

Code: Alles auswählen

static void md5_hash( const char *str )
{
    unsigned char     digest[16];
    char     	      buf[32];
    static const char hash[] 	  = "098f6bcd4621d373cade4e832627b4f6"; /* Wort: 'test' */
    static const int  hash_laenge = sizeof( hash ) - 1;
    unsigned int      i;
    MD5_CTX 	      md5;

    MD5_Init( &md5 );
    MD5_Update( &md5, ( const char * ) str, strlen( str ) );
    MD5_Final( digest, &md5 );

    for( i = 0; i < 16; i++ )
	snprintf( &buf[i*2], sizeof( buf ), "%02x", digest[i] );

    if( strncmp( buf, hash, hash_laenge ) == 0 )
    {
	printf( "!!! Passwort gefunden: '%s' !!!\n", str );

	time( &zeit2 );

        printf( "Elapsed time: %ld minutes %ld seconds.\n\n", ( zeit2 - zeit1 ) / 60, ( zeit2 - zeit1 ) % 60 );

	exit( EXIT_SUCCESS ); /* GEFUNDEN !!! */
    }
}

Die bremst aber das Programm stark aus. Gibt es eine effizientere Methode Wörter zu hashen? Wie könnte ich das beschleunigen?

[Kerli]

Das hashen wirst du schwer selbst beschleunigen können - eventuell könnte es auf der GPU funktionieren. Du fangst außerdem auch gleich mit der schwierigsten Art von Attacke an, also zu einem Hash einen dazugehörigen Ausgangstext zu erhalten. Es gibt zwar bereits theoretische Attacken, die allerdings nur mit extrem hohen Zeitaufwand durchführbar sind. Wesentlich "einfacher" ist es zwei Texte zu finden die zum gleichen Hash führen (sog. Kollision).

[3VAD_YNCAL]

Das hashen wirst du schwer selbst beschleunigen können - eventuell könnte es auf der GPU funktionieren. Du fangst außerdem auch gleich mit der schwierigsten Art von Attacke an, also zu einem Hash einen dazugehörigen Ausgangstext zu erhalten. Es gibt zwar bereits theoretische Attacken, die allerdings nur mit extrem hohen Zeitaufwand durchführbar sind. Wesentlich "einfacher" ist es zwei Texte zu finden die zum gleichen Hash führen (sog. Kollision).

Ja - darüber habe ich schon gelesen. Gerade MD5 und SHA1 sollen für Kollisionen anfällig sein.
Ich wollte es eigentlich schon so haben, dass zu einem Hash der dazugehörige Ausgangstext rausgespuckt wird. Wobei das mit den Kollisionen auch interessant wäre. Aber bestimmt schwerer zu programmieren, oder?

Ich hatte ja oben bereits erwähnt, dass in meiner ersten Variante nur das gesuchte Wort mit den erzeugten Passwörtern verglichen wird. Da findet das Programm den Text 'test' in 0 Sekunden:

Code: Alles auswählen

Passwort gefunden: 'test'
Elapsed time: 0 minutes 0 seconds.

In der zweiten Variante (MD5) dauert es etwas länger:

Code: Alles auswählen

Passwort gefunden: 'test'
Elapsed time: 0 minutes 5 seconds.

Daraus schliesse ich das es an der Funktion "static void md5_hash( const char *str )" liegt.
Zum Vergleich poste ich mal die Funktion der ersten Variante:

Code: Alles auswählen

static void test_password( const char *str, int len )
{
    static const char fake_passwd[] 	 = "test";
    static const int  fake_passwd_laenge = sizeof( fake_passwd ) - 1;

    if( len == fake_passwd_laenge && strncmp( fake_passwd, str, len ) == 0 )
    {
	printf( "Passwort gefunden: '%*s'\n", len, str );

	time( &zeit2 );

        printf( "Elapsed time: %ld minutes %ld seconds.\n\n", ( zeit2 - zeit1 ) / 60, ( zeit2 - zeit1 ) % 60 );

	exit( EXIT_SUCCESS ); /* GEFUNDEN !!! */
    }
}

So geht es verdammt schnell. Kann es wirklich sein, dass das hashen und vergleichen der hashes soviel länger braucht?

[Kerli]

Wobei das mit den Kollisionen auch interessant wäre. Aber bestimmt schwerer zu programmieren, oder?

Kryptografie ist vom Programmieren normalerweise nicht unbedingt schwer, das Problem ist eher einen Algorithmus zu finden/entwerfen der mit möglichst niedriger Zeitkomplex arbeitet. Wenn man keine bekannten Details/Schwachstellen eines Algortihmus ausnützen kann dann gibt es neben der Variante Brute-Force alle möglichen Eingabewörter zu überprüfen auch ein paar Algorithmen die wesentlich effizienter funktionieren können. Für eine Kollisionsattacke kann man zb. nach dem Geburtstagsparadoxon sehr einfach und deutlich schneller eine Kollision finden, als Brute-Force das Passwort zu einem Hash.

In der zweiten Variante (MD5) dauert es etwas länger:

Das ist natürlich zu erwarten, nachdem hashen immer mehr Aufwand bedeutet als nichts tun Was dein Programm allerdings etwas ausbremsen könnte ist die Verwendung von snprintf und der anschließende Stringvergleich. Schneller dürfte es sein wenn du den gesuchten Hash in einen 16 Byte Buffer schreibst (Hexadezimal anstatt ASCII) und dann den berechneten Hash direkt berechnest. Eventuell könnte es auch noch schneller sein einen Hash in ein Array aus 2 64-bit oder 4 32-bit Integer zu speichern und dann nur noch 2 bzw. 4 Zahlen vergleichen. Nachdem zwei Hashwert sich sowieso sehr stark unterscheiden dürfte die Einsparung der Vergleichsoperationen nicht allzu viel ausmachen, da meist eh gleich der erste Vergleich fehlschlägt, snprintf dürfte aber potentiell doch etwas mehr Zeit brauchen.

[3VAD_YNCAL]

Guten Morgen ,

Kryptografie ist vom Programmieren normalerweise nicht unbedingt schwer, das Problem ist eher einen Algorithmus zu finden/entwerfen der mit möglichst niedriger Zeitkomplex arbeitet. Wenn man keine bekannten Details/Schwachstellen eines Algortihmus ausnützen kann dann gibt es neben der Variante Brute-Force alle möglichen Eingabewörter zu überprüfen auch ein paar Algorithmen die wesentlich effizienter funktionieren können. Für eine Kollisionsattacke kann man zb. nach dem Geburtstagsparadoxon sehr einfach und deutlich schneller eine Kollision finden, als Brute-Force das Passwort zu einem Hash.

Könntest du mir da eventuell ein paar Bücher empfehlen? Vielleicht ein Buch das diese Thematik in Kombination mit C/C++ behandelt? Idealerweise in deutscher Sprache, aber englisch geht natürlich auch.

In der zweiten Variante (MD5) dauert es etwas länger:

Das ist natürlich zu erwarten, nachdem hashen immer mehr Aufwand bedeutet als nichts tun Was dein Programm allerdings etwas ausbremsen könnte ist die Verwendung von snprintf und der anschließende Stringvergleich.

Danke. Du hast meine Vermutung bestätigt.

Schneller dürfte es sein wenn du den gesuchten Hash in einen 16 Byte Buffer schreibst (Hexadezimal anstatt ASCII) und dann den berechneten Hash direkt berechnest. Eventuell könnte es auch noch schneller sein einen Hash in ein Array aus 2 64-bit oder 4 32-bit Integer zu speichern und dann nur noch 2 bzw. 4 Zahlen vergleichen. Nachdem zwei Hashwert sich sowieso sehr stark unterscheiden dürfte die Einsparung der Vergleichsoperationen nicht allzu viel ausmachen, da meist eh gleich der erste Vergleich fehlschlägt, snprintf dürfte aber potentiell doch etwas mehr Zeit brauchen.

Damit meinst du den Hash, der jedes Mal aus den generierten Wörtern errechnet werden muss, oder? Den gesuchten Hash kann ich dann beispielsweise schon so speichern, oder?

Code: Alles auswählen

static const char hash[] = "098f6bcd4621d373cade4e832627b4f6"; /* Wort: 'test' */

Wie vergleiche ich die dann am Besten?
Wenn es dir nichts ausmachen würde, könntest du mir deine beiden Vorschläge:
a) gesuchten Hash Hexadezimal in 16 Byte Buffer schreiben
...und...
b) einen Hash in ein Array aus 2 64-bit oder 4 32-bit Integer zu speichern
anhand kurzer Codebeispiele demonstrieren?
Ich weiß nicht ganz, wie ich das genau umsetzen könnte? Einfach als kleine Stütze.

[Kerli]

Könntest du mir da eventuell ein paar Bücher empfehlen? Vielleicht ein Buch das diese Thematik in Kombination mit C/C++ behandelt?

Leider nicht. Ich habe die Informationen bis jetzt eigentlich nur von Vorlesungen und ansonsten verschiedenen Onlinequellen.

gesuchten Hash Hexadezimal in 16 Byte Buffer schreiben

Code: Alles auswählen

const size_t HASH_LEN = 16;
static const unsigned char hash[HASH_LEN] = {
  // "098f6bcd4621d373cade4e832627b4f6" -> Wort: 'test'
  0x09, 0x8f, 0x6b, 0xcd, 0x46, 0x21, 0xd3, 0x73, 0xca, 0xde, 0x4e, 0x83, 0x26, 0x27, 0xb4, 0xf6
};

Nachher kannst du den hash mit dem generierten Hash einfach Zahl für Zahl vergleichen (entweder manuell oder strncmp sollte es auch tun).

einen Hash in ein Array aus 2 64-bit oder 4 32-bit Integer zu speichern

Code: Alles auswählen

static const uint64_t hash[2] = {
  // "098f6bcd4621d373cade4e832627b4f6" -> Wort: 'test'
  0x098f6bcd4621d373, 0xcade4e832627b4f6
};
uint64_t digest[2];
// ...
MD5_Final( (uint8_t*)digest, &md5 );
if( hash[0] == digest[0] && hash[1] == digest[1] )
{
  // Found...
}

Hier musst du übrigens aufpassen. Eine 64 Bit Array auf einen 8 Bit Zeiger zu casten sollte problemlost möglich sein, umgekehrt kann es jedoch unter bestimmten Architekturen Probleme mit Alignment geben (oder zumindest langsamer sein).

[3VAD_YNCAL]

Vielen vielen Dank. Dann werde ich mal versuchen das umzusetzen. Sehr nett von dir.

Gruß Dave

[3VAD_YNCAL]

Okay, habe die Funktion jetzt so geschrieben:

Code: Alles auswählen

static void md5_hash( const char *str )
{
    unsigned char digest[16];
    /* "fc106bacc6a3d86ba0c44b8506cde35a" -> Wort: 'd3xt3r' */
    unsigned char hash[] = { 0xfc, 0x10, 0x6b, 0xac,
		    	     0xc6, 0xa3, 0xd8, 0x6b,
		    	     0xa0, 0xc4, 0x4b, 0x85,
		    	     0x06, 0xcd, 0xe3, 0x5a
		  	   };
    MD5_CTX md5;
    MD5_Init( &md5 );
    MD5_Update( &md5, str, strlen( str ) );
    MD5_Final( digest, &md5 );

    if( strncmp( ( const char * )hash, ( const char * )digest, 5 ) == 0 )
    {
	printf( "!!! Passwort gefunden: '%s' !!!\n", str );

	time( &zeit2 );

        printf( "Elapsed time: %ld minutes %ld seconds.\n\n", ( zeit2 - zeit1 ) / 60, ( zeit2 - zeit1 ) % 60 );

	exit( EXIT_SUCCESS ); /* GEFUNDEN !!! */
    }
}

Für das Wort 'd3xt3r' braucht es 16 min. und 45 sek. Mit snprintf(...) dauerte es 72 min. und 32 sek.
Daher echt nochmal vielen Dank.
Eine Frage hätte ich allerdings noch. (Oh Gott, ich kling schon wie Columbo )
Könnte man die Funktion noch verbessern (Code- und Performance-technisch)?

[nufan]

Könnte man die Funktion noch verbessern (Code- und Performance-technisch)?

Wenn du schon einen Integer zurückgibst, sollte der Rückgabetyp auch int sein. Oder am besten du sparst dir das EXIT_SUCCESS und lässt es bei void ^^

Warum machst du "hash" eigentlich nicht static?

Weiters könntest du noch versuchen memcmp() (http://www.proggen.org/doku.php?id=c:lib:string:memcmp) anstatt strncmp() zu verwenden. memcmp() nimmt keine Rücksicht auf \0, was dir einige Vergleiche ersparen sollte. Aber das ist nur eine Vermutung, müsstest du testen.

Sind diese Aufrufe wirklich immer notwendig?

Code: Alles auswählen

    MD5_CTX md5;
    MD5_Init( &md5 );
    MD5_Update( &md5, str, strlen( str ) );
    MD5_Final( digest, &md5 );

Ich weiß nicht was der Code genau macht, aber reicht es vielleicht sogar MD5_Init() ein einziges mal auf eine static-Variable aufzurufen und danach nur mehr mit MD5_Upate() und MD5_Final() zu arbeiten?

Wie erzeugst du überhaupt "str"? Vielleicht kannst du ja damit was anfangen: http://www.proggen.org/forum/viewtopic. ... 906#p10102
An dem Code kann man noch einiges optimieren. Ist nur ein Hinweis, du hast leider nicht erwähnt woher die Strings kommen.

[Kerli]

Code: Alles auswählen

if( strncmp( ( const char * )hash, ( const char * )digest, 5 ) == 0 )

Sollten hier nicht eigentlich mehr Zeichen verglichen werden?