C program to crack passwords

Question

I have implemented a program in C to crack passwords by generating all possible combinations of words ([A-Z][a-z]) up to the length of 5. While the program works, I would like to receive comments on the efficiency of the algorithm and other design decisions that would improve the code. The exercise is part of the course CS50 by Harvard.

I timed the program using unix's time and the time the program took to print all the combinations was

**real**    14m39.433s; 
**user**    0m10.040s;
**sys**     0m36.356s. 

CS50.h is a library developed for the course as training wheels for students. String (char*) and Bool are types defined in this library.

#define _XOPEN_SOURCE
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <cs50.h>

int main(int argc, char *argv[])
{
    if(argc != 2)
    {
        printf("Usage: ./crack hash\n");
        return 1;
    }

    string alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    char password[6] = "\0\0\0\0\0\0";
    string hash = argv[1];
    char salt[3];
    memcpy(salt, hash, 2);
    salt[2] = '\0';

    bool flag = false;
    int alphabet_len = 52;

    for(int i = 0; i < alphabet_len; i++)
    {
        password[0] = alphabet[i];
        password[1] = password[2] = password[3] = password[4] = '\0';
        if(!strcmp(hash, crypt(password, salt)))
        {
            flag = true;
            break;
        }
        for(int j = 0; j < alphabet_len; j++)
        {
            password[1] = alphabet[j];
            password[2] = password[3] = password[4] = '\0';
            if(!strcmp(hash, crypt(password, salt)))
            {
                flag = true;
                break;
            }
            for(int k = 0; k < alphabet_len; k++)
            {
                password[2] = alphabet[k];
                password[3] = password[4] = '\0';
                if(!strcmp(hash, crypt(password, salt)))
                {
                    flag = true;
                    break;
                }
                for(int l = 0; l < alphabet_len; l++)
                {
                    password[3] = alphabet[l];
                    password[4] = '\0';
                    if(!strcmp(hash, crypt(password, salt)))
                    {
                        flag = true;
                        break;
                    }
                    for(int m = 0; m < alphabet_len; m++)
                    {
                        password[4] = alphabet[m];
                        if(!strcmp(hash, crypt(password, salt)))
                        {
                            flag = true;
                            break;
                        }
                    }
                    if(flag)
                        break;
                }
                if(flag)
                    break;
            }
            if(flag)
                break;
        }
        if(flag)
            break;
    }

    if(flag)
        printf("Password: %s\n", password);
    else
        printf("Password not found\n");
}

Answer 1

cs50.h?

This seems less like a set of "training wheels" and more like a bicycle for fish. It's potentially confusing, opaque, and doesn't seem all that useful. If I were you, I'd be learning how to code in real C - using char*, and bool from stdbool.h.

Don't store things that should be computed

Your string alphabet shouldn't exist. Just iterate a char between a-z and A-Z. Characters can be incremented the same way that integers can.

Input validation

It seems like you expect hash to be two characters long, but you don't check that. You should be checking it with strlen; then you can issue memcpy without later setting a null terminator, as it'll be null-terminated already.

DRY

Don't repeat yourself. This is the most important aspect of the program that needs improvement. This block:

                for(int m = 0; m < alphabet_len; m++)
                {
                    password[4] = alphabet[m];
                    if(!strcmp(hash, crypt(password, salt)))
                    {
                        flag = true;
                        break;
                    }
                }
                if(flag)
                    break;

is repeated nearly verbatim five times. There are many different ways to condense this. The easiest is probably a recursive function that calls itself with an increasing depth integer. This may actually decrease the performance of the application, but that's up to you to test. There are also ways to rewrite this loop to have state so that neither copy-and-paste nor recursion are necessary; you'll probably want to compare such a method against a recursive method to see which is more performant and clean.

Answer 2

regarding:

    printf("Usage: ./crack hash\n");

1. Error messages should be output to stderr, not stdout.
2. an executable can be renamed, so 'crack' is not a good thing to use.

Suggest:

    fprintf( stderr, "USAGE: %s hash\n", argv[0] );

Note: argv[0] always contains the executable name

Answer 3

A function

    bool flag = false;
    int alphabet_len = 52;

    for(int i = 0; i < alphabet_len; i++)
    {
        password[0] = alphabet[i];
        password[1] = password[2] = password[3] = password[4] = '\0';
        if(!strcmp(hash, crypt(password, salt)))
        {
            flag = true;
            break;
        }
        for(int j = 0; j < alphabet_len; j++)
        {
            password[1] = alphabet[j];
            password[2] = password[3] = password[4] = '\0';
            if(!strcmp(hash, crypt(password, salt)))
            {
                flag = true;
                break;
            }
            for(int k = 0; k < alphabet_len; k++)
            {
                password[2] = alphabet[k];
                password[3] = password[4] = '\0';
                if(!strcmp(hash, crypt(password, salt)))
                {
                    flag = true;
                    break;
                }
                for(int l = 0; l < alphabet_len; l++)
                {
                    password[3] = alphabet[l];
                    password[4] = '\0';
                    if(!strcmp(hash, crypt(password, salt)))
                    {
                        flag = true;
                        break;
                    }
                    for(int m = 0; m < alphabet_len; m++)
                    {
                        password[4] = alphabet[m];
                        if(!strcmp(hash, crypt(password, salt)))
                        {
                            flag = true;
                            break;
                        }
                    }
                    if(flag)
                        break;
                }
                if(flag)
                    break;
            }
            if(flag)
                break;
        }
        if(flag)
            break;
    }

    if(flag)

