Subject: [openpgp] Pull request for AEAD encrypted data packet with GCM

From: "brian m. carlson" <[email-masked]>
Date: Mon, 13 Feb 2017 01:06:58 +0000

I've opened a pull request that defines an AEAD encrypted data packet
using GCM.  This work is necessarily incomplete, because it doesn't
define a new version of the symmetrically-encrypted data packet, which
we'd want, and it doesn't define a new encoding for the secret key
packet.

GCM seems to be the uncontroversial choice here.  It's used in TLS and
other protocols, and it provides adequate security.  It isn't encumbered
by patents.  It performs reasonably well.

Other alternatives include OCB and CTR with HMAC.  I personally object
to OCB because it's patented, and while I like CTR with HMAC, it was my
impression that the rest of the working group would not share my
opinion.

While I understand that we are not interested in adding general
extensibility to the protocol, I opted to include an octet for the AEAD
algorithm in case someone wants to define OCB or something like
ChaCha20-Poly1305.  ChaCha20 cannot use GCM, but it is a popular
algorithm that performs well on many architectures and is well-suited to
embedded systems.

I've proposed this as a starting point and welcome further comments.

[0] https://gitlab.com/openpgp-wg/rfc4880bis/merge_requests/2
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

---

From: Jon Callas <[email-masked]>
Date: Mon, 13 Feb 2017 17:09:49 -0800

> On Feb 12, 2017, at 5:06 PM, brian m. carlson <[email-masked]> wrote:
> 

I'll request that another mode than GCM be used. In particular, I disagree with it being "uncontroversial." It's the most controversial mode you could pick.

GCM is very brittle. It breaks in very bad ways if you aren't careful with nonces/tags. There are many cases of people misusing it and getting worse than no security. I state that because if you *think* you're getting authenticated data, but it's actually been altered in transit, and that will likely cause issues in the receiving state machine.

This paper <https://eprint.iacr.org/2016/475.pdf> is all about real-world cases of unintentional misuse of GCM.

Furthermore, the multiply in GHASH is slow in software. Yes, there are hardware instructions in high-end Intel and ARM processors, but if you do it on lower-end processors or in something like javascript, it's a pain. If you have to conditionally do hardware or software, it makes implementation more difficult.

I think GCM is fine to use in some circumstances, like high-speed VPN boxes, but it's the AEAD mode that comes from ACME. If you are Wile E. Coyote it is going to blow up in your face.

Perhaps most rigorously, the real problem with GCM is GHASH. Anything with GHASH is worrisome.

Your mention of alternatives was incomplete, so I'll bring alternatives up.

We all really want to use OCB. If you look at <http://web.cs.ucdavis.edu/~rogaway/ocb/ocb-faq.htm> which is Rogaway's page on it. While it is patented, there are some broad license grants. There's one for open source software, as well as one for non-military software. He's also given one OpenSSL. I'll bet that if someone asked him for a grant for the OpenPGP protocol, he'd probably do it. As it is, the large-swath grants for it (open source, and non-military) suggest that we could either say that's good enough for us or ask for another grant. But if we don't want to, we don't want to. OCB is the mode everyone really wants to use, but I don't want get wrapped around the axle on the controversy here, either.

Beyond OCB, though, there are a lot of alternatives:

* CCM. CCM has been my go-to for AEAD in many cases. It is easy to understand and works well. It is easy to get right. I think that this is an important property, being easy to get right. Its major disadvantage, being a two-pass algorithm, is not that bad for OpenPGP because we have streaming packets in the core protocol. Nonetheless, Rogaway's own paper about it (see the OCB link above for it) is not a bad paper, but remember that Rogaway is arguing against CCM in favor of either OCB or his own EAX.

* ChaCha20+Poly1305. Many of the cool kids are using it. It's fast, reasonably okay to implement, it's in TLS 1.3, and wouldn't be a bad choice. The major criticism I can see is that ChaCha20 is a stream cipher not a streaming mode on a block cipher (like AES or Twofish or whatever). I think most of the legitimate criticisms of it are blunted by its being used a lot in the TLS world.

