In this assignment, you are provided a traditional UNIX-style password ﬁle. The ﬁle contains salted and hashed passwords. Your job is to reveal as many of the passwords as possible, by performing a dictionary attack where you generate password guesses, hash them, and match the result with the entries in the password ﬁle.
On a traditional Unix system, passwords are stored in encrypted form in a world-readable ﬁle /etc/passwd. Moreover, the encryption algorithm is widely known. This means that an attacker can attempt to discover one or more passwords on the system by encrypting a sequence of strings and comparing the results against the stored encrypted passwords of the system. If any of the trial encryptions match stored encrypted passwords, the attacker will know the corresponding cleartext password for that user and can then use it to access the user’s account. This is a classic dictionary attack and explains why many systems enforce rules to ensure that user-generated passwords are not easily guessed words. Password Cracking
Systematic password guessing involves both cleverness and brute force. Dictionary attacks are so named because a word list, or dictionary, is used to generate password guesses. A more sophisticated dictionary attack not only uses common words and phrases, but also attempts users’ surnames, common pet names, “worst passwords” from lists published on the web, etc. Such words and phrases may be prepended to the dictionary and then become available in the attack.
A user may attempt to render his or her password unguessable by “mangling” the plaintext password in some algorithmic way. Some common “mangles” (ways to take a password and make it less easily guessable) are listed below. Assume the plaintext password is “string”. You might:
prepend a character to the string, e.g., 0string; append a character to the string, e.g., string9; delete the ﬁrst character from the string, e.g., tring; delete the last character from the string, e.g., strin; reverse the string, e.g., gnirts; duplicate the string, e.g., stringstring; reﬂect the string, e.g., stringgnirts or gnirtsstring; uppercase the string, e.g., STRING; lowercase the string, e.g., string; capitalize the string, e.g., String; ncapitalize the string, e.g., sTRING; toggle case of the string, e.g., StRiNg or sTrInG.
You only need to consider characters that are letters (uppercase and lowercase) and numbers; so no special characters (such as “#”, “¢”, “?”, etc) or control characters. (This goes against the general wisdom that says that a “good” password should consist of different kinds of characters, but it simpliﬁes the assignment.)
There are several programs available to system administrators to test the guessability of user passwords, as well as by hackers to perform dictionary attacks, such as John the Ripper , Cain & Abel , and Crack .
The goal of this assignment is to implement a portion of those programs’ functionality and attempt to guess one or more passwords. Input to your program will be a “captured” /etc/passwd ﬁle from a system with 20 users. Your aim is to crack as many passwords as possible. But don’t expect to crack them all; if you get 15 or so passwords, you’re doing just ﬁne.
How do you know when to stop? You don’t! Write the program to run until it ﬁnds all of the passwords. Realistically, your program should ﬁnd a majority of the passwords (12 or so) in just a few minutes. Make sure that you print out the passwords as they are found and that you code your program reasonably efﬁciently.
To do this for a speciﬁc user, you might take the following steps:
Extract the encrypted password and salt for that user (see format below); Seed the word list with words that the user might have utilized in constructing his or her password (e.g., his ﬁrst and last name); With the salt and augmented wordlist, systematically encrypt words and compare against the stored encrypted password; Redo step 3, but using mangled versions of the words; Redo step 4, attempting to apply two mangles to each word.
Design your program in such a way as to be as efﬁcient as possible. For example, your program should stop searching with respect to a given user if you have cracked that password. Consider whether to use a breadth-ﬁrst or depth-ﬁrst search. Also consider if you should try to break one password at a time, of if you should try to match each guess against all entries in the password ﬁle. The algorithm only considers the ﬁrst eight characters of a password, but the user might or might not take that into account. You do not have to break all passwords, but you should break at least the simple passwords (generated from words in the dictionary using one mangle). In general, if you can’t break most of the passwords, you’re not trying hard enough. Encryption Speciﬁcs
On traditional UNIX system, passwords are encrypted and stored in the ﬁle /etc/passwd. The stored value is actually the result of encrypting a string of zeros with a key formed from the ﬁrst eight characters of your password and a two-character “salt”.
The “salt” is a two-character string stored with a user’s login information. Salt is used so that anyone guessing passwords has to guess on a per-user basis rather than a per-system basis. Also, in the case that two users have the same password, as long as they have different salt, their encrypted passwords will not be the same.
All of the passwords for this project have been encrypted using JCrypt which can be found online at: JCrypt . JCrypt is a Java implementation of the UNIX Crypt function. JCrypt includes a method crypt( String salt, String password ) which will return the encrypted result of a given salt and password.
For example, if a user’s plain text password is “amazing” and the salt is “(b”, then JCrypt would return “(bUx9LiAcW8As”. Use JCrypt in your program when checking your password guesses.
Lines in /etc/passwd have the following format, with ﬁelds separated by colons:
account:encrypted password data:uid:gid:GCOS-field:homedir:shell
The GCOS ﬁeld is in free-text format and is often used for the full name (the origin of the label “GCOS” is historical). For example, this line represents the account for Tyler Jones. The salt is “<q”.
The encrypted password data ﬁeld is thirteen characters long. The ﬁrst two characters are the salt, and the next eleven characters are the encrypted password (actually, a string of zeros encrypted with the salt and the password).
As a remark, newer systems make dictionary attacks more difﬁcult by employing “shadow passwords.” In a shadow password system, the password ﬁeld in /etc/passwd is replaced with an ‘x’. Actual encrypted passwords are stored in a ﬁle /etc/shadow which is not world-readable. Implementation
In this assignment, a the cracker program is called PasswordCrack. It takes two arguments, and should be executed as follows:
$ javac PasswordCrack.java $ java PasswordCrack <dictionary> <passwd>
The ﬁrst argument <dictionary> is dictionary of words, with one word per line. The second argument <passwd> is the password ﬁle, containing the hashed passwords in the format described above. The cracked plaintext passwords are printed to the terminal (standard output), one per line. The passwords can be printed in any order, so as soon as you have cracked a password, just print it out. Do not write anything else besides passwords to the terminal! So no logging or debug messages. We will run your program and check its output, and everything your program writes will be taken for cracked passwords. Environment This assignment is a programming exercise, and you should use Java to solve it. You can use any Java development environment of your choice; however, it is a requirement that the code you ﬁnally submit runs on the the course virtual machine. Furthermore, your submitted code should be possible to execute directly in a Linux shell, as described above in section “Implementation”, so it should not depend on any IDE tool such NetBeans or Eclipse. Challenge Each student gets a unique password ﬁle to crack – a challenge. So the ﬁrst thing you should do is to fetch your challenge. We use a separate assignment in Canvas for this: Password Cracker Challenge. Request your challenge by making a submission there (it doesn’t matter what you submit). After a while, you will get your individualized challenge as feedback to your submission.
Your challenge will be a zip archive “cracker-challenge.zip”. There you can ﬁnd the following ﬁles:
passwd1.txt – password ﬁle with twenty entries passwd1-plain.txt – plaintext passwords for the entries in passwd1.txt passwd2.txt – password ﬁle with twenty entries (each student gets a different ﬁle) INSTRUCTIONS – a ﬁle with brief instructions for your submission Makeﬁle – conﬁguration ﬁle for “make” that you should use to create your submission
You can ﬁnd a list of words that you can use as a dictionary here: dict.zip. Actually, we strongly recommend you use this dictionary, since it is the main dictionary we use for generating passwords