Kleines Bruteforce-Programm in C

[3VAD_YNCAL]

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 ^^

Ich habe es deswegen so geschrieben, weil ich mir dachte, dass das Programm einfach mit exit( EXIT_SUCCESS ) beendet werden soll, sobald das gesuchte Wort gefunden wurde.

Warum machst du "hash" eigentlich nicht static?

Stimmt, dann bleibts im Speicher. Habe ich geändert.

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.

Habe ich auf memcmp umgeändert. Mehr dazu weiter unten.

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?

Könntest du mir anhand eines kurzen Code-Beispiels zeigen, wie du das genau meinst?

Habe mal die Funktion folgendermaßen umgeschrieben. Verglichen zu vorher etwas schneller. Braucht für 'd3xt3r' 16 min. 23 sek., also 22 Sekunden weniger wie davor.:

Code: Alles auswählen

static void md5_hash( const char *str )
{
    unsigned char 	 digest[16];
    /* "fc106bacc6a3d86ba0c44b8506cde35a" -> Wort: 'd3xt3r' */
    static 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( memcmp( ( const char * )hash, ( const char * )digest, 16 ) == 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 !!! */
    }
}

Doch das mit MD5_Init() ein einziges mal auf eine static-Variable aufzurufen, würde mich noch interessieren, wie ich das genau umsetzen kann. Also ein kurzes Code-Beispiel wäre nett.

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.

Hier mal die Funktion, welche die Strings erzeugt und auch die o.g. Funktion aufruft.

Code: Alles auswählen

/* Global */
time_t zeit1, zeit2;

typedef void( *func_t )( const char * );

