4 characters crack finishes fast but adding 5th loop slows entire program

Question

I'm writing a program for a class that cracks a 5 character (aA-zZ) password by collecting a hashed password at the command prompt and matching the hash with hashes generated with crypt() function. My problem is adding the 5th loop to crack a 5 character password slows the program to a halt, even for 1-4 character passwords, and I have to cancel. Removing 5th loop cracks 1-4 character passwords in under a minute.

We have only covered the basics in class which is demonstrated in my code. So the solution must match this coding level.

#include <cs50.h>
#include <stdio.h>
#include <crypt.h>
#include <string.h>

void printpass (string fst, string hsh1, string hsh);
/* prompt user for 1 cmd line argument */
int main(int argc, string argv[])

{    
    /* only allow 1 cmd line argument and return cmd line error
    and exit if false */    
    if (argc != 2)
    {
        printf("Invalid request!\n");
            return 1;
    }
    string hash = argv[1];
    char slt1 = hash[0];
    char slt2 = hash[1];
    char salt[3] = {slt1, slt2, '\0'};
    char alpha[52] = "QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnm";//upper & lowercase passwords only

    for (int d = 0; d < 52; d++) //search for one character pw
    {
        char s1 = alpha[d];
        char first1[2] = {s1, '\0'};
        string hash0 = crypt(first1, salt);
        printpass (first1, hash0, hash);

        if (strcmp(hash0, hash) != 0) 
        for (int f = 0; f < 52; f++) //search for two character pw
        {
            char s2 = alpha[f];
            char first2[3] = {s1, s2, '\0'};
            string hash1 = crypt(first2, salt);
            printpass (first2, hash1, hash);

            if (strcmp(hash1, hash) != 0 || strcmp(hash0, hash) != 0)
            for (int h = 0; h < 52; h++) //search for two character pw
                {
                    char s3 = alpha[h];
                    char first3[4] = {s1, s2, s3, '\0'};
                    string hash2 = crypt(first3, salt);
                    printpass (first3, hash2, hash);

                    if (strcmp(hash2, hash) != 0 || strcmp(hash1, hash) != 0 || strcmp(hash0, hash) != 0)
                    for (int j = 0; j < 52; j++) //search for two character pw
                        {
                            char s4 = alpha[j];
                            char first4[5] = {s1, s2, s3, s4, '\0'};
                            string hash3 = crypt(first4, salt);
                            printpass (first4, hash3, hash);

                            if (strcmp(hash3, hash) != 0 || strcmp(hash2, hash) != 0 || strcmp(hash1, hash) != 0 || strcmp(hash0, hash) != 0)
                            for (int l = 0; l < 52; l++) //search for two character pw
                                {
                                    char s5 = alpha[l];
                                    char first5[6] = {s1, s2, s3, s4, s5, '\0'};
                                    string hash4 = crypt(first5, salt);
                                    printpass (first5, hash4, hash);

                                }
                            }
                }
        }
    }
}

void printpass (string fst, string hsh1, string hsh) //compare hashes and print if true
{
    if (strcmp(hsh1, hsh) == 0)
    {
        printf("%s", fst);
    }
}

1-4 character passwords should complete in under a minute with the 5th loop in the code.

Answer 1

4 characters long password will take up to 7311616 (or 52^4) iterations to crack, and 5 characters long password will take up to 380204032 (or 52^5) iterations.

Answer 2

The code run 5 nested loops (d, f, j, h, l). Trying Q, QQ, QQQ, QQQQ, QQQQQ, QQQQW, ..., trying all combinations (with various length) of passwords starting with Q, before attempting to evaluate any password starting with any other letter.

While there are about 7.2M 4 letter combinations (52^4), the code will evaluate many 5 letter combinations (there are about 380M of them) before trying the complete smaller subset of 4 letter combination. Even for 1 letter password, (e.g., A), the code will evaluate almost half of the 5 letter combinations, before trying the simple 'A'.

As an alternative, consider reordering the loops:

1. single letter passwords
2. 2 letter passwords
3. 3 letter passwords
4. 4 letter passwords
5. 5 letter passwords

Answer 3

From comments, looks like the required order is shorter passwords will be tested before longer password. This will result in the following sequence: (Q, W, E, ... QQ, QW, QE, ..., WQ, WW, WE, ..., QQQ, QQE, ...), instead of the current dictionary order (Q, QQ, QQQ, QQQQ, QQQQQ, QQQQW, QQQQE, ...).

With MINIMAL changes to the current code, this can be achieved with the following. See below for additional proposal that will require more than minimal changes.

   bool done = false ;
   for (int pwlen=1 ; pwlen<=5 && !done ; pwlen++ ) {
       for (int d = 0; d < 52 && done; d++) {
           char s1 = alpha[d];

           if ( pwlen == 1 ) {
               char first1[2] = {s1, '\0'};
               string hash0 = crypt(first1, salt);
               printpass (first1, hash0, hash);
               if (strcmp(hash0, hash) == 0 ) { done = true ; break } ;
           } else {
               for (int f = 0; f < 52 && done; f++) {
               ... same changes ...
               if ( pwlen == 2 ) {
               } else {
                  ... level 3 here.
               } ;
           } ;
       } ;
   } ;

Also consider the following changes:

1. Moving the whole logic from 'main' into a different function that will be called by main. It will make it easier to modify the code (e.g., use 'return' to break from internal loops, etc). The function should RETURN the matched key.
2. Changing printpass to return true/false indication if the password match. It will eliminate redundant strcmp.

Answer 4

as noted in the other answers, the combinatorial complexity of this sort of problem makes it very hard. hopefully you can see why password length recommendations are generally "something more than 8 letters"

that said, people don't pick characters (uniformly) randomly. hence why password cracking tools such as John the Ripper use dictionary attacks and statistical observations in an attempt to speed up the process. the program can also use multiple CPU and GPU cores where possible so churn through things faster

as a comment on the style of your code, all your nested loops look very similar. I'd recommend turning this into a recursive function, it should be pretty easy and should cut down on the code significantly. most of the time will be spent running crypt(3) so you shouldn't need to worry much about performance of your code but it might be worth profiling just to make sure