Password Cracker

Concepts Covered: Reading and Processing text files, Exception Handling, Writing and using a simple Class, Using the ArrayList class, Using the String.split() method, Password Security

Due: Thursday, February 7 at midnight Tuesday, February 12 at midnight

Files you need: password, wordlist (slightly modified from one that I downloaded from the web)

Turn In: PWCracker.java, Word.java, README

Background: How does UNIX store your password on the computer? In the old days, there was simply a file on the computer called /etc/password. The file stored the userid along with the user's encrypted password. Remember that encryption is the process by which a message is garbled so that it's unreadable by any unauthorized viewers. The unix password encryption process is different from those we have seen, however, in that it is a one-way encryption, meaning that the encryption function that is used does not have a decryption function associated with it (unlike our substitution cipher example, where we can decrypt the message). Therefore it is safe (or so it seems) to store the file containing the encrypted passwords publicly where everyone can see them, since they have no hope of decrypting the passwords.

So, what exactly happened when you type in your password to logon to a UNIX machine in the old days? You would type in your password, UNIX would run it through the encryption function and then compare the result of the encryption with the encrypted password stored in the /etc/password file. If there was a match, you would be granted access to the machine.

Although this sounds relatively secure (in that it will keep unauthorized users off the system), it's not. Unfortunately, most people pick simple passwords that are easy to remember. The downside of this is that the /etc/password file can be cracked by a simple dictionary attack. The dictionary attack simply uses a word list (or a dictionary). It encrypts each word in the list using the UNIX password encryption function (which is public knowledge) and then checks the /etc/password file to see if there are any matches. If there are, then a password has been cracked!

Most knowledgable network administrators no longer use this method because of the threat of these dictionary attacks. They use shadow passwords which keep the encrypted passwords in a private file. As recently as 6 years ago, however, a major educational institution (not USC) had their entire student body's passwords stored in this manner. Any user on the system could simply download the /etc/password file and run it through a program that would crack up to 50% of the passwords. And those passwords were used for everything (much like UGA's myid)! So it's always important to pick good passwords (i.e. stuff that would not be found in a dictionary or your name or slight variants), because you never know if the administrator of the network is keeping your passwords secure.

Requirements: For this project, I have given you a fake password file and a list of commonly used passwords. Your job is to write a program that cracks as many of the passwords as possible using the provided wordlist and some ingenuity.

Your program should start by creating a word list. First, you should write a class called Word that has as attributes a String representing the word and a long representing the encrypted word (sometimes referred to as a hash). It should have a constructor (that takes in a String), getters for each attribute and a method that computes the hash of the word. It should be documented in javadoc format.

The encryption function is very simple. Note that this is NOT the encryption method that UNIX uses - UNIX's is, of course, much more complicated. Our encryption function is simply the sum of the unicode values of all the characters in the word, multiplied by the product of the unicode values of the FIRST FIVE characters in the word. After that, take the remainder from dividing the result by 1459303249 (which happens to be a large prime number). If there are less than 5 letters in the word, then replace "the FIRST FIVE letters" in the previous sentence with "all of the letters". You may check that your encryption function is working correctly by using it on the following words and making sure your results are the same as mine.

• hello : 1205468819
• goodbye : 312635099
• hello27 : 502523728
• eybdoog : 1200983286

Your main program class, PWCracker, should begin by creating a word list. To create a word list in your program you should use the ArrayList class. You can read about how to use methods of the ArrayList class in the Java API. Your ArrayList should contain only Word objects (in other words, it should be a Java 1.5 array list and the compiler should not generate any warnings). So basically, your program will open the wordlist file, go through it one word at a time and add it (and possible variations) to the ArrayList representing your word list.

Next, your program should open and begin reading the password file. For each line in the file, you should (at the very least) extract the encrypted password and check it against all the words in the word list, until you run out of words or you find a match. You may want to consider trying to extract other useful words from the file to add them (along with possible variations) to your wordlist before you begin checking for matches.

Note that when you extract the password it will be a String (since String.split() returns an array of Strings). You can use the parseLong() static method in Long class to convert it into a long integer. You can read more about that method by looking up the Long class in the Java API.

The format of each line of the password file is as follows -

- so you will need to call the split method of each line using ":" as a delimeter. You can read how to do that in the Java API for the String.split() method.

Make sure that you use longs instead of ints for all of the integers in your program - some of the numbers get very big very fast!

At the end of your program, you should print all passwords to the screen in the following format:

In other words, you should print the userid, a tab, and the password or the String "NOT FOUND" if the password is not found.

Grading: In order to get 100% on this project, you must crack at least 15 of the 25 passwords in the password file. For each password that you correctly identify beyond the 15, you will receive 2 bonus points. So, potentially, you can get up to 120% on this project. In addition to that, your grade will be based on the following:

• Meeting all requirements described above
• Your coding style (proper indentation, etc)
• Your inline comments
• Your README file (you may see the requirements for the README file in the project1 assignment).

Rules: Since the stakes are so high on this project, I expect you to follow a few rules that are not in effect on other projects. They are as follows:

• Note that the hash function is not necessarily one-to-one. In other words, multiple passwords may map to the same number. It would be very easy to write a program that goes through Strings systematically until it finds a word that maps to the same number. Any passwords cracked in this manner will not be counted as correct - all passwords in the password file are either in the word list directly, variants of words in the word list, or information that can be found in the password file (or variants thereof).
• You may not add any words to the word list file. Your program may add words to the ArrayList representing your word list, but they should only be variants of the words in the word list, or the information contained in the password file.
• You should be very secretive about how your password cracker works (i.e. the variants that it tries). It would not be fair for other people in the class to get extra credit based on your ingenuity. So DO NOT talk about your implementation of the program with anyone. It is okay to brag about how many passwords you cracked - even which userid's passwords you've found. It is NOT okay to talk about WHAT those passwords are, or HOW you cracked those particular passwords.