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

David-Sarah Hopwood david-sarah at jacaranda.org
Thu Jul 29 15:18:24 EDT 2010


Nicolas Williams wrote:
> On Sat, Jun 12, 2010 at 10:21:51PM -0600, Zooko O'Whielacronx wrote:
>> http://tahoe-lafs.org/pipermail/tahoe-dev/2010-June/004439.html
> 
> There you ask how the Merkle Signature Scheme depends on collision
> resistance.  The authors of the paper you link to say that signature
> itself depends only on second-pre-image resistance, but that the Merkle
> hash tree used to cope with the one-time-use signature (by letting you
> group many one-time-use public keys) depends on collision resistance.
> 
> I believe it's fairly obvious that the hash tree part of MSS does depend
> on collision resistance: the tree node values are hashes of private keys
> (leaf nodes) or interior nodes in the tree (hashes of sequences of
> hashes of .. hashes of private keys), and the peer verifying a signature
> cannot validate those tree node values.  A collision attack on the hash
> tree's hash function would allow you to take a signature and claim it
> was made with someone else's key -- all you have to do is find one
> collision for a public key and its leaf node sibling(s).

This is not correct. To attack any of a given set of existing public keys,
you need to find an authentication path for which the verifier will compute
one of those keys at the root. There's no known way to do that just using
hash collisions, as far as I'm aware.

Note that finding two messages that yield the same signature under the
*attacker*'s chosen key, does not break the usual definition of security for
signature schemes (existential unforgeability under chosen message attack).

I gave my understanding of the answer to Zooko's question in a previous post:

>    Zooko asked in
> <http://allmydata.org/pipermail/tahoe-dev/2010-June/004439.html>,
>    why the original Merkle tree construction, [Merkle1987], can't be
>    proven secure (that is, to preserve the second preimage resistance
>    of the hash it is based on) without assuming that the hash is collision
>    resistant.
>
>    First, note that the applicable security property is the eSec variant
>    of second preimage resistance, since the input is not random as it
>    would have to be for the Sec or aSec variants. (In general, the
>    attacker chooses the inputs at the bottom level of the tree. Also,
>    the output of the hash is not random because that's not implied by
>    any of the properties studied in [RS2004], so neither is the input to
>    the next-higher level.)
>
>    So, we are looking for a tree hash that preserves eSec/TCR. Section 5.1
>    of [BR1997] explains why the Merkle-Damgård construction does not
>    preserve this property in the case of a linear hash. Basically, it's
>    because iterating the hash might result in violating the assumption
>    that the input to later iterations is independent of the seed. The
>    counterexample used to show this is completely contrived, but it's
>    enough to show that security is not preserved for an arbitrary eSec
>    compression function. The same counterexample also shows why the
>    Merkle tree construction (with the same seed used for all of the hash
>    applications) does not preserve eSec.
>
>    Note that eSec *is* preserved if we use independent seeds for each
>    level of the Merkle tree. All the hashes at the same level can use
>    the same key -- that gives the "TH" construction in section 5.4 of
>    [BR1997]. However, that would effectively multiply the seed size
>    by the number of levels. [...]


> [Merkle1987]  Ralph Merkle,
>               "A Digital Signature Based on a Conventional Encryption
>                Function,"
>               In proceedings of CRYPTO '87:
>               Lecture Notes In Computer Science Vol. 293, pp 369-378,
>               Springer-Verlag 1988.
>
<http://systems.cs.colorado.edu/grunwald/Classes/Fall2003-InformationStorage/Papers/merkle-tree.pdf>
>
> [BR1997]      Mihir Bellare and Phillip Rogaway,
>               "Collision-Resistant Hashing: Towards Making UOWHFs
>                Practical,"
>               July 17, 1997.
>               <http://cseweb.ucsd.edu/~mihir/papers/tcr-hash.html>
>               <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.79.6148>
>
> [RS2004]      Phillip Rogaway and Thomas Shrimpton,
>               "Cryptographic Hash-Function Basics: Definitions,
>                Implications, and Separations for Preimage Resistance,
>                Second-Preimage Resistance, and Collision Resistance,"
>               Full version, 2004.
>               <http://eprint.iacr.org/2004/035/>

-- 
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 292 bytes
Desc: OpenPGP digital signature
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20100729/18d7a13d/attachment.asc>


More information about the cryptography mailing list