Subject: [TLS] draft-ietf-tls-tls13-21: TLS 1.3 record padding removal leaks padding size

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Fri, 11 Aug 2017 16:11:10 +0200

Imagine the following scenario, where the server and client have this
repeated communication N times per day:

client     server
    --X-->
    <--Y--

the client puts in X a message A of 1 byte or B of 1024 bytes, and pads
it to the maximum size of TLS record. The server replies with the 
message "ok" (same every time), padded to the maximum size just after
it reads X.

However, TLS 1.3 detects the message size by iterating through all the
padding bytes, and thus there is a timing leak observed by the time
difference between receiving X and sending Y. Thus as an adversary I
could take enough measurements and be able to distinguish between X
having the value A or B.

While I'd expect these iterations to be unmeasurable in desktop or
server hardware, I am not sure about the situation in low-end IoT
hardware. Is the design choice for having the padding removal depending
on padding length intentional?

There is mentioning of possible timing channels in:
https://tools.ietf.org/html/draft-ietf-tls-tls13-21#appendix-E.3
However I don't quite understand how is this section intended to be
read. The sentence for example: "Because the padding is encrypted
alongside the actual content, an attacker cannot directly determine the
length of the padding, but may be able to measure it indirectly by the
use of timing channels exposed during record processing", what is its
intention? Is it to acknowledge the above timing leak?

Shouldn't instead be guidance in section 'Implementation Pitfalls' on
how to remove padding in a way that there are no timing leaks? (the
timing leak here is not in crypto algorithms, but TLS itself). Ideally
TLS 1.3 itself shouldn't use data-size depending calculations itself
such as the one described here. 

regards,
Nikos

---

From: "Short, Todd" <[email-masked]>
Date: Fri, 11 Aug 2017 15:17:27 +0000

The application can solve this by having its own padding. If it’s going to force all messages to be padded out to 1024 bytes by TLS, why not just make that part of the application protocol? Its not as though it’s trying to save bytes here.
--
-Todd Short
// [email-masked]<mailto:[email-masked]>
// "One if by land, two if by sea, three if by the Internet."

On Aug 11, 2017, at 10:11 AM, Nikos Mavrogiannopoulos <[email-masked]<mailto:[email-masked]>> wrote:

client     server
   --X-->
   <--Y--

Yes, I presume so.

regards,
Nikos

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

---

From: Ted Lemon <[email-masked]>
Date: Fri, 11 Aug 2017 11:39:23 -0400

> The application can solve this by having its own padding. If it’s going to force all messages to be padded out to 1024 bytes by TLS, why not just make that part of the application protocol? Its not…

The downside to this is that now you have to get it right in each protocol that does it, instead of getting it right once.

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 11 Aug 2017 08:57:58 -0700

> on padding length intentional?

Yes, we're aware of this, and it's an intentional design choice. The
reasoning
was that once you have the padding removed, you'll need to operate on/copy
the unpadded content somewhere, and that's timing dependent anyway.

> intention? Is it to acknowledge the above timing leak?

Yes.

-Ekr

> [email-masked]

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Fri, 11 Aug 2017 18:43:15 +0200

On Fri, Aug 11, 2017 at 5:17 PM, Short, Todd <[email-masked]> wrote:

> The application can solve this by having its own padding. If it’s going to
> force all messages to be padded out to 1024 bytes by TLS, why not just make
> that part of the application protocol? Its not as though it’s trying to
> save bytes here.
>

I don't argue with this but this is not the approach TLS 1.3 took. It
provides a generic padding mechanism to be used across application
protocols.

regards,
Nikos

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Fri, 11 Aug 2017 18:47:01 +0200

> the unpadded content somewhere, and that's timing dependent anyway.

That is certainly an incorrect assumption. gnutls for example provides a
zero-copy API, and I guess it is not the only implementation to have that.

>> intention? Is it to acknowledge the above timing leak?

I am not sure if that text is sufficient to cover that issue. It seems as
if the cbc timing attack is re-introduced here and pushing the fix to
implementers. It may be better no to provide padding functionality with
this "feature", as unfortunately it will be used by applications.

regards,
Nikos

---

From: Andrei Popov <[email-masked]>
Date: Fri, 11 Aug 2017 17:04:05 +0000

*   I don't argue with this but this is not the approach TLS 1.3 took. It provides a generic padding mechanism to be used across application protocols.
At some point I thought we said that the TLS 1.3 padding mechanism was supposed to be application-driven (in the form of application-provided policy or simply desired pad size), which would mean that the application has to be involved anyway.

Cheers,

Andrei

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 11 Aug 2017 10:20:24 -0700

On Fri, Aug 11, 2017 at 9:47 AM, Nikos Mavrogiannopoulos <[email-masked]>
wrote:

>> On Fri, Aug 11, 2017 at 7:11 AM, Nikos Mavrogiannopoulos <[email-masked]
>> > wrote:
>>

And then the next thing that will happen is that the application will read
the data, which is length-dependent. The problem is that the plaintext is
variable length.

> this "feature", as unfortunately it will be used by applications.

I don't believe that this is analysis is correct. This timing channel only
applies to the data after message integrity has been established (i.e.,
after AEAD processing), which is different from the situation in Lucky 13.
It seems like what leaks here is the length of the plaintext, which is also
what would be leaked if we simply did not have padding.

-Ekr

---

From: "Short, Todd" <[email-masked]>
Date: Fri, 11 Aug 2017 18:32:57 +0000

If the plaintext length indicates a message type, then this could lead to the issue the original query posted. In that an observer might know what message type was passed. TLS padding is supposed to prevent this (but it doesn’t necessarily).

However, I argue that having TLS do significant padding for a protocol is bad design for that protocol. It’s one thing if it’s a few padding bytes, but the example given was 1023 bytes of padding.

Also as pointed out by Andrei Popov, the application needs to tell TLS how much padding to apply, so either way, the application has to deal with determining the padding length. Why not just make it part of the protocol in the first place?

OpenSSL has a callback scheme, and a block-based scheme for determining the amount of padding. Either way, the application is involved.

But my final point is that we are ignoring the amount of non-TLS processing that must be done on various message types (before the response is sent), and THAT might be even more of a giveaway than the minuscule timing difference due to counting padding in TLS.

On Aug 11, 2017, at 1:20 PM, Eric Rescorla <[email-masked]<mailto:[email-masked]>> wrote:

On Fri, Aug 11, 2017 at 9:47 AM, Nikos Mavrogiannopoulos <[email-masked]<mailto:[email-masked]>> wrote:
On Fri, Aug 11, 2017 at 5:57 PM, Eric Rescorla <[email-masked]<mailto:[email-masked]>> wrote:

On Fri, Aug 11, 2017 at 7:11 AM, Nikos Mavrogiannopoulos <[email-masked]<mailto:[email-masked]>> wrote:
Imagine the following scenario, where the server and client have this
repeated communication N times per day:

client     server
    --X-->
    <--Y--

Yes, we're aware of this, and it's an intentional design choice. The reasoning
was that once you have the padding removed, you'll need to operate on/copy
the unpadded content somewhere, and that's timing dependent anyway.

That is certainly an incorrect assumption. gnutls for example provides a zero-copy API, and I guess it is not the only implementation to have that.

And then the next thing that will happen is that the application will read the data, which is length-dependent. The problem is that the plaintext is variable length.

https://tools.ietf.org/html/draft-ietf-tls-tls13-21#appendix-E.3<https://urldefense.proofpoint.com/v2/url?u=https-3A__tools.ietf.org_html_draft-2Dietf-2Dtls-2Dtls13-2D21-23appendix-2DE.3&d=DwMFaQ&c=96ZbZZcaMF4w0F4jpN6LZg&r=QBEcQsqoUDdk1Q26CzlzNPPUkKYWIh1LYsiHAwmtRik&m=XJYxN2Gf0rNXPl3yadis8utHDuyRetUCeYdF-OmwAcQ&s=CJUfP5OPl4Uy3Igpm9hvAvuLiJlWdRLxSnagqfNZEZM&e=>

Yes.

I am not sure if that text is sufficient to cover that issue. It seems as if the cbc timing attack is re-introduced here and pushing the fix to implementers. It may be better no to provide padding functionality with this "feature", as unfortunately it will be used by applications.

I don't believe that this is analysis is correct. This timing channel only applies to the data after message integrity has been established (i.e., after AEAD processing), which is different from the situation in Lucky 13. It seems like what leaks here is the length of the plaintext, which is also what would be leaked if we simply did not have padding.

-Ekr

regards,
Nikos

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 11 Aug 2017 12:19:06 -0700

On Fri, Aug 11, 2017 at 11:32 AM, Short, Todd <[email-masked]> wrote:

> If the plaintext length indicates a message type, then this could lead to
> the issue the original query posted. In that an observer might know what
> message type was passed. TLS padding is supposed to prevent this (but it
> doesn’t necessarily).
>
> However, I argue that having TLS do significant padding for a protocol is
> bad design for that protocol. It’s one thing if it’s a few padding bytes,
> but the example given was 1023 bytes of padding.
>
> Also as pointed out by Andrei Popov, the application needs to tell TLS how
> much padding to apply, so either way, the application has to deal with
> determining the padding length. Why not just make it part of the protocol
> in the first place?
>

The consensus was to provide a generic scheme that applications could use,
or not.

-Ekr

>
> OpenSSL has a callback scheme, and a block-based scheme for determining
> the amount of padding. Either way, the application is involved.
>
> But my final point is that we are ignoring the amount of non-TLS
> processing that must be done on various message types (before the response
> is sent), and THAT might be even more of a giveaway than the minuscule
> timing difference due to counting padding in TLS.
>
> --
> -Todd Short
> // [email-masked]
> On Aug 11, 2017, at 1:20 PM, Eric Rescorla <[email-masked]> wrote:
>
>
>
>>> On Fri, Aug 11, 2017 at 7:11 AM, Nikos Mavrogiannopoulos <nmav@
>>> redhat.com> wrote:
>>>
>>>> <https://urldefense.proofpoint.com/v2/url?u=https-3A__tools.ietf.org_html_draft-2Dietf-2Dtls-2Dtls13-2D21-23appendix-2DE.3&d=DwMFaQ&c=96ZbZZcaMF4w0F4jpN6LZg&r=QBEcQsqoUDdk1Q26CzlzNPPUkKYWIh1LYsiHAwmtRik&m=XJYxN2Gf0rNXPl3yadis8utHDuyRetUCeYdF-OmwAcQ&s=CJUfP5OPl4Uy3Igpm9hvAvuLiJlWdRLxSnagqfNZEZM&e=>

---

From: "Short, Todd" <[email-masked]>
Date: Fri, 11 Aug 2017 19:22:37 +0000

On Aug 11, 2017, at 3:19 PM, Eric Rescorla <[email-masked]<mailto:[email-masked]>> wrote:
On Fri, Aug 11, 2017 at 11:32 AM, Short, Todd <[email-masked]<mailto:[email-masked]>> wrote:

The consensus was to provide a generic scheme that applications could use, or not.

-Ekr

I was referring to the protocol over TLS, not TLS itself, sorry for the confusion.

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Fri, 11 Aug 2017 14:45:15 -0400

> provides a generic padding mechanism to be used across application

The design approach that TLS 1.3 took was to provide a mechanism for
padding at the TLS layer, not to prescribe padding at the application
layer.  You actually probably need both to defend against traffic
analysis in the big picture.

Thoughtful, well-designed application-layer padding is likely to be
better than generic TLS-layer padding.  But not all applications can
actually accomodate padding (and it's not clear that folks have done the
thoughtful work even on those applications which *can* accomodate
padding).

TLS offers a generic mechanism to support the cases where the
application can't do padding, or where the implementer has no control
over (or insight into) the application itself.  It'll probably leak in
the way you describe, but it'll probably also be better than cleartext.

Furthermore, there are TLS messages that are not application data at
all -- so those parts *have* to be padded at the TLS layer, as the
application cannot directly affect their size.

A robust and safe padding approach needs to take into account all layers
of the stack at once and coordinate between them.  Without the padding
mechanism in TLS, it wouldn't be possible to coordinate across the whole
stack.

     --dkg

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Mon, 14 Aug 2017 09:11:53 +0200

On Fri, 2017-08-11 at 14:45 -0400, Daniel Kahn Gillmor wrote:
> mechanism in TLS, it wouldn't be possible to coordinate across the
> whole stack.

Typically protocol design which is build on top of other protocols
assumes that they operate as reasonably. I doubt a TLS implementor who
knows about this timing leak will be the one designing the application
protocol on top, so my bet is that we are going to see application
protocols defined which take advantage of that padding and believing
they offer a plaintext length protection.

That's why, I'd urge to underline this timing leak in the document
rather than hiding it in generic timing leak considerations text. We
already have experience with that. TLS 1.1 documented a similar leak
prominently:
"Implementation Note: Canvel et al. [CBCTIME] have demonstrated a ..."

Note however that documenting the problem itself didn't help in that
case, all implementations were vulnerably to the later lucky13 attack.
The best IMHO is to document the way to address the timing leak.

regards,
Nikos

---

From: Hubert Kario <[email-masked]>
Date: Mon, 14 Aug 2017 20:06:57 +0200

On Friday, 11 August 2017 19:04:05 CEST Andrei Popov wrote:
>   *   I don't argue with this but this is not the approach TLS 1.3 took. It
> At some point I thought we said that the TLS 1.3 padding
> mechanism was supposed to be application-driven (in the form of
> application-provided policy or simply desired pad size), which would mean
> that the application has to be involved anyway. 

Problem is, that the application doesn't know how much time did processing of 
the message took (even if it gets the information that the received message 
was padded, which is not possible with current common library APIs).

So even if the application takes exactly as much time to process a long 
request as it does to process a short request, the length of that processing 
will leak.

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

---

From: Hubert Kario <[email-masked]>
Date: Mon, 14 Aug 2017 20:16:01 +0200

> but the example given was 1023 bytes of padding.

the difference in processing that is equal to just few clock cycles is 
detectable over network[1]
 
> determining the padding length. Why not just make it part of the protocol

The problem is not when the application adds padding. The problem is when the 
padding is removed on the receiver side.
 
> But my final point is that we are ignoring the amount of non-TLS processing
> that must be done on various message types (before the response is sent),
> and THAT might be even more of a giveaway than the minuscule timing
> difference due to counting padding in TLS.

Sure, it can, and in most cases it will be. We are not talking about this 
situation.

When you are careful on the application level (which is fairly simple when you 
just are sending acknowledgement message), the timing will still be leaked.

1 - https://www.imperialviolet.org/2013/02/04/luckythirteen.html (very bottom)

---

From: Colm MacCárthaigh <[email-masked]>
Date: Tue, 15 Aug 2017 00:55:50 +0200

> detectable over network[1]

The post you reference actually says the opposite; "20 CPU cycles is
probably too small to exploit" ... and even today with very low
latency networks and I/O schedulers it remains very difficult to
measure that kind of timing difference remotely. But per the post, the
larger point is that it is prudent to be cautious.

> just are sending acknowledgement message), the timing will still be leaked.

