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

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

 

Rainbow Tables – Part 1 (Introduction)

This is Part 1 of a five part series:

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

In January, I took the SANS Security Essentials (401) class at SANS West.  In the class, we briefly covered the concept of rainbow tables. Rainbow tables are (superficially) just password lookup tables: if you know the encrypted  password, you can look it up in the table and get the unencrypted password.  (The word ‘superficially’  there is critical – rainbow tables are far more interesting than simple lookup tables.)

One of the evening sessions (after the boot camp session) featured Ed Skoudis talking about penetration testing.  He also talked about rainbow tables.  What really caught my attention was his discussion of chains to vastly reduce the size of the tables.  The chains provide a clever way to trade off table size at the cost of some processing time.  I just had to understand the details, and I didn’t have the patience to wait until some day in the future when I might take Ed’s Pen Testing class.  I cornered Ed at the bar on the last night, asked how he would recommend learning them, and he pointed me to Wikipedia.

The wikipedia article is great, but a bit tough to read for someone new to the concept.  Fortunately, the article refers to another article, How Rainbow Tables Work, which is a bit easier.  It also is a good article, and the two were all I needed to help me build some samples of my own in order to really understand the concepts.

In this series of posts, I will attempt to provide an even easier introduction to rainbow tables.  I hope that the posts will help you understand the other articles, and appreciate the beauty of the approach.

I’ve broken the discussion into six parts, so that you can skip any bits that are already familiar to you.  This introduction is Part 1. Part 2 briefly talks about encryption and introduces the concept of hashes. Part 3 looks at some really simple hashing algorithms, including the one used for the examples here. Part 4 goes into reduction functions.  Finally, Part 5 explains rainbow tables and chains.  If you understand that password encryption uses hashes and are familar with common hashes like MD5 and SHA-1, you can probably jump right to Part 5, and then read the other parts if you want to fill in any gaps.

These posts contain simple examples that you can work through yourself with a spreadsheet.  I have built one for you, which you can view using Google Docs or download to Excel.  I encourage you to play with the values in the spreadsheet  if you really want to get a deep understanding of how each part works.

If you’ve never used Google Docs before, it has the equivalent of Excel’s tabs.  At the bottom, you’ll see links that will take you to the different pages.  You also can select File – Export – .xls to export it into an Excel Spreadsheet, and you’ll find all the tabs there.

Enjoy!

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