Prev: CFP DATA MINING 2010: new date - until 29 March 2010
Next: A link to a news on SSL
From: Joseph Ashwood on 25 Mar 2010 07:37
"bmearns" <mearns.b(a)gmail.com> wrote in message
news:2b040dc4-2fc0-430f-9ee1-00e9cd3893bf(a)v20g2000yqv.googlegroups.com...
> I'm performing a salted hash for generating multiple passphrases from
> a single password.
[...]
For instance, if the salt and
> password are of equal length, is it fair to say that the hash output
> is equally dependent on both of them? Does it matter what the entropy
> density of each is, or how those lengths compare to the length of the
> digest? Does any kind of vague concept of dependency even make sense
> in this context?

For this kind of approach it is worth thinking of a hash function as an
entropy distiller, it simply distills the entropy from the inputs into a
fixed size. In this case it is the apparent entropy, not the actual.

The salts have assumed near-0 zero entropy (to make this work it is
necessary to assume that it is not perfectly 0), the entropy of the password
is assumed to be significant, but less than the capacity of the hash.
Summing these, the entropy content of the final hash will be driven by the
password with the salt only functioning in a minimal way to change the
output.

Also Carsten is correct, lots of iterations, 10,000, 100,000, even a million
iterations. We can debate all day about the best way to do it, but we're
splitting hairs versus having the iterations.

Unless you're going to be pushing the limits of the hash function (billions
of iterations, huge lengths, etc), don't worry too much.
Joe

From: bmearns on 28 Mar 2010 13:59
On Mar 25, 7:37 am, "Joseph Ashwood" <ashw...(a)msn.com> wrote:
> "bmearns" <mearn...(a)gmail.com> wrote in message
>
> news:2b040dc4-2fc0-430f-9ee1-00e9cd3893bf(a)v20g2000yqv.googlegroups.com...> I'm performing a salted hash for generating multiple passphrases from
> > a single password.
>
> [...]
> For instance, if the salt and
>
> > password are of equal length, is it fair to say that the hash output
> > is equally dependent on both of them? Does it matter what the entropy
> > density of each is, or how those lengths compare to the length of the
> > digest? Does any kind of vague concept of dependency even make sense
> > in this context?
>
> For this kind of approach it is worth thinking of a hash function as an
> entropy distiller, it simply distills the entropy from the inputs into a
> fixed size. In this case it is the apparent entropy, not the actual.
>
> The salts have assumed near-0 zero entropy (to make this work it is
> necessary to assume that it is not perfectly 0), the entropy of the password
> is assumed to be significant, but less than the capacity of the hash.
> Summing these, the entropy content of the final hash will be driven by the
> password with the salt only functioning in a minimal way to change the
> output.
>
> Also Carsten is correct, lots of iterations, 10,000, 100,000, even a million
> iterations. We can debate all day about the best way to do it, but we're
> splitting hairs versus having the iterations.
>
> Unless you're going to be pushing the limits of the hash function (billions
> of iterations, huge lengths, etc), don't worry too much.
>                     Joe

Great! Thank you everyone for the helpful responses. I was trying to
come up with clever ways to balance out the "dependency", but it
sounds like just straight forward iterations is the best practical
approach.

