Subject: [Spasm] Chunking ciphertexts

From: Adam Langley <[email-masked]>
Date: Thu, 1 Sep 2016 17:22:18 -0700

Since the WG is currently considering changes to S/MIME, I'd like to
mention the benefits of chunking ciphertexts. (Or, rather, the
problems with not chunking them.)

As I understand it, S/MIME and associated standards typically encrypt
payloads as a single ciphertext (i.e. RFC 5084). Since the plaintexts
might be quite large, this encourages implementations to decrypt these
ciphertexts in a "streaming" fashion, i.e. they return plaintext
before it's authenticated.

Encouraging APIs that return unauthenticated plaintext is an ecosystem
cost since such APIs are dangerous. One similarity is with the
MAC-then-encrypt constructions used in TLS, which caused many problems
by processing unauthenticated ciphertext. At a higher level, it's not
hard to find people on the internet suggesting things like:

gpg -d your_archive.tgz.gpg | tar xz

because the gpg command also provides a "streaming" interface.
(http://askubuntu.com/questions/95920/encrypt-tar-gz-file-on-create)

With constructions like AES-GCM it's, of course, very easy to
manipulate the plaintext at will if the application doesn't
authenticate it before processing. Even if the application is careful
not to "release" plaintext to the UI until the authenticity has been
established, a streaming design exposes more program attack surface.

By normalising large ciphertexts and thus streaming APIs, the next
protocol that comes along is more likely to use them without realising
the issues and thus the problem persists.

Preferably, plaintext inputs would be chunked into reasonably large
parts (say 16KiB) and encrypted separately. The chunks only need to be
large enough that the overhead from the additional authenticators is
negligible. With such a design, large messages can be incrementally
processed without having to deal with unauthenticated plaintext, and
AEAD APIs can be safer. (Not to mention that larger messages can be
processed since AES-GCM, for one, has a ~64GiB limit for a single
plaintext.)

Some thought is needed to ensure that the chunks are in the correct
order (i.e. by counting nonces), that the first chunk should be first
(i.e. by starting the nonce at zero) and that the last chunk should be
last (i.e. by appending an empty, terminator chunk with special
additional data). But that's not hard.

Even with such a design it's still the case that an attacker can cause
the message to be detectably truncated. If you want to aim higher, an
all-or-nothing transform can be used, although that requires two
passes over the input and I understand if it's sufficiently
problematic that you don't want to do that.

Cheers

AGL

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

---

From: Wei Chuang <[email-masked]>
Date: Fri, 2 Sep 2016 09:56:17 -0700

Cross posting to Curdle as I think this is more of a general problem than
just S/MIME.

Support for chunking could be done at CMS, and would require updating
RFC5652.

I also wanted to point out that there was a similar discussion in the cfrg
earlier
<https://www.ietf.org/mail-archive/web/openpgp/current/msg08331.html> on
this topic though I don't know what the outcome was.

-Wei

On Thu, Sep 1, 2016 at 5:22 PM, Adam Langley <[email-masked]> wrote:

> _______________________________________________
> Spasm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/spasm
>

---

From: Russ Housley <[email-masked]>
Date: Fri, 2 Sep 2016 14:37:51 -0400

Adam:

I agree that returning yet-to-be-authenticated plaintext is very harmful.  All of the AEAD ciphers that I know explicitly say not to do so.

In thinking about the problem that you raise, I think that a chafe would be needed at the CMS layer, which could then be used at the S/MIME layer.

RFC 5083 defines    AuthEnvelopedData:

      AuthEnvelopedData ::= SEQUENCE {
        version CMSVersion,
        originatorInfo [0] IMPLICIT OriginatorInfo OPTIONAL,
        recipientInfos RecipientInfos,
        authEncryptedContentInfo EncryptedContentInfo,
        authAttrs [1] IMPLICIT AuthAttributes OPTIONAL,
        mac MessageAuthenticationCode,
        unauthAttrs [2] IMPLICIT UnauthAttributes OPTIONAL }

The authEncryptedContentInfo would need to be replaced with a SEQUENCE of encrypted chunks, where each chunk would need an integrity-protected sequence number and ciphertext.

I think this is beyond the scope of the current LAMPS WG charter, but if people would really implement it, I am willing to do the CMS layer work.

Russ

---

From: Russ Housley <[email-masked]>
Date: Fri, 2 Sep 2016 14:40:56 -0400

As I just said on the SPASM mail list: In thinking about the problem that you raise, I think that a chunking would be needed at the CMS layer, which could then be used at the S/MIME layer.

This problem is not one that belongs in the CURDLE WG because it involves much more than new algorithms.

Russ

On Sep 2, 2016, at 12:56 PM, Wei Chuang <[email-masked]> wrote:

> Cross posting to Curdle as I think this is more of a general problem than just S/MIME.  
> 
> Support for chunking could be done at CMS, and would require updating RFC5652.
> 
> I also wanted to point out that there was a similar discussion in the cfrg earlier on this topic though I don't know what the outcome was.
> 
> -Wei
> 
> 
> Curdle mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/curdle

---

From: Jim Schaad <[email-masked]>
Date: Fri, 2 Sep 2016 14:31:08 -0700

Adam,

I have some problems with doing chunked encryption algorithms because I am
never sure what is being attempted with them.

The version that is being proposed for HTTP
(http://httpwg.org/http-extensions/draft-ietf-httpbis-encryption-encoding.ht
ml) is being done because it allows for random access decryption so that it
can be done by multiple streams.  You are suggesting that another reason is
so that one can have even larger encrypted objects than is currently
permitted by some algorithms.  The block size suggested below is much larger
than that suggested for HTTP.  

I know that I have had discussions with people at various points about not
supplying a streaming interface to crypto APIs as being an issue that
"should be fixed" because it is what they are used to having.  This was
raised several times when doing the W3C WebCrypto interfaces.

One of the problems that I have is that you need to do a couple of different
things that I am never sure are properly covered:

1.  You need to make sure that blocks cannot be moved.
2.  You need to make sure that a block cannot be substituted for.
3.  You need to make sure that each block is integrity checked before
release.
4.  If you allow for random access, should all prior blocks be somehow
integrity checked first?

If you are using stream APIs, what do you do if the first ten blocks are
fine, but then the eleventh block is messed up?  This fact then needs to be
propagated down the stream in some fashion so that correct responses can be
executed.  The last think you want is to execute

gpg -d your_archive.tgz.gpg > archive.tar

and have the file left on the disk even though it is not complete.

jim

> -----Original Message-----
> From: Spasm [mailto:[email-masked]] On Behalf Of Adam Langley
> Sent: Thursday, September 01, 2016 5:22 PM
> To: [email-masked]
> Subject: [Spasm] Chunking ciphertexts
> 
mention the
> benefits of chunking ciphertexts. (Or, rather, the problems with not
chunking
> them.)
payloads
> as a single ciphertext (i.e. RFC 5084). Since the plaintexts might be
quite large,
> this encourages implementations to decrypt these ciphertexts in a
"streaming"
> fashion, i.e. they return plaintext before it's authenticated.
> 
cost
> since such APIs are dangerous. One similarity is with the MAC-then-encrypt
> constructions used in TLS, which caused many problems by processing
> unauthenticated ciphertext. At a higher level, it's not hard to find
people on the
> internet suggesting things like:
> 
> With constructions like AES-GCM it's, of course, very easy to manipulate
the
> plaintext at will if the application doesn't authenticate it before
processing. Even
> if the application is careful not to "release" plaintext to the UI until
the
> authenticity has been established, a streaming design exposes more program
> attack surface.
> 
protocol that
> comes along is more likely to use them without realising the issues and
thus the
> problem persists.
> 
> 
> Preferably, plaintext inputs would be chunked into reasonably large parts
(say
> 16KiB) and encrypted separately. The chunks only need to be large enough
that
> the overhead from the additional authenticators is negligible. With such a
> design, large messages can be incrementally processed without having to
deal
> with unauthenticated plaintext, and AEAD APIs can be safer. (Not to
mention
> that larger messages can be processed since AES-GCM, for one, has a ~64GiB
> limit for a single
> plaintext.)
> 
> Some thought is needed to ensure that the chunks are in the correct order
(i.e.
> by counting nonces), that the first chunk should be first (i.e. by
starting the
> nonce at zero) and that the last chunk should be last (i.e. by appending
an
> empty, terminator chunk with special additional data). But that's not
hard.
> 
> 
> Even with such a design it's still the case that an attacker can cause the
message
> to be detectably truncated. If you want to aim higher, an all-or-nothing
> transform can be used, although that requires two passes over the input
and I
> understand if it's sufficiently problematic that you don't want to do
that.

---

From: Adam Langley <[email-masked]>
Date: Fri, 2 Sep 2016 14:54:59 -0700

> than that suggested for HTTP.

Allowing very large messages is one, minor advantage. A much bigger
one is that large ciphertexts present a dilemma: either an
implementation can buffer the whole ciphertext/plaintext in memory and
process it all at once, or else it can decrypt it in a "streaming"
fashion.

The former is unappetising because messages may be larger than available memory.

The latter is dangerous because it encourages the implementation of
APIs that return unauthenticated plaintext and generally makes things
more fragile.

Chunking ciphertexts solves both of these issues.

> 4.  If you allow for random access, should all prior blocks be somehow

That's all correct and I mentioned a solution that used nonces from
zero upwards and the AD to distinguish an EOF chunk. That's not the
only design but, if you have random, per-message keys then it's
probably the most basic.

> and have the file left on the disk even though it is not complete.

That's the truncation issue that I mentioned at the end of my message.

The /last/ thing I want is for archive.tar to contain
attacker-controlled data, which a "streaming" interface allows.
Truncation is less bad than that.

Truncation can only be solved with two passes over the input I believe
(although I'd be happy to be proven wrong). If that's viable (and
perhaps, in CMS, it is?) then please let me know and I'm sure I can
get back to you with a solid proposal.

But I find that needing two passes often puts people off. Thus I was
only aiming to hit what I see as the most pressing issue at this
point: unauthenticated plaintext.

Cheers

AGL

---

From: Jim Schaad <[email-masked]>
Date: Fri, 2 Sep 2016 16:34:41 -0700

> From: [email-masked] [mailto:[email-masked]] On Behalf Of Adam
> Langley
> Sent: Friday, September 02, 2016 2:55 PM
> To: Jim Schaad <[email-masked]>
> Cc: [email-masked]
> Subject: Re: [Spasm] Chunking ciphertexts
> 
> > I have some problems with doing chunked encryption algorithms because
> > I am never sure what is being attempted with them.
> >
> > ml) is being done because it allows for random access decryption so
> > that it can be done by multiple streams.  You are suggesting that
> > another reason is so that one can have even larger encrypted objects
> > than is currently permitted by some algorithms.  The block size
> > suggested below is much larger than that suggested for HTTP.
> 
> Allowing very large messages is one, minor advantage. A much bigger one is that
> large ciphertexts present a dilemma: either an implementation can buffer the
> whole ciphertext/plaintext in memory and process it all at once, or else it can
> decrypt it in a "streaming"
> fashion.
> 
> The latter is dangerous because it encourages the implementation of APIs that
> return unauthenticated plaintext and generally makes things more fragile.
> 
> > One of the problems that I have is that you need to do a couple of
> > different things that I am never sure are properly covered:
> >
> That's all correct and I mentioned a solution that used nonces from zero
> upwards and the AD to distinguish an EOF chunk. That's not the only design but,
> if you have random, per-message keys then it's probably the most basic.
> 
> > If you are using stream APIs, what do you do if the first ten blocks
> > are fine, but then the eleventh block is messed up?  This fact then
> > needs to be propagated down the stream in some fashion so that correct
> > responses can be executed.  The last think you want is to execute
> >
> The /last/ thing I want is for archive.tar to contain attacker-controlled data,
> which a "streaming" interface allows.
> Truncation can only be solved with two passes over the input I believe (although
> I'd be happy to be proven wrong). If that's viable (and perhaps, in CMS, it is?)
> then please let me know and I'm sure I can get back to you with a solid proposal.

If you do two passes then you have killed the benefit that you listed, that you do not have the keep the entire message in memory.  Once you have the entire message in memory you can always do a decrypt in place so you at least do not to have two copies of it.  But doing two passes means that the entire message needs to be there at some point.

This is also going to be the same problem that non-CMS implementations are going to have with doing EdDSA in pure mode.  CMS already does a hash and sign so that problem does not exist.

Jim

> 
> But I find that needing two passes often puts people off. Thus I was only aiming
> to hit what I see as the most pressing issue at this

---

From: Adam Langley <[email-masked]>
Date: Fri, 2 Sep 2016 16:41:49 -0700

On Fri, Sep 2, 2016 at 4:34 PM, Jim Schaad <[email-masked]> wrote:
> If you do two passes then you have killed the benefit that you listed, that you do not have the keep the entire message in memory.

The whole message has to pass /though/ memory twice, but it doesn't
all have to be in memory at the same time. It's possible to do two
passes by reading it from the disk twice.

Cheers

AGL