How can I get this brute force algorithm to check letters incrementally

Question

For this assignment I have to use pthreads in C to make a brute force password cracker.

The code below uses for loops to generate a 6 letter password (ideally 8 letters long) and then I use crypt_r to hash it and compare it with a hash and salt that I give the program at execution.

The hash and salt are taken in at the start, stored in a struct called dataStr which then feeds it to pthreadCreate.

It seems pretty straight forward but even when I memset the array to a null terminating char, at execution the program still sets the whole thing to 'aaaaaa'. The problem with this is that it ignores passwords that are 1-4 chars long.

Here is the data structure I'm using:

typedef struct {

    char * hash;            //hashed code given in argv[1]
    char * salt;            //salt for hashed code given in argv[2]

    int start;              //starting char in alphabet for first letter
    int end;                //ending char in alphabet for first letter

    int id;                 //thread id

} dataStruct;

Size definitions :

//Definitions
#define PW_SIZE 8
#define ALPHABET_SIZE 66
#define HASH_MAX_SIZE 128

and here is the code itself

void * thread(void * arg) {

    struct timespec start, finish;          //Data structure for time.h library
    clock_gettime(CLOCK_MONOTONIC, &start); //Start chronometer
    double elapsed;

    struct crypt_data* cdata = (struct crypt_data *)malloc(sizeof(struct crypt_data));
    cdata->initialized = 0;

    dataStruct dataStr = *((dataStruct*)(arg)); //receive structure in arguement

    const char * alphabet = get_alphabet();     //create alphabet

    bool pw_found = false;                      //boolean used for 
    int retDone = 1;

    char * pwd = malloc(PW_SIZE * sizeof(char));
    memset(pwd, '\0', PW_SIZE);

    int i,j,k,l,m,n;

    for (i = dataStr.start; i <= dataStr.end; i++) {            
        for (j = 0; j <= ALPHABET_SIZE; j++) {
            for (k = 0; k <= ALPHABET_SIZE; k++) {
                for (l = 0; l <= ALPHABET_SIZE; l++) {
                    for (m = 0; m <= ALPHABET_SIZE; m++) {
                        for (n = 0; n <= ALPHABET_SIZE; n++) {

                            if (pw_found) {
                                clock_gettime(CLOCK_MONOTONIC, &finish);        
                                elapsed = finish.tv_sec - start.tv_sec;
                                elapsed += (finish.tv_nsec - start.tv_nsec) / 1000000000.0; 
                                printf("Time elapsed : %f sec(s) \n\n", elapsed);   //Time

                                pthread_exit(&retDone);                                 
                            }                           

                            pwd[0] = alphabet[i];   
                            pwd[1] = alphabet[j];   
                            pwd[2] = alphabet[k];
                            pwd[3] = alphabet[l];
                            pwd[4] = alphabet[m];
                            pwd[5] = alphabet[n];

                            printf("%s\n", pwd);

                            char * hash = crypt_r(pwd, dataStr.salt, cdata);

                            if (strcmp(hash, dataStr.hash) == 0) {
                                printf("\nPassword     : %s\n", pwd);
                                pw_found = true;
                            }
                        }
                    }
                }
            }
        }                       
    }

    pthread_exit(&retDone); 
}

Here's what it produces at execution:

I'd like to learn how I can change the 6 loops somehow in order to get the program to first only search in 1 letter chars, then 2, then 3 and increment from there.

Any help is appreciated. Thanks a lot !

PS - I don't mind emailing someone the code for a global view.

Answer 1

Pointers can be used to accomplish this. ppw will point to somewhere in the pw array. pch will point to somewhere in the characters array. Incrementing(++) and decrementing(--) the pointers moves the pointers within the elements of their respective arrays. Dereferencing(*) gives access to the values that the pointers point to. used is the number of elements in pw that have been used. It starts at 0 for the first element and increases toward SIZE. characters may be modified to include the valid letters, numbers and symbols. Just be careful that there are no duplicates. If, for example, the letter u appears more than once, the program will get in an infinite loop.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 5

int main( void)
{
    char pw[SIZE + 1] = "";
    char *ppw = NULL;
    char *pch = NULL;
    char characters[] = "abcdefghijklmnopqrstuvwxyz";
    int used = 0;
    int out = 1;
    int last = strlen ( characters) - 1;

    //set pw
    pw[used] = characters[0];
    pw[used + 1] = '\0';

    while ( used < SIZE) {//loop until all elements of pw have been used
        ppw = &pw[used];//set ppw to point to last used element of pw
        while ( ppw >= pw) {//so ppw always points to an element of pw
            if ( ( pch = strchr ( characters, *ppw)) != NULL) {//get pointer into characters for current value that ppw point to
                if ( out) {//print when appropriate
                    printf ( "%s\n", pw);
                }
                if ( pch < &characters[last]) {//pch does not point to last element of characters
                    ++pch;//pch points to next element of characters
                    *ppw = *pch;//set what ppw points to to be the same as what pch points to
                    if ( ppw != &pw[used]) {//ppw is not pointing to last element of pw
                        ppw = &pw[used];
                    }
                    out = 1;//allow printing
                }
                else {//pch is pointing to last element of characters
                    *ppw = characters[0];//set what ppw points to to be the first element of characters
                    ppw--;//ppw points to next lower element of pw. ex from pw[n] to pw[n-1]
                    out = 0;//disable printing
                }
            }
        }//exit loop when ppw points to address less than pw
        used++;//increase elements in use
        memset ( pw, characters[0], used);//reset all elements to first element of characters
        pw[used + 1] = '\0';//just in case, terminate
    }//exit loop when all elements have been used

    exit ( 0);
}

This seems to be working. Added two lines to set out to 1 and added used + 1 to the call to memset.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// one more than the desired size
#define SIZE 4

int main( void)
{
    char pw[SIZE] = "";
    char *ppw = NULL;
    char *pch = NULL;
    char characters[] = "abc";
    int used = 0;
    int out = 1;
    int last = strlen ( characters) - 1;

    //set pw as character[0]
    pw[used] = characters[0];
    pw[used + 1] = '\0';

    while ( used < SIZE - 1) {//loop until all elements of pw have been used
        ppw = &pw[used];//set ppw to point to last used element of pw
        out = 1;
        while ( ppw >= pw) {//so ppw always points to an element of pw
            if ( ( pch = strchr ( characters, *ppw)) != NULL) {//get pointer into characters for current value that ppw point to
                if ( out) {//print when appropriate
                    printf ( "%s\n", pw);
                }
                out = 1;
                if ( pch < &characters[last]) {//pch does not point to last element of characters
                    ++pch;//pch points to next element of characters
                    *ppw = *pch;//set what ppw points to to be the same as what pch points to
                    if ( ppw != &pw[used]) {//ppw is not pointing to last element of pw
                        ppw = &pw[used];
                    }
                }
                else {//pch is pointing to last element of characters
                    *ppw = characters[0];//set what ppw points to to be the first element of characters
                    ppw--;//ppw points to next lower element of pw. ex from pw[n] to pw[n-1]
                    out = 0;//disable printing
                }
            }
        }//exit loop when ppw points to address less than pw
        used++;//increase elements in use
        memset ( pw, characters[0], used + 1);//reset all elements to first element of characters
        pw[used + 1] = '\0';//just in case, terminate
    }//exit loop when all elements have been used

    exit ( 0);
}