Rainbow Tables – Part 2 (Encryption and Hashes)

This is Part 2 of a five part series:

1. Introduction
2. Encryption and Hashes (you are here)
3. Simple Hashes and Collisions
4. Reduction Functions
5. Rainbow Tables and Chains

1. Addendum

As I mentioned in the first post of this series, rainbow tables are used to find a password if you know the encrypted password.

Passwords typically are (or should be) encrypted with a one-way encryption algorithm. This type of encryption is known as a hash.  With a hash, there is no algorithm that can be applied to the encrypted password to determine the unencrypted password.  There are only two ways to determine the unencrypted password:

• keep trying passwords until you find the right one (brute force)
• in advance, create a list of passwords and their encrypted results.  This is known as a lookup table.  Such a table can be huge, but is very simple to use and is fast.  Rainbow tables are a compromise.  They consume less space, but require more processing.  Compared with brute force, they still can be very fast (unless the password is poor and can be guessed immediately).

To understand rainbow tables, you need to be comfortable with hashes.  Most experienced computer users are at least somewhat familiar with MD-5 hashes, which are often used as a checksum to validate that a downloaded file was not corrupted in-flight. MD-5 is known to be vulnerable, but it makes a fine checksum.  SHA-1 is a more secure hash.

The rainbow table explanations I cited before (wikipedia and kuliukas) both use MD-5 for their example hashes.  While MD-5 is well-known and is easily available, it is difficult to calculate an MD-5 hash within Excel.  Because Excel makes a great platform for experimenting with data and tables to learn a concept, I found some simpler hash functions that I’ll use for the examples here.  These hashes would be terrible for real encryption, but they work well for creating a simple, understandable rainbow table in Excel.  We’ll look at those hash algorithms in Part 3.

If you’re not comfortable with hashes, these simple algorithms will also provide a gentle introduction to the concept.

The examples in the other articles use character strings for their passwords to hash.  To keep things simple, my examples will stick to encrypting numbers between 0 and 99.  After all, in a computer, characters are all represented by numbers anyway, so we’re just skipping the step of translating a character into ASCII or Unicode.

Let’s go look at these simple hashes in Part 3.

1. Introduction
2. Encryption and Hashes
3. Simple Hashes and Collisions (next)
4. Reduction Functions
5. Rainbow Tables and Chains