CS50: Introduction to Computer Science I (Week 5/Mon)

>> David Malan: All right, welcome back to CS50! This is week five, so in problem set two, you'll recall that some of your classmates tackled the so-called hacker edition, and that hacker edition had them tackle a number of encrypted passwords, which looked a little something like this. So, long story short, if you didn't actually read this PDF at the time, this was the hacker edition. Passwords on the typical Linux system are stored in an encrypted form, so you have essentially this format in a file called XE Password Etcetera/Password. Julius would be the username, colon, and then some cryptic-looking string would be the encrypted password. And do you mind, Barry, taking my voice down a little bit? There's a bit of an echo up here. Much better. So, these students, who tackled the hacker edition, needed to decipher, needed to crack those passwords; but, unfortunately, the routine that's used in a typical Linux system to encrypt passwords is a one-way function, which means it's relatively easy and relatively fast to take in plaintext and generate cipher text, but you can't actually reverse the process. So, as I mentioned a few weeks ago, if you've ever lost a password to a typical website or to your FAS account, odds are you might've gotten annoyed at the text support person, because they insisted, "I can't tell you what your password is," but they can change it, and that's because of this mathematical property that's generally used for passwords. They're normally known as a one-way hash. And as the name implies, you can only encrypt in one direction; you can't decrypt. So, if you can't decrypt passwords in this way, how in the world are all of us logging in to FAS and logging in to Facebook and other such sites every day of the week? How is it that these sites are storing our passwords encrypted, and yet they're still somehow checking that what I type in, in plaintext, matches my password? So, in other words, if you can't decrypt the cipher text to then compare the plaintext I initially gave them, when I created my account, and the plaintext I just typed in, when visiting Facebook.com or equivalent, how do you actually compare what I typed in and what they know my password to be? Yeah?

>> Just encrypt what [inaudible].

>> David: Just what?

>> Encrypt what —

>> David: Yeah, just encrypt what I just typed in. So, in other words, what a typical website or server does these days is, again, it encrypts your password when you create your account and stores it in a crazy format like this; but, subsequently, when you log in, the server simply re-encrypts whatever you just typed in, using the same algorithm. And then if the two cipher texts match, does it actually let you pass. But the curious thing is, because of the mathematics of a lot of these implementations, there is a probability, though very, very low, that you could type in one word, and it would encrypt to some cipher text, and you could type in another word, a different word, but it might very well encrypt to that same cipher text; in other words, you might very well be able to login to some accounts you guys have, using any number of passwords, but the probability of that is very low, and the probability of figuring out what other words might hash, so to speak, to the same value is itself very low. So, a number of our students, who are more comfortable, did, in fact, determine that Julius' password was just 13. The clever, or those who like stupid jokes might understand what the reference there is. Julius Caesar, you know, 13.