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 athttps://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."¶

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

An Authenticated Encryption with Associated Data (AEAD) algorithmprovides confidentiality and integrity.[RFC5116] specifies an AEADas a function with four inputs -- secret key, nonce, plaintext, associated data(of which plaintext and associated data can optionally be zero-length) -- thatproduces ciphertext output and an error codeindicating success or failure. The ciphertext is typically composed of the encryptedplaintext bytes and an authentication tag.¶

The generic AEAD interface does not describe usage limits. Each AEAD algorithmdoes describe limits on its inputs, but these are formulated as strictfunctional limits, such as the maximum length of inputs, which are determined bythe properties of the underlying AEAD composition. Degradation of the securityof the AEAD as a single key is used multiple times is not given the samethorough treatment.¶

Effective limits can be influenced by the number of "users" ofa given key. In the traditional setting, there is one key shared between twoparties. Any limits on the maximum length of inputs or encryption operationsapply to that single key. The attacker's goal is to break security(confidentiality or integrity) of that specific key. However, in practice, thereare 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 manykeys, further assuming the attacker may have done some offline work to help breaksecurity. As a result, AEAD algorithm limits may depend on offline work and thenumber of keys. However, given that a multi-key attacker does not target any specifickey, 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 berelevant to security. For some algorithms, such as AEAD_AES_128_GCM orAEAD_AES_256_GCM, this limit is 1 and using the same pair of key and nonce hasserious consequences for both confidentiality and integrity; see[NonceDisrespecting]. Nonce-reuse resistant algorithms likeAEAD_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 ofkey and nonce) are used. Setting a limit based on some measurable property ofthe 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 ofsimplifying assumptions. For example, TLS 1.3 and QUIC both specify limits onthe number of records that can be protected, using the simplifying assumptionthat records are the same size; seeSection 5.5 of [TLS] andSection 6.6 of [RFC9001].¶

Exceeding the determined usage limit can be avoided using rekeying. Rekeyinguses a lightweight transform to produce new keys. Rekeying effectively resetsprogress toward single-key limits, allowing a session to be extended withoutdegrading security. Rekeying can also provide a measure of forward andbackward (post-compromise) security.[RFC8645] contains a thorough surveyof rekeying and the consequences of different design choices.¶

Currently, AEAD limits and usage requirements are scattered among peer-reviewedpapers, standards documents, and other RFCs. Determining the correct limits fora given setting is challenging as papers do not use consistent labels orconventions, and rarely apply any simplifications that might aid in reaching asimple limit.¶

The intent of this document is to collate all relevant information about theproper usage and limits of AEAD algorithms in one place. This may serve as astandard reference when considering which AEAD algorithm to use, and how to useit.¶

2.Requirements Notation

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

3.Notation

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

For each AEAD algorithm, we define the (passive) confidentiality and (active)integrity advantage roughly as the advantage an attacker has in breaking thecorresponding classical security property for the algorithm. A passive attackercan query ciphertexts for arbitrary plaintexts. An active attacker can additionallyquery plaintexts for arbitrary ciphertexts. Moreover, we define the combinedauthenticated encryption advantage guaranteeing both confidentiality and integrityagainst an active attacker. Specifically:¶

• Confidentiality advantage (CA): The probability of a passive attackersucceeding in breaking the confidentiality properties (IND-CPA) of the AEAD scheme.In this document, the definition of confidentiality advantage roughly is theprobability that an attacker successfully distinguishes the ciphertext outputsof the AEAD scheme from the outputs of a random function.¶
• Integrity advantage (IA): The probability of an active attacker succeedingin breaking the integrity properties (INT-CTXT) of the AEAD scheme. In this document,the definition of integrity advantage roughly is the probability that an attackeris able to forge a ciphertext that will be accepted as valid.¶
• Authenticated Encryption advantage (AEA): The probability of an activeattacker succeeding in breaking the authenticated-encryption properties of theAEAD scheme. In this document, the definition of authenticated encryptionadvantage roughly is the probability that an attacker successfully distinguishesthe ciphertext outputs of the AEAD scheme from the outputs of a random functionor is able to forge a ciphertext that will be accepted as valid.¶

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

CA <= AEAIA <= AEAAEA <= CA + IA

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

4.Calculating Limits

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

• Confidentiality limit (CL): The number of messages an application can encryptbefore giving the adversary a confidentiality advantage higher than CA.¶
• Integrity limit (IL): The number ciphertexts an application can decrypt,either successfully or not, before giving the adversary an integrity advantagehigher than IA.¶
• Authenticated encryption limit (AEL): The combined number of messages andnumber of ciphertexts an application can encrypt or decrypt before giving theadversary an authenticated encryption advantage higher than AEA.¶

When limits are expressed as a number of messages an application can encrypt ordecrypt, this requires assumptions about the size of messages and anyauthenticated additional data (AAD). Limits can instead be expressed in termsof 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 AEADschemes' block length in bits (n) is provided.¶

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

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

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

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

5.Single-Key AEAD Limits

This section summarizes the confidentiality and integrity bounds and limits for modern AEAD algorithmsused 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 withina connection), seeSection 6.¶

These algorithms, as cited, all define a nonce length (r) of 96 bits. Somedefinitions of these AEAD algorithms allow for other nonce lengths, but theanalyses in this document all fix the nonce length to r = 96. Using other noncelengths might result in different bounds; for example,[GCMProofs] shows thatusing 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.¶

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6.Multi-Key AEAD Limits

In the multi-key setting, each user is assumed to have an independent anduniformly distributed key, though nonces may be re-used across users with somevery small probability. The success probability in attacking one of these manyindependent keys can be generically bounded by the success probability ofattacking 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-keysetting is the product of the single-key advantage and the number of keys.¶

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

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

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

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

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

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

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

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

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

IA <= AEA

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

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

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

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

IA <= AEA

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

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

7.Security Considerations

The different analyses of AEAD functions that this work is based upon generallyassume that the underlying primitives are ideal. For example, that apseudorandom function (PRF) used by the AEAD is indistinguishable from a trulyrandom function or that a pseudorandom permutation (PRP) is indistinguishablefrom a truly random permutation. Thus, the advantage estimates assume that theattacker 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 thisdocument to set limits, it is necessary to validate all these assumptionsfor the setting in which the limits might apply. In most cases, the goal isto use assumptions that result in setting a more conservative limit, but thisis not always the case. As an example of one such simplification, this documentdefines v as the total number of failed decryption queries (that is, failed forgeryattempts), whereas models usually count in v all forgery attempts.¶

The CA, IA, and AEA values defined in this document are upper bounds based on existingcryptographic research. Future analysis may introduce tighter bounds. ApplicationsSHOULD NOT assume these bounds are rigid, and SHOULD accommodate changes. Inparticular, in two-party communication, one participant cannot regard apparentoveruse of a key by other participants as being in error, when it could be thatthe other participant has better information about bounds.¶

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

8.IANA Considerations

This document does not make any request of IANA.¶

Authors' Addresses