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

From: Ben Laurie <[email-masked]>
Date: Sun, 01 Nov 2015 21:47:48 +0000

On Sat, 31 Oct 2015 at 19:36 Taylor R Campbell <[email-masked]>
wrote:

> Tahoe-LAFS uses a different function for internal nodes vs leaves, but
> otherwise no differences (e.g., no difference between height-1 and
> height-2 internal nodes), by prepending a tag to the input of SHA256d:
> x |---> SHA256(SHA256(x)).  In particular, it is something like:
>
> Tahoe-Merkle(a || b) =
>     SHA256d('internal' || SHA256d('leaf' || a) || SHA256d('leaf' || a))
>

FWIW, Certificate Transparency also uses this construction, only with 0x00
for 'leaf" and 0x01 for 'internal'.

>
> This avoids the trivial second-preimage attack, enables deduplication,
> and allows receivers to incrementally verify paths from a signed root
> to leaves.  (SHA256d avoids concerns with standard Merkle-Damgard
> length-extension attacks.)  But I'm not aware of any formal analysis
> of this construction.
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Bryan Ford <[email-masked]>
Date: Mon, 2 Nov 2015 10:12:02 +0900

+1 on the proposition that defining a standard for structure and representation of Merkle trees seems like a useful and worthwhile potential activity for CFRG.

In addition to defining basic Merkle tree structure while avoiding common pitfalls (such as the leaf-vs-internal-node indistinguishability problem), it would seem useful as well to define a common structure and representation for inclusion proofs and related objects commonly derived from Merkle trees.

Question for further thought: beyond basic hash-based Merkle trees, would it be worth considering constant-space alternatives for some of the functions Merkle trees commonly serve such as inclusion proofs?  With pairing-based crypto or cryptographic accumulators, for example, we can get small constant-space Merkle inclusion proofs instead of the O(log N)-size required with hash-based Merkle trees.  This space savings of course comes with a fairly substantial computation cost, but in some cases this tradeoff might be justified.  I don’t have strong feelings one way or another about this at the moment - hash-based Merkle trees and inclusion proofs may well be “good enough” for most purposes - but perhaps exploring constant-space approaches would be worthwhile even if only to add diversity to the “crypto toolkit” that’s effectively usable for Internet protocols.

B

> On Nov 1, 2015, at 4:36 AM, Taylor R Campbell <[email-masked]> wrote:
> 
>   Date: Fri, 30 Oct 2015 14:28:10 -0700
>   From: Adam Langley <[email-masked]>
> 
>   On Fri, Oct 30, 2015 at 11:47 AM, Andy Lutomirski <[email-masked]> wrote:
>> As far as I know, everyone thinks they know how to do a Merkle tree
>> for things like this, but there doesn't seem to be a credible
>> standard, and there are at least two modern examples of doing it
>> wrong: Amazon's Glacier hash and (unless it changed) Bittorrent's new
>> Merkle tree.
> 
>   Do you have references for either of these two issues? I wasn't aware of them.
> 
> The naive approach of computing
> 
> Naive-Merkle-SHA256(a || b) = SHA256(SHA256(a) || SHA256(b))
> 
> lends itself to the trivial second-preimage attack
> 
> Naive-Merkle-SHA256(a || b) = Naive-Merkle-SHA256(SHA256(a) || SHA256(b))
> 
> provided the leaves are >=64 bytes so that SHA256(a) || SHA256(b)
> makes up a single leaf.  Both the Amazon Glacier and the BitTorrent
> Merkle trees that Andy cited use this naive approach.
> 
> Sakura and Blake2's family of Merkle tree constructions, which tweak
> the underlying hash function for each distinct depth, offset, tree
> fanout, and other parameters, are adequate for the purposes of signing
> a monolithic document, as dkg was originally asking for, but are a
> little unsatisfying for other applications, such as deduplicated
> storage.
> 
> In particular, for deduplication, in order to store a || c as well as
> a || b || c.  we would like the Merkle tree of the first object to be
> a function of H(a) and H(c), and that of the second object to be a
> function of H(a), H(b), and H(c), for a fixed hash function H.
> 
> But Sakura and Blake2 both use a different function for each internal
> and leaf node, indicating its depth and its offset from the start of
> the message -- which works for fixed-width edits to a disk image, as
> the Blake2 specification suggests, but breaks down in the case of
> insertions or deletions.
>

---

From: Watson Ladd <[email-masked]>
Date: Sun, 1 Nov 2015 20:52:24 -0500

> Question for further thought: beyond basic hash-based Merkle trees, would it be worth considering constant-space alternatives for some of the functions Merkle trees commonly serve such as inclusion…

Accumulators tend to have issues with trusted parameters. RSA UFOs are
gargantuan. I don't know about pairing based approaches to
accumulators.

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Bryan Ford <[email-masked]>
Date: Mon, 2 Nov 2015 10:57:11 +0900

> gargantuan. I don't know about pairing based approaches to

Indeed, I don’t think the RSA-based approaches are highly practical and wouldn’t suggest that route.  It was the pairing-based approaches I had in mind, which do seem likely to be fairly practical - though I admit I haven’t actually used or carefully evaluated them yet.

B

---

From: Paul Lambert <[email-masked]>
Date: Mon, 2 Nov 2015 17:56:14 +0000

Tahoe-Merkle(a || b) =

FWIW, Certificate Transparency also uses this construction, only with 0x00 for 'leaf" and 0x01 for 'internal'.

This construct works ... and given the documentation (here and http://www.certificate-transparency.org) seems like a viable starting point.
The hash could be parameterized ... perhaps also the leaf and internal node tags.

Paul

PS - wrote a 'readable' python implementation as an implementation reference:
https://github.com/nymble/merkletree/blob/master/merklehashtree.py

_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg

---

From: Andy Lutomirski <[email-masked]>
Date: Mon, 2 Nov 2015 15:44:43 -0800

On Mon, Nov 2, 2015 at 3:25 PM, Peter Todd <[email-masked]> wrote:
> On Fri, Oct 30, 2015 at 03:09:19PM -0700, Andy Lutomirski wrote:
>> No, but here goes:
>>
>> Amazon does this:
>>
>> http://docs.aws.amazon.com/amazonglacier/latest/dev/checksum-calculations.html
>>
>> Take 1MB chunks (and a possible short trailing chunk).  Hash them with
>> SHA256.  Then, as long as you have more than one hash in your array,
>> hash pairs of hashes together and just keep the extra odd one at the
>> end, if any.  This reduces the number of hashes from n to ceil(n/2).
>> When you have exactly one hash left, you're done.
>>
>> This is vulnerable to a trivial second-preimage attack.  Fortunately,
>> it seems to be okay if you also store the length of the data along
>> with the hash value.
>
> Mind explaining in a bit more detail what exactly you think this attack
> is? Bitcoin did have an attack on a similar implementation, but with the
> critical difference that in Bitcoin rather than moving the odd block up
> to the "next level" it was duplicated:
>

In the simple case, take any long input that's a power of two blocks
long.  Calculate its Amazon-style hash tree root value.  While
calculating it, remember the top two non-root internal node hash
values.  Concatenate them and compute the Amazon-style hash tree root
for *that*.  You'll get exactly the same hash tree root.

This violates both the collision resistance and second-preimage
resistance properties of hash functions, so the Amazon hash tree
construction is not a cryptographically secure hash function.

This attack isn't just theoretical.  It means that, for any given big
file you archive in Glacier, there exists an incorrect and easy to
construct file that could be substituted and would pass a hash
equality check.  That's not okay.

--Andy

---

From: Andy Lutomirski <[email-masked]>
Date: Mon, 2 Nov 2015 16:15:20 -0800

On Mon, Nov 2, 2015 at 4:12 PM, Peter Todd <[email-masked]> wrote:
> On Mon, Nov 02, 2015 at 03:44:43PM -0800, Andy Lutomirski wrote:
> Ah, that's a different attack than what I was thinking of. You could
> also fix this attack by simply using tagged hashing to make the
> computation of inner nodes and leaf nodes be guaranteed to be different.
> If so, concatenating the two leaf nodes' digests and computing the
> Amazon-style hash tree root value would result in a different digest.
>

Indeed.  My point is just that hash trees are useful and that they're
apparently easy enough to screw up that major commercial users have
screwed them up.

Sakura is interesting because it allows lots of flexibility while
retaining a security proof.  For applications that require or even
demand reduced flexibility, other options would work fine as well.

--Andy

---

From: Gilles Van Assche <[email-masked]>
Date: Tue, 3 Nov 2015 17:34:53 +0100

On 10/31/2015 08:36 PM, Taylor R Campbell wrote:
> little unsatisfying for other applications, such as deduplicated storage.
>
> a || b || c. we would like the Merkle tree of the first object to be a
> function of H(a) and H(c), and that of the second object to be a

In Sakura coding, there is no explicit indication of the depth and
offset of a node. So one can reuse message nodes (intermediate hashes)
in different tree shapes.

Kind regards,
Gilles

---

From: Ben Laurie <[email-masked]>
Date: Tue, 03 Nov 2015 18:09:55 +0000

> in different tree shapes.

This is vital for sparse trees (blindness to offset, at least, depth would
be OK).

---

From: Taylor R Campbell <[email-masked]>
Date: Tue, 3 Nov 2015 20:57:45 +0000

Date: Tue, 3 Nov 2015 17:34:53 +0100
   From: Gilles Van Assche <[email-masked]>

With apologies for my false claim above, I must have skimmed the
paper[1] too quickly to come to that conclusion -- it was a bit more
general and abstract than the Blake2 tree-hashing specification.

Do I understand correctly that Sakura is map from tree shape to
encoding, not necessarily with a fixed number of bytes per message
chunk or fixed fanout, depth per message length, &c.?  That is, you
get is something like the following, with, e.g., H = RawSHAKE256 and
with the shape of the tree specified by the caller, no matter how long
a, b, and c are?

Sakura-H(a) = H(a || root=1)
Sakura-H(a || b) =
  H(H(a || root=0) || H(b || root=0) || nrCVs=2 || interleave=0 || root=1)
Sakura-H((a || b) || c) =
  H(H(H(a || root=0) || H(b || root=0) || nrCVs=2 || interleave=0 || root=0)
    || H(c || root=0)
    || nrCVs=2
    || interleave=0
    || root=1)

If I understand correctly, that suggests that Sakura-H(a || b) is not
a function of Sakura-H(a), since it is the root (`final') node that is
distinguished from other (`inner') nodes, not leaf nodes (`message
hops'?) that are distingushed from branch nodes (`chaining hops'?).

I expect that property from a random oracle -- but it's not as useful
for deduplication, since the additional storage for a || b can't be
derived from just the storage index of a, namely Sakura-H(a).

[1] http://keccak.noekeon.org/Sakura.pdf

---

From: Zooko Wilcox-OHearn <[email-masked]>
Date: Wed, 4 Nov 2015 02:01:28 +0000

Dear CFRG Folks:

There's something unsettling here: a feature which seems naturally
desirable and useful in the context of Merkle Trees is related to
length-extension attack in the context of Merkle-Damgård Chaining.

Length-extension attack is that I gave you the terminal node from a
Merkle-Damgård Chain, but I withheld from you the data (the inputs to
the Merkle-Damgård Chain), and then you can generate a new
Merkle-Damgård Chain which includes my chain's terminal node as one of
your chain's internal nodes.

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.

(The Merkle Tree that we defined in Tahoe-LAFS ³, ⁴ — before the SHA-3
process began — *does* allow that. Oops! Fortunately the way those
trees are used in Tahoe-LAFS do not require protection against
length-extension attack.)

Now what if I give you one of the *internal* nodes of my Merkle Tree
(the root of one of its subtrees) but withhold from you the data.
Should you be able to generate a new Merkle Tree which re-uses those
internal nodes?

Sakura allows this. Ben Laurie says on this thread that this behavior
is necessary for sparse trees. (I don't understand why.) The Merkle
Tree that we use in Tahoe-LAFS allows this.

BLAKE2's tree mode doesn't allow you to re-use those internal nodes in
a *different* spot in your tree, because the node offset and node
depth are included in the hash of each node.

Now what weirds me out about this is that I imagine that it is 35
years ago when Merkle and Damgård are coming up with Merkle-Damgård
Chaining, and somebody is saying "That's potentially useful to be able
to re-use nodes like that.".

Seriously, does anybody know if they said that? Because later we sure
as hell decided that it was such a pernicious security flaw that it
was a prime requirement for the SHA-3 process to eliminate that
particular feature.

I don't know if re-usable internal Merkle Tree nodes, like in Sakura
and Tahoe-LAFS, will turn out to be a dangerous security flaw the way
length-extension (re-usable Merkle-Damgård Chain terminal nodes) did.
It just makes me nervous.

Also, observe that we *can't* prevent reusing internal Merkle Tree
nodes entirely, the way we prevent re-using terminal nodes (in either
Merkle-Damgård Chains or Merkle Trees). That's because normal use of
Merkle Trees expose internal nodes — unlike normal uses of
Merkle-Damgård Chains — and while we can prevent such exposed nodes
from being reused in a different location in the tree, we can't
prevent them being re-used in the same location in a different tree.

Final thought: if re-using internal nodes from a Merkle Tree is a
useful thing to do, when why isn't re-using the terminal node — the
root of the Merkle Tree — also useful for such purposes? Could someone
who has one of those uses explain it?

Regards,

Zooko

¹ http://keccak.noekeon.org/Sakura.pdf
² https://blake2.net/blake2.pdf
³ http://eprint.iacr.org/2012/524
⁴ https://github.com/tahoe-lafs/tahoe-lafs/blob/40c78297e897bd38b389b7870f9d18f368035996/src/allmydata/hashtree.py

---

From: Tony Arcieri <[email-masked]>
Date: Tue, 3 Nov 2015 18:13:17 -0800

> was a prime requirement for the SHA-3 process to eliminate that

There is a conceptual use, although clearly "naive" Merkle-Damgård is not
how you want to implement it:

The chained HMAC construction used by Amoeba and Macaroons for credentials
that any bearer can attenuate by adding "caveats" takes advantage of the
concept. In some ways it can be seen as a form of Merkle-Damgård...

-- 
Tony Arcieri

---

From: Ben Laurie <[email-masked]>
Date: Wed, 04 Nov 2015 08:26:32 +0000

On Wed, 4 Nov 2015 at 02:01 Zooko Wilcox-OHearn <[email-masked]>
wrote:

> is necessary for sparse trees. (I don't understand why.)

Because you can't calculate the root of a depth 256 (say) sparse tree
unless the vast majority of nodes have the same value.

> The Merkle

This is an interesting point, and it depends on how you want to use the
tree. If you want to use it to prove that a data structure is append only,
then the ability to extend is exactly the property you want.

If you want to use it to verify a frozen data structure, then maybe you
don't want this property.

OTOH, Merkle trees are generally used in conjunction with signatures rather
than as MACs, in which case, is this a problem at all?

> who has one of those uses explain it?

I think I did above (i.e. re-using the root is useful to allow proof of
append-only). OTOH, for a binary tree, you only need to know two values to
calculate the root, or convert it to an internal node, so doesn't sound
like that big a deal to make it non-re-usable.

---

From: Bryan Ford <[email-masked]>
Date: Sat, 7 Nov 2015 10:46:34 +0900

To return to this thread - DKG brought up one important potential functionality goal for the next OpenPGP message format (streaming-mode integrity protection); then the thread diverged into a different and I think orthogonal - though equally interesting - potential functionality goal (namely random-access capability via Merkle trees as in Tahoe-LAFS).

I included a slide on this topic in my OpenPGP WG presentation (https://drive.google.com/file/d/0BwK1bcoczINtMEI2Y3A1Rm52SXc/view?usp=sharing <https://drive.google.com/file/d/0BwK1bcoczINtMEI2Y3A1Rm52SXc/view?usp=sharing> slide 10) and was hoping to solicit discussion but there wasn’t time, so perhaps we can continue here?

To be clear, there are two separate use-cases, each of which make sense without the other and require different technical solutions (but could also make sense together):

1. Streaming-mode integrity protection:  We want to make sure OpenPGP can be used Unix filter-style on both encryption and decryption sides, to process arbitrarily large files (e.g., huge backup tarballs), while satisfying the following joint requirements:

	(a) Ensure that neither the encryptor nor decryptor ever has to buffer the entire stream in memory or any other intermediate storage.
	(b) Ensure that the decryptor integrity-checks everything it decrypts BEFORE passing it onto the next pipeline stage (e.g., un-tar).

2. Random-access: Once a potentially-huge OpenPGP-encrypted file has been written to some random-access-capable medium, allow a reader to decrypt and integrity-check parts of that encrypted file without (re-)processing the whole thing: i.e., support integrity-protected random-access reads.

Let’s call these goals #1 and #2, respectively.

Achieving either goal will require dividing encrypted files into chunks of some kind, but the exact metadata these chunks need to have will vary depending on which goal we want to achieve (or both).

To achieve goal #1 properly, it appears that what we need is not only a MAC per chunk but a signature per chunk.  If the encryptor only signs a single aggregate MAC at the end, then the decryptor needs to process its input all the way to that signature at the end before it can be certain that any (even the first) bytes of the decrypted data are valid.  If the encryptor produces a Merkle tree at the end and signs its root as in Tahoe-LAFS (e.g., in pursuit of goal #2), the decryptor still needs to read to the end of its input before being able to integrity-check anything, and hence still fails to achieve goal #1.

To achieve goal #2, the Merkle tree approach used in Tahoe-LAFS seems well-suited.  But it assumes/requires the decryptor has a complete, random-access seekable copy of the encrypted file sitting somewhere, which is certainly a reasonable assumption in the context of a file system like Tahoe-LAFS, but violates requirement (a) of goal #1 and in particular may not hold when OpenPGP is used to filter-decrypt from unseekable media or a network stream to an un-tar type process.

We could very well design an OpenPGP format that addresses both goals together, if we decide both goals are valuable.  The encryptor would need to build its Merkle tree incrementally - without initially knowing its total size - and after encrypting and outputting each chunk, generate and sign a new Merkle tree root after each chunk.  We wouldn’t necessarily have to store an entirely new Merkle tree after each chunk, only a log2(N)-size list of hashes comprising the “update path” from the new chunk back to the root, reusing the un-updated parts of the Merkle tree already stored in earlier parts of the encrypted file.  (But this will require that earlier Merkle trees be “incrementally updatable”, which might violate the properties of some of the Merkle tree proposals suggested elsewhere in other threads.)

There are some obvious tradeoffs here, both in storage and complexity costs.  I’m not that worried about the storage efficiency costs, because even the costs of a log2(N)-size list of hashes per chunk can be amortized fairly effectively by making the chunks moderately large, e.g., 65KB or even 1MB.  There’s also the compute cost of performing a public-key signature rather than just a MAC per chunk, but that can be similarly amortized by using relatively large chunks.  On the other hand, large chunks might not be ideal for embedded/constrained devices.  And the implementation-complexity is certainly an issue regardless.

So some questions about this:

1. How important is the ability to achieve goal #1 above in the OpenPGP format (streaming-mode integrity-checking)?

2. How important is the ability to achieve goal #2 above in the OpenPGP format (random-access integrity-checking)? 

3. For whichever goal(s) we wish to be able to achieve, should those be *mandatory* or *optional* in the format?  That is, should *every* OpenPGPv5-encrypted file satisfy either or both of these goals, or should they be configurable or user-selectable (such that some encrypted files might contain per-chunk signatures and/or Merkle trees while others do not)?  Making either of these goals “supported but optional” might help mitigate any performance/storage cost concerns with either of them, but would only further increase the complexity of the overall OpenPGP spec and increase the “usability risk” of a user accidentally failing to enable a relevant option when he really should have (e.g., streaming-mode protection for backups).

4. What are reasonable upper- and lower-bounds for chunk sizes, and what are the considerations behind them?  

Thanks
Bryan

---

From: Andy Lutomirski <[email-masked]>
Date: Fri, 6 Nov 2015 17:54:17 -0800

On Fri, Nov 6, 2015 at 5:46 PM, Bryan Ford <[email-masked]> wrote:
> To return to this thread - DKG brought up one important potential
> functionality goal for the next OpenPGP message format (streaming-mode
> integrity protection); then the thread diverged into a different and I think
> orthogonal - though equally interesting - potential functionality goal
> (namely random-access capability via Merkle trees as in Tahoe-LAFS).
>
> I included a slide on this topic in my OpenPGP WG presentation
> (https://drive.google.com/file/d/0BwK1bcoczINtMEI2Y3A1Rm52SXc/view?usp=sharing
> slide 10) and was hoping to solicit discussion but there wasn’t time, so
> perhaps we can continue here?
>
> To be clear, there are two separate use-cases, each of which make sense
> without the other and require different technical solutions (but could also
> make sense together):
>
> 1. Streaming-mode integrity protection:  We want to make sure OpenPGP can be
> used Unix filter-style on both encryption and decryption sides, to process
> arbitrarily large files (e.g., huge backup tarballs), while satisfying the
> following joint requirements:
>
> (a) Ensure that neither the encryptor nor decryptor ever has to buffer the
> entire stream in memory or any other intermediate storage.
> (b) Ensure that the decryptor integrity-checks everything it decrypts BEFORE
> passing it onto the next pipeline stage (e.g., un-tar).
>
> 2. Random-access: Once a potentially-huge OpenPGP-encrypted file has been
> written to some random-access-capable medium, allow a reader to decrypt and
> integrity-check parts of that encrypted file without (re-)processing the
> whole thing: i.e., support integrity-protected random-access reads.
>
> Achieving either goal will require dividing encrypted files into chunks of
> some kind, but the exact metadata these chunks need to have will vary
> depending on which goal we want to achieve (or both).
>
> To achieve goal #1 properly, it appears that what we need is not only a MAC
> per chunk but a signature per chunk.  If the encryptor only signs a single
> aggregate MAC at the end, then the decryptor needs to process its input all
> the way to that signature at the end before it can be certain that any (even
> the first) bytes of the decrypted data are valid.  If the encryptor produces
> a Merkle tree at the end and signs its root as in Tahoe-LAFS (e.g., in
> pursuit of goal #2), the decryptor still needs to read to the end of its
> input before being able to integrity-check anything, and hence still fails
> to achieve goal #1.
>

[...]

> 1. How important is the ability to achieve goal #1 above in the OpenPGP
> format (streaming-mode integrity-checking)?
>

Are you willing to accept a format that allows streaming decryption
but not streaming encryption?  If so, then you'd only need one
signature if you organize your Merkle tree correctly.  In fact:

> 2. How important is the ability to achieve goal #2 above in the OpenPGP
> format (random-access integrity-checking)?

It's fairly easy to imagine a format that allows both streaming
verification and random-access verification with minimal size
overhead.  You could even create the thing in a semi-streamy manner,
where you'd stream out the bulk portion with blanks where the internal
nodes go and then write the internal nodes after the fact.

The best of all worlds might be to treat the Merkle data and the
signature as a detached file.  I bet that one could streamily encrypt
and sign a big file and produce *two* output streams: the bulk data
and a detached serialization of intermediate nodes, where there's a
single signature at the end.  A reader with access to both files could
random-access it or seek the detached signature a bit and then stream
the bulk file.

--Andy

---

From: Bryan Ford <[email-masked]>
Date: Sat, 7 Nov 2015 16:19:21 +0900

On Nov 7, 2015, at 10:54 AM, Andy Lutomirski <[email-masked]> wrote:
> On Fri, Nov 6, 2015 at 5:46 PM, Bryan Ford <[email-masked] <mailto:[email-masked]>> wrote:

That’s certainly one reasonable use-case to consider, but I don’t think it fully satisfies the “filter-mode encrypted backup” scenario that DKG originally brought up.  If I’m encrypting and streaming my huge backups to a huge network connection, then I don’t want the encryption side to have to store the whole huge backup tarball locally either.  My intuition is that if the "filter-mode streaming backup” scenario is important on either the encryption or decryption side, then it’s probably important to be able to handle on both sides.

On the other hand, it might be quite reasonable to define an encrypted message format that allows either mode of operation, and have the encryptor choose the mode of operation automatically depending on the situation.  If the encryptor sees that both its input and its output are regular files, i.e., it knows the total length of its input and can seek in its output, then the encryptor could (as you suggest) leave room for a signed Merkle tree at the beginning, process everything, then go back to the beginning and fill in the Merkle tree and the signature on its root.  Then a streaming-mode decryptor would get the signed Merkle tree first and subsequently be able to integrity-check all subsequent chunks independently.  However, if the encryptor finds that either it doesn’t know the length of its input in advance, or has been told to send output to a non-seekable stream (e.g., over an SSH-forwarded network pipe), then the encryptor might have to fall back to a more incremental approach, with signatures (or signature-plus-incremental-Merkle-trees) after each chunk.

> random-access it or seek the detached signature a bit and then stream

I think detached files sound convenient to implementers but prove troublesome to users who need to know how to juggle and keep track of two files where before they only need to keep track of one. :)

B

---

From: Bryan Ford <[email-masked]>
Date: Sat, 7 Nov 2015 22:45:00 +0900

Hi Zooko,

> On Nov 4, 2015, at 11:01 AM, Zooko Wilcox-OHearn <[email-masked]> wrote:
> 

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.

Case in point: the collective timestamping and time-freshness-proof we’ve implemented in the collective signing/witnessing scheme I presented in the Trans WG (see http://datatracker.ietf.org/doc/draft-ford-trans-witness/ <http://datatracker.ietf.org/doc/draft-ford-trans-witness/> and http://arxiv.org/abs/1503.08768 <http://arxiv.org/abs/1503.08768>) and briefly in the NTP WG.

In the timestamping use-case for this protocol, we have a “leader” timeserver of some kind, and any number of followers or “witnesses”.  Every so often, say every 10 seconds or so, the leader initiates a new round in which it proposes a new uint64 timestamp representing what it thinks is the current time, and broadcasts a message to all its witnesses soliciting contributions to a large Merkle tree of hashes to be timestamped in that rounds.  Both the leader and all followers can accept timestamp requests from clients, in which a client simply submits a hash or other random value of the client’s choosing, and waits for an answer until the next round completes.  

Each server (leader or follower) takes all the hashes/nonces submitted in each round, and composes them into a local Merkle tree, yielding a hash representing the root of that tree.  For efficiency the followers are organized into a communication-tree structure (not to be confused with the Merkle trees).  Each leaf follower in this communication tree passes the root of its local Merkle tree up to its parent, who composes its own local Merkle tree and those of its children into a larger Merkle tree to be passed up to its parent, and so on, until the leader finally forms the top levels of a global Merkle tree accounting for all hashes/nonces submitted by all clients to any of the servers in that round.

Now the leader initiates a second round-trip down through the communication-tree, which serves two purposes: (a) it allows the leader to collect the parts of a collective signature on the root of the global Merkle tree, and (b) more importantly for the present purposes, it enables servers higher in the communication-tree to “hand down” to each of their immediate children an inclusion-proof (Merkle tree path) of each immediate child’s smaller Merkle tree within the global Merkle tree.  These inclusion-proofs further compose going down the communication-tree towards the leaves.  Any witness server anywhere in the communication-tree who observes that its local Merkle tree wasn’t included in the global one to be signed (i.e., if the inclusion proof doesn’t check out) can raise an alarm and refuse to co-sign.  Finally, once each server has an inclusion-proof relating its local Merkle tree to the collectively-signed global root for this round, each server can compose that with an inclusion-proof within its local Merkle tree to produce an inclusion-proof for each of its waiting clients, proving to that client (and anyone else) that the client’s submission in that round was included (and hence timestamped) under the collective authority of the collective signature on the global Merkle tree root for that round.

I think it’s fairly important for the efficiency of this scheme that (a) each individual server gets to create a local tree of whatever size it “needs” in that round (depending on the number of clients that show up and submit hashes to timestamp in that round), without having to coordinate in advance with other servers or their parents in the communication-tree; (b) the higher-level servers in the communication tree need not know or care how big their descendants’ local Merkle trees are, or whether their sizes or depths are “balanced” with respect to each other; and (c) most important, none of these servers ever need to ship around the bulk contents of any of these Merkle trees.  The most that gets communicated between any pair of communicating partners in any round (between parent and child servers or between any server and one of its clients) is a single inclusion proof.  Clients who just wanted a particular hash timestamped just get one inclusion proof (and the collectively signed global Merkle tree root) in return, and don’t need to know or care what part of that inclusion proof connects the global root to their server’s local root and which part connects the local root to their hash.

The type of “length-extension attack” you’re worried about here (shouldn’t it be called a “tree-extension attack”?) aren’t a security problem at least in the timestamping case because the root of trust is the global root of the tree: anyone is free to compose that tree or any (perhaps unknown to them) subtree of it into some other Merkle tree, but no one is going to use that for anything (at least in this protocol) unless it’s appropriately signed.  Further, anyone is free to take a subtree (or an entire global root) from one round and submit it as a “hash to be timestamped” in a future round by the same leader, or in another time-sequence driven by another leader entirely; doing so is useful because it can create provable “happens-before” relationships relating one leader’s time-series to any other's.  If handled appropriately, this type of “ad hoc composition” can ensure that there is eventually a demonstrable “happens-before” relationship, evidenced by a single, efficient, uniform Merkle inclusion proof, between any two “timestamps” on any two trees, provided their trees cross-fertilize regularly in this way.

Outside of the scalable collective timestamping example, I think it’s often desirable to be able to build a Merkle tree incrementally without initially knowing its complete size, or to create incremental modifications (“edits”) of an existing Merkle tree efficiently, by creating a new tree that just re-uses parts of an older one.  For example, in a (perhaps distributed) file system in which large files or directories are represented by Merkle trees, it can be nice not to have to re-create the entire Merkle tree when one part of it changes, but to allow some number of incremental changes that reuse parts of the old tree and thus require less metadata-update (perhaps until the tree gets too messy or unbalanced).  In the discussion on streaming-mode encryption for OpenPGP, there was an example of the encryptor needing to build a Merkle tree incrementally without knowing in advance how big it will eventually - although in this case it at least can always build it “left-to-right, bottom-to-top”, which simplifies things.

For many use-cases, especially where we expect Merkle trees always to be built “all at once”, I agree that it’s probably best to include the type of “unexpected-reuse-protection” or “tree-extension protection” mechanisms you have in mind.  But my point is simply that there are also situations in which I would want to be able to turn them off. :)

B

---

From: Bill Cox <[email-masked]>
Date: Sat, 7 Nov 2015 09:53:48 -0800

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

> 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

---

From: Bryan Ford <[email-masked]>
Date: Mon, 9 Nov 2015 06:27:59 +0100

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

---

From: Alex Elsayed <[email-masked]>
Date: Thu, 12 Nov 2015 06:32:16 +0000 (UTC)

On Fri, 30 Oct 2015 08:11:48 +0900, Daniel Kahn Gillmor wrote:

> Hi CFRG folks--
> 
> We're looking into fixing the OpenPGP symmetrically-encrypted data
> formats for RFC4880bis.  The structures are used for mail messages but
> also for large file encryption.  It's clear that the OpenPGP CFB mode
> isn't designed to modern symmetric encryption standards, so we're hoping
> to introduce a better approach.
> 
> We need, among other things to address integrity protection in a more
> meaningful way than the current OpenPGP MDC (modification detection
> code), which is basically a SHA-1 hash of the cleartext.  This was never
> much better than a band-aid.  And as discussed in the recent "OpenPGP
> SEIP downgrade attack" thread, an "integrity-protected" packet with an
> MDC can be stripped down to produce a syntactically-valid packet without
> integrity protection.
> 
> But one of our constraints is the OpenPGP use case that streams
> decrypted data, like this:
> 
>  pgp --decrypt <backup.pgp | tar x
> 
> It's unlikely that this use case will go away.

<snip>

> Thoughts, pointers, or suggestions would be much appreciated.

Rogaway et. al. have a pair of constructions that come with very good 
security reductions, named CHAIN (requires strongly nonse-misuse-
resistant underlying AEAD, which is hard to come by) and STREAM (only 
requires nonce-based AEAD).

https://eprint.iacr.org/2015/189

If you want to forbid out-of-order decryption, you can also use each 
packet (or a hash thereof) as AD to the next.

---

From: Gilles Van Assche <[email-masked]>
Date: Fri, 20 Nov 2015 11:06:34 +0100

Hi Taylor,

Sorry for the late answer.

> general and abstract than the Blake2 tree-hashing specification.

No problemo. And yes, Sakura is not tight to a particular hash function.

> chunk or fixed fanout, depth per message length, &c.?

Yes, or "to encodings" since there could be more than one possible
encodings for a given tree shape, given the degrees of freedom that are
foreseen in Sakura. Alternatively, we speak about "Sakura-compatible
modes", where a mode specifies unambiguously how to shape and format the
tree.

> That is, you

I see your point.

Alternatively to your example above, one could define MyTreeH(a) = H(H(a
|| root=0) || nrCVs=1 || root=1). This way, H(a || root=0) would be a
"hash over chunk a", where this chunk could be reused in other files,
and H(a || root=1) or H(H(a || root=0) || nrCVs=1 || root=1) a "hash
over a file whose full content is composed of chunk a only". In other
words, the root/final flag behaves like domain separation between the
hash of a (complete) file versus the hash of a chunk (not necessarily a
complete file).

Kind regards,
Gilles