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

From: Bryan A Ford <[email-masked]>
Date: Fri, 27 Nov 2015 15:35:27 +0100

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

---

From: Henrick Hellström <[email-masked]>
Date: Fri, 27 Nov 2015 17:21:18 +0100

On 2015-11-27 15:35, Bryan A Ford wrote:
> fingerprinting and traffic analysis harder.

How, exactly, would this be significantly harder? The adversary will 
still be able to tell when, and how much, TCP/IP data is sent between 
the peers. If there happens to be a revealing TLS record boundary in the 
middle of a TCP/IP packet, it would seem to me there is an 
implementation problem rather than a problem with the abstract protocol.

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 28 Nov 2015 11:15:57 +0000

>fingerprinting and traffic analysis harder.

Argh, no!  I sent the following to the SSH list a few days ago in support of
someone else's suggestion to finally abandon this misguided idea:

-- Snip --

SSL/TLS have used unencrypted lengths for twenty years without there being any
(known) attack or weakness based on this.  OTOH SSH has used encrypted lengths
for nearly the same period, and there have been several attacks/weaknesses
based on that.  Security-wise, it has the opposite effect of the one intended,
it makes the protocol weaker, not stronger.

My real issue with it though is that, as you've pointed out, it makes it
impossible to create an efficient streaming implementation.  With TLS you read
the length at the start, stream the rest into the target memory location, and
decrypt in place.  With SSH you have to read a single block, decrypt it, make
sure you're not providing an oracle for the attacker, copy what's left around,
read more encrypted data onto the end, decrypt the remainder, ugh.

-- Snip --

Encrypting the length information is a serious step backwards both in terms of
security and processing efficiency.

Peter.

---

From: Henrick Hellström <[email-masked]>
Date: Sat, 28 Nov 2015 13:05:24 +0100

On 2015-11-28 12:30, Kriss Andsten wrote:
> On 27 Nov 2015, at 17:21, Henrick Hellström <[email-masked]> wrote:
>
>> How, exactly, would this be significantly harder? The adversary will still be able to tell when, and how much, TCP/IP data is sent between the peers. If there happens to be a revealing TLS record boundary in the middle of a TCP/IP packet, it would seem to me there is an implementation problem rather than a problem with the abstract protocol.
>
> This is actually quite common. Even when it does align with packet boundaries, it is providing known information rather than inferred information ("here's a length X blob, then a length Y blob" vs "Here's a bunch of packets whose lengths minus TLS headers amount to to X+Y").

Maybe I have missed something, but this seems awfully implementation 
dependent to me. Let's take a more specific example:

Suppose a web server is serving a request for a web page, which 
typically means that the client firstly sends a single HTTP request for 
the HTML page, and then multiple requests for the css, images, etc in a 
row.

Most times, the latter row of requests could easily be encoded in a 
single TLS fragment. This means that the server will become aware of all 
of the requests at the same time, and might encode all of the HTTP 
responses before beginning to encode the TLS fragments.

Carefully implemented, such a solution would not necessarily require 
significantly more resources to handle pipe-lining, compared to an 
alternative solution that would serve, encode and send the responses 
on-the-fly, and as a consequence quickly fill up the outgoing TCP/IP queue.

---

From: Roland Zink <[email-masked]>
Date: Sat, 28 Nov 2015 17:41:59 +0100

