Brute-force password cracking

Folder: passwords
Files: passwords/summary.txt, cracked1.txt, cracked2.txt, cracked3.txt, passwords.py

Partner or solo, as you wish.

Goals

• Learn some basic facts about how passwords are stored
• Analyze the effects of salt as a protection against brute-force password cracking
• Think about why we store hashed passwords instead of just the passwords

Rubric

Part 1: Unsalted one-word passwords

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

As we'll see, this is not quite a modern format for a variety of reasons, including the fact that the cryptographic hash function has not been explicitly specified and there's no salt included. But this is pretty close to how passwords are stored on most Linux systems.

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

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

A little help

• Every one of the passwords in this file is one all-lowercase word taken randomly from this file of words.
• For your debugging assistance: the password for "jondich" is "moose".
• You can load the words file into a python list quickly using this line:
  words = [line.strip().lower() for line in open('words.txt')]
• Working in python3 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: Unsalted two-word passwords

Same task as Part 1, but using example password file #2. This time, all the passwords are two random words concatenated (e.g. "cowgecko"). The password for jondich is still "moose".

Part 3: Salted passwords

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

For this phase, use example password file #3.

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 concatenated with the password (i.e. H(salt || pw)). 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 SHA-256.

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

As in parts 1 and 2:

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

What to hand in?

In your "passwords" folder, put:

• Your source code in a program named passwords.py

• A file for Part 1 named cracked1.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 cracked2.txt, using the same format as cracked1.txt.

• A file for Part 3 named cracked3.txt, using the same format as cracked1.txt.

• A file named summary.txt, showing:

  Part 1 Total time: [user time from a "time" command] Number of hashes computed: [count of the # of hashes computed] Passwords cracked: [number cracked] Time per hash computed: [seconds per hash] Time per password cracked: [seconds per password] Passwords cracked per number of hashes computed: [passwords per hash] Part 2 Total time: [user time from a "time" command] Number of hashes computed: [count of the # of hashes computed] Passwords cracked: [number cracked] Time per hash computed: [seconds per hash] Time per password cracked: [seconds per password] Passwords cracked per number of hashes computed: [passwords per hash] Part 3 Total time: [user time from a "time" command] Number of hashes computed: [count of the # of hashes computed] Passwords cracked: [number cracked] Time per hash computed: [seconds per hash] Time per password cracked: [seconds per password] Passwords cracked per number of hashes computed: [passwords per hash] Analysis: - Did your time per hash computed change between phases? By what factor? Why? - Did your time per password crack change between phases? By what factor? Why? - Suppose you wanted to precompute all the hashes for each possible password so you could just look up the password in a table indexed by the hash. How much memory would be required for each phase? - Give 3-4 reasons we should store password hashes and not the passwords themselves. Think in terms of threats, who the attackers might be, etc.

A couple clarifications

• For the memory question in summary.txt, as a rough estimate you may assume:

  • Each hash string is 32 bytes long.
  • Each password is 16 bytes long.
  • Each mapping of a hash to a password takes up an additional 32 bytes of overhead beyond the space required to store the hash and the password.

• How many passwords do you need to crack for Phase 2 to get that point's worth of credit? Well, I just wrote a very simple cracker and ran it for two hours. That's how long it took to get through the 2-word passwords starting with a and b. I got over 200 cracked passwords that way. So I figure I will give that full point in the rubric to you if you can crack at least 300 of the 2-word passwords. Half a point for 100.

Have fun!