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

[Daniel Kahn Gillmor <[e-mail]>]

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.

> 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.

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