Hash keys assigned: Tuesday, March 13th, 12:01 AM
Challenge hashes available: Thursday, March 15th, 12:01 AM (60 minutes max allowed to crack)
The goal of this project is to build a rainbow table implementation and to use it to crack passwords.
You may work on this project on any Unix machine, including OS X and Linux. Building rainbow tables is computationally intensive, so you may not want to do it inside a VM.
Your first task is to complete a rainbow table implementation
by filling in a function in
gen-table.c and another
A little after midnight on Tuesday morning, we will mail you a salt. You should then start building rainbow tables with this salt. (If you are working with a partner, you may use either of the two salt values you’re sent.)
Then, a little after midnight on Thursday morning, we will mail you a link to a file with password hashes. Once you retrieve this file, you will have one hour to crack as many as you can and submit the corresponding passwords for grading, along with the source of your rainbow table implementation. Regardless of when on Thursday you choose to download the password hashes, we must receive your solution no later than 11:59 PM that night.
We recommend that you not use late days on this assignment. If you would like to use late days, please contact your TAs to coordinate getting a new salt.
Start by reading this excellent introduction to rainbow tables.
If you want more details, you may refer to the 2003 paper introducing rainbow tables or a more detailed (and technical) 2008 followup.
We will be building our rainbow tables for the ECHO hash function, one of the functions submitted to NIST’s SHA-3 competition. The starter code includes the ECHO team’s reference implementation.
You can generate new round keys for a 100-round rainbow table,
then generate 10000 rows in that table, for salt
by running a command like
./gen-table -r 100 -e 10000 -g mysalt mykeyfile mytablefile
That will write the round keys to the file
you can use those round keys in subsequent calls to
by omitting the
The resulting table, in the file
mytablefile will not be
sorted, so it won’t yet be suitable for using for password cracking.
You may concatenate it with other tables built using the same key file
to obtain a single larger table.
To prepare the table for using in password cracking, you must sort it. Run a command like
This will rewrite the table to be sorted. (Sorting a table larger than the physical RAM on your machine is likely to be unpleasant.)
Once the table is sorted, you can use it to try to crack password hashes, with a command like
./search-table -r 100 mysalt mykeyfile mytablefile < myhashes
search-table command expects (printable ASCII)
password hashes, one per line, on standard input. It should output
any passwords it finds that match an input hash on standard output,
one per line.
As your tables get larger (and especially as you concatenate multiple
large tables) the probability that multiple rows have the same final
hash increases. If your search code doesn’t account for that
probability, you may find that searching in a combined table fails
to recover some passwords that would have been found in one of the
smaller constitutent tables. Keep that in mind when you are filling
If you’d like to generate some (printable ASCII) password
hashes for testing, you may use the
utility; if you run
./hash-password mysalt CSE127!fun
hash-password utility will hash the very secure
CSE127!fun” using salt
mysalt” and print the resulting hash to
standard output. (The result, incidentally, should be
For this assignment, we will restrict ourselves to passwords
of the form word1 punct num word2
and word1 num punct word2, where
the words come from the dictionary
zwords included in
the project download, punct is one of 16 punctuation symbols, and
num is a number between 0 and 3.
The search space of such passwords is relatively large, but much smaller than what can be cracked using rainbow tables, given access to more substantial computational resources than we assume CSE 127 students have easy access to. If you’d like a challenge, contact us about building rainbow tables for a larger password space instead.
Obviously, you will need to modify the rainbow table
implementation in the project tarball to complete the two
functions that have
You will want to read over the rest of the code (except the ECHO files, which you do not need to understand) to learn how it is put together.
Feel free to modify and optimize any or all parts of the implementation. The starter code was written for portability and readability rather than performance, and could certainly be sped up.
You must do your password cracking using the rainbow table implementation in the project tarball, though you may modify this implementation as you see fit. You must not use other rainbow table implementations.
You may use other implementations of the ECHO hash function, provided that you first get instructor approval.