[TLS] cost of padding removal in TLS1.3 [was: Possible timing attack on TLS 1.3 padding mechanism]

[Nikos Mavrogiannopoulos <[e-mail]>]

On Thu, 2018-03-01 at 21:52 +0000, Paterson, Kenny 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 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).

Hi,
 I'd like to get back into that old thread because we've figured out
that making the padding removal not depending on the data is quite
costly for aes-gcm on a modern processor. Roughly, the record
processing time drops by half for large packets comparing to TLS1.2, in
effect pushing implementors to make the default padding removal time-
variable. Has this performance drop been observed by others?

regards,
Nikos