Subject: Re: [openpgp] AEAD encrypted data packet with EAX

From: "brian m. carlson" <[email-masked]>
Date: Mon, 3 Jul 2017 16:00:56 +0000

On Sun, May 21, 2017 at 11:43:02PM +0000, brian m. carlson wrote:
> I have a proposed pull request for a streaming AEAD encrypted data
> packet using EAX mode[0].  I will send a patch shortly.
> 
> EAX is a block cipher mode combining CTR mode and OMAC.  It is similar
> to CCM and is considered secure.  It can be easily implemented securely
> in a variety of languages using the CBC and CTR modes available in most
> cryptographic libraries.
> 
> The packet allows for fixed-sized chunks from 64 bytes to 65536 bytes
> (or larger) in size and also permits streaming.  It contains truncation
> detection at the cost of 16 bytes of buffering.
> 
> I retained the AEAD algorithm octet so as not to need to overload one
> octet with cipher type and AEAD algorithm.  This allows us to use
> something like Poly1305 with both AES and ChaCha20 in the future.
> 
> I welcome feedback on this proposal.  If it's determined to be viable,
> I'd also like to see adjustments to the SKESK and Secret Key packets to
> add AEAD support.

Were there opinions on this proposal?  Do people like it, dislike it,
not care, etc?  I'm happy to try to revise or let the editors do that,
but it would be useful to get some feedback on it at all, even if it's
that people hate it and want something else.
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

---

From: Werner Koch <[email-masked]>
Date: Mon, 03 Jul 2017 18:41:11 +0200

> Were there opinions on this proposal?  Do people like it, dislike it,

I have an opinion on your proposal but wanted to give others time to
reply first ;-).  I have had too many other open tasks this year so that
my editorial work was too much delayed, I am sorry for this.

I have two points, briefly:

1. The prior discussion showed that it will be hard to find a common
   conclusion on what algorithm to use.  Thus instead of having one
   fixed algorithm, I will propose a modification to make the new packet
   format extensible.  I know that this had a lot of drawbacks and
   having only one algorithm would be far better than a bunch of
   algorithms which we may all need to implement.  But the advantage of
   allow other algorithms will give the implementers more options to
   to show in practice the advantages of different algorithms.

2. We really should have a way to early detect a corrupt message - not
   necessary an attack but for example a bit flip somewhere on the
   channel.  Inserting a running checksum (say, every 1GiB) would solve
   this.  Obviously this depends on the algorithms, so that the existing
   cipher state can be used for such a checksum.  A hackish way to that
   could be to take the internal state of the algorithm, hash it and
   insert it into the stream.  A cleaner solution would require several
   concatenated cipher streams.

Shalom-Salam,

   Werner

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

---

From: "brian m. carlson" <[email-masked]>
Date: Mon, 3 Jul 2017 17:06:28 +0000

>    to show in practice the advantages of different algorithms.

Yes, I tend to agree.  Did you feel the existing extensibility mechanism
in my proposal (cipher algo, AEAD algo, chunk size) was insufficient or
did you have something else in mind?

>    concatenated cipher streams.

I think my proposal actually implements that.  Since my chunk proposal
contains the chunk index (basically, an incrementing counter), as long
as we have the key, we can immediately tell if any chunk is corrupt
simply by knowing the chunk size and authentication tag length.  That
allows random-access to data if, for example, you know that all of your
data is uncompressed tar archives.

If we want something simpler in addition, we could reuse the CRC24 as
most implementations will require it for the ASCII armor format.
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

---

From: Werner Koch <[email-masked]>
Date: Mon, 03 Jul 2017 20:19:46 +0200

> did you have something else in mind?

Frankly, I answered out of my memory without reading your proposal
again.  Let's see:

  * A one-octet chunk size.

This is general enough for all algorithms.

  * A starting initialization vector of size specified by the AEAD
    algorithm.  This value MUST be unique and it MUST be unpredictable.

This seems to be specific for the selected AEAD mode.  Thus I would prefer
to put this into an algorithm specific section.  For ease of
describing it might be easier to put the next two items also into such
an AEAD specific section.

> as we have the key, we can immediately tell if any chunk is corrupt

Right.  I would prefer to have this algorithm specific, though.
Your description says:

  The chunk size octet specifies the size of chunks using the following
  formula (in C), where c is the chunk size octet:

        chunk_size = ((uint64_t)1 << (c + 6))

  An implementation MUST support chunk size octets with values from 0
  to 10.  An implementation MAY support other chunk sizes.  Chunk size
  octets with values larger than 127 are reserved for future extensions.

Thus this allowed for chunks from 64 to 65536 octets.  Given that larger
values are optional, implementations will need limit C to 10.  I
consider this too low for practical purposes.  We should require all
implementations to support the same range.

Given that we have a 64 bit counter the maximum value for C should be 57
- I would even say 56 so that we avoid signed and signed problems in the
number of octets.

> most implementations will require it for the ASCII armor format.

Better not.  That requires to run a second algorithm over the data.

Salam-Shalom,

   Werner

---

From: "brian m. carlson" <[email-masked]>
Date: Fri, 21 Jul 2017 22:21:50 +0000

> in a variety of languages using the CBC and CTR modes available in most

I've updated my proposal and will be sending out a series of three
patches shortly.  As Werner suggested, I've moved the IV requirements to
the mode specification and I've expanded the possible values of the
cipher type octet.

New in this proposal are patches for proposed text for a v5 SKESK packet
with AEAD and a secret key packet with AEAD.  These packets use a fixed
value of 10 for the chunk size octet (a chunk of 65536 bytes), which
essentially means that the entire encrypted data will be in one chunk,
even if we adopt post-quantum algorithms in the future.  This simplifies
implementation with a unified code path.

I welcome comments on this proposal with the goal of trying to get
consensus.
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

---

From: "brian m. carlson" <[email-masked]>
Date: Fri, 21 Jul 2017 22:27:16 +0000

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

