Re: Hashed password secure?
From: Matthew Skala (mskala_at_ansuz.sooke.bc.ca)
Date: 4 Jul 2004 22:49:54 GMT
In article <Xs1Ec.33374$3N6.email@example.com>,
Matthijs Hebly <firstname.lastname@example.org> wrote:
>Is this b*sh*? I couldn't find anything on the internet on *NOT* storing
>salt-values. Why would one *store* the salt if it would take only 1
>second average to check whether a password is correct?
I wouldn't say bullshit, but I think it's a bad idea if you're protecting
more than one password.
Consider the way that a typical password hash attack program works. Let's
say "crack", the standard Unix-password attack tool. It's not targetting an
individual user's password - it's targetting an entire file of passwords, or
many files. So it starts out by splitting the input file into classes based on
the salt, and then it hashes the dictionary once for each unique salt value
in the input. If you and I happen to have the same salt value, then a
dictionary attack against my password can be combined with a dictionary
attack against yours.
Now, suppose there are 2^8 different salt values in the password file, in
the normal case, with stored salt. The legitimate verifier has to do one
hash operation to verify a password. The cracker has to hash the dictionary
Suppose we use your system with 16 bits of non-stored salt. There are,
again, 2^8 different salt values in the password file, but the attacker
doesn't know what they are. So the attacker has to hash the dictionary 2^16
times (2^8 times as much work as before) and then compare the results
against the entire password file instead of just one salt class (negligible
additional work there). The attacker's work has increased by a factor of
2^8. But what about the legitimate verifier? The legitimate verifier has
to do 2^16 hash operations to verify the password. You've increased the
legitimate verifier's work by a factor of 2^16 and the attacker's work by a
factor of only 2^8, so the gap between the two, which is a good way to
measure security, has actually *decreased* by a factor of 2^8. What's going
on is that you're forcing the attacker and the legitimate user to both try
all possible salt values - but the attacker was already trying a lot of salt
values, whereas the defender was trying only one, so the defender suffers
more from the change.
If you want to increase the attacker's work at the cost of also increasing
the legitimate verifier's work, you would do better to just switch to a new
hash function that takes longer to compute, because that will affect both
parties by the same amount even when there's more than one password under
-- Matthew Skala email@example.com Embrace and defend. http://ansuz.sooke.bc.ca/