[tahoe-dev] 100-year digital signatures Re: signed Introducer messages, server-selection work

[Zooko O'Whielacronx]

On Thu, Jun 10, 2010 at 11:56 PM, Zooko O'Whielacronx <zookog at gmail.com> wrote:
> On the other hand, I'm super-excited about the Merkle-Signature-Scheme that David-Sarah reminded us of recently...
>
> http://www.cdc.informatik.tu-darmstadt.de/~dahmen/papers/hashbasedcrypto.pdf
>
> https://www.minicrypt.cdc.informatik.tu-darmstadt.de/reports/reports/REDBP08.pdf

As David-Sarah has pointed out, a Merkle Signature Scheme is at least
as secure as *any* other digital signature scheme, even in the
long-term—even if attackers have quantum computers and the knowledge
of how to solve math problems that we don't know how to solve today.

If you had some other digital signature scheme (even, for the sake of
argument, a post-quantum digital signature scheme with some sort of
beautiful reduction from some classic math problem), then you would
probably start wanting to digitally sign messages larger than the few
hundreds of bits that the digital signature algorithm natively
handles. Therefore, you would end up hashing your messages with a
secure hash function to generate "message representatives" short
enough to sign. Therefore, your system will actually depend on both
the security of the digital signature scheme *and* the security of a
hash function. With a Merkle Signature Scheme you rely on just the
security of a hash function, so there is one less thing that can go
wrong. That's why a Merkle Signature Scheme is at least as secure as
the best digital signature scheme that you can imagine. :-)

Something else that pleases me greatly about Merkle Signature Schemes
they are easy to learn for a normal engineer who understands the
property of "one-wayness" a.k.a. "pre-image resistance" in a secure
hash function. You don't have to learn any fancy math concepts to
understand how they work.

Another thing that I like about it is that we already use Merkle Trees
in several ways in Tahoe-LAFS for ensuring integrity of data, so if we
also used Merkle Trees for digital signatures then we would get to
re-use code, optimizations, and engineering knowledge.


Now it seems to me that the security of a Merkle Signature Scheme
relies on the second-preimage-resistance of the underlying hash
function. However, cryptographers appear to agree with each other that
it actually relies on the collision-resistance of the hash function.

This is a big difference! It is a big difference in theory—an ideal
secure hash function which emits K-bit outputs has K-bit
second-preimage-resistance but only K/2-bit collision-resistance.

It is an even bigger difference in practice—so far every real secure
hash function (such as MD4, MD5, SHA-1, Tiger, SHA-256) which has been
cryptanalyzed has shown a lot more propensity to fail at collision
resistance than to fail at second-preimage-resistance. Of those hash
functions that I named, you can generate collisions for MD4 or MD5 in
a few seconds on your laptop, and some people or organizations can
probably generate SHA-1 collisions if they really want to, but nobody
is anywhere close to generating a second-preimage for any of those
algorithms in the forseeable future. (The state of the art for
generating second-preimages on MD4 is to do 2¹²⁸ precomputations,
storing results in a 2⁸⁰ storage table, then you can generate
second-preimages after that for "only" 2⁶⁹ computations per
second-preimage. See what I mean? There's just no comparison—so
far—between the real-world difficulty of collisions and the real-world
difficulty of second-preimages.)

Anyway, as I said it seems obvious to *me* that a Merkle Signature
Scheme will be secure as long as the underlying hash function has
second-preimage-resistance, but cryptographers appear to think that
the underlying hash function needs to exhibit the much stronger
property of collision-resistance before a Merkle Signature Scheme will
be secure. Here is a paper which makes this claim and furthermore
claims that their tweak to a Merkle Signature Scheme improves things
so that it requires only second-preimage-resistance from the
underlying hash function:

http://pubgrid.tahoe-lafs.org/file/URI%3ACHK%3Ajfh3rs3lfzc6bocahmany5vteu%3A4v3wk352d5bjrnwa4roxvwg5iav3bvs2hqxlhp5tylqmg2rfiqlq%3A3%3A10%3A309460/@@named=/Dahmen_etal-Digital_Signatures_Out_of_Second-Preimage_Resistant_Hash_Functions.pdf

I don't really understand why their tweak is needed.


Regards,

Zooko