Project #5, Rainbow Tables

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 function in search-table.c.

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.

Using the Rainbow Tables Package

You can generate new round keys for a 100-round rainbow table, then generate 10000 rows in that table, for salt mysalt, by running a command like

./gen-table -r 100 -e 10000 -g mysalt mykeyfile mytablefile

That will write the round keys to the file mykeyfile; you can use those round keys in subsequent calls to gen-table by omitting the -g argument.

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

./sort-table mytablefile

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

The 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 in search-table.c.

If you’d like to generate some (printable ASCII) password hashes for testing, you may use the hash-password utility; if you run

./hash-password mysalt CSE127!fun

the hash-password utility will hash the very secure password “CSE127!fun” using salt “mysalt” and print the resulting hash to standard output. (The result, incidentally, should be 66ec7e0cc94a13aec81787b6580ee3dd.)

The Password Search Space

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.

Modifying the Rainbow Table Implementation

Obviously, you will need to modify the rainbow table implementation in the project tarball to complete the two functions that have TODO sections.

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.

Navigation: CSE // CSE 127 // Project 5