Subject: Re: [quicwg/base-drafts] Forgery limits on packet protection (#3619)

From: Nick Banks <[email-masked]>
Date: Fri, 01 May 2020 08:19:19 -0700

Another (simplier?) option could be to just update keys **much** more often. I've done performance tests with msquic on the effect of updating the key ~once per round trip. There was no noticeable effect on performance. In fact, more often than not, the key update perf tests happen to perform slightly better (within noise tolerance) than without key update.

I'm not suggesting we advocate once a round trip or anything near that; more like every 2^20 packets (or 2^30 bytes?) sent or received (including failed decryptions). As I understand it, this is an ultra conservative number as far as protecting from any kind of attacks, and should be _free_ as far as any performance impact on the connection. This also has the added benefit of exercising the key update scenario more often, which should hopefully improve interoperability of the feature.

-- 
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/issues/3619#issuecomment-622430128

---

From: martinduke <[email-masked]>
Date: Fri, 01 May 2020 11:59:17 -0700

I support a change like this, but I am not qualified to say what the thresholds should be. There certainly isn't a reason to push it to very high limits. This change would not break interoperability, so it's a good one.

Banning CCM might break interoperability for someone, but I'm not too concerned, particularly if we can update all the browsers to not offer it.

A somewhat bigger concern is the lack of key update support in a lot of implementations: I read 9 of 15 servers as supporting it.

-- 
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/issues/3619#issuecomment-622517738

---

From: Martin Thomson <[email-masked]>
Date: Fri, 01 May 2020 14:58:01 -0700

(Tentative) good news on CCM: Kenny identified a security analysis paper and it seems relatively simple to go from that to numbers.

I am not personally concerned about support for key update. 9/15 isn't 15, but that doesn't bother me. It turns out to be a little fiddly to implement, so if people decide to drop connections that hit these limits instead, the effect isn't that bad. Of course, if you want to follow Nick's suggestion, that works too (I remember Dan Bernstein seriously suggesting a cipher that updated every record, back when I first proposed this scheme for TLS).

-- 
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/issues/3619#issuecomment-622584353

---

From: Anthony Rossi <[email-masked]>
Date: Fri, 01 May 2020 15:55:18 -0700

If we're looking for a new bound to initiate a key update, there's precedent in the SSH RFC to rekey after every 1 GB of data transferred. See [here](https://tools.ietf.org/html/rfc4253#section-9)

-- 
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/issues/3619#issuecomment-622601163

---

From: martinduke <[email-masked]>
Date: Fri, 01 May 2020 18:17:26 -0700

I should point out that my "9 of 15" figure is based on the interop matrix, where the client initiates an early update and the server responds. That is a different thing than a server initiating an update when required by the spec, which fewer than 9 servers might do.

-- 
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/issues/3619#issuecomment-622647876

---

From: Martin Thomson <[email-masked]>
Date: Sun, 03 May 2020 18:49:34 -0700

Based on [this paper analysing CCM](https://link.springer.com/content/pdf/10.1007%2F3-540-36492-7_7.pdf) by Jonsson, I have calculated the bounds on the number of forgeries and encryptions for CCM.  The numbers aren't great, but that probably doesn't matter much for the purposes to which CCM is generally put.

(I'm using the notation from the [AEBounds paper](https://www.isg.rhul.ac.uk/~kp/TLS-AEbounds.pdf) here because that is easier to type than some of what is being used in other papers.  For reference, q is the number of genuine encryptions, l is the length of each in 16 byte blocks, v is the number of forgeries, n is the key length in bits, t is the tag length in bits.)

## Confidentiality

Jonsson puts the advantage an attacker has over a generic PRF at `(ql)^2/2^(n+1)`.

If we assume the same numbers in the AEBounds paper for record/packet size, `l=2^10` (this is for consistency, most QUIC packets will be much smaller, in the order of 2^7, but we might also go as high as 2^12; this being dictated by the MTU).  For AES, `n=2^128`.

To keep the advantage an attacker has to 2^-60 (to match the analysis in TLS), we therefore need to keep q to below 2^24.5.  Somewhat unsurprisingly, that matches the numbers we have for AES-GCM.

## Integrity

Jonsson puts the advantage for an attacker over a generic PRF at `v/2^t + (2^l*(v + q))^2/2^(n+1)`.  As the first term is negligible even for large v (up to 2^64), we consider the second term alone and aim for a bound on the advantage of 2^-57 to match the analysis for other ciphers.

That leaves us with `v+q <= 2^26`.  As q is already established to be 2^24.5, we can say that v should be limited to 2^25 (or `log2(2^26 - 2^24.5)` if you want to be precise).

(As a side note, for t=64, as in AEAD_AES_128_CCM_8, the first term becomes relevant and our security bound limits the number of forgeries to 2^7, which is probably a bit limiting in practice.  That's good justification for not enabling AEAD_AES_128_CCM_8 by default; though different applications might use a different target bound than 2^-57.)

## Caveat

I'm an not a cryptographer.  These papers all read like chicken-chicken-chicken.  My calculation

-- 
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/issues/3619#issuecomment-623224483

---

From: Antoine Delignat-Lavaud <[email-masked]>
Date: Sun, 03 May 2020 20:29:49 -0700

The shape of the bound seems plausible but I'll start a thread with the cryptographers to check everything

-- 
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/issues/3619#issuecomment-623240676

---

From: Felix Günther <[email-masked]>
Date: Tue, 05 May 2020 05:43:44 -0700

I reproduced Martin's analysis of CCM based on [Rogaway's 2011 evaluation](https://crossbowerbt.github.io/docs/crypto/rogaway_modes.pdf) of the bounds by [Jonsson](https://link.springer.com/content/pdf/10.1007%2F3-540-36492-7_7.pdf). (Myself not being an expert in producing such bounds, I found the second-level confirmation by Rogaway to be helpful.)

I essentially agree with the numbers, except that --when following the same metric as the [AEBounds paper](https://www.isg.rhul.ac.uk/~kp/TLS-AEbounds.pdf)-- the advantage over an ideal PRP (instead of PRF) should be considered. This simply means losing a 1/2 factor in the bound:

**Confidentiality bound:** `(ql)^2 / 2^n`

`q = 2^24.5` yields an advantage of `2^-59`. I'd hence say it's fine to keep TLS 1.3's recommendation on sending max. full-sized `2^24.5` records.

**Integrity bound:** `v/2^t + (l*(v + q))^2 / 2^n`

`v+q <= 2^25.5`, hence `v <= 24.5` yields an advantage of `2^-57` (matching the other analyses).

Most importantly, I concur with Martin that AEAD_AES_128_CCM_8 would need either much lower bounds or a different risk assessment: applying the same limit of `v = 24.5` would bring the advantage incurred through the `v/2^t` bound up to `2^-39.5`.

Would it still be the best approach to define the same anti-forgery limit across all cipher suites, even if this means going down to `2^24.5`?

Of course, I'm happy to discuss more with @ad-l !

-- 
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/issues/3619#issuecomment-624032621

---

From: Martin Thomson <[email-masked]>
Date: Wed, 06 May 2020 00:08:40 -0700

Thanks for checking this @fxguenther.  I was a little concerned about the PRP/PRF split, so I'm glad to have you correct me.

I ultimately went with per-AEAD recommendations, and a lower limit for CCM.  That's mainly to establish some sort of uniformity around 2^-60 and 2^-57.  Even if those are basically arbitrary choices, at least I think they are defensible and using them uniformly establishes the right expectations about what the standard is.

I'm comfortable with specifying different limits for each AEAD in specifications.  In practice, however, I expect that a far lower tolerance for forgery attempts.

Assuming that these numbers work out, a review of the pull request would be greatly appreciated.  If there are other relevant papers, I'm always happy to pull those in as well.

-- 
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/issues/3619#issuecomment-624479890

---

From: Martin Thomson <[email-masked]>
Date: Wed, 06 May 2020 00:21:14 -0700

I realize that I didn't respond to @anrossi.  That advice applies to the limits that TLS specifies already; this issue is primarily about responding to forgeries.

That said, 1G is pretty good advice.  However what we've seen from this analysis that 1G results in a lower safety margin than TLS aims for.  But it's close enough that if the AEAD is as good as the set we have here, you are probably OK.  However, this does depend a lot on the specific AEAD.  I'd be uncomfortable using so simple a guide in the general 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/issues/3619#issuecomment-624484456

---

From: Martin Thomson <[email-masked]>
Date: Thu, 07 May 2020 18:37:09 -0700

@chris-wood points out an error in my calculation.  I had based my calculations on direct mapping of `l[E]` in the CCM analysis to `l` in our calculations.  That is, `l` was the number of blocks in the message.  But the analysis by Jonsson defines this as:

![image](https://user-images.githubusercontent.com/67641/81360611-b252b580-911f-11ea-8d81-d6824c685d51.png)

The definition of \Beta is the CCM function, so this function really reduces to 2 times the length of the message (in blocks), plus 1 (to account for the additional encryption).  We can ignore the extra 1 as that is absorbed by the tag length.

I'm updating the numbers in the PR.  The result is another halving of the number of packets.  @fxguenther, @ad-l, it's pretty clear that I'm out of my depth here, so your input would be highly valued.

-- 
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/issues/3619#issuecomment-625581184

---

From: Felix Günther <[email-masked]>
Date: Thu, 07 May 2020 23:44:28 -0700

Good catch, yes, the double passing over the message requires a factor 2 here. (The AD a may also be up to 3 blocks if I understand the header format correctly, but I guess that's negligible compared to the conservative 2^10 message size.)

-- 
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/issues/3619#issuecomment-625663474

---

From: Martin Thomson <[email-masked]>
Date: Fri, 08 May 2020 00:26:00 -0700

Good point about the AD.  The AD - at least for QUIC - is always sent, so that fits in the same space.  We don't necessarily need to double count the tiny number of blocks, but as you say, counting that only once yields a negligible difference.  If we had a large AD that wasn't also transmitted, that would be different.

-- 
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/issues/3619#issuecomment-625678827

---

From: Felix Günther <[email-masked]>
Date: Fri, 08 May 2020 00:38:09 -0700

Agreed. To be precise: if I'm not mistaken the AD isn't counted at all right now (`l` accounts for the max. `2^10` payload blocks), but of course the difference is still negligible as long as the AD is small.

-- 
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/issues/3619#issuecomment-625683801