Subject: Re: [openpgp] [Cfrg] streamable AEAD construct for stored data?

From: Natanael <[email-masked]>
Date: Fri, 30 Oct 2015 13:25:03 +0100

Den 30 okt 2015 11:01 skrev "Daniel Kahn Gillmor" <[email-masked]>:
>
> 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:

[...]

> This approach still has two notable problems i can see, which may or may
> not be addressable (but if they are, i'd love to hear it):
>
>  a) it doesn't deal with truncation -- the initially-streamed data has
>     already been streamed by the time a truncation is discovered.
>     (there may be no way to fix this; it seems kind of like a fact of
>     nature, and if so, systems should only do streaming decryption if
>     they're capable of coping with truncation)

Does it help to define the ciphertext length and check that first, before
decrypting? Doesn't help if the file isn't local and the connection is
broken, but then at least your software should detect that and halt of
necessary.

>  b) it doesn't seem to compose as well with asymmetric signatures as one
>     might like: a signature over the whole material can't itself be
>     verified until one full pass through the data; and a signature over
>     just the symmetric key would prove nothing, since anyone getting the
>     symmetric key could forge an arbitrary valid, decryptable stream.
>     Is there an intermediate approach that would combine an asymmetric
>     signature with a chunkable authenticated encryption such that a
>     decryptor could stream one pass and be certain of its origin (at
>     least up until truncation, if (a) can't be resolved)?
>
> Thoughts, pointers, or suggestions would be much appreciated.

To solve B what you need to do is something like signing a list of
ciphertext hashes/authentication tags.

One thought I've had before (my idea is to use it for FDE*) is to for
example use HMAC over segments (including counters) or to extract AEAD tags
(prefixed with counters to preserve order) and create a Merkle tree hash of
those lists when creating the message, to then sign that Merkle tree, such
that when you decrypt and recreate the tags for comparison you can confirm
that nothing has been modified (with the level of assurance that the tags
can provide). Or you skip the standard AEAD and MAC constructs and use a
signed Merkle tree hash of the ciphertext itself as your own custom MAC.

One benefit of using a hash-tree like algorithm with a signature is the
reduction of storage overhead and memory usage, and that you retain the
ability to independently verify each segment. Ideally you would use a
hash-tree like algorithm which also can be generated efficiently in a
single pass over even large ciphertexts with reasonable memory usage (does
anybody know of one?).

Not that I've also read the referenced Tahoe-LAFS link, it looks like
they're doing something very close to what I described above, but slightly
different:
They use AES-CTR over the whole file with a unique key, one plain hash over
the entire ciphertext, one Merkle tree hash over the ciphertext blocks and
one Merkle tree hash over the erasure coded shares of the blocks, if I'm
reading it correctly, with all three hashes stored in plaintext with the
shares and then hashed together (also including the length of the file).
They also have some sort of hash chain, but the graphics don't load and I
can't figure out how exactly it is applied, beyond potentially having to do
with confirming the order of blocks. Instead of using HMAC they use double
SHA256 in a particular format.

Minus the erasure coding** and with an added signature of the file
hashes/header, that's almost exactly what I imagined, I'm just worried
about the risk of the performance penalty limiting adoption. If the
performance of this method is considered acceptable or can be improved to
an acceptable level, I definitely support using it.

* A bit off topic here, but for FDE I imagine changing the encryption key
every write-session using a KDF and session counter, keeping an
authenticated encrypted list of which segments uses which session write
keys. This way you prevent partial ciphertext reversal and prevent
detection of when ciphertext segments repeat over time (re-zeroized or
restored files). You can also arbitrarily re-encrypt random segments to
obscure your real write patterns (and reduce the list size occasionally by
purging unused keys after re-encrypting the last segments using them).

** In Tahoe-LAFS, erasure coding of blocks is used to allow you to split
files across storage nodes with minimal risk of data loss. That's not
applicable here, as it can be applied independently when considered
necessary.

---

From: Natanael <[email-masked]>
Date: Fri, 30 Oct 2015 14:18:12 +0100

Den 30 okt 2015 13:30 skrev "Watson Ladd" <[email-masked]>:
>  On Oct 30, 2015 8:25 AM, "Natanael" <[email-masked]> wrote:
>> [...]
> Use authenticated encryption so no signatures are required. Detached
signature verification is used for large public messages already: no
streaming needed.

I'm not sure if we read the requirements differently. He asked for
immutable signed files, as in that an AEAD authentication key is
insufficient because the other recipients all have the same key and can
substitute the ciphertext. There's an explicit requirement that the
capabilities of the sender and (potentially multiple) receivers are
different.

Yes, the signature would fail if combining standard AEAD with a full
ciphertext signature and one receiver modified the ciphertext, but see the
reasoning for why it is necessary again - by the time the failure is
detected, the software that's performing the streaming decryption and
processing may already have taken some undesired action, or might fail to
cancel a future undesired action (by not deleting the resulting plaintext).
Preemptively preventing mistakes done by the client software.

It isn't just AEAD, it is seekable streaming AEAD with per-block
verification of immutability. Allowing you to look up any block
individually and confirm *that block* hasn't been modified by anybody but
the original sender.

Imagine for example an encrypted video or a large archive of files being
sent to multiple receivers. With AES-GCM and a signature at the end, you
either decrypt and verify everything before viewing or you decrypt just one
part and accept that another one of the receivers may have tampered with
your copy of the video/files (if it for example is stored on a NAS).

Or worse, the software parsing the plaintext might have an exploitable bug,
which may then already have been exploited when the signature verification
fails, so that even if the decryption software rolls back everything it did
then you now have malware on your system anyway.

The other option is of course the sender creating multiple ciphertexts with
separate keys for every recipient. Very much not ideal for large files.

>
> The idea below demands conditions beyond MAC security.

Feel free to explain what conditions those are. I'll happily admit I'm just
a cryptography novice, I'm willing to learn why this might be flawed or
insufficient.

---

From: Taylor R Campbell <[email-masked]>
Date: Fri, 30 Oct 2015 18:32:30 +0000

Date: Fri, 30 Oct 2015 08:11:48 +0900
   From: Daniel Kahn Gillmor <[email-masked]>

If only the receiving end needs streaming -- that is, if the sender
can process an entire message before the receiver receives any of it
-- then you can relatively easily address this, as Tahoe-LAFS does,
given a session key k:

(sender)
1. Break the data up into bounded-size chunks.
2. (Symmetrically encrypt the chunks with k if you want.)
3. Compute a Merkle tree under a PRF keyed by k of the chunks.
4. Sign the root of the Merkle tree.
5. Store the signed root, and each chunk alongside its path down the
Merkle tree.

This requires only O(log n) working memory to compute the Merkle tree
-- it takes a single pass over the whole input.

(receiver)
1. Verify the root of the Merkle tree.
2. When receiving a chunk and a path, verify the path from the root.
3. (Decrypt the chunk with k if you want.)

For public signatures, you can fix k = 0 and hope nobody finds
collisions in PRF_0, or randomize k and hope nobody finds
target-collision attacks on PRF (which is unlikely -- even MD5(k, m)
is probably still OK for that, as far as I know).  For authenticated
encrypted messages, you can derive it from a DH shared secret, or do
standard public-key-encrypted key wrap, &c.

---

From: Andy Lutomirski <[email-masked]>
Date: Fri, 30 Oct 2015 11:47:42 -0700

> -- it takes a single pass over the whole input.
...which reminds me:

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.

Should CFRG consider standardizing a transport format for hash tree
verifiers (or proofs or whatever they're called) and for a large blob
that can be used to efficiently generate the proofs (essentially some
kind of serialized tree)?  The Sakura construction could be a good
starting point.  If I were designing such a standard, I would be
extremely hesitant to start with SHA256 or similar because of the lack
of personalization, whereas Sakura (and maybe BLAKE2) doesn't have
this problem.

Sadly, Sakura doesn't seem to be officially blessed yet.

--Andy

---

From: Adam Langley <[email-masked]>
Date: Fri, 30 Oct 2015 14:28:10 -0700

> wrong: Amazon's Glacier hash and (unless it changed) Bittorrent's new

Do you have references for either of these two issues? I wasn't aware of them.

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Andy Lutomirski <[email-masked]>
Date: Fri, 30 Oct 2015 15:09:19 -0700

> Do you have references for either of these two issues? I wasn't aware of them.

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.

I don't know what Bittorrent is actually doing, but I found this
thing:  http://www.bittorrent.org/beps/bep_0030.html  It seems
similarly broken.

--Andy

---

From: Björn Edström <[email-masked]>
Date: Sat, 31 Oct 2015 10:20:53 +0100

On Fri, Oct 30, 2015 at 12:11 AM, Daniel Kahn Gillmor
<[email-masked]> wrote:
>  pgp --decrypt <backup.pgp | tar x
>
> It's unlikely that this use case will go away.

Is that constraint really set in stone?

PGP is a complicated system to use and understand for most people and
the more an implementation can do to prevent potential dangers the
better. I think it could be worthwhile of the spec to have security
guidelines for implementers to make dangerous invocations more
difficult.

To use your example, consider the following further examples:

pgp --decrypt --file backup.pgp | tar x

The above is fine. Run two passes over the file, one for integrity,
one for output.

pgp --decrypt < small-backup.pgp | tar x

The above is fine. The file is small and it fits into some predefined
buffer in memory before reaching EOF. Similar to the above: check
before outputting anything.

pgp --decrypt < backup.pgp | tar x

The above is *not* fine, and the user should have to go through hoops
to make it work (for example some kind of --unsafe option, or big
warning pop up box in a GUI application).

In general I think the OpenPGP spec should have more guidelines for
implementors since it's very easy for the user to screw up if the user
is not familiar with intricate details of the system. This is to a
greater extent than other specs, that mostly concern specialists
anyway.

Removing the constraint above, and living in the normal world where
you do 1 pass integrity before decrypting, you can use much more
boring and standard cryptographic constructs, which I personally would
prefer in this case.

Cheers
Björn

---

From: Andrey Jivsov <[email-masked]>
Date: Sat, 31 Oct 2015 19:10:41 -0700

On 10/30/2015 07:46 AM, Watson Ladd wrote:
> In AES-GCM the nonce is 96 bits. (Yes, I know it admits any length
> nonces, but there is a weakness due to Iwata-Ohashi-Minematsu for any
> length not 96 bits). Reserving 64 bits for the chunk counter leaves 32
> bits. Each chunk can be a maximum of 2^12  or so blocks, due to the
> absence of a beyond-birthday bound security result. (Maybe there is
> one, I don't know it, and I suspect there isn't for confidentiality).

Such a generic claim about "absence of a beyond-birthday bound 
security", is unfortunately not true for AES-GCM.

David Mcgrew pointed out his eprint paper, which I will distill here 
into a practical attack on the current TLS 1.3 privacy feature. The 
feature in question intends to hide the size of the TLS record 
(https://tools.ietf.org/html/draft-ietf-tls-tls13-10#section-5.2.3)

The feature is broken in the very use case the feature was intended to 
defend against:
- passive monitoring, including analysis of previously recorded traffic
- the size of the protected (real) plaintext is revealed, and not just 
the the fact that the padding was used.

The only challenge in this attack is the need to accumulate on the order 
of 2^64 16 byte blocks for a probability 1/2 statements, but this will 
be less, accordingly, for lower probability, and actually we will see 
that this even less due to the design of the feature. However this 
storage requirement is a common property of birthday boundary attacks.

To remind, the TLS 1.3 padding pads the plaintext record at the end with 
Z=0^128 blocks.

The key property that enables the attack is that encryption of Z will 
produce a block that is unique so far for the given stream.

Let's see in details how this is exploited.

- accumulate all 16-byte ciphertext blocks in the TLS session, building 
the table T with all seen 16-byte C_i.
- Once the table has near 2^64 unique entries, we are setup to break the 
padding
- For a new TLS record, iterating from the last_index-x 16-byte block: 
If the block is unique, this is likely C_j = AES-GCM(Z). Iterating up, 
we stop when we have a collision with an entry in T. On collision, we 
know that C_j wasn't an encrypted Z.

Note that the property of multiple Z at the end amplifies this attack 
(not discussed further here). This means that we will need much less 
than 2^64 blocks for 1/2 probability.

( x here is to adjust for the fact that the very last block won't be Z 
due to fixed metadata. This shouldn't be a problem in practice. )

( One possible fix is to use random/pseudorandom data instead of Z. 
Another is to limit the number of records sent, currently 2^64, which is 
too high in this attack).

( It's true, however,  that AES-GCM seems to go farther than AES-CBC or 
AES-CFB in its defense against outright decryption of plaintext. )

---

From: Peter Todd <[email-masked]>
Date: Mon, 2 Nov 2015 18:25:02 -0500

> it seems to be okay if you also store the length of the data along

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:

https://github.com/bitcoin/bitcoin/blob/d22701118413b876579c020ea90ecf7a0d5671cb/src/primitives/block.cpp#L17

-- 
'peter'[:-1]@petertodd.org
00000000000000001082036bc5c78a25a50b85744159b260e5136771a5611715

---

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

> 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: Peter Todd <[email-masked]>
Date: Mon, 2 Nov 2015 19:12:40 -0500

> equality check.  That's not okay.

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.

-- 
'peter'[:-1]@petertodd.org
000000000000000003ee8302880a8e3d7a1e76be81c561cee33a44767680472e

---

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

> 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: Peter Todd <[email-masked]>
Date: Mon, 2 Nov 2015 19:43:31 -0500

> Sadly, Sakura doesn't seem to be officially blessed yet.

I wasn't aware of Sakura previously; it does seem very complex which I'm
sure is holding it back.

I had a need for a merkle tree over a list of items with the ability to
efficiency prove the (relative) position of items committed to in the
tree, as well as strict determinism. (for every message there is only
one valid digest) I came up a fairly simple scheme that I'm calling
merkle-mountain-ranges:

https://github.com/proofchains/python-proofmarshal/blob/master/proofmarshal/mmr.py

While I didn't write the above with hashing byte strings in mind, by
specifying a block size it could be easily modified to do so. (though be
careful you don't lose the determinism!)

-- 
'peter'[:-1]@petertodd.org
00000000000000000de6dfa01305b9163ad2efd9f72c77c23ebddf62afc18b00

---

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: ianG <[email-masked]>
Date: Sun, 8 Nov 2015 10:43:02 +0000

On 7/11/2015 01:46 am, Bryan Ford wrote:
> 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.

Yes.

> (b) Ensure that the decryptor integrity-checks everything it decrypts
> BEFORE passing it onto the next pipeline stage (e.g., un-tar).

ok.  So this is where a program-level option comes in.  In streaming 
mode, the streamer can keep decrypting and passing it across to the 
reader, and then break when an integrity check fails.

In streaming mode, this is how we would expect it to operation.  A user 
program can however offer some options in this case.  Eg., do an 
integrity check pass before hand as a separate option;  and turn the 
integrity checks into warnings, keep decrypting the data, knowing that 
there is garble in there, keep streaming.  Both two useful options a 
program could offer.

So I'd say NO - streaming is streaming, and there isn't a requirement in 
the spec to be sure about the entire file before hand.  That's just a 
quirk of the streaming mode that users will have to accept.

> 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.
>
...
> We could very well design an OpenPGP format that addresses both goals
> together, if we decide both goals are valuable. ...
>
> There are some obvious tradeoffs here, both in storage and complexity
> costs.  I’m not that worried about the storage efficiency costs,...
>   And the implementation-complexity is certainly an issue regardless.

Nod.  Let's see how the requirements go first, and whether there is a 
reasonable design possible second.

> format (streaming-mode integrity-checking)?

It's certainly important.  If we want to bring everyone across to a new 
format, and start ditching the old (from the standard) then we have to 
provide an equivalent to common use cases.

I'm inclined to say that stream-mode must be integrity checked.  We want 
to achieve the same standard across the board, we don't want to say "if 
X, then Y, but if the Z, then not Y and maybe W..." and complicate the 
user understanding.

> format (random-access integrity-checking)?

Random access is a new feature.  It's certainly an *attractive* feature 
for the inner geek, just because.  But I am not seeing a clear use case 
as yet, at the user level.  If I think about the command line, I can't 
see a way a user would say "decrypt from blocks 1234 to 8960" without 
getting into some arcane geeky construction like doing dd(1) or somesuch 
... which no sane end-user does.

What I am seeing is that this would be an API call to other systems 
which do know what they want.  This would be quite useful for a backup 
for example, or an rsync-like tool.  Being able to re-start the backup 
is incredibly useful, being able to set off a backup to do a sort of 
"rsync" phased copy from "state N" without phase errors would be fantastic.

We would be then entering into the library space rather than the 
end-user interface space.  This might actually be a good thing, it might 
tear our childlike grip from the command line and drag us into the new 
millenium in time for the next decade.  It might finally kill off our 
obsession with email :)

Or it could be mission creep, scope enlargement, or the sinking of the 
project if we become all things to all other projects building GUIs on top?

> 3. For whichever goal(s) we wish to be able to achieve, should those be
> *mandatory* or *optional* in the format?

I'd really like to see one format.  The boolean logic that goes with 
different formats just ripples through the users minds and creates 
confusions.  Every confusion creates loss of users.  Every user we lose 
to confusion is a breach of security because they go on to do it 
cleartext or some other inadequate tool.  If we have 10 such confusions 
scattered across the code, we'll probably half the number of users.

That's without even talking about bugs, and security snafus and the 
potential for choosing the wrong mode and breaking the lot...  E.g., it 
took me 2 years to find out the reason why SVN would break every month 
was that the client side was mounted on a Mac OSX drive that had an 
*option* to select case insensitivity...  dozens of mandays lost in 
rectification/recovery/rebuilding client repos because of an obscure option.

There is a reason the MiB run around and insert multiple-mode madness 
into people's minds in groups.  It makes security brittle.  It makes it 
easy for them to futz.

> 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).

Yup.  And then he goes off an uses another tool.  Coz the sales force 
have realised that taking options away makes the sale easier, and the 
user can't see the schlock under the hood anyway.

> are the considerations behind them?

Defer to later.

iang