CSC 290: Cryptology 2003: Dictionary Attack

UNIX Passwords and Dictionary Attacks

OK, now you've got me doing it. I'm shamelessly cutting and pasting from some site I found on google to bring you this tiny tutorial on UNIX-style password use.

Unix passwords are only stored in an encrypted form. When you log in, UNIX takes the first eight characters of your password (and some information from your login ID, called "salt") and produces from them a key for a very strong DES-style encryption of a string of zeroes. This encrypted "zero-message" is compared with the results generated by the same process when you created your password, which are stored in the "password" (or nowadays "shadow") file under your login name. Successful comparison means your password matches, even though the system does not store the password itself.

A dictionary attack uses a large list of "words" (or a carefully-chosen or guessed short list of likely "words") and encrypts them using the same hash function the computer uses to encrypt passwords. Then, just as in normal password situations, the cracking program compares the encrypted word with the encrypted string stored in the password file.

In order for this to work, the attacker must have access to the password file and a word list that includes the password for the account the attacker wants to compromise. In the good old days there was just a publicly-available password file but nowadays passwords are kept in a read-protected "shadow" file.

The "words" in the dictionary can be plain old english words or proper names, but nowadays systems typically demand both upper and lower case, non-alphabetic characters, etc. So a "dictionary" may be augmented with code that alters the base words systematically, say by trying different capitalizations, appending numerical digits to either end, whatever.

Salt

Salt is extra information that depends on the password owner that is put with a password before encryption; it tries to guarantee that each password is thus "personalized", and thus that just searching for passwords instead of pairs will not work. Thus hacker has N times the work for a system with N users.

Unix's extremely strong password encipherment is duplicated in PERL's crypt($pass,$salt) command, or at least I hope it is because that's what I used to make up this exercise.

The password encryption process goes something like this in Perl:

print ("Enter word to be crypted\t");
chop($word = );
$salt = "jo"; # Salt is the salt or seed and ends up being first
#two characters of the crypt output. In this
# case the salt is for Joel Seiferas, hence the jo.
$crypted = crypt($word, $salt);
print "encrypted password is $crypted\n\n";

Thus if Joel's password were theory, his encrypted password would be joKDYc97c4XkE. If the salt had been "br" (if brown's password were also theory), then the encryption would have been brFLIF6hzTUso. The idea is to make the hacker run his attack on a per-person basis, not on a per-system basis. So he's never looking for "some valid password", he's looking for "brown's password" or "joel's password".

Attack with Facts and Salt

Get on a Unix/Linux system and read the man page on the crypt function. Use this function and web/other resources to mount a dictionary attack on encrypted passwords. Note Perl has a crypt function that does the right thing, and I think Java has one too... java crypt function? .

From public sources you have obtained a copy of the URCS internal directory. Here is what it tells you in a tab-delimited way about the faculty . From a highly private source you have obtained the corresponding entries from the department's /etc/shadow file. As expected, you see the two letters of each login name appearing as salt at the beginning of each encrypted passord. You know the URCS faculty are incredibly, criminally naive and lazy about everything, including making up their passwords. Mount a dictionary attack on them and see how many passwords you can reconstruct.

Things to keep in mind for guessing passwords: areas of research, words in the dictionary, capitalization, numbers. Schneier has some references to papers that purport to describe attacks that are successful on 30 to 40 percent of users on real systems, so there is how-to literature out there if you're interested.

Use of fully canned password crackers is discouraged, as are pre-encrypted dictionaries. Past classes have done impressively well on this exercise, but I gather they spent significant time on it as well. Use of text dictionary resources on the other hand (e.g. /usr/dict/words ), is encouraged and probably necessary to complete the assignment in a timely fashion. As usual, document all of the resources you use. Note that the crypt function does not run all that fast (deliberately), so you may have to allow considerable time for your program to run. Depending on the software you are using, you may also have to put -lcrypt on the link line in Linux systems, which is not mentioned in the documentation, at least on my Linux system.

Fewer Facts, no Salt

Next, try to attack the accounts of this gaggle of celebs. Here is their celebs shadow file. Here it seems there is no salting, which makes things easier for you since you can check your guessed passwords directly against all celebs in the file. Most of these passwords are poorly chosen, i.e. they are short, or words, or names, or minor variations thereof, or potentially guessable because they are TOOOO clever, or all of the above. (No guarantees about only lowercase letters being present though). See how many you can find out of the list of 50. The same rules apply as on the previous part.

Chris Brown's code to do all this was about 200 lines of Perl.

As usual, hand in writeup in PDF through webCT, hardcopy of everything to the prof. as well.

---

This page is maintained by CB.

Last update: 30.08.03.