* SIV. SIV is another Rogaway mode, it's unencumbered, has resistance to misuse, and I can't think of anything bad to say about it other than a plea not to use the GCM version because GHASH. Many cool kids are using it.

* EAX. I tend to discount EAX because it's not OCB, not CCM (which was created to be Not OCB), and not SIV. I wouldn't scream, though. I just think that in this day, it doesn't have an advantage over any non-GCM AEAD thing.

* CTR+HMAC. Like you, I mention it for completeness. But while I think that any of the above would be better, I think it is again better than GCM. It's not sexy but it works, and it's harder to screw up than many things.

So to sum up, I think that GCM is actually controversial and dangerous for generic use.

	Jon

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 14 Feb 2017 01:24:24 +0000

Just on one point...

On 14/02/17 01:09, Jon Callas wrote:
> We all really want to use OCB. If you look at
> <http://web.cs.ucdavis.edu/~rogaway/ocb/ocb-faq.htm> which is
> Rogaway's page on it. While it is patented, there are some broad
> license grants.

A recurring issue with OCB in other contexts has been that it
it not only Rogaway's IPR that is at issue. Despite (what I
think is) his very flexible and reasonable way of handling his
own IPR, and even his efforts to get others to play ball, there
are multiple other parties involved, not all of whom are IIUC
equally reasonable (according to my personal view of what's
reasonable).

I don't know that that situation has resolved itself favourably
in any case to date. I'd be happy if it had though, so please
do follow up this with good news, if such exists.

This issue was discussed on both the CFRG and TLS lists, maybe
a year or two ago, so interested folks would benefit from
checking those archives for OCB related threads.

Cheers,
S.

PS: Note that I'm not stating any opinion pro- or contra- GCM
nor any other AEAD construct here.

---

From: "brian m. carlson" <[email-masked]>
Date: Tue, 14 Feb 2017 01:28:17 +0000

> Beyond OCB, though, there are a lot of alternatives:

I think OCB is a non-starter because of the patent.  It doesn't matter
what the patent situation actually *is*.  It matters what Red Hat's
lawyers and the lawyers of thousands of companies worldwide think it
*might be*.  Red Hat refused to implement ECC for a long time because
they thought it *might* have potential patent problems, and the
uncertainty was enough to seriously delay modern ECC support on a
significant portion of servers.  I don't want to write a spec that is
going to be unusable or less usable because of the patent.

OCB is also not implemented in most crypto libraries (for the above
reason).  If we have people writing code in web browsers and scripting
languages, we want something that Web Crypto and OpenSSL are going to
support.  Otherwise, we're going to have people writing crypto
implementations in JavaScript and Ruby and whatnot, and those aren't
going to be side-channel safe.  People are already doing this, so we
should consider it as a use case.

> * ChaCha20+Poly1305. Many of the cool kids are using it. It's fast, reasonably okay to implement, it's in TLS 1.3, and wouldn't be a bad choice. The major criticism I can see is that ChaCha20 is a…

That's why my proposal (which I will send a patch to the list for
shortly) proposed an octet for AEAD algorithm.  We can implement
ChaCha20 as a cipher and Poly1305 as an AEAD algorithm.  I support doing
this, but doing just ChaCha20-Poly1305 excludes a secure implementation
of all the block ciphers that we currently have.  We need something that
works with AES.

> * CTR+HMAC. Like you, I mention it for completeness. But while I think that any of the above would be better, I think it is again better than GCM. It's not sexy but it works, and it's harder to scr…

That's why I like it.  Assuming you have a constant time AES
implementation, you can implement CTR and HMAC in constant time in
almost any language.  Those algorithms are also implemented in most
libraries.
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

---

From: "brian m. carlson" <[email-masked]>
Date: Tue, 14 Feb 2017 01:29:53 +0000

---
 middle.mkd   | 46 ++++++++++++++++++++++++++++++++++++++++++++++
 template.xml | 11 +++++++++++
 2 files changed, 57 insertions(+)

