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

Nikos Mavrogiannopoulos <nmav@redhat.com> Mon, 18 June 2018 09:41 UTC

Return-Path: <nmav@redhat.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 9211B130E3B for <tls@ietfa.amsl.com>; Mon, 18 Jun 2018 02:41:40 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.921
X-Spam-Status: No, score=-1.921 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id xUl-fbyZAUio for <tls@ietfa.amsl.com>; Mon, 18 Jun 2018 02:41:29 -0700 (PDT)
Received: from mail-wm0-f50.google.com (mail-wm0-f50.google.com []) (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 67401130DCF for <tls@ietf.org>; Mon, 18 Jun 2018 02:41:29 -0700 (PDT)
Received: by mail-wm0-f50.google.com with SMTP id p126-v6so12951124wmb.2 for <tls@ietf.org>; Mon, 18 Jun 2018 02:41:29 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:message-id:subject:from:to:cc:date:in-reply-to :references:mime-version:content-transfer-encoding; bh=LkTv9bxBOlbApzUX/CQx/QbUJT9v9gm3humptBW3AMU=; b=LZM62z2KGVej7jrOgmNN3PFTflCuGcyQFHaUZLhRwbBHER7Gcb+hNejUAcf5HtvMGR 3OsgOQ6d3//KTNK3XJjg0/1W0Z7rGNkaaKyC9yuToX7LhE6XQM/RmYenJlsXga1fLrvb NtcGphkWvB1RfH0ZkgLOfb7eAJBWbpgi5Dugjlc0QeCH++2lA8DmmFAu13y2ORt5eBln coB0YI+ZCwRJo0rLo0gerzBJckNEEcZcxqGrZaeqj+eX/R+F0gCukOJEcjT6tWykr1AC stawsw23P4rHI5scJN9xdmdgNaYTPjlyF3zv5oSf4I9L8Dbr86JxjfOvegxf/rCqm8Hi rWag==
X-Gm-Message-State: APt69E0CARLfgbMotRSc490+HBSajSGKavXtEdqyu15I4YcGR77zFkBP bqiCDP1jYcdmBlN2K/Um1ex4RBl7fGI=
X-Google-Smtp-Source: ADUXVKJtdDGC3rF+swsv0n7jbNjJK3DyLYO/8iAvRkhTNtyRdgwZkwWy4mLiGhtovbSnoVKIvlu1uQ==
X-Received: by 2002:a1c:4a9d:: with SMTP id n29-v6mr7389635wmi.46.1529314887579; Mon, 18 Jun 2018 02:41:27 -0700 (PDT)
Received: from dhcp-10-40-1-102.brq.redhat.com (nat-pool-brq-t.redhat.com. []) by smtp.gmail.com with ESMTPSA id a184-v6sm7991953wmf.30.2018. (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Mon, 18 Jun 2018 02:41:26 -0700 (PDT)
Message-ID: <5461a61b9b22446ef38841c8eda16381b7fa8628.camel@redhat.com>
From: Nikos Mavrogiannopoulos <nmav@redhat.com>
To: tls@ietf.org, tls@ietf.org
Date: Mon, 18 Jun 2018 11:41:25 +0200
In-Reply-To: <16A9FD3A-7805-4130-8438-39D0D3E7E3AB@rhul.ac.uk>
References: <16A9FD3A-7805-4130-8438-39D0D3E7E3AB@rhul.ac.uk>
Content-Type: text/plain; charset="UTF-8"
X-Mailer: Evolution 3.28.2 (3.28.2-1.fc28)
Mime-Version: 1.0
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/K8ZTOXprpmkWeZkccaBRVaNHz2A>
Subject: [TLS] cost of padding removal in TLS1.3 [was: Possible timing attack on TLS 1.3 padding mechanism]
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.26
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: Mon, 18 Jun 2018 09:41:41 -0000

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

 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?