Subject: Re: [TLS] Possible timing attack on TLS 1.3 padding mechanism

From: "Paterson, Kenny" <[email-masked]>
Date: Thu, 1 Mar 2018 21:52:51 +0000

Hi,

I've been analysing the record protocol spec for TLS 1.3 a bit, specifically the new padding mechanism. I think there's a possible timing attack on a naïve implementation of de-padding. Maybe this is already known to people who've been paying more attention than me!

Recall that the padding mechanism permits an arbitrary number of 00 bytes to be added after the plaintext and content type byte, up to the max record size. This data is then encrypted using whichever AEAD scheme is specified in the cipher suite. This padding scheme is quite important for TLS 1.3 because the current AEAD schemes do leak the length of record plaintexts. There should be no padding oracle style attack possible because of the integrity guarantees of the AEAD schemes in use. 

The idea for the timing attack is as follows. 

The natural way to depad (after AEAD decryption) is to remove the 00 bytes at the end of the plaintext structure one by one, until a non-00 byte is encountered. This is then the content type byte. Notice that the amount of time needed to execute this depadding routine would be proportional to the number of padding bytes. If there's some kind of response record for this record, then measuring the time taken from reception of the target record to the appearance of the response record can be used to infer information about the amount of padding, and thereby, the true length of the plaintext (since the length of the padded plaintext is known from the ciphertext length).

The timing differences here would be small. But they could be amplified by various techniques. For example, the cumulative timing difference over many records could allow leakage of the sum of the true plaintext lengths. Think of a client browser fetching a simple webpage from a browser. The page is split over many TLS records, each of which is individually padded, with the next GET request from the client being the "response record". (This is a pretty simplistic view of how a web browser works, I know!). The total timing difference might then be sufficient for webpage fingerprinting, for example. 

I'm not claiming this is a big issue, but maybe something worth thinking about and addressing in the TLS 1.3 spec.

There's at least a couple of ways to avoid the problem:

1. Do constant-time depadding - by examining every byte in the plaintext structure even after the first non-00 byte is encountered. 
2. Add an explicit padding length field at the end of the plaintext structure, and removing padding without checking its contents. (This should be safe because of the AEAD integrity guarantees.) 

Option 2 is probably a bit invasive at this late stage in the specification process. Maybe a sentence or two on option 1 could be added to the spec.

Thoughts?

Cheers,

Kenny

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 1 Mar 2018 14:27:13 -0800

Hi Kenny,

Yes, this is something we are aware of. Here's the relevant text from the
document:
https://tlswg.github.io/tls13-spec/draft-ietf-tls-tls13.html#rfc.appendix.E.3

I don't think we're likely to change the protocol, but if you have some
proposed text
that you think would be informative above and beyond what we already have,
please
send it along.

Best,
-Ekr

On Thu, Mar 1, 2018 at 1:52 PM, Paterson, Kenny <[email-masked]>
wrote:

