Skip to main content

Usage Limits on AEAD Algorithms
draft-irtf-cfrg-aead-limits-04

Document Type Active Internet-Draft (cfrg RG)
Authors Felix Günther , Martin Thomson , Christopher A. Wood
Last updated 2022-03-07
Replaces draft-wood-cfrg-aead-limits
Stream Internet Research Task Force (IRTF)
Intended RFC status Informational
Formats plain text html xml htmlized pdfized bibtex
Stream IRTF state Active RG Document
Consensus boilerplate Unknown
Document shepherd (None)
IESG IESG state I-D Exists
Telechat date (None)
Responsible AD (None)
Send notices to (None)
draft-irtf-cfrg-aead-limits-04
Network Working Group                                         F. Günther
Internet-Draft                                                ETH Zurich
Intended status: Informational                                M. Thomson
Expires: 8 September 2022                                        Mozilla
                                                              C. A. Wood
                                                              Cloudflare
                                                            7 March 2022

                    Usage Limits on AEAD Algorithms
                     draft-irtf-cfrg-aead-limits-04

Abstract

   An Authenticated Encryption with Associated Data (AEAD) algorithm
   provides confidentiality and integrity.  Excessive use of the same
   key can give an attacker advantages in breaking these properties.
   This document provides simple guidance for users of common AEAD
   functions about how to limit the use of keys in order to bound the
   advantage given to an attacker.  It considers limits in both single-
   and multi-key settings.

Discussion Venues

   This note is to be removed before publishing as an RFC.

   Discussion of this document takes place on the Crypto Forum Research
   Group mailing list (cfrg@ietf.org), which is archived at
   https://mailarchive.ietf.org/arch/search/?email_list=cfrg.

   Source for this draft and an issue tracker can be found at
   https://github.com/cfrg/draft-irtf-cfrg-aead-limits.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

Günther, et al.         Expires 8 September 2022                [Page 1]
Internet-Draft                 AEAD Limits                    March 2022

   This Internet-Draft will expire on 8 September 2022.

Copyright Notice

   Copyright (c) 2022 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents (https://trustee.ietf.org/
   license-info) in effect on the date of publication of this document.
   Please review these documents carefully, as they describe your rights
   and restrictions with respect to this document.  Code Components
   extracted from this document must include Revised BSD License text as
   described in Section 4.e of the Trust Legal Provisions and are
   provided without warranty as described in the Revised BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
   2.  Requirements Notation . . . . . . . . . . . . . . . . . . . .   4
   3.  Notation  . . . . . . . . . . . . . . . . . . . . . . . . . .   4
   4.  Calculating Limits  . . . . . . . . . . . . . . . . . . . . .   6
   5.  Single-Key AEAD Limits  . . . . . . . . . . . . . . . . . . .   8
     5.1.  AEAD_AES_128_GCM and AEAD_AES_256_GCM . . . . . . . . . .   8
       5.1.1.  Confidentiality Limit . . . . . . . . . . . . . . . .   8
       5.1.2.  Integrity Limit . . . . . . . . . . . . . . . . . . .   8
     5.2.  AEAD_CHACHA20_POLY1305  . . . . . . . . . . . . . . . . .   9
     5.3.  AEAD_AES_128_CCM  . . . . . . . . . . . . . . . . . . . .   9
       5.3.1.  Confidentiality Limit . . . . . . . . . . . . . . . .   9
       5.3.2.  Integrity Limit . . . . . . . . . . . . . . . . . . .  10
     5.4.  AEAD_AES_128_CCM_8  . . . . . . . . . . . . . . . . . . .  10
     5.5.  Single-Key Examples . . . . . . . . . . . . . . . . . . .  10
   6.  Multi-Key AEAD Limits . . . . . . . . . . . . . . . . . . . .  11
     6.1.  AEAD_AES_128_GCM and AEAD_AES_256_GCM . . . . . . . . . .  12
       6.1.1.  Authenticated Encryption Security Limit . . . . . . .  12
       6.1.2.  Confidentiality Limit . . . . . . . . . . . . . . . .  13
       6.1.3.  Integrity Limit . . . . . . . . . . . . . . . . . . .  13
     6.2.  AEAD_CHACHA20_POLY1305  . . . . . . . . . . . . . . . . .  13
       6.2.1.  Authenticated Encryption Security Limit . . . . . . .  13
       6.2.2.  Confidentiality Limit . . . . . . . . . . . . . . . .  14
       6.2.3.  Integrity Limit . . . . . . . . . . . . . . . . . . .  14
     6.3.  AEAD_AES_128_CCM and AEAD_AES_128_CCM_8 . . . . . . . . .  14
     6.4.  Multi-Key Examples  . . . . . . . . . . . . . . . . . . .  15
   7.  Security Considerations . . . . . . . . . . . . . . . . . . .  16
   8.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  16
   9.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  16
     9.1.  Normative References  . . . . . . . . . . . . . . . . . .  16
     9.2.  Informative References  . . . . . . . . . . . . . . . . .  18

