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.`

http://eprint.iacr.org/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