Rainbow tables are dead
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.
user1:14758f1afd44c09b7992073ccf00b43d user2:14758f1afd44c09b7992073ccf00b43d user3:14758f1afd44c09b7992073ccf00b43d user4:14758f1afd44c09b7992073ccf00b43d user5:14758f1afd44c09b7992073ccf00b43d
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
user1:123:9cc0b57f6ac46685677554a83bdf8776 user2:456:5608fe118f7271ea7fc65275957bc0ab user3:789:1ccb417f798ab2825d3c96b91d037535 user4:asd:7f01af3960b179532705b6df794df304 user5:qwe:62e3e7465cf2f6600b07c9b354ebfc5e
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.