There are application-level and tls-implementation-level approaches
that can prevent the network timing leak. The easiest is to only write
TLS records during fixed period slots.

For example, suppose your process can handle 100 connections
concurrently, then you can divide 1ms into 100 slots of 10
microseconds each. Every 1ms you have a writer thread or process
'visit' each connection (you may use an epoll/kqueue driven I/O loop
or similar for this) during its fixed slot and send its pending
output.

-- 
Colm

---

From: Hubert Kario <[email-masked]>
Date: Tue, 15 Aug 2017 13:55:40 +0200

On Tuesday, 15 August 2017 00:55:50 CEST Colm MacCárthaigh wrote:
> probably too small to exploit"

exactly what we though about cbc padding at the time TLS 1.1 was published...

> ... and even today with very low
> measure that kind of timing difference remotely.

simply not true[1], you can measure the times to arbitrary precision with any 
real world network connection, it will just take more tries, not infinite 
tries

> But per the post, the

exactly, unless you can show that the difference is not measurable, under all 
conditions, you have to assume that it is.

> > When you are careful on the application level (which is fairly simple when
> > you just are sending acknowledgement message), the timing will still be
> > leaked.

sure it is, it also limits available bandwidth and it will always use that 
amount of bandwidth, something which is not always needed

we are not concerned if the issue can be workarouded, we want to be sure that 
the TLS stack does not undermine application stack work towards constant time 
behaviour

 1 - http://www.isg.rhul.ac.uk/tls/TLStiming.pdf

---

From: Hubert Kario <[email-masked]>
Date: Tue, 15 Aug 2017 15:31:56 +0200

I've created a Pull Request that introduces requirement for constant time 
processing of padding and an example on how to do it:

https://github.com/tlswg/tls13-spec/pull/1073

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 15 Aug 2017 16:54:15 +0300

> https://github.com/tlswg/tls13-spec/pull/1073

-1

Except doing the depad in constant-time is useless if you just re-
introduce the timing leaks at the next step. Actually not introducing
timing leaks in TLS library requires special API for passing the data
to application... API that has had no reason to exist so far, and is
more complicated to use than current read or zerocopy callback APIs.

And even if you have such special API, it is extremely doubtful how
many applications could use it correctly. Constant-time processing of
variable-length data is extremely hard (LUCKY13 anyone?)

Oh, and then there are timing leaks when sending data too...

-Ilari

---

From: Hubert Kario <[email-masked]>
Date: Tue, 15 Aug 2017 16:16:10 +0200

On Tuesday, 15 August 2017 15:54:15 CEST Ilari Liusvaara wrote:
> to application...

In C you pass data to application using pointer to memory location and a 
length variable. Padding influences only the length variable value. How 
exactly can you do that in _non_ constant time?

> API that has had no reason to exist so far, and is

with current read(3), you require the application to provide a buffer the size 
of the whole padded data, you copy the whole padded data, you return a length 
that truncates the content type and padding.

I fail to see how is that a "special API"

> variable-length data is extremely hard (LUCKY13 anyone?)

right, so because it is hard, we should just throw our hands in the air and 
walk away?

The point is that, if possible, we shouldn't undermine the work of 
applications that *do* have constant-time processing of variable-length data.

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 15 Aug 2017 08:28:22 -0700

I generally agree with Ilari. To recap what I said on the PR:
I think it would be fine to sharpen the point about padding leaking
information and I'd take a short PR for that. I don't believe it's
necessary either to require that it be constant time (for the reasons I
indicated on-list and already documented in the spec) or to describe a
specific algorithm, especially at this point on the document life cycle.

-Ekr

---

From: Colm MacCárthaigh <[email-masked]>
Date: Tue, 15 Aug 2017 18:27:27 +0200

> exactly what we though about cbc padding at the time TLS 1.1 was published...

