Reduction in entropy by repeated hashing

[Caecilius]

I've heard that performing many iterations of a hash will reduce the
entropy of the output, so hash(hash(hash(m))) would have less entopy
than hash(m). And I wonder what effect this has on iterated hashes as
they are used in password hashing algorithms such as Ulrich Drepper's
SHA2-based algorithm[1].

I wonder if the reduction in entopy would ever become significant
enough that at some point adding more interations would start
weakening the mechanism rather than strenghtening it.

Does anyone have any details or pointers to information about this
entropy reduction?

[1] http://www.akkadia.org/drepper/sha-crypt.html

[unruh]

On 2013-01-11, Caecilius <nos...@spamless.invalid> wrote:
> I've heard that performing many iterations of a hash will reduce the
> entropy of the output, so hash(hash(hash(m))) would have less entopy
> than hash(m). And I wonder what effect this has on iterated hashes as
> they are used in password hashing algorithms such as Ulrich Drepper's
> SHA2-based algorithm[1].

Yes, but it is fairly slow, and the hash is usually used in a case where
the entropy of the key is much less than the ln of the size of the hash
anyway. Ie, the chances of getting two likely passwords hashing to the
same result is already small.

>
> I wonder if the reduction in entopy would ever become significant
> enough that at some point adding more interations would start
> weakening the mechanism rather than strenghtening it.

If you repeated the hash often enough you would probably enter into a
loop of large size.

[Caecilius]

On Fri, 11 Jan 2013 21:03:06 GMT, unruh <un...@invalid.ca> wrote:
>Yes, but it is fairly slow, and the hash is usually used in a case where
>the entropy of the key is much less than the ln of the size of the hash
>anyway. Ie, the chances of getting two likely passwords hashing to the
>same result is already small.

Thanks for the explanation. I had expected that the entropy reduction
would be small, and you're right about the entropy of the key
(password) being much less than that of the hash so no need to worry
about collisions.

I'm using a SHA2-512-based hash, which has about eight times the
amount of entropy that a good password has, so a moderate decrease in
entopy is not an issue.

I'm using tens of thousands of iterations at the moment, and can
imagine going up to hundreds of thousands in a few years time as
processing speeds improve. But I expect that by the time I need
millions of iterations there will be a new algorithm.

So the question is: is an iteration count of a few hundred thousand
going to reduce the entropy significantly? My guess is it won't matter
in my application as SHA2-512 has vastly more bits than I need, so I'd
need to lose a lot of entopy before it became a problem.

[Karl-Uwe Frank]

On 12.01.13 16:03, Caecilius wrote:

> I'm using tens of thousands of iterations at the moment, and can
> imagine going up to hundreds of thousands in a few years time as
> processing speeds improve. But I expect that by the time I need
> millions of iterations there will be a new algorithm.
>

Instead of increasing the amount of hashing rounds it might be better
using a different approach which prevent the usage of paralleled GPU for
brute force attacks. Such solutions are offered by bcrypt and Scrypt,
which significantly slow down any brute force attempt.

Cheers,
Karl-Uwe

[unruh]

On 2013-01-12, Caecilius <nos...@spamless.invalid> wrote:
> On Fri, 11 Jan 2013 21:03:06 GMT, unruh <un...@invalid.ca> wrote:
>>Yes, but it is fairly slow, and the hash is usually used in a case where
>>the entropy of the key is much less than the ln of the size of the hash
>>anyway. Ie, the chances of getting two likely passwords hashing to the
>>same result is already small.
>
> Thanks for the explanation. I had expected that the entropy reduction
> would be small, and you're right about the entropy of the key
> (password) being much less than that of the hash so no need to worry
> about collisions.
>
> I'm using a SHA2-512-based hash, which has about eight times the
> amount of entropy that a good password has, so a moderate decrease in
> entopy is not an issue.
>
> I'm using tens of thousands of iterations at the moment, and can
> imagine going up to hundreds of thousands in a few years time as
> processing speeds improve. But I expect that by the time I need
> millions of iterations there will be a new algorithm.

In the design of the password hashing algorithms, they do not simply
iterate a hash, but also put in lots of time wasting things like
shuffles etc. Their purpose is to ensure that one cannot find some
simple algorithm which will allow one to do say 10 shaa hashes at once
in about the same time as one. Ie, which the design goal of most crypto
hash algorithms is to do them as quickly as possible, the design goal of
a password hash is to do it as slowly as possible. Thus you might be
better to find some slow hashes (which may not be crypto grade, but are
slow) with the crypto grade hashes, simply to slow things down rather
than simply concatenating the same hash many times.

[Mark Wooding]

Caecilius <nos...@spamless.invalid> writes:

> I've heard that performing many iterations of a hash will reduce the
> entropy of the output, so hash(hash(hash(m))) would have less entopy
> than hash(m). And I wonder what effect this has on iterated hashes as
> they are used in password hashing algorithms such as Ulrich Drepper's
> SHA2-based algorithm[1].

I'm not going to do a full analysis on this scheme now, but I'm not
really very impressed by it. Suffice to say, it looks like it wasn't
designed by a cryptographer. The biggest error, I think, is in failing
to delimit the salt string from the password properly when constructing
`digest A'.

The entropy loss effect isn't going to be very pronounced here, since a
thing fairly closely related to the password (the `byte sequence P' in
the specification) is mixed into every round.

> I wonder if the reduction in entopy would ever become significant
> enough that at some point adding more interations would start
> weakening the mechanism rather than strenghtening it.

No. If SHA2 works like a random function, then the entropy loss here is
independent of the number of rounds.

> Does anyone have any details or pointers to information about this
> entropy reduction?

http://www.cs.berkeley.edu/~daw/my-posts/hash-iteration looks relevant.

-- [mdw]

[Caecilius]

On Sun, 13 Jan 2013 02:15:59 +0000, Mark Wooding
<m...@distorted.org.uk> wrote:

>I'm not going to do a full analysis on this scheme now, but I'm not
>really very impressed by it. Suffice to say, it looks like it wasn't
>designed by a cryptographer

I had the same feeling. Crypto code designed by someone who's not a
cryptographer often doesn't survive close scrutiny.

Drepper says that the code has been "reviewed from security teams at
HP, IBM, Red Hat, and Sun" , and their names are listed at the top of
the specification document here:
http://www.akkadia.org/drepper/SHA-crypt.txt

>No. If SHA2 works like a random function, then the entropy loss here is
>independent of the number of rounds.

I don't understand this statement. Doesn't the reference you've given
below support the idea that iterative hashing will reduce the entropy
of the final output?

I use the term "iterations" rather than "rounds" to avoid confusion
with rounds inside the hash function, but I think we're talking about
the same thing.

>http://www.cs.berkeley.edu/~daw/my-posts/hash-iteration looks relevant.

Thank you. That's a very interesting post, and one that I'd not seen
before.

[Mark Wooding]

Caecilius <nos...@spamless.invalid> writes:

> On Sun, 13 Jan 2013 02:15:59 +0000, Mark Wooding
> <m...@distorted.org.uk> wrote:
> >No. If SHA2 works like a random function, then the entropy loss here is
> >independent of the number of rounds.
>
> I don't understand this statement. Doesn't the reference you've given
> below support the idea that iterative hashing will reduce the entropy
> of the final output?

Yes, it does -- but it concerns itself strictly with old-fashioned
output-feedback style iteration H(H(...(H(x))...)). The basic problem
here is that H is noninjective.

Let's write D (`digests' -- it turns out my first choice of a curly H
works poorly in ASCII) for the codomain of H. Then H(D) is (almost
certainly) strictly smaller than D itself, and so on for H^i(D).

We can imagine a diagram (which I'm not going to sketch in ASCII). On
the left, put a big column containing a cell for each string in D, and
colour each cell green. To its right, after a gap, put another column,
the same height. For each x in D, find the cell for x in the leftmost
column, and draw an arrow from it to the cell for H(x) in the one to its
right. Colour each cell in the column to the right green if it has an
arrow pointing to it; colour the other cells red. Now draw another
column, further over to the right, and draw arrows only from the green
cells y in the middle column to H(y) in the new column. Again, colour
cells with arrows pointing to them green, and colour the other ones
red. Carry on doing this until you get bored.

Now you can take a bunch of starting cells on the left and follow the
arrows along. As you progress rightwards, you'll see the paths merging.
And once they've merged, nothing can pull them apart again.
Essentially, what's happening is that the noninjectivity of H is
forgetting the distinctions between the starting points. And that's why
you lose entropy.

But that's not quite what's happening with the SHA2 crypt.. It's closer
to something like

H(x || H(... (H(x || H(x)))...))

(but unnecessarily complicated because Drepper doesn't really understand
his tools). We're feeding the number we first thought of into every
iteration.

Let's fiddle with the notation a bit, and write H_x(y) = H(x || y).
Then we're looking at H_x(H_x(...(H_x(H(x)))...)), which looks kind of
similar to what we had before. We can try to draw a diagram, like we
did for the simple case above, but it doesn't work the same way. What
goes wrong with it is that the arrows don't all mean the same thing.
We've effectively invented a separate function for each cell on the
left, tagged with its starting point. So we'd need to label each arrow
we draw. And, most significantly, draw an outbound arrow from a cell
for /each/ inbound arrow -- and they can point to different cells in the
next column over. Now, just because two paths appear to merge at some
point, nothing prevents them from diverging again later -- and they
almost certainly will.

There are still things which can go wrong with this kind of iteration.
The obvious one is that a particular iteration can fall into a cycle --
but we don't expect that to happen until we've done a truly silly number
of iterations, so we can ignore that effect.

> I use the term "iterations" rather than "rounds" to avoid confusion
> with rounds inside the hash function, but I think we're talking about
> the same thing.

We are. Sorry for being confusing. I've tried to use your terminology
here.

-- [mdw]

[unruh]

On 2013-01-13, Mark Wooding <m...@distorted.org.uk> wrote:
> Caecilius <nos...@spamless.invalid> writes:
>
>> I've heard that performing many iterations of a hash will reduce the
>> entropy of the output, so hash(hash(hash(m))) would have less entopy
>> than hash(m). And I wonder what effect this has on iterated hashes as
>> they are used in password hashing algorithms such as Ulrich Drepper's
>> SHA2-based algorithm[1].
>
> I'm not going to do a full analysis on this scheme now, but I'm not
> really very impressed by it. Suffice to say, it looks like it wasn't
> designed by a cryptographer. The biggest error, I think, is in failing
> to delimit the salt string from the password properly when constructing
> `digest A'.
>
> The entropy loss effect isn't going to be very pronounced here, since a
> thing fairly closely related to the password (the `byte sequence P' in
> the specification) is mixed into every round.
>
>> I wonder if the reduction in entopy would ever become significant
>> enough that at some point adding more interations would start
>> weakening the mechanism rather than strenghtening it.
>
> No. If SHA2 works like a random function, then the entropy loss here is
> independent of the number of rounds.

Untrue. If it works like a random function then each additional running
will decrease the entropy until, probably, the hash enters a cycle.
There are probably lots of such cycles, some longer than others.
Lets take the following hash on 5 bit numbers
H(x)=((2x+1)^7+x^5) mod 32
which should be a reasonable hash, after 10 iterations, the only two
values are 20 and 25. Ie, the entropy has gone from 5 bits to 1 bit.



Then,

[Mark Wooding]

unruh <un...@invalid.ca> writes:

> Untrue. If it works like a random function then each additional running
> will decrease the entropy until, probably, the hash enters a cycle.
> There are probably lots of such cycles, some longer than others.
> Lets take the following hash on 5 bit numbers
> H(x)=((2x+1)^7+x^5) mod 32
> which should be a reasonable hash, after 10 iterations, the only two
> values are 20 and 25. Ie, the entropy has gone from 5 bits to 1 bit.

Well done. Now read what I actually wrote, and the specification of the
Crypt SHA2 function again, and try again.

-- [mdw]

[unruh]

On 2013-01-13, Mark Wooding <m...@distorted.org.uk> wrote:

Adding in something simply makes a different hash. Ie, there is a
function
H(x) which is a many to one function. That function, whether it is
obtained by combining something with some original hash, or is that
original hash, IS a hash which you are itterating. I happend to pick one
particular hash. You claim that your hash function works better. Prove
it.

[Peter Fairbrother]

On 14/01/13 00:05, unruh wrote:
> On 2013-01-13, Mark Wooding<m...@distorted.org.uk> wrote:
>> unruh<un...@invalid.ca> writes:
>>
>>> Untrue. If it works like a random function then each additional running
>>> will decrease the entropy until, probably, the hash enters a cycle.
>>> There are probably lots of such cycles, some longer than others.
>>> Lets take the following hash on 5 bit numbers
>>> H(x)=((2x+1)^7+x^5) mod 32
>>> which should be a reasonable hash, after 10 iterations, the only two
>>> values are 20 and 25. Ie, the entropy has gone from 5 bits to 1 bit.
>>
>> Well done. Now read what I actually wrote, and the specification of the
>> Crypt SHA2 function again, and try again.
>
> Adding in something simply makes a different hash. Ie, there is a
> function
> H(x) which is a many to one function. That function, whether it is
> obtained by combining something with some original hash, or is that

> original hash, IS a hash which you are iterating. I happened to pick one

> particular hash. You claim that your hash function works better. Prove
> it.
>

No, Mark says that there is a *different* hash function for each
starting point (as the starting point is reused in each iteration).

Which means that if/when a cycle is reached, it is a *different* cycle
for each starting point.


(assuming the hashes work like random functions, there might be a single
matching pair of cycles of length 1 - but matching pairs of cycles of
longer length are so improbable they can be ignored)



-- Peter Fairbrother

[Bryan]

Mark Wooding wrote:

> Caecilius writes:
> > I've heard that performing many iterations of a hash will reduce the
> > entropy of the output, so hash(hash(hash(m))) would have less entopy
> > than hash(m).

[...]

> > Does anyone have any details or pointers to information about this
> > entropy reduction?
>
> http://www.cs.berkeley.edu/~daw/my-posts/hash-iterationlooks relevant.

I have to disagree with David Wagner's analysis there. He seemed to
assume that each iteration is independent, as if we use a new random
function every time. That's different from the case he states, "we've
got a random function F," repeatedly applied.

Iterated application of a single random function will fall into
cycles. Given a reasonably large domain, there's no significant chance
that all the inputs will ever, no matter how many iterations, all
induce the same output.

Iterated application of different random functions will eventually map
all inputs to the same output. It's not a practical problem, but
that's that what happens in the limit as the number of applications
goes to infinity.

I'm on about a tangential and theoretical point there. Mark Wooding
answered correctly, and that Wagner guy is a strong candidate for
sci.crypt's all time best contributor. I just don't think Wagner's
analysis from 1998 is entirely correct.

[Jeffrey Goldberg]

I know I'm late to this discussion, but ...

On 2013-01-13, Caecilius <nos...@spamless.invalid> wrote:

> Drepper says that the code has been "reviewed from security teams at
> HP, IBM, Red Hat, and Sun" , and their names are listed at the top of
> the specification document here:
> http://www.akkadia.org/drepper/SHA-crypt.txt

Somehow this is managed to evade the attention of the people I know
who study these things.

As Bill Unruh correctly pointed out, if you just compose a hash, you
will eventually hit a loop, where the result of round R is the same
as the result of round Q and you will just loop forever among Q, R,
and all of the things in between.

Assuming that the hash in a prf, then you can calculate your chances
of hitting a loop using Birthday Paradox math on the number of
rounds and the number of possible hash results. So this probably
isn't a real concern for when the number of rounds is just a few
thousands, but it does mean that the system doesn't scale and only
have a maximum number of rounds that should ever be used.

What is completely unanswered for me as I look at that document is
why they think that that scheme is better than PBKDF2, bcrypt, or
scrypt.

Now there are problems with each of those, but a quick inspection
makes me think that Drepper's scheme not only fails to improve upon
existing alternatives, but is inferior to them.

(I'm not sure how widely known scrypt was at the time that SHA-crypt
was proposed, but PBKDF2 had been a standard for a while.)

Depending on needs, if you have to use something available today, my
first recommendation would be scrypt. It is designed to be resistent
to GPU optimization and requires memory as well as time, thus
constraining paralellized attacks. It's drawbacks are that it is new
(so there is less review and fewer libraries that already implement
it for you), and that it can be hard to figure out the appropriate
parameters for your needs.

After that, I would suggest PBKDF2, but using HMAC-SHA-512 as its
prf. Although PBKDF2 wasn't designed to resist GPU optimization,
using a "wide" hash gives it some of that resistence.

bcrypt has the honor of being the first among these. I don't really
know enough about it, but I know that the developers of PBKDF2 and
scrypt were fully aware of bcyrpt, and so that we can hope that the
newer ones are at least as well designed.

PBKDF2, probably because it has been standardized, has been the
best studied, but even then that study has proved insufficient.
There is a design bug discovered in April which, under some very
limited circumstances, means that the attacker only has to perform
half as many "rounds" as the defender.

You can read about my sad experience in learning this. I'm the
"Defender" in this case.

http://blog.agilebits.com/2013/04/16/1password-hashcat-strong-master-passwords/

Also the implementation in OpenSSL fails to use an optimization
which means that if the Defender uses OpenSSL and the attacker uses
an optimized algorithm, then the attacker can use half of the number
of hash compressions as the Defender. This is also discussed in that
article.

For those who are interested in discussion and progress toward
building better password hashing schemes, please take a look at this
project

https://password-hashing.net/

and in particular at the Password Hashing Competition.

I'm sure that everyone here understands that increasing the number
of iterations of such a scheme can only get you so far. The
"strength" of the password hash goes up linearly with the number of
iterations, and it does so at a cost for the legitimate processor.
Consider if you are a large service, authenticating a large number
of clients per second. But the "strenth" gain should (under most
circumstances) increase exponentially with the length of the
password.

But while everyone here undersands that, I've found that when
discussing PBKDF2 with the public, many people want to see the
number of iterations increased even though they could get much more
bang for the buck by making their passwords stronger.

Cheers,

-j

--
Jeffrey Goldberg http://www.goldmark.org/jeff/
I rarely read top-posted, over-quoting or HTML postings.
Reply-To address is valid.