[TLS] Encrypting record headers: practical for TLS 1.3 after all?

[Bryan A Ford <[e-mail]>]

The idea of encrypting TLS record headers has come up before, the most
important purpose being to hide record lengths and boundaries and make
fingerprinting and traffic analysis harder.  I had convinced myself that
goal this would be "too hard" to accomplish in TLS 1.3, but after
further thought I'm not so sure.  So I would like to request comment on
one approach that strikes me as a practical and requires only a rather
minor change to the current spec.

The quick summary:

* To encrypt a record, we first AEAD-encrypt the record's payload,
protecting the header fields via the additional_data, exactly as
currently specified.  But then we XOR-encrypt the 5-byte TLS header just
before transmission, using a (separate) stream cipher indexed by a nonce
that depends on record sequence number and *_write_iv, in exactly the
same way the AEAD is already nonce-indexed.

* To decrypt a record, we simply do the reverse: first use the stream
cipher with the appropriate nonce to XOR-decrypt the 5-byte TLS header,
then sanity-check it as usual to determine its length, read the rest of
the record, and submit it to AEAD for decryption and full integrity
checking as before.

That's it, in a nutshell.  Two likely concerns immediately arise,
discussed below, but feel free to TL;DR the rest if you don't share
these concerns.

---

Concern #1: What if an active attacker messes with the TLS header,
especially the length field, since stream ciphers don't protect
integrity?  The simple answer is that *exactly* the same thing happens
as now: the AEAD decryption attempt fails, because the
(stream-decrypted) header is AEAD-protected as additional_data.  Nothing
is gained or lost.

SSH, which did something like this, ran into trouble with attackers
being able to twiddle the record length field to make the record length
look big, causing the receiver to try to receive a very large record,
and hence appear to the user to hang, instead of immediately detecting
the modification and terminating the connection.  But there are three
mitigating factors here: (1) TLS is not usually used for interactive
terminal traffic like SSH is; (2) TLS's 2-byte record length field
imposes a pretty reasonable upper-bound on the maximum size an attacker
could maliciously make a record appear to be; and (3) if this risk of
length-twiddling is at all a problem in this proposed encrypted-header
protocol, then it's already a problem for the current TLS 1.3 spec
without encrypted headers, because active attackers can twiddle the bits
of a cleartext length field just as easily (and even be *certain* they
are making the length appear large!).  So I can't see any way this
length-twiddling vulnerability becomes any worse, and maybe it gets a
bit better (because the attacker can no longer be entirely certain
whether he's setting a 1 bit to 0 or a 0 bit to 1).

---

Concern #2: Do we want to have to go to the trouble of adding a stream
cipher to every TLS 1.3-compatible ciphersuite?  Answer: maybe not, but
we don't necessarily need to.  We could instead just specify a generic
method of using the ciphersuite's main AEAD as a stream cipher for
header encryption/decryption purposes.

The conceptually simplest approach I can think of: In the specification
of how AEAD nonces are generated (section 5.2.2 of
draft-ietf-tls-tls13-07), reserve the least-significant bit of the
record sequence number, so that sequence numbers increment by 2 rather
than 1 each record.  Thus, we get two unique nonces per record from the
same set of symmetric keys.  We first use the nonce with a '0'
least-significant bit to perform the regular AEAD-encryption of the
record with the header info as additional_data.

Then for the same record we use the nonce with a '1' least-significant
to AEAD-encrypt a sequence of five zero bytes ("\0\0\0\0\0"), and use
the first five bytes of result as the cipherstream to XOR the 5-byte TLS
header with before transmitting.  The AEAD will of course uselessly
append some kind of authenticator to this ciphertext that we won't end
up using, but that's OK.  The receiver will just use AEAD-encrypt
(again) on the same five-zero-byte message to reproduce the 5
cipherstream bytes with which to decrypt the TLS header.  Thus, senders
perform two AEAD-encrypts per record, and receivers do one AEAD-encrypt
and one AEAD-decrypt per record.

This approach seems pretty conceptually clean and simple, but has the
performance downside that we always need to invoke the AEAD twice per
record rather than once, which might be (a bit) costly especially when
records are small.  So a simple refinement is to amortize this cost
across records: e.g., once every 256 records (every sequence number
ending in 0x00) we AEAD-encrypt a sequence of 5*256=1280 zero bytes, and
the result in 5-byte chunks as the cipherstream with which to encrypt
and decrypt 256 consecutive TLS record headers.  Thus, we're only adding
one additional AEAD-encryption of a "normal-packet-sized" 1280-byte blob
once every 256 records, which seems likely to be a pretty
inconsequential performance cost.

---

Comments?

Thanks
Bryan