Rainbow Tables

Rainbow tables are a clever strategy to discover the plain text string from a hash generated by a Cryptographic Hash Algorithms. These hashes are "one-way" and can not be decrypted. However, they operate on the principle that the same inputs return the same outputs, and rainbow tables make use of that fact. They primarily affect the security of password hashing.

It takes a long time and a lot of computer processing effort to guess the correct password using a Brute Force Attack, and then an attacker would need to start over for the next password. Instead, attackers spend time and effort on encrypting millions of strings and saving each string with the resulting hash in a database table. This is what is known as a rainbow table. Once constructed, a rainbow table can be searched for a matching hash to look up the original input.

The "pre-computing" process still requires a lot of work, but the work can be shared between many computers and the resulting rainbow table is re-usable. It provides a very fast future reference for cracking passwords. Attackers can also improve their results by hashing and storing dictionary words and common passwords first before moving on to hashing random strings.

For rainbow tables to be useful, the encrypted string must be known. They are not helpful in blindly guessing a password. Attackers often gain access to thousands of encrypted passwords in a stolen database and then use rainbow tables to look up 80-90% of the passwords in only a few hours. For most algorithms, a brute force approach to cracking the same number of passwords would take billions of years.

There are many sources online for downloading rainbow tables, most frequently for the MD5 and SHA-1 algorithms.


Counter-measures

Salts are the best counter-measure against rainbow tables. Adding a custom string to the plain text input before encryption changes the output string. As long as the same custom string is added before encryption, the results will still match for password authentication. However, a rainbow table will be ineffective. The output string could still match an entry in the rainbow table, but if an attacker tried to login with the associated string, it would not be the correct password.

The bcrypt algorithm also discourages rainbow tables through the use of its cost parameter. The cost makes bcrypt hashing slower than MD5 or SHA-1, making it more difficult to create rainbow tables. In addition, each cost setting (typically a number 8-20) changes all of the results. It is possible to create rainbow tables for all the cost settings from 8 to 20 but it would require much more pre-computing, and higher cost values add significant time to each calculation. For this reason, rainbow tables are uncommon for bcrypt.

Fork me on GitHub