0

My code takes like 1-2 minutes to execute, and the result is always Killed. Here is my code:

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

string crack(string hashed);
string deleteAll(string s, char target);

// Deals with input and stuff and feeds info into functions.
int main(int argc, string argv[])
{
    // Returns 1 because this is an error (because there is no hashed pw).
    if (argc != 2)
    {
        printf("Usage: ./crack hash\n");
        return 1;
    }
    else
    {
        // Makes crack do all the 'hard work' of guess/checking.
        string pw = crack(argv[1]);
        // Prints the pw.
        printf("%s\n", pw);
        return 0;
    }
}

// Does all the 'hard work'.
string crack(string hashed)
{
    // A string is a list of chars, so this is easier than doing characters[0] = ' '; ...
    string characters = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ",
           // A temporary variable that is useful for guessing.
           temp = malloc(5),
           // The salt for crypt() (salt will be defined in next two lines).
           salt = malloc(2),
           // The output.
           out = malloc(5);
    salt[0] = hashed[0];
    salt[1] = hashed[1];
    // Length will be used in the for loops in the next lines.
    int length = (int) strlen(characters);
    for (int a = 0; a < length; a++)
    {
        for (int b = 0; b < length; b++)
        {
            for (int c = 0; c < length; c++)
            {
                for (int d = 0; d < length; d++)
                {
                    for (int e = 0; e < length; e++)
                    {
                        // Sets temp to characters[a] characters[b]...characters[e].
                        temp[0] = characters[a];
                        temp[1] = characters[b];
                        temp[2] = characters[c];
                        temp[3] = characters[d];
                        temp[4] = characters[e];
                        // Deletes spaces in temp.
                        temp = deleteAll(temp, ' ');
                        // Checks if it is the right password.
                        if (crypt(temp, salt) == hashed)
                        {
                            out = temp;
                        }
                    }
                }
            }
        }
    }
    return out;
}

string deleteAll(string s, char target)
{
    // Gets a string length.
    int length = (int) strlen(s), count = 0;
    // Sets the length of the output to the length of the input string (which is faster than calculating).
    string out = malloc(length);
    // Scans the input string and checks for target.
    for (int i = 0; i < length; i++)
    {
        if (!(s[i] == target))
        {
            out[count] = s[i];
            count++;
        }
    }
    return out;
}

Is there something wrong with it?

--EDIT--

New code:

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

string crack(string hashed);
string deleteAll(string s, char target);

// Deals with input and stuff and feeds info into functions.
int main(int argc, string argv[])
{
    // Returns 1 because this is an error (because there is no hashed pw).
    if (argc != 2)
    {
        printf("Usage: ./crack hash\n");
        return 1;
    }
    else
    {
        // Makes crack do all the 'hard work' of guess/checking.
        string pw = crack(argv[1]);
        // Prints the pw.
        printf("%s\n", pw);
        return 0;
    }
}

// Does all the 'hard work'.
string crack(string hashed)
{
    // A string is a list of chars, so this is easier than doing characters[0] = '\0'; ...
    string characters = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ",
           // A temporary variable that is useful for guessing.
           temp = malloc(5),
           // The salt for crypt() (salt will be defined in next two lines).
           salt = malloc(3),
           // The output.
           out = malloc(5);
    salt[0] = hashed[0];
    salt[1] = hashed[1];
    salt[2] = '\0';
    // Length will be used in the for loops in the next lines.
    int length = (int) strlen(characters),
        c1 = 0,    // c1-4 are counters for the while loops.
        c2 = 0,
        c3 = 0,
        c4 = 0;
    // These things check if each loop is done.
    bool done1 = false,
         done2 = false,
         done3 = false,
         done4 = false;
    while (!done1)
    {
        while (!done2)
        {
            while (!done3)
            {
                while (!done4)
                {
                    // Sets temp to the current pw (the loops guess in the following order: a, b, c, d, e..., Z, aa, ab, ac...zz, Aa, ...).
                    temp[0] = characters[c1];
                    temp[1] = characters[c2];
                    temp[2] = characters[c3];
                    temp[3] = characters[c4];
                    temp[4] = '\0';
                    temp = deleteAll(temp, ' ');
                    // Checks if the pw is the correct one.
                    if (strcmp(crypt(temp, salt), hashed) == 0)
                    {
                        out = temp;    // Sets out to temp, and exits the loops
                        done1 = true;
                        done2 = true;
                        done3 = true;
                        done4 = true;
                    }
                    if ((c1 == length - 1) &  // Sees if it should stop.
                        (c2 == length - 1) &
                        (c3 == length - 1) &
                        (c4 == length - 1))
                    {
                        out = "Unknown hash";    // Sets out to temp, and exits the loops
                        done1 = true;
                        done2 = true;
                        done3 = true;
                        done4 = true;
                    }
                    c4++;
                }
                c3++;
            }
            c2++;
        }
        c1++;
    }
    return out;
}

string deleteAll(string s, char target)
{
    // Gets a string length.
    int length = (int) strlen(s), count = 0;
    // Sets the length of the output to the length of the input string (which is faster than calculating).
    string out = malloc(length);
    // Scans the input string and checks for target.
    for (int i = 0; i < length; i++)
    {
        if (!(s[i] == target))
        {
            out[count] = s[i];
            count++;
        }
    }
    return out;
}
1

Keep in mind that a "string" in C is simply a character array that is null terminated.

