On 01/09/2010 22:45, Zooko O'Whielacronx wrote: > On Wed, Sep 1, 2010 at 2:55 PM, Ben Laurie <b...@links.org> wrote: >> Or, to put it another way, in order to show that a Merkle signature is >> at least as good as any other, then you'll first have to show that an >> iterated hash is at least as secure as a non-iterated hash (which seems >> like a hard problem, since it isn't). > > I'm not sure that I agree with you that security of a hash function > used once on an arbitrarily large message is likely to be better than > security of a hash function used a few times iteratively on its own > outputs.
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). So, on that basis alone, I reject the "most secure possible" argument. > But regardless of that, I think the fair comparison here is: > > ... show that an iterated hash is more likely to have preimage > resistance than a non-iterated hash is to have collision-resistance. > > And I think it is quite clear that for any real hash function such as > MD5, SHA-1, Tiger, Ripemd, SHA-2, and the SHA-3 candidates that this > does hold! > > What do you think of that argument? I think I've failed to understand why you thing collisions are not a problem for Merkle trees. Also, regardless, you are now talking probabilities and so a claim of "most secure possible" still doesn't apply. Merkle trees, probably the best signature in the world? :-) Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.links.org/ "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com