const char zeichen[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
const int  nbzeichen = sizeof( zeichen ) - 1;

/* Prototypes */
static void brute_force( const int * restrict, const int * restrict, int, func_t );
static void md5_hash( const char * );

static void brute_force( const int * restrict erster_eingang, 
			 const int * restrict letzter_eingang, int laenge, func_t md5_hash )
{
    char passwd[laenge];
    int  eingang[laenge];
    int  i, j;

    for( i = 0; i < laenge; ++i )
	eingang[i] = erster_eingang[i];

    i = 0;

    while( i < laenge )
    {
	/* Generiere das nächste Passwort für den Vergleichstest */
	for( i = 0; i < laenge; ++i )
	    passwd[i] = zeichen[eingang[i]];

	md5_hash( passwd ); /* generiertes Passwort hashen und testen */ <-- hier Aufruf der Funktion

	/* eingang inkrementieren */
	for( i = 0; i < laenge && ++eingang[laenge-i-1] == nbzeichen; i++ )
	    eingang[laenge-i-1] = 0;

	/* return wenn eingang == letzter_eingang */
	for( j = 0; j < laenge; ++j )
	    if( eingang[j] != letzter_eingang[j] )
		break;

	if( j == laenge ) /* eingang == letzter_eingang */
	    return;
    }
}

Code: Alles auswählen
if( strncmp( ( const char * )hash, ( const char * )digest, 5 ) == 0 )

Sollten hier nicht eigentlich mehr Zeichen verglichen werden?

Ja schon. Dann hatte ich dich wohl missverstanden. Du hattest geschrieben, dass sich die Hashes eigentlich so sehr unterscheiden, dass man nicht unbedingt alle Bytes miteinander vergleichen braucht. Zumindest hatte ich das so verstanden. Aber habe es jetzt folgendermaßen geändert:

Code: Alles auswählen

if( memcmp( ( const char * )hash, ( const char * )digest, 16 ) == 0 )

[nufan]

Habe mal die Funktion folgendermaßen umgeschrieben. Verglichen zu vorher etwas schneller. Braucht für 'd3xt3r' 16 min. 23 sek., also 22 Sekunden weniger wie davor.:

22 Sekunden sind doch schon was

Doch das mit MD5_Init() ein einziges mal auf eine static-Variable aufzurufen, würde mich noch interessieren, wie ich das genau umsetzen kann. Also ein kurzes Code-Beispiel wäre nett.

Kann ich gerne machen, wenn du mir sagst was die MD5_*-Funktionen machen ^^ Ist es wirklich notwendig diese Methoden für jede Zeichen-Permutation zu auszuführen? Kannst du nicht immer die gleiche Struktur verwenden und diese immer aktualisieren, anstatt sie jedes mal komplett neu anzulegen und zu initialisieren?

Hier mal die Funktion, welche die Strings erzeugt und auch die o.g. Funktion aufruft.

Code: Alles auswählen

    /* Global */
    time_t zeit1, zeit2;

    typedef void( *func_t )( const char * );

    const char zeichen[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    const int  nbzeichen = sizeof( zeichen ) - 1;

    /* Prototypes */
    static void brute_force( const int * restrict, const int * restrict, int, func_t );
    static void md5_hash( const char * );

    static void brute_force( const int * restrict erster_eingang,
              const int * restrict letzter_eingang, int laenge, func_t md5_hash )
    {
        char passwd[laenge];
        int  eingang[laenge];
        int  i, j;

        for( i = 0; i < laenge; ++i )
       eingang[i] = erster_eingang[i];

        i = 0;

        while( i < laenge )
        {
       /* Generiere das nächste Passwort für den Vergleichstest */
       for( i = 0; i < laenge; ++i )
           passwd[i] = zeichen[eingang[i]];

       md5_hash( passwd ); /* generiertes Passwort hashen und testen */ <-- hier Aufruf der Funktion

       /* eingang inkrementieren */
       for( i = 0; i < laenge && ++eingang[laenge-i-1] == nbzeichen; i++ )
           eingang[laenge-i-1] = 0;

       /* return wenn eingang == letzter_eingang */
       for( j = 0; j < laenge; ++j )
           if( eingang[j] != letzter_eingang[j] )
          break;

       if( j == laenge ) /* eingang == letzter_eingang */
           return;
        }
    }

Hm... das sieht schon ziemlich gut aus. Ich hab jetzt mal unabhängig davon folgenden Code fabriziert:

Code: Alles auswählen

// Pool aus Zeichen, die zur Generierung verwendet wird
static char pool[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
// Index des letzten gültigen Zeichen im Pool (exklusive \0)
static const int maxPoolIndex = sizeof( pool ) - 2;
// Maximale Länge des Passworts
static const int maxLength = 50;
// Speicherbereich, in dem die Passwörter generiert werden
static char str[maxLength];
// Indizes der Zeichen in 'str' in 'pool'
static int poolIndex[maxLength];
// Iteriert über 'str'
static char *strIt;
// Iteriert über 'poolIndex'
static int *indexIt;

// length: Anzahl Zeichen ohne '\0'
void crack( int length )
{
  // Länge muss um 1 erhöht werden, da das letzte Zeichen als Überlauf-Puffer verwendet wird
  ++length;
  // Zeichen des Passworts auf das erste Zeichen im Pool setzen
  memset( str, '0', length );
  memset( poolIndex, 0, length * sizeof( int ) );
  // Adresse des Überlauf-Puffers berechnen
  static char *last = str + length - 1;

  // Bis der Überlauf verwendet wird...
  while( *last == '0' ) 
  {
    //////////////////////////////////////
    // Hier muss 'str' verwendet werden
    //md5_hash( str );
    fprintf( stdout, "%s\n", str );
    //////////////////////////////////////
    // Das erste Zeichen erhöhen
    *str = pool[++(*poolIndex)];
    // Iteratoren auf das erste Zeichen setzen
    strIt = str;
    indexIt = poolIndex;
    // Wenn ein Zeichen den Pool überschreitet, wird es auf das erste
    // Zeichen gesetzt und dafür das nächste um 1 erhöht. Wird der
    // Überauf-Puffer erreicht, wurden alle Kombinationen erstellt.
    while( *indexIt > maxPoolIndex ) 
    {
      *strIt = '0';
      *indexIt = 0;
      ++strIt;
      ++indexIt;
      *strIt = pool[++( *indexIt )];
    } 
  }
}

Ob der schneller ist, musst du wohl selbst testen ^^ Wobei du in dem "str"-String immer ein Zeichen zu viel hast, das '0' (ASCII 48, nicht 0) ist. Aber wenn du sowieso die Anzahl der zu vergleichenden Zeichen angibst, ist das kein Problem.

[3VAD_YNCAL]

Habe mal die Funktion folgendermaßen umgeschrieben. Verglichen zu vorher etwas schneller. Braucht für 'd3xt3r' 16 min. 23 sek., also 22 Sekunden weniger wie davor.:

22 Sekunden sind doch schon was

Auf jeden Fall.

Doch das mit MD5_Init() ein einziges mal auf eine static-Variable aufzurufen, würde mich noch interessieren, wie ich das genau umsetzen kann. Also ein kurzes Code-Beispiel wäre nett.

Kann ich gerne machen, wenn du mir sagst was die MD5_*-Funktionen machen ^^ Ist es wirklich notwendig diese Methoden für jede Zeichen-Permutation zu auszuführen? Kannst du nicht immer die gleiche Struktur verwenden und diese immer aktualisieren, anstatt sie jedes mal komplett neu anzulegen und zu initialisieren?

Habe die MD5-Funktionen nicht selber geschrieben sondern nur implementiert.

Code: Alles auswählen

#include <sys/types.h>
#include <openssl/md5.h>

Beim kompilieren dann u.a. mit -lcrypto.

Wahrscheinlich ist es aber so nicht ganz sinnvoll, die erzeugten Wörter zu hashen und zu vergleichen, oder? Zumindest was die Performance anbelangt. Was meint ihr?

Ich werde deinen Code heute gleich mal ausprobieren und dir dann Feedback geben. Jedenfalls vielen Dank dafür. Es ist immer interessant zu sehen, welche Möglichkeiten es noch gibt um das umzusetzen.

Ansonsten wäre ich für weitere Tipps bzgl. der MD5-Funktionen sehr dankbar. Zumindest wie man das hashen und vergleichen noch etwas beschleunigen könnte.

[Kerli]

Ja schon. Dann hatte ich dich wohl missverstanden. Du hattest geschrieben, dass sich die Hashes eigentlich so sehr unterscheiden, dass man nicht unbedingt alle Bytes miteinander vergleichen braucht. Zumindest hatte ich das so verstanden.

Ich hab eigentlich gemeint, dass snprintf immer den ganze Hash in einen String umwandelt und dann vergleicht, obwohl mit sehr hoher Wahrscheinlichkeit der Unterschied zwischen verschiedenen Hashwerten bereits in den ersten paar Zeichen auftritt. ^^

[3VAD_YNCAL]

Ja schon. Dann hatte ich dich wohl missverstanden. Du hattest geschrieben, dass sich die Hashes eigentlich so sehr unterscheiden, dass man nicht unbedingt alle Bytes miteinander vergleichen braucht. Zumindest hatte ich das so verstanden.

Ich hab eigentlich gemeint, dass snprintf immer den ganze Hash in einen String umwandelt und dann vergleicht, obwohl mit sehr hoher Wahrscheinlichkeit der Unterschied zwischen verschiedenen Hashwerten bereits in den ersten paar Zeichen auftritt. ^^

Sorry. Hatte dich missverstanden.

[nufan]

Doch das mit MD5_Init() ein einziges mal auf eine static-Variable aufzurufen, würde mich noch interessieren, wie ich das genau umsetzen kann. Also ein kurzes Code-Beispiel wäre nett.

Kann ich gerne machen, wenn du mir sagst was die MD5_*-Funktionen machen ^^ Ist es wirklich notwendig diese Methoden für jede Zeichen-Permutation zu auszuführen? Kannst du nicht immer die gleiche Struktur verwenden und diese immer aktualisieren, anstatt sie jedes mal komplett neu anzulegen und zu initialisieren?

Habe die MD5-Funktionen nicht selber geschrieben sondern nur implementiert.

Code: Alles auswählen

#include <sys/types.h>
#include <openssl/md5.h>

Beim kompilieren dann u.a. mit -lcrypto.

Ausschnit aus der Ausgabe von "man 3 md5":

MD2(), MD4(), and MD5() compute the MD2, MD4, and MD5 message digest of
the n bytes at d and place it in md (which must have space for
MD2_DIGEST_LENGTH == MD4_DIGEST_LENGTH == MD5_DIGEST_LENGTH == 16 bytes
of output). If md is NULL, the digest is placed in a static array.

The following functions may be used if the message is not completely
stored in memory:

MD2_Init() initializes a MD2_CTX structure.

MD2_Update() can be called repeatedly with chunks of the message to be
hashed (len bytes at data).

MD2_Final() places the message digest in md, which must have space for
MD2_DIGEST_LENGTH == 16 bytes of output, and erases the MD2_CTX.

Hier sehe ich gleich 2 Möglichkeiten deinen Code zu verbessern.

1. Du hast deine Daten (dein mögliches Passwort) komplett im Speicher. Du könntest also auch einfach die Methode MD5() verwenden, ohne die Struktur überhaupt anzulegen.

2. MD5_Final() löscht deine Daten in der MD5_CTX-Struktur. Wenn du diese Struktur als static anlegst und ein einziges mal mit MD5_Init() initialisierst, könntest du versuchen nur mehr MD5_Update() und MD5_Final() darauf aufzurufen, alles andere ist ja bereits erledigt. Da bin ich mir aber nicht ganz sicher, der 1. Punkt sieht sowieso noch vielversprechender aus.

Wahrscheinlich ist es aber so nicht ganz sinnvoll, die erzeugten Wörter zu hashen und zu vergleichen, oder? Zumindest was die Performance anbelangt. Was meint ihr?

Wie willst du das sonst lösen? Besser kannst du das nur machen, wenn du eine Schwachstelle in MD5 kennst, über die du das Ergebnis schneller finden kannst.

Ich werde deinen Code heute gleich mal ausprobieren und dir dann Feedback geben. Jedenfalls vielen Dank dafür. Es ist immer interessant zu sehen, welche Möglichkeiten es noch gibt um das umzusetzen.

Kein Problem Wenns fragen gibt nur her damit

[3VAD_YNCAL]

Ausschnit aus der Ausgabe von "man 3 md5":

MD2(), MD4(), and MD5() compute the MD2, MD4, and MD5 message digest of
the n bytes at d and place it in md (which must have space for
MD2_DIGEST_LENGTH == MD4_DIGEST_LENGTH == MD5_DIGEST_LENGTH == 16 bytes
of output). If md is NULL, the digest is placed in a static array.

The following functions may be used if the message is not completely
stored in memory:

MD2_Init() initializes a MD2_CTX structure.

MD2_Update() can be called repeatedly with chunks of the message to be
hashed (len bytes at data).

MD2_Final() places the message digest in md, which must have space for
MD2_DIGEST_LENGTH == 16 bytes of output, and erases the MD2_CTX.

Hier sehe ich gleich 2 Möglichkeiten deinen Code zu verbessern.

1. Du hast deine Daten (dein mögliches Passwort) komplett im Speicher. Du könntest also auch einfach die Methode MD5 anlegen, ohne die Struktur überhaupt anzulegen.

Mit mögliches Passwort meinst du z.B. das, oder?

Code: Alles auswählen

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

Wie funktioniert das? Also die Methode MD5 anlegen, ohne die Struktur?

2. MD5_Final() löscht deine Daten in der MD5_CTX-Struktur. Wenn du diese Struktur als static anlegst und ein einziges mal mit MD5_Init() initialisierst, könntest du versuchen nur mehr MD5_Update() und MD5_Final() darauf aufzurufen, alles andere ist ja bereits erledigt. Da bin ich mir aber nicht ganz sicher, der 1. Punkt sieht sowieso noch vielversprechender aus.

Die MD5_CTX-Struktur als static anzulegen habe ich probiert. Das hat aber nicht funktioniert. D.h. das Programm hat dann plötzlich keine Übereinstimmungen gefunden. Vermutlich lief dann beim hashen was falsch.
Dann habe ich auch versucht die Struktur global anzulegen. Initialisiert habe ich die Struktur dann nur einmal in der main()-Funktion. So das in der md5_hash()-Funktion nur MD5_Update() und MD5_Final() aufgerufen werden. Das hat aber leider auch nicht funktioniert.

Wahrscheinlich ist es aber so nicht ganz sinnvoll, die erzeugten Wörter zu hashen und zu vergleichen, oder? Zumindest was die Performance anbelangt. Was meint ihr?

Wie willst du das sonst lösen? Besser kannst du das nur machen, wenn du eine Schwachstelle in MD5 kennst, über die du das Ergebnis schneller finden kannst.

Ja stimmt.

Ich werde deinen Code heute gleich mal ausprobieren und dir dann Feedback geben. Jedenfalls vielen Dank dafür. Es ist immer interessant zu sehen, welche Möglichkeiten es noch gibt um das umzusetzen.

Kein Problem Wenns fragen gibt nur her damit

Die kommen bestimmt.

[nufan]

Ausschnit aus der Ausgabe von "man 3 md5":

MD2(), MD4(), and MD5() compute the MD2, MD4, and MD5 message digest of
the n bytes at d and place it in md (which must have space for
MD2_DIGEST_LENGTH == MD4_DIGEST_LENGTH == MD5_DIGEST_LENGTH == 16 bytes
of output). If md is NULL, the digest is placed in a static array.

The following functions may be used if the message is not completely
stored in memory:

MD2_Init() initializes a MD2_CTX structure.

MD2_Update() can be called repeatedly with chunks of the message to be
hashed (len bytes at data).

MD2_Final() places the message digest in md, which must have space for
MD2_DIGEST_LENGTH == 16 bytes of output, and erases the MD2_CTX.

Hier sehe ich gleich 2 Möglichkeiten deinen Code zu verbessern.

1. Du hast deine Daten (dein mögliches Passwort) komplett im Speicher. Du könntest also auch einfach die Methode MD5 anlegen, ohne die Struktur überhaupt anzulegen.

Mit mögliches Passwort meinst du z.B. das, oder?

Code: Alles auswählen

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

Wie funktioniert das? Also die Methode MD5 anlegen, ohne die Struktur?

Sorry, war ein Tippfehler von mir, habs inzwischen editiert. Ich meinte natürlich die Methode MD5() aufrufen und nicht anlegen. Mit einem möglichen Passwort meinte ich eigentlich deine Variable "str".
Du kannst nun:

Code: Alles auswählen

unsigned char *MD5(const unsigned char *d, unsigned long n,
                         unsigned char *md);

anstatt:

Code: Alles auswählen

        int MD5_Init(MD5_CTX *c);
        int MD5_Update(MD5_CTX *c, const void *data,
                         unsigned long len);
        int MD5_Final(unsigned char *md, MD5_CTX *c)

verwenden.
Aus:

Code: Alles auswählen

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

Machst du dann einfach:

Code: Alles auswählen

MD5( str, strlen( str ), digest );

Ist dein letzter Parameter NULL, wird ein Zeiger auf ein statisches Array mit dem Ergebnis zurückgegeben. Ob das nun effizienter ist als selbst einen Speicherbereich zu übergeben, müsstest du wieder selbst rausfinden.

[3VAD_YNCAL]

Ah okay cool. Danke. Werde ich gleich mal ausprobieren.

[3VAD_YNCAL]

Okay, ich musste nun feststellen, dass

Code: Alles auswählen

MD5( ( const unsigned char * )str, strlen( str ), digest );

17 min. 34 sek. und

Code: Alles auswählen

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

nur 16 min. und 22 sek. benötigt und somit schneller ist.