Benötige Hilfe bei kleinem Brute Force Programm in C unter Linux



  • Hallo zusammen,

    ich versuche mich gerade an ein Brute Force Programm in der Programmiersprache C unter Linux.
    Die Generierung der Wörter wird mittels OpenMP parallelisiert. Es klappt an für sich relativ gut.
    Allerdings treten hierbei nach ein paar Nebeneffekte auf, die mich stören.
    Ich werde hier zwei Versionen meiner Quellcodes posten. Einmal ohne Hasherzeugung bzw. Hashvergleich (MD5).
    Bei der ersten Version funktioniert alles soweit okay. Allerdings glaube ich das man da bei der Parallelisierung
    bestimmt noch einiges verbessern kann.
    Bei der zweiten Version des Quellcodes ist hashing und Hash-Vergleich mit dabei. Dort kommt es nämlich vor, dass
    das gesuchte Wort ab und zu einfach nicht gefunden wird. Also zumindest wenn alle CPU-Kerne genutzt werden. In meinem
    Fall 8 Kerne (4 physikalisch und 4 virtuell). Aber nur ab und zu. Wenn ich das Programm beispielsweise zehn Mal starte,
    findet es das gesuchte Wort von zehn Mal zwei Mal nicht. So als wenn der Prozessor sich bei der Berechnung
    irgendwie verzetteln würde.

    Mein Prozessor: Intel Core i7-920@2.66GHz
    Betriebssystem: Ubuntu 14.04 LTS 64-Bit

    Vielleicht könnt ihr mir dabei helfen die Ursache zu finden und das Ganze noch etwas zu verbessern.
    Ich würde mich jedenfalls sehr über eure Hilfe freuen.

    Quellcode Nr. 1 (ohne hashen und Hashvergleich):

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <omp.h>
    #include <time.h>
    
    /*
     * Hier sollen dann später noch weitere Optionen hinzu kommen...
     * z.B. LiteralsUpper[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"...
     * und  Digits[] = "0123456789"...
     * usw.
     */
    const char  LiteralsLower[] = "abcdefghijklmnopqrstuvwxyz";
    const int   NLiteralsLower  = sizeof( LiteralsLower ) - 1;
    time_t      StartTime, EndTime;
    
    static void BruteForce( const int * restrict, const int * restrict, const char *, const int *, int );
    
    int main()
    {
        const int  *BFOptionSize  = &NLiteralsLower;
        const char *BFOption      = LiteralsLower;
        int        PasswordLength = 7;
    
        /* Timer starten */
        time( &StartTime );
    
        #pragma omp parallel default( shared )
        for( int PWLength = 0; PWLength < PasswordLength + 1; ++PWLength )
        {
            /* Array-Größe für FstEntry und LstEntry festlegen */
            int FstEntry[PWLength], LstEntry[PWLength];
    
            /* Array-Felder mit 0 initialisieren */
            for( int j = 0; j < PWLength; ++j )
                FstEntry[j] = LstEntry[j] = 0;
    
            #pragma omp for schedule( dynamic )
            for( int i = 0; i < *BFOptionSize; ++i )
            {
                FstEntry[0] = i;
                LstEntry[0] = i + 1;
                BruteForce( FstEntry, LstEntry, BFOption, BFOptionSize, PWLength );
            }
        }
    
        /* Timer stoppen */
        time( &EndTime );
    
        puts( "!!! Wort nicht gefunden !!!" );
    
        printf( "Elapsed time: %ld minutes %ld seconds\n\n", ( EndTime - StartTime ) / 60, ( EndTime - StartTime ) % 60 );
    
        return EXIT_FAILURE;
    }
    
    static void BruteForce( const int * restrict FirstEntry, const int * restrict LastEntry, const char *Letters, const int *NLetters, int PSSWDLength )
    {
        char Password[PSSWDLength];
        int  Entry[PSSWDLength + 1];
        int  i, j;
    
        /* Null-Byte hinzufügen */
        memset( Entry, '\0', PSSWDLength );
        memset( Password, '\0', PSSWDLength );
    
        /* FirstEntry in Entry kopieren */
        for( i = 0; i < PSSWDLength; ++i )
            Entry[i] = FirstEntry[i];
    
        i = 0;
    
        while( i < PSSWDLength )
        {
            /* Generiere Passwort für Hash-Vergleich */
            for( i = 0; i < PSSWDLength; ++i )
                Password[i] = Letters[Entry[i]];
    
            if( strncmp( "davex", Password, strlen( "davex" ) ) == 0 )
            {
                fprintf( stdout, "!!! Wort gefunden: %s !!!\n", Password );
    
                /* Timer stoppen */
                time( &EndTime );
    
                printf( "Elapsed time: %ld minutes %ld seconds\n\n", ( EndTime - StartTime ) / 60, ( EndTime - StartTime ) % 60 );
    
                exit( EXIT_SUCCESS );
            }
    
            /* Entry inkrementieren */
            for( i = 0; i < PSSWDLength && ++Entry[PSSWDLength-i-1] == *NLetters; i++ )
                Entry[PSSWDLength-i-1] = 0;
    
            /* Return wenn Entry != LastEntry raus aus der Schleife */
            for( j = 0; j < PSSWDLength; ++j )
                if( Entry[j] != LastEntry[j] )
                    break;
    
            /* wenn Entry == LastEntry Funktion verlassen */
            if( j == PSSWDLength )
                return;
        }
    }
    

    Beim kompilieren bitte folgendes angeben: -std=c99 -fopenmp.
    Zunächst wäre es mir wichtig zu sehen ob man hier schon was optimieren kann.
    Später könnten wir uns dann dem zweiten Quellcode widmen. 🙂

    Wie gesagt. Ich würde mich sehr über eure Hilfe freuen.

    Grüße DaveX 😉


  • Mod

    Bei der zweiten Version des Quellcodes ist hashing und Hash-Vergleich mit dabei. Dort kommt es nämlich vor, dass
    das gesuchte Wort ab und zu einfach nicht gefunden wird.

    Heißt das, der Code, den du hier gezeigt hast, funktioniert fehlerfrei (also ich konnte zumindest keinen Fehler entdecken) und du möchtest jetzt von uns wissen, was an der zweiten Version, die du hier nicht gezeigt hast, fehlerhaft ist?



  • Ja genau. Der Code den ich gepostet habe funktioniert soweit fehlerfrei. Nur war ich mir mit den pragmas nicht ganz sicher. Also ob man da noch etwas verbessern könnte. Zum nächsten Code den ich jetzt posten werde tritt folgendes Problem auf:
    Wie ich bereits erwähnt habe, kommt es zu einem seltsamen Fehler.
    Wenn beim brute-forcing alle Kerne genutzt werden. Nämlich das hin- und wieder das gesuchte Wort nicht gefunden wird. Also grob geschätzt bei jedem 4. bis 6. Programmstart.
    Bleiben wir mal beim Beispiel 'davex'.
    Der MD5-Hash zu 'davex' ist folgender: e7a2dd71fbb5707d6947e61d95003453.

    Wenn ich beispielsweise einstelle, dass er beim brute-forcing Wörter bis max. sechs Stellen erzeugen soll und das nur mit Kleinbuchstaben, geht es mittels omp natürlich super schnell.

    D.h. wenn ich das Programm starte kommt folgende Ausgabe:

    !!! Wort gefunden: 'davex' !!!
    Elapsed time: 0 minutes 0 seconds
    

    Wenn ich das ein paar Mal hintereinander mache, kommt es eben vor, dass das Programm rechnet und weiter rechnet bis es letztendlich 'zzzzzz' erzeugt hat und ausgibt, dass es keinen Treffer gelandet hat.

    Aber wie gesagt, eben nicht immer. Komischerweiser aber nur wenn alle Kerne genutzt und die erzeugten Wörter gehasht und verglichen werden.
    Füge ich beispielsweise vorher

    omp_set_num_threads(4);
    

    im Code ein, entsteht der Fehler nicht.

    Hier aber zunächst mal die zweite Version:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <omp.h>
    #include <openssl/md5.h>
    #include <time.h>
    
    const char   LiteralsLower[] = "abcdefghijklmnopqrstuvwxyz";
    const int    NLiteralsLower  = sizeof( LiteralsLower ) - 1;
    char         HexByteHash[16];
    time_t       StartTime, EndTime;
    
    static  void MD5Hash( const char * );
    static  void BruteForce( const int * restrict, const int * restrict, const char *, const int *, int );
    
    int main()
    {
        const char HashAsString[] = "e7a2dd71fbb5707d6947e61d95003453";
        const int  *BFOptionSize  = &NLiteralsLower;
        const char *BFOption      = LiteralsLower;
        int        PasswordLength = 6;
        int        StrLength      = strlen( HashAsString );
    
        for( int i = 0; i < StrLength / 2 ; i++ )
        {
            if( !sscanf( HashAsString + 2 * i, "%02x", ( unsigned int * ) &HexByteHash[i] ) )
            {
                fprintf( stderr, "FEHLER!!! -> '%s' ist kein Hash-Wert!\n", HashAsString );
                exit( EXIT_FAILURE );
            }
        }
    
        /* Timer starten */
        time( &StartTime );
    
        #pragma omp parallel default( shared )
        for( int PWLength = 0; PWLength < PasswordLength + 1; ++PWLength )
        {
            /* Array-Größe für FstEntry und LstEntry festlegen */
            int FstEntry[PWLength], LstEntry[PWLength];
    
            /* Array-Felder mit 0 initialisieren */
            for( int j = 0; j < PWLength; ++j )
                FstEntry[j] = LstEntry[j] = 0;
    
            #pragma omp for schedule( dynamic )
            for( int i = 0; i < *BFOptionSize; ++i )
            {
                FstEntry[0] = i;
                LstEntry[0] = i + 1;
                BruteForce( FstEntry, LstEntry, BFOption, BFOptionSize, PWLength );
            }
        }
    
        /* Timer stoppen */
        time( &EndTime );
    
        puts( "!!! Wort nicht gefunden !!!" );
    
        printf( "Elapsed time: %ld minutes %ld seconds\n\n", ( EndTime - StartTime ) / 60, ( EndTime - StartTime ) % 60 );
    
        return EXIT_FAILURE;
    }
    
    static void MD5Hash( const char *PasswordStringPointer )
    {
        unsigned char Digest[16];
    
        /* MD5-Hash erzeugen */
        MD5_CTX md5;
        MD5_Init( &md5 );
        MD5_Update( &md5, PasswordStringPointer, strlen( PasswordStringPointer ) );
        MD5_Final( Digest, &md5 );
    
        if( memcmp( HexByteHash, Digest, 16 ) == 0 )
        {
            printf( "!!! Wort gefunden: '%s' !!!\n", PasswordStringPointer );
    
            /* Timer stoppen */
            time( &EndTime );
    
            printf( "Elapsed time: %ld minutes %ld seconds\n\n", ( EndTime - StartTime ) / 60, ( EndTime - StartTime ) % 60 );
    
            /* Passwortsuche war erfolgreich */
            exit( EXIT_SUCCESS);
        }
    }
    
    static void BruteForce( const int * restrict FirstEntry, const int * restrict LastEntry, const char *Letters, const int *NLetters, int PSSWDLength )
    {
        char Password[PSSWDLength];
        int  Entry[PSSWDLength + 1];
        int  i, j;
    
        /* Null-Byte hinzufügen */
        memset( Entry, '\0', PSSWDLength );
        memset( Password, '\0', PSSWDLength );
    
        /* FirstEntry in Entry kopieren */
        for( i = 0; i < PSSWDLength; ++i )
            Entry[i] = FirstEntry[i];
    
        i = 0;
    
        while( i < PSSWDLength )
        {
            /* Generiere Passwort für Hash-Vergleich */
            for( i = 0; i < PSSWDLength; ++i )
                Password[i] = Letters[Entry[i]];
            /* hier wird gehasht und verglichen */
            MD5Hash( Password );
    
            /* Entry inkrementieren */
            for( i = 0; i < PSSWDLength && ++Entry[PSSWDLength-i-1] == *NLetters; i++ )
                Entry[PSSWDLength-i-1] = 0;
    
            /* Return wenn Entry != LastEntry raus aus der Schleife */
            for( j = 0; j < PSSWDLength; ++j )
                if( Entry[j] != LastEntry[j] )
                    break;
    
            /* wenn Entry == LastEntry Funktion verlassen */
            if( j == PSSWDLength )
                return;
        }
    }
    

    Fällt euch da was auf?



  • Und wer sagt dir, dass deine MD5 Bibliothek multithreadingfähig ist?



  • Ja niemand. Ich dachte mir das fast schon. Deswegen probierte ich das auch mit

    omp_set_num_threads(4)
    

    aus und stellte fest, dass es einwandfrei funktioniert. Aber was kann ich tun, damit es auch mit multithreading geht?


  • Mod

    DaveX schrieb:

    Ja niemand. Ich dachte mir das fast schon. Deswegen probierte ich das auch mit

    omp_set_num_threads(4)
    

    aus und stellte fest, dass es einwandfrei funktioniert. Aber was kann ich tun, damit es auch mit multithreading geht?

    Du darfst halt keine nicht-threadsicheren Funktionen parallel aufrufen. Dass es mit 4 Threads klappt ist reiner Zufall, sofern es wirklich an der MD5-Bibliothek liegt. Falls diese die Ursache ist, dann musst du eben
    -gucken, ob die auch threadsichere Funktionen anbietet oder man sie anderweitig threadsicher machen kann
    oder
    -eine andere Bibliothek benutzen, die threadsichere Funktionen anbietet
    oder zur Not
    -selber eine threadsichere Funktion dafür schreiben

    PS: Die richtige Antwort bei OpenSSL ist übrigens die erste Methode. Aber Handbücher einer Bibliothek zu lesen ist eine wichtige Programmiererfähigkeit, daher sage ich dir nicht genau, wie das geht.



  • Okay. 🙂 Dann werde ich mich da mal einlesen.
    Jedenfalls vielen Dank. Ihr habt mich somit auf den richtigen Weg gebracht. Nun weiß ich was ich zu tun habe. 😉

    Grüße
    DaveX


Log in to reply