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
Advertisements