Re: [Cfrg] Merkle trees [was Re: streamable AEAD construct for stored data?]

[Bill Cox <[e-mail]>]

On Sat, Nov 7, 2015 at 5:45 AM, Bryan Ford <[e-mail]> wrote:

> Hi Zooko,
>
> On Nov 4, 2015, at 11:01 AM, Zooko Wilcox-OHearn <[e-mail]>
> wrote:
>
> Preventing length-extension attack was a prime requirement for SHA-3,
> because users had sometimes interpreted "can produce a terminal node
> that has this data as input" as a proof of "knows this data". This
> resulted in security failures, for example against naive key-prefix
> MACs.
>
> Now, what if I give you the root of a Merkle Tree but withhold from
> you the data (the inputs to the leaves). Should you be able to
> generate a new Merkle Tree which has my Merkle Tree as one of its
> subtrees? Obviously not! That would be a length-extension attack.
> Sakura ¹ and BLAKE2 ² (designed after SHA-3) don't allow that.
>
>
> In at least some Merkle tree usage scenarios I would argue are
> “reasonable,” that is precisely what you want.  In particular, you
> sometimes want Merkle trees to “compose” cleanly, allowing large Merkle
> trees to be built from smaller Merkle trees whose (individual) creators
> didn’t necessarily know or care how big the large, composed Merkle tree
> would be.
>

For your use case of global time-stamping (which is super cool), you should
differentiate the stuff being timestamped (leaf data from clients) from the
internal nodes generated by followers, by using a different hash for nodes
and leaves.  Otherwise, it is not entirely clear, given a proof, what
exactly was timestamped.

You could use a keyed hash like Blake2, or a keyed wrapper like HMAC or
HKDF2.  However, just prepending one sequence for leaves, and another for
internal nodes should be enough.  This is a super-simple change that will
improve your time-stamp application's security.

Bill