> Hi,
>
> I've been analysing the record protocol spec for TLS 1.3 a bit,
> specifically the new padding mechanism. I think there's a possible timing
> attack on a naïve implementation of de-padding. Maybe this is already known
> to people who've been paying more attention than me!
>
> Recall that the padding mechanism permits an arbitrary number of 00 bytes
> to be added after the plaintext and content type byte, up to the max record
> size. This data is then encrypted using whichever AEAD scheme is specified
> in the cipher suite. This padding scheme is quite important for TLS 1.3
> because the current AEAD schemes do leak the length of record plaintexts.
> There should be no padding oracle style attack possible because of the
> integrity guarantees of the AEAD schemes in use.
>
> The natural way to depad (after AEAD decryption) is to remove the 00 bytes
> at the end of the plaintext structure one by one, until a non-00 byte is
> encountered. This is then the content type byte. Notice that the amount of
> time needed to execute this depadding routine would be proportional to the
> number of padding bytes. If there's some kind of response record for this
> record, then measuring the time taken from reception of the target record
> to the appearance of the response record can be used to infer information
> about the amount of padding, and thereby, the true length of the plaintext
> (since the length of the padded plaintext is known from the ciphertext
> length).
>
> The timing differences here would be small. But they could be amplified by
> various techniques. For example, the cumulative timing difference over many
> records could allow leakage of the sum of the true plaintext lengths. Think
> of a client browser fetching a simple webpage from a browser. The page is
> split over many TLS records, each of which is individually padded, with the
> next GET request from the client being the "response record". (This is a
> pretty simplistic view of how a web browser works, I know!). The total
> timing difference might then be sufficient for webpage fingerprinting, for
> example.
>
> I'm not claiming this is a big issue, but maybe something worth thinking
> about and addressing in the TLS 1.3 spec.
>
> 1. Do constant-time depadding - by examining every byte in the plaintext
> structure even after the first non-00 byte is encountered.
> 2. Add an explicit padding length field at the end of the plaintext
> structure, and removing padding without checking its contents. (This should
> be safe because of the AEAD integrity guarantees.)
>
> Option 2 is probably a bit invasive at this late stage in the
> specification process. Maybe a sentence or two on option 1 could be added
> to the spec.
>
> Thoughts?
>
> Cheers,
>
> Kenny
>
>
>
>
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: "Paterson, Kenny" <[email-masked]>
Date: Thu, 1 Mar 2018 22:30:40 +0000

Hi Ekr.

Ah that's great, thanks - and I think the text in the Appendix already addresses the issues very well.

Sorry for the bandwidth consumption.

Cheers,

Kenny 

-----Original Message-----
From: Eric Rescorla <[email-masked]>
Date: Thursday, 1 March 2018 at 22:27
To: "Paterson, Kenny" <[email-masked]>
Cc: "[email-masked]" <[email-masked]>
Subject: Re: [TLS] Possible timing attack on TLS 1.3 padding mechanism

    Hi Kenny,

    Yes, this is something we are aware of. Here's the relevant text from the document:
    https://tlswg.github.io/tls13-spec/draft-ietf-tls-tls13.html#rfc.appendix.E.3

    I don't think we're likely to change the protocol, but if you have some proposed text
    that you think would be informative above and beyond what we already have, please
    send it along.

    Best,
    -Ekr

    

    
    On Thu, Mar 1, 2018 at 1:52 PM, Paterson, Kenny 
    <[email-masked]> wrote:
    
    Hi,
    
    I've been analysing the record protocol spec for TLS 1.3 a bit, specifically the new padding mechanism. I think there's a possible timing attack on a naïve implementation of de-padding. Maybe this is already known to people who've been paying more attention
     than me!
    
    Recall that the padding mechanism permits an arbitrary number of 00 bytes to be added after the plaintext and content type byte, up to the max record size. This data is then encrypted using whichever AEAD scheme is specified in the cipher suite. This padding
     scheme is quite important for TLS 1.3 because the current AEAD schemes do leak the length of record plaintexts. There should be no padding oracle style attack possible because of the integrity guarantees of the AEAD schemes in use.

    The natural way to depad (after AEAD decryption) is to remove the 00 bytes at the end of the plaintext structure one by one, until a non-00 byte is encountered. This is then the content type byte. Notice that the amount of time needed to execute this depadding
     routine would be proportional to the number of padding bytes. If there's some kind of response record for this record, then measuring the time taken from reception of the target record to the appearance of the response record can be used to infer information
     about the amount of padding, and thereby, the true length of the plaintext (since the length of the padded plaintext is known from the ciphertext length).
    
    The timing differences here would be small. But they could be amplified by various techniques. For example, the cumulative timing difference over many records could allow leakage of the sum of the true plaintext lengths. Think of a client browser fetching a
     simple webpage from a browser. The page is split over many TLS records, each of which is individually padded, with the next GET request from the client being the "response record". (This is a pretty simplistic view of how a web browser works, I know!). The
     total timing difference might then be sufficient for webpage fingerprinting, for example.

    

    Thoughts?
    
    Cheers,
    
    Kenny

---

