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

From: Martin Thomson <[email-masked]>
Date: Thu, 30 Apr 2020 21:36:11 -0700

tl;dr We need to recommend limits on the number of failed decryptions.

## Introduction

At [the QUIPS workshop](https://www.ndss-symposium.org/ndss2020/cfp-quips-workshop/) one of the side discussions concentrated on the quality of the analysis of the [record limits in TLS](https://tools.ietf.org/html/rfc8446#section-5.5) and the applicability of that analysis to QUIC.

Felix Günther, along with Marc Fischlin, Christian Janson, and Kenny Paterson have done a little analysis, based on [the QUIPS paper Felix presented at QUIPS](https://felixguenther.info/Q20_RC.pdf) and the [paper by Atul Luykx and Kenny](https://www.isg.rhul.ac.uk/~kp/TLS-AEbounds.pdf) we used to set limits in TLS.

There are two relevant limits in this analysis:

1. The confidentiality bound, which is usually expressed in terms of advantage an attacker gains in being able to break confidentiality of records/packets as they get more data from valid packets.  For instance, in AES-GCM, the analysis shows that after seeing 2^24.5 packets (almost 24 million) the attacker has a 2^-60 better chance than pure chance of winning the IND-CPA game.

2. The forgery bound, which is again expressed as an probably of an attacker successfully creating a forged record/packet.  Thanks to the analysis done previously, we know that AES-GCM and ChaCha20+Poly1305 have a forgery chance of 2^-57 after 2^60 and 2^36 forgery attempts respectively.

The current text just points to TLS 1.3, which recommends the use of key updates to protect confidentiality.  But TLS has a forgery tolerance of 0: a single failed forgery attempt causes the connection to break.  QUIC (and DTLS) allow for multiple forgeries to be ignored, so we need to factor that in.

## Proposed Solution

As discussed in [this paper](https://felixguenther.info/Q20_RC.pdf) if we want to maintain security, we need to consider both confidentiality and integrity.  For that we need two independent limits:

1. The number of packets that are successfully encrypted and decrypted.

2. The number of packets that are *unsuccessfully* decrypted.

We have the former already.  The latter is what this issue tracks.  Once the limit is at risk of being exceeded, updating keys will force the attacker to start over.

Based on Felix's recommendation I am going to suggest that we limit forgery attempts to 2^36.  I have confirmed this with a close reading of the paper and concur.  There is a significant difference here between AES-GCM and ChaCha20+Poly1305 but we believe that setting a single limit is the best approach.  I will create a pull request to document this approach shortly.

## Notes

We could split the recommendation and allow a larger limit for AES-GCM, but I don't believe that 2^36 (~68 billion) is a significant barrier.  For reference, if you were able to saturate a 10Gbps link with 50 byte IP packets that contained plausible QUIC packets, and the recipient didn't treat this as DoS traffic, it would take 5 minutes.  If we assume that [Fastly's recent performance numbers](https://www.fastly.com/blog/measuring-quic-vs-tcp-computational-efficiency) are more likely representative of potential packet rates, then the limit goes up to 10s of hours.  I would point out that that volume of unproductive traffic is probably a good reason to use something other than a key update to deal with the sender.

A reminder that the underlying analysis assumes that packets are all 2^14 in size, which is the record size in TLS.  This is ~10 times larger than typical MTU on the Internet and many QUIC packets might be smaller than that, so - at least for AES-GCM - recommending a 2^36 limit is more conservative than necessary.  However, if we were to allow for different limits, we'd have to address the question of packet size, as a 2^16 byte packet will be used by some deployments.  For ChaCha20+Poly1305, the only value that matters is the number of packets, so we avoid that question.

Quoting from Felix's email for reference (with permission):

> To briefly recall, the analysis of the QUIC and DTLS 1.3 record layers in terms of robustness when handling maliciously injected packets we did [1] and I presented at QUIPS [2] suggests that a security degradation linear not only in regularly sent/received packets but *also* in the number of rejected packets should be taken into account. I.e., the unreliable-transport nature affects the integrity bounds, with unnoticeable, hence tolerated forgery attempts linearly degrading the underlying AEAD schemes' authenticity security level.
>
> I revisited the analysis done for TLS [3] together with Kenny, with the following conclusions (for both DTLS 1.3 and QUIC):
> 
> 1. AES-GCM
>    The (integrity) bounds in [3] for AES-GCM were already calculated with v = 2^60 forgery attempts ("verification attempts"). Therefore, the same data limits as for TLS 1.3 can be applied, but maybe a note should be added to the RFC that forgery attempts should be counted (and limited to < 2^60, if that's a practical concern).
>
> 2. ChaCha20+Poly1305
>    Integrity degradation for ChaCha20+Poly1305 is v * 2^-93 (for v verification/forgery attempts). In order to keep the same safety margin of 2^-57 as for TLS 1.3 [4], the number of overall received records (correctly verifying or rejected) must be limited to 2^36, requiring counting of received records and an according note in the RFC.
>
> We hope that these conclusions can answer the open questions on AEAD limits. Please let me know if any further investigation is needed, or in which way we can best contribute to adding the according notes to the draft standards.
>
> Best,
> Felix
>
> (with Christian, Kenny, Marc)
>
> [1] Marc Fischlin, Felix Günther, Christian Janson. "Robust Channels: Handling Unreliable Networks in the Record Layers of QUIC and DTLS". Preliminary version at http://felixguenther.info/Q20_RC.pdf
>
> [2] QUIPS slides on Robust Channels: https://github.com/chris-wood/NDSS20-QUIPS/blob/master/slides/quips2020_rch.pdf
>
> [3] Atul Luykx, Kenny Paterson. Limits on Authenticated Encryption Use in TLS". http://www.isg.rhul.ac.uk/~kp/TLS-AEbounds.pdf
>
> [4] https://tools.ietf.org/html/rfc8446#section-5.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/issues/3619

---

From: Martin Thomson <[email-masked]>
Date: Thu, 30 Apr 2020 21:43:48 -0700

@ad-l Can I request that you review this analysis for correctness?  I know that you had reservations about the claims here.

-- 
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-622245505