Re: [openpgp] AEAD Chunk Size

"Neal H. Walfield" <neal@walfield.org> Thu, 07 March 2019 16:11 UTC

Return-Path: <neal@walfield.org>
X-Original-To: openpgp@ietfa.amsl.com
Delivered-To: openpgp@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id CC642127876 for <openpgp@ietfa.amsl.com>; Thu, 7 Mar 2019 08:11:29 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 6u4Inq90hChW for <openpgp@ietfa.amsl.com>; Thu, 7 Mar 2019 08:11:22 -0800 (PST)
Received: from mail.dasr.de (mail.dasr.de [217.69.77.164]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 189D7124184 for <openpgp@ietf.org>; Thu, 7 Mar 2019 08:11:21 -0800 (PST)
Received: from p54abd93f.dip0.t-ipconnect.de ([84.171.217.63] helo=chu.huenfield.org.walfield.org) by mail.dasr.de with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.86_2) (envelope-from <neal@walfield.org>) id 1h1vc7-0007EH-4u for openpgp@ietf.org; Thu, 07 Mar 2019 16:11:19 +0000
Date: Thu, 07 Mar 2019 17:11:18 +0100
Message-ID: <87mum6ekbd.wl-neal@walfield.org>
From: "Neal H. Walfield" <neal@walfield.org>
To: openpgp@ietf.org
In-Reply-To: <871s3qd4yg.fsf@wheatstone.g10code.de>
References: <87mumh33nc.wl-neal@walfield.org> <871s3qd4yg.fsf@wheatstone.g10code.de>
User-Agent: Wanderlust/2.15.9 (Almost Unreal) SEMI-EPG/1.14.7 (Harue) FLIM/1.14.9 (=?ISO-8859-4?Q?Goj=F2?=) APEL/10.8 EasyPG/1.0.0 Emacs/24.5 (x86_64-pc-linux-gnu) MULE/6.0 (HANACHIRUSATO)
MIME-Version: 1.0 (generated by SEMI-EPG 1.14.7 - "Harue")
Content-Type: text/plain; charset=US-ASCII
Archived-At: <https://mailarchive.ietf.org/arch/msg/openpgp/WvaisWDd9WzoKXL1FyHDeZNtZ2U>
Subject: Re: [openpgp] AEAD Chunk Size
X-BeenThere: openpgp@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "Ongoing discussion of OpenPGP issues." <openpgp.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/openpgp>, <mailto:openpgp-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/openpgp/>
List-Post: <mailto:openpgp@ietf.org>
List-Help: <mailto:openpgp-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/openpgp>, <mailto:openpgp-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 07 Mar 2019 16:11:30 -0000

Hi Werner,

Thanks for following up.

At Fri, 01 Mar 2019 15:50:15 +0100,
Werner Koch wrote:
> On Wed, 27 Feb 2019 11:51, neal@walfield.org said:
> > Consequently, I propose not only imposing a reasonable ceiling on the
> > chunk size that even small embedded devices with a cortex M0 could
> > handle, but to simply fix the parameter to 16 KiB.  It's not clear to
> 
> Without sufficient storage a smaller chunk size does not help you in any
> way.  You can still run a truncation attack and by that time the
> preceding chunks have already been processed in some way because, well,
> there was no way to store the entire message.  Without the final chunk
> you have an incomplete and thus unauthenticated message because the
> sender authenticated the entire message and not certain parts of it.

It's true that a smaller chunk size doesn't provide protection against
truncation attacks.  And, I agree with you that for the receiver to
protect itself against truncation attacks, it can only release the
plaintext after it has authenticated the whole message, which it can
only do if it buffers the whole message.  But, I strongly disagree
that a smaller chunk size does not help us in any way: even in the
face of truncation attacks, AE dramatically increases the security of
streaming.

AE provides ciphertext integrity [1].  Ciphertext integrity means that
the ciphertext has been authenticated.  That is, used correctly, AE
would stop an attack that modifies the ciphertext, like EFAIL.

  [1] See for instance Chapter 9 of A Graduate Course in Applied
  Cryptography by Dan Boneh and Victor Shoup for an explanation:

  https://crypto.stanford.edu/~dabo/cryptobook/BonehShoup_0_4.pdf

Since ciphertext integrity is guaranteed at the chunk granularity, the
ability to buffer a single chunk is sufficient to ensure ciphertext
integrity.

Now, if we admit steaming, and historically, OpenPGP has been
streaming friendly, then chunks must be small enough to fit in the
receiver's available buffer space.  This is essential, because the
decryption function must reject chunks that it can't authenticate [2];
releasing unauthenticated plaintext break's AE's security guarantees.

  [2] RFC 5116, Section 2.2: "[The authenticated decryption operation]
  has only a single output, either a plaintext value P or a special
  symbol FAIL that indicates that the inputs are not authentic."

  https://tools.ietf.org/html/rfc5116#section-2.2

On the other hand, if if we prohibit streaming, well, no, someone is
going to do it anyway.  So, we should just accommodate it as best we
can.

Given streaming, for me, the logical consequence is that we need to
somehow figure out an appropriate chunk size (or sizes).  Since the
sender can rarely make a sensible choice, and the chunk size doesn't
change AEAD's security properties, I've concluded that the most
sensible choice maximizes the number of devices that can decrypt
messages, which means making the chunk size as small as possible
without adversely impacting performance, e.g., 16 kiB or 256 kiB.

(Note: using a small chunk size doesn't mean that an implementation
has to release a chunk as soon as it is authenticated.  An
implementation can frustrate truncation attacks by ensuring that at
least, say, 25 MB of data remain buffered as long as it has not
encountered the end of the file.  FWIW, this is what Sequoia does.)


Let's assume that there are cases where we don't care about ciphertext
integrity, and a larger chunk size is better for some reason.  To
accommodate these cases, we could allow implementations to emit
unauthenticated data if a large chunk size is used.  We can even fix
the threshold in the specification so that senders can be sure that
messages that need ciphertext integrity are processed in a more secure
manner.

Unfortunately, some basic testing using a hacked version of Sequoia
suggests that an attacker can just take a message with a chunk size <
X and change the chunk size to be larger than X, and Sequoia will
happily emit the first chunk, because the chunk size parameter is only
checked after the first chunk is authenticated!  Ouch.

But, it's worse.  We can further defeat any opportunistic buffering
without appending a lot of garbage by wrapping the AEAD packet in a
Compression packet that is jammed at the end with a decompression
bomb.  Thus, the size of the message is only marginally larger than
the original message!

For me, this means that if we want AEAD's security properties, and I
think we do, we can't allow implementations to emit unauthenticated
plaintext.  Although we can write in the specification that
implementations MUST return "EBUYABIGGERCOMPUTER" if the chunk size is
too large, implementors will almost certainly ignore this, because
security must not get in the way of a user getting her job done.  In
fact, there is already an OpenPGP implementation that does this.  The
better way, I think, is to make it hard to do it wrong.  And that
means using a small, fixed chunk size.


If my argumentation and authority are too weak, perhaps Adam Langley
can convince you.  In his 2015 talk, he addresses exactly this problem
and why it is essential to support chunking even though it enables
truncation attacks.  The relevant discussion starts at 18:20, but the
most important bit (quoted below) starts at 22:43:

  Let's say the attacker does cut here.  They can only cut between
  chunks, because you'll figure that you.  But, they cut here.  You
  will know that it is not the correct end, because you never saw this
  tag on the AD.  But, if you are piping it straight into bash, the
  attacker still managed to truncated things.  The only way around
  this is to buffer the whole thing to disk before you release any
  plain text.  And, now you might think, "well, if I'm doing that, why
  did I put all this effort into chunking?"

  And, I'd like to do a quick aside here on what I call Adam's rule of
  weak crypto.  Another common thing that people come up with is---and
  suggest---is that they've done a careful analysis and they only need
  n-bit security where n is 80, or, if it is particularly weak, 40,
  and they have a very carefully argued plan about why what they are
  protecting is almost meaningless.  Like, they almost wouldn't bother
  with cryptography and they've got very tight bandwidth overheads,
  like bluetooth LE is a very common one.  And, so they are going to
  do 40-bit security or something similar.  And, they're correct.
  Their argument is perfectly reasonable.

  They still shouldn't do it.  They reason is that the Internet is
  built out of whatever was laying around.  It's like children with
  lego.  Things are never designed, you'll carefully reasoned argument
  about why this is completely correct will be discarded almost
  immediately.  And in the future, someone you've never met, and may
  never met, and may never talk to, will pick up your think and go:
  "oh, it's cryptography, right, this is fine, I'll build on it".  And
  then 10 years down the road, we find we have some massive
  societal-wide flaw, in some very important system, because they
  built it out of your weak system, never understanding the basis.

  So, you should still do [AEAD chunking], because if your argument is
  that we need to buffer everything, because of truncation attacks, so
  we're going to buffer everything, so we're going to have one huge
  chunk, because it doesn't make any difference, someone will come
  along in the future, they will discard your very carefully reasoned
  argument, they will go: "oh, I'm running on an embedded system, I
  don't have enough disk space, my messages are too large", and they
  will stream it, and it is still your fault, even though they screwed
  up.  So, for the people who are going to stream it, you should do as
  well as you can, which is [AEAD chunking].

  Yahoo Trust Unconference: TLS, Adam Langley (2015)
  https://finance.yahoo.com/video/yahoo-trust-unconference-tls-adam-223046696.html?guccounter=1

> Let me repeat it again: The chunking was introduced for just one
> purpose: To be able to detect rare transmission errors earlier than at
> the end of the message.

I agree that AEAD helps detect transmission errors earlier.  But, AEAD
does so much more than that.  In particular, it prevents attacks like
EFAIL.  It seems to me that it's worth adapting to this new threat.

Even if everyone accepts that the AEAD packet should only be used for
detecting transmission errors early, then in the very least, we need
to rename it.  AEAD has a specific technical meaning, and as currently
realized, 4880bis makes it very hard to meet those expectations.  This
will come back and bite us in the foot.

> For large pipes large chunks are a sensible
> choice.

I don't understand this argument.  The buffer size ought to be
independent of the chunk size.  AEAD doesn't say that as soon as a
chunk is authenticated it must be released; if you want, your
implementation can buffer 128 megabytes of data even if AEAD uses 16
kilobyte chunks.




I'd like to summarize your concerns as I understand them.  Please
correct me, add anything that you haven't yet mentioned, or fill in
something that I left out.

  1. Because AEAD doesn't protect against truncation attacks, streaming
     is as insecure as it ever was.

  2. The sole purpose of AEAD chunking is to detect transmission
     errors early.

  3. Small chunk sizes are bad for IPC.

My reactions:

  1. Although AEAD doesn't protect against truncation attacks, it does
     increase protection, because it would protect against ciphertext
     modifications as done in EFAIL.

  2. Perhaps when AEAD was introduced that was the sole reason, but
     with a small tweak, AEAD can be used to increase security in
     other settings.

  3. You don't have to release chunks as soon as they are
     authenticated, so you can make your buffer really large, if you
     like.



If you are adverse to changing packet 20, then let's just mark 20 as
reserved and create a new packet, 21, which changes the semantics.


Thanks,

Neal