[145799] in cryptography@c2.net mail archive
Re: Merkle Signature Scheme is the most secure signature scheme possible
daemon@ATHENA.MIT.EDU (Ben Laurie)
Fri Sep 3 10:05:57 2010
Date: Fri, 03 Sep 2010 09:45:20 +0100
From: Ben Laurie <ben@links.org>
To: Zooko O'Whielacronx <zooko@zooko.com>
CC: Cryptography List <cryptography@metzdowd.com>,
Discussion of cryptography and related <cryptography@randombit.net>
In-Reply-To: <AANLkTimk1AsOUowrwg0v_LAOGymtuhk7kDhqPyqneDzL@mail.gmail.com>
On 01/09/2010 22:45, Zooko O'Whielacronx wrote:
> On Wed, Sep 1, 2010 at 2:55 PM, Ben Laurie <ben@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 majordomo@metzdowd.com
