QotW #9: What are Rainbow Tables and how are they used?

2011-09-09 by . 0 comments

Post to Twitter

This week’s question, asked by @AviD, turned out to have subtle implications that even experienced security professionals may not have been aware of.

A quick bit of background:

With all the furore about passwords, most companies and individuals know they should have strong passwords in place, and many use system enforced password complexity rules (eg 8 characters, with at least 1 number and 1 special character) but how could a company actually audit password strength.

John the Ripper was a pretty good tool for this – it would brute force or use a dictionary attack on password hashes, and if it broke them quickly they were weak. If they lasted longer they were stronger (broadly speaking)

So far so good, but what if you are a security professional emulating an attacker to assess controls? You could run the brute forcer for a while, but this isn’t what an attacker will do – maths has provided much faster ways to get passwords:

Hash Tables and Rainbow Tables

Hash Tables are exactly as the name sounds – tables of hashes generated from every possible password in the space you want, for example a table of all DES crypt hashes for unsalted alphanumeric passwords 8 characters or less, along with the password. If you manage to get hold of the password hashes from the target you simply match them with the hashes in this table, and if the passwords are in the table you win – the password is there (excluding the relatively small possibility of hash collisions – which for most security purposes is irrelevant as you can still use the wrong password if its hash matches the correct one). The main problem with Hash tables is that they get very big very quickly, which means you need a lot of storage space, and an efficient table lookup over this space.

Which is where Rainbow Tables come in. @Crunge‘s answer provides excellent detail in relatively simple language to describe the combination of hashing function, reduction function and the mechanism by which chains of these can lead to an efficient way to search for passwords that are longer or more complex than those that lend themselves well to a hash table.

In fact @Crunge’s conclusion is:

Hash tables are good for common passwords, Rainbow Tables are good for tough passwords. The best approach would be to recover as many passwords as possible using hash tables and/or conventional cracking with a dictionary of the top N passwords. For those that remain, use Rainbow Tables.

@Mark Davidson points us in the direction of resources. You can either generate the rainbow tables yourself using an application like RainbowCrack or you can download them from sources like The Shmoo GroupFree Rainbow Tables project website, Ophcrackproject and many other places depending on what type of hashes you need tables for.

Now from a defence perspective, what do you need to know? 

Two things:

Longer passwords are still stronger against attack, but be aware that if they are too long then users may not be able to remember them. (Correct Horse Battery Staple!)

Salt and Pepper@Rory McCune describes salt and pepper in this answer:

A simple and effective defence that most password hashing functions provide now is salting – the addition of a per user “salt” value stored in the database along with the hashed password. It isn’t intended to be secret but is used to slow down the brute force process and to make rainbow tables impractical to use.  Another add-on is what is called a “pepper” value. This was just another random string but was the same for all users and stored with the application code as opposed to in the database. the theory here is that in some circumstances the database may be compromised but the application code is not, and in those cases this could improve the security. It does, however, introduce problems if there are multiple applications using the same password database.

Filed under Password

Comments are closed.