Merkle Signature Scheme is the most secure signature scheme possible for general-purpose use

[Zooko O'Whielacronx]

On Wed, Sep 1, 2010 at 2:55 PM, Ben Laurie <ben at 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 majordomo at metzdowd.com