If you define a function, you could get rid of flag. E.g.

bool find_password(string alphabet, int alphabet_len, char salt[]) {
    for(int i = 0; i < alphabet_len; i++)
    {
        password[0] = alphabet[i];
        password[1] = password[2] = password[3] = password[4] = '\0';

        if (!strcmp(hash, crypt(password, salt)))
        {
            return true;
        }

        for (int j = 0; j < alphabet_len; j++)
        {
            password[1] = alphabet[j];
            password[2] = password[3] = password[4] = '\0';

            if (!strcmp(hash, crypt(password, salt)))
            {
                return true;
            }

            for (int k = 0; k < alphabet_len; k++)
            {
                password[2] = alphabet[k];
                password[3] = password[4] = '\0';

                if (!strcmp(hash, crypt(password, salt)))
                {
                    return true;
                }

                for (int l = 0; l < alphabet_len; l++)
                {
                    password[3] = alphabet[l];
                    password[4] = '\0';

                    if (!strcmp(hash, crypt(password, salt)))
                    {
                        return true;
                    }

                    for (int m = 0; m < alphabet_len; m++)
                    {
                        password[4] = alphabet[m];

                        if (!strcmp(hash, crypt(password, salt)))
                        {
                            return true;
                        }
                    }
                }
            }
        }
    }

    return false;
}

Which you'd use like

    if (find_password(alphabet, strlen(alphabet), make_salt(argv[1]), password))

Recursive

Now, if you automate the increasing length, you could have

bool find_password(string alphabet, int alphabet_len, string salt, char password[])
{
    return find_password(alphabet, alphabet_len, salt, password, 0, 5);
}

bool find_password_recursive(string alphabet, int len, string salt, char password[], int i, int n) {
    if (i >= n)
    {
        return false;
    }

    for (int j = 0; j < len; j++)
    {
        password[i] = alphabet[j];

        if (!strcmp(hash, crypt(password, salt))
         || find_password(alphabet, len, salt, password, i + 1, n)
           )
        {
            return true;
        }
    }

    password[i] = '\0';

    return false;
}

Short variable names used to avoid scrolling.

We can clear password[i] exactly once here. In the loop, we keep changing it. We only have to clear once after finishing the loop. We don't have to clear later characters, as we already cleared those.

Static globals

C allows file scoped variables through the use of the static keyword. E.g.

static string alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

These would be defined outside of any function and be accessible to functions in the same file.

Now we don't have to keep passing alphabet and alphabet_len around everywhere.

A useful return

But do we really want our function to return a Boolean value and modify one of the inputs? A general rule is to only do one of those things. So we'd really prefer to use the function like

    char *password = find_password(make_salt(argv[1]), 5);
    if (password)
    {
        printf("Password: %s\n", password);

        free(password);
    }
    else
    {
        printf("Password not found\n");
    }

And with the proper helper function, we can.

char *find_password(char *salt, int maximum_length)
{
    char *password = calloc(maximum_length + 1, sizeof password[0]);
    if (!password)
    {
        /* Panic:  perhaps output or log an error message, but certainly */
        exit(-1);
    }

    char *result = find_password_recursive(salt, password, 0, maximum_length);
    if (!result)
    {
        free(password);
    }

    return result;
}

And

char * find_password_recursive(char * salt, char *password, int index, int maximum_length) {
    if (index >= maximum_length)
    {
        return NULL;
    }

    for (int i = 0; alphabet[i]; i++)
    {
        password[index] = alphabet[i];

        if (!strcmp(hash, crypt(password, salt))
         || find_password(salt, password, index + 1, maximum_length)
           )
        {
            return password;
        }
    }

    password[index] = '\0';

    return NULL;
}

A downside of this approach is that the allocation for the password is implicit but the free needs to be explicit. An alternative would be to allocate the password explicitly and pass it into the function. Then both would be explicit. C doesn't have good support for making both implicit while allowing the results to be used by the caller.

Both calloc and free are from stdlib.h, as is NULL.

This time, I used the native C names rather than the cs50.h names. Remember to include bool.h if you drop cs50.h and continue using true and false.

Now if we want to lengthen (or shorten) the potential passwords, we just have to call find_password with a larger maximum_length.