CS50 Week 1 Continued: Walkthroughs

Caesar

The Caesar cipher is just n steps away from the letter you are given. If the cipher key is 1, and I give you “GH,” then you would move one step to the right of the alphabet for each letter giving you the decoded message “HI.” The cipher key is the same for every letter given.

Steps:

1. get the key
2. get the plain text
3. encipher
4. print ciphered text

A few libraries included:

• stdlib.h gives me the atoi function (changes a string to integer value)
• string.h has the strlen function (returns the length of a string without the null terminator \0)
• ctype has functions isupper and islower functions.

The user has to provide a number that will be our cipher key, and instead of getting this within main, we’re going to use command line arguments. We have to guard against any values that are not positive integers. On line 18 we check if the count for command line arguments is not 2. This way the program will just output an error message if the user just tries this:

~/workspace/pset1/ $ ./caesar

Remember that ./caesar counts as an argument, so argv[0] is always the program name. We are looking for ./caesar integer-value, which has an argc (count) equal to 2. Notice on line 18 the OR logical operator, we also won’t accept 0 or negative numbers.

We use the else statement as our condition if everything is acceptable to continue running the program. We declare our variable to store the cipher on line 16 and assign it the value of argv[1] on line 25 within the else block.

Notice the atoi function, remember command line arguments are all “strings.” We have to convert it to an integer for running calculations with other numbers later in program.

There are 3 #define statements starting on line 7:

• UPPER_ALPHA_INDEX 65 – ASCII table number at char ‘A’
• LOWER_ALPHA_INDEX 97 – ASCII table number at char ‘a’
• ALPHABET_MAX 26 – Number of letters in English alphabet

On line 29 we create a value to hold the cipher_text the user will give us. Running a do while loop ensures we get a string, using strlen() provided by the string.h library (line 35).

Looking at the end result of this program, we want to take the user’s string of text, do some encryption and each character and print it back in the terminal. First we can just create a loop that prints each char to the terminal. Line 41 starts a loop that will run while i is less than the length of the string the user gave us. Then on line 42 we start with this:

printf(“%c“,………

We are printing out a char, and since we are not adding the ‘\n’ line break character this will print out our user’s text like a typewriter. Since we’re inside the loop we can run a function on each character as it goes through the loop.

These donuts are getting an add_sprinkles() function added to each one, similar to what we’re doing in our loop.

encipher() is a function I’ve created to handle the encryption. It takes a char and an int.

Now we have this on line 42:

printf("%c", encipher(cipher_text[i], cipher_key));

Personally, it made more sense to create this line before the encipher() implementation existed. At the end of the day this is what I want, some black box that just does work on what it’s given. Then I imagine what arguments are needed to do the work, in this case it needs the letter I want to change and the cipher_key that transforms it n places in the alphabet.

I like to test my program out on the terminal and see something print out. You might want to start with this:

printf("%c", encipher(cipher_text[i], cipher_key));

Then within the function implementation do something like this just so it prints to the terminal:

char encipher(char index, int cipher_key)
{
  return index + cipher_key;
}

Nothing special here, because in the c language an integer can be added to a char by using the char’s integer value, the result is printed based on the printf formatter. In our context we want a char, so if my text was the letter ‘A’ and my key was the number 1, this function would just add one to ‘A’, which in the ASCII table is 65. 65 plus 1 gives us 66 which is returned back to main() and we print out the char of 66 which in ASCII is ‘B’.

going over the actual implementation of encipher:

There are 3 possible cases that can happen at this point:

• User gives an upper case letter
• User gives a lower case letter
• User gives a special character like ‘!?\}{‘ etc.

I used an if else statement starting on line 62

char encipher(char index, int cipher_key)
{
 if (isupper(index))
   return ((index - UPPER_ALPHA_INDEX) + cipher_key) % ALPHABET_MAX + UPPER_ALPHA_INDEX;
 else if (islower(index) )
   return ((index - LOWER_ALPHA_INDEX) + cipher_key) % ALPHABET_MAX + LOWER_ALPHA_INDEX;
 else
 return index;
}

The first block handles if the char is upper case using the isupper function provided by string.h

then we have an else if block which handles if the char is lower case.

Finally we just pass anything that isn’t upper or lower case back to the caller, unchanged, in the else block.

So what exactly are we doing to the char?

return ((index - UPPER_ALPHA_INDEX) + cipher_key) % ALPHABET_MAX + UPPER_ALPHA_INDEX;

Not my most readable piece of code. This is also hard to debug as I recently discovered because I misplaced a parenthesis. In the future I will break stuff like this down in several variables so I can see their values change when using breakpoints. Since there is no variable debug50 can’t show us anything until it’s passed back and assigned to something.

Let’s imagine my cipher key is int 2 and I give the program the  “AZ” Remember this function runs within a loop that acts upon each character, so let’s start with ‘A.’ It hits the if block for isupper and since is true returns the block of code within.

Starting from the inner most parenthesis in the above line of code:

(index - UPPER_ALPHA_INDEX)
now let's replace it with concrete values...

('A' - 65)
Since we are passing a char C treats 'A' as it's ASCII
integer value...

(65 - 65)

The difference is 7, leaving us with:

(0 + cipher_key) % ALPHABET_MAX + UPPER_ALPHA_INDEX;
and our cipher key I gave it was 2...0+2 is 2...

2 % ALPHABET_MAX + UPPER_ALPHA_INDEX;

Modulo is always tricky for me at first. But it can be really simple if you consider it this way:

Imagine we have a bucket that holds 10 cups of water.
Modulo will dump out the water each time it gets full.
If we give module 22 cups, or 22 % 10, modulo will say:
max is 10
filling up 10 out of 10, cup is full so dump it out
filling up 10 out of 10, cup is full so dump it out
filling up to 2...not a full cup so return
giving us 2.

2 % 26
fill up to 2...not the entire alphabet so return
giving us 2

Finally we want to use this value as the number of steps from the beginning of the alphabet to move forward, giving us our enciphered character.

2 % ALPHABET_MAX + UPPER_ALPHA_INDEX;
2 + UPPER_ALPHA_INDEX;
remember in the ASCII table the alphabet
happens in upper case and lower case.
So the upper case A starts at ASCII value 65

2 + 65
so we move 2 letters up from A
1 up from A is B
2 up from A is C

So what about ‘Z’?

Let’s do this but a little more quickly:

((index - UPPER_ALPHA_INDEX) + cipher_key) % ALPHABET_MAX + UPPER_ALPHA_INDEX;

'Z' which is 90
UPPER_ALPHA_INDEX is the ASCII table number where
uppercase letters start at letter 'A' which is 65

(( 90 - 65 ) + cipher_key)
we'll give the same cipher key, 2...

( 25 + 2 ) = 27

Now we put this against the modulo operator...

27 % ALPHABET_MAX + UPPER_ALPHA_INDEX;
max is 26
filling up 26 out of 26, reached max so dump
filling up 1 out of 26...not full so return

Finally add our result to UPPER_ALPHA_INDEX
1 + 65 = 66
or we could say

1 + 'A' = 'B'

I think it’s amazing how much easier this is for a human brain to figure out. I would just say:

“If I give you a letter, give me the letter 2 characters ahead of it, if you need to just wrap back around to the beginning of the alphabet. So ‘Y’ would be ‘A,’ and as we just figured out ‘Z’ would be the letter ‘B.’

Obviously computers need us to be much more verbose.

Hope that made sense!

Vigenere

While Caesar’s cipher works when you want to make a decoder ring, it’s easy to crack the code once you know the single cipher key. Vigenere uses the same technique of moving the letter n steps, but the cipher key is multiple numbers. In this scenario if I gave you a ciphered message “GY,” and the key 12, ‘G’ would be moved 1 step ahead to ‘H’ and ‘Y’ would be moved 2 steps, which would wrap back around to ‘A,’ giving us the decoded message “HA.”

encoded message: "GY"

cipher key: 12

GY
12

G + 1 = H

Y + 2 = A 
//remember we are wrapping back around so
// we are actually saying:
Y % 26 + 2 = A

This actually becomes more challenging because we’re not actually going to use a number up front. Our cipher is going to be a word, which we’ll convert to numbers based on the ASCII table.

So this is way harder to break because if the message/cipher key is:

message: "This is my secret message"

cipher key: nori

This is my secret message
nori no ri norino rinorin

Each letter is not going to be shifted based on the ASCII value like in Caesar. It doesn’t matter if the cipher key text is upper case or lower case. Somehow we have to take the ASCII value of ‘a’ and ‘A’ and resolve it to equal the number 0. Another example, ‘B’ and ‘b’ would resolve to the cipher key 1 and so on.

Steps:

• Get the key
• Get the plain text
• encipher
• print ciphered text

So the steps are really the same as Caesar, however our implementation of the encipher function is going to be different.

A sub step would also be to get the cipher key. Line 106 shows an implementation of convert_key(), which returns a number representing a position in the alphabet starting from 0 instead of the ASCII mapping for upper (65) or lower (97). So if i pass it the letter ‘B’, it’s going to do the work and say ok it’s an upper case so i’m going to return ‘B’ – 65, or 66 – 65 which is 1. This works in either upper or lower giving us the cipher key we want which is 1 if we’re mapping the alphabet using a zero based index.

Also note the loop on line 53 declares both an i variable of type int and a j variable. This is because we need to loop over our cipher text.

This was really hard to understand for me at first because the modulo was mysterious. But now using the bucket of water analogy it’s not as bad. Let’s try to work it out in some pseudo code. Starting on line 57:

converted_key = convert_key( cipher_key[j % key_len]);
j++;

Let's say the cipher key is nori
our message is "Hello World"
It's length never changes, so on line 51
we store the result (4) in the variable key_len


so first time around j is equal to 0

converted_key = convert_key( cipher_key[0 % 4]);

what does the modulo operator do if
explain it like a cup and bucket?

max cups in the bucket is 4
pouring 0 cups in the bucket...
bucket is not full so return 0

afterwards we see j is incremented using j++
and it goes on and on.

Now let's say we are at the 6th iteration of the loop...

converted_key = convert_key( cipher_key[6 % 4]);

max cups in the bucket is 4
pouring 4 cups in the bucket...
dumping the bucket...
pouring 2 cups in the bucket...
bucket is not full so return 2

Modulo allows us to keep going around and around the total length of our cipher key within the loop. This really messed with my head for a while and I highly recommend doing some work in a C repl to work it out for yourself.

On line 60, If the current character in our user’s message is not upper or lower we set the cipher key to 0, this way if they pass ‘!’ it’s going to run through our system unchanged.

Now that we have found a way to use a different cipher key on each letter, we can do our encryption just like caesar. This time I assigned a value to the character one step at a time, as you can see in line 88 and 96 depending on lower or uppercase. By doing it this way rather than returning a big mess of nested parenthesis I was able to use debug50 when I had bugs in my code.

Crack

Note: The walkthrough video incorrectly states that passwords are no longer than four (4) characters. Instead, per the specification, make sure to handle passwords that are up to five (5) characters.

I can’t stress enough what a pain this was to complete.  It’s been well over a week since I started working on this post. Don’t get discouraged if this problem is confusing, frustrating and makes you want to throw your computer out the window. If you are not making progress after 15-20 minutes, do yourself a favor and get away from the problem for 5-10 minutes and then try again for another round. If you are glued in front of the screen for hours on end you are wasting your time.

Within the pset2 docs, it is explained we have access to a function called crypt(). It is based on DES, which stands for Data Encryption Standard. Created in the 70’s by IBM and in collaboration with the NSA. We pass two arguments to crypt(), the key (our password in plain text), and the salt. Salt is an additional piece of data, which the crypt function works with to encrypt our password. When we use the crypt() function we are hashing our password. This means the password is being sent through a one-way function, that is practically impossible to reverse. The benefit is you can store a hashed password in your database and if someone were to steal your data somehow, they wouldn’t have the plain text passwords. The only way to use that hash would be to re-enter your plaintext password, run it through the crypt() function and see if the hashed passwords match. Let’s look at some pseudo code to see this in action:

Please sign up to my website for the first time!
username: John
password: **** // (I type the password nori)

// now the website runs a crypt function.
// It won't save nori, it will only save
// the hash nori produces after being run
// through the crypt() function.
// Remember the hash created is always
// the same so long as you provide the
// identical plain text password
----------------
my database
----------------
Username | PW
----------------
John     | 20wj610bb8AIc

// So now i'm going to log into the website
// with my username and password

username: John
password: **** // (I type the password nori)

// Look at my database above.
// I am not storing nori so how does
// the website know I typed the correct password?

...program running...finding username in database...
username John found...
username hash is 20wj610bb8AIc
// Remember the salt is going to be
// the first 2 characters of the hash
salt is 20...
checking inputted password...
password given is nori...
running nori through crypt...
crypt(nori, 20)...checking for a match
crypt returned 20wj610bb8AIc...
checking against saved hash in database...
20wj610bb8AIc == 20wj610bb8AIc
Match is true!

You are logged in!

So let’s review how our program should behave:

• User inputs a command line argument, the hashed password
• Try every possible combination of uppercase/lowercase letters (max length 5 characters)
• If the hash produced matches the hash given on the command line, print the plain text password.

First let’s make sure the user input has been given when the program starts, otherwise return an error message. If they’ve given us the correct input, let’s store it in a variable that is named with a clear name:

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

Since we know that the salt is going to be the first two characters in the user_input (the hashed password), let’s create a new string that is a substring of user_input.

char salt[3];
 
 for(int i = 0; i < 2; i++)
   salt[i] = user_input[i];
 
 salt[2] = '
char salt[3];
for(int i = 0; i < 2; i++)
salt[i] = user_input[i];
salt[2] = '\0';
';

We create a new array that holds 3 elements. Why 3 if we only take the first 2 chars from user_input? We need to loop through adding each char, but finally outside of the loop we add a special character, ‘\0’ at the very end.

// pseudo code but this is what our loop is
// essentially doing...
char *user_input = "50jkre829.p";
char salt[3];
salt[0] = '5';
salt[1] = '0';
salt[2] = '
// pseudo code but this is what our loop is
// essentially doing...
char *user_input = "50jkre829.p";
char salt[3];
salt[0] = '5';
salt[1] = '0';
salt[2] = '\0';
';

C uses the null terminator ‘\0‘ to denote the end of a string. So when we give a printf statement the %s formatter, along with, let’s say user_input, we’re really saying “here is the address of the first element, and it’s a string so just keep reading each element until you reach \0.”

Because we know the only possible characters used will be uppercase or lowercase letters of the alphabet, let’s just create a concrete representation of this as an array.

char alpha[] = 
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

We should store the length of this array somewhere as well, since we’ll be using a for loop to go through each letter.

int alpha_len = (sizeof alpha / sizeof alpha[0]) - 1 ;

How did we get the length? We check the total number of bytes divided by the bytes within a single element in the array. This gives us the length in terms of elements. This will return the integer 52. But there is one gotcha since we’re using this value in a for loop later in the program. Remember we start our for loop with ( int i = 0; condition; code to run if true). If we are checking i against the alpha_len:

( int i = 0; i < alpha_len; i++)

when i is 0 it will be the start of our array. Length is originally given to us starting from 1 which means to get the length (in zero index based terms) we need to subtract 1 from length. Sound confusing? It is totally confusing, which is why there is a whole wiki page dedicated to this common mistake.

To make this easier take an array of items like this and hand count it:

int myarray = {1,2,3,4};

The length is obviously 4 if you count it by hand. But if you start with an index of 0, then you have this:

myarray[0]
myarray[1]
myarray[2]
myarray[3]

So when you put this in a for loop you have to make sure your condition doesn’t allow you to go past 3. So the condition might be i < 3 so when it hits 3, which is equal to 3, it stops. If you do i < 4 you’ll end at myarray[4] which is not gonna work out!

The sizeof unary operator returns the size of the given data in signed chars, or in our case, a single char is = 1 byte.

Try this out in a repl to see what I mean:

#include "stdio.h"
int main(void) {
 
 char char_array[2] = "hi"; // '
#include "stdio.h"
int main(void) {
char char_array[2] = "hi"; // '\0' automatically added here
printf("size of the array char_array is %d\n", sizeof char_array);
printf("size of a single element in char_array is %d\n", sizeof char_array[0]);
printf("\n");
// now try with data type int
int integer_array[2] = {1,2}; //
printf("size of the array integer_array is %d\n", sizeof integer_array);
printf("size of a single element in integer_array is %d\n", sizeof integer_array[0]);
}
' automatically added here
 
 printf("size of the array char_array is %d\n", sizeof char_array);
 
 printf("size of a single element in char_array is %d\n", sizeof char_array[0]);
 
 printf("\n");
 // now try with data type int

int integer_array[2] = {1,2}; //
 
 printf("size of the array integer_array is %d\n", sizeof integer_array);
 
 printf("size of a single element in integer_array is %d\n", sizeof integer_array[0]);

}

So we have everything we need to crack some passwords! The user gave us a hashed password, we’ve extracted the salt, and we have an array of possible characters. Since we know the max length is 5 let’s create some loops that go only as deep as 5 characters. To clarify what we’re trying to do let’s consider this gif image (click the image if you are not seeing the animation):

Instead of numbers, let’s imaging letters of the alphabet. We start with the first position moving quickly through out letters ‘a’ through ‘z’ then ‘A’ through ‘Z.’ Once it has gone all the way through it starts again, but the second to last now is activated giving us it’s first character ‘a.’ So we continue this process, testing each possible combination from just a single character ‘a,’ all the way to the 5 character length of ‘ZZZZZ.’ We can stop the program if we find the password before this of course.

Copy this entire code snippet and paste it in a repl to see how it works:

#include "stdio.h"
int main(void) {
 
 // implement crack in a somewhat easy to understand way
 
 // first we try a password of only one letter.
 // we need to loop through each possible letter
 // create an isAlpha condition to go through both upper and lower case
 // always make room in the array for the null terminating char 
#include "stdio.h"
int main(void) {
// implement crack in a somewhat easy to understand way
// first we try a password of only one letter.
// we need to loop through each possible letter
// create an isAlpha condition to go through both upper and lower case
// always make room in the array for the null terminating char \0
char alpha[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
int alpha_len = (sizeof alpha / sizeof alpha[0]) - 1 ;
// guess password length 1
char g_1[2];
for(int a1 = 0; a1 < alpha_len; a1++)
{
g_1[0] = alpha[a1]; g_1[1] = '\0';
printf("%s\n", g_1);
}
// guess password length 2
char g_2[3];
for(int b2 = 0; b2 < alpha_len; b2++)
for(int a2 = 0; a2 < alpha_len; a2++)
{
g_2[0] = alpha[b2]; g_2[1] = alpha[a2]; g_2[2] = '\0';
printf("%s\n", g_2);
}
// __ __ __ __ __ __ __ __ __
// _\/_ _\/_ _\/_ _\/_ _\/_ _\/_ _\/_ _\/_ _\/_
// \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/
// Uncommenting this code will make this run super slow
// This is just to show what adding more letters looks like
// I didn't show password length 5, but i'm sure you can figure it out!
// // guess password length 3
// char g_3[4];
// for(int c3 = 0; c3 < alpha_len; c3++)
// for(int b3 = 0; b3 < alpha_len; b3++)
// for(int a3 = 0; a3 < alpha_len; a3++)
// {
// g_3[0] = alpha[c3]; g_3[1] = alpha[b3]; g_3[2] = alpha[a3]; g_3[3] = '\0';
// printf("%s\n", g_3);
// }
// // guess password length 4
// char g_4[5];
// for(int d4 = 0; d4 < alpha_len; d4++)
// for(int c4 = 0; c4 < alpha_len; c4++)
// for(int b4 = 0; b4 < alpha_len; b4++)
// for(int a4 = 0; a4 < alpha_len; a4++)
// {
// g_4[0] = alpha[d4]; g_4[1] = alpha[c4]; g_4[2] = alpha[b4]; g_4[3] = alpha[a4]; g_4[4] = '\0';
// printf("%s\n", g_4);
// }
}
// The copy paste is strong in this one
// char g_x[x];
// for(int x = 0; x < alpha_len; x++)
// g_x[x] = alpha[x];
 
 char alpha[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
 int alpha_len = (sizeof alpha / sizeof alpha[0]) - 1 ;
 
 // guess password length 1
 char g_1[2];
 for(int a1 = 0; a1 < alpha_len; a1++)
 {
 g_1[0] = alpha[a1]; g_1[1] = '
#include "stdio.h"
int main(void) {
// implement crack in a somewhat easy to understand way
// first we try a password of only one letter.
// we need to loop through each possible letter
// create an isAlpha condition to go through both upper and lower case
// always make room in the array for the null terminating char \0
char alpha[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
int alpha_len = (sizeof alpha / sizeof alpha[0]) - 1 ;
// guess password length 1
char g_1[2];
for(int a1 = 0; a1 < alpha_len; a1++)
{
g_1[0] = alpha[a1]; g_1[1] = '\0';
printf("%s\n", g_1);
}
// guess password length 2
char g_2[3];
for(int b2 = 0; b2 < alpha_len; b2++)
for(int a2 = 0; a2 < alpha_len; a2++)
{
g_2[0] = alpha[b2]; g_2[1] = alpha[a2]; g_2[2] = '\0';
printf("%s\n", g_2);
}
// __ __ __ __ __ __ __ __ __
// _\/_ _\/_ _\/_ _\/_ _\/_ _\/_ _\/_ _\/_ _\/_
// \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/
// Uncommenting this code will make this run super slow
// This is just to show what adding more letters looks like
// I didn't show password length 5, but i'm sure you can figure it out!
// // guess password length 3
// char g_3[4];
// for(int c3 = 0; c3 < alpha_len; c3++)
// for(int b3 = 0; b3 < alpha_len; b3++)
// for(int a3 = 0; a3 < alpha_len; a3++)
// {
// g_3[0] = alpha[c3]; g_3[1] = alpha[b3]; g_3[2] = alpha[a3]; g_3[3] = '\0';
// printf("%s\n", g_3);
// }
// // guess password length 4
// char g_4[5];
// for(int d4 = 0; d4 < alpha_len; d4++)
// for(int c4 = 0; c4 < alpha_len; c4++)
// for(int b4 = 0; b4 < alpha_len; b4++)
// for(int a4 = 0; a4 < alpha_len; a4++)
// {
// g_4[0] = alpha[d4]; g_4[1] = alpha[c4]; g_4[2] = alpha[b4]; g_4[3] = alpha[a4]; g_4[4] = '\0';
// printf("%s\n", g_4);
// }
}
// The copy paste is strong in this one
// char g_x[x];
// for(int x = 0; x < alpha_len; x++)
// g_x[x] = alpha[x];
';
 printf("%s\n", g_1);
 }
 
 
 
 // guess password length 2
 char g_2[3];
 for(int b2 = 0; b2 < alpha_len; b2++)
 for(int a2 = 0; a2 < alpha_len; a2++)
 {
 g_2[0] = alpha[b2]; g_2[1] = alpha[a2]; g_2[2] = '
#include "stdio.h"
int main(void) {
// implement crack in a somewhat easy to understand way
// first we try a password of only one letter.
// we need to loop through each possible letter
// create an isAlpha condition to go through both upper and lower case
// always make room in the array for the null terminating char \0
char alpha[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
int alpha_len = (sizeof alpha / sizeof alpha[0]) - 1 ;
// guess password length 1
char g_1[2];
for(int a1 = 0; a1 < alpha_len; a1++)
{
g_1[0] = alpha[a1]; g_1[1] = '\0';
printf("%s\n", g_1);
}
// guess password length 2
char g_2[3];
for(int b2 = 0; b2 < alpha_len; b2++)
for(int a2 = 0; a2 < alpha_len; a2++)
{
g_2[0] = alpha[b2]; g_2[1] = alpha[a2]; g_2[2] = '\0';
printf("%s\n", g_2);
}
// __ __ __ __ __ __ __ __ __
// _\/_ _\/_ _\/_ _\/_ _\/_ _\/_ _\/_ _\/_ _\/_
// \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/
// Uncommenting this code will make this run super slow
// This is just to show what adding more letters looks like
// I didn't show password length 5, but i'm sure you can figure it out!
// // guess password length 3
// char g_3[4];
// for(int c3 = 0; c3 < alpha_len; c3++)
// for(int b3 = 0; b3 < alpha_len; b3++)
// for(int a3 = 0; a3 < alpha_len; a3++)
// {
// g_3[0] = alpha[c3]; g_3[1] = alpha[b3]; g_3[2] = alpha[a3]; g_3[3] = '\0';
// printf("%s\n", g_3);
// }
// // guess password length 4
// char g_4[5];
// for(int d4 = 0; d4 < alpha_len; d4++)
// for(int c4 = 0; c4 < alpha_len; c4++)
// for(int b4 = 0; b4 < alpha_len; b4++)
// for(int a4 = 0; a4 < alpha_len; a4++)
// {
// g_4[0] = alpha[d4]; g_4[1] = alpha[c4]; g_4[2] = alpha[b4]; g_4[3] = alpha[a4]; g_4[4] = '\0';
// printf("%s\n", g_4);
// }
}
// The copy paste is strong in this one
// char g_x[x];
// for(int x = 0; x < alpha_len; x++)
// g_x[x] = alpha[x];
';
 printf("%s\n", g_2);
 }
 
 
// __ __ __ __ __ __ __ __ __
// _\/_ _\/_ _\/_ _\/_ _\/_ _\/_ _\/_ _\/_ _\/_
// \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/
// Uncommenting this code will make this run super slow
// This is just to show what adding more letters looks like
// I didn't show password length 5, but i'm sure you can figure it out!

// // guess password length 3
 // char g_3[4];
 // for(int c3 = 0; c3 < alpha_len; c3++)
 // for(int b3 = 0; b3 < alpha_len; b3++)
 // for(int a3 = 0; a3 < alpha_len; a3++)
 // {
 // g_3[0] = alpha[c3]; g_3[1] = alpha[b3]; g_3[2] = alpha[a3]; g_3[3] = '
#include "stdio.h"
int main(void) {
// implement crack in a somewhat easy to understand way
// first we try a password of only one letter.
// we need to loop through each possible letter
// create an isAlpha condition to go through both upper and lower case
// always make room in the array for the null terminating char \0
char alpha[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
int alpha_len = (sizeof alpha / sizeof alpha[0]) - 1 ;
// guess password length 1
char g_1[2];
for(int a1 = 0; a1 < alpha_len; a1++)
{
g_1[0] = alpha[a1]; g_1[1] = '\0';
printf("%s\n", g_1);
}
// guess password length 2
char g_2[3];
for(int b2 = 0; b2 < alpha_len; b2++)
for(int a2 = 0; a2 < alpha_len; a2++)
{
g_2[0] = alpha[b2]; g_2[1] = alpha[a2]; g_2[2] = '\0';
printf("%s\n", g_2);
}
// __ __ __ __ __ __ __ __ __
// _\/_ _\/_ _\/_ _\/_ _\/_ _\/_ _\/_ _\/_ _\/_
// \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/
// Uncommenting this code will make this run super slow
// This is just to show what adding more letters looks like
// I didn't show password length 5, but i'm sure you can figure it out!
// // guess password length 3
// char g_3[4];
// for(int c3 = 0; c3 < alpha_len; c3++)
// for(int b3 = 0; b3 < alpha_len; b3++)
// for(int a3 = 0; a3 < alpha_len; a3++)
// {
// g_3[0] = alpha[c3]; g_3[1] = alpha[b3]; g_3[2] = alpha[a3]; g_3[3] = '\0';
// printf("%s\n", g_3);
// }
// // guess password length 4
// char g_4[5];
// for(int d4 = 0; d4 < alpha_len; d4++)
// for(int c4 = 0; c4 < alpha_len; c4++)
// for(int b4 = 0; b4 < alpha_len; b4++)
// for(int a4 = 0; a4 < alpha_len; a4++)
// {
// g_4[0] = alpha[d4]; g_4[1] = alpha[c4]; g_4[2] = alpha[b4]; g_4[3] = alpha[a4]; g_4[4] = '\0';
// printf("%s\n", g_4);
// }
}
// The copy paste is strong in this one
// char g_x[x];
// for(int x = 0; x < alpha_len; x++)
// g_x[x] = alpha[x];
';
 // printf("%s\n", g_3);
 // }
 
 
 
 // // guess password length 4
 // char g_4[5];
 // for(int d4 = 0; d4 < alpha_len; d4++)
 // for(int c4 = 0; c4 < alpha_len; c4++)
 // for(int b4 = 0; b4 < alpha_len; b4++)
 // for(int a4 = 0; a4 < alpha_len; a4++)
 // {
 // g_4[0] = alpha[d4]; g_4[1] = alpha[c4]; g_4[2] = alpha[b4]; g_4[3] = alpha[a4]; g_4[4] = '
#include "stdio.h"
int main(void) {
// implement crack in a somewhat easy to understand way
// first we try a password of only one letter.
// we need to loop through each possible letter
// create an isAlpha condition to go through both upper and lower case
// always make room in the array for the null terminating char \0
char alpha[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
int alpha_len = (sizeof alpha / sizeof alpha[0]) - 1 ;
// guess password length 1
char g_1[2];
for(int a1 = 0; a1 < alpha_len; a1++)
{
g_1[0] = alpha[a1]; g_1[1] = '\0';
printf("%s\n", g_1);
}
// guess password length 2
char g_2[3];
for(int b2 = 0; b2 < alpha_len; b2++)
for(int a2 = 0; a2 < alpha_len; a2++)
{
g_2[0] = alpha[b2]; g_2[1] = alpha[a2]; g_2[2] = '\0';
printf("%s\n", g_2);
}
// __ __ __ __ __ __ __ __ __
// _\/_ _\/_ _\/_ _\/_ _\/_ _\/_ _\/_ _\/_ _\/_
// \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/ \/\/
// Uncommenting this code will make this run super slow
// This is just to show what adding more letters looks like
// I didn't show password length 5, but i'm sure you can figure it out!
// // guess password length 3
// char g_3[4];
// for(int c3 = 0; c3 < alpha_len; c3++)
// for(int b3 = 0; b3 < alpha_len; b3++)
// for(int a3 = 0; a3 < alpha_len; a3++)
// {
// g_3[0] = alpha[c3]; g_3[1] = alpha[b3]; g_3[2] = alpha[a3]; g_3[3] = '\0';
// printf("%s\n", g_3);
// }
// // guess password length 4
// char g_4[5];
// for(int d4 = 0; d4 < alpha_len; d4++)
// for(int c4 = 0; c4 < alpha_len; c4++)
// for(int b4 = 0; b4 < alpha_len; b4++)
// for(int a4 = 0; a4 < alpha_len; a4++)
// {
// g_4[0] = alpha[d4]; g_4[1] = alpha[c4]; g_4[2] = alpha[b4]; g_4[3] = alpha[a4]; g_4[4] = '\0';
// printf("%s\n", g_4);
// }
}
// The copy paste is strong in this one
// char g_x[x];
// for(int x = 0; x < alpha_len; x++)
// g_x[x] = alpha[x];
';
 // printf("%s\n", g_4);
 // }
 
}

// The copy paste is strong in this one
// char g_x[x];
// for(int x = 0; x < alpha_len; x++)
// g_x[x] = alpha[x];

So our output will be something like this:

click to enlarge

See how we try everything of length 1 char and then move on to the next loop, trying everything with length 2 chars? All we have to do now is:

• Run the current output in our loop through the crypt function
• compare the hash to the user’s hash given at the start of the program
• if they match print the plain text password and end the program, otherwise keep trying until we reach the last possible password ‘ZZZZZ.’

So I decided to create a function that takes the current combination of letters in the loop, runs it through crypt(), stores the hash and compares it against the hash given to us by the user at the start of the program:

bool crack(char *user_input, char *guess, char *salt)
{
 char *encrypted_guess = crypt(guess, salt);
 
 if (strcmp(encrypted_guess, user_input) == 0)
 return true;
 
 return false;
}

So now to test a single character password we have this:

// guess password length 1
 char g_1[2];
 for(int a1 = 0; a1 < alpha_len; a1++)
 {
   g_1[0] = alpha[a1]; g_1[1] = '
// guess password length 1
char g_1[2];
for(int a1 = 0; a1 < alpha_len; a1++)
{
g_1[0] = alpha[a1]; g_1[1] = '\0';
if(crack(user_input, g_1, salt))
{
printf("Password is: %s\n", g_1);
return 0;
}
}
';
 
   if(crack(user_input, g_1, salt))
   {
     printf("Password is: %s\n", g_1);
     return 0;
   }
 }

This was really tough, and I did a lot of reading about arrays, pointers, indirection and pointer arithmetic to understand not only this implementation but other more complicated versions of crack.c.

So finally here is the entire code I decided would solve this problem. For me at this stage in my learning this made total sense, and for that i’m happy with the result:

Until next time, keep on cracking!