Am 28.11.2015 um 13:05 schrieb Henrick Hellström:
>>> still be able to tell when, and how much, TCP/IP data is sent 
>>> between the peers. If there happens to be a revealing TLS record 
>>> boundary in the middle of a TCP/IP packet, it would seem to me there 
>>> is an implementation problem rather than a problem with the abstract 
>>> protocol.
>>
>> This is actually quite common. Even when it does align with packet 
>> boundaries, it is providing known information rather than inferred 
>> information ("here's a length X blob, then a length Y blob" vs 
>> "Here's a bunch of packets whose lengths minus TLS headers amount to 
>> to X+Y").
>
> typically means that the client firstly sends a single HTTP request 
> for the HTML page, and then multiple requests for the css, images, etc 
> in a row.
>
> single TLS fragment. This means that the server will become aware of 
> all of the requests at the same time, and might encode all of the HTTP 
Even if it could be encoded in a single TLS fragment a simple minded 
browser may encode it one by one. Also there are many more use cases 
where such optimization may not work. Can you provide data what browsers 
are actually doing for HTTP/1.1 and HTTP2?
> on-the-fly, and as a consequence quickly fill up the outgoing TCP/IP 
I think it is more complicated so it will use more resources. You have 
to weight what is more important, the additional "security" or the 
"overhead". Anyway I thought the decision was to hide the record length.

Regards,
Roland

---

From: Henrick Hellström <[email-masked]>
Date: Sat, 28 Nov 2015 17:56:56 +0100

> are actually doing for HTTP/1.1 and HTTP2?

AFAIK, HTTP 1.1 browsers typically don't send a new request over an open 
connection, before it has received the response to the previous request. 
If that is the case, it is trivial to get the message lengths from the 
traffic, with or without encrypted TLS record headers. IOW you gain 
nothing by encrypting the length fields.

> "overhead". Anyway I thought the decision was to hide the record length.

You will have to make sure the peer is sending out a continuous stream 
of encrypted messages, anyway, or else you will not gain much by 
encrypting the TLS record headers. Relying on TLS fragments piling up at 
the TCP/IP level, rather than at the application level or TLS level, is 
not a reliable way to make traffic analysis harder. Even if the 
responses to a specific pair of requests pile up 999 times of 1000, 
there will still be a signal from the 1 in 1000 event that will be 
detectable by traffic analysis.

---

From: Henrick Hellström <[email-masked]>
Date: Sat, 28 Nov 2015 18:03:41 +0100

> security and processing efficiency.

I am inclined to +1 on that.

---

From: Roland Zink <[email-masked]>
Date: Sat, 28 Nov 2015 18:05:23 +0100

Am 28.11.2015 um 17:56 schrieb Henrick Hellström:
> AFAIK, HTTP 1.1 browsers typically don't send a new request over an 
> open connection, before it has received the response to the previous 
> request. If that is the case, it is trivial to get the message lengths 
> from the traffic, with or without encrypted TLS record headers. IOW 
> you gain nothing by encrypting the length fields.
>
I think this is what browsers do by default. For HTTP2 this should be 
different.

Regards,
Roland

---

From: Tony Arcieri <[email-masked]>
Date: Sat, 28 Nov 2015 11:08:09 -0700

On Sat, Nov 28, 2015 at 10:05 AM, Roland Zink <[email-masked]> wrote:

>> connection, before it has received the response to the previous request. If
>> that is the case, it is trivial to get the message lengths from the
>> traffic, with or without encrypted TLS record headers. IOW you gain nothing
>> by encrypting the length fields.
>>

This is HTTP/1.1 pipelining, which is supported by most browsers but
typically disabled by default as most servers don't support pipelining
correctly.

-- 
Tony Arcieri

---

From: Watson Ladd <[email-masked]>
Date: Sat, 28 Nov 2015 13:58:55 -0500

> typically disabled by default as most servers don't support pipelining

I think the above analysis is wrong. Consider a service written in Go using
the built-in TLS library. Then the number and sizes of writes is visible to
an attacker, which can reveal information about which branches were taken
and the data sent. That's not because the total size of the response
necessarily changes, but the sequence of writes taken to get there.

> --
> Tony Arcieri
>
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>
>

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Henrick Hellström <[email-masked]>
Date: Sat, 28 Nov 2015 20:20:36 +0100

On 2015-11-28 19:58, Watson Ladd wrote:
> I think the above analysis is wrong. Consider a service written in Go
> using the built-in TLS library. Then the number and sizes of writes is
> visible to an attacker, which can reveal information about which
> branches were taken and the data sent. That's not because the total size
> of the response necessarily changes, but the sequence of writes taken to
> get there.

I am not familiar with the internals of that implementation, but if the 
individual writes are immediately TLS encrypted and sent over the 
network, the timing of the TCP/IP data will likely leak a lot of 
information about the number and sizes of writes as well.

It doesn't seem like a perfect design choice to use encryption to hide 
information that will leak with non-negligible probability anyway.

---

From: Bryan A Ford <[email-masked]>
Date: Sun, 29 Nov 2015 10:16:40 +0100

Hi Peter,

On 11/28/15 12:15 PM, Peter Gutmann wrote:
> (known) attack or weakness based on this.  

Leaving all headers in the clear (and in particular record lengths) is a
huge side-channel, and historical experience is that attackers are
getting better and better at exploiting side-channels in surprising
ways.  The CRIME attack, for example, applied to a close relative of TLS
(namely SPDY), and exploited the attacker's ability to learn precise
information about (compressed in this case) record lengths.  I'm not
saying that hiding TLS/SPDY record lengths in particular would
necessarily address the CRIME attack (there were many factors involved
and a combination of weaknesses), but it is certainly an attack in which
the attacker's ability to see fine-grained length information was a
factor.  The general lesson is simply that lengths do represent
sometimes-exploitable side-channels.

> OTOH SSH has used encrypted lengths

You're conflating the goal (hiding TLS headers) with one particular old,
broken approach to achieving that goal (namely SSH's). I am not
proposing to hide TLS headers in the same way SSH did, and just because
one historical approach to hiding headers was broken doesn't mean that
the goal itself is a bad idea, or that all possible ways to achieve that
goal are broken, or that my proposal in particular is broken. Feel free
to attack my proposal but then please attack *my* proposal, not the old
broken SSH approach.

I already addressed one specific weakness the SSH approach had and
explained why that's not an issue in my proposal.  You allude to
"several attacks/weaknesses" SSH had: if there were several, can you
summarize or point me to information about the others?  And can you say
whether and in what way any of those past weaknesses in SSH might
conceivably apply to my proposed approach?  I claim you won't be able to
(but would be happy to be shown wrong), because there appears to be a
rather trivial "security proof" that my proposed hiding approach can't
possibly create any new security weaknesses that weren't already in TLS
1.3 as currently specified.  I already outlined that reasoning in my
proposal but will expand on it a bit more below.

> read more encrypted data onto the end, decrypt the remainder, ugh.

How exactly does my proposal make it "impossible to create an efficient
streaming implementation"?  Again, it sounds like you're attacking SSH's
broken approach while ignoring my proposal itself.  With my proposal you
can still perform exactly the same optimization just as before:

1. Read the 5-byte TLS header at the start, and decrypt it by XORing
with the output of the stream cipher as my proposal specifies, so you
now have the length.

2. Stream the rest into the target memory location, and AEAD-decrypt in
place.

I don't see how my proposal in any way makes life more difficult for
such streaming optimizations, because my proposal keeps
encryption/decryption of TLS headers separate from encryption/decryption
of the body.  What *might* make this optimization a bit more difficult
is the MAC that the AEAD wants to attach to each ciphertext, but if
that's a problem it's caused by TLS's use of AEAD and has nothing to do
with my proposal.  (That problem can in principle be worked around if
the AEAD cipher implementation has a simple "scatter/gather" capability
so it can put the MAC elsewhere, but that's a completely separate and
orthogonal topic.)

Now, returning to your concern about TLS header hiding creating security
weaknesses: my claim is that all that my proposal introduces is a change
of encoding of the 5-byte TLS header, which cannot possibly introduce
any new security weaknesses because it is not affecting in any way the
actual information content transmitted or received in the protocol or
the way it is processed outside of that header encoding change.

Consider this example:  Suppose we decided we wanted the 2-byte length
field in the TLS header to be transmitted in little-endian rather than
big-endian.  A useless change, yes, but could it create a new security
vulnerability that TLS 1.3 doesn't already have as specified?  Obviously
not; this would yield a perfectly (and provably) equivalent protocol.

Similarly, what if we decided for whatever reason it would be nice to
XOR the 5-byte length field with the constant five-byte sequence
[0x55,0x55,0x55,0x55,0x55]?  Could that create a new security
vulnerability?  Again, obviously not.

What if we decided that the TLS headers of odd-numbered records should
be XORed with [0x55,0x55,0x55,0x55,0x55], and the even-numbered records
should be XORed with [0xaa,0xaa,0xaa,0xaa,0xaa].  Could that create a
new security vulnerability?  No, it's still just an encoding change -
just one that happens to depend dynamically on record number.

What if we decided that the TLS headers should be XORed with an MD5 hash
of the record number?  Again, useless from a security perspective, but
not harmful either: it's still just changing the TLS header encoding
without changing anything else about how the protocol works - and in
particular doesn't change anything about how the record is
AEAD-protected or how the protocol behaves if an attacker flips any bits.

What if we decided that the TLS headers should be XORed with an
HMAC-SHA256 of the record number, keyed with a shared secret used only
for TLS header hiding?  This is now (finally) potentially useful from a
security perspective, and is basically isomorphic to my proposal - but
even if the attacker could break HMAC-SHA256 tomorrow or could learn the
shared secret used for TLS header protection, we would just be back to
the same security level as TLS's current cleartext-header design
achieves; we would still not be introducing any new security weaknesses
that TLS 1.3 doesn't already have.

Again, if you believe my reasoning is in any way flawed here, please
point out how you think my proposal (*not* the old SSH approach) could
conceivably introduce any new security weaknesses that TLS 1.3 doesn't
already have.

Thanks
Bryan

---

From: Bryan A Ford <[email-masked]>
Date: Sun, 29 Nov 2015 10:48:01 +0100

> implementation problem rather than a problem with the abstract protocol.

There are a variety of reasons TLS segment boundaries can and often do
become desynchronized from TLS record boundaries, such as:

(a) if the TLS implementation happens to encrypt several consecutive
records in a buffer and sends them with one write() call for efficiency.

(b) if the kernel TCP stack's send buffer is already non-empty on write
(e.g., held back to to congestion or flow control) and the TCP stack
decides simply to append the newly-written data to the already buffered
data, the boundary between those wrotes need not appear as a TCP segment
boundary.

(c) quite a few middleboxes can and do silently re-segment TCP streams
obliviously to the content of that stream.  In particular this tends to
happen as an incidental side-effect whenever the middlebox interposes on
the TCP stream by "terminating" the TCP connection and transparently
forwarding the content to/from a second TCP connection.

Now, this doesn't mean that "incidental" desynchronization of TCP
segment boundaries from TLS record boundaries will by itself add any
kind of robust protection against traffic analysis.  To achieve that, we
would want to ensure that a burst of (say) multiple HTTP requests and
their responses over the TLS connection get merged together and then
transmitted as a uniform-length series of blobs.  A sufficiently careful
TLS implementation could potentially achieve this, but with TLS headers
sent in cleartext, the TLS implementation is the *only* entity in the
system that can provide any kind of traffic analysis protection.

With TLS headers encrypted, it becomes feasible for some (weak or
strong) traffic analysis protection to be introduced at multiple points:

1. The TLS implementation can do it, either way.

2. Even if the TLS implementation doesn't try to provide any traffic
analysis protection, the kernel's TCP stack could provide some
protection (either intentionally or unintentionally) simply by merging
together consecutive writes as discussed above, so that transmissions
are usually just bursts of MTU-sized TCP segments even if they hold many
varying-size TLS records.

3. Finally, middleboxes can (again either intentionally or
unintentionally) add traffic analysis protection by re-segmenting TCP
traffic.  Corporate network operators often already see NATs as a
security advantage because they obfuscate the source IP addresses of
connections coming from the private network.  If TLS 1.3 encrypts its
record headers, then network operators and the middleboxes they deploy
will similarly be able to add traffic analysis protection "in the
middle" by re-segmenting TCP streams (which many of these middleboxes
may already be doing anyway), and whatever protection this provides will
apply to automatically to *all* TLS 1.3 traffic crossing that middlebox,
even if few or none of the actual TLS 1.3 endpoint implementations know
or care about traffic analysis protection.

In short, leaving TLS headers in cleartext basically hands any
eavesdropper a huge information side-channel unnecessarily and precludes
anyone *but* the TLS implementation itself from adding any traffic
analysis protection into the system.  Encrypting TLS headers appears to
cost practically nothing (at least if done as I've proposed), and it
allows traffic analysis protection (whether weak or strong, intentional
or unintentional) to be introduced at multiple points: e.g., by TLS
itself, or by the TCP stack, or by middleboxes.

Cheers
Bryan

---

From: Henrick Hellström <[email-masked]>
Date: Sun, 29 Nov 2015 12:29:04 +0100

On 2015-11-29 10:48, Bryan A Ford wrote:
> anyone*but*  the TLS implementation itself from adding any traffic

Thank you for the explanation. A few points:

The only way to completely thwart traffic analysis, is to always send 
data with the exact same amount-frequency pattern. The middleboxes you 
describe will *not* be able to achieve this, unless the TLS sender is 
adapted for such processing anyway.

The middleboxes can't inject data. All they can do is wait for data to 
arrive and delay data that has already arrived. Traffic analysis is 
about deriving information from patterns that emerge from the 
combination of timing and sizes. If data is delayed in order to reach a 
specific size before being forwarded, the middlebox might just be 
shifting the size signal to an equally detectable timing signal.

This is particularly true, if low latency is also a requirement. If very 
high latency is acceptable, the middleboxes might theoretically hide 
everything except the total amount of data transmitted during specific 
time intervals.

---

From: Bryan A Ford <[email-masked]>
Date: Sun, 29 Nov 2015 13:11:06 +0100

> adapted for such processing anyway.

Very true.  But perfect traffic analysis protection isn't the only goal
of interest, and is usually impractical anyway.  A less ambitious but
still worthwhile goal is simply to make sure that in
imperfectly-protected connections, transmission bursts leak as little of
their internal structure as possible even though the timing and burst of
the (whole) burst will still inevitably risk leaking something.  Even
when it's impractical to leak nothing, it's still worthwhile to leak less.

A fairly important common-case example of this, I think, is Web page
loads in which the client submits a bunch of requests in parallel over
the same connection.  This was never widely enabled in HTTP/1.1 due to
compatibility concerns but will probably become the norm quickly with
HTTP/2.0.  A TLS implementation designed without much concern for
traffic analysis will probably send those multiple small
requests/replies in separate TLS records, giving eavesdroppers a nice
fine-grained fingerprint of what all is in that transmission burst.  If
TLS 1.3 hides its headers, then either the TLS implementation, the TCP
stack, or a middlebox could readily scrub that internal structure and at
least make life harder for the attacker (e.g., reduce the bandwidth of
the side-channel).  That seems worthwhile to me if it doesn't cost much.

Cheers
Bryan

---

From: Bill Cox <[email-masked]>
Date: Sun, 29 Nov 2015 09:11:39 -0800

Thanks for the detailed description of why we might want to obfuscate TLS
record lengths.  From a security point of view, the only potential attack
vector this might create is that the attacker will know in many cases the
plain text of the first 5 bytes.  A weakness in the stream cipher might be
more easily exploited in this case.  IIUC, we feel pretty good about the
latest AEAD ciphers, and guessing the clear text of many bytes in the
record already is not too hard.  Is that right?  So, from my fairly
uninformed point of view, this seems like a reasonable upgrade.

I have one concern.  These same boxes that hide record lengths by merging
and breaking up packets arbitrarily likely would deliver the packets not
well aligned to record boundaries.  Is this already the case?  If these
boxes currently inspect packets when breaking them up to split packets
along record boundaries, encrypting the lengths will defeat this efficiency
hack.  We might cause an increase in network latency in this case.  Do any
of the routers out there currently use the record length field when
splitting up packets?

Bill

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Sun, 29 Nov 2015 15:00:38 -0500 (EST)

----- Original Message -----
> minor change to the current spec.

I believe your proposal is a nice example of putting the cart before the
horse. Before proposing something it should be clear what do you want to
protect from, what is the threat? Here you imply that the revealing the length
is somehow a weakness. However, TLS isn't supposed to hide lengths and never
did [0]. So will hiding the length _field_ of such a protocol, will really
protect against attacks taking advantage of packet lengths? If you see 
the previous work of analyzing TLS packet lengths they don't even need to 
read that length field, they just use the packet length on the wire.
There is already a solution for protecting packet lengths, and that's
called padding [1].

regards,
Nikos

[0]. the cbc ciphersuite approach was a half baked approach which never worked.
[1]. http://alfredo.pironti.eu/research/publications/full/identifying-website-users-tls-traffic-analysis-new-attacks-and-effective-counterme

---

From: Dave Garrett <[email-masked]>
Date: Sun, 29 Nov 2015 16:47:16 -0500

Maybe I'm missing something, but hasn't this issue already been sufficiently dealt with via padding?

https://tools.ietf.org/html/draft-ietf-tls-tls13-10#section-5.2.2

The record type and version fields are now frozen, and the record length field is not indicative of the real length if padding is used. The only way I could see encrypting the length field as helpful would be to further obfuscate it from something that can see the record layer but not the transport layer and doesn't know the full record size, though the padding already obfuscates it somewhat. Is this really worth jumping through hoops for?

Dave

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 30 Nov 2015 01:26:15 +0000

Bryan A Ford <[email-masked]> writes:

>Feel free to attack my proposal but then please attack *my* proposal, not 
>the old broken SSH approach.

I was actually commenting on the concept of encrypting headers in general,
not the specific case you'd given.  That is, I assumed you'd specifically 
chosen the one case where it's practical, an AEAD stream cipher, and used
that as a strawman.  Re-reading your post, it looks like "adding a stream
cipher to every TLS 1.3-compatible ciphersuite" should really be "require
that the only cipher type allowed for TLS be an AEAD stream cipher", 
because it's not going to work with anything else.

This breaks a fundamental principle of TLS, that you can drop in any 
algorithm or mechanism you like (well, within reason) and it'll still work.  
More importantly, if a flaw is found in one mechanism, you can switch to 
another.  In the past we've been able to switch between a KSG cipher (RC4), 
64-bit block ciphers, 128-bit block ciphers, and AEAD ciphers as required.
With this change, it looks like the only choice you have is an AEAD stream
cipher.

In addition, it doesn't actually achieve what you think it does, I'll 
expand on that in a separate message in reply to another post.

Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 30 Nov 2015 01:40:07 +0000

Nikos Mavrogiannopoulos <[email-masked]> writes:

>protect from, what is the threat?

Exactly.  If you want to thwart traffic analysis, you need to do something
like what's done by designs like Aqua ("Towards Efficient Traffic-analysis 
Resistant Anonymity Networks"), or ideas from any of the other anti-traffic-
analysis work that's emerged in the past decade or two.  You get traffic 
analysis resistance by, for example, breaking data into fixed-length 
packets, using cover traffic, and messing with packet timings, not by 
encrypting TLS headers.

Peter.

---

From: "Short, Todd" <[email-masked]>
Date: Mon, 30 Nov 2015 01:54:26 +0000

This brings up an interesting point; having a record length that corresponds to the TCP segment size can help hardware implementations such that they don't need to deal with scatter/gather; i.e. one TCP segment corresponds to a single TLS record. This goes along with 8 (or 4) byte record lengths for hardware implementations. 

--
-Todd Short
// Sent from my iPhone
// "One if by land, two if by sea, three if by the Internet."

> On Nov 29, 2015, at 8:40 PM, Peter Gutmann <[email-masked]> wrote:
>

---

From: Bryan A Ford <[email-masked]>
Date: Mon, 30 Nov 2015 09:56:05 +0100

> because it's not going to work with anything else.

In my proposal I focused on AEAD because I had understood (and thought I
had read in the TLS spec) that TLS had decided to move to AEAD-based
encryption in general.

I had no intention of implying that TLS "must" switch to AEAD
completely, and there's no reason it would need to for my proposal to
work.  It would work just as well and in exactly the same way if the
AEAD is replaced with the traditional Encrypt-then-MAC construction, for
example.

Also, if any issues with some (e.g., old) ciphersuites do arise, I
wouldn't object to specifying that TLS header encryption is done only
with "new" ciphersuites (e.g., the AEAD-based ones, or using some other
appropriate definition of "new").

Bryan

---

From: Bryan A Ford <[email-masked]>
Date: Mon, 30 Nov 2015 10:58:48 +0100

On 11/30/15 2:40 AM, Peter Gutmann wrote:
> analysis work that's emerged in the past decade or two.

I'm well aware of Aqua and "the other anti-traffic-analysis work that's
emerged in the past decade or two": in fact I led one of the major
recent systematic projects in that space.  See for example:

	http://dedis.cs.yale.edu/dissent/
	http://cacm.acm.org/magazines/2015/10/192387-seeking-anonymity-in-an-internet-panopticon/fulltext

> You get traffic

Packet padding and header encryption are both important, complementary
security measures: you get security benefits from each that you don't
get from the other.  Yes, you need padding to obtain systematic
protection from traffic analysis - when for whatever reason not all
implementations are always padding to the exact same standardized record
length, header encryption makes padded streams less trivially
distinguishable from unpadded streams, and makes streams with different
record sizes less trivially distinguishable from each other.

Padding-based transmission formats such as Aqua and Tor tend to specify
a single fixed packet size for *all* traffic using that protocol.  For
example, the Tor protocol always uses 256-byte cells for everything.
This is for obvious indistinguishability reasons: e.g., if some versions
of Tor padded to 256 bytes while other versions padded to 512 bytes,
then it would be trivial for an adversary to distinguish the two.  And
if the 512-byte version of Tor were fairly uncommon (either because it's
"too new" or "too old" or specific to a rare platform or whatever), then
the Tor streams using 512-byte cells would stick out obviously from
anyone else.

Furthermore, popular and well-designed as it is, Tor and similar
protocols have the well-known problem that it's pretty trivial for a
traffic analysis attacker to distinguish a Tor stream from any other
non-Tor stream. The severity of this weakness was put in sharp
perspective by the Harvard bomb hoax incident
(http://edition.cnn.com/2013/12/18/justice/massachusetts-harvard-hoax/).
 And it's not in any way because Tor was poorly-designed: on the
contrary, the problem is Tor sticks out because it's a well-designed
traffic-analysis-resistant protocol sharply silhouetted against a
backdrop of traffic that makes no attempt at traffic analysis
protection.  One thing that would greatly help Tor and all similar,
padded protocols is if they could "blend in" even just a little bit
better with the vast bulk of ordinary TLS-encrypted Web traffic, and
that's one of the big opportunities we're talking about here.  But to
make that happen, we would need to either (a) specify that *all* TLS 1.3
implementations use the same standardized record length like Tor does,
or (b) if that's not practical, do whatever we can to make flows padded
to a particular size less obviously distinguishable from unpadded flows
or flows padded to a different size.

If you think it is practical for the TLS 1.3 standard to specify a
single, fixed record size that all implementations of TLS 1.3 must use
(i.e., explicitly freeze not only the version field but the length
field), then that would be great for traffic analysis protection and on
that basis I would support that proposal.  But that frankly seems to me
likely a bit too much to ask given the diversity of TLS implementations
and use-cases.  Tell me if you believe otherwise.

So on the assumption that TLS 1.3 might not be ready to jump "whole-hog"
into Aqua/Tor-style transmission protocols that standardize a single
constant record size, I believe that header encryption provides at least
a useful, weak but significant security improvement at negligible cost.
 Sure, active attackers can still use "dribble attacks" (as discussed
recently on the SSH mailing list) to sniff out the record boundaries,
but they have to be active on-path and have to delay traffic, which
risks getting noticed.  Many attackers in practice are passive (don't
have the option or just don't want to invest the resources for full
MITM), and/or don't want to risk getting noticed by fiddling with the
traffic in readily detectable ways.

Cheers
Bryan

---

From: Bryan A Ford <[email-masked]>
Date: Mon, 30 Nov 2015 11:02:31 +0100

> This brings up an interesting point; having a record length that corresponds to the TCP segment size can help hardware implementations such that they don't need to deal with scatter/gather; i.e. on…

This is wildly unsafe to assume or depend on for all sorts of reasons;
TCP streams regularly get merged or re-segmented in the network in a
variety of unpredictable ways (e.g., by middleboxes).  See my earlier
E-mail discussing that issue extensively.

B

---

From: Bryan A Ford <[email-masked]>
Date: Mon, 30 Nov 2015 11:16:15 +0100

Thanks Bill for the feedback.

On 11/29/15 6:11 PM, Bill Cox wrote:
> Thanks for the detailed description of why we might want to obfuscate
> TLS record lengths.  From a security point of view, the only potential
> attack vector this might create is that the attacker will know in many
> cases the plain text of the first 5 bytes.  A weakness in the stream
> cipher might be more easily exploited in this case.  IIUC, we feel
> pretty good about the latest AEAD ciphers, and guessing the clear text
> of many bytes in the record already is not too hard.  Is that right? 
> So, from my fairly uninformed point of view, this seems like a
> reasonable upgrade.

Just a nitpicky semantic correction: my proposal doesn't "create" the
attack vector you describe (that the attacker will know the plaintext of
the 5-byte header).  That weakness is already there in TLS 1.3 as
currently specified, because the TLS header is unencrypted so the
attacker will *definitely* know the 5-byte header. :)  This is merely an
existing weakness that is not fixed by my proposal.

> I have one concern.  These same boxes that hide record lengths by
> merging and breaking up packets arbitrarily likely would deliver the
> packets not well aligned to record boundaries.  Is this already the
> case?  

It's already the case that middleboxes of various kinds re-segment
(merge and break up along different boundaries) TCP streams for various
reasons, often as an unintentional side-effect of interposing on the
stream by "accepting" the TCP connection (pretending to be an endpoint)
on one of the middlebox's interfaces and opening a new outgoing
connection on the other interface, and just forwarding the traffic
between them. In fact, Performance Enhancing Proxies (PEPs) are one
class of middlebox that often do this intentionally, so they can get
better control over and fiddle with the way congestion control works
over "troublesome" types of links like high-bandwidth-delay-product
(e.g., satellite) links.

> If these boxes currently inspect packets when breaking them up to
> split packets along record boundaries, encrypting the lengths will
> defeat this efficiency hack.  We might cause an increase in network
> latency in this case.  Do any of the routers out there currently use the
> record length field when splitting up packets?

If I understand your question correctly, you're asking if encrypting TLS
record lengths might break middleboxes that currently want to track TLS
records for some reason, e.g., perhaps to re-segment the TCP stream to
correspond to TLS records (which might "fix" or "revert" the effect of
another middlebox in the path that re-segments TCP in a TLS-oblivious
fashion).  I don't know of any middleboxes that do precisely this, but
it's not inconceivable that they could exist.

More generally, since basically all manner of evil/broken middleboxes do
exist, it's entirely possible that most any change to TLS's wire
encoding *could* disagree with some middleboxes.  That's not specific to
the change I'm proposing; any wire-visible change could trigger unknown
middlebox badness.  The only solution to this I'm aware of is empirical:
try the change, deploy it experimentally at first, and see what the pain
level is, i.e., see if we find any middleboxes that complain and if so
how prevalent they are.  But since TLS 1.3 is already changing a lot of
other prominently wire-visible stuff with respect to prior versions of
TLS that might equally well break middleboxes, it's not clear that my
proposed change in particular is more likely to cause pain than any of
the other changes already made, and in general I don't think we should
let a few broken/evil middleboxes prevent meaningful evolution of the
TLS protocol.

Cheers
Bryan

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 30 Nov 2015 10:34:27 +0000

Bryan A Ford <[email-masked]> writes:

>It would work just as well and in exactly the same way if the AEAD is
>replaced with the traditional Encrypt-then-MAC construction, for example.

No it wouldn't, unless the encrypt part is a stream cipher.  You're still
locked into using an AEAD stream cipher or the equivalent of an AEAD stream
cipher built with encrypt+MAC.  It won't work with, for example, the OCB AEAD
mode, or CBC + MAC.

Peter.

---

From: Jacob Appelbaum <[email-masked]>
Date: Mon, 30 Nov 2015 12:26:07 +0000

Dear Bryan,

> existing weakness that is not fixed by my proposal.

That is my read as well. I think your proposal sounds pretty interesting.

> it's not inconceivable that they could exist.

Why would that concern anyone other than to help an attacker?

If my ISP requires me to use such a box, I should use it as a proxy or
configure it manually. If they use it on me without my consent, it is
an attack. I want TLS to break and to do so in a way that fails
closed. If another ISP, backbone ISP, or XKeyscore would have a harder
job, I fail to see why we should care at all.

They're the adversary, we should not give them anything. We should
make their job as difficult as possible technically as well as in most
other ways as well. I have no sympathy for the
what-about-poor-NSAT&T's-big-networks of the world.

> let a few broken/evil middleboxes prevent meaningful evolution of the

Agreed entirely. TLS should also be able to be composed with anonymity
networks in a way that we solve complementary problems, as you've
said. The less a hostile Tor exit can learn about a person's TLS 1.3
flow, the better. One could even imagine a key setup over one Tor
circuit and then a seemingly unrelated connection using the negotiated
key over another Tor circuit.

In an ideal world, we'd have two basic phases...

setup/keyex/etc:
  which is distinguishable

transfer of data/tear down:
  which if done correctly, should almost all look the same unless we
have a full network view with reassembly.

It would be nice if the biggest problem for traffic analysis was then
TCP/IP related, though we're far from that point with TLS 1.3 or any
other general purpose protocol.

It is true that to beat traffic analysis, we need to tackle that
problem directly and I very much agree with you that we still should
make these positive changes. Your suggested changes will also assist
others who are dealing with those problems directly.

All the best,
Jacob

---

From: Hubert Kario <[email-masked]>
Date: Mon, 30 Nov 2015 15:20:36 +0100

On Monday 30 November 2015 10:58:48 Bryan A Ford wrote:
> >> I believe your proposal is a nice example of putting the cart
> >> before the horse. Before proposing something it should be clear
> >> what do you want to protect from, what is the threat?
> > 
> > Exactly.  If you want to thwart traffic analysis, you need to do
> > something like what's done by designs like Aqua ("Towards Efficient
> > Traffic-analysis Resistant Anonymity Networks"), or ideas from any
> > of the other anti-traffic- analysis work that's emerged in the past
> > decade or two.
> 
> I'm well aware of Aqua and "the other anti-traffic-analysis work
> that's emerged in the past decade or two": in fact I led one of the
> major recent systematic projects in that space.  See for example:
> 
> 	http://cacm.acm.org/magazines/2015/10/192387-seeking-anonymity-in-an-> internet-panopticon/fulltext
> > You get traffic
> implementations are always padding to the exact same standardized
> record length, header encryption makes padded streams less trivially
> distinguishable from unpadded streams, and makes streams with
> different record sizes less trivially distinguishable from each
> other.

the header contains only one piece of information, and it is public 
already - the amount of data transmitted*

If you want to hide how much data was transmitted, you need to establish 
a tunnel that transmits data constantly, at the exact same rate for the 
whole duration of connection.

that means that you need to know a). what bandwidth the client has, b). 
what bandwidth the server can spare and c). how much data the user wants 
to get or send to the server (I really don't want to transmit 1GiB of 
data over a 100KiB/s stream if I have a 100Mbps link...).

