Re: New confidentiality and integrity limits

Martin Thomson <mt@lowentropy.net> Thu, 25 June 2020 00:58 UTC

Return-Path: <mt@lowentropy.net>
X-Original-To: quic@ietfa.amsl.com
Delivered-To: quic@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 83F253A120B for <quic@ietfa.amsl.com>; Wed, 24 Jun 2020 17:58:34 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level:
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_MSPIKE_H4=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=lowentropy.net header.b=OTkuYu3L; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=T/hg1eGx
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 ht7zzuG3djJN for <quic@ietfa.amsl.com>; Wed, 24 Jun 2020 17:58:32 -0700 (PDT)
Received: from wout4-smtp.messagingengine.com (wout4-smtp.messagingengine.com [64.147.123.20]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 8A7463A120A for <quic@ietf.org>; Wed, 24 Jun 2020 17:58:32 -0700 (PDT)
Received: from compute2.internal (compute2.nyi.internal [10.202.2.42]) by mailout.west.internal (Postfix) with ESMTP id 4AC0FA5F for <quic@ietf.org>; Wed, 24 Jun 2020 20:58:31 -0400 (EDT)
Received: from imap2 ([10.202.2.52]) by compute2.internal (MEProxy); Wed, 24 Jun 2020 20:58:31 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=lowentropy.net; h=mime-version:message-id:in-reply-to:references:date:from:to :subject:content-type:content-transfer-encoding; s=fm2; bh=dMwkg IFCmndv1dhVMP7p+qL68Z9W/x7q6O16Icg36MI=; b=OTkuYu3LM2le6xdw8XxH0 3SWV/HQBtjA6tltOTaW559j5go5xaT+9m+T2c2aZdqra/JLxg9BEUFNGRUQR8wPH r1sZevVLd4+zUrDSJGpYir74MZIWfBsE0HINVzyZqLgMkIxTeB1t3FE09LFCRszJ UIBJMqNqPvuT0SmdreL6+NML0b3qOrMD29dTvj2sGe5e29RSJ6AoxDqu8eHfK8jE anSb82HTLcdv5RlFQDiW/OzRsXz50YN0vh358j/ad8YrVUaFKewjrsPHWE/uPkVE 96bd4t3SsmmzZVfPeSEhKohRNIxi3lfUePPZj9tJYU5ILeEQsCm3Ljcp/cdUlqeZ A==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender :x-sasl-enc; s=fm3; bh=dMwkgIFCmndv1dhVMP7p+qL68Z9W/x7q6O16Icg36 MI=; b=T/hg1eGx7mVliyAm8CKLPxwVzlNGWuEPsCv/sAiVfMW+6QSEdG6LMiErt ybFdl+Z2Uz3JmxmZU3SlRc3V9XVWBuxwt72Ol+6AswDKQ8gqDHNKQgO3Jt9Y7pri XUMK/JVETNDmmwh6JgzRk1xn/OyOk/GsAKnhtlMnfr7VMmS3vITUXQjo1yTVm7DF 2/1S/fc6+eUyYOJLy1cWQbWoKf36IZDzKCAcBls5Px8wbfaO0Z3hqdzya/RmJMwc RPcpmzvjVqAsLUzPlPJhdf3Ghhxc49WaPzSpUgU3+0kpegjEdAy7owDZWoTRTSG4 OvYExsiAy+VJhr4sG6q6jF2bG1fnw==
X-ME-Sender: <xms:tvbzXlacXT1WHZldTqdIk_UFEKfX-CdiIlhHPMQ6xmVqxwym6QvbuQ>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduhedrudekkedggedtucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfgjfhffhffvufgtgfesth hqredtreerjeenucfhrhhomhepfdforghrthhinhcuvfhhohhmshhonhdfuceomhhtsehl ohifvghnthhrohhphidrnhgvtheqnecuggftrfgrthhtvghrnhepkeejgfetvdeuheevvd elgffgleegfeehueeufefhgeevgfeuffeggedvtdevkefgnecuffhomhgrihhnpehgihht hhhusgdrrdgtohhmpdhgihhthhhusgdrtghomhdpihgrtghrrdhorhhgpdhsphhrihhngh gvrhdrtghomhdprhhhuhhlrdgrtgdruhhkpdhutghsugdrvgguuhdprggtmhdrohhrghen ucevlhhushhtvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehmtheslh hofigvnhhtrhhophihrdhnvght
X-ME-Proxy: <xmx:tvbzXsbwjjZX387lHUa41-pgtOFwnCGvjXx0QwEkj2ljaOQsySogcw> <xmx:tvbzXn_AFkkj6FMDJaLMkikOb2fvYZ_N4Pxg3622Tdo_8zHsJLlgzA> <xmx:tvbzXjp8mWvM5_bUyuQbfy13g-n9luqHbY9e37IgdFn0Xl8A_Qqf7Q> <xmx:tvbzXp5wb3X8C3DmnCuLFA_wdB7uHD-0mkVRqruo3CwjXo-lFuZldQ>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id A48CBE00A8; Wed, 24 Jun 2020 20:58:30 -0400 (EDT)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.3.0-dev0-543-gda70334-fm-20200618.004-gda703345
Mime-Version: 1.0
Message-Id: <e4cd18e8-0ffb-44c2-928b-d3cbbf50e8ec@www.fastmail.com>
In-Reply-To: <43bb1525-0afa-4c4e-a234-f6ccfacbdd29@www.fastmail.com>
References: <43bb1525-0afa-4c4e-a234-f6ccfacbdd29@www.fastmail.com>
Date: Thu, 25 Jun 2020 10:58:11 +1000
From: "Martin Thomson" <mt@lowentropy.net>
To: quic@ietf.org
Subject: Re: New confidentiality and integrity limits
Content-Type: text/plain;charset=utf-8
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/JYDW5Ey2oLX48Bj911Yh59NjOhk>
X-BeenThere: quic@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Main mailing list of the IETF QUIC working group <quic.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/quic>, <mailto:quic-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/quic/>
List-Post: <mailto:quic@ietf.org>
List-Help: <mailto:quic-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/quic>, <mailto:quic-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 25 Jun 2020 00:58:35 -0000

The concrete change here is twofold:

1. there are new limits (based on the most recent analysis of AES-GCM)

2. counts of (apparent) forgery attempts are not reset on key update

We contemplated doing the second for confidentiality limits as well, but that was unlikely to preserve margins as making a new connection has the same effect.

For me, the upshot was that - at least with current analyses - we don't have quite enough headroom in these ciphers.  We can't use them in all the ways we might want AND keep very conservative safety margins.  The worst-case margins aren't *awful*, but they aren't in the realm of near impossibility that I like.

We use up a lot of headroom in assumptions and approximations.  There are likely gains to be had from refinements to analysis techniques or the threat model.  And, as Chris says, we don't have a thorough analysis of some modes; if that works out the way AES-GCM did, we will be in very good shape.  Or maybe we'll just get a new AEAD with lots more headroom.

I don't expect this to be the final word on the subject, but this represents our current understanding on the subject and what we believe is the best response based on that understanding.

On Thu, Jun 25, 2020, at 09:47, Christopher Wood wrote:
> Hi folks, 
> 
> I'm following up here based on an issue and proposed PR I just filed 
> against against draft-ietf-quic-tls.
> 
>    Issue #3788: New confidentiality and integrity limits 
> [https://github..com/quicwg/base-drafts/issues/3788
>    PR: https://github.com/quicwg/base-drafts/pull/3789
> 
> TL;DR: We propose changing per-key limits to per-connection limits, 
> with different margins. 
> 
> Ongoing analysis efforts with Jean Paul Degabriele, Felix Günther, 
> Kenny Paterson, and Martin Thomson revealed that QUIC should consider 
> changing its confidentiality and integrity limits to account for 
> multi-user security settings. As some background, the existing limits 
> in draft-ietf-quic-tls apply to a single key. They are derived from 
> several existing analyses in the literature, including [1], [2], [3], 
> and [4]. Concretely, they seek to bound an attacker’s advantage in 
> breaking the security guarantees of the AEAD algorithm for a specific 
> key in question. When a Key Update occurs, endpoints receive a new key, 
> which resets the encryption and forgery attempt counters for this new 
> key. 
> 
> This analysis fails to account for settings in which there are 
> multiple, independent users of an AEAD algorithm, each with their own 
> unique key. In these so-called “multi-user” settings, the attacker is 
> allowed to perform some amount of offline work to help accelerate any 
> attack on the AEAD algorithm. However, rather than target a single 
> user’s specific key, they are tasked with distinguishing all traffic 
> (under all keys) from an equal amount of random bits. In the public-key 
> setting, Bellare et al. [5] prove that the success probability in 
> attacking one of the many independent users (or keys) is bounded by the 
> success probability of attacking a single user (or key) multiplied by 
> the number of users present. (This result extends to the symmetric-key 
> setting.)
> 
> Why is this important? Each key used throughout the duration of a 
> single connection is effectively a distinct user. This means that the 
> attacker’s probability of success against any key in a connection must 
> be considered across all keys. Or, more precisely, the integrity limit 
> counters MUST NOT reset across Key Updates. (Confidentiality limits 
> still apply for individual keys, rather than across Key Updates, since 
> there’s no functional difference in the analyses between tearing down a 
> connection and performing an update. The analyses consider encryption 
> as a function of plaintext blocks protected. Thus, users that need to 
> send N blocks of data will send N blocks of data, whether it be in one 
> connection with many keys, or many connections with a single key.)
> 
> Fortunately, this may not be much of a problem in practice. Hoang et 
> al. [6] provide tight multi-user security bounds for AES-GCM with nonce 
> randomization (as is used by TLS 1.3 and QUIC), and those bounds permit 
> a higher amount than previously established for a single key. However, 
> to the best of our knowledge, there are no multi-user security analyses 
> giving tighter bounds than the generic analyses of 
> AEAD_CHACHA20_POLY1305 and AEAD_AES_128_CCM. Thus, for the time being, 
> we are stuck with the single-user integrity limits spread across Key 
> Updates for these AEADs. Recognizing that this is a relatively new area 
> for research, we are aiming to be quite conservative in setting limits, 
> though we do allow an attacker a greater advantage in this multi-user 
> attack than we would for a single connection. We may relax these limits 
> if and when future analyses demonstrate that it’s safe to do so.
> 
> Note that this is not an ideal outcome. A “true” multi-user setting 
> would consider all users, i.e., all keys in all connections used by all 
> QUIC clients and servers, simultaneously. However, endpoints cannot 
> obtain such a global view of the Internet, and thus cannot make 
> realistic parameter choices for bounds based on the number of users. 
> The compromise struck in this PR is to consider a narrow view of 
> multi-user security, i.e., one in which the only “users” in a 
> connection are those introduced by Key Update messages. (This is 
> certainly a gap in the literature worth exploring in the future.) We 
> also recommend setting very strong targets for attacker advantage for a 
> single key, which we estimate will ensure that an attacker still has 
> limited advantage in the multi-user setting.
> 
> Felix, Martin, and I did our best to document the basis for the 
> analysis in this issue (and corresponding PR) in this CFRG I-D:
> 
>    https://github.com/chris-wood/draft-wood-cfrg-aead-limits
> 
> We believe the foundations for this analysis are sound, though we are 
> of course happy to learn if we made arithmetic mistakes. :-)
> 
> Thanks,
> Chris, on behalf of Jean Paul, Felix, Kenny, and Martin
> 
> [1] https://eprint.iacr.org/2012/438.pdf
> [2] https://eprint.iacr.org/2014/613.pdf
> [3] https://link.springer.com/chapter/10.1007/3-540-36492-7_7
> [4] https://www.isg.rhul.ac.uk/~kp/TLS-AEbounds.pdf
> [5] https://cseweb.ucsd.edu/~mihir/papers/musu.pdf
> [6] https://dl.acm.org/doi/10.1145/3243734.3243816
> 
>