Günther, et al.         Expires 8 September 2022                [Page 2]
Internet-Draft                 AEAD Limits                    March 2022

   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  19

1.  Introduction

   An Authenticated Encryption with Associated Data (AEAD) algorithm
   provides confidentiality and integrity.  [RFC5116] specifies an AEAD
   as a function with four inputs -- secret key, nonce, plaintext,
   associated data (of which plaintext and associated data can
   optionally be zero-length) -- that produces ciphertext output and an
   error code indicating success or failure.  The ciphertext is
   typically composed of the encrypted plaintext bytes and an
   authentication tag.

   The generic AEAD interface does not describe usage limits.  Each AEAD
   algorithm does describe limits on its inputs, but these are
   formulated as strict functional limits, such as the maximum length of
   inputs, which are determined by the properties of the underlying AEAD
   composition.  Degradation of the security of the AEAD as a single key
   is used multiple times is not given the same thorough treatment.

   Effective limits can be influenced by the number of "users" of a
   given key.  In the traditional setting, there is one key shared
   between two parties.  Any limits on the maximum length of inputs or
   encryption operations apply to that single key.  The attacker's goal
   is to break security (confidentiality or integrity) of that specific
   key.  However, in practice, there are often many users with
   independent keys.  This multi-key security setting, often referred to
   as the multi-user setting in the academic literature, considers an
   attacker's advantage in breaking security of any of these many keys,
   further assuming the attacker may have done some offline work to help
   break security.  As a result, AEAD algorithm limits may depend on
   offline work and the number of keys.  However, given that a multi-key
   attacker does not target any specific key, acceptable advantages may
   differ from that of the single-key setting.

   The number of times a single pair of key and nonce can be used might
   also be relevant to security.  For some algorithms, such as
   AEAD_AES_128_GCM or AEAD_AES_256_GCM, this limit is 1 and using the
   same pair of key and nonce has serious consequences for both
   confidentiality and integrity; see [NonceDisrespecting].  Nonce-reuse
   resistant algorithms like AEAD_AES_128_GCM_SIV can tolerate a limited
   amount of nonce reuse.

   It is good practice to have limits on how many times the same key (or
   pair of key and nonce) are used.  Setting a limit based on some
   measurable property of the usage, such as number of protected
   messages or amount of data transferred, ensures that it is easy to
   apply limits.  This might require the application of simplifying

Günther, et al.         Expires 8 September 2022                [Page 3]
Internet-Draft                 AEAD Limits                    March 2022

   assumptions.  For example, TLS 1.3 and QUIC both specify limits on
   the number of records that can be protected, using the simplifying
   assumption that records are the same size; see Section 5.5 of [TLS]
   and Section 6.6 of [RFC9001].

   Exceeding the determined usage limit can be avoided using rekeying.
   Rekeying uses a lightweight transform to produce new keys.  Rekeying
   effectively resets progress toward single-key limits, allowing a
   session to be extended without degrading security.  Rekeying can also
   provide a measure of forward and backward (post-compromise) security.
   [RFC8645] contains a thorough survey of rekeying and the consequences
   of different design choices.

   Currently, AEAD limits and usage requirements are scattered among
   peer-reviewed papers, standards documents, and other RFCs.
   Determining the correct limits for a given setting is challenging as
   papers do not use consistent labels or conventions, and rarely apply
   any simplifications that might aid in reaching a simple limit.

   The intent of this document is to collate all relevant information
   about the proper usage and limits of AEAD algorithms in one place.
   This may serve as a standard reference when considering which AEAD
   algorithm to use, and how to use it.

2.  Requirements Notation

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
   "OPTIONAL" in this document are to be interpreted as described in
   BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
   capitals, as shown here.

3.  Notation

   This document defines limitations in part using the quantities in
   Table 1 below.

Günther, et al.         Expires 8 September 2022                [Page 4]
Internet-Draft                 AEAD Limits                    March 2022

      +========+====================================================+
      | Symbol | Description                                        |
      +========+====================================================+
      |      n | AEAD block length (in bits)                        |
      +--------+----------------------------------------------------+
      |      k | AEAD key length (in bits)                          |
      +--------+----------------------------------------------------+
      |      r | AEAD nonce length (in bits)                        |
      +--------+----------------------------------------------------+
      |      t | Size of the authentication tag (in bits)           |
      +--------+----------------------------------------------------+
      |      l | Maximum length of each message (in blocks)         |
      +--------+----------------------------------------------------+
      |      s | Total plaintext length in all messages (in blocks) |
      +--------+----------------------------------------------------+
      |      q | Number of protected messages (AEAD encryption      |
      |        | invocations)                                       |
      +--------+----------------------------------------------------+
      |      v | Number of attacker forgery attempts (failed AEAD   |
      |        | decryption invocations)                            |
      +--------+----------------------------------------------------+
      |      p | Upper bound on adversary attack probability        |
      +--------+----------------------------------------------------+
      |      o | Offline adversary work (in number of encryption    |
      |        | and decryption queries; multi-key setting only)    |
      +--------+----------------------------------------------------+
      |      u | Number of keys (multi-key setting only)            |
      +--------+----------------------------------------------------+
      |      B | Maximum number of blocks encrypted by any key      |
      |        | (multi-key setting only)                           |
      +--------+----------------------------------------------------+

                             Table 1: Notation

   For each AEAD algorithm, we define the (passive) confidentiality and
   (active) integrity advantage roughly as the advantage an attacker has
   in breaking the corresponding classical security property for the
   algorithm.  A passive attacker can query ciphertexts for arbitrary
   plaintexts.  An active attacker can additionally query plaintexts for
   arbitrary ciphertexts.  Moreover, we define the combined
   authenticated encryption advantage guaranteeing both confidentiality
   and integrity against an active attacker.  Specifically:

Günther, et al.         Expires 8 September 2022                [Page 5]
Internet-Draft                 AEAD Limits                    March 2022

   *  Confidentiality advantage (CA): The probability of a passive
      attacker succeeding in breaking the confidentiality properties
      (IND-CPA) of the AEAD scheme.  In this document, the definition of
      confidentiality advantage roughly is the probability that an
      attacker successfully distinguishes the ciphertext outputs of the
      AEAD scheme from the outputs of a random function.

   *  Integrity advantage (IA): The probability of an active attacker
      succeeding in breaking the integrity properties (INT-CTXT) of the
      AEAD scheme.  In this document, the definition of integrity
      advantage roughly is the probability that an attacker is able to
      forge a ciphertext that will be accepted as valid.

   *  Authenticated Encryption advantage (AEA): The probability of an
      active attacker succeeding in breaking the authenticated-
      encryption properties of the AEAD scheme.  In this document, the
      definition of authenticated encryption advantage roughly is the
      probability that an attacker successfully distinguishes the
      ciphertext outputs of the AEAD scheme from the outputs of a random
      function or is able to forge a ciphertext that will be accepted as
      valid.

   See [AEComposition], [AEAD] for the formal definitions of and
   relations between passive confidentiality (IND-CPA), ciphertext
   integrity (INT-CTXT), and authenticated encryption security (AE).
   The authenticated encryption advantage subsumes, and can be derived
   as the combination of, both CA and IA:

   CA <= AEA
   IA <= AEA
   AEA <= CA + IA

   Each application requires an individual determination of limits in
   order to keep CA and IA sufficiently small.  For instance, TLS aims
   to keep CA below 2^-60 and IA below 2^-57 in the single-key setting;
   see Section 5.5 of [TLS].

4.  Calculating Limits

   Once upper bounds on CA, IA, or AEA are determined, this document
   defines a process for determining three overall operational limits:

   *  Confidentiality limit (CL): The number of messages an application
      can encrypt before giving the adversary a confidentiality
      advantage higher than CA.

Günther, et al.         Expires 8 September 2022                [Page 6]
Internet-Draft                 AEAD Limits                    March 2022

   *  Integrity limit (IL): The number ciphertexts an application can
      decrypt, either successfully or not, before giving the adversary
      an integrity advantage higher than IA.

   *  Authenticated encryption limit (AEL): The combined number of
      messages and number of ciphertexts an application can encrypt or
      decrypt before giving the adversary an authenticated encryption
      advantage higher than AEA.

   When limits are expressed as a number of messages an application can
   encrypt or decrypt, this requires assumptions about the size of
   messages and any authenticated additional data (AAD).  Limits can
   instead be expressed in terms of the number of bytes, or blocks, of
   plaintext and maybe AAD in total.

   To aid in translating between message-based and byte/block-based
   limits, a formulation of limits that includes a maximum message size
   (l) and the AEAD schemes' block length in bits (n) is provided.

   All limits are based on the total number of messages, either the
   number of protected messages (q) or the number of forgery attempts
   (v); which correspond to CL and IL respectively.

   Limits are then derived from those bounds using a target attacker
   probability.  For example, given an integrity advantage of IA = v *
   (8l / 2^106) and a targeted maximum attacker success probability of
   IA = p, the algorithm remains secure, i.e., the adversary's advantage
   does not exceed the targeted probability of success, provided that v
   <= (p * 2^106) / 8l.  In turn, this implies that v <= (p * 2^103) / l
   is the corresponding limit.

   To apply these limits, implementations can count the number of
   messages that are protected or rejected against the determined limits
   (q and v respectively).  This requires that messages cannot exceed
   the maximum message size (l) that is chosen.

   This analysis assumes a message-based approach to setting limits.
   Implementations that use byte counting rather than message counting
   could use a maximum message size (l) of one to determine a limit for
   q that can be applied with byte counting.  This results in
   attributing per-message overheads to every byte, so the resulting
   limit could be significantly lower than necessary.  Actions, like
   rekeying, that are taken to avoid the limit might occur more often as
   a result.