this goes well past the TLS WG charter, if only because it requires very 
close cooperation with the application layer

so while the padding mechanism should be there, we really can't describe 
how it needs to be used, as it can't be made universal nor is it 
necessary for all use cases

 * - sure, the record layer boundaries can tell something about the data 
being transmitted, but so can the presence of data transmission taking 
place in the first place (think of a station sending reports only when 
it detects something while keeping connection open the whole time)
 
> One thing that would greatly help Tor and all similar,
> that's one of the big opportunities we're talking about here. 

the initial message in handshake in TLS MUST stay the same thus it is 
impossible to make it look like Tor. Not to thwart the Pervasive 
Monitoring threat of TLA agencies.
 
> field), then that would be great for traffic analysis protection and
> on that basis I would support that proposal.  But that frankly seems
> to me likely a bit too much to ask given the diversity of TLS
> implementations and use-cases.  Tell me if you believe otherwise.

That will just round up to a multiple of 256 bytes the data sizes 
transmitted. Hardly an improvement over the current 16 byte blocks.

-- 
Regards,
Hubert Kario
Senior Quality Engineer, QE BaseOS Security team
Web: www.cz.redhat.com
Red Hat Czech s.r.o., Purkyňova 99/71, 612 45, Brno, Czech Republic

---

From: Jacob Appelbaum <[email-masked]>
Date: Tue, 1 Dec 2015 00:14:14 +0000

