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.

You do not show the size definitions etc, but usually a loop such as `for (j = 0; j <= ALPHABET_SIZE; j++)` followed by `pwd[1] = alphabet[j];` is over by 1, a recipe for disaster. — Weather Vane, Nov 02 '16 at 20:36
Well, they help improve your question to follow site rules. Which in terms increases the chance of your question to get an answer. I'd say they are very well constructive. — too honest for this site, Nov 02 '16 at 20:46
When I see 6 inner loops there is something wrong In the design — Ed Heal, Nov 02 '16 at 20:52
@EdHeal I sat down and tried to code it recursively but I couldn't figure it out... please help me ! — John Livingston, Nov 02 '16 at 21:01
Most likely it should be `j < ALPHABET_SIZE` otherwise this is basically the correct approach, it's how brute force is done with many loops. There are minor improvements to make, but most of the work is done by `crypt_r` which will slow down the program. — Barmak Shemirani, Nov 07 '16 at 16:55
[don't cast the result of malloc in C](http://stackoverflow.com/q/605845/995714) — phuclv, Nov 07 '16 at 16:57

user3121023 · Accepted Answer · 2016-11-07T16:48:50.977

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);
}

This is great ! I integrated this within a pthread in order to brute force a password and it works like a charm. It slows down as we approach 6 chars. So what I did was ask at the start of the program how many threads we want to execute. Based on that, I chop up the alphabet (divided by the number of threads). That way each thread can work on a certain range. Would you know where in this code I could set my start and end points for the character generation? Here's a link to the full code : [Github link](https://github.com/warisp/pw_cracker) — John Livingston, Nov 03 '16 at 19:00
I use this function to print up to a lenght of 3 for just char * characters = [a,b,c]; and once it gets to cc it never tries aaa,aab,aac. Instead it jumps straight to aba, abb, abc. — John Livingston, Nov 07 '16 at 15:45
This one is good but there is no need to define SIZE to one more than desired as in your first while condition you do (SIZE - 1). By removing this we can define SIZE to the actual size desired. — John Livingston, Nov 07 '16 at 19:37
change the last 2 lines to `memset(pw, characters[0], used);` and `pw[used]='\0';` — Barmak Shemirani, Nov 08 '16 at 00:45

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

1 Answers1