As such, your salt variable is not a string, nor is your temp variable in all cases.

As a consequence, when you call crypt, which is expecting 2 strings, it will look at the location of each string and keep reading until it finds the null char that signifies the end. If you haven't explicitly set it (by declaring the array long enough to include it and setting it), then crypt can end up trying to access memory that it has no right to.

When that happens, you see that crash (the Deadly Signal, ie, a segfault).

Be sure all your strings are null-terminated and of the correct length.

3
  • I fixed that and now there's an error. Mar 29 '19 at 2:29
  • UndefinedBehaviorSanitizer:DEADLYSIGNAL ==752==ERROR: UndefinedBehaviorSanitizer: SEGV on unknown address 0x000000439000 (pc 0x000000428b5b bp 0x7ffdc38f56b0 sp 0x7ffdc38f5380 T752) ==752==The signal is caused by a READ memory access. #0 0x428b5a in crack /root/sandbox/crack.c:70:35 #1 0x42804e in main /root/sandbox/crack.c:21:21 #2 0x7ff3677e0b96 in __libc_start_main /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:310 #3 0x402b39 in _start (/root/sandbox/crack+0x402b39) UndefinedBehaviorSanitizer can not provide additional info. ==752==ABORTING Mar 29 '19 at 2:37
  • The buggy code is still temp[4] = characters[c5]; Mar 29 '19 at 2:38
1

This program takes a notoriously long time to run. It's also an exercise in making code more efficient. Also, at this point, you should start being able to answer questions on your own, like this one:

Is there something wrong with [my code]?

Good question. Did you run tests and get valid and correct answers? Did you encode simple passwords on your own and then run the hashed result through your code to test whether you got the desired result?

Did you test with a 1 char password? Did you then test with a 2 char? a 3 char? a 4 char?

Did the runs get progressively slower or were they all roughly the same time?

Did you test with passwords of the same length that start with a, and then with n, or z? Was there a performance difference when you did?

Or did you just run check50? (Does pset2 allow for check50? I forgot)

When you say "My code takes like 1-2 minutes to execute, and the result is always Killed." Does that mean that the environment is timing out your program and ending it?

If so, then there are two possibilities. Either it's just taking a very long time to run, or it's actually caught in an infinite loop. What have you done to determine which is the case? Maybe inserted some printf statements to see what's happening? Or a conditional if statement that prints every n times something happens (less time spent printing, more time processing).

There are a lot of things you can do here to see what's happening. Have you thought much about what your code is doing? Is it checking all passwords starting with "a" no matter the length, or maybe checking all the short passwords first? Are there other ways to do things faster?

To be honest, I only took the briefest look at the code. I can't say that there are specific errors or bugs in the code, but I can say that there are far more efficient ways to design the program. Since two of the major hidden purposes of this exercise are to learn to test and to think about more efficient code designs, I probably gave you too much as it is! I leave it to you to think about what I've written and to really analyze your code with this in mind!

But I will give you a hint. Finding short passwords should take milliseconds. 4 and 5 chars may time out in the IDE, even if they are running correctly. An inefficient design will almost always time out, and rarely complete, if ever, depending on how inefficient it is.

[EDIT: some words on efficiency.] When working this, or any, coding project, you need to know what is more important. Is it more important to run really fast, to conserve memory, to conserve disk space, or something else? Often, these can be at odds with each other. For example, a program written with a minimal number of lines of code can be very inefficient to execute, while a notably longer program can actually execute faster. Usually, there's are two goldilocks zones to look for. One is to write more code, but make sure its as efficient as possible. Another is to write the code to balance two important criteria such as execution speed vs. memory usage.

You need to look at the purpose of the program and its criteria to decide what the criteria and to put them in order and decide how important they are, or if they can even be ignored! This has to happen BEFORE considering how to design the program!

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

5
  • Every time I tested with a password, the program always said Killed, when i put printf()'s in the program, even though the password always showed up, it always said Killed. I'm sure that using while will help. Thank's for the advice. Mar 26 '19 at 2:12
  • If the code is finding the password, it should immediately end. If it's not, there's a serious problem - it's either continuing to check all the passwords or it's in an infinite loop. If the password is not being detected as a correct password, then there's a logic problem. happy coding! ;-)
    – Cliff B
    Mar 26 '19 at 2:27
  • Now that I'm using while loops, there is an error (not in the compilation, in the running of the program). Mar 26 '19 at 3:20
  • The error:UndefinedBehaviorSanitizer:DEADLYSIGNAL ==823==ERROR: UndefinedBehaviorSanitizer: SEGV on unknown address 0x000000439000 (pc 0x000000428ac9 bp 0x7ffda4713a40 sp 0x7ffda4713750 T823) ==823==The signal is caused by a READ memory access. #0 0x428ac8 in crack /root/sandbox/crack.c:68:35 #1 0x42804e in main /root/sandbox/crack.c:21:21 #2 0x7f244de1ab96 in __libc_start_main /build/glibc-OTsEL5/glibc-2.27/csu/../csu/libc-start.c:310 #3 0x402b39 in _start (/root/sandbox/crack+0x402b39) UndefinedBehaviorSanitizer can not provide additional info. ==823==ABORTING Mar 26 '19 at 3:23
  • And the buggy code: temp[4] = /*It seems to start here*/ characters[c5]; Mar 26 '19 at 3:26

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .