[openpgp] AEAD encrypted data packet with EAX

[brian m. carlson]

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.

[0] https://gitlab.com/openpgp-wg/rfc4880bis/merge_requests/4

[brian m. carlson]

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

diff --git a/middle.mkd b/middle.mkd
index c2447d5..b240a5e 100644
--- a/middle.mkd
+++ b/middle.mkd
@@ -2550,6 +2550,78 @@ 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. 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.
+
+ * 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 10. An implementation MAY support other chunk sizes. Chunk size
+octets with values larger than 127 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 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 +3159,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
@@ -4485,6 +4567,10 @@ SHOULD be rejected.
- Although technically possible, the EdDSA algorithm MUST NOT be
used with a digest algorithms weaker than SHA2-256.

+ - Implementations should consider limiting chunk sizes for AEAD
+ algorithms to avoid denial-of-service attacks when decrypting
+ messages.
+

OpenPGP was designed with security in mind, with many smart,
intelligent people spending a lot of time thinking about the
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

[brian m. carlson]

Post by brian m. carlson
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.

[Werner Koch]

Post by brian m. carlson
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

[brian m. carlson]

Post by Werner Koch

Post by brian m. carlson
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.
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.

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?

Post by Werner Koch
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.

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.

[Werner Koch]

Post by brian m. carlson
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?

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.

Post by brian m. carlson
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

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.

Post by brian m. carlson
If we want something simpler in addition, we could reuse the CRC24 as
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

[brian m. carlson]

Post by brian m. carlson
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.

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]

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

[brian m. carlson]

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

[brian m. carlson]

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

[brian m. carlson]

Post by brian m. carlson
+### {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.
+

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.

[Werner Koch]

Post by brian m. carlson
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.

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

Post by brian m. carlson
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

I am fine with this.

Post by brian m. carlson
I welcome comments on this proposal with the goal of trying to get
consensus.

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