> already - the amount of data transmitted*

I'm pretty sure TLS has a lot more data...

> whole duration of connection.

...

> data over a 100KiB/s stream if I have a 100Mbps link...).

...

> necessary for all use cases

I think it should be described how it needs to be used...

> it detects something while keeping connection open the whole time)

Yes, they tell something and that something is better removed.

> Monitoring threat of TLA agencies.

That Tor claim is strange and seemingly false in any case. Also, I've
said it before quoting the RFC but I'll say it again: Pervasive
Monitoring is an attack.

> transmitted. Hardly an improvement over the current 16 byte blocks.

Closer to 512 bytes is better.

All the best,
Jacob

---

From: Viktor Dukhovni <[email-masked]>
Date: Tue, 1 Dec 2015 00:56:09 +0000

> cipher built with encrypt+MAC.  It won't work with, for example, the OCB AEAD

I think we should focus on what would get TLS 1.3 to be adopted:

    * Reasonably implementable in libraries that support older
      versions alongside TLS 1.3.

    * Interoperable in the field with various capital-intensive
      middle boxen.

This suggests focusing on solidifying the core protocol, and a
healthy dose of skepticism around bells and whistles.  If the
protocol is overloaded with too many (alright even more) incompatible
innovations, the net effect is likely less security due to
substantially delayed deployment of the key improvements.

Encrypting message lengths looks rather marginal from this perspective,
and quite likely to hinder interoperability and delay both
implementation and upgrades.  However cool an idea this might be,
this does not look to me like the right time to add this feature
to TLS.

At this point, TLS 1.3 is rather feature rich, and it is I think
time to focus on reviewing the already agreed changes (maybe even
drop some if they look inessential).  Make it solid, trim the fat,
get it out the door in a usable form.

-- 
	Viktor.

---

From: Jacob Appelbaum <[email-masked]>
Date: Tue, 1 Dec 2015 01:36:26 +0000

>       versions alongside TLS 1.3.

That doesn't change with Bryan's suggestion, I think.

>     * Interoperable in the field with various capital-intensive

Which would those be? And what is the definition of capital-intensive
for those watching on the sidelines?

> substantially delayed deployment of the key improvements.

This seems borderline absurd. The TLS protocol is doing a major
version revision.

> this does not look to me like the right time to add this feature

I don't think it will hinder interoperability and not one person has
even named a single device that would have issues with it. I think the
only thing that comes close is when I've named a classified US
government surveillance program (XKeyscore) that would probably have
trouble with it.

We should add Bryan's feature and not pander to non-specific concerns
about middleboxes that should be considered as adversaries.

> get it out the door in a usable form.

That is part of what is happening in Bryan's suggestion. He found a
reasonably practical way to encrypt record headers. His suggestion
will make TLS more secure. His suggestion includes a review of a part
of the previous state of TLS 1.3 with a proposed improvement.

No one is debating it on the cryptographic merits which is surprising.

All the best,
Jacob

---

From: Fabrice Gautier <[email-masked]>
Date: Mon, 30 Nov 2015 19:02:05 -0800

1) What would be the implications of this for DTLS? (Knowing that one difference between TLS and DTLS is the record header)

2) In some implementations the record framing/parsing and encryption/decryption are down at different layers. Would this proposal make this type of implementation impossible? 

-- Fabrice

> On Nov 27, 2015, at 06:35, Bryan A Ford <[email-masked]> wrote:
>

---

From: "Jim Schaad" <[email-masked]>
Date: Mon, 30 Nov 2015 20:18:06 -0800

> -----Original Message-----
> From: TLS [mailto:[email-masked]] On Behalf Of Jacob Appelbaum
> Sent: Monday, November 30, 2015 5:36 PM
> To: [email-masked]
> Subject: Re: [TLS] Encrypting record headers: practical for TLS 1.3 after
all?
> >> >It would work just as well and in exactly the same way if the AEAD
> >> >is replaced with the traditional Encrypt-then-MAC construction, for
> >> >example.
> >>
> >> No it wouldn't, unless the encrypt part is a stream cipher.  You're
> >> still locked into using an AEAD stream cipher or the equivalent of an
> >> AEAD stream cipher built with encrypt+MAC.  It won't work with, for
> >> example, the OCB AEAD mode, or CBC + MAC.
> >
> Which would those be? And what is the definition of capital-intensive for
those
> watching on the sidelines?
> 
> >
> > This suggests focusing on solidifying the core protocol, and a healthy
> > dose of skepticism around bells and whistles.  If the protocol is
> > overloaded with too many (alright even more) incompatible innovations,
> > the net effect is likely less security due to substantially delayed
> > deployment of the key improvements.
> 
> This seems borderline absurd. The TLS protocol is doing a major version
revision.
> 
> > Encrypting message lengths looks rather marginal from this
> > perspective, and quite likely to hinder interoperability and delay
> > both implementation and upgrades.  However cool an idea this might be,
> > this does not look to me like the right time to add this feature to
> > TLS.
> 
> I don't think it will hinder interoperability and not one person has even
named a
> single device that would have issues with it. I think the only thing that
comes
> close is when I've named a classified US government surveillance program
> (XKeyscore) that would probably have trouble with it.
> 
about
> middleboxes that should be considered as adversaries.
> 
> >
> > At this point, TLS 1.3 is rather feature rich, and it is I think time
> > to focus on reviewing the already agreed changes (maybe even drop some
> > if they look inessential).  Make it solid, trim the fat, get it out
> > the door in a usable form.
> 
reasonably
> practical way to encrypt record headers. His suggestion will make TLS more
> secure. His suggestion includes a review of a part of the previous state
of TLS
> 1.3 with a proposed improvement.

I would strongly prefer that the analysis for TLS and DTLS no be too
different.  This approach will not work for DTLS given that packets can
arrive out of order and multiple times.

Jim