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: Colm MacCárthaigh <colm@allcosts.net>
Date: Thu, 01 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
- [TLS] cost of padding removal in TLS1.3 [was: Pos… Nikos Mavrogiannopoulos
- Re: [TLS] Possible timing attack on TLS 1.3 paddi… Paterson, Kenny
- Re: [TLS] Possible timing attack on TLS 1.3 paddi… Eric Rescorla
- Re: [TLS] Possible timing attack on TLS 1.3 paddi… Paterson, Kenny
- Re: [TLS] Possible timing attack on TLS 1.3 paddi… Colm MacCárthaigh
- Re: [TLS] Possible timing attack on TLS 1.3 paddi… David Benjamin
- Re: [TLS] Possible timing attack on TLS 1.3 paddi… Daniel Kahn Gillmor
- Re: [TLS] Possible timing attack on TLS 1.3 paddi… Martin Thomson
- Re: [TLS] Possible timing attack on TLS 1.3 paddi… Eric Rescorla
- Re: [TLS] Possible timing attack on TLS 1.3 paddi… Martin Thomson
- Re: [TLS] Possible timing attack on TLS 1.3 paddi… Nikos Mavrogiannopoulos
- Re: [TLS] Possible timing attack on TLS 1.3 paddi… Paterson, Kenny