A Rainbow Table is a more space efficient mechanism for storing pre-computed known passwords. It does this through a mechanism known as hash chaining, where passwords are connected through the use of reduction functions, which simply take a hash value, and produce any valid element of the password space.
For this assignment, you will write a C++ program that will produce a valid Rainbow Table file.
For this assignment, you will be creating a Rainbow Table to break passwords of length 6, where every character is known to be lowercase alphabetic. Towards that end, you will need to define 3 reduction functions, and use these reduction function in conjunction with the MD5 hash algorithm provided in lecture 16.
You are required to define files called reductions.h and
reductions.cpp.
These files are going to house your 3 reduction functions.
Your 3 functions must be named reduction_1,
reduction_2, and reduction_3. They should
follow the following template:
char* reduction_1(char* hashcode);
Remember, reduction functions are a function r: X → Y, where
Once you have your reduction functions defined, you can start worrying about reading in a password dictionary file. This file will be of the following format:
aaaaaa aaaaab aaaaac aaaaad aaaaae ...
Where each line contains one 6 character lowercase alphabetic string, which represents the start of some hash chain we want to include in the rainbow table.
To complete this assignment, you must take each line of the pre-determined password dictionary, and compute the hash chain using MD5 and your reductions. Essentially, you must compute:
reduction_3(md5_hash(reduction_2(md5_hash(reduction_1(md5_hash(password))))))
For every line in the pre-determined dictionary.
Your program will output a rainbow table text file of the following format:
aaaaaa csqqqq aaaaab qaysay aaaaac qqqsac aaaaad aacyya aaaaae qaqsqc ...
Using your set of reduction functions from above. The first part of each line is exactly the original password, as stored in the pre-determined dictionary. The second part of each line is the result of the above hash chaining algorithm. These two segments should be separated by a single space, and each line should contain a single one of these pairs.
Write a C++ program that takes a single command line argument: a file
name of the form filename.txt. You can assume that any
provided filename will be of this format, with the extension ".txt".
This file is the specified pre-determined password dictionary you
will use to generate the full rainbow table.
Your program should write a file (not using file redirection) called
filename.rbw It should be the same file name, just
with a ".rbw" extension. This file should be of the format
specified above.
I should be able to execute your program as follows:
$ ./build_rainbow input_file.txt $ ls … build_rainbow input_file.rbw input_file.txt Makefile README reductions.cpp reductions.h … $
Keep in mind, you are required to have the two reductions files, as specified above. I need these functions in these files, named in such a specific way to facilitate easy testing of your code. Programs that do not adhere to this naming standard will not be graded!
A portion of your grade (up to 10%, depending on the performance of the class as a whole) will be determined by how many passwords your rainbow table can crack using my program on this dictionary input file.
You must submit a tar file that extracts all of your code into a
directory called assignment3. You should also include
a README file and a Makefile to build your
program.
This assignment is due Thursday, November 14th by the beginning of class. You must write this program in C++. Other languages will not be graded. You should follow all typical code conventions, which can be found at CPSC 120 course website. Specifically you should avoid memory leaks and magic numbers, and include Pre and Post conditions for all defined functions. Submissions will be made through cseval.roanoke.edu.