Re: Hashed password secure?

From: Matthijs Hebly (heeb_at_iname.com)
Date: 07/05/04 

Date: Mon, 05 Jul 2004 16:41:06 GMT

Matthew Skala wrote:
> In article <Xs1Ec.33374$3N6.4061@amsnews05.chello.com>,
> Matthijs Hebly <heeb@iname.com> 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 bull***, 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
> 2^8 times.
>
> 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).
On modern computers this would be more like 2^18 times, and I'm sure
pretty soon this would go more in the direction of 2^24 times (a slower
hash function would bring this down again). So if he'd want to store his
dictionaries, he would have to use 2^18 times the diskspace compared to
just storing 1 dictionary that would go with one salt value. If he'd
want to not store his dictionaries, he'd have to try on average half his
dictionary (provided the password *is* actually in his dictionary...),
which would take 1 second per dictionary entry if his computer were the
same speed as the user's.

> 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.
That would be (2^16)/2 = 2^15 on average... Which would take half a
second. So where's the problem? What is the problem with having to wait
0.5 secs on average (1 sec max) if the password was entered correctly,
and 1 sec to get an error if the password was not entered correctly? The
user doesn't have to do any "work", just wait for max. 1 second. In one
day, how often do you enter a 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.
Don't agree. As I see it, the user does *not* suffer at all (what is 1
second?), the attacker on the other hand *does*, in having to build and
store a multitude of dictionaries, or having to try for a whole lot longer.

> 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,
Why is he *trying* salts if you just *give* it to him by storing them?

> whereas the defender was trying only one, so the defender suffers
> more from the change.
Where's the suffering? 1 second max., 0.5 on average. I see no suffering.

> 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,
Staying up to date with the hash function is *always* a good idea...

> because that will affect both parties by the same amount even when
> there's more than one password under consideration.

Thanx,

Matthijs.