Unix Passwords

In this lab you will try several methods of attacking a file to find user passwords.

Objectives

• understand how UNIX handles passwords
• understand the evolution of UNIX password handling and the reasons behind it
• understand the techniques that attackers use to crack passwords
• realize the importance of choosing a password that is resistant to these kinds of attacks

Background

Unix passwords are hashed with the crypt() function. The crypt function takes a plaintext password and a "salt". The salt is used to ensure that users with the same password will most likely not have the same encrypted password. The system randomly chooses the salt, hashes it along with the password, and then stores the salt in the password file so that it remembers what to add the next time the user's password needs to be verified. crypt() hashes the plaintext password and salt, and returns the encrypted password. The salt is traditionally stored as the first two letters of the encrypted password. When programming in C you need to compile with the -lcrypt command to link in the crypt() function. Do a "man crypt" or see the link below to find out more.

Password hashes were traditionally computed using a variant of DES and stored in a world-readable file called /etc/passwd. This made it easy for various services to require user passwords - they could hash the entered password and check it for themselves. The disadvantage of this approach was that anyone on the system could copy the password file to another machine and spend as long as they wanted guessing passwords. This is known as an off-line attack.

Within the last 10 years or so, Unix systems have prevented these off-line attacks by keeping the hashes in a separate file, /etc/shadow, which only root can read. Now an attacker has to try passwords on-line, and the system can log his failed attempts.

The other limitation of the original crypt() function is that it only accepts 56 bits of input. This effectively limited passwords to 8 (7-bit) characters. In 1998, the Electronic Frontier Foundation showed that 56-bit passwords could be completely brute-forced in a reasonable amount of time with reasonably cheap hardware (Read about the EFF DES cracker here). Consequently, many variants of Unix now use MD5 to hash user passwords, allowing passwords of arbitrary length. Additionally, the output of the normal MD5 function is run back in as input, hashing it again. This is done 1000 times. Why? It's a constant-factor tradeoff in CPU cycles for security - verifying a valid password by the system takes 1000 times longer, but so does trying an invalid one. If a cracker gets ahold of the /etc/shadow file, an attack that would take 1 day on single-round MD5 passwords takes almost 3 years with 1000-round hashes.

An easy way to break a poorly chosen password is the dictionary attack. In a dictionary attack you encrypt all the words of a dictionary with the salt and compare the result with the encrypted password you are trying to break.

If the dictionary attack doesn't recover the password, a simple substitution attack is sometimes used. Some of the most common substitutions in passwords are 0 for O or o, 1 for l or I, and 3 for e or E. With this attack you will need to use the dictionary attack, but replace occurences of the commonly substituted letter with the corresponding number. You can also try appending or prepending one or two digit numbers to the dictionary words.

The brute force attack is an exhaustive attack; for good passwords of sufficient length, it's completely impractical. Every possible combination of legal letters is encrypted and matched against the encrypted password to see if it's a match.

Samples

DES sample

MD5 sample

Password Files

DES passwords

MD5 passwords

Passoff Requirements (Demonstrate in-person to a TA that you have fulfilled these)

1. You must write a program (or three seperate programs) that do each of the following: 1) a brute force attack 2) a dictionary attack and 3) a substitution attack.
2. Your program should allow the user to input a password file using DES or MD5. (Run your program for a while using both methods to get a feel for the time difference required).
3. If you code your program correctly, you should quickly retrieve three dictionary words that were added to the password file by the TA's. You must retrieve these words in order to pass off.

Suggestion:
Run as many attacks as you can on the two password files. The top ten students with the most passwords cracked will recieve extra credit. It would be wise to start early on this lab so you will have plenty of time to run your code.

Rules:

1. You are not allowed to use any commercial or open source password cracking software. You can only use the program you write.
2. You may use any dictionary you can find or download. See the link below.
3. You may not work with other students. The passwords you turn in must be generated by your own program.
4. If you run your code on multiple lab machines, make sure you "nice" the processes so that other users can still get reasonable performance from those machines.

Resouces

One of the best dictionary sites can be found at: Access Data. You can download and use any of their dictionaries, but remember that sometimes a smaller english dictionary is better, because it allows you to do more substitutions and number appending. They also offer several language dictionaries, common password dictionaries, common name dictionaries, etc. I would start with the small "English Lover's Dictionary" just to be sure your code is working.

The man page on crypt() is very useful. Note that by default it performs DES, but under the "GNU Extension" section it talks about how to make crypt() do MD5.

Here is a simple program that demonstrates how to hash: Hasher