>> 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.