CS 231: Computer Security

Playing with passwords

Partner or alone, as you wish.

Hand in by creating a folder named "passwords" at the top level of your CS231 repository. See the What to hand in section below for more details.

Part 1. Unsalted passwords

Password files on Unix systems have lines that look something like this:

This colon-delimited set of fields includes the user name, the MD5 hash of the user's password, and then miscellaneous other stuff that won't concern us.

As we'll see, this is not an ideal format for a variety of reasons, including the fact that MD5 has been substantially weakened by mathematical research and faster computers, but it's certainly an improvement on storing the passwords themselves.

Consider this example password file. Your job for Part 1 is to:

• Figure out as many of the passwords as possible
• Collect timing information (see What to hand in below for details)".

A little help

• Every one of the passwords is either one all-lowercase word taken from this file of words, or two words from the same file concatenated together. So "moose" or "goatlizard" are both possible passwords.
• For your debugging assistance: the password for "jondich" is "moose".
• You can load the words file into a python3 list quickly using this line:
  words = [line.strip().lower() for line in open('words.txt')]
• Working in python3 (which I recommend) means that you have to do some pretty nutty type conversions between the password string and the hash value, etc. Here's a short sample program to help you get started.
• You can time a Unix command-line program by putting "time " in front of the command (like "time python yourprogram.py"). It produces output like this:
  real 0m0.022s user 0m0.002s sys 0m0.006s
  (This was the output for "ls", so the numbers are very small.) There's a nice description of the meaning of this output on stackoverflow, not surprisingly. When you report times, you should report user time.

Part 2. Salted passwords

Now, let's switch to a slightly different password file format:

In the hash field, we have an 8-digit hexadecimal number known as "salt", then a dollar sign, and then the hash of the salt (which is just a string of hexadecimal digits) concatenated with the password. As before, the "jondich" password is "moose", so you can use that to check your hash computation code. Also, as before, the hash function we're using is MD5.

(WARNING: This hashing technique is designed to introduce you to the basic idea of salted passwords. However, the technique and salt sizes used here are not ready for prime-time. There are a couple more steps we need to take—longer salts, multiple rounds of hashing, etc.—before we're getting close to best practice for password storage.)

Here's the salted password file. Same kind of passwords as in Part 1.

Again:

• Figure out as many of the passwords as possible
• Collect timing information (see What to hand in below for details)".

By what factor has your password-checking slowed down? Why?

What to hand in?

In your "passwords" folder, put:

• A file for Part 1 named passwords1.txt, consisting of lines of the form "username:password", like
  jondich:moose
  for each of the passwords you discovered.
• A file for Part 2 named passwords2.txt, same format as passwords1.txt.
• A file named summary.txt, showing:
  Part 1 Passwords cracked: [number cracked] Total time: [user time from a "time" command] Number of hashes computed: [number of MD5's computed] Passwords cracked per number of hashes computed: [passwords per hash] Time per password cracked: [seconds per password] Part 2 Passwords cracked: [number cracked] Total time: [user time from a "time" command] Number of hashes computed: [number of MD5's computed] Passwords cracked per number of hashes computed: [passwords per hash] Time per password cracked: [seconds per password] Factor by which your time per password lengthened, and why. [number and explanation]

Have fun!