From: Dave Searles on
Arne Vajh�j wrote:
> Dave Searles wrote:
>> markspace wrote:
>>> Dave Searles wrote:
>>>>
>>>> It seems to me that if you have the hash and the salt, and know the
>>>> algorithm for convolving the password with the salt, then you can
>>>> still carry out a dictionary attack.
>>>
>>>
>>> A dictionary attack pre-computes the hash, and then just scans the
>>> password file for a simple string match. The salt defeats this,
>>> because each bit in the salt doubles the storage needed for the
>>> dictionary.
>>>
>>> <http://en.wikipedia.org/wiki/Salt_%28cryptography%29>
>>>
>>> You're right in that if the password itself is weak and could be
>>> guessed, then all bets are off.
>>
>> As Tom explained, the salt does not make any single password harder to
>> crack, but it does slow down an attack aimed at getting all (or the
>> first) dictionary-vulnerable password.
>>
>> I was thinking in terms of protecting a particular targeted account
>> (yours, say, or the superuser account), while you two were apparently
>> thinking more of protecting all of the accounts in some statistical
>> sense.
>
> [says I'm a liar]

Whaaat? Nonsense.

> The use of salt makes all dictionary attacks more difficult, because
> it invalidates pre-calculated dictionaries.

Moving the hashing of the dictionary out of the loop only occurs when
there's a loop (multiple passwords being attacked) to move it out of.
It's that move that salting makes impossible.
From: Arne Vajhøj on
Dave Searles wrote:
> Arne Vajh�j wrote:
>> Dave Searles wrote:
>>> markspace wrote:
>>>> Dave Searles wrote:
>>>>>
>>>>> It seems to me that if you have the hash and the salt, and know the
>>>>> algorithm for convolving the password with the salt, then you can
>>>>> still carry out a dictionary attack.
>>>>
>>>>
>>>> A dictionary attack pre-computes the hash, and then just scans the
>>>> password file for a simple string match. The salt defeats this,
>>>> because each bit in the salt doubles the storage needed for the
>>>> dictionary.
>>>>
>>>> <http://en.wikipedia.org/wiki/Salt_%28cryptography%29>
>>>>
>>>> You're right in that if the password itself is weak and could be
>>>> guessed, then all bets are off.
>>>
>>> As Tom explained, the salt does not make any single password harder
>>> to crack, but it does slow down an attack aimed at getting all (or
>>> the first) dictionary-vulnerable password.
>>>
>>> I was thinking in terms of protecting a particular targeted account
>>> (yours, say, or the superuser account), while you two were apparently
>>> thinking more of protecting all of the accounts in some statistical
>>> sense.
>>
>> No no no.
>
> Whaaat? Nonsense.

It is true.

>> The use of salt makes all dictionary attacks more difficult, because
>> it invalidates pre-calculated dictionaries.
>
> Moving the hashing of the dictionary out of the loop only occurs when
> there's a loop (multiple passwords being attacked) to move it out of.
> It's that move that salting makes impossible.

It is:

no salt =>

for username, hashedPassword in passwordFile:
word = lookup_in_internet_database(hashedPassword)
print username, word # pwned!

same salt for all users =>

for word in dictionary:
hashedWord = hash(salt, word)
for username, hashedPassword in passwordFile:
if (hashedPassword == hashedWord):
print username, word # pwned!

different salt for each user =>

for word in dictionary:
for username, salt, hashedPassword in passwordFile:
hashedWord = hash(word, salt)
if (hashedPassword == hashedWord):
print username, word # pwned!

Arne
From: Eric Sosman on
Arne Vajh�j wrote:
> Tom Anderson wrote:
>> On Mon, 28 Sep 2009, Mike Schilling wrote:
>>> Dave Searles wrote:
>>>> I still think the surest bet is to avoid using dictionary-attackable
>>>> passwords. :)
>>>
>>> Absolutely, which is why many environments require passwords to
>>> contain both letters and numbers.
>>
>> Which is absolutely not a good defence. "pa55w0rd" and "password1",
>> which are the kind of thing this rule usually engenders, are not a lot
>> more difficult to guess than "password" - it's a small constant-factor
>> increase in the amount of work a password cracker has to do.
>
> The effect is still exponential related to length.

Don't you mean "polynomial" instead of "exponential?"
The number of possible passwords of length N from an alphabet
of size R is exponential in N, but only polynomial in R.
Increasing from R to R+r gives polynomial, not exponential,
growth. To get exponential growth, lengthen the password from
N to N+n symbols.

--
Eric Sosman
esosman(a)ieee-dot-org.invalid
From: Arne Vajhøj on
Eric Sosman wrote:
> Arne Vajh�j wrote:
>> Tom Anderson wrote:
>>> On Mon, 28 Sep 2009, Mike Schilling wrote:
>>>> Dave Searles wrote:
>>>>> I still think the surest bet is to avoid using dictionary-attackable
>>>>> passwords. :)
>>>>
>>>> Absolutely, which is why many environments require passwords to
>>>> contain both letters and numbers.
>>>
>>> Which is absolutely not a good defence. "pa55w0rd" and "password1",
>>> which are the kind of thing this rule usually engenders, are not a
>>> lot more difficult to guess than "password" - it's a small
>>> constant-factor increase in the amount of work a password cracker has
>>> to do.
>>
>> The effect is still exponential related to length.
>
> Don't you mean "polynomial" instead of "exponential?"
> The number of possible passwords of length N from an alphabet
> of size R is exponential in N, but only polynomial in R.
> Increasing from R to R+r gives polynomial, not exponential,
> growth. To get exponential growth, lengthen the password from
> N to N+n symbols.

You are correct.

My mistake.

Arne
From: Lew on
Arne Vajhøj wrote:
>> [says I'm a liar]
>

Dave Searles wrote:
> Whaaat? Nonsense.
>

What is nonsense is to claim that Arne Vajhøj said you were a liar.
That's a lie; he did not say that, "Dave Searles". I realize this is
pointless to point out, but claiming that someone made a mistake is
not claiming that they lied. Claiming that someone made an incorrect
statement is not /ipso facto/ saying that they're a liar. This is
normal English, so presumably you knew that, therefore you lied when
you claimed that Arne Vajhøj said you were a liar. What he did was
claim that you were incorrect without any attribution of malice to you
at all.

It is certainly true that a person can speak in good faith, ergo not
lying, and still speak falsehood through ignorance, misunderstanding
or even typographical error. I know I've made many statements here in
this Usenet forum that other people have corrected. I knew they did
not accuse me of lying - the beauty of that is that I was able to
learn from the correction and obtain a better understanding. You
should try that, "Dave Searles", assuming you are humble enough to
admit that you still have something left to learn.

--
Lew