Rainbow tables are dead

30th Jan 2017

Say "Rainbow tables" one more time

This is a public service announcement. It's 2017 and people are still referencing to rainbow tables, usually when talking about password salts.
That's not the real reason of salt usage; rainbow tables are long dead, let's find out why.

First of all, what's a "rainbow table"? Directly from the Wikipedia article:

A rainbow table is a precomputed table for reversing cryptographic hash functions, usually for cracking password hashes. Tables are usually used in recovering a plaintext password up to a certain length consisting of a limited set of characters. It is a practical example of a space/time trade-off, using less computer processing time and more storage than a brute-force attack which calculates a hash on every attempt, but more processing time and less storage than a simple lookup table with one entry per hash. Use of a key derivation function that employs a salt makes this attack infeasible.

What does it mean?

Instead of bruteforcing the whole keyspace with every character combination, we could create a massive lookup table, where with the hash as index referring to the plaintext password. In theory, once the table is ready, we can find the solution pretty fast.
In practice, that's not possible: the amount of space required would be enormous, that's why rainbow table were created. Put it in simple words, they are a reduced "indexed table" faster than a plain bruteforce attack.

So they are useful!

For God's sake, no! They used to be useful back in the old days, when computers where much slower and we had no GPU cracking.
Now they are simply anachronistic. Accordingly to this page, you need 52 Gb of space just to guess a 7 chars password and 460 Gb (!!!) for 8 chars one.
This is completely useless: cracking a 7-8 chars password is trivial and bruteforce should really be your last options.
First of all you can try some dictionary attack combined with ruling, then some mask attack and finally (if everything else fails), you can start thinking about pure bruteforcing.

Now I'm lost, why do we have the salt?

Salts are used to slow down password recovery in large sets of data.
Please consider the following example: we have 5 users and all of them set their passoword to foobar

The same password produces the same hash for each user. While cracking we simply have one single hash to find, which will give us the password of all five users.
So if our wordlist is made of 1 million of words, we have to create 1 million of hashes before exhausting all the candidates.

Let's see what happens when a salt is applied


As you can see, even if the same password is used we have 5 different hashes. If we are still using our 1 million wordlist, now we have to create 5 million of hashes before reaching the end.


While cracking, time is your main constraint.
Every password can be recovered, it's just a matter on how long you want to wait: it could be a couple of minutes or until the sun explodes. Yes, salts will force the attacker to rebuild the entire rainbow table from scratch, but their main scope is to slow down the entire process.


Blog Comments powered by Disqus.