-Brian
From: unruh on 28 Mar 2010 18:59
On 2010-03-28, bmearns <mearns.b(a)gmail.com> wrote:
> On Mar 25, 7:37?am, "Joseph Ashwood" <ashw...(a)msn.com> wrote:
>> "bmearns" <mearn...(a)gmail.com> wrote in message
>>
>> news:2b040dc4-2fc0-430f-9ee1-00e9cd3893bf(a)v20g2000yqv.googlegroups.com...> I'm performing a salted hash for generating multiple passphrases from
>> > a single password.
>>
>> [...]
>> For instance, if the salt and
>>
>> > password are of equal length, is it fair to say that the hash output
>> > is equally dependent on both of them? Does it matter what the entropy
>> > density of each is, or how those lengths compare to the length of the
>> > digest? Does any kind of vague concept of dependency even make sense
>> > in this context?
>>
>> For this kind of approach it is worth thinking of a hash function as an
>> entropy distiller, it simply distills the entropy from the inputs into a
>> fixed size. In this case it is the apparent entropy, not the actual.
>>
>> The salts have assumed near-0 zero entropy (to make this work it is
>> necessary to assume that it is not perfectly 0), the entropy of the password
>> is assumed to be significant, but less than the capacity of the hash.
>> Summing these, the entropy content of the final hash will be driven by the
>> password with the salt only functioning in a minimal way to change the
>> output.
>>
>> Also Carsten is correct, lots of iterations, 10,000, 100,000, even a million
>> iterations. We can debate all day about the best way to do it, but we're
>> splitting hairs versus having the iterations.
>>
>> Unless you're going to be pushing the limits of the hash function (billions
>> of iterations, huge lengths, etc), don't worry too much.
>> ? ? ? ? ? ? ? ? ? ? Joe
>
> Great! Thank you everyone for the helpful responses. I was trying to
> come up with clever ways to balance out the "dependency", but it
> sounds like just straight forward iterations is the best practical
> approach.

Each iteration will almost certainly decrease the entropy. If you start
with a number, each successive iteration will eventually settle down
into a loop. or converge to 0 entropy. By the birthday paradox, and assuming that the hash acts as
a random function, once you get of order sqrt(N) outputs, two of them
will be the same. If two are the same, then you have entered a loop. The
entropy of any element in that loop is basically the log of the size of
the loop, which is of order L/2, where L is the length of the hash
output. Ie, the entropy decreases until it settles down to 1/2 the
expected entropy.

outputs, two of those outputs will be the same.
>
> -Brian
From: Maaartin on 28 Mar 2010 20:25
On Mar 29, 12:59 am, unruh <un...(a)wormhole.physics.ubc.ca> wrote:
> Each iteration will almost certainly decrease the entropy. If you start
> with a number, each successive iteration will eventually settle down
> into a loop. or converge to 0 entropy.  By the birthday paradox, and assuming that the hash acts as
> a random function, once you get of order sqrt(N) outputs, two of them
> will be the same. If two are the same, then you have entered a loop.

IIUYC the problem happens after about sqrt(N) iterations with N=2**128
for the simplest hash in use - MD5. But 2**64 iterations is far beyond
being practical for password strengthening, isn't it? Additionally, as
the purpose of the iteration is to slow down the attacker, you can use
a 10 times slower hash and do 10 times less iterations. When using
SHA-512 you get N=2**4096 and rid of the problem, or am I wrong?

> The
> entropy of any element in that loop is basically the log of the size of
> the loop, which is of order L/2, where L is the length of the hash
> output. Ie, the entropy decreases until it settles down to 1/2 the
> expected entropy.

I was about to ask the question, but you gave me the answer already,
thank you.


Is there any reason against using some better iteration, I mean
instead of

key = hash(password + salt); manyTimes {key = hash(key);}

using something like

key = hash(password + salt); manyTimes {key = hash(key + password +
salt);}

or maybe (in order to get timings independent of the password length)

key0 = hash(password + salt); key = key0; manyTimes {key = hash(key +
key0);}

From: Maaartin on 28 Mar 2010 22:26
On Mar 29, 2:25 am, Maaartin <grajc...(a)seznam.cz> wrote:
> Additionally, as
> the purpose of the iteration is to slow down the attacker, you can use
> a 10 times slower hash and do 10 times less iterations. When using
> SHA-512 you get N=2**4096 and rid of the problem, or am I wrong?

For whatever reason, I assumed the output of SHA-512 to be 512 bytes
(not bits) long, which is wrong. However, with N=2**512 you - after
sqrt(N) iterations - get still enough entropy for AES-256.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: CFP DATA MINING 2010: new date - until 29 March 2010
Next: A link to a news on SSL