idnits 2.17.1 draft-irtf-cfrg-aead-limits-00.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 2 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 doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (14 August 2020) is 1352 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-34) exists of draft-ietf-quic-tls-29 -- Duplicate reference: RFC8446, mentioned in 'TLS', was also mentioned in 'RFC8446'. Summary: 0 errors (**), 0 flaws (~~), 4 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: 15 February 2021 Mozilla 6 C.A. Wood 7 Cloudflare 8 14 August 2020 10 Usage Limits on AEAD Algorithms 11 draft-irtf-cfrg-aead-limits-00 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-user settings. 23 Discussion Venues 25 This note is to be removed before publishing as an RFC. 27 Source for this draft and an issue tracker can be found at 28 https://github.com/chris-wood/draft-wood-cfrg-aead-limits 29 (https://github.com/chris-wood/draft-wood-cfrg-aead-limits). 31 Status of This Memo 33 This Internet-Draft is submitted in full conformance with the 34 provisions of BCP 78 and BCP 79. 36 Internet-Drafts are working documents of the Internet Engineering 37 Task Force (IETF). Note that other groups may also distribute 38 working documents as Internet-Drafts. The list of current Internet- 39 Drafts is at https://datatracker.ietf.org/drafts/current/. 41 Internet-Drafts are draft documents valid for a maximum of six months 42 and may be updated, replaced, or obsoleted by other documents at any 43 time. It is inappropriate to use Internet-Drafts as reference 44 material or to cite them other than as "work in progress." 46 This Internet-Draft will expire on 15 February 2021. 48 Copyright Notice 50 Copyright (c) 2020 IETF Trust and the persons identified as the 51 document authors. All rights reserved. 53 This document is subject to BCP 78 and the IETF Trust's Legal 54 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 55 license-info) in effect on the date of publication of this document. 56 Please review these documents carefully, as they describe your rights 57 and restrictions with respect to this document. Code Components 58 extracted from this document must include Simplified BSD License text 59 as described in Section 4.e of the Trust Legal Provisions and are 60 provided without warranty as described in the Simplified BSD License. 62 Table of Contents 64 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 65 2. Requirements Notation . . . . . . . . . . . . . . . . . . . . 4 66 3. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 4 67 4. Calculating Limits . . . . . . . . . . . . . . . . . . . . . 6 68 5. Single-User AEAD Limits . . . . . . . . . . . . . . . . . . . 6 69 5.1. AEAD_AES_128_GCM and AEAD_AES_256_GCM . . . . . . . . . . 7 70 5.1.1. Confidentiality Limit . . . . . . . . . . . . . . . . 7 71 5.1.2. Integrity Limit . . . . . . . . . . . . . . . . . . . 7 72 5.2. AEAD_CHACHA20_POLY1305 . . . . . . . . . . . . . . . . . 7 73 5.3. AEAD_AES_128_CCM . . . . . . . . . . . . . . . . . . . . 8 74 5.3.1. Confidentiality Limit . . . . . . . . . . . . . . . . 8 75 5.3.2. Integrity Limit . . . . . . . . . . . . . . . . . . . 8 76 5.4. AEAD_AES_128_CCM_8 . . . . . . . . . . . . . . . . . . . 9 77 6. Multi-User AEAD Limits . . . . . . . . . . . . . . . . . . . 9 78 6.1. AEAD_AES_128_GCM and AEAD_AES_256_GCM . . . . . . . . . . 9 79 6.1.1. Confidentiality Limit . . . . . . . . . . . . . . . . 9 80 6.1.2. Integrity Limit . . . . . . . . . . . . . . . . . . . 9 81 6.2. AEAD_CHACHA20_POLY1305, AEAD_AES_128_CCM, and 82 AEAD_AES_128_CCM_8 . . . . . . . . . . . . . . . . . . . 10 83 6.2.1. AEAD_CHACHA20_POLY1305 . . . . . . . . . . . . . . . 10 84 6.2.2. AEAD_AES_128_CCM and AEAD_AES_128_CCM_8 . . . . . . . 10 85 7. Security Considerations . . . . . . . . . . . . . . . . . . . 11 86 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 87 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 88 9.1. Normative References . . . . . . . . . . . . . . . . . . 11 89 9.2. Informative References . . . . . . . . . . . . . . . . . 12 90 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 13 92 1. Introduction 94 An Authenticated Encryption with Associated Data (AEAD) algorithm 95 provides confidentiality and integrity. [RFC5116] specifies an AEAD 96 as a function with four inputs - secret key, nonce, plaintext, and 97 optional associated data - that produces ciphertext output and error 98 code indicating success or failure. The ciphertext is typically 99 composed of the encrypted plaintext bytes and an authentication tag. 101 The generic AEAD interface does not describe usage limits. Each AEAD 102 algorithm does describe limits on its inputs, but these are 103 formulated as strict functional limits, such as the maximum length of 104 inputs, which are determined by the properties of the underlying AEAD 105 composition. Degradation of the security of the AEAD as a single key 106 is used multiple times is not given a thorough treatment. 108 These limits might also be influenced by the number of "users" of a 109 given key. In the traditional setting, there is one key shared 110 between a two parties. Any limits on the maximum length of inputs or 111 encryption operations apply to that single key. The attacker's goal 112 is to break security (confidentiality or integrity) of that specific 113 key. However, in practice, there are often many users with 114 independent keys. In this "multi-user" setting, the attacker is 115 assumed to have done some offline work to help break security of 116 single key (or user), where the attacker cannot choose which key is 117 attacked. As a result, AEAD algorithm limits may depend on offline 118 work and the number of users. However, given that a multi-user 119 attacker does not target any specific user, acceptable advantages may 120 differ from that of the single-user setting. 122 The number of times a single pair of key and nonce can be used might 123 also be relevant to security. For some algorithms, such as 124 AEAD_AES_128_GCM or AEAD_AES_256_GCM, this limit is 1 and using the 125 same pair of key and nonce has serious consequences for both 126 confidentiality and integrity; see [NonceDisrespecting]. Nonce-reuse 127 resistant algorithms like AEAD_AES_128_GCM_SIV can tolerate a limited 128 amount of nonce reuse. 130 It is good practice to have limits on how many times the same key (or 131 pair of key and nonce) are used. Setting a limit based on some 132 measurable property of the usage, such as number of protected 133 messages or amount of data transferred, ensures that it is easy to 134 apply limits. This might require the application of simplifying 135 assumptions. For example, TLS 1.3 specifies limits on the number of 136 records that can be protected, using the simplifying assumption that 137 records are the same size; see Section 5.5 of [TLS]. 139 Currently, AEAD limits and usage requirements are scattered among 140 peer-reviewed papers, standards documents, and other RFCs. 141 Determining the correct limits for a given setting is challenging as 142 papers do not use consistent labels or conventions, and rarely apply 143 any simplifications that might aid in reaching a simple limit. 145 The intent of this document is to collate all relevant information 146 about the proper usage and limits of AEAD algorithms in one place. 147 This may serve as a standard reference when considering which AEAD 148 algorithm to use, and how to use it. 150 2. Requirements Notation 152 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 153 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 154 "OPTIONAL" in this document are to be interpreted as described in 155 BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all 156 capitals, as shown here. 158 3. Notation 160 This document defines limitations in part using the quantities below. 162 +========+====================================================+ 163 | Symbol | Description | 164 +========+====================================================+ 165 | n | Number of bits per block | 166 +--------+----------------------------------------------------+ 167 | k | Size of the AEAD key (in bits) | 168 +--------+----------------------------------------------------+ 169 | t | Size of the authentication tag (in bits) | 170 +--------+----------------------------------------------------+ 171 | l | Length of each message (in blocks) | 172 +--------+----------------------------------------------------+ 173 | s | Total plaintext length in all messages (in blocks) | 174 +--------+----------------------------------------------------+ 175 | q | Number of user encryption attempts | 176 +--------+----------------------------------------------------+ 177 | v | Number of attacker forgery attempts | 178 +--------+----------------------------------------------------+ 179 | p | Adversary attack probability | 180 +--------+----------------------------------------------------+ 181 | o | Offline adversary work (in number of encryption | 182 | | and decryption queries; multi-user setting only) | 183 +--------+----------------------------------------------------+ 184 | u | Number of users or keys (multi-user setting only) | 185 +--------+----------------------------------------------------+ 187 Table 1 189 For each AEAD algorithm, we define the confidentiality and integrity 190 advantage roughly as the advantage an attacker has in breaking the 191 corresponding security property for the algorithm. Specifically: 193 * Confidentiality advantage (CA): The advantage of an attacker 194 succeeding in breaking the confidentiality properties of the AEAD. 195 In this document, the definition of confidentiality advantage is 196 the increase in the probability that an attacker is able to 197 successfully distinguish an AEAD ciphertext from the output of a 198 random function. 200 * Integrity advantage (IA): The probability of an attacker 201 succeeding in breaking the integrity properties of the AEAD. In 202 this document, the definition of integrity advantage is the 203 probability that an attacker is able to forge a ciphertext that 204 will be accepted as valid. 206 Each application requires a different application of limits in order 207 to keep CA and IA sufficiently small. For instance, TLS aims to keep 208 CA below 2^-60 and IA below 2^-57. See [TLS], Section 5.5. 210 4. Calculating Limits 212 Once an upper bound on CA and IA are determined, this document 213 defines a process for determining two overall limits: 215 * Confidentiality limit (CL): The number of bytes of plaintext and 216 maybe authenticated additional data (AAD) an application can 217 encrypt before giving the adversary a non-negligible CA. 219 * Integrity limit (IL): The number of bytes of ciphertext and maybe 220 authenticated additional data (AAD) an application can process, 221 either successfully or not, before giving the adversary a non- 222 negligible IA. 224 For an AEAD based on a block function, it is common for these limits 225 to be expressed instead in terms of the number of blocks rather than 226 bytes. Furthermore, it might be more appropriate to track the number 227 of messages rather than track bytes. Therefore, the guidance is 228 usually based on the total number of blocks processed (s). To aid in 229 calculating limits for message-based protocols, a formulation of 230 limits that includes a maximum message size (l) is included. 232 All limits are based on the total number of messages, either the 233 number of protected messages (q) or the number of forgery attempts 234 (v); which correspond to CL and IL respectively. 236 Limits are then derived from those bounds using a target attacker 237 probability. For example, given a confidentiality advantage of "v * 238 (8l / 2^106)" and attacker success probability of "p", the algorithm 239 remains secure, i.e., the adversary's advantage does not exceed the 240 probability of success, provided that "v <= (p * 2^106) / 8l". In 241 turn, this implies that "v <= (p * 2^106) / 8l" is the corresponding 242 limit. 244 5. Single-User AEAD Limits 246 This section summarizes the confidentiality and integrity bounds and 247 limits for modern AEAD algorithms used in IETF protocols, including: 248 AEAD_AES_128_GCM [RFC5116], AEAD_AES_256_GCM [RFC5116], 249 AEAD_AES_128_CCM [RFC5116], AEAD_CHACHA20_POLY1305 [RFC8439], 250 AEAD_AES_128_CCM_8 [RFC6655]. 252 The CL and IL values bound the total number of encryption and forgery 253 queries (q and v). Alongside each value, we also specify these 254 bounds. 256 5.1. AEAD_AES_128_GCM and AEAD_AES_256_GCM 258 The CL and IL values for AES-GCM are derived in [AEBounds] and 259 summarized below. For this AEAD, n = 128 and t = 128 [GCM]. In this 260 example, the length s is the sum of AAD and plaintext, as described 261 in [GCMProofs]. 263 5.1.1. Confidentiality Limit 265 CA <= ((s + q + 1)^2) / 2^129 267 This implies the following usage limit: 269 q + s <= p^(1/2) * 2^(129/2) - 1 271 Which, for a message-based protocol with "s <= q * l", if we assume 272 that every packet is size "l", produces the limit: 274 q <= (p^(1/2) * 2^(129/2) - 1) / (l + 1) 276 5.1.2. Integrity Limit 278 IA <= 2 * (v * (l + 1)) / 2^128 280 This implies the following limit: 282 v <= (p * 2^127) / (l + 1) 284 5.2. AEAD_CHACHA20_POLY1305 286 The only known analysis for AEAD_CHACHA20_POLY1305 287 [ChaCha20Poly1305Bounds] combines the confidentiality and integrity 288 limits into a single expression, covered below: 290 CA <= v * ((8 * l) / 2^106) 291 IA <= v * ((8 * l) / 2^106) 293 This advantage is a tight reduction based on the underlying Poly1305 294 PRF [Poly1305]. It implies the following limit: 296 v <= (p * 2^103) / l 298 5.3. AEAD_AES_128_CCM 300 The CL and IL values for AEAD_AES_128_CCM are derived from 301 [CCM-ANALYSIS] and specified in the QUIC-TLS mapping specification 302 [I-D.ietf-quic-tls]. This analysis uses the total number of 303 underlying block cipher operations to derive its bound. For CCM, 304 this number is the sum of: the length of the associated data in 305 blocks, the length of the ciphertext in blocks, the length of the 306 plaintext in blocks, plus 1. 308 In the following limits, this is simplified to a value of twice the 309 length of the packet in blocks, i.e., 2l represents the effective 310 length, in number of block cipher operations, of a message with l 311 blocks. This simplification is based on the observation that common 312 applications of this AEAD carry only a small amount of associated 313 data compared to ciphertext. For example, QUIC has 1 to 3 blocks of 314 AAD. 316 For this AEAD, n = 128 and t = 128. 318 5.3.1. Confidentiality Limit 320 CA <= (2l * q)^2 / 2^n 321 <= (2l * q)^2 / 2^128 323 This implies the following limit: 325 q <= sqrt((p * 2^126) / l^2) 327 5.3.2. Integrity Limit 329 IA <= v / 2^t + (2l * (v + q))^2 / 2^n 330 <= v / 2^128 + (2l * (v + q))^2 / 2^128 332 This implies the following limit: 334 v + (2l * (v + q))^2 <= p * 2^128 336 In a setting where "v" or "q" is sufficiently large, "v" is 337 negligible compared to "(2l * (v + q))^2", so this this can be 338 simplified to: 340 v + q <= p^(1/2) * 2^63 / l 342 5.4. AEAD_AES_128_CCM_8 344 The analysis in [CCM-ANALYSIS] also applies to this AEAD, but the 345 reduced tag length of 64 bits changes the integrity limit calculation 346 considerably. 348 IA <= v / 2^t + (2l * (v + q))^2 / 2^n 349 <= v / 2^64 + (2l * (v + q))^2 / 2^128 351 This results in reducing the limit on "v" by a factor of 2^64. 353 v * 2^64 + (2l * (v + q))^2 <= p * 2^128 355 6. Multi-User AEAD Limits 357 In the public-key, multi-user setting, [MUSecurity] proves that the 358 success probability in attacking one of many independently users is 359 bounded by the success probability of attacking a single user 360 multiplied by the number of users present. Each user is assumed to 361 have an independent and identically distributed key, though some may 362 share nonces with some very small probability. Absent concrete 363 multi-user bounds, this means the attacker advantage in the multi- 364 user setting is the product of the single-user advantage and the 365 number of users. 367 This section summarizes the confidentiality and integrity bounds and 368 limits for the same algorithms as in Section 5, except in the multi- 369 user setting. The CL and IL values bound the total number of 370 encryption and forgery queries (q and v). Alongside each value, we 371 also specify these bounds. 373 6.1. AEAD_AES_128_GCM and AEAD_AES_256_GCM 375 Concrete multi-user bounds for AEAD_AES_128_GCM and AEAD_AES_256_GCM 376 exist due to [GCM-MU]. AES-GCM without nonce randomization is also 377 discussed in [GCM-MU], though this section does not include those 378 results as they do not apply to protocols such as TLS 1.3 [RFC8446]. 380 6.1.1. Confidentiality Limit 382 CA <= ((v + q) * l)^2 / (u * 2^128) 384 This implies the following limit: 386 v + q <= sqrt(p * u * 2^128) / l 388 6.1.2. Integrity Limit 389 CA <= (1 / 2^1024) + ((2 * (v + q)) / 2^256) 390 + ((2 * o * (v + q)) / 2^(k + 128)) 391 + (128 * ((v + q) + ((v + q) * l)) / 2^k) 393 When k = 128, the last term in this inequality dominates. Thus, we 394 can simplify this to: 396 CA <= (128 * ((v + q) + ((v + q) * l)) / 2^128) 398 This implies the following limit: 400 v + q <= (p * 2^128) / (128 * (l + 1)) 402 When k = 256, the second and fourth terms in the CA inequality 403 dominate. Thus, we can simplify this to: 405 CA <= ((2 * (v + q)) / 2^256) 406 + (128 * ((v + q) + ((v + q) * l)) / 2^256) 408 This implies the following limit: 410 v + q <= (p * 2^255) / ((64 * l) + 65) 412 6.2. AEAD_CHACHA20_POLY1305, AEAD_AES_128_CCM, and AEAD_AES_128_CCM_8 414 There are currently no concrete multi-user bounds for 415 AEAD_CHACHA20_POLY1305, AEAD_AES_128_CCM, or AEAD_AES_128_CCM_8. 416 Thus, to account for the additional factor "u", i.e., the number of 417 users, each "p" term in the confidentiality and integrity limits is 418 replaced with "p / u". 420 6.2.1. AEAD_CHACHA20_POLY1305 422 The combined confidentiality and integrity limit for 423 AEAD_CHACHA20_POLY1305 is as follows. 425 v <= ((p / u) * 2^106) / 8l 426 <= (p * 2^103) / (l * u) 428 6.2.2. AEAD_AES_128_CCM and AEAD_AES_128_CCM_8 430 The integrity limit for AEAD_AES_128_CCM is as follows. 432 v + q <= (p / u)^(1/2) * 2^63 / l 434 Likewise, the integrity limit for AEAD_AES_128_CCM_8 is as follows. 436 v * 2^64 + (2l * (v + q))^2 <= (p / u) * 2^128 438 7. Security Considerations 440 Many of the formulae in this document depend on simplifying 441 assumptions that are not universally applicable. When using this 442 document to set limits, it is necessary to validate all these 443 assumptions for the setting in which the limits might apply. In most 444 cases, the goal is to use assumptions that result in setting a more 445 conservative limit, but this is not always the case. 447 8. IANA Considerations 449 This document does not make any request of IANA. 451 9. References 453 9.1. Normative References 455 [AEBounds] Luykx, A. and K. Paterson, "Limits on Authenticated 456 Encryption Use in TLS", 8 March 2016, 457 . 459 [CCM-ANALYSIS] 460 Jonsson, J., "On the Security of CTR + CBC-MAC", 461 DOI 10.1007/3-540-36492-7_7, Selected Areas in 462 Cryptography pp. 76-93, 2003, 463 . 465 [ChaCha20Poly1305Bounds] 466 Procter, G., "A Security Analysis of the Composition of 467 ChaCha20 and Poly1305", 11 August 2014, 468 . 470 [GCM] Dworkin, M., "Recommendation for Block Cipher Modes of 471 Operation: Galois/Counter Mode (GCM) and GMAC", 472 NIST Special Publication 800-38D, November 2007. 474 [GCMProofs] 475 Iwata, T., Ohashi, K., and K. Minematsu, "Breaking and 476 Repairing GCM Security Proofs", 1 August 2012, 477 . 479 [MUSecurity] 480 Bellare, M., Boldyreva, A., and S. Micali, "Public-Key 481 Encryption in a Multi-user Setting: Security Proofs and 482 Improvements", May 2000, 483 . 485 [Poly1305] Bernstein, D., "The Poly1305-AES Message-Authentication 486 Code", DOI 10.1007/11502760_3, Fast Software 487 Encryption pp. 32-49, 2005, 488 . 490 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 491 Requirement Levels", BCP 14, RFC 2119, 492 DOI 10.17487/RFC2119, March 1997, 493 . 495 [RFC5116] McGrew, D., "An Interface and Algorithms for Authenticated 496 Encryption", RFC 5116, DOI 10.17487/RFC5116, January 2008, 497 . 499 [RFC6655] McGrew, D. and D. Bailey, "AES-CCM Cipher Suites for 500 Transport Layer Security (TLS)", RFC 6655, 501 DOI 10.17487/RFC6655, July 2012, 502 . 504 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 505 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 506 May 2017, . 508 [RFC8439] Nir, Y. and A. Langley, "ChaCha20 and Poly1305 for IETF 509 Protocols", RFC 8439, DOI 10.17487/RFC8439, June 2018, 510 . 512 9.2. Informative References 514 [GCM-MU] Hoang, V., Tessaro, S., and A. Thiruvengadam, "The Multi- 515 user Security of GCM, Revisited", 516 DOI 10.1145/3243734.3243816, Proceedings of the 2018 ACM 517 SIGSAC Conference on Computer and Communications Security, 518 January 2018, . 520 [I-D.ietf-quic-tls] 521 Thomson, M. and S. Turner, "Using TLS to Secure QUIC", 522 Work in Progress, Internet-Draft, draft-ietf-quic-tls-29, 523 9 June 2020, . 526 [NonceDisrespecting] 527 Bock, H., Zauner, A., Devlin, S., Somorovsky, J., and P. 528 Jovanovic, "Nonce-Disrespecting Adversaries -- Practical 529 Forgery Attacks on GCM in TLS", 17 May 2016, 530 . 532 [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol 533 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 534 . 536 [TLS] Rescorla, E., "The Transport Layer Security (TLS) Protocol 537 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 538 . 540 Authors' Addresses 542 Felix Günther 543 ETH Zurich 545 Email: mail@felixguenther.info 547 Martin Thomson 548 Mozilla 550 Email: mt@lowentropy.net 552 Christopher A. Wood 553 Cloudflare 555 Email: caw@heapingbits.net