From: Colm MacCárthaigh <[email-masked]>
Date: Thu, 1 Mar 2018 14:40:27 -0800

There's another, more cache-friendly approach too, which is to record the
position of the highest non-zero byte as the decryption occurs (while that
cache-line of plaintext is still in-cache) in-order. I found that a bit
easier to implement in constant time too because it's easy to generate an
all-1s mask that's conditional on a non-zero value.

-- 
Colm

---

From: David Benjamin <[email-masked]>
Date: Thu, 01 Mar 2018 23:00:21 +0000

The data ultimately needs to be returned to the calling application,
presumably some HTTP parser, which in turn passes data up to more calling
code and so on. Conversely, the data must have been produced by some also
application-level process on the sender, some HTTP serializer, before it
was handed off to TLS at all. All of that work is going to freely branch on
the length. (Indeed even the traditional read/write APIs of most TLS
libraries are the wrong shape here.) Patching just the unpad corner is not
very useful without a clearer story for the rest.

I'd actually suggest that, for cases where the length needs to remain
impervious to timing leaks end-to-end, TLS is the wrong layer to pad.
Writing a fully general HTTP parser which avoids leaking the padding length
across arbitrary record boundaries not under your control sounds
implausible. You'd have to account for padding potentially between *every
byte* at the lowest-level serialization.

Rather, the higher up the stack you insert your padding, the fewer layers
you must traverse. If the process is designed to treat some length as
secret in the first place, it probably has the "padding" built-in. E.g., EC
private keys are serialized and (at least in good implementations)
represented in memory as fixed-width, bounded only by the curve order, even
though an individual private key might happen to have a leading zero byte
or so.

David

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 01 Mar 2018 18:23:18 -0500

On Thu 2018-03-01 21:52:51 +0000, Paterson, Kenny wrote:
> I think there's a possible timing attack on a naïve implementation of
> de-padding.

Thanks for observing this, Kenny!  I think this came up when we were
designing the padding originally, and iirc, the general consensus was:

 (a) this scheme allows people to not pad at all, which saves bytes in
     the most heavily traffic-constrained case, and

 (b) there may well be timing attacks based on the handling of the
     non-padded data too, and those are likely to be stronger timing
     effects than the effects in the padding layer.

I think with (b) we might have gotten a bit overly nihilistic -- for one
thing, depadding probably happens in the TLS layer of the implementation
itself, so any response generated by the TLS layer will have tighter
timing bounds than anything that does data handling.  And, implementers
that use any given TLS stack can control their own timing code, but
can't necessarily control the code of the TLS implementation that
they're sitting atop.  TLS implementers probably don't want to leak info
that the user has deliberately taken steps to avoid leaking!

Our implementer guidance should also already say that the best place to
pad is at the application layer, where the implementer can more
accurately design padding that meets the expected usage profile --
padding at the TLS layer is available for implementers that don't have
this option, but probably isn't the optimal solution.

> This padding scheme is quite important for TLS 1.3 because the current
> AEAD schemes do leak the length of record plaintexts.

thanks for acknowledging the value of the padding. i agree! :)

The timing-based size leak you're talking about still looks harder to
attack reliably than the direct size leakage we have without the
padding.

> 1. Do constant-time depadding - by examining every byte in the
> plaintext structure even after the first non-00 byte is encountered.

do you have concrete implementation suggestions?

I'm not sure how to convince a clever compiler to actually run this
entire loop if you count from the back -- i can easily see the tail of
the walk being optimized away since it has no bearing on the rest of the
program control or data flow.

You could of course check from the front of the plaintext, keeping every
non-zero value:

  char ptype = 0;
  for (i = 0; i < plaintext_len; i++)
    if plaintext[i]
      ptype = plaintext[i];

but iiuc, this leaks the number of zeros in the plaintext overall,
assuming that the store instruction has noticeable time.

can you tell i'm not good at devising constant-time code? :P If there's
a concrete suggestion that we think will work for common
implementations, i would have no problem including it as implementer
guidance.

> structure, and removing padding without checking its contents. (This
> should be safe because of the AEAD integrity guarantees.)
>
> specification process. Maybe a sentence or two on option 1 could be
> added to the spec.

