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

[Bryan Ford <[e-mail]>]

On Nov 7, 2015, at 6:53 PM, Bill Cox <[e-mail]> wrote:
> On Sat, Nov 7, 2015 at 5:45 AM, Bryan Ford <[e-mail] <mailto:[e-mail]>> wrote:
> Hi Zooko,
> 
>> On Nov 4, 2015, at 11:01 AM, Zooko Wilcox-OHearn <[e-mail] <mailto:[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.

Indeed, cleanly distinguishing the semantic difference between leaves and internal nodes seems worthwhile and easily doable even in situations like these where we want trees to be composable.  We will still want clients to be able to submit either “leaf hashes” or “subtree hashes” for timestamping, the latter case allowing any client to build a tree of his own (or perhaps reuse one previously timestamped by some other timeline) and effectively get a new “collective timestamp” all at once on everything in the submitted subtree (without the client ever having to transmit the subtree itself).  But the semantic difference between those two types of “submissions” could be easily distinguished via a flag parameter submitted along with the hash or nonce to be timestamped.

B

> 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