Subject: New confidentiality and integrity limits

From: "Christopher Wood" <[email-masked]>
Date: Wed, 24 Jun 2020 16:47:40 -0700

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

---

From: "Martin Thomson" <[email-masked]>
Date: Thu, 25 Jun 2020 10:58:11 +1000

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:
>    Issue #3788: New confidentiality and integrity limits 
> [https://github..com/quicwg/base-drafts/issues/3788
> 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:
> 
> We believe the foundations for this analysis are sound, though we are 
> of course happy to learn if we made arithmetic mistakes. :-)
> 
> Thanks,

---

From: Christian Huitema <[email-masked]>
Date: Wed, 24 Jun 2020 18:10:01 -0700

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:
>    Issue #3788: New confidentiality and integrity limits [https://github..com/quicwg/base-drafts/issues/3788

---

From: "Christopher Wood" <[email-masked]>
Date: Thu, 25 Jun 2020 11:29:13 -0700

Hi Christian,

> derived from the same master secret?

In the multi-user setting, a user is effectively a distinct key. Thus, the set of users is all keys used across all connections. (Key updates give what is effectively a new independent key, so they introduce new "users" into the system.)

> QUIC connection, each with its own master secret?

For confidentiality, the important bit is to keep the amount of data encrypted per key "reasonably low." Running a key update before the limits are reached helps drive down the adversary's advantage. So, it's fine to maintain a long-lived connection provided the confidentiality limits are not violated and endpoints update frequently. 

As Martin noted, for the integrity limit, the story is slightly different. Key updates do not help there.

Best,
Chris

---

From: "Martin Thomson" <[email-masked]>
Date: Fri, 26 Jun 2020 09:44:55 +1000

On Fri, Jun 26, 2020, at 04:29, Christopher Wood wrote:
> As Martin noted, for the integrity limit, the story is slightly 
> different. Key updates do not help there.

Or we don't know that they do...  There are still a lot of unanswered questions.  We do know that a forgery attempt against one key is likely still good for a different key on the same connection.  It might not be good for another connection (the inclusion of connection IDs might help us here, but that's another unknown - and unreliable - factor) but we can't really control for that.  So we chose something we believe to be both conservative and practical.

The forgery limits are still quite generous: if you have to drop a connection due to that many forgeries, then I'd suggest that something is seriously wrong.

---

From: Jana Iyengar <[email-masked]>
Date: Thu, 25 Jun 2020 18:01:04 -0700

Chris, (and all others involved),

Thank you for all the analysis and for distilling it into the
recommendations above -- the more precise bounds are super helpful!
It seems to me that the other limits are not practical limits for the most
part. Am I correct in understanding that the practical impact of this boils
down to "We might need to do key updates more frequently than we had hoped"
since the integrity limits are a bit more modest?

I've left some comments on the PR.

Thanks again,
- jana

On Thu, Jun 25, 2020 at 4:45 PM Martin Thomson <[email-masked]> wrote:

> Or we don't know that they do...  There are still a lot of unanswered
> questions.  We do know that a forgery attempt against one key is likely
> still good for a different key on the same connection.  It might not be
> good for another connection (the inclusion of connection IDs might help us
> here, but that's another unknown - and unreliable - factor) but we can't
> really control for that.  So we chose something we believe to be both
> conservative and practical.
>
> The forgery limits are still quite generous: if you have to drop a
> connection due to that many forgeries, then I'd suggest that something is
> seriously wrong.
>
>

---

From: "Martin Thomson" <[email-masked]>
Date: Fri, 26 Jun 2020 14:31:03 +1000

On Fri, Jun 26, 2020, at 11:01, Jana Iyengar wrote:
> It seems to me that the other limits are not practical limits for the 
> most part. 

Assuming that you mean "the limits are unlikely to be a problem in practice"?  I think that is right.

The numbers that change here are forgery limits, and we expect that a real connection will have very few apparent forgeries.  In testing, I see a handful during the handshake (with my RTT, I often get Initial retransmissions that arrive after the keys have been dropped), but that's only ever about 2 packets from what I've seen.  Similarly, an implementation that drops keys aggressively around a key update might see a few near each update.  

Overall, we're talking about seeing a handful of apparent forgeries in normal use, not millions (which is the lowest limit we have).  This could mean that someone using AES-CCM will run into this limit before they hit the 2^62 packet limit, but that is unlikely to be problem for the other ciphers as their limits are higher.

This is mostly a problem for people who might be subject to sustained forgery attacks, but an attacker that sends ~8 million bad packets to close a connection has earned their ability to kill that connection.  It's not exactly an economical attack.  (For contrast, the AES-128-GCM number is ~16 quadrillion.)

> Am I correct in understanding that the practical impact of 
> this boils down to "We might need to do key updates more frequently 
> than we had hoped" since the integrity limits are a bit more modest?

Unfortunately, integrity limits are not reset by a key update, so the net effect is that you have to make a new connection.  But see above.

The confidentiality limits are marginally higher as a result of the new analysis, so you end up having to update a tiny bit less.