[Discuss] salt question

[tmetro+blu at gmail.com (Tom Metro)]

Eric Chadbourne wrote:
> And don't quite understand this line:
> "Salts are normally stored along with the hashes. They are not secret."

The other responses have pretty much covered everything, except for a
few points.

First, a simple example:

A basic hashed password:

% echo monkey | sha1sum
744a9a056f145b86339221bb457aa57129f55bc2  -

A basic hashed password with salt:

% echo saltmonkey | sha1sum
a3a686f363fb197b9688f70a392992763ff42b14  -

(Yes, salt can literally be as simple as a concatenated string.)


> So if they are not secret what is the advantage if your site is
> exploited?

To guard against use of rainbow tables.


> Such as if the salt is stored in a config file couldn't the
> attacker utilize this with his rainbow tables?

A rainbow table is a database of precomputed hashes for common
passwords. Any alteration of the password prior to computing the hash
results in a different hash, which will no longer match the rainbow
table version. As long as your salt isn't something predictable, its
perfectly fine (for the original goal of salting) for it to be stored in
the same place as the password.


> Also I see in PHP crypt() you don't have to supply a salt.  How does
> that work?

Same idea as the first example above. An empty string is concatenated
(or the concatenation step is sipped).


> I have a log in system I wrote myself with sha1 but from everything I've
> been reading this seems inadequate.

Most hashing algorithms traditionally used for storing passwords were
designed for speed of execution, like SHA1, which is opposite of what
you want in a password hashing algorithm.

These algorithms are being replaced by computationally hard algorithms,
like you find in bcrypt[1] and others[2][3]. There are also "memory
hard" algorithms[4]. (Same idea, but they require a lot of memory rather
than a lot of CPU cycles.)

Because of the prevalence of salting and the ubiquity of high
performance GPUs and cloud computing clusters, rainbow tables have
fallen out of favor. Salting is still a good idea, but insufficient by
modern standards if used with a fast hash algorithm. (Salting is
integral to bcrypt.)

There are also some people experimenting with the idea of fragmenting
the password hash and storing it distributed among multiple servers. A
form of Secret sharing[5]. This way if one server is breached, the
attackers have not necessarily obtained the full hash.

1. http://en.wikipedia.org/wiki/Bcrypt
2. http://en.wikipedia.org/wiki/Password_cracking#Prevention
3. http://en.wikipedia.org/wiki/Key_stretching
4. http://en.wikipedia.org/wiki/Memory_bound_function
5. http://en.wikipedia.org/wiki/Secret_sharing

 -Tom

-- 
Tom Metro
Venture Logic, Newton, MA, USA
"Enterprise solutions through open source."
Professional Profile: http://tmetro.venturelogic.com/