ROB BOWDEN: I'm Rob, and let's get cracking. So remember from the pset spec that we're going to be needing to use the crypt function. For the man page, we have two hash define _xopensource. Don't worry about why we need to do that. And also hash include unistd.h. 

So once that's out of the way, let's get to the actual program. First thing we need to do is make sure the user entered a valid encrypted password at the command line. Remember that the program is supposed to be run like dot slash crack, and then encrypted string. 

So here we're checking to make sure that argc to two if we want to continue with the program. If argc is not two, that means either the user didn't enter an encrypted password at the command line, or they entered more than just the encrypted password at the command line, in which case we don't know what to do with the command line arguments. 

So if argc was two, we can continue. And here, we're going to declare a variable encrypted. That's just going to alias the original argv1 so that throughout this program, we don't have to call it argv1, which then you have to think about what that actually meant. 

So finally, we want to validate that the encrypted password the user entered could have actually been an encrypted password. Per the man page of crypt, the encrypted password must be 13 characters long. Up here, notice that we hash defined encrypt length as 13. So we're just making sure that the string length of the encrypted password is 13. 

And if it's not, we want to exit the program. So once that's out of the way, we can now actually try to find what the password that gave the encrypted password was. Here, we want to grab the salt from the encrypted password. Remember, per the man page, that the first two characters of an encrypted string, like here-- 50ZPJ and so on-- the first two characters give us the salt that was used in the crypt function. 

And here, we see that the salt was ha. So we want to copy the first two characters, salt length being hash defined as two. We have to copy the first two characters into this array, salt. Notice that we need salt length plus one, since we still need a null terminator at the end of our salt. 

Then we're going to declare this array, guest, of size max length plus one, where max length is hash defined as eight, since the maximum password is eight characters long. And we're going to use this to iterate over all possible strings that could be valid passwords. So if the valid characters in a password were just a, b, and c, then we would iterate over a, b, c, aa, ba, ca, and so on, until we get to see cccccccc-- eight c's. 

And if we have not down a valid password, then we need to say that the encrypted string wasn't valid to begin with. So now, we reach this while 1 loop. Notice that means it's an infinite loop. 

Notice there are no break statement inside of this infinite loop. There are only return statements. So we never actually expect to exit the loop. We only expect to exit the program. I've added this print statement to the top of this loop to just print out what our current guess at what the password is. 

Now, what is this loop doing? It's looping over all possible strings that could be valid passwords. The first thing we're going to do is take our current guess for what the password is. We'll take the salt that we grabbed from the encrypted string, and we're going to encrypt the guess. This will give us an encrypted guess, which we're going to compare against the encrypted string that the user entered at the command line. 

If they are the same, in which case string comparable will return zero, if they're the same, then guess was the password that generated the encrypted string, in which case we can print that as our password and return. But if they weren't the same, that means our guess was incorrect. 

And we want to iterate to the next valid guess. So that's what this while loop is trying to do. It's going to iterate our guess to the next valid guess. Notice that when we say that a particular character in our guess has reached the max symbol, which up here is hash defined as a tilde, since that's the largest ASCII value character that a user can enter at the keyboard, when the character reaches the max symbol, then we want to send it back to the minimum symbol, which is a space, again the lowest ASCII value symbol that a user can enter at the keyboard. 

So we're going to set that to the minimum symbol. And then we're going to go on to the next character. So how are our guesses going to iterate? Well, if the valid characters are a, b, and c, then if we started with a, it'll iterate to b, it'll iterate to c. c is our max symbol, so we'll set c back to a, the minimum symbol. And then we'll iterate index to the next character. 

So if the original guess was c, the next character is going to be the null terminator. Down here, notice that if the character that we now want to increment was the null terminator, then we're going to set it to the minimum symbol. So if the guess was c, then our new guess is going to be aa. And if our original guess was cccc, then our new guess is going to be aaaaa. 

So whenever we reach the maximum string of a given length, then we're going to implement to the minimum string of the next length, which will just be all characters of the minimum symbol. Now, what is this check doing here? Well, if index moved from the eighth character to the nine character-- so we add eight c's as our previous guess-- then index is going to focus on the last null terminator of our guess array, which is not meant to actually be used in our password. 

So if we are focused on that last null terminator, then we haven't found a password that's valid using just eight characters, which means there is no valid password that encrypts to the given string. And we have to print that, saying we couldn't find a valid password, and return. So this while loop is going to iterate over all possible strings. 

If it finds any that encrypts to the expected encrypted string, it'll return that password. And it it doesn't find anything, then it will return, printing that it wasn't able to find anything. Now, notice that iterating over all possible strings is probably going to take a while. Let's actually see how long that takes. 

Let's make crack. Well, oops-- it says undefined reference to crypt. So remember, for the p sets spec and also the man page for crypt that we need to link in crypt. Now, the default make command doesn't know that you want to use that function. 

So let's copy this client command and just add on to the end of it, linking crypt. Now, it compiles. So let's run crack on a given encrypted string-- so Caesar's. So that was pretty fast. 

Notice that this ended on 13. Well, Caesar's encrypted password happens to be 13. So let's try another password. Let's take Hirschhorn's encrypted password and try cracking that. 

So notice we've already reached three characters. And we're iterating over all possible three-character strings. That means we've already finish iterating over all possible one and two character strings. Now, it looks like this is going to take a while before we reach the four-character strings. It might take a couple of minutes. 

It didn't take a couple of minutes. We're on the four-character strings. But now, we need to iterate over all possible four-character strings, which that might take maybe 10 minutes. And then when we reach five character strings, we need to iterate over all of those, which might take a couple hours. And we need to iterate over all possible six-character strings, which might take a couple days and so on. 

So it could take a potentially very long time to iterate over all possible eight-character and fewer strings. So notice that this isn't necessarily a very efficient algorithm for finding a password. You might think that there are better ways. For example, the password zyx!32ab probably isn't a very common password, whereas the password 12345 is probably a lot more common. 

So one way of trying to find a password more quickly is to just look at passwords that are more common. So for example, we can try to read words from a dictionary and try all of those words as our password guesses. Now, maybe a password isn't that simple. Maybe the user was somewhat clever and try appending a number to the end of a word. 

So maybe their password was password1. So you can try iterating over all words in the dictionary with a one appended to the end of it. And then maybe after doing that, you'll append a two to the end of it. 

Or maybe the user is trying to be even more clever, and they want their password to be "hacker," but they're going to replace all instances of e's with threes. So you could do this too. Iterate over all words in the dictionary but replace characters that look like numbers with those numbers. 

So this way, you might catch even more passwords that are pretty common. But in the end, the only way you can capture all passwords is to brute force iterate over all possible strings. So in the end, you do need to iterate over all strings from one character to eight characters, which might take a very long time, but you need to do it. 

My name is Rob Bowden. And this is Crack.