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

[Fedor Brunner <[e-mail]>]

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
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>