diff --git a/middle.mkd b/middle.mkd
index 5182c7d..e842938 100644
--- a/middle.mkd
+++ b/middle.mkd
@@ -2483,6 +2483,42 @@ packet length.  The reason for this is that the hashing rules for
 modification detection include a one-octet tag and one-octet length in
 the data hash.  While this is a bit restrictive, it reduces complexity.
 
+## {5.14} AEAD Encrypted Data Packet (Tag 18)
+
+This packet contains data encrypted with an authenticated encryption and
+additional data (AEAD) construction.  When it has been decrypted, it
+will typically contain other packets (often a Literal Data packet or
+Compressed Data packet).
+
+The body of this packet consists of:
+
+  * A one-octet version number.  The only currently defined value
+    is 1.
+
+  * A one-octet cipher algorithm.
+
+  * A one-octet AEAD algorithm.
+
+  * An initialization vector of size specified by the AEAD algorithm.
+    This value MUST be unique and it MUST be unpredictable.
+
+  * Encrypted data, the output of the selected symmetric-key cipher
+    operating in the given AEAD mode.
+
+  * The authentication tag for the AEAD mode.
+
+The AEAD construction is given the packet header, version number, cipher
+algorithm octet, and AEAD algorithm octet as additional data.
+
+### {5.14.1} Galois Counter Mode
+
+The only currently defined AEAD algorithm is Galois Counter Mode
+[](#GCM).  This algorithm can only use block ciphers with 16-byte
+blocks.  The initialization vector is 12 bytes long.
+
+The security of GCM requires that the counter is never reused, hence the
+requirement that the initialization vector be unique.
+
 # {6}  Radix-64 Conversions
 
 As stated in the introduction, OpenPGP's underlying native
@@ -3014,6 +3050,16 @@ algorithm.
 Implementations MUST implement SHA-1.  Implementations MAY implement
 other algorithms.  MD5 is deprecated.
 
+## {9.5} AEAD Algorithms
+
+       ID  Algorithm
+ --------  ---------
+        1  GCM [](#GCM)
+ 100--110  Private/Experimental algorithm
+
+Implementations MUST implement GCM.  Implementations MAY implement
+other algorithms.
+
 # {10} IANA Considerations
 
 OpenPGP is highly parameterized, and consequently there are a number
diff --git a/template.xml b/template.xml
index 9ea1582..f52521e 100644
--- a/template.xml
+++ b/template.xml
@@ -144,6 +144,17 @@
         </front>
       </reference>
 
+      <reference anchor='GCM'>
+        <front>
+        <title>Recommendation for Block Cipher Modes of Operation:
+            Galois/Counter Mode (GCM) and GMAC (SP 800-38D)</title>
+        <author>
+          <organization>NIST</organization>
+        </author>
+        <date year="2007" month="November" />
+        </front>
+      </reference>
+
       <reference anchor="HAC">
         <front>
           <title>Handbook of Applied Cryptography</title>
-- 
2.11.0

---

From: Jon Callas <[email-masked]>
Date: Mon, 13 Feb 2017 17:32:45 -0800

> On Feb 13, 2017, at 5:24 PM, Stephen Farrell <[email-masked]> wrote:
> 

I have no disagreement with this. I am constantly pained that this is a mess, because OCB *is* what we all really want to use.

	Jon

---

From: Jon Callas <[email-masked]>
Date: Mon, 13 Feb 2017 18:05:34 -0800

> On Feb 13, 2017, at 5:28 PM, brian m. carlson <[email-masked]> wrote:
> 

[OCB discussion removed because we're all in violent agreement.]

> of all the block ciphers that we currently have.  We need something that

Forgive my being out of the loop on this and behind in document reading.

4880 uses CFB implicitly with two flavors (regular and with MDC). Historically, OpenPGP leaves lots of parameterization around which is great for experimentation, but hell on test matrixes. One could parameterize a new packet in which there was a cipher parameter and an integrity parameter. Thus, one could have a the matrix [AES(key size), Twofish(key size), ...., whatever; CCM, SIV, HMAC, ...]. (The clever reader might note that HMAC leads to its own parameter.) Or one could have a parameter for a full thing like AES128-SIV, or AES256-HMAC-SHA512. I recommend the latter, myself. 

In that case, just pick decent parameters on ChaCha20+Poly1305 and be done. This is slightly important because this would be the first time OpenPGP used a stream cipher per se.

Historic note: OpenPGP dates from a time when there were a lot of good arguments for a lot of options. Okay, there were better arguments than there are now. :) You know, should we use IDEA, CAST5, or Blowfish? Should we allow DSA to be used RIPEMD-160 because SHA-1 was created by the NSA and some people think it's backdoored. We also in those days wanted maximum consensus on getting 2440 done as fast as possible. That led to a lot of parameters and then contraction of those parameters later when people never implemented the algorithm they really wanted. I think this is an opportunity to collapse option explosion by just having AE suite parameters. This would allow some generosity in parameters without total option explosion.

> almost any language.  Those algorithms are also implemented in most

This is also an argument in favor of CCM, SIV, and perhaps others.

One final thing that just occurred to me. If we really, really want this to preserve some OpenPGP goodness, there would also be a preference packet to allow someone to state what they do and don't speak. 

	Jon

---

From: "brian m. carlson" <[email-masked]>
Date: Tue, 14 Feb 2017 02:26:45 +0000

> In that case, just pick decent parameters on ChaCha20+Poly1305 and be done. This is slightly important because this would be the first time OpenPGP used a stream cipher per se.

My patch implements exactly that: a cipher byte, and an AEAD algorithm
byte (it uses GCM, but it sounds like we want to change that).  I feel
like this provides us the flexibility we need without providing too many
options, especially since I get the impression we may want both block
and stream ciphers).

If we did CTR+HMAC, I'd propose CTR+HMAC-SHA512 and CTR+HMAC-SHA-3-512
as the AEAD algorithms (just hardcoding those as AEAD algorithm bytes).
If we did EAX or SIV, that would logically be the AEAD algorithm.  If we
additionally did ChaCha20, I'd define Poly1305 as the AEAD algorithm in
the TLS way.

I was not considering allowing further parameterization beyond that
point, as that's a great way to let people pick bad options.

We do need to preserve the existing cipher byte values for AES Key Wrap
in coordination with ECDH, though.

> Historic note: OpenPGP dates from a time when there were a lot of good arguments for a lot of options. Okay, there were better arguments than there are now. :) You know, should we use IDEA, CAST5,…

