Passwords Et Cetera, Problem Set 2: Crypto. Walkthrough

I'm wondering how can I do this pset without doing the fist thing that comes to mind when reading this pset. From Itsa Mario to this there is a really big jump. Please talk me about crypt and file I/O in a Less Comfy way than the man page. And write the pseudocode explaining it like in Zamyla's walkthroughs. It's weird that there's only one useful question about this pset.

• Let's agree that hacker editions are literally challenging. Part of the challenge is to be able to figure things out on your own by reading the man pages as well as using the other resources. I don't think you should expect someone to write down the pseudocode for you specially that this is an optional set. If you're not up to the challenge, maybe you should skip it!
– kzidane
Dec 11 '14 at 19:06
• Ok, thanks, then maybe I'll come back in the future to respond this question. I'll move on now. Dec 11 '14 at 19:18
• Good luck with that! ;)
– kzidane
Dec 11 '14 at 19:28

Less Comfy Man Page

NAME
crypt - password and data encryption

SYNOPSIS
#define _XOPEN_SOURCE
#include <unistd.h>
string crypt (key, salt);

DESCRIPTION
key is a user's typed password.

salt is a two-character string chosen from the set [a-zA-Z0-9./].  This string is used to perturb the algorithm in  one  of  4096 different ways ( (a-z && A-Z) 26 * 2 + (0-9) 10 + (./) 2 = 64; 64 ^ 2 = 4096).
The first two characters of the hash (the actual encrypted "password") is the salt. The salt is used to influence the encryption process. If you call the function "string crypt (key, salt)" twice with the same key but different salts you get different encryptions (see the EXAMPLES below).
Warning: Exhaustive searches of this key are possible. Hence, password selection should, at minimum, avoid common words and names.

GLIBC NOTES
The glibc2 version of this function supports additional encryption algorithms.
If salt is a character string starting with the characters "$id$" followed by a string terminated by "$":$id$salt$encrypted

then instead of using the DES machine, id identifies the encryption method used and this then determines how the  rest   of the password string is interpreted.  The following values of id are supported:

ID  | Method
─────────────────────────────────────────────────────────
1   | MD5
2a  | Blowfish (not in mainline glibc; added in some
| Linux distributions)
5   | SHA-256 (since glibc 2.7)
6   | SHA-512 (since glibc 2.7)

So $5$salt$encrypted is an SHA-256 encoded password and$6$salt$encrypted is an SHA-512 encoded one.

"salt"  stands for the up to 16 characters following "$id$" in the salt.  The encrypted part of the password string is    the actual computed password.  The size of this string is fixed:

MD5     | 22 characters
SHA-256 | 43 characters
SHA-512 | 86 characters

EXAMPLES
PROGRAM

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

int main (int argc, string argv[])
{
//If the program is executed without any command-line arguments or with more than one command-line argument, it should complain and exit immediately, with main returning any non-zero int. It should also check if the salt is 2 character long. There is no restriction for the length of the key.
if ( argc != 3 && strlen (argv[2]) != 2 ) {
printf ("Usage: ./crypt key 2-character-salt\n");
return 1;
}

string key = argv[1], salt = argv[2];

printf ("%s\n", crypt (key, salt));

return 0;
}

INPUT                OUTPUT
./crypt crimson 50          50yoN9fp966dU
./crypt crimson 5a          5a9vZiZYVcRk.
./crypt crimson '$1$salt$'$1$salt$d5Efc3PJwA9f2Zf/EDYUr1
./crypt crimson '$5$salt$'$5$salt$u56CFXYl6ngeX7vwZWAR.rV7Hj.yCV6QKEQ77wPyTH/
./crypt crimson '$6$salt$'$6$salt$irYq5wMLae2zBqwlVIG5K2DWhVll6KHgb..HlsjGVSMmlEv7pUqh4njYIvn4/ddqkC3fRpr04vtVCg0BdGpPk1


What we have to do is to call the function crypt for all possible combinations of ASCII characters as arguments and compare the result with the hash that we are given.

We begin the program declaring an array with the symbols allowed in the alphabet just below the header files because we want to use them in all functions and not only in the main function, we also declare the size of the alphabet, and the maximum length of the password that we are given.

We begin the function making sure that if the program is executed without any command-line arguments or with more than one command-line argument, it should complain and exit immediately, with main returning any non-zero int.

Then we extract the salt from the 2 first letters of the hash. You may want to take a look at this function.

We have to implement various functions and all of them will be of type bool so that all of them finish when the password is found.

We have to make a function to generate all possible words with a series of letters. So how can we do that? We are going to use this snippet It's a recursive function. Supose an alphabet {"abc"} the first time that bruteSequential is called it passes an index 0 and a maxDepth 1, then str[0] gets the first letter in the alphabet a as the if is true it prints the only letter in the array the rest of the array is filled with null characters thanks to the calloc function and doesn't display anything. The second time bruteImpl is passed an index 0 and maxDepth 1, str[0] takes the value a but this time index isn't equal to maxDepth so the function calls it recursively until index equals maxDepth wich in this case happens only one time printing aa and ab, then str[0] gets the value b, and equally prints ba, bb and so on..

We'll call the bruteSequential function from the main function for length one to our given maximum length.

Instead of printing the word the bruteImpl function should call another bool function that checks if the encrypted key is equal to the hash. We have to pass the key and the salt to all the functions as arguments so that the final function gets them and it can call the function crypt. Then you would like to use a function like strcmp. If you know how to use pointers use them when calling the several functions so you are not doing a lot of copies of the variables.

Finally when the password is found the deepest function should print it with a \n at the end and all the functions should return.

I will include something about file I/O for improving the program with a list of the 10,000 Most Common Passwords.

Here are some interesting facts from xato.net: