CSE 539: Applied Cryptography
Project 3, Due date: Oct 24
Rainbow Table Attack
This project is to be done in groups of TWO. This requirement will be enforced.
Many organizations secure user credentials using a hash generated from the password, rather storing than the password in plain text. Using hash algorithms in this way adds layers of security that make it difficult to guess or reverse-engineer a passwordóbut not impossible. In this project, you will create a rainbow table and use it to decrypt secured information and reflect on the strengths and weaknesses of the approach.
● Write a program that can brute force a password using its hash (the hashing method is provided in hash.zip)
● Decrypt hashed data using a rainbow table attack
● Combine a dictionary and rainbow table attack to decrypt hashed data
● Describe the strengths and shortcomings of a rainbow table attack for decrypting a list of encrypted data
Typically, every user-credentials table will not store the password as plain text, but as a hash generated from the password. Passwords hashses can also be salted. For this project we will assume UN-salted passwords.
Even with hashing, it is still possible to brute force the hashing algorithm to generate a match with any entry. Though brute forcing works, the time it takes to hash every attempt makes it less efficient than approaches like the dictionary attack and rainbow table attack. Rainbow tables offer a space-time tradeoff, using less processing time and more storage than a brute-force attack.
You are provided with a hash.zip file that contains one C program hash.c, along with md5.h, which uses MD-5 routines. The hash.c program takes as an input a password that is exactly four characters long, where each character is from [a-z][A-Z][0-9]. It then converts the four characters to a 32-bit integer (using the ASCII codes) and computes a 32-bit hash and prints the hash in HEX format.
1. Write a program that takes a hash of a password and uses brute force to get the password. Note that there are 624 = 14,776,336 different passwords.
2. Generate a rainbow table. To create a rainbow table, you need a 4-character dictionary, a reversal function, and you must choose the number of words in the dictionary and the length of the chain. All these are left up to you.
3. Use the rainbow table to find (crack) a password from a password hash. Once you can do it, try the hashes from the list below.
Submission Directions for Project Deliverables
Submit a short report that explains your process for this project, data about the size of your rainbow table, the time taken to brute force, and the time taken to use the rainbow table. Discuss any shortcomings you found, such as passwords that could not be cracked using one method or the other.
Keep it short. Upload to Canvas (.doc, .pdf). Put both names on the document but upload it only once.