Network Working Group F. Günther
Internet-Draft ETH Zurich
Intended status: Informational M. Thomson
Expires: 24 March 2021 Mozilla
C.A. Wood
Cloudflare
20 September 2020
Usage Limits on AEAD Algorithms
draft-irtf-cfrg-aead-limits-01
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-user settings.
Discussion Venues
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
(https://github.com/chris-wood/draft-wood-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."
This Internet-Draft will expire on 24 March 2021.
Günther, et al. Expires 24 March 2021 [Page 1]
Internet-Draft AEAD Limits September 2020
Copyright Notice
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.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements Notation . . . . . . . . . . . . . . . . . . . . 4
3. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4. Calculating Limits . . . . . . . . . . . . . . . . . . . . . 6
5. Single-User AEAD Limits . . . . . . . . . . . . . . . . . . . 7
5.1. AEAD_AES_128_GCM and AEAD_AES_256_GCM . . . . . . . . . . 7
5.1.1. Confidentiality Limit . . . . . . . . . . . . . . . . 7
5.1.2. Integrity Limit . . . . . . . . . . . . . . . . . . . 8
5.2. AEAD_CHACHA20_POLY1305 . . . . . . . . . . . . . . . . . 8
5.3. AEAD_AES_128_CCM . . . . . . . . . . . . . . . . . . . . 8
5.3.1. Confidentiality Limit . . . . . . . . . . . . . . . . 9
5.3.2. Integrity Limit . . . . . . . . . . . . . . . . . . . 9
5.4. AEAD_AES_128_CCM_8 . . . . . . . . . . . . . . . . . . . 9
6. Multi-User AEAD Limits . . . . . . . . . . . . . . . . . . . 9
6.1. AEAD_AES_128_GCM and AEAD_AES_256_GCM . . . . . . . . . . 10
6.1.1. Authenticated Encryption Security Limit . . . . . . . 10
6.1.2. Confidentiality Limit . . . . . . . . . . . . . . . . 10
6.1.3. Integrity Limit . . . . . . . . . . . . . . . . . . . 10
6.2. AEAD_CHACHA20_POLY1305, AEAD_AES_128_CCM, and
AEAD_AES_128_CCM_8 . . . . . . . . . . . . . . . . . . . 11
6.2.1. AEAD_CHACHA20_POLY1305 . . . . . . . . . . . . . . . 11
6.2.2. AEAD_AES_128_CCM and AEAD_AES_128_CCM_8 . . . . . . . 11
7. Security Considerations . . . . . . . . . . . . . . . . . . . 11
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 11
9.1. Normative References . . . . . . . . . . . . . . . . . . 11
9.2. Informative References . . . . . . . . . . . . . . . . . 13
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 14
Günther, et al. Expires 24 March 2021 [Page 2]
Internet-Draft AEAD Limits September 2020
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, 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.
These limits might also 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. The "multi-user" security setting hence 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 users. However, given that
a multi-user attacker does not target any specific user, acceptable
advantages may differ from that of the single-user 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
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].
Günther, et al. Expires 24 March 2021 [Page 3]
Internet-Draft AEAD Limits September 2020
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 below.
Günther, et al. Expires 24 March 2021 [Page 4]
Internet-Draft AEAD Limits September 2020
+========+====================================================+
| 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 | 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 | Adversary attack probability |
+--------+----------------------------------------------------+
| o | Offline adversary work (in number of encryption |
| | and decryption queries; multi-user setting only) |
+--------+----------------------------------------------------+
| u | Number of users or keys (multi-user setting only) |
+--------+----------------------------------------------------+
| B | Maximum number of blocks encrypted by any user or |
| | key (multi-user setting only) |
+--------+----------------------------------------------------+
Table 1
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. Moreover, we define the combined authenticated encryption
advantage guaranteeing both confidentiality and integrity against an
active attacker. Specifically:
* 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.
Günther, et al. Expires 24 March 2021 [Page 5]
Internet-Draft AEAD Limits September 2020
* Integrity advantage (IA): The probability of a 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 a
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-user
setting). See [TLS], Section 5.5.
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.
* 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.
Günther, et al. Expires 24 March 2021 [Page 6]
Internet-Draft AEAD Limits September 2020
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.
5. Single-User 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 CL and IL values bound the total number of encryption and forgery
queries (q and v). Alongside each 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, 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
Günther, et al. Expires 24 March 2021 [Page 7]
Internet-Draft AEAD Limits September 2020
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)
5.1.2. Integrity Limit
IA <= 2 * (v * (l + 1)) / 2^128
This implies the following limit:
v <= (p * 2^127) / (l + 1)
5.2. AEAD_CHACHA20_POLY1305
The only known analysis for AEAD_CHACHA20_POLY1305
[ChaCha20Poly1305Bounds] combines the confidentiality and integrity
limits into a single expression, covered below:
CA <= v * ((8 * l) / 2^106)
IA <= v * ((8 * l) / 2^106)
This advantage is a tight reduction based on the underlying Poly1305
PRF [Poly1305]. It implies the following limit:
v <= (p * 2^103) / l
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
[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.
Günther, et al. Expires 24 March 2021 [Page 8]
Internet-Draft AEAD Limits September 2020
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)
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 <= p^(1/2) * 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
6. Multi-User AEAD Limits
In the multi-user setting, each user is assumed to have an
independent and identically 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 user keys can
be generically bounded by the success probability of attacking a
single user multiplied by the number of users present [MUSecurity],
[GCM-MU]. Absent concrete multi-user bounds, this means the attacker
advantage in the multi-user setting is the product of the single-user
advantage and the number of users.
Günther, et al. Expires 24 March 2021 [Page 9]
Internet-Draft AEAD Limits September 2020
This section summarizes the confidentiality and integrity bounds and
limits for the same algorithms as in Section 5 for the multi-user
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.
6.1. AEAD_AES_128_GCM and AEAD_AES_256_GCM
Concrete multi-user bounds for AEAD_AES_128_GCM and AEAD_AES_256_GCM
exist due to [GCM-MU2]. AES-GCM without nonce randomization is also
discussed in [GCM-MU2], though this section does not include those
results as they do not apply to protocols such as TLS 1.3 [RFC8446].
For this AEAD, n = 128, t = 128, and r = 96; the key length is k =
128 or k = 256.
6.1.1. Authenticated Encryption Security Limit
AEA <= ((q+v)*l*B / 2^127) + (1 / 2^48)
This implies the following limit:
q + v <= (p * 2^127 - 2^79) / (l * B)
6.1.2. Confidentiality Limit
The confidentiality advantage is essentially dominated by the same
terms as the AE advantage:
CA <= (q*l*B / 2^127) + (1 / 2^48)
This implies the following limit:
q <= (p * 2^127 - 2^79) / (l * B)
6.1.3. Integrity Limit
There is currently no dedicated integrity multi-user 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 <= (q+v)*l*B / 2^127 + 1/2^48
This implies the following limit:
q + v <= (p * 2^127 - 2^79) / (l * B)
Günther, et al. Expires 24 March 2021 [Page 10]
Internet-Draft AEAD Limits September 2020
6.2. AEAD_CHACHA20_POLY1305, AEAD_AES_128_CCM, and AEAD_AES_128_CCM_8
There are currently no concrete multi-user bounds for
AEAD_CHACHA20_POLY1305, AEAD_AES_128_CCM, or AEAD_AES_128_CCM_8.
Thus, to account for the additional factor "u", i.e., the number of
users, each "p" term in the confidentiality and integrity limits is
replaced with "p / u".
6.2.1. AEAD_CHACHA20_POLY1305
The combined confidentiality and integrity limit for
AEAD_CHACHA20_POLY1305 is as follows.
v <= ((p / u) * 2^106) / 8l
<= (p * 2^103) / (l * u)
6.2.2. AEAD_AES_128_CCM and AEAD_AES_128_CCM_8
The integrity limit for AEAD_AES_128_CCM is as follows.
v + q <= (p / u)^(1/2) * 2^63 / l
Likewise, the integrity limit for AEAD_AES_128_CCM_8 is as follows.
v * 2^64 + (2l * (v + q))^2 <= (p / u) * 2^128
7. Security Considerations
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.
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,
.
Günther, et al. Expires 24 March 2021 [Page 11]
Internet-Draft AEAD Limits September 2020
[AEBounds] Luykx, A. and K. Paterson, "Limits on Authenticated
Encryption Use in TLS", 8 March 2016,
.
[AEComposition]
Bellare, M. and C. Namprempre, "Authenticated Encryption:
Relations among notions and analysis of the generic
composition paradigm", July 2007,
.
[CCM-ANALYSIS]
Jonsson, J., "On the Security of CTR + CBC-MAC",
DOI 10.1007/3-540-36492-7_7, Selected Areas in
Cryptography pp. 76-93, 2003,
.
[ChaCha20Poly1305Bounds]
Procter, G., "A Security Analysis of the Composition of
ChaCha20 and Poly1305", 11 August 2014,
.
[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, .
[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,
.
[GCMProofs]
Iwata, T., Ohashi, K., and K. Minematsu, "Breaking and
Repairing GCM Security Proofs", 1 August 2012,
.
[MUSecurity]
Bellare, M., Boldyreva, A., and S. Micali, "Public-Key
Encryption in a Multi-user Setting: Security Proofs and
Improvements", May 2000,
.
Günther, et al. Expires 24 March 2021 [Page 12]
Internet-Draft AEAD Limits September 2020
[Poly1305] Bernstein, D., "The Poly1305-AES Message-Authentication
Code", DOI 10.1007/11502760_3, Fast Software
Encryption pp. 32-49, 2005,
.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
.
[RFC5116] McGrew, D., "An Interface and Algorithms for Authenticated
Encryption", RFC 5116, DOI 10.17487/RFC5116, January 2008,
.
[RFC6655] McGrew, D. and D. Bailey, "AES-CCM Cipher Suites for
Transport Layer Security (TLS)", RFC 6655,
DOI 10.17487/RFC6655, July 2012,
.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, .
[RFC8439] Nir, Y. and A. Langley, "ChaCha20 and Poly1305 for IETF
Protocols", RFC 8439, DOI 10.17487/RFC8439, June 2018,
.
9.2. Informative References
[I-D.ietf-quic-tls]
Thomson, M. and S. Turner, "Using TLS to Secure QUIC",
Work in Progress, Internet-Draft, draft-ietf-quic-tls-30,
9 September 2020, .
[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,
.
[RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol
Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018,
.
[TLS] Rescorla, E., "The Transport Layer Security (TLS) Protocol
Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018,
.
Günther, et al. Expires 24 March 2021 [Page 13]
Internet-Draft AEAD Limits September 2020
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 24 March 2021 [Page 14]