Subject: Re: [Cfrg] Discuss/standardize Preview extension to AEAD abstraction?

From: Fedor Brunner <[email-masked]>
Date: Wed, 02 Dec 2015 12:57:23 +0100

Hi Bryan,

if we have AEAD function:
- Input: key, nonce, plaintext
- Output: ciphertext, authentication tag

Then APEAD can be:
- Input: key, nonce, plaintext
- Output is concatenation of:
	- AEAD(key, nonce, header)
	- AEAD(key, nonce + 1, plaintext)

where header is length of plaintext, or length of plaintext together
with some fixed length additional data. Overhead of this scheme is one
additional authentication tag. After this operation nonce has to be
increased by 2.

Fedor

Bryan Ford:
> A few days ago I started a thread on the TLS list on encrypting TLS headers, like SSH has been doing for a long time, to add (limited but useful) protection against passive fingerprinting and traffic analysis attacks.  I then learned that there’s a parallel discussion thread touching on the same topic on the SSH mailing list.  I don’t want to start yet another discussion thread on the merits of header-encryption in general (see either of those two existing threads if you want to jump in on that :) ) - but I wanted to bring up the technical issue of how header-encryption interacts with the shift toward AEAD cipher designs.  This seemed like a potentially interesting CFRG topic.
> 
> The general problem (for TLS or SSH or many other protocols) is that we might like to encrypt both the header and the payload, but the header typically includes the length field, and the receiver needs that length field to know how big of a blob to read and pass to the AEAD for decryption and integrity-checking.  Thus, we really would like a three-stage receive process: (1) decrypt header to retrieve length, (2) read the cipher text payload, (3) decrypt the payload and integrity-check both the header and payload.  Is it worth considering a fairly simple extension to the AEAD abstraction that would support this form of operation?
> 
> Let’s call it APEAD: Authenticated Previewable Encryption with Additional Data.  Every APEAD would also be an AEAD cipher: i.e., APEAD is a subclass of AEAD.  Not every AEAD would be an APEAD, although many (practically all I think) of the most popular AEAD schemes are already implicitly APEADs as discussed below.  The API of an APEAD cipher looks exactly like that of an AEAD cipher but provides one more operation, “Preview”, which the receiver can do before decryption:
> 
> APEAD Encryption:
> 
> - Input: key, plaintext, and optional additional data, just as in AEAD.  However, APEAD allows some or all of the transmitted “header” (including length) to be included in the plaintext to be encrypted, leaving the “additional data” input to be used only for implicit context data, such as the record number in the case of TLS.  (The record number doesn’t need to be transmitted explicitly in TLS because it just counts consecutively.)
> 
> - Output: ciphertext (including encrypted header) and authentication tag.
> 
> APEAD Preview:
> 
> - Input: key, and some prefix of the ciphertext.  The specific APEAD may (or may not) set a limit on the amount of previewable data: e.g., for sponge constructions like MonkeyDuplex this will typically be the sponge’s rate, while for “stream cipher plus MAC” constructions (e.g., AES-GCM, ChaCha20+Poly1305) the cipher would not need to impose any fixed limit.  Regardless, in practice only a few previewable bytes should ever be needed (e.g., TLS headers are 5 bytes, way smaller than any realistic cipher block size or rate).
> 
> - Output: an *unauthenticated* decryption of the corresponding prefix of the ciphertext.  A receiver obviously must careful here about how it uses this unauthenticated, decrypted data.  But the security considerations here are exactly the same as the ones the receiver must take anyway in how it would handle not-yet-authenticated header data it receives in the unencrypted header part of a traditionally AEAD-encrypted message (e.g., an unencrypted length field), before decrypting and authenticating the AD and payload.
> 
> APEAD Decryption:
> 
> - Input: key, complete ciphertext, authentication tag, and additional data. 
> - Output: plaintext, or authentication error, exactly as in AEAD.
> 
> So with an AEAD cipher that supports the Preview operation (i.e., an APEAD), a protocol like TLS or SSH can include the length and other transmitted header information in the plaintext to be encrypted rather than in the AD.  The AD is still useful to carry implicit context (e.g., TLS record number); it just isn’t needed for explicitly-transmitted headers. The receiver uses the Preview operation to decode the received header and determine the length, then reads the rest of the encrypted blob appropriately, and invokes the Decryption operation to decrypt and MAC the whole blob.
> 
> Before I get a lot of knee-jerk reactions about the dangers of using unauthenticated encrypted data (which are real and important!), note that protocols like TLS that use AEAD-encrypted records are *already* making exactly such use of unauthenticated header data - e.g., the received length field, which the receiver needs to extract before it can authenticate the received packet.  In any proper use of an APEAD interface as summarised above, the *only* thing that the receiver should do with the unauthenticated data it gets view the Preview operation is exactly the same (hopefully extremely limited and carefully-protected) set of things it would have to do in any case with the unencrypted header *before authentication* in a conventional AEAD-based protocol design.
> 
> So provided this restriction on the use of the Preview operation is followed, moving from AEAD-based operation with unencrypted headers to APEAD-based operation with encrypted headers cannot introduce any new security weakness that wasn’t present already in the AEAD-based design.  There are still the old weaknesses of bad things attackers can do by fiddling with the length or other header fields to make the receiver to bad things before it’s fully authenticated the packet - but all those weaknesses were already there and would be present anyway if the header was transmitted unencrypted and authenticated as Additional Data.  (And such weaknesses are even easier to exploit when the headers are transmitted in cleartext as in AEAD.)
> 
> I mentioned earlier that many AEAD constructions are already, in effect, APEAD (or APEAD-compatible) ciphers.  For example, all the standard AEAD constructions with a stream cipher plus MAC (e.g., AES-CTR+HMAC, AES-GCM, ChaCha20+Poly1305) already trivially support previewing at least internally; the only challenge is the software engineering effort of bringing this functionality out as part of the API.  Sponges and other recent constructions should have no trouble either, provided at least the first “block” or “rate” bytes of data can be decrypted without having the full ciphertext or MAC available.  The one class of recent AEAD constructions I can think of that will definitely be *not* compatible with APEAD are the so-called “misuse-resistant” AEADs: i.e., those that take two passes over the whole data to ensure that the encryption of every bit of ciphertext depends on every bit of plaintext, making it cryptographically infeasible for the receiver to decrypt before having the whol
 e
 ciphertext in hand.  So APEADs and “misuse-resistant AEADs” will necessarily form mutually exclusive subclasses of AEADs, each with their distinct purposes and tradeoffs - and I think that’s fine.
> 
> So my ultimate question: in the interest of harmonising the (perfectly reasonable) desire by many protocols to move to AEAD-based ciphers with the (also perfectly reasonable) desire for protocols to be able to encrypt their transmitted headers as well, would it be worth discussing and potentially standardising something like such an APEAD extension to the AEAD abstraction and API?
> 
> Thanks
> Bryan
> 
> 
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Damien Miller <[email-masked]>
Date: Thu, 3 Dec 2015 11:28:20 +1100 (AEDT)

On Mon, 30 Nov 2015, Bryan Ford wrote:

> A few days ago I started a thread on the TLS list on encrypting TLS
> headers, like SSH has been doing for a long time, to add (limited but
> useful) protection against passive fingerprinting and traffic analysis
> attacks. I then learned that there’s a parallel discussion thread
> touching on the same topic on the SSH mailing list. I don’t want to
> start yet another discussion thread on the merits of header-encryption
> in general (see either of those two existing threads if you want to
> jump in on that :) ) - but I wanted to bring up the technical issue
> of how header-encryption interacts with the shift toward AEAD cipher
> designs. This seemed like a potentially interesting CFRG topic.
>
> The general problem (for TLS or SSH or many other protocols) is that
> we might like to encrypt both the header and the payload, but the
> header typically includes the length field, and the receiver needs
> that length field to know how big of a blob to read and pass to the
> AEAD for decryption and integrity-checking. Thus, we really would
> like a three-stage receive process: (1) decrypt header to retrieve
> length, (2) read the cipher text payload, (3) decrypt the payload and
> integrity-check both the header and payload. Is it worth considering
> a fairly simple extension to the AEAD abstraction that would support
> this form of operation?

Speaking as an application developer, I want a primitive that allows
me to "seal" zero or more bytes of plaintext to be encrypted and
authenticated along with zero or more bytes of AAD to be authenticated
into a self-delimiting blob that preserves the integrity and
*optionally the privacy* of the lengths of the plaintext and AAD.

At the other end, I want to, given enough of the header of that blob,
be able to determine a) how many bytes I need to read to get the whole
thing, b) how much space I'll need to extract the plaintext (if any) and
c) how much space I'll need to extract the AAD (if any).

This is pretty close to the crypto_box abstraction in NaCl or
BoringSSL's EVP_AEAD_CTX_seal, but it goes a little further in making
the result *including length fields* entirely opaque to the application
developer.

IMO this would cover most (not all) application use-cases with a simple,
hard to misuse primitive.

Something like this:

size_t box_seal_need(struct cipher *ctx,
    size_t plaintext_len, size_t aad_len);

int box_seal(struct cipher *ctx,
    const u_char *plaintext, size_t plaintext_len,
    const u_char *aad, size_t aad_len,
    u_char *sealtext, size_t sealtext_len);

size_t seal_header_need(struct cipher *ctx);

int box_open_need(struct cipher *ctx,
    const u_char *seal_header, size_t seal_header_len,
    size_t *sealtext_len, size_t *plaintext_len, size_t *aad_len);

int box_open(struct cipher *ctx,
    const u_char *sealtext, size_t sealtext_len,
    u_char *plaintext, size_t plaintext_len,
    u_char *aad, size_t aad_len);

-d

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 4 Dec 2015 03:15:09 +0000

Damien Miller <[email-masked]> writes:

>At the other end, I want to, given enough of the header of that blob, be able
>to determine a) how many bytes I need to read to get the whole thing, b) how
>much space I'll need to extract the plaintext (if any) and c) how much space
>I'll need to extract the AAD (if any).

+1.  This is my big gripe with SSH, it doesn't allow you to do this.

(An elegant trick, mentioned to me by someone else off-list, is to
speculatively read ahead, or at least non-blocking over-read each block, by 5
bytes so you optionally get the info on the next TLS data block before you
need it.  Then you can read and decrypt in-place, for an overhead of close to
1 network I/O/kernel transition/whatever your TCP stack does per block).

Peter.

---

From: Bryan Ford <[email-masked]>
Date: Fri, 4 Dec 2015 11:53:02 +0100

> c) how much space I'll need to extract the AAD (if any).

Agreed, that’s exactly what the APEAD interface-extension I proposed is trying to make possible, at least in the case of TLS.  The same APEAD interface extension also solves a slightly different need in the case of DTLS and similar out-of-order datagram-oriented protocols, where the length isn’t a problem but the receiver instead needs to get at an encrypted sequence number somehow in order to know which nonce to use for decryption.

Philipp Jovanovic, my amazing new postdoc, pointed out that the CAESAR cipher competition defined a “secret message number” feature that AEAD submissions can optionally implement:

	http://competitions.cr.yp.to/caesar-call.html <http://competitions.cr.yp.to/caesar-call.html>

…and pointed to a nice explanation by DJB clarifying both the motivation and intended function of this secret message number feature:

	https://groups.google.com/forum/#!searchin/crypto-competitions/secret$20message$20numbers/crypto-competitions/n5ECGwYr6Vk/bsEfPWqSAU4J <https://groups.google.com/forum/#!searchin/crypto-competitions/secret$20message$20numbers/crypto-competitions/n5ECGwYr6Vk/bsEfPWqSAU4J>

This seems like exactly the thing the DTLS case wants, although it doesn’t address the encrypted-length problem in the case of TLS.  I’m curious how many CAESAR cipher submissions actually ended up supporting secret message numbers; does anyone have a sense for this?

It seems like the APEAD extension I proposed is more general than an AEADs with secret message numbers, in that it is easy to build an “AEAD with secret message numbers” from an APEAD.  On encryption, just prepend the secret message number to both the plaintext and the nonce and feed them to the APEAD encrypt interface.  On decryption, invoke the APEAD preview call to decrypt the (not-yet-authenticated) secret message number, prepend it to the nonce, and invoke the full APEAD decrypt-and-authentication function.

Perhaps DJB can comment - is my reasoning sound about the relationship between the proposed APEAD extension and the CAESAR competition’s optional secret message number feature?  Is there anything seriously problematic or unsound from a crypto perspective about such an APEAD interface extension or feature, aside from the well-known risks associated with any use of (“previewed”) data before it’s been integrity-checked?

Cheers
Bryan