Hacker News new | comments | show | ask | jobs | submit login

Salting the password should defeat the rainbow table, right?



Using a salt would require the attacker to include an entry for each possible salt for each password candidate. If the salt is only one bit, this makes the attack take twice as long (or, requires tables twice as large). If the salt sufficiently long it makes the attack infeasible.


Thanks for this question! The answer is complicated. :D

Let me tell you first why it does not help! In order to build a rainbow table, we must be able to build a lookup table (since they're just compressed lookup tables). But a lookup table is basically a brute force attack on a certain category of passwords! So, if your password would fall to a modern rainbow table, it can be brute-forced by modern computational clusters. Salting does not change that. Intrinsically the password is no more secure than it was before. (To make it more secure, use bcrypt, scrypt, or pbkdf2. Seriously, even PHP has pbkdf2 nowadays, you have no excuse[1].)

Now let me mitigate that naysaying a bit. If you salt every password with a random 12-character base64 string, you do indeed prevent building a lookup table for the database. And that's actually not bad. Security is best measured not in bits or in operations, but in dollars. If the value of the information is much smaller than the cost to crack it, you'll defeat a rational attacker.

Rainbow tables can be built in a highly parallel way, with attackers pooling their resources and attacking multiple systems. So it will generally cost more to brute-force a password than it will to break it with a rainbow table: the rainbow table lookup can be done with one CPU; but brute forcing may require a botnet or lots of GPUs.

[1] Okay, there is one excuse: you might want to be able to do password administration from phpMyAdmin using only built-in MySQL functions. If you are stuck in this particular case the REPEAT() and SHA1 commands can have a similar effect:

    create function pw(salt char(12), password varchar(255)) returns char(40) 
        return sha1(repeat(concat(salt, sha1(password)), 100000));
but if you're not in this case, use something better.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: