On 09/03/2010 03:45 AM, Ben Laurie wrote:

That's the whole point - a hash function used on an arbitrary message
produces one of its possible outputs. Feed that hash back in and it
produces one of a subset of its possible outputs. Each time you do this,
you lose a little entropy (I can't remember how much, but I do remember
David Wagner explaining it to me when I discovered this for myself quite
a few years ago).

I found this to be interesting:
Danilo Gligoroski, Vlastimil Klima: Practical consequences of the aberration of narrow-pipe hash designs from ideal random functions, IACR eprint, Report 2010/384, pdf.

The theoretical loss is -log2(1/e) = about 0.66 bits of entropy per
log2(N additional iterations).

This assumes that there is no systematic correlation between the hash input and the calculation of the output, which is not really a good assumption with the MD's and SHA's in current use. They accept, process, and output vectors of 32- or 64-bit words, even preserving their order to some extent. So it would seem reasonable to expect that to the extent that these actual functions differed from an ideal random function they could easily have the type of systematic bias which would be amplified through repeated iteration.

I played with some simulations with randomly-generated mappings, the observed value would at times wander over 1.0 BoE/log2 N.

It seems like this entropy loss could be largely eliminated by hashing the previous two intermediate results on each iteration instead of just one. But this basically amounts to widening the data path, so perhaps it would be cheating for the purposes of this discussion.

- Marsh

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com

Reply via email to