It's not only too late to take this approach, i think we explicitly
rejected this option because of the cost it imposes on unpadded packets,
as mentioned above.

        --dkg

---

From: Martin Thomson <[email-masked]>
Date: Fri, 2 Mar 2018 12:12:57 +1100

>   for (i = 0; i < plaintext_len; i++)

What about ?

size_t l[2];
size_t t[2];
for (i = 0; i < plaintext_len; ++i) {
  l[plaintext[i] != 0] = i;
  t[plaintext[i] != 0] = plaintext[i];
}
unpadded_len = l[0] - 1;
content_type = t[1];

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 1 Mar 2018 17:17:22 -0800

>   t[plaintext[i] != 0] = plaintext[i];

This is fun, but I want to note that many (most) APIs are not zero-copy but
rather involve
SSL_Read() copying data from some internal buffer into a caller supplied
buffer. So
that operation also needs to be made constant time (e.g., by copying the
whole
padded region?), and so on...

-Ekr

---

From: Martin Thomson <[email-masked]>
Date: Fri, 2 Mar 2018 12:29:26 +1100

> padded region?), and so on...

Forgive me for indulging :)  For the record, I think that the current
text is perfectly adequate.

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Fri, 02 Mar 2018 09:32:12 +0100

On Thu, 2018-03-01 at 21:52 +0000, Paterson, Kenny wrote:
> specifically the new padding mechanism. I think there's a possible
> timing attack on a naïve implementation of de-padding. Maybe this is
> already known to people who've been paying more attention than me!
> 
> Recall that the padding mechanism permits an arbitrary number of 00
> bytes to be added after the plaintext and content type byte, up to
> the max record size. This data is then encrypted using whichever AEAD
> scheme is specified in the cipher suite. This padding scheme is quite
> important for TLS 1.3 because the current AEAD schemes do leak the
> length of record plaintexts. There should be no padding oracle style
> attack possible because of the integrity guarantees of the AEAD
> schemes in use. 
> 
> The natural way to depad (after AEAD decryption) is to remove the 00
> bytes at the end of the plaintext structure one by one, until a non-
> 00 byte is encountered. This is then the content type byte. Notice
> that the amount of time needed to execute this depadding routine
> would be proportional to the number of padding bytes. If there's some
> kind of response record for this record, then measuring the time
> taken from reception of the target record to the appearance of the
> response record can be used to infer information about the amount of
> padding, and thereby, the true length of the plaintext (since the
> length of the padded plaintext is known from the ciphertext length).
> 
> The timing differences here would be small. But they could be
> amplified by various techniques. For example, the cumulative timing
> difference over many records could allow leakage of the sum of the
> true plaintext lengths. Think of a client browser fetching a simple
> webpage from a browser. The page is split over many TLS records, each
> of which is individually padded, with the next GET request from the
> client being the "response record". (This is a pretty simplistic view
> of how a web browser works, I know!). The total timing difference
> might then be sufficient for webpage fingerprinting, for example. 
> 
> I'm not claiming this is a big issue, but maybe something worth
> thinking about and addressing in the TLS 1.3 spec.
> 

Hi,
 It was brought previously to the WG [0], and the bottom line was to push
for any solution to implementations.

As of the "naïve implementation of de-padding", I wouldn't put like that.
It is a straightforward method of de-padding after reading the draft, and
I believe all implementations out there use that method.

regards,
Nikos

[0].
https://www.ietf.org/mail-archive/web/tls/current/msg24365.html

---

From: "Paterson, Kenny" <[email-masked]>
Date: Fri, 2 Mar 2018 10:17:21 +0000

Hi,

> On 2 Mar 2018, at 08:32, Nikos Mavrogiannopoulos <[email-masked]> wrote:
> 

Thanks Nikos - sorry for missing your post from last August. At least I'm now only six months behind the curve :-)

> I believe all implementations out there use that method.

Agreed. "Natural" would have been a better choice here. 

Cheers,

Kenny