Operating system: Linux Solution

Software required: Crypto libraries. You are allowed to use only the primitive hash functions that take a single input. For instance, hashlib.md5(string) in python. Password cracking utilities are explicitly prohibited (but can be used for verification).

Language: C/C++ or any other that you prefer. Note that speed may be a consideration.







In this project, you are asked to crack passwords from a "stolen" /etc/shadow file on a Linux system (See the file etc_shadow). You will work as teams of two. Each teacm will crack the password for team[i] where i is the team number that is assigned by the TA. Each line in the file has the hash type, salt, and the hash of the password.

For instance, consider an example first line "team0:$1$hfT7jp2q$/sDfNdP2e3OCxg2zGq1FK0:16653:0:99999:7:::",

$1$ indicates the hash algorithm to be MD5

$hfT7jp2q$ indicates the salt to be hfT7jp2q

$/sDfNdP2e3OCxg2zGq1FK0 indicates the password hash to be /sDfNdP2e3OCxg2zGq1FK0




A common password cracking strategy is to bruteforce all possible passwords. This can be time-consuming and sometimes inefficient. Therefore, various "dictionary" of commonly used passwords from leaked sources have been used to speed up the process. However, in our case, the passwords are intentionally randomized so that the dictionary approach may not work well. Therefore, you are better off writing your bruteforce-style program to crack the password hashes. Note that there are existing tools that implement bruteforce password cracking on the Internet. You are NOT allowed to use them. You are, however, allowed to use the primitive hash functions such as hashlib.md5(string). Check out tutorials on how md5 password hashes are computed (with 1000 rounds of

primitive md5 hashes): https://www.vidarholen.net/contents/blog/?p=32. You may also learn (but not directly COPY) from reference implementations in various open source libraries.




Reference that explains the ins and outs of password hashing: https://crackstation.net/hashing-security.htm

Online tool that generates the password hash (for verification purposes): https://unix4lyfe.org/crypt/




To allow passwords cracked within reasonable amount of time. The passwords for team users are generated with less than or equal to 6 characters (all lowercase letters only). For the bonus user password, it is 8 characters exact (lowercase letters only).




Rules:

- If you use any shared machines to perform the password cracking, you are NOT allowed to interfere with other people's use of machines. You can be penalized in grades if the rule is violated (e.g., from complaints). On some CS servers, there are background processes that auto-kill applications that are overly aggressive in using the resources. The exact rule is defined by our IT admin. Please be aware.










Submission requirement:

- (4 points) Show the correct password for your team user.

- (4 points) Submit the following in a packaged file (zip or rar). 1) The source code. 2) The number of threads/processes is used. 3) The CPU model that your code is run on. 4) The throughput of password cracking, i.e., the number of candidate passwords tested per second.

- (2 bonus points) Show the correct password for the bonus user (do not giveaway/copy results across teams), as well as the throughput (if different from above).










After successfully completing this project, you can use the cracked password to log in to the server and obtain the instructions of project 2 and have a head start. The later projects are substantially more time-consuming and it is best that you complete project 1 as early as you can.