Günther, et al.         Expires 8 September 2022                [Page 7]
Internet-Draft                 AEAD Limits                    March 2022

5.  Single-Key AEAD Limits

   This section summarizes the confidentiality and integrity bounds and
   limits for modern AEAD algorithms used in IETF protocols, including:
   AEAD_AES_128_GCM [RFC5116], AEAD_AES_256_GCM [RFC5116],
   AEAD_AES_128_CCM [RFC5116], AEAD_CHACHA20_POLY1305 [RFC8439],
   AEAD_AES_128_CCM_8 [RFC6655].  The limits in this section apply to
   using these schemes with a single key; for settings where multiple
   keys are deployed (for example, when rekeying within a connection),
   see Section 6.

   These algorithms, as cited, all define a nonce length (r) of 96 bits.
   Some definitions of these AEAD algorithms allow for other nonce
   lengths, but the analyses in this document all fix the nonce length
   to r = 96.  Using other nonce lengths might result in different
   bounds; for example, [GCMProofs] shows that using a variable-length
   nonce for AES-GCM results in worse security bounds.

   The CL and IL values bound the total number of encryption and forgery
   queries (q and v).  Alongside each advantage value, we also specify
   these bounds.

5.1.  AEAD_AES_128_GCM and AEAD_AES_256_GCM

   The CL and IL values for AES-GCM are derived in [AEBounds] and
   summarized below.  For this AEAD, n = 128 and t = 128 [GCM].  In this
   example, the length s is the sum of AAD and plaintext (in blocks of
   128 bits), as described in [GCMProofs].

5.1.1.  Confidentiality Limit

   CA <= ((s + q + 1)^2) / 2^129

   This implies the following usage limit:

   q + s <= p^(1/2) * 2^(129/2) - 1

   Which, for a message-based protocol with s <= q * l, if we assume
   that every packet is size l (in blocks of 128 bits), produces the
   limit:

   q <= (p^(1/2) * 2^(129/2) - 1) / (l + 1)

5.1.2.  Integrity Limit

   IA <= 2 * (v * (l + 1)) / 2^128

   This implies the following limit:

Günther, et al.         Expires 8 September 2022                [Page 8]
Internet-Draft                 AEAD Limits                    March 2022

   v <= (p * 2^127) / (l + 1)

5.2.  AEAD_CHACHA20_POLY1305

   The known single-user analyses for AEAD_CHACHA20_POLY1305
   [ChaCha20Poly1305-SU], [ChaCha20Poly1305-MU] combine the
   confidentiality and integrity limits into a single expression,
   covered below.  For this AEAD, n = 512, k = 256, and t = 128; the
   length l is the sum of AAD and plaintext (in blocks of 128 bits), see
   [ChaCha20Poly1305-MU].

   AEA <= (v * (l + 1)) / 2^103

   This advantage is a tight reduction based on the underlying Poly1305
   PRF [Poly1305].  It implies the following limit:

   v <= (p * 2^103) / (l + 1)

5.3.  AEAD_AES_128_CCM

   The CL and IL values for AEAD_AES_128_CCM are derived from
   [CCM-ANALYSIS] and specified in the QUIC-TLS mapping specification
   [RFC9001].  This analysis uses the total number of underlying block
   cipher operations to derive its bound.  For CCM, this number is the
   sum of: the length of the associated data in blocks, the length of
   the ciphertext in blocks, the length of the plaintext in blocks, plus
   1.

   In the following limits, this is simplified to a value of twice the
   length of the packet in blocks, i.e., 2l represents the effective
   length, in number of block cipher operations, of a message with l
   blocks.  This simplification is based on the observation that common
   applications of this AEAD carry only a small amount of associated
   data compared to ciphertext.  For example, QUIC has 1 to 3 blocks of
   AAD.

   For this AEAD, n = 128 and t = 128.

5.3.1.  Confidentiality Limit

   CA <= (2l * q)^2 / 2^n
      <= (2l * q)^2 / 2^128

   This implies the following limit:

   q <= sqrt((p * 2^126) / l^2)

Günther, et al.         Expires 8 September 2022                [Page 9]
Internet-Draft                 AEAD Limits                    March 2022

5.3.2.  Integrity Limit

   IA <= v / 2^t + (2l * (v + q))^2 / 2^n
      <= v / 2^128 + (2l * (v + q))^2 / 2^128

   This implies the following limit:

   v + (2l * (v + q))^2 <= p * 2^128

   In a setting where v or q is sufficiently large, v is negligible
   compared to (2l * (v + q))^2, so this this can be simplified to:

   v + q <= sqrt(p) * 2^63 / l

