idnits 2.17.1 draft-irtf-cfrg-aead-limits-04.txt: -(2): Line appears to be too long, but this could be caused by non-ascii characters in UTF-8 encoding Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == There are 3 instances of lines with non-ascii characters in the document. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (7 March 2022) is 781 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Obsolete informational reference (is this intentional?): RFC 5246 (Obsoleted by RFC 8446) Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group F. Günther 3 Internet-Draft ETH Zurich 4 Intended status: Informational M. Thomson 5 Expires: 8 September 2022 Mozilla 6 C. A. Wood 7 Cloudflare 8 7 March 2022 10 Usage Limits on AEAD Algorithms 11 draft-irtf-cfrg-aead-limits-04 13 Abstract 15 An Authenticated Encryption with Associated Data (AEAD) algorithm 16 provides confidentiality and integrity. Excessive use of the same 17 key can give an attacker advantages in breaking these properties. 18 This document provides simple guidance for users of common AEAD 19 functions about how to limit the use of keys in order to bound the 20 advantage given to an attacker. It considers limits in both single- 21 and multi-key settings. 23 Discussion Venues 25 This note is to be removed before publishing as an RFC. 27 Discussion of this document takes place on the Crypto Forum Research 28 Group mailing list (cfrg@ietf.org), which is archived at 29 https://mailarchive.ietf.org/arch/search/?email_list=cfrg. 31 Source for this draft and an issue tracker can be found at 32 https://github.com/cfrg/draft-irtf-cfrg-aead-limits. 34 Status of This Memo 36 This Internet-Draft is submitted in full conformance with the 37 provisions of BCP 78 and BCP 79. 39 Internet-Drafts are working documents of the Internet Engineering 40 Task Force (IETF). Note that other groups may also distribute 41 working documents as Internet-Drafts. The list of current Internet- 42 Drafts is at https://datatracker.ietf.org/drafts/current/. 44 Internet-Drafts are draft documents valid for a maximum of six months 45 and may be updated, replaced, or obsoleted by other documents at any 46 time. It is inappropriate to use Internet-Drafts as reference 47 material or to cite them other than as "work in progress." 48 This Internet-Draft will expire on 8 September 2022. 50 Copyright Notice 52 Copyright (c) 2022 IETF Trust and the persons identified as the 53 document authors. All rights reserved. 55 This document is subject to BCP 78 and the IETF Trust's Legal 56 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 57 license-info) in effect on the date of publication of this document. 58 Please review these documents carefully, as they describe your rights 59 and restrictions with respect to this document. Code Components 60 extracted from this document must include Revised BSD License text as 61 described in Section 4.e of the Trust Legal Provisions and are 62 provided without warranty as described in the Revised BSD License. 64 Table of Contents 66 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 67 2. Requirements Notation . . . . . . . . . . . . . . . . . . . . 4 68 3. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 4 69 4. Calculating Limits . . . . . . . . . . . . . . . . . . . . . 6 70 5. Single-Key AEAD Limits . . . . . . . . . . . . . . . . . . . 8 71 5.1. AEAD_AES_128_GCM and AEAD_AES_256_GCM . . . . . . . . . . 8 72 5.1.1. Confidentiality Limit . . . . . . . . . . . . . . . . 8 73 5.1.2. Integrity Limit . . . . . . . . . . . . . . . . . . . 8 74 5.2. AEAD_CHACHA20_POLY1305 . . . . . . . . . . . . . . . . . 9 75 5.3. AEAD_AES_128_CCM . . . . . . . . . . . . . . . . . . . . 9 76 5.3.1. Confidentiality Limit . . . . . . . . . . . . . . . . 9 77 5.3.2. Integrity Limit . . . . . . . . . . . . . . . . . . . 10 78 5.4. AEAD_AES_128_CCM_8 . . . . . . . . . . . . . . . . . . . 10 79 5.5. Single-Key Examples . . . . . . . . . . . . . . . . . . . 10 80 6. Multi-Key AEAD Limits . . . . . . . . . . . . . . . . . . . . 11 81 6.1. AEAD_AES_128_GCM and AEAD_AES_256_GCM . . . . . . . . . . 12 82 6.1.1. Authenticated Encryption Security Limit . . . . . . . 12 83 6.1.2. Confidentiality Limit . . . . . . . . . . . . . . . . 13 84 6.1.3. Integrity Limit . . . . . . . . . . . . . . . . . . . 13 85 6.2. AEAD_CHACHA20_POLY1305 . . . . . . . . . . . . . . . . . 13 86 6.2.1. Authenticated Encryption Security Limit . . . . . . . 13 87 6.2.2. Confidentiality Limit . . . . . . . . . . . . . . . . 14 88 6.2.3. Integrity Limit . . . . . . . . . . . . . . . . . . . 14 89 6.3. AEAD_AES_128_CCM and AEAD_AES_128_CCM_8 . . . . . . . . . 14 90 6.4. Multi-Key Examples . . . . . . . . . . . . . . . . . . . 15 91 7. Security Considerations . . . . . . . . . . . . . . . . . . . 16 92 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16 93 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 16 94 9.1. Normative References . . . . . . . . . . . . . . . . . . 16 95 9.2. Informative References . . . . . . . . . . . . . . . . . 18 97 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 19 99 1. Introduction 101 An Authenticated Encryption with Associated Data (AEAD) algorithm 102 provides confidentiality and integrity. [RFC5116] specifies an AEAD 103 as a function with four inputs -- secret key, nonce, plaintext, 104 associated data (of which plaintext and associated data can 105 optionally be zero-length) -- that produces ciphertext output and an 106 error code indicating success or failure. The ciphertext is 107 typically composed of the encrypted plaintext bytes and an 108 authentication tag. 110 The generic AEAD interface does not describe usage limits. Each AEAD 111 algorithm does describe limits on its inputs, but these are 112 formulated as strict functional limits, such as the maximum length of 113 inputs, which are determined by the properties of the underlying AEAD 114 composition. Degradation of the security of the AEAD as a single key 115 is used multiple times is not given the same thorough treatment. 117 Effective limits can be influenced by the number of "users" of a 118 given key. In the traditional setting, there is one key shared 119 between two parties. Any limits on the maximum length of inputs or 120 encryption operations apply to that single key. The attacker's goal 121 is to break security (confidentiality or integrity) of that specific 122 key. However, in practice, there are often many users with 123 independent keys. This multi-key security setting, often referred to 124 as the multi-user setting in the academic literature, considers an 125 attacker's advantage in breaking security of any of these many keys, 126 further assuming the attacker may have done some offline work to help 127 break security. As a result, AEAD algorithm limits may depend on 128 offline work and the number of keys. However, given that a multi-key 129 attacker does not target any specific key, acceptable advantages may 130 differ from that of the single-key setting. 132 The number of times a single pair of key and nonce can be used might 133 also be relevant to security. For some algorithms, such as 134 AEAD_AES_128_GCM or AEAD_AES_256_GCM, this limit is 1 and using the 135 same pair of key and nonce has serious consequences for both 136 confidentiality and integrity; see [NonceDisrespecting]. Nonce-reuse 137 resistant algorithms like AEAD_AES_128_GCM_SIV can tolerate a limited 138 amount of nonce reuse. 140 It is good practice to have limits on how many times the same key (or 141 pair of key and nonce) are used. Setting a limit based on some 142 measurable property of the usage, such as number of protected 143 messages or amount of data transferred, ensures that it is easy to 144 apply limits. This might require the application of simplifying 145 assumptions. For example, TLS 1.3 and QUIC both specify limits on 146 the number of records that can be protected, using the simplifying 147 assumption that records are the same size; see Section 5.5 of [TLS] 148 and Section 6.6 of [RFC9001]. 150 Exceeding the determined usage limit can be avoided using rekeying. 151 Rekeying uses a lightweight transform to produce new keys. Rekeying 152 effectively resets progress toward single-key limits, allowing a 153 session to be extended without degrading security. Rekeying can also 154 provide a measure of forward and backward (post-compromise) security. 155 [RFC8645] contains a thorough survey of rekeying and the consequences 156 of different design choices. 158 Currently, AEAD limits and usage requirements are scattered among 159 peer-reviewed papers, standards documents, and other RFCs. 160 Determining the correct limits for a given setting is challenging as 161 papers do not use consistent labels or conventions, and rarely apply 162 any simplifications that might aid in reaching a simple limit. 164 The intent of this document is to collate all relevant information 165 about the proper usage and limits of AEAD algorithms in one place. 166 This may serve as a standard reference when considering which AEAD 167 algorithm to use, and how to use it. 169 2. Requirements Notation 171 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 172 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 173 "OPTIONAL" in this document are to be interpreted as described in 174 BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all 175 capitals, as shown here. 177 3. Notation 179 This document defines limitations in part using the quantities in 180 Table 1 below. 182 +========+====================================================+ 183 | Symbol | Description | 184 +========+====================================================+ 185 | n | AEAD block length (in bits) | 186 +--------+----------------------------------------------------+ 187 | k | AEAD key length (in bits) | 188 +--------+----------------------------------------------------+ 189 | r | AEAD nonce length (in bits) | 190 +--------+----------------------------------------------------+ 191 | t | Size of the authentication tag (in bits) | 192 +--------+----------------------------------------------------+ 193 | l | Maximum length of each message (in blocks) | 194 +--------+----------------------------------------------------+ 195 | s | Total plaintext length in all messages (in blocks) | 196 +--------+----------------------------------------------------+ 197 | q | Number of protected messages (AEAD encryption | 198 | | invocations) | 199 +--------+----------------------------------------------------+ 200 | v | Number of attacker forgery attempts (failed AEAD | 201 | | decryption invocations) | 202 +--------+----------------------------------------------------+ 203 | p | Upper bound on adversary attack probability | 204 +--------+----------------------------------------------------+ 205 | o | Offline adversary work (in number of encryption | 206 | | and decryption queries; multi-key setting only) | 207 +--------+----------------------------------------------------+ 208 | u | Number of keys (multi-key setting only) | 209 +--------+----------------------------------------------------+ 210 | B | Maximum number of blocks encrypted by any key | 211 | | (multi-key setting only) | 212 +--------+----------------------------------------------------+ 214 Table 1: Notation 216 For each AEAD algorithm, we define the (passive) confidentiality and 217 (active) integrity advantage roughly as the advantage an attacker has 218 in breaking the corresponding classical security property for the 219 algorithm. A passive attacker can query ciphertexts for arbitrary 220 plaintexts. An active attacker can additionally query plaintexts for 221 arbitrary ciphertexts. Moreover, we define the combined 222 authenticated encryption advantage guaranteeing both confidentiality 223 and integrity against an active attacker. Specifically: 225 * Confidentiality advantage (CA): The probability of a passive 226 attacker succeeding in breaking the confidentiality properties 227 (IND-CPA) of the AEAD scheme. In this document, the definition of 228 confidentiality advantage roughly is the probability that an 229 attacker successfully distinguishes the ciphertext outputs of the 230 AEAD scheme from the outputs of a random function. 232 * Integrity advantage (IA): The probability of an active attacker 233 succeeding in breaking the integrity properties (INT-CTXT) of the 234 AEAD scheme. In this document, the definition of integrity 235 advantage roughly is the probability that an attacker is able to 236 forge a ciphertext that will be accepted as valid. 238 * Authenticated Encryption advantage (AEA): The probability of an 239 active attacker succeeding in breaking the authenticated- 240 encryption properties of the AEAD scheme. In this document, the 241 definition of authenticated encryption advantage roughly is the 242 probability that an attacker successfully distinguishes the 243 ciphertext outputs of the AEAD scheme from the outputs of a random 244 function or is able to forge a ciphertext that will be accepted as 245 valid. 247 See [AEComposition], [AEAD] for the formal definitions of and 248 relations between passive confidentiality (IND-CPA), ciphertext 249 integrity (INT-CTXT), and authenticated encryption security (AE). 250 The authenticated encryption advantage subsumes, and can be derived 251 as the combination of, both CA and IA: 253 CA <= AEA 254 IA <= AEA 255 AEA <= CA + IA 257 Each application requires an individual determination of limits in 258 order to keep CA and IA sufficiently small. For instance, TLS aims 259 to keep CA below 2^-60 and IA below 2^-57 in the single-key setting; 260 see Section 5.5 of [TLS]. 262 4. Calculating Limits 264 Once upper bounds on CA, IA, or AEA are determined, this document 265 defines a process for determining three overall operational limits: 267 * Confidentiality limit (CL): The number of messages an application 268 can encrypt before giving the adversary a confidentiality 269 advantage higher than CA. 271 * Integrity limit (IL): The number ciphertexts an application can 272 decrypt, either successfully or not, before giving the adversary 273 an integrity advantage higher than IA. 275 * Authenticated encryption limit (AEL): The combined number of 276 messages and number of ciphertexts an application can encrypt or 277 decrypt before giving the adversary an authenticated encryption 278 advantage higher than AEA. 280 When limits are expressed as a number of messages an application can 281 encrypt or decrypt, this requires assumptions about the size of 282 messages and any authenticated additional data (AAD). Limits can 283 instead be expressed in terms of the number of bytes, or blocks, of 284 plaintext and maybe AAD in total. 286 To aid in translating between message-based and byte/block-based 287 limits, a formulation of limits that includes a maximum message size 288 (l) and the AEAD schemes' block length in bits (n) is provided. 290 All limits are based on the total number of messages, either the 291 number of protected messages (q) or the number of forgery attempts 292 (v); which correspond to CL and IL respectively. 294 Limits are then derived from those bounds using a target attacker 295 probability. For example, given an integrity advantage of IA = v * 296 (8l / 2^106) and a targeted maximum attacker success probability of 297 IA = p, the algorithm remains secure, i.e., the adversary's advantage 298 does not exceed the targeted probability of success, provided that v 299 <= (p * 2^106) / 8l. In turn, this implies that v <= (p * 2^103) / l 300 is the corresponding limit. 302 To apply these limits, implementations can count the number of 303 messages that are protected or rejected against the determined limits 304 (q and v respectively). This requires that messages cannot exceed 305 the maximum message size (l) that is chosen. 307 This analysis assumes a message-based approach to setting limits. 308 Implementations that use byte counting rather than message counting 309 could use a maximum message size (l) of one to determine a limit for 310 q that can be applied with byte counting. This results in 311 attributing per-message overheads to every byte, so the resulting 312 limit could be significantly lower than necessary. Actions, like 313 rekeying, that are taken to avoid the limit might occur more often as 314 a result. 316 5. Single-Key AEAD Limits 318 This section summarizes the confidentiality and integrity bounds and 319 limits for modern AEAD algorithms used in IETF protocols, including: 320 AEAD_AES_128_GCM [RFC5116], AEAD_AES_256_GCM [RFC5116], 321 AEAD_AES_128_CCM [RFC5116], AEAD_CHACHA20_POLY1305 [RFC8439], 322 AEAD_AES_128_CCM_8 [RFC6655]. The limits in this section apply to 323 using these schemes with a single key; for settings where multiple 324 keys are deployed (for example, when rekeying within a connection), 325 see Section 6. 327 These algorithms, as cited, all define a nonce length (r) of 96 bits. 328 Some definitions of these AEAD algorithms allow for other nonce 329 lengths, but the analyses in this document all fix the nonce length 330 to r = 96. Using other nonce lengths might result in different 331 bounds; for example, [GCMProofs] shows that using a variable-length 332 nonce for AES-GCM results in worse security bounds. 334 The CL and IL values bound the total number of encryption and forgery 335 queries (q and v). Alongside each advantage value, we also specify 336 these bounds. 338 5.1. AEAD_AES_128_GCM and AEAD_AES_256_GCM 340 The CL and IL values for AES-GCM are derived in [AEBounds] and 341 summarized below. For this AEAD, n = 128 and t = 128 [GCM]. In this 342 example, the length s is the sum of AAD and plaintext (in blocks of 343 128 bits), as described in [GCMProofs]. 345 5.1.1. Confidentiality Limit 347 CA <= ((s + q + 1)^2) / 2^129 349 This implies the following usage limit: 351 q + s <= p^(1/2) * 2^(129/2) - 1 353 Which, for a message-based protocol with s <= q * l, if we assume 354 that every packet is size l (in blocks of 128 bits), produces the 355 limit: 357 q <= (p^(1/2) * 2^(129/2) - 1) / (l + 1) 359 5.1.2. Integrity Limit 361 IA <= 2 * (v * (l + 1)) / 2^128 363 This implies the following limit: 365 v <= (p * 2^127) / (l + 1) 367 5.2. AEAD_CHACHA20_POLY1305 369 The known single-user analyses for AEAD_CHACHA20_POLY1305 370 [ChaCha20Poly1305-SU], [ChaCha20Poly1305-MU] combine the 371 confidentiality and integrity limits into a single expression, 372 covered below. For this AEAD, n = 512, k = 256, and t = 128; the 373 length l is the sum of AAD and plaintext (in blocks of 128 bits), see 374 [ChaCha20Poly1305-MU]. 376 AEA <= (v * (l + 1)) / 2^103 378 This advantage is a tight reduction based on the underlying Poly1305 379 PRF [Poly1305]. It implies the following limit: 381 v <= (p * 2^103) / (l + 1) 383 5.3. AEAD_AES_128_CCM 385 The CL and IL values for AEAD_AES_128_CCM are derived from 386 [CCM-ANALYSIS] and specified in the QUIC-TLS mapping specification 387 [RFC9001]. This analysis uses the total number of underlying block 388 cipher operations to derive its bound. For CCM, this number is the 389 sum of: the length of the associated data in blocks, the length of 390 the ciphertext in blocks, the length of the plaintext in blocks, plus 391 1. 393 In the following limits, this is simplified to a value of twice the 394 length of the packet in blocks, i.e., 2l represents the effective 395 length, in number of block cipher operations, of a message with l 396 blocks. This simplification is based on the observation that common 397 applications of this AEAD carry only a small amount of associated 398 data compared to ciphertext. For example, QUIC has 1 to 3 blocks of 399 AAD. 401 For this AEAD, n = 128 and t = 128. 403 5.3.1. Confidentiality Limit 405 CA <= (2l * q)^2 / 2^n 406 <= (2l * q)^2 / 2^128 408 This implies the following limit: 410 q <= sqrt((p * 2^126) / l^2) 412 5.3.2. Integrity Limit 414 IA <= v / 2^t + (2l * (v + q))^2 / 2^n 415 <= v / 2^128 + (2l * (v + q))^2 / 2^128 417 This implies the following limit: 419 v + (2l * (v + q))^2 <= p * 2^128 421 In a setting where v or q is sufficiently large, v is negligible 422 compared to (2l * (v + q))^2, so this this can be simplified to: 424 v + q <= sqrt(p) * 2^63 / l 426 5.4. AEAD_AES_128_CCM_8 428 The analysis in [CCM-ANALYSIS] also applies to this AEAD, but the 429 reduced tag length of 64 bits changes the integrity limit calculation 430 considerably. 432 IA <= v / 2^t + (2l * (v + q))^2 / 2^n 433 <= v / 2^64 + (2l * (v + q))^2 / 2^128 435 This results in reducing the limit on v by a factor of 2^64. 437 v * 2^64 + (2l * (v + q))^2 <= p * 2^128 439 5.5. Single-Key Examples 441 An example protocol might choose to aim for a single-key CA and IA 442 that is at most 2^-50. If the messages exchanged in the protocol are 443 at most a common Internet MTU of around 1500 bytes, then a value for 444 l might be set to 2^7. Table 2 shows limits for q and v that might 445 be chosen under these conditions. 447 +========================+===========+===========+ 448 | AEAD | Maximum q | Maximum v | 449 +========================+===========+===========+ 450 | AEAD_AES_128_GCM | 2^32.5 | 2^71 | 451 +------------------------+-----------+-----------+ 452 | AEAD_AES_256_GCM | 2^32.5 | 2^71 | 453 +------------------------+-----------+-----------+ 454 | AEAD_CHACHA20_POLY1305 | n/a | 2^46 | 455 +------------------------+-----------+-----------+ 456 | AEAD_AES_128_CCM | 2^30 | 2^30 | 457 +------------------------+-----------+-----------+ 458 | AEAD_AES_128_CCM_8 | 2^30.9 | 2^13 | 459 +------------------------+-----------+-----------+ 461 Table 2: Example single-key limits 463 AEAD_CHACHA20_POLY1305 provides no limit to q based on the provided 464 single-user analyses. 466 The limit for q on AEAD_AES_128_CCM and AEAD_AES_128_CCM_8 is reduced 467 due to a need to reduce the value of q to ensure that IA does not 468 exceed the target. This assumes equal proportions for q and v for 469 AEAD_AES_128_CCM. AEAD_AES_128_CCM_8 permits a much smaller value of 470 v due to the shorter tag, which permits a higher limit for q. 472 Some protocols naturally limit v to 1, such as TCP-based variants of 473 TLS, which terminate sessions on decryption failure. If v is limited 474 to 1, q can be increased to 2^31 for both CCM AEADs. 476 6. Multi-Key AEAD Limits 478 In the multi-key setting, each user is assumed to have an independent 479 and uniformly distributed key, though nonces may be re-used across 480 users with some very small probability. The success probability in 481 attacking one of these many independent keys can be generically 482 bounded by the success probability of attacking a single key 483 multiplied by the number of keys present [MUSecurity], [GCM-MU]. 484 Absent concrete multi-key bounds, this means the attacker advantage 485 in the multi-key setting is the product of the single-key advantage 486 and the number of keys. 488 This section summarizes the confidentiality and integrity bounds and 489 limits for the same algorithms as in Section 5 for the multi-key 490 setting. The CL and IL values bound the total number of encryption 491 and forgery queries (q and v). Alongside each value, we also specify 492 these bounds. 494 6.1. AEAD_AES_128_GCM and AEAD_AES_256_GCM 496 Concrete multi-key bounds for AEAD_AES_128_GCM and AEAD_AES_256_GCM 497 exist due to Theorem 4.3 in [GCM-MU2], which covers protocols with 498 nonce randomization, like TLS 1.3 [TLS] and QUIC [RFC9001]. Here, 499 the full nonce is XORed with a secret, random offset. The bound for 500 nonce randomization was further improved in [ChaCha20Poly1305-MU]. 502 Results for AES-GCM with random, partially implicit nonces [RFC5288] 503 are captured by Theorem 5.3 in [GCM-MU2], which apply to protocols 504 such as TLS 1.2 [RFC5246]. Here, the implicit part of the nonce is a 505 random value, of length at least 32 bits and fixed per key, while the 506 explicit part of the nonce is a non-repeating counter. The full 507 nonce is the concatenation of the two parts. This produces similar 508 limits under most conditions. 510 For this AEAD, n = 128, t = 128, and r = 96; the key length is k = 511 128 or k = 256 for AEAD_AES_128_GCM and AEAD_AES_128_GCM 512 respectively. 514 6.1.1. Authenticated Encryption Security Limit 516 Protocols with nonce randomization have a limit of: 518 AEA <= (q+v)*l*B / 2^127 520 This implies the following limit: 522 q + v <= p * 2^127 / (l * B) 524 This assumes that B is much larger than 100; that is, each user 525 enciphers significantly more than 1600 bytes of data. Otherwise, B 526 should be increased by 161 for AEAD_AES_128_GCM and by 97 for 527 AEAD_AES_256_GCM. 529 Protocols with random, partially implicit nonces have the following 530 limit, which is similar to that for nonce randomization: 532 AEA <= (((q+v)*o + (q+v)^2) / 2^(k+26)) + ((q+v)*l*B / 2^127) 534 The first term is negligible if k = 256; this implies the following 535 simplified limits: 537 AEA <= (q+v)*l*B / 2^127 538 q + v <= p * 2^127 / (l * B) 539 For k = 128, assuming o <= q+v (i.e., that the attacker does not 540 spend more work than all legitimate protocol users together), the 541 limits are: 543 AEA <= (((q+v)*o + (q+v)^2) / 2^154) + ((q+v)*l*B / 2^127) 544 q + v <= min( sqrt(p) * 2^76, p * 2^126 / (l * B) ) 546 6.1.2. Confidentiality Limit 548 The confidentiality advantage is essentially dominated by the same 549 term as the AE advantage for protocols with nonce randomization: 551 CA <= q*l*B / 2^127 553 This implies the following limit: 555 q <= p * 2^127 / (l * B) 557 Similarly, the limits for protocols with random, partially implicit 558 nonces are: 560 CA <= ((q*o + q^2) / 2^(k+26)) + (q*l*B / 2^127) 561 q <= min( sqrt(p) * 2^76, p * 2^126 / (l * B) ) 563 6.1.3. Integrity Limit 565 There is currently no dedicated integrity multi-key bound available 566 for AEAD_AES_128_GCM and AEAD_AES_256_GCM. The AE limit can be used 567 to derive an integrity limit as: 569 IA <= AEA 571 Section 6.1.1 therefore contains the integrity limits. 573 6.2. AEAD_CHACHA20_POLY1305 575 Concrete multi-key bounds for AEAD_CHACHA20_POLY1305 are given in 576 Theorem 7.8 in [ChaCha20Poly1305-MU], covering protocols with nonce 577 randomization like TLS 1.3 [TLS] and QUIC [RFC9001]. 579 For this AEAD, n = 512, k = 256, t = 128, and r = 96; the length l is 580 the sum of AAD and plaintext (in blocks of 128 bits). 582 6.2.1. Authenticated Encryption Security Limit 584 Protocols with nonce randomization have a limit of: 586 AEA <= (v * (l + 1)) / 2^103 587 It implies the following limit: 589 v <= (p * 2^103) / (l + 1) 591 Note that this is the same limit as in the single-user case except 592 that the total number of forgery attempts v and maximum message 593 length in blocks l is calculated across all used keys. 595 6.2.2. Confidentiality Limit 597 While the AE advantage is dominated by the number of forgery attempts 598 v, those are irrelevant for the confidentiality advantage. The 599 relevant limit for protocols with nonce randomization becomes 600 dominated, at a very low level, by the adversary's offline work o, 601 number of protected messages q and maximum blocks encrypted B, across 602 all used keys: 604 CA <= ((o + q) / 2^247) + ((B + q)^2 / 2^513) 606 It implies the following simplified limit, which for most reasonable 607 values of p is dominated by a technical limitation around q = 2^100: 609 q <= min( p * 2^246 - o, sqrt(p) * 2^256 - B, 2^100 ) 611 6.2.3. Integrity Limit 613 The AE limit for AEAD_CHACHA20_POLY1305 essentially is the integrity 614 (multi-key) bound. The former hence also applies to the latter: 616 IA <= AEA 618 Section 6.2.1 therefore contains the integrity limits. 620 6.3. AEAD_AES_128_CCM and AEAD_AES_128_CCM_8 622 There are currently no concrete multi-key bounds for AEAD_AES_128_CCM 623 or AEAD_AES_128_CCM_8. Thus, to account for the additional factor u, 624 i.e., the number of keys, each p term in the confidentiality and 625 integrity limits is replaced with p / u. 627 The multi-key integrity limit for AEAD_AES_128_CCM is as follows. 629 v + q <= sqrt(p / u) * 2^63 / l 631 Likewise, the multi-key integrity limit for AEAD_AES_128_CCM_8 is as 632 follows. 634 v * 2^64 + (2l * (v + q))^2 <= (p / u) * 2^128 636 6.4. Multi-Key Examples 638 An example protocol might choose to aim for a multi-key AEA, CA, and 639 IA that is at most 2^-50. If the messages exchanged in the protocol 640 are at most a common Internet MTU of around 1500 bytes, then a value 641 for l might be set to 2^7. Table 3 shows limits for q and v across 642 all keys that might be chosen under these conditions. 644 +========================+================+==============+ 645 | AEAD | Maximum q | Maximum v | 646 +========================+================+==============+ 647 | AEAD_AES_128_GCM | 2^69/B | 2^69/B | 648 +------------------------+----------------+--------------+ 649 | AEAD_AES_256_GCM | 2^69/B | 2^69/B | 650 +------------------------+----------------+--------------+ 651 | AEAD_CHACHA20_POLY1305 | 2^100 | 2^46 | 652 +------------------------+----------------+--------------+ 653 | AEAD_AES_128_CCM | 2^30/sqrt(u) | 2^30/sqrt(u) | 654 +------------------------+----------------+--------------+ 655 | AEAD_AES_128_CCM_8 | 2^30.9/sqrt(u) | 2^13/u | 656 +------------------------+----------------+--------------+ 658 Table 3: Example multi-key limits 660 The limits for AEAD_AES_128_GCM, AEAD_AES_256_GCM, AEAD_AES_128_CCM, 661 and AEAD_AES_128_CCM_8 assume equal proportions for q and v. The 662 limits for AEAD_AES_128_GCM, AEAD_AES_256_GCM and 663 AEAD_CHACHA20_POLY1305 assume the use of nonce randomization, like in 664 TLS 1.3 [TLS] and QUIC [RFC9001]. 666 The limits for AEAD_AES_128_GCM and AEAD_AES_256_GCM further depend 667 on the maximum number B of 128-bit blocks encrypted by any single 668 key. For example, limiting the number of messages (of size <= 2^7 669 blocks) to at most 2^20 (about a million) per key results in B = 670 2^27, which limits both q and v to 2^42 messages. 672 Only the limits for AEAD_AES_128_CCM and AEAD_AES_128_CCM_8 depend on 673 the number of used keys u, which further reduces them considerably. 674 If v is limited to 1, q can be increased to 2^31/sqrt(u) for both CCM 675 AEADs. 677 7. Security Considerations 679 The different analyses of AEAD functions that this work is based upon 680 generally assume that the underlying primitives are ideal. For 681 example, that a pseudorandom function (PRF) used by the AEAD is 682 indistinguishable from a truly random function or that a pseudorandom 683 permutation (PRP) is indistinguishable from a truly random 684 permutation. Thus, the advantage estimates assume that the attacker 685 is not able to exploit a weakness in an underlying primitive. 687 Many of the formulae in this document depend on simplifying 688 assumptions, from differing models, which means that results are not 689 universally applicable. When using this document to set limits, it 690 is necessary to validate all these assumptions for the setting in 691 which the limits might apply. In most cases, the goal is to use 692 assumptions that result in setting a more conservative limit, but 693 this is not always the case. As an example of one such 694 simplification, this document defines v as the total number of failed 695 decryption queries (that is, failed forgery attempts), whereas models 696 usually count in v all forgery attempts. 698 The CA, IA, and AEA values defined in this document are upper bounds 699 based on existing cryptographic research. Future analysis may 700 introduce tighter bounds. Applications SHOULD NOT assume these 701 bounds are rigid, and SHOULD accommodate changes. In particular, in 702 two-party communication, one participant cannot regard apparent 703 overuse of a key by other participants as being in error, when it 704 could be that the other participant has better information about 705 bounds. 707 Note that the limits in this document apply to the adversary's 708 ability to conduct a single successful forgery. For some algorithms 709 and in some cases, an adversary's success probability in repeating 710 forgeries may be noticeably larger than that of the first forgery. 711 As an example, [MF05] describes such multiple forgery attacks in the 712 context of AES-GCM in more detail. 714 8. IANA Considerations 716 This document does not make any request of IANA. 718 9. References 720 9.1. Normative References 722 [AEAD] Rogaway, P., "Authenticated-Encryption with Associated- 723 Data", September 2002, 724 . 726 [AEBounds] Luykx, A. and K. Paterson, "Limits on Authenticated 727 Encryption Use in TLS", 8 March 2016, 728 . 730 [AEComposition] 731 Bellare, M. and C. Namprempre, "Authenticated Encryption: 732 Relations among notions and analysis of the generic 733 composition paradigm", July 2007, 734 . 736 [CCM-ANALYSIS] 737 Jonsson, J., "On the Security of CTR + CBC-MAC", Selected 738 Areas in Cryptography pp. 76-93, 739 DOI 10.1007/3-540-36492-7_7, 2003, 740 . 742 [ChaCha20Poly1305-MU] 743 Degabriele, J., Govinden, J., Günther, F., and K. 744 Paterson, "The Security of ChaCha20-Poly1305 in the Multi- 745 User Setting", Proceedings of the 2021 ACM SIGSAC 746 Conference on Computer and Communications Security, 747 DOI 10.1145/3460120.3484814, November 2021, 748 . 750 [ChaCha20Poly1305-SU] 751 Procter, G., "A Security Analysis of the Composition of 752 ChaCha20 and Poly1305", 11 August 2014, 753 . 755 [GCM] Dworkin, M., "Recommendation for Block Cipher Modes of 756 Operation: Galois/Counter Mode (GCM) and GMAC", 757 NIST Special Publication 800-38D, November 2007. 759 [GCM-MU] Bellare, M. and B. Tackmann, "The Multi-User Security of 760 Authenticated Encryption: AES-GCM in TLS 1.3", 27 November 761 2017, . 763 [GCM-MU2] Hoang, V. T., Tessaro, S., and A. Thiruvengadam, "The 764 Multi-user Security of GCM, Revisited: Tight Bounds for 765 Nonce Randomization", 15 October 2018, 766 . 768 [GCMProofs] 769 Iwata, T., Ohashi, K., and K. Minematsu, "Breaking and 770 Repairing GCM Security Proofs", 1 August 2012, 771 . 773 [MUSecurity] 774 Bellare, M., Boldyreva, A., and S. Micali, "Public-Key 775 Encryption in a Multi-user Setting: Security Proofs and 776 Improvements", May 2000, 777 . 779 [Poly1305] Bernstein, D., "The Poly1305-AES Message-Authentication 780 Code", Fast Software Encryption pp. 32-49, 781 DOI 10.1007/11502760_3, 2005, 782 . 784 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 785 Requirement Levels", BCP 14, RFC 2119, 786 DOI 10.17487/RFC2119, March 1997, 787 . 789 [RFC5116] McGrew, D., "An Interface and Algorithms for Authenticated 790 Encryption", RFC 5116, DOI 10.17487/RFC5116, January 2008, 791 . 793 [RFC6655] McGrew, D. and D. Bailey, "AES-CCM Cipher Suites for 794 Transport Layer Security (TLS)", RFC 6655, 795 DOI 10.17487/RFC6655, July 2012, 796 . 798 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 799 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 800 May 2017, . 802 [RFC8439] Nir, Y. and A. Langley, "ChaCha20 and Poly1305 for IETF 803 Protocols", RFC 8439, DOI 10.17487/RFC8439, June 2018, 804 . 806 9.2. Informative References 808 [MF05] McGrew, D. A. and S. R. Fluhrer, "Multiple forgery attacks 809 against Message Authentication Codes", 31 May 2005, 810 . 814 [NonceDisrespecting] 815 Bock, H., Zauner, A., Devlin, S., Somorovsky, J., and P. 816 Jovanovic, "Nonce-Disrespecting Adversaries -- Practical 817 Forgery Attacks on GCM in TLS", 17 May 2016, 818 . 820 [RFC5246] Dierks, T. and E. Rescorla, "The Transport Layer Security 821 (TLS) Protocol Version 1.2", RFC 5246, 822 DOI 10.17487/RFC5246, August 2008, 823 . 825 [RFC5288] Salowey, J., Choudhury, A., and D. McGrew, "AES Galois 826 Counter Mode (GCM) Cipher Suites for TLS", RFC 5288, 827 DOI 10.17487/RFC5288, August 2008, 828 . 830 [RFC8645] Smyshlyaev, S., Ed., "Re-keying Mechanisms for Symmetric 831 Keys", RFC 8645, DOI 10.17487/RFC8645, August 2019, 832 . 834 [RFC9001] Thomson, M., Ed. and S. Turner, Ed., "Using TLS to Secure 835 QUIC", RFC 9001, DOI 10.17487/RFC9001, May 2021, 836 . 838 [TLS] Rescorla, E., "The Transport Layer Security (TLS) Protocol 839 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 840 . 842 Authors' Addresses 844 Felix Günther 845 ETH Zurich 846 Email: mail@felixguenther.info 848 Martin Thomson 849 Mozilla 850 Email: mt@lowentropy.net 852 Christopher A. Wood 853 Cloudflare 854 Email: caw@heapingbits.net