On Wed, Sep 1, 2010 at 2:55 PM, Ben Laurie <b...@links.org> wrote: >> >> Therefore, you would end up hashing your messages with a >> secure hash function to generate "message representatives" short >> enough to sign.
> Way behind the curve here, but this argument seems incorrect. Merkle > signatures rely on the properties of chained hash functions, whereas > RSA, for example, only needs a single iteration of the hash function to > be good. All digital signatures, including RSA and including the hash-based signatures that I am advocating, require a "message representative" which is a small fixed-length thing, and since your message is an arbitrarily large thing we need to use a compressing function, which we do today with Merkle-Damgård chaining and in the future with SHA-3 (which will probably have some mechanism that looks a little bit like a Merkle-Damgård chain if you squint at it just right). A Merkle-Damgård chain is definitely relying on the properties of chained "inner compression functions", and several practical and theoretical weaknesses of this reliance have been identified (length extension, herding, multi-collisions, entropy-loss). The Merkle Trees which are used in hash-based signatures don't seem obviously weaker than normal linear hashes and indeed seem stronger in at least some theoretical ways against collisions (they should not suffer from entropy-loss, for example). In addition, using a full hash function with initialization and finalization on larger inputs instead of a inner-compression-function on smaller inputs is almost certainly safer against preimage attacks. Oh, but there's the rub! The security of the message-representative depends on collision-resistance, but the security of the hash-based signature depends only on pre-image resistance! This is a vast gulf both practically and theoretically. Consider: MD5: collisions: seconds on your laptops; pre-images: perhaps in a hundred years if we make more progress [1] SHA-1: collisions: a year or two of great expense and effort; pre-images: perhaps never unless we have a breakthrough SHA-3-256: collisions: 2¹²⁸; pre-images: 2²⁵⁶ > 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. 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? Regards, Zooko [1] http://www.springerlink.com/content/d7pm142n58853467/ --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com