diff --git a/middle.mkd b/middle.mkd
index c2447d5..166b575 100644
--- a/middle.mkd
+++ b/middle.mkd
@@ -2550,6 +2550,81 @@ 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.
+
+  * A one-octet chunk size.
+
+  * A starting initialization vector of size specified by the AEAD
+    algorithm.
+
+  * Encrypted data, the output of the selected symmetric-key cipher
+    operating in the given AEAD mode.
+
+  * A final, summary authentication tag for the AEAD mode.
+
+An AEAD encrypted data packet consists of one or more chunks of data.
+The plaintext of each chunk is of a size specified using the chunk size
+octet using the method specified below.
+
+The encrypted data consists of the encryption of each chunk of
+plaintext, followed immediately by the relevant authentication tag.  If
+the last chunk of plaintext is smaller than the chunk size, the
+ciphertext for that data may be shorter; it is nevertheless followed by
+a full authentication tag.
+
+For each chunk, the AEAD construction is given the packet header,
+version number, cipher algorithm octet, AEAD algorithm octet, chunk size
+octet, and an eight-octet, big-endian chunk index as additional
+data.  The index of the first chunk is zero.
+
+After the final chunk, the AEAD algorithm is used to produce a final
+authentication tag encrypting the empty string.  This AEAD instance is
+given the additional data specified above, plus an eight-octet,
+big-endian values specifying the total number of plaintext octets
+encrypted.  This allows detection of a truncated ciphertext.
+
+The chunk size octet specifies the size of chunks using the following
+formula (in C), where c is the chunk size octet:
+
+        chunk_size = ((uint64_t)1 << (c + 6))
+
+An implementation MUST support chunk size octets with values from 0
+to 56.  An implementation MAY support other chunk sizes.  Chunk size
+octets with other values are reserved for future extensions.
+
+A new random initialization vector MUST be used for each message.
+
+### {5.14.1} EAX Mode
+
+The only currently defined AEAD algorithm is EAX Mode
+[](#EAX).  This algorithm can only use block ciphers with 16-octet
+blocks.  The starting initialization vector and authentication tag are
+both 16 octets long.
+
+The starting initialization vector for this mode MUST be unique and
+unpredictable.
+
+The nonce for EAX mode is computed by treating the starting
+initialization vector as a 16-octet, big-endian value and
+exclusive-oring the low eight octets of it with the chunk index.
+
+The security of EAX requires that the nonce is never reused, hence the
+requirement that the starting initialization vector be unique.
+
 # {6}  Radix-64 Conversions
 
 As stated in the introduction, OpenPGP's underlying native
@@ -3087,6 +3162,16 @@ require the use of SHA-1 with the exception of computing version 4 key
 fingerprints and for purposes of the MDC packet.  Implementations
 SHOULD NOT use MD5 or RIPE-MD/160.
 
+## {9.5} AEAD Algorithms
+
+       ID  Algorithm
+ --------  ---------
+        1  EAX [](#EAX)
+ 100--110  Private/Experimental algorithm
+
+Implementations MUST implement EAX.  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 68651ba..85782ce 100644
--- a/template.xml
+++ b/template.xml
@@ -91,6 +91,17 @@
         <date></date>
         </front>
       </reference>
+
+      <reference anchor='EAX'>
+        <front>
+        <title>A Conventional Authenticated-Encryption Mode</title>
+        <author surname="Bellare" initials="M." />
+        <author surname="Rogaway" initials="P." />
+        <author surname="Wagner" initials="D." />
+        <date year="2003" month="April" />
+        </front>
+    </reference>
+
       <reference anchor='ELGAMAL'>
         <front>
         <title>A Public-Key Cryptosystem and a
-- 
2.14.0.rc0.284.gd933b75aa4

---

From: "brian m. carlson" <[email-masked]>
Date: Fri, 21 Jul 2017 22:27:18 +0000

---
 middle.mkd | 28 +++++++++++++++++++---------
 1 file changed, 19 insertions(+), 9 deletions(-)

diff --git a/middle.mkd b/middle.mkd
index 95ec44d..b1fecc1 100644
--- a/middle.mkd
+++ b/middle.mkd
@@ -356,7 +356,7 @@ unencrypted.  The MD5 hash function was always used to convert the
 passphrase to a key for the specified cipher algorithm.
 
 For compatibility, when an S2K specifier is used, the special value
-254 or 255 is stored in the position where the hash algorithm octet
+253, 254, or 255 is stored in the position where the hash algorithm octet
 would have been in the old data structure.  This is then followed
 immediately by a one-octet algorithm identifier, and then by the S2K
 specifier as encoded above.
@@ -364,9 +364,9 @@ specifier as encoded above.
 Therefore, preceding the secret data there will be one of these
 possibilities:
 
-       0:           secret data is unencrypted (no passphrase)
-       255 or 254:  followed by algorithm octet and S2K specifier
-       Cipher alg:  use Simple S2K algorithm using MD5 hash
+       0:                 secret data is unencrypted (no passphrase)
+       255, 254, or 253:  followed by algorithm octet and S2K specifier
+       Cipher alg:        use Simple S2K algorithm using MD5 hash
 
 This last possibility, the cipher algorithm number with an implicit
 use of MD5 and IDEA, is provided for backward compatibility; it MAY be
@@ -1960,10 +1960,13 @@ The packet contains:
   * Only for a version 5 packet, a one-octet scalar octet count of the
     next 3 optional fields.
 
-  * [Optional] If string-to-key usage octet was 255 or 254, a one-
+  * [Optional] If string-to-key usage octet was 255, 254, or 253, a one-
     octet symmetric encryption algorithm.
 
-  * [Optional] If string-to-key usage octet was 255 or 254, a
+  * [Optional] If string-to-key usage octet was 253, a one-octet AEAD
+    algorithm.
+
+  * [Optional] If string-to-key usage octet was 255, 254, or 253, a
     string-to-key specifier.  The length of the string-to-key
     specifier is implied by its type, as described above.
 
@@ -1984,8 +1987,10 @@ The packet contains:
     usage octet was 254, then a 20-octet SHA-1 hash of the
     plaintext of the algorithm-specific portion.  This checksum or
     hash is encrypted together with the algorithm-specific fields
-    (if string-to-key usage octet is not zero).  Note that for all
-    other values, a two-octet checksum is required.
+    (if string-to-key usage octet is not zero).  If the string-to-key
+    usage octet was 253, then an AEAD authentication tag is included
+    here.  Note that for all other values, a two-octet checksum is
+    required.
 
 Note that the version 5 packet format adds two count values
 to help parsing packets with unknown S2K or public key algorithms.
@@ -2009,7 +2014,12 @@ at the beginning of each new MPI value, so that the CFB block boundary
 is aligned with the start of the MPI data.
 
 With V4 and V5 keys, a simpler method is used.  All secret MPI values
-are encrypted in CFB mode, including the MPI bitcount prefix.
+are encrypted, including the MPI bitcount prefix.
+
+If the string-to-key usage octet is 253, the encrypted MPI values are
+encrypted as one combined plaintext exactly as an AEAD Encrypted Data
+packet with a chunk size octet of 10 would be.  This implicit chunk size
+octet is included in the normal calculations of additional data.
 
 The two-octet checksum that follows the algorithm-specific portion is
 the algebraic sum, mod 65536, of the plaintext of all the algorithm-
-- 
2.14.0.rc0.284.gd933b75aa4

---

From: "brian m. carlson" <[email-masked]>
Date: Fri, 21 Jul 2017 22:27:17 +0000

---
 middle.mkd | 27 ++++++++++++++++++++++++---
 1 file changed, 24 insertions(+), 3 deletions(-)

diff --git a/middle.mkd b/middle.mkd
index 166b575..95ec44d 100644
--- a/middle.mkd
+++ b/middle.mkd
@@ -1735,10 +1735,9 @@ message to be encrypted to a number of public keys, and also to one or
 more passphrases.  This packet type is new and is not generated by
 PGP 2.x or PGP 5.0.
 
-The body of this packet consists of:
+A version 4 Symmetric-Key Encrypted Session Key packet consists of:
 
-  * A one-octet version number.  The only currently defined version
-    is 4.
+  * A one-octet version number with value 4.
 
   * A one-octet number describing the symmetric algorithm used.
 
@@ -1766,6 +1765,28 @@ specifier MUST use a salt value, either a Salted S2K or an
 Iterated-Salted S2K.  The salt value will ensure that the decryption
 key is not repeated even if the passphrase is reused.
 
+A version 5 Symmetric-Key Encrypted Session Key packet consists of:
+
+  * A one-octet version number with value 5.
+
+  * A one-octet cipher algorithm.
+
+  * A one-octet AEAD algorithm.
+
+  * A string-to-key (S2K) specifier, length as defined above.
+
+  * A starting initialization vector of size specified by the AEAD
+    algorithm.
+
+  * The encrypted session key itself, which is decrypted with the
+    string-to-key object using the given cipher and AEAD mode.
+
+  * A final, summary authentication tag for the AEAD mode.
+
+The encrypted session key is encrypted exactly as an AEAD Encrypted Data
+packet with a chunk size octet of 10 would be.  This implicit chunk size
+octet is included in the normal calculations of additional data.
+
 ## {5.4} One-Pass Signature Packets (Tag 4)
 
 The One-Pass Signature packet precedes the signed data and contains
-- 
2.14.0.rc0.284.gd933b75aa4

---

From: "brian m. carlson" <[email-masked]>
Date: Tue, 25 Jul 2017 01:02:43 +0000

> +blocks.  The starting initialization vector and authentication tag are

I received an inquiry off-list about the limitation on 16-byte block
ciphers here.  While EAX mode does indeed support 8-byte block ciphers,
the authentication tag is limited to 64 bits.  Combined with the fact
that many implementations will use a large number of chunks for large
messages, I felt the risk of forgery was too high.

However, should the working group disagree, we can remove this language,
or it can be modified to reflect that we require it but the underlying
standard does not.
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

---

From: Werner Koch <[email-masked]>
Date: Tue, 25 Jul 2017 21:03:53 +0200

> the mode specification and I've expanded the possible values of the

Thanks.  I pushed your patches so that we can use this as a starting
point.  I made two changes:

 - Assigned tag 20 for the AEAD Encrypted data packet
 - Removed a probably left-over sentence:

    An implementation MUST support chunk size octets with values from 0
    to 56.  An implementation MAY support other chunk sizes.  Chunk size
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    octets with other values are reserved for future extensions.

and also pushed this to indicate the support for AEAD

--8<---------------cut here---------------start------------->8---
@@ -1594,6 +1594,9 @@ #### {5.2.3.24} Features
 
     0x01 - Modification Detection (packets 18 and 19)
 
+    0x02 - AEAD Encrypted Data Packet (packet 20) and version 5
+           Symmetric-Key Encrypted Session Key Packets (packet 3)
+
 If an implementation implements any of the defined features, it SHOULD
 implement the Features subpacket, too.
--8<---------------cut here---------------end--------------->8---

> value of 10 for the chunk size octet (a chunk of 65536 bytes), which

I am fine with this.

> I welcome comments on this proposal with the goal of trying to get

Do we have an RFC for EAX Mode?  That would make a better reference.

I think we should have a more verbose description of the AEAD chunk
construction in particular related to the use of the IV/nonce in the
chunks.

Salam-Shalom,

   Werner

p.s.
I uploaded a rendered version to https://dev.gnupg.org/F167170