I think we're in agreement.

> This is also an argument in favor of CCM, SIV, and perhaps others.

I think the two-pass nature of CCM is undesirable, but I'd be fine with
EAX or SIV.  I feel confident I could implement those in a constant time
manner in a variety of languages given a constant-time AES-ECB and
AES-CTR.
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

---

From: Werner Koch <[email-masked]>
Date: Tue, 14 Feb 2017 09:49:34 +0100

> I have no disagreement with this. I am constantly pained that this is a mess, because OCB *is* what we all really want to use.

From our experience with adding the MDC feature to OpenPGP we known that
it will take several years until the majority of code has been upgraded
to make use of a new feature.  The mentioned non-Rogaway patents were
filed around 2001 and thus will expire 4 to 7 years.  Which would match
the time I expect to get OCB mode actually deployed (or any other new
mode).

Sure there are also follow up patents but given that they are owned by
IBM they may even be an advantage against patent trolls.  But this has
likely already been discussed in the context of TLS.

Shalom-Salam,

   Werner

-- 
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.

---

From: Werner Koch <[email-masked]>
Date: Tue, 14 Feb 2017 10:17:42 +0100

Hi,

putting the patent mess aside, there are also a few other question
involved in a new encryption mode:

 1. Exactly one mode defined by a new packet number
    or a new packet with a parameter to define the mode?
 
 2. Bind the mode to a certain cipher algorithm?  For example only allow
    a mode with AES.

 3. How can we do early detection of corruption?  When decrypting
    several gigs we should be able to detect corrupted data after having
    processed, say, one gig.  Shall such a feature be configurable?
    Shall we link it to partial length headers.

