Rainbow Tables: How to defend against them??

Question

I recently obtained the l0pht-CD for windows and tried it out on my PC and It WORKS!!

http://2600hertz.wordpress.com/2009/12/22/100-windows-xp-vista-7-password-recovery/

• I have also read http://kestas.kuliukas.com/RainbowTables/

I'm designing a "Login-Simulator" that stores pwd-s in a similar manner. The current implementation will be vulnerable to the above attack. Plz could anyone illustrate (in as simple terms as possible), how to strengthen against such a rainbow tables attack.

MY GOAL : Build "Login-Simulator" to be as secure as possible. (Read Hacking Competition ;-) )

Thank You.

Answer 1

You should use bcrypt, which has been designed by professional cryptographers to do exactly what you're looking for.

In general, you should never invent your own encryption / hashing schemes.
Cryptography is extremely complicated, and you should stick to what has been proven to work.

However, the basic answer to your question is to add a random per-user salt, and switch to a slower hash.

Answer 2

Since a rainbow table is a series of precomputed hash chains for various passwords, it is easily foiled by adding a salt to the passwords. Because hash functions usually remove much of the local correspondence between input and output (that is, a small change in input produces large, seemingly unrelated changes in output), even a small salt will be immensely effective.

Best of all, the salt does not need to be secret for this to be effective; the rainbow table needs to be recomputed for all possible password-salt combinations.