Usage Limits on AEAD Algorithms
draftirtfcfrgaeadlimits00
This document is an InternetDraft (ID) that has been submitted to the Internet Research Task Force (IRTF) stream.
This ID is not endorsed by the IETF and has no formal standing in the
IETF standards process.
The information below is for an old version of the document.
Document  Type 
This is an older version of an InternetDraft whose latest revision state is "Active".



Authors  Felix Günther , Martin Thomson , Christopher A. Wood  
Last updated  20200816 (Latest revision 20200814)  
Replaces  draftwoodcfrgaeadlimits  
RFC stream  Internet Research Task Force (IRTF)  
Formats  
Additional resources  Mailing list discussion  
Stream  IRTF state  Active RG Document  
Consensus boilerplate  Unknown  
Document shepherd  (None)  
IESG  IESG state  ID Exists  
Telechat date  (None)  
Responsible AD  (None)  
Send notices to  (None) 
draftirtfcfrgaeadlimits00
Network Working Group F. Günther InternetDraft ETH Zurich Intended status: Informational M. Thomson Expires: 15 February 2021 Mozilla C.A. Wood Cloudflare 14 August 2020 Usage Limits on AEAD Algorithms draftirtfcfrgaeadlimits00 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 multiuser 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/chriswood/draftwoodcfrgaeadlimits (https://github.com/chriswood/draftwoodcfrgaeadlimits). Status of This Memo This InternetDraft is submitted in full conformance with the provisions of BCP 78 and BCP 79. InternetDrafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as InternetDrafts. The list of current Internet Drafts is at https://datatracker.ietf.org/drafts/current/. InternetDrafts 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 InternetDrafts as reference material or to cite them other than as "work in progress." This InternetDraft will expire on 15 February 2021. Günther, et al. Expires 15 February 2021 [Page 1] InternetDraft AEAD Limits August 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/ licenseinfo) 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. SingleUser AEAD Limits . . . . . . . . . . . . . . . . . . . 6 5.1. AEAD_AES_128_GCM and AEAD_AES_256_GCM . . . . . . . . . . 7 5.1.1. Confidentiality Limit . . . . . . . . . . . . . . . . 7 5.1.2. Integrity Limit . . . . . . . . . . . . . . . . . . . 7 5.2. AEAD_CHACHA20_POLY1305 . . . . . . . . . . . . . . . . . 7 5.3. AEAD_AES_128_CCM . . . . . . . . . . . . . . . . . . . . 8 5.3.1. Confidentiality Limit . . . . . . . . . . . . . . . . 8 5.3.2. Integrity Limit . . . . . . . . . . . . . . . . . . . 8 5.4. AEAD_AES_128_CCM_8 . . . . . . . . . . . . . . . . . . . 9 6. MultiUser AEAD Limits . . . . . . . . . . . . . . . . . . . 9 6.1. AEAD_AES_128_GCM and AEAD_AES_256_GCM . . . . . . . . . . 9 6.1.1. Confidentiality Limit . . . . . . . . . . . . . . . . 9 6.1.2. Integrity Limit . . . . . . . . . . . . . . . . . . . 9 6.2. AEAD_CHACHA20_POLY1305, AEAD_AES_128_CCM, and AEAD_AES_128_CCM_8 . . . . . . . . . . . . . . . . . . . 10 6.2.1. AEAD_CHACHA20_POLY1305 . . . . . . . . . . . . . . . 10 6.2.2. AEAD_AES_128_CCM and AEAD_AES_128_CCM_8 . . . . . . . 10 7. Security Considerations . . . . . . . . . . . . . . . . . . . 11 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 9.1. Normative References . . . . . . . . . . . . . . . . . . 11 9.2. Informative References . . . . . . . . . . . . . . . . . 12 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 13 Günther, et al. Expires 15 February 2021 [Page 2] InternetDraft AEAD Limits August 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 a 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. In this "multiuser" setting, the attacker is assumed to have done some offline work to help break security of single key (or user), where the attacker cannot choose which key is attacked. As a result, AEAD algorithm limits may depend on offline work and the number of users. However, given that a multiuser attacker does not target any specific user, acceptable advantages may differ from that of the singleuser 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]. Noncereuse 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 15 February 2021 [Page 3] InternetDraft AEAD Limits August 2020 Currently, AEAD limits and usage requirements are scattered among peerreviewed 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 15 February 2021 [Page 4] InternetDraft AEAD Limits August 2020 +========+====================================================+  Symbol  Description  +========+====================================================+  n  Number of bits per block  +++  k  Size of the AEAD key (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 user encryption attempts  +++  v  Number of attacker forgery attempts  +++  p  Adversary attack probability  +++  o  Offline adversary work (in number of encryption    and decryption queries; multiuser setting only)  +++  u  Number of users or keys (multiuser setting only)  +++ Table 1 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: * Confidentiality advantage (CA): The advantage of an attacker succeeding in breaking the confidentiality properties of the AEAD. In this document, the definition of confidentiality advantage is the increase in the probability that an attacker is able to successfully distinguish an AEAD ciphertext from the output of a random function. * Integrity advantage (IA): The probability of an attacker succeeding in breaking the integrity properties of the AEAD. In this document, the definition of integrity advantage is the probability that an attacker is able to forge a ciphertext that will be accepted as valid. 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. Günther, et al. Expires 15 February 2021 [Page 5] InternetDraft AEAD Limits August 2020 4. Calculating Limits Once an upper bound on CA and IA are determined, this document defines a process for determining two overall limits: * Confidentiality limit (CL): The number of bytes of plaintext and maybe authenticated additional data (AAD) an application can encrypt before giving the adversary a nonnegligible CA. * Integrity limit (IL): The number of bytes of ciphertext and maybe authenticated additional data (AAD) an application can process, either successfully or not, before giving the adversary a non negligible IA. 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 messagebased 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. 5. SingleUser 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. Günther, et al. Expires 15 February 2021 [Page 6] InternetDraft AEAD Limits August 2020 5.1. AEAD_AES_128_GCM and AEAD_AES_256_GCM The CL and IL values for AESGCM 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 Which, for a messagebased 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 Günther, et al. Expires 15 February 2021 [Page 7] InternetDraft AEAD Limits August 2020 5.3. AEAD_AES_128_CCM The CL and IL values for AEAD_AES_128_CCM are derived from [CCMANALYSIS] and specified in the QUICTLS mapping specification [ID.ietfquictls]. 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. 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 Günther, et al. Expires 15 February 2021 [Page 8] InternetDraft AEAD Limits August 2020 5.4. AEAD_AES_128_CCM_8 The analysis in [CCMANALYSIS] 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. MultiUser AEAD Limits In the publickey, multiuser setting, [MUSecurity] proves that the success probability in attacking one of many independently users is bounded by the success probability of attacking a single user multiplied by the number of users present. Each user is assumed to have an independent and identically distributed key, though some may share nonces with some very small probability. Absent concrete multiuser bounds, this means the attacker advantage in the multi user setting is the product of the singleuser advantage and the number of users. This section summarizes the confidentiality and integrity bounds and limits for the same algorithms as in Section 5, except in 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 multiuser bounds for AEAD_AES_128_GCM and AEAD_AES_256_GCM exist due to [GCMMU]. AESGCM without nonce randomization is also discussed in [GCMMU], though this section does not include those results as they do not apply to protocols such as TLS 1.3 [RFC8446]. 6.1.1. Confidentiality Limit CA <= ((v + q) * l)^2 / (u * 2^128) This implies the following limit: v + q <= sqrt(p * u * 2^128) / l 6.1.2. Integrity Limit Günther, et al. Expires 15 February 2021 [Page 9] InternetDraft AEAD Limits August 2020 CA <= (1 / 2^1024) + ((2 * (v + q)) / 2^256) + ((2 * o * (v + q)) / 2^(k + 128)) + (128 * ((v + q) + ((v + q) * l)) / 2^k) When k = 128, the last term in this inequality dominates. Thus, we can simplify this to: CA <= (128 * ((v + q) + ((v + q) * l)) / 2^128) This implies the following limit: v + q <= (p * 2^128) / (128 * (l + 1)) When k = 256, the second and fourth terms in the CA inequality dominate. Thus, we can simplify this to: CA <= ((2 * (v + q)) / 2^256) + (128 * ((v + q) + ((v + q) * l)) / 2^256) This implies the following limit: v + q <= (p * 2^255) / ((64 * l) + 65) 6.2. AEAD_CHACHA20_POLY1305, AEAD_AES_128_CCM, and AEAD_AES_128_CCM_8 There are currently no concrete multiuser 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 Günther, et al. Expires 15 February 2021 [Page 10] InternetDraft AEAD Limits August 2020 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 [AEBounds] Luykx, A. and K. Paterson, "Limits on Authenticated Encryption Use in TLS", 8 March 2016, <http://www.isg.rhul.ac.uk/~kp/TLSAEbounds.pdf>. [CCMANALYSIS] Jonsson, J., "On the Security of CTR + CBCMAC", DOI 10.1007/3540364927_7, Selected Areas in Cryptography pp. 7693, 2003, <https://doi.org/10.1007/3540364927_7>. [ChaCha20Poly1305Bounds] Procter, G., "A Security Analysis of the Composition of ChaCha20 and Poly1305", 11 August 2014, <https://eprint.iacr.org/2014/613.pdf>. [GCM] Dworkin, M., "Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC", NIST Special Publication 80038D, November 2007. [GCMProofs] Iwata, T., Ohashi, K., and K. Minematsu, "Breaking and Repairing GCM Security Proofs", 1 August 2012, <https://eprint.iacr.org/2012/438.pdf>. [MUSecurity] Bellare, M., Boldyreva, A., and S. Micali, "PublicKey Encryption in a Multiuser Setting: Security Proofs and Improvements", May 2000, <https://cseweb.ucsd.edu/~mihir/papers/musu.pdf>. Günther, et al. Expires 15 February 2021 [Page 11] InternetDraft AEAD Limits August 2020 [Poly1305] Bernstein, D., "The Poly1305AES MessageAuthentication Code", DOI 10.1007/11502760_3, Fast Software Encryption pp. 3249, 2005, <https://doi.org/10.1007/11502760_3>. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfceditor.org/info/rfc2119>. [RFC5116] McGrew, D., "An Interface and Algorithms for Authenticated Encryption", RFC 5116, DOI 10.17487/RFC5116, January 2008, <https://www.rfceditor.org/info/rfc5116>. [RFC6655] McGrew, D. and D. Bailey, "AESCCM Cipher Suites for Transport Layer Security (TLS)", RFC 6655, DOI 10.17487/RFC6655, July 2012, <https://www.rfceditor.org/info/rfc6655>. [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfceditor.org/info/rfc8174>. [RFC8439] Nir, Y. and A. Langley, "ChaCha20 and Poly1305 for IETF Protocols", RFC 8439, DOI 10.17487/RFC8439, June 2018, <https://www.rfceditor.org/info/rfc8439>. 9.2. Informative References [GCMMU] Hoang, V., Tessaro, S., and A. Thiruvengadam, "The Multi user Security of GCM, Revisited", DOI 10.1145/3243734.3243816, Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, January 2018, <https://doi.org/10.1145/3243734.3243816>. [ID.ietfquictls] Thomson, M. and S. Turner, "Using TLS to Secure QUIC", Work in Progress, InternetDraft, draftietfquictls29, 9 June 2020, <http://www.ietf.org/internetdrafts/draft ietfquictls29.txt>. [NonceDisrespecting] Bock, H., Zauner, A., Devlin, S., Somorovsky, J., and P. Jovanovic, "NonceDisrespecting Adversaries  Practical Forgery Attacks on GCM in TLS", 17 May 2016, <https://eprint.iacr.org/2016/475.pdf>. Günther, et al. Expires 15 February 2021 [Page 12] InternetDraft AEAD Limits August 2020 [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, <https://www.rfceditor.org/info/rfc8446>. [TLS] Rescorla, E., "The Transport Layer Security (TLS) Protocol Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, <https://www.rfceditor.org/info/rfc8446>. 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 15 February 2021 [Page 13]