My ideas here are:

 re 1. A new packet with a parameter to define the actual mode.  Make
       one mode mandatory.  Additional parameters should have a length
       header so that parsers have an easier way to parse the header
       even if they don't implement that mode.
   
       The rational for this is to allow for some experimentation and
       separate the packet format from the finally chosen mandatory
       mode.

 re 2: Binding a mode to an algorithm makes testing easier.  This will
       also make implementing stream cipher modes easier because it
       allows to blur the distinction between cipher algorithm and mode.

 re 3: The simplest idea would be to use fixed chunks of the ciphertext
       and either link them together using a counter or the hash of the
       previous authentication tag.  The packet header would give the
       length of the chunks in blocks.  It needs to be decided whether a
       final one-block chunk is okay.

Salam-Shalom,

   Werner

---

From: Tom Ritter <[email-masked]>
Date: Tue, 14 Feb 2017 10:41:13 -0600

>        final one-block chunk is okay.

This seems the same question/solution of some sort of authenticated
chunked-streaming mode.  I mentioned this a couple years ago but
didn't get much discussion:
https://www.ietf.org/mail-archive/web/openpgp/current/msg07546.html

-tom

---

From: Werner Koch <[email-masked]>
Date: Tue, 14 Feb 2017 21:14:33 +0100

> https://www.ietf.org/mail-archive/web/openpgp/current/msg07546.html

for easier reference, here is Tom's mail:

    Date: Tue, 24 Mar 2015 07:25:31 -0500

  Adam's post on streaming API's has been posted before:
  <https://www.imperialviolet.org/2014/06/27/streamingencryption.html>
  
  The same problem is the root cause of the Java GCM CipherInputStream
  issue: <http://blog.philippheckel.com/2014/03/01/cipherinputstream-for-aead-modes-is-broken-in-jdk7-gcm/>
  
  But I haven't seen any discussion of Adam's point that one _can_
  construct a format for chunking and authenticating the chunks (and
  ordering thereof) to provide authenticated streaming. And that someone
  has already done so:
  <https://github.com/kaepora/miniLock#4-file-encryption>
  
  I think support for a mode like this would be good to consider, and I
  think if IPR allows it, a fully-specified design for it is a good
  place to start.
  
  -tom

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 15 Feb 2017 03:34:55 +0000

Jon Callas <[email-masked]> writes:

>I'll request that another mode than GCM be used. In particular, I disagree
>with it being "uncontroversial." It's the most controversial mode you could
>pick.

+1.  However the adjective I'd use for GCM is most trendy, not necessarily
most controversial.  It's the mode you use without thinking about it
because... um, because everyone says its cool.  Like MongoDB, or Go, or
Angular.js, or Bimodal IT.

>GCM is very brittle. It breaks in very bad ways if you aren't careful with
>nonces/tags. There are many cases of people misusing it and getting worse
>than no security. I state that because if you *think* you're getting
>authenticated data, but it's actually been altered in transit, and that will
>likely cause issues in the receiving state machine.

+1 again.  You can take something like AES-CBC + HMAC and abuse it as much as
you want, e.g. by memsetting the IV to all zeroes on each block, and at most
you degrade to ECB, with no effect on the MAC's security.  OTOH do that with a
single IV in GCM (== CTR) mode (so you get a repeated IV) and you get a
catastrophic loss of security.  CTR is RC4 all over again.

>Furthermore, the multiply in GHASH is slow in software. 

Again, and at the risk of sounding like the Callas fan club... 

GCM is a dangerously easy to misuse encryption mode paired with a slow, also
failure-prone MAC.  If you want a minimal-fuss AEAD mode, just turn the
current encryption into encrypt-then-MAC.  It's a very minimal change, append
an HMAC to the end of the existing encrypted data.

>I think that GCM is actually controversial and dangerous for generic use.

Not sure about controversial since it's so trendy that most people don't think
about it but just use it, but it's certainly too dangerous for general use.

Peter.

---

From: Derek Atkins <[email-masked]>
Date: Fri, 17 Feb 2017 11:19:21 -0500

+1 for your suggestions, Werner.

-derek

-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant