Re: Hashed password secure?

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

Date: 8 Jul 2004 23:38:15 GMT

In article <CwfGc.19401$qK.18431@amsnews02.chello.com>,
Matthijs Hebly <heeb@iname.com> wrote:
>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

One second is 1000 times one millisecond. You seem to be asserting that
small amounts of computer time are equal to zero. Whether the user notices
it isn't the point - you still have to count it when you're doing a security
analysis, else you get meaningless answers.

>> 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?

Because he's attacking more than one password at once, and there are
multiple distinct salt values in the password file. The real-life attacker
isn't attacking a password; he is attacking a password file. He'll encrypt
the dictionary for each of the salt values that occurs in the password file.
I recommend you download and take a look at the "crack" utility - it works
just the way I describe, and there's a section in the documentation
explaining why it works this way.

You make the attacker try all possible salt values instead of just the
several stored in the file. You make the legitimate verifier try all
possible salt values instead of just the one stored for that one password.
If you don't like my use of the word "try" for cases where the values to be
used are known, substitute "hash the dictionary using". The work still has
to be done no matter what you call it. Your scheme increases the work for
both parties, but it increases the work MORE for the legitimate verifier
than it does for the attacker. (By a factor equal to the "several" from the
first sentence of this paragraph.) Thus the gap between legitimate verifier
and attacker decreases under your scheme. It would be better to increase
the gap, or at least keep it the same - as you can do by using other
techniques instead of yours.

>Where's the suffering? 1 second max., 0.5 on average. I see no suffering.

If your computer time has no value, then your adversary's computer time also
has no value, so he can afford to brute-force your scheme no matter how many
secret bits you have. You *must* place some kind of value on computer time
for security analysis to be meaningful at all; you're not allowed to say "it
doesn't count because it's small"; and with a nonzero value on computer
time, decreasing the gap between the adversary's resource requirements and
the legitimate user's resource requirements is a bad thing. 

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