Subject: [quicwg/base-drafts] Update AEAD limits for larger packets (#4175)

From: Martin Thomson <[email-masked]>
Date: Thu, 01 Oct 2020 22:47:12 -0700

The analysis describes conditions where higher limits might be allowed, and provides a formula in each case that can be used to determine other limits more readily.

The number of changes I&#39;ve made here are somewhat frightening.  This is why I resisted doing this.  This will need careful double-checking.  I think that this is better, but I&#39;m not sure that I feel happy about having spent the time.

The actual numbers don&#39;t concern me much, anyone can subtract 2, but the changes to the structure really need to be looked at.  Some of the changes are editorial, but they still need extra eyes.

Closes #3701.
You can view, comment on, or merge this pull request online at:

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

-- Commit Summary --

  * Update AEAD limits for larger packets

-- File Changes --

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

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/4175.patch
https://github.com/quicwg/base-drafts/pull/4175.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/4175

---

From: Christopher Wood <[email-masked]>
Date: Fri, 02 Oct 2020 05:57:48 -0700

cc @fxguenther 

-- 
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/4175#issuecomment-702718814

---

From: David Schinazi <[email-masked]>
Date: Fri, 02 Oct 2020 08:52:27 -0700

@DavidSchinazi approved this pull request.

This PR is exactly what I was hoping for, thanks for writing it. As far as I can tell, it's correct. It also fully addresses my concerns from #3701.

-- 
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/4175#pullrequestreview-501253402

---

From: Christopher Wood <[email-masked]>
Date: Tue, 06 Oct 2020 06:19:42 -0700

@chris-wood approved this pull request.

Thanks, @martinthomson! I checked the derivations and produced the same results. 

-- 
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/4175#pullrequestreview-502941500

---

From: Mike Bishop <[email-masked]>
Date: Tue, 06 Oct 2020 11:12:39 -0700

@MikeBishop commented on this pull request.

The actual analysis is beyond my scope, but the text looks good.

> @@ -2404,37 +2421,33 @@ no more than:
 (2l * q)^2 / 2^n
 ~~~
 
-For a target advantage of 2^-57, this results in the relation:
-
-~~~
-q <= 2^24.5
-~~~
-
-That is, endpoints cannot protect more than 2^23 packets with the same set of
-keys without causing an attacker to gain a larger advantage than the target of
-2^-57.  Note however that the integrity limits further constrain this value.
+The integrity limit in Theorem 1 in {{?CCM-ANALYSIS}} provides an attacker a
+strictly higher advantage for the same number of messages. As the targets

```suggestion
strictly higher advantage for the same number of messages. As the target
```
Or "targeted"?

-- 
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/4175#pullrequestreview-503218954

---

From: Martin Thomson <[email-masked]>
Date: Tue, 06 Oct 2020 17:29:28 -0700

@martinthomson commented on this pull request.

 (2l * q)^2 / 2^n
 ~~~

I'm trying to say that the "value of the goal" is the same.  I think that this is correct.

I think that you might say "target advantages for A and B", but I think that "advantages" means something else and so I avoided the plural.

Maybe instead "As the target for both the confidentiality advantage and integrity advantage is the same, ..." ?

My grammar skillz aren't up to this, clearly.

-- 
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/4175#discussion_r500669756

---

From: Mike Bishop <[email-masked]>
Date: Thu, 08 Oct 2020 07:16:08 -0700

(2l * q)^2 / 2^n
 ~~~

Or plural works in that last arrangement, so "As the targets for the confidentiality advantage and the integrity advantage are the same...."  I think any of them are fine, so long as they agree in number.  What stuck out to me was "targets advantage" more than anything else.

-- 
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/4175#discussion_r501756204

---

From: Martin Thomson <[email-masked]>
Date: Thu, 08 Oct 2020 16:13:23 -0700

@martinthomson pushed 1 commit.

551184a2b3b9cd9069092eeadb8a7c4489a7bb4e  Grammaaaaaa!

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/4175/files/ef94ae1459b3369fb234d36c9cad9c85ec04ee06..551184a2b3b9cd9069092eeadb8a7c4489a7bb4e

---

From: Martin Thomson <[email-masked]>
Date: Thu, 08 Oct 2020 16:39:31 -0700

> @@ -2337,18 +2352,19 @@ distinguishing advantage between a real and random AEAD algorithm gained by an
 attacker is:
 
 ~~~
-2 * (q * l)^2 / 2^128
+2 * (q * l)^2 / 2^n

I forgot to call this out.  @chris-wood, can you check that this is right here?  I think that this comes from the `\sigma*B/2^n` term in Bad3 in [the paper](https://eprint.iacr.org/2018/993.pdf), but I want to make sure that my understanding is correct in that we are treating `\sigma*B` as `\sigma^2` in the single-user case.

-- 
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/4175#pullrequestreview-505247543

---

From: Jana Iyengar <[email-masked]>
Date: Thu, 15 Oct 2020 14:27:57 -0700

@janaiyengar approved this pull request.

A few minor points.

> @@ -2299,17 +2307,23 @@ 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.
+involved in producing each message. This analysis is performed for packets of
+up to 2^11 (l = 2^7) and 2^16 (l = 2^12). A size of 2^11 is expected to be a

```suggestion
size up to 2^11 (l = 2^7) and 2^16 (l = 2^12). A size of 2^11 is expected to be a
```

> @@ -2299,17 +2307,23 @@ 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.
+involved in producing each message. This analysis is performed for packets of
+up to 2^11 (l = 2^7) and 2^16 (l = 2^12). A size of 2^11 is expected to be a
+limit that matches common deployment patterns, whereas the 2^16 is the maximum
+possible size of a QUIC packet. Only endpoints that strictly limit packet size
+can use the larger limits that are derived using the smaller packet size.

limit is being used for multiple things here -- these limits and also packet size limit. 
```suggestion
can use the larger confidentiality and integrity limits that are derived using the smaller packet size.
```

-Thus, endpoints cannot protect more than 2^25 packets in a single connection
-without causing an attacker to gain an larger advantage than the target of
-2^-57.
+Thus, endpoints that do not send packets larger than 2^11 bytes cannot protect
+more than 2^28 packets in a single connection without causing an attacker to
+gain an larger advantage than the target of 2^-57. The limit for endpoints that
+do not limit packet size is instead 2^23.

```suggestion
allow for the packet size to be as large as 2^16 is instead 2^23.
```

-For AEAD_AES_256_GCM, the second and fourth terms dominate the rest, so the
-others can be removed without affecting the result. This produces the following
-approximation:
+Endpoints that do not attempt to remove protection from packets larger than
+2^11 bytes can attempt to remove protection from at most 2^57 packets. Packets

```suggestion
2^11 bytes can attempt to remove protection from at most 2^57 packets. Endpoints
```

> +attempt to remove protection from any packet can attempt to remove protection
+from at most 2^52 packets.

```suggestion
that do not restrict the size of processed packets can attempt to remove protection
from at most 2^52 packets.
```

-Assuming `q = v`, endpoints cannot attempt to protect or authenticate more than
-2^23.5 packets with the same set of keys without causing an attacker to gain a
-larger advantage in forging packets than the target of 2^-57.
+By setting `q = v`, values for both confidentiality and integrity limits can be
+produced. Endpoints that limit packets to 2^11 bytes therefore have both
+confidentiality and integrity limits of 2^26.5 packets. Endpoints that do not
+limit packet size have a limit of 2^21.5.

```suggestion
restrict packet size have a limit of 2^21.5.
```

-- 
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/4175#pullrequestreview-509812569

---

From: Martin Thomson <[email-masked]>
Date: Thu, 15 Oct 2020 16:20:44 -0700

5280b951376d486bc41a322e5f9ef25391542c5b  Code review tweaks

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/4175/files/551184a2b3b9cd9069092eeadb8a7c4489a7bb4e..5280b951376d486bc41a322e5f9ef25391542c5b

---

From: Martin Thomson <[email-masked]>
Date: Thu, 15 Oct 2020 16:21:45 -0700

feff7323e85389f3d25776b59617f0a8ef31e4cf  Wrap

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/4175/files/5280b951376d486bc41a322e5f9ef25391542c5b..feff7323e85389f3d25776b59617f0a8ef31e4cf

---

From: Martin Thomson <[email-masked]>
Date: Thu, 15 Oct 2020 16:23:33 -0700

Merged #4175 into master.

-- 
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/4175#event-3883944311