I'm not going to defend the poor design of TLS1.1 padding, but it does
remain unexploitable over real-world networks. The Lucky13 attack that
you reference is practical against DTLS, but not TLS. It is worth
understanding the nuance, because the differences can help us continue
to make TLS more robust and hint where to optimize. The property that
has protected has TLS Vs DTLS is non-replayability, so it's important
we keep that.

> real world network connection, it will just take more tries, not infinite

Surely the Nyquist limits apply? The fundamental resolution of
networks is finite. Clock cycles are measured in partial billionths of
a second, but even 10Gbit/sec networks use framing (85 byte minimum)
in a way that gives you a resolution of around 70 billionths of a
second. Nyquist says that to measure a signal you need a sampling
resolution twice that of the signal itself ... that's about 2 orders
of magnitude of distance to cover in this case.

> amount of bandwidth, something which is not always needed

Constant-time schemes work by taking the maximum amount of time in
every case. This fundamentally reduces the throughput; because small
payloads don't get a speed benefit.

> the TLS stack does not undermine application stack work towards constant time

The TLS stack can take a constant amount of time to encrypt/decrypt a
record, regardless of padding length, but it's very difficult to see
how it can pass data to/from the application in constant time; besides
the approach I outlined, which you don't like.

Note that these problems get harder with larger amounts of padding.
Today the lack of padding makes passive traffic analysis attacks very
easy. It's extremely feasible for an attacker to categorize request
and content lengths (e.g. every page on Wikipedia) and figure out what
page is user is browsing. That's a practical attack, that definitely
works, today, and it's probably the most practical and most serious
attack that we do know works. The fix for that attack is padding, and
quite large amounts are needed to defeat traffic analysis. But that
will make the timing challenges harder. In that context: it's
important to remember; so far those timing attacks have not been
practical. We don't want to optimize for the wrong problem.

-- 
Colm

---

From: Hubert Kario <[email-masked]>
Date: Tue, 15 Aug 2017 19:02:13 +0200

On Tuesday, 15 August 2017 18:27:27 CEST Colm MacCárthaigh wrote:
> > simply not true[1], you can measure the times to arbitrary precision with
> > any real world network connection, it will just take more tries, not
> > infinite tries
> 

Nyquist applies to a single sample, not to multiple sampling of the same 
signal.

In other words, if I sample a signal 4 times, and once I get 0 and 3 times I 
get 1, then assuming uniform distribution[1] I can deduce that the signal is 
closer to 0.75 than it is to 1, 0 or 0.5.

 1 - yes, it's a "spherical cow in a vacuum" example

> > exactly, unless you can show that the difference is not measurable, under
> > all conditions, you have to assume that it is.
> > 

My point is that if I don't care about the side channel of presence or absence 
of the communication, then I am limited by the size of the maximal record, not 
amount of records I can send in a second. So my bandwidth is limited in 
"Transaction Per Second" sense, not actual bandwidth (measured in bytes per 
second)
 
> > we are not concerned if the issue can be workarouded, we want to be sure
> > that the TLS stack does not undermine application stack work towards
> > constant time behaviour
> 

As I said in a different email, in C you pass a pointer and length, that can 
be returned in constant time quite easily (even in read(3)-like API).

encryption is indeed much harder

> practical. We don't want to optimize for the wrong problem.

True, that being said, I'd prefer if we did release protocol in which we can't 
poke holes before the official release...
-- 
Regards,
Hubert Kario
Senior Quality Engineer, QE BaseOS Security team
Web: www.cz.redhat.com
Red Hat Czech s.r.o., Purkyňova 115, 612 00  Brno, Czech Republic

---

From: Hubert Kario <[email-masked]>
Date: Tue, 15 Aug 2017 19:42:46 +0200

On Tuesday, 15 August 2017 17:28:22 CEST Eric Rescorla wrote:
> information and I'd take a short PR for that.

I've prepared https://github.com/tlswg/tls13-spec/pull/1074 with that in mind.

> I don't believe it's