CSE 539: Applied Cryptography

Project 3, Due date: Oct 24

Rainbow Table Attack

Groups

This project is to be done in groups of TWO. This requirement will be enforced.

Purpose

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.

Objectives

        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

 

Project Description

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.

Directions

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.

NOTE: Brute force cracking will always work. Rainbow table cracking will be faster if your reversal function and dictionary word choice are appropriate.

Password hashes:

19fbc7c1

7e1d96fd

88df723c

3974cffc

8f6bb61b

8e564270

655ca818

58712b2b

97e75d32

14928501

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.