Re: New confidentiality and integrity limits

Christian Huitema <huitema@huitema.net> Thu, 25 June 2020 01:11 UTC

Return-Path: <huitema@huitema.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 131BB3A1211 for <quic@ietfa.amsl.com>; Wed, 24 Jun 2020 18:11:57 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
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 tRsEsbwjKGL7 for <quic@ietfa.amsl.com>; Wed, 24 Jun 2020 18:11:55 -0700 (PDT)
Received: from mx36-out10.antispamcloud.com (mx36-out10.antispamcloud.com [209.126.121.30]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 2F30A3A120E for <quic@ietf.org>; Wed, 24 Jun 2020 18:11:54 -0700 (PDT)
Received: from xse333.mail2web.com ([66.113.197.79] helo=xse.mail2web.com) by mx169.antispamcloud.com with esmtp (Exim 4.92) (envelope-from <huitema@huitema.net>) id 1joGQa-000sl7-G0 for quic@ietf.org; Thu, 25 Jun 2020 03:11:54 +0200
Received: from xsmtp21.mail2web.com (unknown [10.100.68.60]) by xse.mail2web.com (Postfix) with ESMTPS id 49shkx6KCTz2M46 for <quic@ietf.org>; Wed, 24 Jun 2020 18:10:01 -0700 (PDT)
Received: from [10.5.2.14] (helo=xmail04.myhosting.com) by xsmtp21.mail2web.com with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.92) (envelope-from <huitema@huitema.net>) id 1joGOv-0003i7-Ok for quic@ietf.org; Wed, 24 Jun 2020 18:10:01 -0700
Received: (qmail 12876 invoked from network); 25 Jun 2020 01:10:01 -0000
Received: from unknown (HELO [192.168.1.107]) (Authenticated-user:_huitema@huitema.net@[172.58.46.130]) (envelope-sender <huitema@huitema.net>) by xmail04.myhosting.com (qmail-ldap-1.03) with ESMTPA for <quic@ietf.org>; 25 Jun 2020 01:10:01 -0000
To: Christopher Wood <caw@heapingbits.net>, quic@ietf.org
References: <43bb1525-0afa-4c4e-a234-f6ccfacbdd29@www.fastmail.com>
From: Christian Huitema <huitema@huitema.net>
Autocrypt: addr=huitema@huitema.net; prefer-encrypt=mutual; keydata= mDMEXtavGxYJKwYBBAHaRw8BAQdA1ou9A5MHTP9N3jfsWzlDZ+jPnQkusmc7sfLmWVz1Rmu0 J0NocmlzdGlhbiBIdWl0ZW1hIDxodWl0ZW1hQGh1aXRlbWEubmV0PoiWBBMWCAA+FiEEw3G4 Nwi4QEpAAXUUELAmqKBYtJQFAl7WrxsCGwMFCQlmAYAFCwkIBwIGFQoJCAsCBBYCAwECHgEC F4AACgkQELAmqKBYtJQbMwD/ebj/qnSbthC/5kD5DxZ/Ip0CGJw5QBz/+fJp3R8iAlsBAMjK r2tmyWyJz0CUkVG24WaR5EAJDvgwDv8h22U6QVkAuDgEXtavGxIKKwYBBAGXVQEFAQEHQJoM 6MUAIqpoqdCIiACiEynZf7nlJg2Eu0pXIhbUGONdAwEIB4h+BBgWCAAmFiEEw3G4Nwi4QEpA AXUUELAmqKBYtJQFAl7WrxsCGwwFCQlmAYAACgkQELAmqKBYtJRm2wD7BzeK5gEXSmBcBf0j BYdSaJcXNzx4yPLbP4GnUMAyl2cBAJzcsR4RkwO4dCRqM9CHpVJCwHtbUDJaa55//E0kp+gH
Subject: Re: New confidentiality and integrity limits
Message-ID: <a4d7e8cf-5879-6941-e059-5d2f3e67ae86@huitema.net>
Date: Wed, 24 Jun 2020 18:10:01 -0700
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.9.0
MIME-Version: 1.0
In-Reply-To: <43bb1525-0afa-4c4e-a234-f6ccfacbdd29@www.fastmail.com>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Content-Language: en-US
X-Originating-IP: 66.113.197.79
X-Spampanel-Domain: xsmtpout.mail2web.com
X-Spampanel-Username: 66.113.197.0/24
Authentication-Results: antispamcloud.com; auth=pass smtp.auth=66.113.197.0/24@xsmtpout.mail2web.com
X-Spampanel-Outgoing-Class: unsure
X-Spampanel-Outgoing-Evidence: Combined (0.15)
X-Recommended-Action: accept
X-Filter-ID: Mvzo4OR0dZXEDF/gcnlw0f6LF1GdvkEexklpcFpSF5apSDasLI4SayDByyq9LIhVUZbR67CQ7/vm /hHDJU4RXkTNWdUk1Ol2OGx3IfrIJKywOmJyM1qr8uRnWBrbSAGDcnqpk5VeF3xR4kF6iVwRtbgN zB/4Jkrw1eDLcif59ftqd9MAh6+PE/scPcm/ACndU7Tmz6iKnkQL9gqsxD347235Nhqq+/HvroPq 8GSPg+60/QPNqXybIny9WGhadIo/1Ofn8DBBgDynfYj8uZOR2ryme9ldZJ7uNXfg/GfS8fUvP/L5 rCqHDsKZM+xa1iwJX+gRCHfMVnsAk591zk0uilUI+ZL4xWiN8NS6C+dmX6OEdA4u1aThyWrQ/ou2 +v/lmX4Em37yFgrCB6NHRn1g+f3uncIqYSL3lhh5c81YyJqFoLZMmkWsaurVZfvqROaDnDtHb8z5 dpPkEuJ8Snwqla7jUnW3hy14Yji8fo+4xCnSRo4Rcu5Z37rMuDjCny5fE9ykbJ7I9co1MAEE3ruN Xsm8UJsAPvDcVSKtDCYkioPY5Qx4fJOk03R5fJtf/Dv/dkIzS7m4GUpXCY1Y3j3ilQ8EW2aDkYIa 2M5pALviQra5n1qAU0VTFRks+evUvJt4mhP0mU7v5izoFH0HNZLbcgwWr7Zk/vFgNdJniksrUhAx iMxSpkvqIEtRL3s4ePxvne6Agjui5gKB/Byw/yqfyPKY2AXNZGS5G93aGyH8MqMlOQRMVMd0HCeT skOZ5TL8PQsBQED/m9MQs2avfela3TXg724gFzhHYUe+7aKm0vWOXKxN13EcU2ca0tDxf/UiTi+J 2sBvM/O0p+zizleC4lU8fDj1CnRx+r4b/1Q/PZ86zB2Vu6+TJiLath6PGP2/vOnCUbNPgcPcQwzM gKHyQxUo+ql2ySTkvEFH/23XMww2BnTTFGX5/yI4Ky+1ZJcbGqc5H4PEZHeoI/d6LWFf332z7LMw LGdoi9FMQ5j9dQUvMi1YKAun15JQSJLyCT5k+MTObVKxHy/dols381l9r9ft9daDonlwd6LnuX+J u10=
X-Report-Abuse-To: spam@quarantine11.antispamcloud.com
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/uxIaaNM2GJKdsMJWNaimwOYBMS4>
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 01:11:57 -0000

Chris,

I would like to understand how exactly we should quantify the
multi-users set. You write that "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." OK, but what about keys used in
different connections, such as multiple clients connecting to the same
server, or for that matter multiple clients connecting to different
servers? Is this because all the keys used in the same connection are
derived from the same master secret?

If derivation from the same master secret is the issue, that means that
the protection offered by the key update function is seriously limited.
Otherwise, the keys used at different epochs would effectively be
independent. Obviously, we cannot design a new update function that
would somehow incorporate more entropy, at least not for QUIC V1. Does
that mean that the update mechanism is not very useful? Is it insecure
for applications to maintain long connections and rely on key update?
Should application rely instead on splitting the workload onto several
QUIC connection, each with its own master secret?

-- Christian huitema

On 6/24/2020 4:47 PM, 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
>