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

Colm MacCárthaigh <colm@allcosts.net> Thu, 01 March 2018 22:40 UTC

Return-Path: <colm@allcosts.net>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 2C3B4124B0A for <tls@ietfa.amsl.com>; Thu, 1 Mar 2018 14:40:31 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 3.102
X-Spam-Level: ***
X-Spam-Status: No, score=3.102 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, GB_SUMOF=5, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=allcosts-net.20150623.gappssmtp.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 16FwUnWa97P9 for <tls@ietfa.amsl.com>; Thu, 1 Mar 2018 14:40:29 -0800 (PST)
Received: from mail-yb0-x236.google.com (mail-yb0-x236.google.com [IPv6:2607:f8b0:4002:c09::236]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 3B7A1126CBF for <tls@ietf.org>; Thu, 1 Mar 2018 14:40:29 -0800 (PST)
Received: by mail-yb0-x236.google.com with SMTP id i13-v6so2760657ybl.9 for <tls@ietf.org>; Thu, 01 Mar 2018 14:40:29 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=allcosts-net.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=5BoHOSA1bp5mLb6qmpvzZ3QvoVU9/ebVTcRKZBpAR3Q=; b=g3wKiaQTBjnqehNc7K1Fy5n859tLeiC5k1P3H0Vg3Xw8A8777d0CmoD4qen+E3evza Tv7OV4uOI2VWOduECTTN3/VrDYzr6RhQnT5M7IxA1tTvb57ogXPHw9fH01FqwhW2sxQf Qvb2BmknD/QehOWyZFDDfZz8T3mrJD1dRovLHhjn9TP7yWVv2oUl5Ipe4oc/xnFeWw9i 6VJwto+4XAAnonH5MOBAVWE3o8fT1xEdOMsf9a8YzY7+cCwf2o30nUy4npsny+a1uKmq ISOxu/KR3vb4Ts2BHpN9ztdx7S55Cd/kNN+It3HoNvoviIbN/7NsOuO9387T1cc/EzNg RjBw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=5BoHOSA1bp5mLb6qmpvzZ3QvoVU9/ebVTcRKZBpAR3Q=; b=DM2fuee3KqY/TRQb8ciZ63iNddm30415S0p5cC8Lyrp0tYittKZdrTPsHbt4YHH2YD 5vkgAsM0zjzUBVga4utiUFhuDQWp8UgS/SxUsb1Dx5KYqB5q3JAJaNrTBT+Ph4K9uXU1 LSCYtENdD8OP856G4B/0T20rTYNlY2gYNXrNuDoDDuHOm7aBBTt9QtX+/W4zuwAlCAcs ERPmCuMcP9eAsTTgNedYNYzleNrAuN0vN5eLsP1S7215u/RhC6HTnxL4yv7nYR/OZR/1 4z3FTB47KIH3LaPsxP4emePpdKLJ2wE8aofC/U/9/CuyGwBP81ycj06Z1DambxxvsMc/ CEDg==
X-Gm-Message-State: AElRT7FgmdlvLx+3rhqsvVg9CUhOii57kHR7a9uJepVbWX9OM/XoFKMR uctBOfc7bYP5CJTXHGs4HFWEA3MIIAL4bQ+IJt0lzg==
X-Google-Smtp-Source: AG47ELukefbc9tw2/6t11aqCggph7x9t8cBv902whqDCxhuVFc4/h/a2i3SfruCLg7wDSWlZ8O2IG5GIPK+8qR7oC5w=
X-Received: by 2002:a25:8b91:: with SMTP id j17-v6mr2493177ybl.252.1519944028011; Thu, 01 Mar 2018 14:40:28 -0800 (PST)
MIME-Version: 1.0
Received: by 10.129.108.203 with HTTP; Thu, 1 Mar 2018 14:40:27 -0800 (PST)
In-Reply-To: <16A9FD3A-7805-4130-8438-39D0D3E7E3AB@rhul.ac.uk>
References: <16A9FD3A-7805-4130-8438-39D0D3E7E3AB@rhul.ac.uk>
From: =?UTF-8?Q?Colm_MacC=C3=A1rthaigh?= <colm@allcosts.net>
Date: Thu, 1 Mar 2018 14:40:27 -0800
Message-ID: <CAAF6GDfJsh-pVKsiG8==mFYwSa4e2Q3CDLhQe=+vQdSpyN1OaQ@mail.gmail.com>
To: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
Cc: "<tls@ietf.org>" <tls@ietf.org>
Content-Type: multipart/alternative; boundary="000000000000de54730566618b9e"
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/asZjkqWag2AW7ZhJeLGBIJvrJLc>
Subject: Re: [TLS] Possible timing attack on TLS 1.3 padding mechanism
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 01 Mar 2018 22:40:31 -0000

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.

On Thu, Mar 1, 2018 at 1:52 PM, Paterson, Kenny <Kenny.Paterson@rhul.ac.uk>
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).
>
> 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
>
>
>
>
> _______________________________________________
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
>



-- 
Colm