Re: Hashed password secure?

From: Matthew Skala (mskala_at_ansuz.sooke.bc.ca)
Date: 07/05/04 

Date: 4 Jul 2004 22:49:54 GMT

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 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
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). 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
consideration. 

-- 
Matthew Skala
mskala@ansuz.sooke.bc.ca                    Embrace and defend.
http://ansuz.sooke.bc.ca/

Relevant Pages

  • Re: Password scrambler program
    ... provide the string to salt it with) MD5 equivalent with the ability to ... password) is sent to a hash function and hashed multiple times - 1000 is ... and so not helping at all against some types of attack. ... might as well grab, for example, the keys from disk encryption ...
    (sci.crypt)
  • Re: Password scrambler program
    ... provide the string to salt it with) MD5 equivalent with the ability to ... password) is sent to a hash function and hashed multiple times - 1000 is ... is not a trivial problem if it's properly chosen, no matter ... and so not helping at all against some types of attack. ...
    (sci.crypt)
  • Re: Is this a secure key derivation function?
    ... If the password is close to the maximum length, then only part of the salt is used. ... Actually the version that introduces password every time is more secure. ... The race condition is most immediately worrisome, I've personally used race conditions on several ocassions to break security, usually it is used for privilege escalation, but it is just a variation of a timing attack which is never a good thing in cryptography. ... The lack of memory initialization has always been complex to use in an attack, but it is closely related to buffer overflow attacks. ...
    (sci.crypt)
  • Re: How good an encryption algorithm is this?
    ... Actually it's vitally important that the salt is different every time. ... but a one-way hash of the password). ... >>> attack (using my dictionary of plaintext trial passwords and the ... you need to perform this iteration only once. ...
    (microsoft.public.vc.language)
  • Re: How good an encryption algorithm is this?
    ... Actually it's vitally important that the salt is different every time. ... but a one-way hash of the password). ... >>> attack (using my dictionary of plaintext trial passwords and the ... you need to perform this iteration only once. ...
    (microsoft.public.dotnet.languages.csharp)