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

[Jack Lloyd]

On Fri, Sep 03, 2010 at 09:45:20AM +0100, Ben Laurie wrote:
> 
> 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).

A recent result relevant to this is

"Practical consequences of the aberration of narrow-pipe hash designs
from ideal random functions", Klima and Gligoroski
(http://eprint.iacr.org/2010/384)

Which shows that narrow-pipe designs have a huge null space for
messages which are exactly as big as the compression function input
size. For instance hashing inputs that are multiples of 512 bits,
SHA-256 will only produce about 63% of the possible 2^256
outputs. This could be quite relevant to a Merkle scheme since
typically the input will be a set of hash outputs; if the internal
block size and the output length are not coprime, one would easily
encounter this limitation. It could probably be hacked around by using
padding on the inputs (eg the input to each Merkle hash is N subtree
hashes plus as many zero bytes as required to make the input length a
prime number of bytes), but that definitely sets of some bogosity
alarms in my mind.

One point I am uncertain on is if wide-pipe hashes like Blue Midnight
Wish or SHA-384 suffer the same levels of entropy loss as narrow-pipe
designs (outside of the case described in the referenced paper, which
is specific to narrow pipes).

-Jack

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com