5.4.  AEAD_AES_128_CCM_8

   The analysis in [CCM-ANALYSIS] also applies to this AEAD, but the
   reduced tag length of 64 bits changes the integrity limit calculation
   considerably.

   IA <= v / 2^t + (2l * (v + q))^2 / 2^n
      <= v / 2^64 + (2l * (v + q))^2 / 2^128

   This results in reducing the limit on v by a factor of 2^64.

   v * 2^64 + (2l * (v + q))^2 <= p * 2^128

5.5.  Single-Key Examples

   An example protocol might choose to aim for a single-key CA and IA
   that is at most 2^-50.  If the messages exchanged in the protocol are
   at most a common Internet MTU of around 1500 bytes, then a value for
   l might be set to 2^7.  Table 2 shows limits for q and v that might
   be chosen under these conditions.

Günther, et al.         Expires 8 September 2022               [Page 10]
Internet-Draft                 AEAD Limits                    March 2022

            +========================+===========+===========+
            | AEAD                   | Maximum q | Maximum v |
            +========================+===========+===========+
            | AEAD_AES_128_GCM       |    2^32.5 |      2^71 |
            +------------------------+-----------+-----------+
            | AEAD_AES_256_GCM       |    2^32.5 |      2^71 |
            +------------------------+-----------+-----------+
            | AEAD_CHACHA20_POLY1305 |       n/a |      2^46 |
            +------------------------+-----------+-----------+
            | AEAD_AES_128_CCM       |      2^30 |      2^30 |
            +------------------------+-----------+-----------+
            | AEAD_AES_128_CCM_8     |    2^30.9 |      2^13 |
            +------------------------+-----------+-----------+

                    Table 2: Example single-key limits

   AEAD_CHACHA20_POLY1305 provides no limit to q based on the provided
   single-user analyses.

   The limit for q on AEAD_AES_128_CCM and AEAD_AES_128_CCM_8 is reduced
   due to a need to reduce the value of q to ensure that IA does not
   exceed the target.  This assumes equal proportions for q and v for
   AEAD_AES_128_CCM.  AEAD_AES_128_CCM_8 permits a much smaller value of
   v due to the shorter tag, which permits a higher limit for q.

   Some protocols naturally limit v to 1, such as TCP-based variants of
   TLS, which terminate sessions on decryption failure.  If v is limited
   to 1, q can be increased to 2^31 for both CCM AEADs.

6.  Multi-Key AEAD Limits

   In the multi-key setting, each user is assumed to have an independent
   and uniformly distributed key, though nonces may be re-used across
   users with some very small probability.  The success probability in
   attacking one of these many independent keys can be generically
   bounded by the success probability of attacking a single key
   multiplied by the number of keys present [MUSecurity], [GCM-MU].
   Absent concrete multi-key bounds, this means the attacker advantage
   in the multi-key setting is the product of the single-key advantage
   and the number of keys.

   This section summarizes the confidentiality and integrity bounds and
   limits for the same algorithms as in Section 5 for the multi-key
   setting.  The CL and IL values bound the total number of encryption
   and forgery queries (q and v).  Alongside each value, we also specify
   these bounds.

Günther, et al.         Expires 8 September 2022               [Page 11]
Internet-Draft                 AEAD Limits                    March 2022

6.1.  AEAD_AES_128_GCM and AEAD_AES_256_GCM

   Concrete multi-key bounds for AEAD_AES_128_GCM and AEAD_AES_256_GCM
   exist due to Theorem 4.3 in [GCM-MU2], which covers protocols with
   nonce randomization, like TLS 1.3 [TLS] and QUIC [RFC9001].  Here,
   the full nonce is XORed with a secret, random offset.  The bound for
   nonce randomization was further improved in [ChaCha20Poly1305-MU].

   Results for AES-GCM with random, partially implicit nonces [RFC5288]
   are captured by Theorem 5.3 in [GCM-MU2], which apply to protocols
   such as TLS 1.2 [RFC5246].  Here, the implicit part of the nonce is a
   random value, of length at least 32 bits and fixed per key, while the
   explicit part of the nonce is a non-repeating counter.  The full
   nonce is the concatenation of the two parts.  This produces similar
   limits under most conditions.

   For this AEAD, n = 128, t = 128, and r = 96; the key length is k =
   128 or k = 256 for AEAD_AES_128_GCM and AEAD_AES_128_GCM
   respectively.

6.1.1.  Authenticated Encryption Security Limit

   Protocols with nonce randomization have a limit of:

   AEA <= (q+v)*l*B / 2^127

   This implies the following limit:

   q + v <= p * 2^127 / (l * B)

   This assumes that B is much larger than 100; that is, each user
   enciphers significantly more than 1600 bytes of data.  Otherwise, B
   should be increased by 161 for AEAD_AES_128_GCM and by 97 for
   AEAD_AES_256_GCM.

   Protocols with random, partially implicit nonces have the following
   limit, which is similar to that for nonce randomization:

   AEA <= (((q+v)*o + (q+v)^2) / 2^(k+26)) + ((q+v)*l*B / 2^127)

   The first term is negligible if k = 256; this implies the following
   simplified limits:

   AEA <= (q+v)*l*B / 2^127
   q + v <= p * 2^127 / (l * B)

Günther, et al.         Expires 8 September 2022               [Page 12]
Internet-Draft                 AEAD Limits                    March 2022

   For k = 128, assuming o <= q+v (i.e., that the attacker does not
   spend more work than all legitimate protocol users together), the
   limits are:

   AEA <= (((q+v)*o + (q+v)^2) / 2^154) + ((q+v)*l*B / 2^127)
   q + v <= min( sqrt(p) * 2^76,  p * 2^126 / (l * B) )

6.1.2.  Confidentiality Limit

   The confidentiality advantage is essentially dominated by the same
   term as the AE advantage for protocols with nonce randomization:

   CA <= q*l*B / 2^127

   This implies the following limit:

   q <= p * 2^127 / (l * B)

   Similarly, the limits for protocols with random, partially implicit
   nonces are:

   CA <= ((q*o + q^2) / 2^(k+26)) + (q*l*B / 2^127)
   q <= min( sqrt(p) * 2^76,  p * 2^126 / (l * B) )

6.1.3.  Integrity Limit

   There is currently no dedicated integrity multi-key bound available
   for AEAD_AES_128_GCM and AEAD_AES_256_GCM.  The AE limit can be used
   to derive an integrity limit as:

   IA <= AEA

   Section 6.1.1 therefore contains the integrity limits.

6.2.  AEAD_CHACHA20_POLY1305

   Concrete multi-key bounds for AEAD_CHACHA20_POLY1305 are given in
   Theorem 7.8 in [ChaCha20Poly1305-MU], covering protocols with nonce
   randomization like TLS 1.3 [TLS] and QUIC [RFC9001].

   For this AEAD, n = 512, k = 256, t = 128, and r = 96; the length l is
   the sum of AAD and plaintext (in blocks of 128 bits).

6.2.1.  Authenticated Encryption Security Limit

   Protocols with nonce randomization have a limit of:

   AEA <= (v * (l + 1)) / 2^103

Günther, et al.         Expires 8 September 2022               [Page 13]
Internet-Draft                 AEAD Limits                    March 2022

   It implies the following limit:

   v <= (p * 2^103) / (l + 1)

   Note that this is the same limit as in the single-user case except
   that the total number of forgery attempts v and maximum message
   length in blocks l is calculated across all used keys.

6.2.2.  Confidentiality Limit

   While the AE advantage is dominated by the number of forgery attempts
   v, those are irrelevant for the confidentiality advantage.  The
   relevant limit for protocols with nonce randomization becomes
   dominated, at a very low level, by the adversary's offline work o,
   number of protected messages q and maximum blocks encrypted B, across
   all used keys:

   CA <= ((o + q) / 2^247) + ((B + q)^2 / 2^513)

   It implies the following simplified limit, which for most reasonable
   values of p is dominated by a technical limitation around q = 2^100:

   q <= min( p * 2^246 - o,  sqrt(p) * 2^256 - B, 2^100 )

6.2.3.  Integrity Limit

   The AE limit for AEAD_CHACHA20_POLY1305 essentially is the integrity
   (multi-key) bound.  The former hence also applies to the latter:

   IA <= AEA

   Section 6.2.1 therefore contains the integrity limits.

6.3.  AEAD_AES_128_CCM and AEAD_AES_128_CCM_8

   There are currently no concrete multi-key bounds for AEAD_AES_128_CCM
   or AEAD_AES_128_CCM_8.  Thus, to account for the additional factor u,
   i.e., the number of keys, each p term in the confidentiality and
   integrity limits is replaced with p / u.

   The multi-key integrity limit for AEAD_AES_128_CCM is as follows.

   v + q <= sqrt(p / u) * 2^63 / l

   Likewise, the multi-key integrity limit for AEAD_AES_128_CCM_8 is as
   follows.

   v * 2^64 + (2l * (v + q))^2 <= (p / u) * 2^128

Günther, et al.         Expires 8 September 2022               [Page 14]
Internet-Draft                 AEAD Limits                    March 2022

6.4.  Multi-Key Examples

   An example protocol might choose to aim for a multi-key AEA, CA, and
   IA that is at most 2^-50.  If the messages exchanged in the protocol
   are at most a common Internet MTU of around 1500 bytes, then a value
   for l might be set to 2^7.  Table 3 shows limits for q and v across
   all keys that might be chosen under these conditions.

        +========================+================+==============+
        | AEAD                   |      Maximum q |    Maximum v |
        +========================+================+==============+
        | AEAD_AES_128_GCM       |         2^69/B |       2^69/B |
        +------------------------+----------------+--------------+
        | AEAD_AES_256_GCM       |         2^69/B |       2^69/B |
        +------------------------+----------------+--------------+
        | AEAD_CHACHA20_POLY1305 |          2^100 |         2^46 |
        +------------------------+----------------+--------------+
        | AEAD_AES_128_CCM       |   2^30/sqrt(u) | 2^30/sqrt(u) |
        +------------------------+----------------+--------------+
        | AEAD_AES_128_CCM_8     | 2^30.9/sqrt(u) |       2^13/u |
        +------------------------+----------------+--------------+

                    Table 3: Example multi-key limits

   The limits for AEAD_AES_128_GCM, AEAD_AES_256_GCM, AEAD_AES_128_CCM,
   and AEAD_AES_128_CCM_8 assume equal proportions for q and v.  The
   limits for AEAD_AES_128_GCM, AEAD_AES_256_GCM and
   AEAD_CHACHA20_POLY1305 assume the use of nonce randomization, like in
   TLS 1.3 [TLS] and QUIC [RFC9001].

   The limits for AEAD_AES_128_GCM and AEAD_AES_256_GCM further depend
   on the maximum number B of 128-bit blocks encrypted by any single
   key.  For example, limiting the number of messages (of size <= 2^7
   blocks) to at most 2^20 (about a million) per key results in B =
   2^27, which limits both q and v to 2^42 messages.

   Only the limits for AEAD_AES_128_CCM and AEAD_AES_128_CCM_8 depend on
   the number of used keys u, which further reduces them considerably.
   If v is limited to 1, q can be increased to 2^31/sqrt(u) for both CCM
   AEADs.

Günther, et al.         Expires 8 September 2022               [Page 15]
Internet-Draft                 AEAD Limits                    March 2022

7.  Security Considerations

   The different analyses of AEAD functions that this work is based upon
   generally assume that the underlying primitives are ideal.  For
   example, that a pseudorandom function (PRF) used by the AEAD is
   indistinguishable from a truly random function or that a pseudorandom
   permutation (PRP) is indistinguishable from a truly random
   permutation.  Thus, the advantage estimates assume that the attacker
   is not able to exploit a weakness in an underlying primitive.

   Many of the formulae in this document depend on simplifying
   assumptions, from differing models, which means that results are not
   universally applicable.  When using this document to set limits, it
   is necessary to validate all these assumptions for the setting in
   which the limits might apply.  In most cases, the goal is to use
   assumptions that result in setting a more conservative limit, but
   this is not always the case.  As an example of one such
   simplification, this document defines v as the total number of failed
   decryption queries (that is, failed forgery attempts), whereas models
   usually count in v all forgery attempts.

   The CA, IA, and AEA values defined in this document are upper bounds
   based on existing cryptographic research.  Future analysis may
   introduce tighter bounds.  Applications SHOULD NOT assume these
   bounds are rigid, and SHOULD accommodate changes.  In particular, in
   two-party communication, one participant cannot regard apparent
   overuse of a key by other participants as being in error, when it
   could be that the other participant has better information about
   bounds.

   Note that the limits in this document apply to the adversary's
   ability to conduct a single successful forgery.  For some algorithms
   and in some cases, an adversary's success probability in repeating
   forgeries may be noticeably larger than that of the first forgery.
   As an example, [MF05] describes such multiple forgery attacks in the
   context of AES-GCM in more detail.

8.  IANA Considerations

   This document does not make any request of IANA.

9.  References

9.1.  Normative References

   [AEAD]     Rogaway, P., "Authenticated-Encryption with Associated-
              Data", September 2002,
              <https://web.cs.ucdavis.edu/~rogaway/papers/ad.pdf>.

Günther, et al.         Expires 8 September 2022               [Page 16]
Internet-Draft                 AEAD Limits                    March 2022

   [AEBounds] Luykx, A. and K. Paterson, "Limits on Authenticated
              Encryption Use in TLS", 8 March 2016,
              <http://www.isg.rhul.ac.uk/~kp/TLS-AEbounds.pdf>.

   [AEComposition]
              Bellare, M. and C. Namprempre, "Authenticated Encryption:
              Relations among notions and analysis of the generic
              composition paradigm", July 2007,
              <https://eprint.iacr.org/2000/025.pdf>.

   [CCM-ANALYSIS]
              Jonsson, J., "On the Security of CTR + CBC-MAC", Selected
              Areas in Cryptography pp. 76-93,
              DOI 10.1007/3-540-36492-7_7, 2003,
              <https://doi.org/10.1007/3-540-36492-7_7>.

   [ChaCha20Poly1305-MU]
              Degabriele, J., Govinden, J., Günther, F., and K.
              Paterson, "The Security of ChaCha20-Poly1305 in the Multi-
              User Setting", Proceedings of the 2021 ACM SIGSAC
              Conference on Computer and Communications Security,
              DOI 10.1145/3460120.3484814, November 2021,
              <https://doi.org/10.1145/3460120.3484814>.

   [ChaCha20Poly1305-SU]
              Procter, G., "A Security Analysis of the Composition of
              ChaCha20 and Poly1305", 11 August 2014,
              <https://eprint.iacr.org/2014/613.pdf>.

   [GCM]      Dworkin, M., "Recommendation for Block Cipher Modes of
              Operation: Galois/Counter Mode (GCM) and GMAC",
              NIST Special Publication 800-38D, November 2007.

   [GCM-MU]   Bellare, M. and B. Tackmann, "The Multi-User Security of
              Authenticated Encryption: AES-GCM in TLS 1.3", 27 November
              2017, <https://eprint.iacr.org/2016/564.pdf>.

   [GCM-MU2]  Hoang, V. T., Tessaro, S., and A. Thiruvengadam, "The
              Multi-user Security of GCM, Revisited: Tight Bounds for
              Nonce Randomization", 15 October 2018,
              <https://eprint.iacr.org/2018/993.pdf>.

   [GCMProofs]
              Iwata, T., Ohashi, K., and K. Minematsu, "Breaking and
              Repairing GCM Security Proofs", 1 August 2012,
              <https://eprint.iacr.org/2012/438.pdf>.

Günther, et al.         Expires 8 September 2022               [Page 17]
Internet-Draft                 AEAD Limits                    March 2022

   [MUSecurity]
              Bellare, M., Boldyreva, A., and S. Micali, "Public-Key
              Encryption in a Multi-user Setting: Security Proofs and
              Improvements", May 2000,
              <https://cseweb.ucsd.edu/~mihir/papers/musu.pdf>.

   [Poly1305] Bernstein, D., "The Poly1305-AES Message-Authentication
              Code", Fast Software Encryption pp. 32-49,
              DOI 10.1007/11502760_3, 2005,
              <https://doi.org/10.1007/11502760_3>.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://www.rfc-editor.org/rfc/rfc2119>.

   [RFC5116]  McGrew, D., "An Interface and Algorithms for Authenticated
              Encryption", RFC 5116, DOI 10.17487/RFC5116, January 2008,
              <https://www.rfc-editor.org/rfc/rfc5116>.

   [RFC6655]  McGrew, D. and D. Bailey, "AES-CCM Cipher Suites for
              Transport Layer Security (TLS)", RFC 6655,
              DOI 10.17487/RFC6655, July 2012,
              <https://www.rfc-editor.org/rfc/rfc6655>.

   [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
              2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
              May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.

   [RFC8439]  Nir, Y. and A. Langley, "ChaCha20 and Poly1305 for IETF
              Protocols", RFC 8439, DOI 10.17487/RFC8439, June 2018,
              <https://www.rfc-editor.org/rfc/rfc8439>.

9.2.  Informative References

   [MF05]     McGrew, D. A. and S. R. Fluhrer, "Multiple forgery attacks
              against Message Authentication Codes", 31 May 2005,
              <https://csrc.nist.gov/CSRC/media/Projects/Block-Cipher-
              Techniques/documents/BCM/Comments/CWC-GCM/multi-forge-
              01.pdf>.

   [NonceDisrespecting]
              Bock, H., Zauner, A., Devlin, S., Somorovsky, J., and P.
              Jovanovic, "Nonce-Disrespecting Adversaries -- Practical
              Forgery Attacks on GCM in TLS", 17 May 2016,
              <https://eprint.iacr.org/2016/475.pdf>.

Günther, et al.         Expires 8 September 2022               [Page 18]
Internet-Draft                 AEAD Limits                    March 2022

   [RFC5246]  Dierks, T. and E. Rescorla, "The Transport Layer Security
              (TLS) Protocol Version 1.2", RFC 5246,
              DOI 10.17487/RFC5246, August 2008,
              <https://www.rfc-editor.org/rfc/rfc5246>.

   [RFC5288]  Salowey, J., Choudhury, A., and D. McGrew, "AES Galois
              Counter Mode (GCM) Cipher Suites for TLS", RFC 5288,
              DOI 10.17487/RFC5288, August 2008,
              <https://www.rfc-editor.org/rfc/rfc5288>.

   [RFC8645]  Smyshlyaev, S., Ed., "Re-keying Mechanisms for Symmetric
              Keys", RFC 8645, DOI 10.17487/RFC8645, August 2019,
              <https://www.rfc-editor.org/rfc/rfc8645>.

   [RFC9001]  Thomson, M., Ed. and S. Turner, Ed., "Using TLS to Secure
              QUIC", RFC 9001, DOI 10.17487/RFC9001, May 2021,
              <https://www.rfc-editor.org/rfc/rfc9001>.

   [TLS]      Rescorla, E., "The Transport Layer Security (TLS) Protocol
              Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018,
              <https://www.rfc-editor.org/rfc/rfc8446>.

Authors' Addresses

   Felix Günther
   ETH Zurich
   Email: mail@felixguenther.info

   Martin Thomson
   Mozilla
   Email: mt@lowentropy.net

   Christopher A. Wood
   Cloudflare
   Email: caw@heapingbits.net

Günther, et al.         Expires 8 September 2022               [Page 19]