| Internet-Draft | AEAD Limits | May 2020 |
| Günther, et al. | Expires 21 November 2020 | [Page] |
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.¶
This note is to be removed before publishing as an RFC.¶
Source for this draft and an issue tracker can be found at https://github.com/chris-wood/draft-wood-cfrg-aead-limits.¶
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."¶
This Internet-Draft will expire on 21 November 2020.¶
Copyright (c) 2020 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 Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.¶
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, and optional associated data - that produces ciphertext output and 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 a thorough treatment.¶
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 assumptions. For example, TLS 1.3 specifies 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].¶
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.¶
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.¶
This document defines limitations in part using the quantities below.¶
| Symbol | Description |
|---|---|
| n | Size of the AEAD block cipher (in bits) |
| t | Size of the authentication tag (in bits) |
| l | Length of each message (in blocks) |
| s | Total plaintext length in all messages (in blocks) |
| q | Number of encryption attempts |
| v | Number of forgery attempts |
| p | Adversary attack probability |
For each AEAD algorithm, we define the confidentiality and integrity advantage roughly as the advantage an attacker has in breaking the corresponding security property for the algorithm. Specifically:¶
Each application requires a different application 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. See [TLS], Section 5.5.¶
Once an upper bound on CA and IA are determined, this document defines a process for determining two overall limits:¶
For an AEAD based on a block function, it is common for these limits to be expressed instead in terms of the number of blocks rather than bytes. Furthermore, it might be more appropriate to track the number of messages rather than track bytes. Therefore, the guidance is usually based on the total number of blocks processed (s). To aid in calculating limits for message-based protocols, a formulation of limits that includes a maximum message size (l) is included.¶
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 a confidentiality advantage of v * (8l / 2^106) and attacker
success probability of p, the algorithm remains secure, i.e., the adversary's
advantage does not exceed the probability of success, provided that
v <= (p * 2^106) / 8l. In turn, this implies that v <= (p * 2^106) / 8l
is the corresponding limit.¶
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 CL and IL values bound the total number of encryption and forgery queries (q and v). Alongside each value, we also specify these bounds.¶
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, as described in [GCMProofs].¶
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, produces the limit:¶
q <= (p^(1/2) * 2^(129/2) - 1) / (l + 1)¶
IA = 2 * (v * (l + 1)) / 2^128¶
This implies the following limit:¶
v <= (p * 2^127) / (l + 1)¶
The only known analysis for AEAD_CHACHA20_POLY1305 [ChaCha20Poly1305Bounds] combines the confidentiality and integrity limits into a single expression, covered below:¶
CA = IA = v * (8l / 2^106)¶
This advantage is a tight reduction based on the underlying Poly1305 PRF [Poly1305]. It implies the following limit:¶
v <= (p * 2^106) / 8l¶
The CL and IL values for AEAD_AES_128_CCM are derived from [CCM-ANALYSIS] and specified in the QUIC-TLS mapping specification [I-D.ietf-quic-tls]. 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.¶
CA = (2l * q)^2 / 2^n = (2l * q)^2 / 2^128¶
This implies the following limit:¶
q <= sqrt((p * (2^127)) / l^2)¶
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 <= p^(1/2) * 2^63 / l¶
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¶
Many of the formulae in this document depend on simplifying assumptions that 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.¶
This document does not make any request of IANA.¶