Monday, October 20, 2008

The Limits of Rainbow Tables

In a standard offline password cracking attack you have a hash that you are trying to crack, (for example 7c6a180b36896a0a8c02787eeafb0e4c), and you need to guess the password that generated it, (in the above case it would be 'password1'). To do this you make a lot of guesses, hash them and then compare the guess's hash to the hash you are trying to crack. If they match, you have "cracked" the password.

What this means is that you often spend a majority of your time generating hashes. Since the MD5 hash of 'password1' will always hash to 7c6a180b36896a0a8c02787eeafb0e4c though, some smart people thought it would be a great idea to make all our guesses, hash them, and then save the results. That way when we want to crack a password, we just do a lookup on our table of precomputed hashes.

A defense against this is to use a password "salt" which is a random value added to the password before it is hashed. For example if you salted the password 'password1' with the salt '122342' the resulting password hash would be cff2402abb06e3015d70619a9310930b. If everyone uses a different salt, precomputed hashes do not work. It's a simple solution, but unfortunately from what I've seen with the disclosed password lists we deal with, very few people actually use salts.

Now the above method of saving passwords is called a "Hash Lookup Table". They work really well, but for the most part are very unpopular because they can grow to an enormous size. Even a simple hash lookup table can be several terabytes large. To solve this problem though an algorithm was developed to dramatically shrink the size of these Hash Lookup Tables by a factor of several thousand, (or more). Lookup tables generated this way are called "Rainbow Tables" and they are extremely popular in password cracking. That being said, you rarely get anything for free, and they have some severe shortcomings compared to traditional Hash Lokup Tables.

So yah, all the above was a long introduction to the meat of this post. I just wanted to talk about some of the tradeoffs between choosing Rainbow Tables vs. Hash Lookup Tables. As disk space gets cheaper and if people continue to avoid using salts, I think it will be important as a community to be able to weigh the merits of the two so we can focus on the best approach to spend our free CPU cycles generating.

Rainbow Tables Pluses:

  1. Takes up much, much less disk space than Hash Lookup Tables
  2. Nothing else, but I want to stress, point #1 is really important

Rainbow Tables Minuses:

  1. Rainbow tables usually take much longer to crack an individual password than a Hash Lookup Table. The more you compress a rainbow table, the longer it takes.
  2. It takes a Rainbow table twice as much time to crack two passwords as it takes to crack one password. While this generally applies to Hash Lookup Tables as well, (depends on your search algorithm), it is much worse with a Rainbow Table attack due to point #1. In fact, if you have several thousand passwords to audit, it can actually be faster to do traditional password cracking, (where you generate all the hashes), instead of using a Rainbow Table.
  3. When you create Rainbow Tables, you do it by randomly generating guesses in a repeatable fashion. What this means is that you are not guaranteed to have a password guess in your Rainbow Table. For example, if you generate a Rainbow Table that contains all words of length 8, it might not include the word 'password'. With a Hash Lookup Table you don't have that problem
  4. As a side note to point #3, Rainbow Tables take much longer to create than Hash Lookup Tables because you end up generating and hashing many duplicate guesses to increase the probability of covering the entire keyspace. If it takes you a week to brute-force a keyspace, it would probably take you several months to generate a Rainbow Table that does the same thing.
  5. It's trivial to add new guesses to a hash lookup table, while with Rainbow Tables it is much more complicated.

In short, Rainbow Tables are not perfect, but they are convenient since they can be used by people who don't have several hundred terabytes of free diskspace to spare. For smaller keyspaces though, (for example, a list of the most popular passwords), Hash Lookup Tables can be very useful.

No comments: