Gareth Heyes Wrote:
-------------------------------------------------------
> @kogir
>
> How do you store per user salts? What happens when
> a new user is created? If the salts are stored in
> the database then I can see major problems with
> this method.
>
> I fail to understand why I'm missing the point
> please provide me with a link to a rainbow table
> that does MD5(MD5($password . RANDOMSALT)), you
> would need a pretty big table to store all that
> information.
===========
Random Salt
===========
I store random, per user salts in the database right next to the users' password hashes. This is effective even when the salts are known because any rainbow table an attacker creates will be valid only against a single user's password. The point of a salt is to force the attacker to brute force each user's password individually, not to keep them from brute forcing a single password.
For example, given two users, A and B, with passwords Pa and Pb, I'll produce two random salts, Sra and Srb. Using any hash algorithm I want, F(), I store password hashes Ha = F(Sra + Pa) and Hb = F(Srb + Pb) in the database for verification when authenticating A and B.
When a user A logs in, I look up the salt (Sra) and compute F(Sra + <provided password>). If F(Sra + <provided password>) matches what's in the database, the user is authenticated.
Computing a rainbow table for user A would require me to compute F(Sra + <password>) for all passwords I wish to precompute. This rainbow table would be useless in cracking user B's password because F(Sra + <password>) != F(Srb + <password>) for all values of <password>.
It's true that attacking a single user's password is only as hard as brute forcing a single password, but all the effort expended in brute forcing A's password is useless in brute forcing B's password.
===========
Static Salt
===========
Using a static salt, Ss, would result in hashes of the form F(Ss + <password>) being stored in the database. Ha would be F(Ss + Pa) and Hb would be F(Ss + Pb). No matter how random Ss is when you first generate it, it's not random when used to compute Ha and Hb. If Pa == Pb, then Ha == Hb, and a rainbow table attack is now useful. You can now find users with the same password hashes and crack them all at the same time.
This holds true even for F() = MD5(MD5(<password> + StaticSalt))
=======
Summary
=======
The only benefit a salt can provide is to force the attacker to treat each hash individually. Even if Ha and Hb match, if a random, per user, salt is used, then Pa and Pb won't match. Discovering Pa does not reveal Pb.
With resources like Aamzon S3 and EC2, for a few thousand dollars I can make a rainbow table that completely covers hashes for typical length passwords, given Ss and F(), in under a week. The mere fact that a rainbow table doesn't yet exist does not make static salts any less useless. The goal is to make creating such a table intractable.
It is possible to pick a hash function F() that is so computationally expensive that brute forcing a even a single user's password would be infeasible, but such functions are usually too burdensome to run on a web server handling reasonable traffic.
I hope this makes sense.
-kogir
