A Rainbow Table Attack is an attack that makes use of something called a pre-computed rainbow table. A rainbow table is a large database that contains a large number of a hash function’s inputs and corresponding outputs. A rainbow table makes brute forcing a password hash much easier, by removing the most computationally complicated part of a brute force – performing the hash function itself. With all of the values already computed, it’s simplified to just a simple search-and-compare operation on the table.
With rainbow tables, you are comparing a table of known inputs and outputs to a bunch of unknown outputs. If there’s a match, you know for certain that the hash function returns that output for it’s corresponding input in the table. A large portion of the security of the hash (the fact that the hash function is not an instant operation, and requires some amount of computational power, and therefore time, to perform) is bypassed with rainbow tables, meaning that if you’re lucky, you’ll find some matches.
However, rainbow tables do have their disadvantages. If the hash you’re trying to break is not in your table, you’re not going to find the result, period. You’re limited to the table that you use, and how that table is created is another challenge entirely. Because rainbow tables have to be made by someone, at some point someone had to generate all of the hashes in the table – likely a very expensive operation for larger, more useful tables. Rainbow tables are also limited by their size – for the speed you gain by not having to compute each hash, you now have to store a significant amount of data – often more than a hard-drive’s worth.
For a short period of time, rainbow tables were actually an effective way of cracking passwords. With a big enough table (and a big enough database of potential hashes) the chances of finding some matches were quite likely – mainly because of the hash algorithm used (in it’s peak, MD5) and also because of common hashes that circulated the web (such as the hash of very common passwords). However, as the popularity of less secure hashing algorithms fell, and as password salting became a more common practice, rainbow tables have fallen out of common use.