0

I am building a program where one will use the linux command line to issue a password's hash as the 2nd argument (./program ,to run the program, as the 1st), and the program will find the string with the according hash (aka password) for him. The key needs to be up to 4 characters long (a-z, A-Z), with a 2-digit salt (a-z, A-Z, 0-9). As a total beginner, I cannot come up with something other than using 6 loops to calculate all the possible combinations, which is bound to take the program hours to solve. This problem is part of an online course's problem set (Harvard's cs50), and I am using the course's library, so if you want to be able to use the functions and data types in the program below, so as not to be forced to come up with the corresponding functions/types of the libraries you use, you can create an account on edx and enter cs50.io. Here's the problem's description, if you need any more info: http://docs.cs50.net/problems/crack/crack.html

The source code:

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

int main (int argc, string argv [])
{
    if (argc != 2){
        printf ("Oops! Goodbye!\n");
        return 1;
    }

    char letters [] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',     'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u',
                        'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E',    'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P',
                    'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
    char leet [] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u',
                    'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P',
                    'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    char key [4];
    char salt [2];
    int i, j, k, l, m, n;
    for (i = 0; i < 52; i++){
        for (j = 0; j < 52; j++){
            for (k = 0; k < 52; k++){
                for (l = 0; l < 52; l++){
                    for (m=0; m < 62; m++){
                        for (n=0; n < 62; n++){
                        key [0] = letters [i];
                        key [1] = letters [j];
                        key [2] = letters [k];
                        key [3] = letters [l];
                        salt [0] = leet [m];
                        salt [1] = leet [n];
                        if (strcmp(crypt (key, salt), argv [1])==0){
                            printf ("%c%c%c%c", key [0], key [1], key [2], key [3]);
                            break;
                       }   
                   }   

                }

            }
        }
    }
}
printf ("\n");
return 0;
}

Other than the complexity, if you find anything else that can be improved or should be changed, please do tell me. All advice will be highly appreciated.

Edit: Thank you for the time you took into answering. I have taken all your suggestions into account and changed the code, but it still won't run for some reason (it won't print anything, as if the condition (strcmp function) is never satisfied). Could you elaborate as to what could be the problem? One more question. How can I use the debugger in a program that takes command line arguments? Whenever I run the program with the debugger it appears that it takes by default just the "./program" argument and exits. Here's how the new code looks like:

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

int main (int argc, string argv [])
{
    char salt [] = "50";
    if (argc != 2)
    {
        printf ("Oops! Goodbye!\n");
        return 1;
    }

    char letters [] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    char key [4];
    int i, j, k, l;
    for (i = 0; i < 52; i++){
        for (j = 0; j < 53; j++){
            for (k = 0; k < 53; k++){
                for (l = 0; l < 53; l++){
                        key [0] = letters [i];
                        key [1] = letters [j];
                        key [2] = letters [k];
                        key [3] = letters [l];
                        if (strcmp(crypt (key, salt), argv [1])==0)
                        {
                            printf ("%c%c%c%c", key [0], key [1], key [2], key [3]);    
                            break;
                        }

                }
            }
        }
    }
    printf ("\n");
    return 0;
}
Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
Leet
  • 83
  • 8
  • 1
    Keep in mind that the first two characters of the given hash are the salt, and that the output of the `crypt` function does not include the salt. – dbush Mar 23 '17 at 00:38
  • 2
    Also keep in mind that the parameters to `crypt` should be null terminated strings. – dbush Mar 23 '17 at 00:39
  • @dbush No, the output of `crypt()` **does** include the salt, which is `50` for every string included in the exercise. Only 4 nested loops are needed (about 7 million iterations for an exhaustive search). – r3mainer Mar 23 '17 at 00:42
  • 1
    From the spec: "Assume that each password is **no longer than** (gasp) four characters" – dbush Mar 23 '17 at 01:01
  • You have two good answers from dave and Ordoshsen below. Note that password searching is a slow process, so you will not get much faster unless you write your own super-fast crypt(). However, if you want to be elegant (but not improve speed), you can still do the same search in one for loop that is `for i` up to 7311616 (which is 52^4), and converts each `i` into your key values by doing divisions and mods 52. i.e. `key[0]=letters[i%52]; key[1]=letters[(i/52)%52]; key[2]=letters[(i/2704)%52]; key[3]=letters[(i/140608)%52];` – TheGreatContini Mar 23 '17 at 21:13
  • @ThegreatContini Thanks for the tip! One more thing, I do not know why, but in some cases, the code runs much faster using your suggested tip. Before it used to constantly take about 15 seconds, now some results are displayed in 1-2 after I hit enter. The worst case scenario seems to be the same, though. However, shouldn't the average case remain as it is? – Leet Mar 24 '17 at 13:20
  • Yes, on average the time will be roughly the same. If you get an answer very fast, it is just luck. – TheGreatContini Mar 25 '17 at 20:12

2 Answers2

2

Two things: firstly, as someone stated, you have to pass NULL terminated string to crypt. What you're passing is a pointer to the first character of your possible key and then you pray that there is nothing in the memory after it. What I mean is you should declare key as char [ 5 ] and setting char [ 4 ] to 0 (to value 0 not char '0' (which is by the way char '\0')). If you don't terminate it, crypt just reads and reads until it finds some other zero and thus gives you wrong hashes because the key is different.

Also, why is the outer most for loop counting until 52 and the others to 53? This is acutally safe, because you're just setting a char in the key to letters[52]which just happens to be the aformentioned '\0'character, basically terminating the key string prematurely. All loops should go until variable < 52, 53 just makes the program a little slower (you wouldn't probably even notice), anything bigger results again in undefined behaviour because you'd be accessing values out of bounds of the array.

Ordoshsen
  • 650
  • 3
  • 15
  • The program runs as it should now, thanks to your suggestions. Thank you very much, to both you and the other people, who were kind enough to help. As for the loop counting up to 53, the key needs to be up to 4 characters long. It could be 1, 2 or 3, so in order to cover those options, I wanted my program to include the '\0' character, in some slot among the 4 possible slots, to cover all the possible combinations. If the password were "abc", had I not dictated the last loop to reach up to 53, the {'a','b','c','\0'} string would never be found. Thanks again! – Leet Mar 24 '17 at 11:41
  • oh, ok then, I thought you knew it was supposed to be 4 chars long. I would still probably advise you to try to come up with some other way to do this, since this way you're testing one char long passwords 2809 each (143259 unnecessary crypts, if I'm not mistaken and another 140608 for two-char passwords). It may be not a whole lot, but it's important to think about these things. – Ordoshsen Mar 24 '17 at 15:24
1

From the problem statement:

Be sure to read up on crypt, taking particular note of its mention of "salt":

man crypt

Did you do that? Then you'd notice that the salt is given to you as the first two characters of the hash. Wait a second, look at those hashed passwords: did they really use the same salt for every password?? That's poor security. (Hint: you are doing a course called CS50 and the salt is 50 on each password).

What was the purpose of a salt when doing a hash? What does it prevent the attacker from doing? And the answer to those questions will give you how to improve performance. Good luck.

dave
  • 4,812
  • 4
  • 25
  • 38