Subject: [quicwg/base-drafts] Expand AEAD limits to consider multi-user security. (#3789)

From: Christopher Wood <[email-masked]>
Date: Wed, 24 Jun 2020 16:41:33 -0700

Addresses #3788.

In a typical multi-user setting, the adversary is assumed to perform some
(massive) amount of offline work to break the integrity of a single random
connection. Each user is represented as a unique (key, nonce) pair. In
considering the same threat model, we must treat each key resulting from
a KeyUpdate event as a unique user. As a result, roughly speaking, bounds
implied from the multi-user setting imply (minimally) for the lifetime of
a single connection.

Hoang et al. [1] present tight multi-user security bounds for randomized AES-GCM
(as is used in TLS 1.3 and QUIC), so we can take advantage of those for
per-connection integrity limits. (Confidentiality limits still apply per-key, as
the analysis considers only encrypted blocks, which would not change if an endpoint
updated its key or created a new connection.) In contrast, there are no multi-user
security bounds for AEAD_CHACHA20_POLY1305 or AEAD_AES_128_CCM, so we must use the
single-user bounds in their stead.

[1] https://dl.acm.org/doi/10.1145/3243734.3243816
You can view, comment on, or merge this pull request online at:

  https://github.com/quicwg/base-drafts/pull/3789

-- Commit Summary --

  * Expand AEAD limits to consider multi-user security.

-- File Changes --

    M draft-ietf-quic-tls.md (176)

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/3789.patch
https://github.com/quicwg/base-drafts/pull/3789.diff

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789

---

From: Christopher Wood <[email-masked]>
Date: Wed, 24 Jun 2020 16:45:49 -0700

@chris-wood pushed 1 commit.

89bbe1515f04766c0fa48dfd1b0fd4126fc3ecae  Fix linter issues.

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789/files/71684bc7e71580cffa434ca1c3255a6c980f3671..89bbe1515f04766c0fa48dfd1b0fd4126fc3ecae

---

From: Jana Iyengar <[email-masked]>
Date: Thu, 25 Jun 2020 17:59:52 -0700

@janaiyengar commented on this pull request.

Thank you for the PR, @chris-wood ! A few comments.

> @@ -2207,10 +2206,14 @@ v:
   bound on the number of forged packets that an endpoint can reject before
   updating keys.
 
-The analysis of AEAD_AES_128_CCM relies on a count of the number of block
-operations involved in producing each message. For simplicity, and to match the
-analysis of other AEAD functions in {{AEBounds}}, this analysis assumes a
-packet length of 2^10 blocks and a packet size limit of 2^14.
+o:
+
+: The amount of offline ideal cipher queries made by an adversary.
+
+The analyses that follow rely on a count of the number of block operations
+involved in producing each message. For simplicity, and to match the analysis of
+other AEAD functions in {{AEBounds}}, this analysis assumes a packet length of
+2^10 blocks; that is, a packet size limit of 2^14 bytes.

I don't understand how this impacts the analysis, but why is packet size 2^14 bytes? For QUIC, I would suggest that 2^11 ought to be adequate (if a larger packet size is more conservative).

> +
+~~~
+(q + v) <= 2^28
+~~~
+
+Assuming `v = q`, endpoints cannot protect more than 2^27 packets in a single
+connection without causing an attacker to gain an larger advantage than the
+target of 2^-60.
+
+### Integrity Limit
+
+For integrity, Theorem (4.3) in {{?GCM-MU}} establishes that an attacker gains
+an advantage in successfully forging a packet of no more than:
+
+~~~
+(1 / 2^(8 * n)) + ((2 * v) / 2^2*n) + ((2 * o * v) / 2^(k + n))

```suggestion
(1 / 2^(8 * n)) + ((2 * v) / 2^(2 * n)) + ((2 * o * v) / 2^(k + n))
```
?

-Key updates MUST be initiated before usage limits on packet protection keys are
-exceeded. For the cipher suites mentioned in this document, the limits in
-Section 5.5 of {{!TLS13}} apply. {{!TLS13}} does not specify a limit for
-AEAD_AES_128_CCM, but the analysis in {{ccm-bounds}} shows that a limit of 2^23
-packets can be used to obtain the same confidentiality protection as the limits
-specified in TLS.
+This document sets usage limits for AEAD algorithms to ensure that overuse does
+not give an adversary a disproportionate advantage in attacking the
+confidentiality and integrity of communications.

```suggestion
confidentiality and integrity of communications when using QUIC.
```

> +If the number of packets sent or fail authentication within the connection
+(across all keys) exceeds a limit that is specific to the AEAD in use, the
+endpoint MUST immediately close the connection and not attempt to process any
+further packets.  Applying a limit reduces the probability that an attacker can
+successfully forge a packet; see {{AEBounds}}, {{ROBUST}}, and {{?GCM-MU}}.
+
+A connection MUST be closed if the number of packets that fail authentication
+exceed the integrity limit for the selected AEAD. For AEAD_AES_128_GCM, and the
+integrity limit is 2^54 encrypted or forged packets; see {{gcm-bounds}}.  For
+AEAD_CHACHA20_POLY1305, the limit on number of packets that fail authentication
+is 2^36; see {{AEBounds}}.  For AEAD_AES_128_CCM, the integrity limit is 2^23.5
+forged packets; see {{ccm-bounds}}.

There seems to be some redundancy and some inconsistencies in the text heree, I've tried to clean it up a bit. See if the following is accurate.
```suggestion
If the total number of received packets that fail authentication within the
connection, across all keys, exceeds the integrity limit for the selected AEAD,
the endpoint MUST immediately close the connection and not process any more
packets. For AEAD_AES_128_GCM, the integrity limit is 2^54 forged packets; see
{{gcm-bounds}}. For AEAD_CHACHA20_POLY1305, the integrity limit is 2^36
forged packets; see {{AEBounds}}. For AEAD_AES_128_CCM, the integrity limit
is 2^23.5 forged packets; see {{ccm-bounds}}. Applying this limit reduces the
probability that an attacker can successfully forge a packet; see {{AEBounds}},
{{ROBUST}}, and {{?GCM-MU}}.
```

> -  This means that packets that fail authentication will often use the packet
-  protection keys from the next key phase.  It is therefore necessary to also
-  track the number of packets that fail authentication with the next set of
-  packet protection keys.  To avoid exhaustion of both sets of keys, it might be
-  necessary to initiate two key updates in succession.
-
-For AEAD_AES_128_GCM, AEAD_AES_256_GCM, and AEAD_CHACHA20_POLY1305, the limit on
-the number of packets that fail authentication is 2^36.  Note that the analysis
-in {{AEBounds}} supports a higher limit for the AEAD_AES_128_GCM and
-AEAD_AES_256_GCM, but this specification recommends a lower limit.  For
-AEAD_AES_128_CCM, the limit on the number of packets that fail authentication
-is 2^23.5; see {{ccm-bounds}}.
+Endpoints MUST count the number of encrypted packets for each set of keys. If
+the number of encrypted packets with the same key exceeds a limit that is
+specific to the AEAD in use, the endpoint MUST stop using those keys. If a key
+update is not possible, the endpoint MUST immediately close the connection.

Should an error code specified here? How is the endpoint closing the connection?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789#pullrequestreview-437946485

---

From: Martin Thomson <[email-masked]>
Date: Thu, 25 Jun 2020 18:52:50 -0700

@martinthomson commented on this pull request.

I think that we need to just stop using the connection and send no more packets.  We probably need to be explicit about that and mention that a stateless reset is the only thing that can be sent thereafter.

An immediate close before reaching the limit might be recommended to avoid the sudden nature of that sort of close.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789#discussion_r445927529

---

From: Martin Thomson <[email-masked]>
Date: Thu, 25 Jun 2020 18:53:20 -0700

+~~~
+(q + v) <= 2^28
+~~~
+

The only potential problem here is with line length, but this seems better.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789#discussion_r445927672

---

From: Martin Thomson <[email-masked]>
Date: Thu, 25 Jun 2020 18:55:06 -0700

We decided that matching the TLS analysis in this regard is best.  Using the larger number is more conservative, so the margins in practice will be better than what we have calculated here.

There is of course the theoretical limit on QUIC packets, which is 2^16 bytes or 2^12 blocks, but as you say, they are mostly much smaller.  There is an existing note about this discrepancy for those running a massive MTU.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789#discussion_r445928115

---

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

+~~~
+(q + v) <= 2^28
+~~~
+

```
this:~ jiyengar$ echo "(1 / 2^(8 * n)) + ((2 * v) / 2^(2 * n)) + ((2 * o * v) / 2^(k + n))" | wc -c
      68
```

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789#discussion_r445928244

---

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

Where's the note? Perhaps a pointer to that here would be helpful. Should the integrity/confidentiality limits be made explicit for 2^16-byte packets?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789#discussion_r445929154

---

From: Martin Thomson <[email-masked]>
Date: Thu, 25 Jun 2020 19:17:18 -0700

Line 1588 (on the new side).  David raised an issue requesting that we provide limits based on an assumption of 2^16 byte packets.  If we do that, we might want to do a split between 2^11 and 2^16 rather than having 2^14.  We should track that on that issue though.

+~~~
+(q + v) <= 2^28
+~~~
+

OK, that's safe (just).

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789#discussion_r445933209

---

From: Christopher Wood <[email-masked]>
Date: Mon, 29 Jun 2020 08:30:53 -0700

@chris-wood commented on this pull request.

Agreed. I'd prefer if we left the 2^16 limits to a separate issue.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789#discussion_r447060021

---

From: Christopher Wood <[email-masked]>
Date: Mon, 29 Jun 2020 08:31:00 -0700

7d763fd6e71e4e1c38add4d78dbf3f7c28645f07  Update draft-ietf-quic-tls.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789/files/89bbe1515f04766c0fa48dfd1b0fd4126fc3ecae..7d763fd6e71e4e1c38add4d78dbf3f7c28645f07

---

From: Christopher Wood <[email-masked]>
Date: Mon, 29 Jun 2020 08:31:07 -0700

847f3c1666ca1ec23c92c72a9be998e74fb1ce68  Update draft-ietf-quic-tls.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789/files/7d763fd6e71e4e1c38add4d78dbf3f7c28645f07..847f3c1666ca1ec23c92c72a9be998e74fb1ce68

---

From: Christopher Wood <[email-masked]>
Date: Mon, 29 Jun 2020 08:32:58 -0700

e50a65d844bf4c09891bf873d64c9211b28f43f5  Update draft-ietf-quic-tls.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789/files/847f3c1666ca1ec23c92c72a9be998e74fb1ce68..e50a65d844bf4c09891bf873d64c9211b28f43f5

---

From: Christopher Wood <[email-masked]>
Date: Mon, 29 Jun 2020 08:51:40 -0700

69be76608b8f7a81d2e64e210121ddbbe1788c78  Clarify connection close cases for the confidentiality limit.

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789/files/e50a65d844bf4c09891bf873d64c9211b28f43f5..69be76608b8f7a81d2e64e210121ddbbe1788c78

---

From: Christopher Wood <[email-masked]>
Date: Mon, 29 Jun 2020 08:52:03 -0700

I took a crack at this, though I don't love the language. Clarifying suggestions would be most welcome!

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789#discussion_r447075004

---

From: martinduke <[email-masked]>
Date: Tue, 30 Jun 2020 11:52:54 -0700

@martinduke commented on this pull request.

-Note:
+For AEAD_AES_128_GCM, the integrity limit is 2^54 forged packets; see

And _256_GCM? I have no idea if it's the same but we should include it one way or another.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789#pullrequestreview-440297247

---

From: martinduke <[email-masked]>
Date: Tue, 30 Jun 2020 11:56:55 -0700

@martinduke requested changes on this pull request.

> @@ -1552,30 +1549,40 @@ number of attempts to forge packets. TLS achieves this by closing connections
 after any record fails an authentication check. In comparison, QUIC ignores any
 packet that cannot be authenticated, allowing multiple forgery attempts.
 
-Endpoints MUST count the number of received packets that fail authentication for
-each set of keys.  If the number of packets that fail authentication with the
-same key exceeds a limit that is specific to the AEAD in use, the endpoint MUST
-stop using those keys.  Endpoints MUST initiate a key update before reaching
-this limit.  If a key update is not possible, the endpoint MUST immediately
-close the connection.  Applying a limit reduces the probability that an attacker
-is able to successfully forge a packet; see {{AEBounds}} and {{ROBUST}}.
+Endpoints MUST count the number of encrypted packets for each set of keys. If

Can this clarify who is doing the updating? If I've sent 2^27 or received 2^27 do I initiate?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789#pullrequestreview-440299792

---

From: Martin Thomson <[email-masked]>
Date: Tue, 30 Jun 2020 18:37:44 -0700

This is an existing ambiguity.  And the answer is that either endpoint can do the update.  As updates are symmetric, this isn't a big deal, but you can stumble over each other if you do it poorly.

I haven't implemented this bit yet, but when I did it for TLS, the sender updates at limit-N and the receiver requests an update at limit-M where M < N.  This is because the primary responsibility for the update lies with the sender.  This stops endpoints using the same implementation from doing near-simultaneous updates, which is a little wasteful.  If M for one implementation matches N for another, then you can still get a race.  Of course, QUIC handles simultaneous updates well, so maybe you don't care for that level of sophistication.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789#discussion_r448068353

---

From: Martin Thomson <[email-masked]>
Date: Tue, 30 Jun 2020 18:38:32 -0700

-Note:

The limit is much, much higher, for 256-bit keys.  But the analysis below recommends that the same limit apply.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/3789#discussion_r448068535