Network Working Group A.A. Bozhko, Ed. Internet-Draft CryptoPro Intended status: Informational 14 October 2022 Expires: 17 April 2023 Properties of AEAD algorithms draft-bozhko-cfrg-aead-properties-01 Abstract Authenticated Encryption with Associated Data (AEAD) algorithms provide confidentiality and integrity of data. The extensive use of AEAD algorithms in various high-level applications has caused the need for AEAD algorithms with additional properties and motivated research in the area. This document gives definitions for the most common of those properties intending to improve consistency in the field. 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 17 April 2023. Copyright Notice Copyright (c) 2022 IETF Trust and the persons identified as the document authors. All rights reserved. Bozhko Expires 17 April 2023 [Page 1] Internet-Draft Properties of AEAD algorithms October 2022 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 Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Background . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Scope . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Conventions Used in This Document . . . . . . . . . . . . . . 4 3. AEAD properties . . . . . . . . . . . . . . . . . . . . . . . 4 3.1. Security properties . . . . . . . . . . . . . . . . . . . 4 3.1.1. Confidentiality . . . . . . . . . . . . . . . . . . . 4 3.1.2. Data integrity . . . . . . . . . . . . . . . . . . . 4 3.1.3. Blockwise security . . . . . . . . . . . . . . . . . 4 3.1.4. Key Dependent Messages (KDM) security . . . . . . . . 4 3.1.5. Key commitment . . . . . . . . . . . . . . . . . . . 5 3.1.6. Leakage resistance . . . . . . . . . . . . . . . . . 5 3.1.7. Multi-user security . . . . . . . . . . . . . . . . . 5 3.1.8. Nonce misuse . . . . . . . . . . . . . . . . . . . . 5 3.1.8.1. Nonce misuse resilience . . . . . . . . . . . . . 5 3.1.8.2. Nonce misuse resistance . . . . . . . . . . . . . 5 3.1.9. Reforgeability resilience . . . . . . . . . . . . . . 6 3.1.10. Release of unverified plaintext (RUP) security . . . 6 3.2. Implementation properties . . . . . . . . . . . . . . . . 6 3.2.1. Inverse-free . . . . . . . . . . . . . . . . . . . . 6 3.2.2. Lightweight . . . . . . . . . . . . . . . . . . . . . 6 3.2.3. Online . . . . . . . . . . . . . . . . . . . . . . . 6 3.2.4. Parallelizable . . . . . . . . . . . . . . . . . . . 6 3.2.5. Single pass . . . . . . . . . . . . . . . . . . . . . 7 3.2.6. ZK-friendly . . . . . . . . . . . . . . . . . . . . . 7 3.3. Additional functionality properties . . . . . . . . . . . 7 3.3.1. Incremental . . . . . . . . . . . . . . . . . . . . . 7 3.3.2. Nonce-hiding . . . . . . . . . . . . . . . . . . . . 7 3.3.3. Remotely-keyed . . . . . . . . . . . . . . . . . . . 7 4. Security Considerations . . . . . . . . . . . . . . . . . . . 8 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 6. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 6.1. Normative References . . . . . . . . . . . . . . . . . . 8 6.2. Informative References . . . . . . . . . . . . . . . . . 8 Appendix A. Contributors . . . . . . . . . . . . . . . . . . . . 13 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 13 Bozhko Expires 17 April 2023 [Page 2] Internet-Draft Properties of AEAD algorithms October 2022 1. Introduction An Authenticated Encryption with Associated Data (AEAD) algorithm is an extension of authenticated encryption, which provides confidentiality for the plaintext to be encrypted and integrity for the plaintext and some Associated Data (sometimes called Header). AEAD algorithms are used in numerous applications and have become an important field in cryptographic research. 1.1. Background AEAD algorithms are formally defined in [RFC5116]. The main benefit of AEAD algorithms is that they provide both data confidentiality and data integrity and have a simple unified interface. The importance of the AEAD algorithms is mainly explained by their exploitation simplicity: they have a unified interface, easy-to- understand security guarantees, and are much easier to implement properly than MAC and encryption schemes separately. Therefore, their embedding into high-level schemes and protocols is highly transparent, since, for example, there is no need for additional key derivation procedures. Apart from that, when using the AEAD algorithm it is possible to reduce the key size, state size, and to improve the data processing speed. For instance, the use of such algorithms is mandatory for TLS 1.3 [RFC8446], IPsec ESP [RFC4303] [RFC8221], QUIC [RFC9000]. Hence, the research and standardization efforts in the field are extremely active. Most AEAD algorithms usually come with security guarantees, formal proofs, usage guidelines and reference implementations. Even though providing core properties of AEAD algorithms is enough for use in many applications, some environments require other unusual cryptographic properties which commonly require additional analysis and research. With the growing number of such properties and research papers, misunderstanding and confusion inevitably appear. Some properties might be understood in different ways, for some only non-trivial formal security notions are provided, others require modification or extension of the standard AEAD interface to support additional functionality. Therefore, the risk of misuse of AEAD algorithms increases which can lead to security issues. 1.2. Scope In the following document, we provide a short overview of the most common properties of AEAD algorithms, by giving high-level definitions of these properties in Section 3. The document aims to improve clarity and establish a common language in the field. Bozhko Expires 17 April 2023 [Page 3] Internet-Draft Properties of AEAD algorithms October 2022 2. Conventions Used in This Document 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. AEAD properties 3.1. Security properties 3.1.1. Confidentiality Definition. An AEAD algorithm guarantees that data is available only to those authorized to obtain it. That property is required for the AEAD algorithm to be called secure. Synonyms. Privacy. Further reading. [R2002], [BN2000] 3.1.2. Data integrity Definition. An AEAD algorithm guarantees that data is available only to those authorized to obtain it. That property is required for the AEAD algorithm to be called secure. Synonyms. Message authentication. Further reading. [R2002], [BN2000] 3.1.3. Blockwise security Definition. An AEAD algorithm provides security even if an adversary can adaptively choose the next block of a plaintext (ciphertext) depending on already computed blocks of the ciphertext (plaintext) during an encryption (decryption) operation. Further reading. [JMV2002], [FJMV2004] 3.1.4. Key Dependent Messages (KDM) security Definition. An AEAD algorithm provides security even when key- dependent plaintexts are encrypted. Notes. KDM-security is achievable only if nonces are chosen randomly and associated data is key-independent. Bozhko Expires 17 April 2023 [Page 4] Internet-Draft Properties of AEAD algorithms October 2022 Further reading. [BK2011] 3.1.5. Key commitment Definition. An AEAD algorithm guarantees that it is difficult to find a tuple of nonce, associated data and ciphertext, such that it can be decrypted correctly with more than one key. Synonyms. Key-robustness, key collision resistance. Further reading. [FOR17], [LGR21], [GLR17] 3.1.6. Leakage resistance Definition. An AEAD algorithm provides its security even if an additional information about computations of an encryption (and possibly decryption) operation is obtained via side-channel leakages. Further reading. [GPPS19], [B20] 3.1.7. Multi-user security Definition. An AEAD algorithm security level degrades sublinearly in a number of users. Here the level of security is understood in the sense of Authenticated Encryption advantage (AEA) as given in [I-D.irtf-cfrg-aead-limits]. Further reading. [BT16] 3.1.8. Nonce misuse Definition. An AEAD algorithm provides security (resilience or resistance) even if an adversary can repeat nonces in its encryption queries. 3.1.8.1. Nonce misuse resilience Definition. Security is provided only for messages encrypted with unique nonces. Further reading. [ADL17], [RS06] 3.1.8.2. Nonce misuse resistance Definition. Security is provided for all messages. Further reading. [RS06] Bozhko Expires 17 April 2023 [Page 5] Internet-Draft Properties of AEAD algorithms October 2022 3.1.9. Reforgeability resilience Definition. An AEAD algorithm guarantees that once a successful forgery for the algorithm has been found, it is still hard to find any subsequent forgery. Further reading. [BC09], [FLLW17] 3.1.10. Release of unverified plaintext (RUP) security Definition. An AEAD algorithm provides its security even if a plaintext is released for every ciphertext, including those with failed integrity verification. Further reading. [A14] 3.2. Implementation properties 3.2.1. Inverse-free Definition. A blockcipher-based AEAD algorithm can be securely implemented without any evaluation of the block cipher inverse. 3.2.2. Lightweight Definition. An AEAD algorithm can be efficiently and securely implemented on resource-constrained devices. Particularly, it meets the criteria, required in the NIST Lightweight Cryptography competition [MBTM17]. Further reading. [MBTM17] 3.2.3. Online Definition. An AEAD algorithm encryption (decryption) algorithm can be implemented with a constant memory and a single one-direction pass over the plaintext (ciphertext), writing out the result during that pass. Further reading. [HRRV15] [FJMV2004] 3.2.4. Parallelizable Definition. An AEAD algorithm can fully exploit the parallel computation infrastructure. In other words, with unlimited number of threads, computation time remains constant in an input length. Further reading. [C20] Bozhko Expires 17 April 2023 [Page 6] Internet-Draft Properties of AEAD algorithms October 2022 3.2.5. Single pass Definition. An AEAD algorithm encryption (decryption) operation can be implemented with a single pass over the plaintext (ciphertext). 3.2.6. ZK-friendly Definition. An AEAD algorithm operates on binary and prime fields with a low number of non-linear operations (often referred to as the multiplicative complexity). Thus, allows efficient implementation using a domain specific language (DSL) for writing zk-SNARKs circuits. Synonyms. ZK-focused, Arithmetization-oriented, Low Multiplicative Complexity Further reading. [DGGK21] 3.3. Additional functionality properties 3.3.1. Incremental Definition. An AEAD algorithm design allows to encrypt a message, which only partly differs from some other previously encrypted message, faster than encrypting the whole message with the encryption operation. Further reading. [SY16], [BKY02] 3.3.2. Nonce-hiding Definition. An AEAD algorithm decryption operation doesn't need the nonce value to perform the decryption. Thus, the algorithm provides privacy for the nonce value. Further reading. [BNT19] 3.3.3. Remotely-keyed Definition. An AEAD algorithm can be securely implemented with most of the operations in encryption/decryption performed by an insecure (i.e. it leaks all intermediate values) device, which has no access to the key, while operations involving the key are performed by another secure device. Further reading. [BFN98], [DA03] Bozhko Expires 17 April 2023 [Page 7] Internet-Draft Properties of AEAD algorithms October 2022 4. Security Considerations This document defines the properties of AEAD algorithms. However, the document does not describe any concrete mechanisms providing these properties, neither it describes how to achieve them. In fact, one can claim that an AEAD algorithm provides any of the defined properties only if its formal analysis in the relevant models was carried out. 5. IANA Considerations This document has no IANA actions. 6. References 6.1. Normative References [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, . [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . 6.2. Informative References [A14] Forler, C., List, E., Forler, C., List, E., List, E., and E. List, "How to Securely Release Unverified Plaintext in Authenticated Encryption", Advances in Cryptology – ASIACRYPT 2014. ASIACRYPT 2014. Lecture Notes in Computer Science, vol 8873. Springer, Berlin, Heidelberg, DOI 10.1007/978-3-662-45611-8_6, 2014, . [ADL17] Ashur, T., Dunkelman, O., and A. Luykx, "Boosting Authenticated Encryption Robustness with Minimal Modifications", Advances in Cryptology – CRYPTO 2017. CRYPTO 2017. Lecture Notes in Computer Science, vol 10403. Springer, Cham, DOI 10.1007/978-3-319-63697-9_1, 2017, . Bozhko Expires 17 April 2023 [Page 8] Internet-Draft Properties of AEAD algorithms October 2022 [B20] Bellizia, D., Bronchain, O., Cassiers, G., Grosso, V., Guo, C., Momin, C., Pereira, O., Peters, T., and FX. Standaert, "Mode-Level vs. Implementation-Level Physical Security in Symmetric Cryptography: A Practical Guide Through the Leakage-Resistance Jungle", Advances in Cryptology – CRYPTO 2020. CRYPTO 2020. Lecture Notes in Computer Science, vol 12170. Springer, Cham, DOI 10.1007/978-3-030-56784-2_13, 2020, . [BC09] Forler, C. and E. List, "MAC Reforgeability", Fast Software Encryption. FSE 2009. Lecture Notes in Computer Science, vol 5665. Springer, Berlin, Heidelberg, DOI 10.1007/978-3-642-03317-9_21, 2009, . [BFN98] Blaze, M., Feigenbaum, J., and M. Naor, "A formal treatment of remotely keyed encryption", Advances in Cryptology — EUROCRYPT'98. EUROCRYPT 1998. Lecture Notes in Computer Science, vol 1403. Springer, Berlin, Heidelberg, DOI 10.1007/BFb0054131, 1998, . [BK2011] Bellare, M. and S. Keelveedhi, "Authenticated and Misuse- Resistant Encryption of Key-Dependent Data", Advances in Cryptology – CRYPTO 2011. CRYPTO 2011. Lecture Notes in Computer Science, vol 6841. Springer, Berlin, Heidelberg., DOI 10.1007/978-3-642-22792-9_35, 2011, . [BKY02] Buonanno, E., Katz, J., and M. Yung, "Incremental Unforgeable Encryption", Fast Software Encryption. FSE 2001. Lecture Notes in Computer Science, vol 2355. Springer, Berlin, Heidelberg, DOI 10.1007/3-540-45473-X_9, 2002, . [BN2000] Bellare, M. and C. Namprempre, "Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm", Proceedings of ASIACRYPT 2000, Springer-Verlag, LNCS 1976, pp. 531-545, DOI 10.1007/s00145-008-9026-x, 2000, . [BNT19] Bellare, M., Ng, R., and B. Tackmann, "Nonces Are Noticed: AEAD Revisited", Advances in Cryptology – CRYPTO 2019. CRYPTO 2019. Lecture Notes in Computer Science, vol 11692. Springer, Cham, DOI 10.1007/978-3-030-26948-7_9, 2019, . Bozhko Expires 17 April 2023 [Page 9] Internet-Draft Properties of AEAD algorithms October 2022 [BT16] Bellare, M. and B. Tackmann, "The Multi-User Security of Authenticated Encryption: AES-GCM in TLS 1.3", Advances in Cryptology – CRYPTO 2016. CRYPTO 2016. Lecture Notes in Computer Science, vol 9814. Springer, Berlin, Heidelberg, DOI 10.1007/978-3-662-53018-4_10, 2016, . [C20] Chakraborti, A., Datta, N., Jha, A., Mancillas-López, C., Nandi, M., and Y. Sasaki, "INT-RUP Secure Lightweight Parallel AE Modes", IACR Transactions on Symmetric Cryptology, 2019(4), 81–118, DOI 10.13154/tosc.v2019.i4.81-118, 2020, . [DA03] Dodis, Y. and JH. An, "Concealment and Its Applications to Authenticated Encryption", Advances in Cryptology — EUROCRYPT 2003. EUROCRYPT 2003. Lecture Notes in Computer Science, vol 2656. Springer, Berlin, Heidelberg, DOI 10.1007/3-540-39200-9_19, 2003, . [DGGK21] Dobraunig, C., Grassi, L., Guinet, G., and K. Kuijsters, "CIMINION: Symmetric Encryption Based on Toffoli-Gates over Large Finite Fields", Advances in Cryptology – EUROCRYPT 2021. EUROCRYPT 2021. Lecture Notes in Computer Science(), vol 12697. Springer, Cham, DOI 10.1007/978-3-030-77886-6_1, 2021, . [FJMV2004] Valette, PA., Joux, A., Martinet, G., and F. Valette, "Authenticated On-Line Encryption", Selected Areas in Cryptography. SAC 2003. Lecture Notes in Computer Science, vol 3006. Springer, Berlin, Heidelberg., DOI 10.1007/978-3-540-24654-1_11, 2004, . [FLLW17] Forler, C., List, E., Lucks, S., and J. Wenzel, "Reforgeability of Authenticated Encryption Schemes", Information Security and Privacy. ACISP 2017. Lecture Notes in Computer Science, vol 10343. Springer, Cham, DOI 10.1007/978-3-319-59870-3_2, 2017, . Bozhko Expires 17 April 2023 [Page 10] Internet-Draft Properties of AEAD algorithms October 2022 [FOR17] Farshim, P., Orlandi, C., and R. Rosie, "Authenticated and Misuse-Resistant Encryption of Key-Dependent DataSecurity of Symmetric Primitives under Incorrect Usage of Keys", IACR Transactions on Symmetric Cryptology, 2017(1), 449–473., DOI 10.13154/tosc.v2017.i1.449-473, 2017, . [GLR17] Grubbs, P., Lu, J., and T. Ristenpart, "Message Franking via Committing Authenticated Encryption.", Advances in Cryptology – CRYPTO 2017. CRYPTO 2017. Lecture Notes in Computer Science, vol 10403. Springer, Cham, DOI 10.1007/978-3-319-63697-9_3, 2017, . [GPPS19] Guo, C., Pereira, O., Peters, T., and FX. Standaert, "Authenticated Encryption with Nonce Misuse and Physical Leakages: Definitions, Separation Results and Leveled Constructions", Progress in Cryptology – LATINCRYPT 2019. LATINCRYPT 2019. Lecture Notes in Computer Science, vol 11774. Springer, Cham, DOI 10.1007/978-3-030-30530-7_8, 2019, . [HRRV15] Hoang, VT., Reyhanitabar, R., Rogaway, P., and D. Vizár, "Online Authenticated-Encryption and its Nonce-Reuse Misuse-Resistance", Advances in Cryptology -- CRYPTO 2015. CRYPTO 2015. Lecture Notes in Computer Science, vol 9215. Springer, Berlin, Heidelberg, DOI 10.1007/978-3-662-47989-6_24, 2015, . [I-D.irtf-cfrg-aead-limits] Günther, F., Thomson, M., and C. A. Wood, "Usage Limits on AEAD Algorithms", Work in Progress, Internet-Draft, draft- irtf-cfrg-aead-limits-05, 11 July 2022, . [JMV2002] Joux, A., Martinet, G., and F. Valette, "Blockwise- Adaptive Attackers Revisiting the (In)Security of Some Provably Secure Encryption Modes: CBC, GEM, IACBC", Advances in Cryptology — CRYPTO 2002. CRYPTO 2002. Lecture Notes in Computer Science, vol 2442. Springer, Berlin, Heidelberg, DOI 10.1007/3-540-45708-9_2, 2002, . [LGR21] Len, J., Grubbs, P., and T. Ristenpart, "Partitioning Oracle Attacks", 30th USENIX Security Symposium (USENIX Security 21), 195--212, 2021. Bozhko Expires 17 April 2023 [Page 11] Internet-Draft Properties of AEAD algorithms October 2022 [MBTM17] McKay, K., Bassham, L., Turan, MS., and N. Mouha, "Report on Lightweight Cryptography", DOI 10.6028/NIST.IR.8114, 2017, . [R2002] Rogaway, P., "Authenticated-encryption with associated- data.", Proceedings of the 9th ACM conference on Computer and communications security (CCS '02), Association for Computing Machinery, New York, NY, USA, 98–107, DOI 10.1145/586110.586125, 2002, . [RFC4303] Kent, S., "IP Encapsulating Security Payload (ESP)", RFC 4303, DOI 10.17487/RFC4303, December 2005, . [RFC8221] Wouters, P., Migault, D., Mattsson, J., Nir, Y., and T. Kivinen, "Cryptographic Algorithm Implementation Requirements and Usage Guidance for Encapsulating Security Payload (ESP) and Authentication Header (AH)", RFC 8221, DOI 10.17487/RFC8221, October 2017, . [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, . [RFC9000] Iyengar, J., Ed. and M. Thomson, Ed., "QUIC: A UDP-Based Multiplexed and Secure Transport", RFC 9000, DOI 10.17487/RFC9000, May 2021, . [RS06] Rogaway, R. and T. Shrimpton, "A Provable-Security Treatment of the Key-Wrap Problem", Advances in Cryptology - EUROCRYPT 2006. EUROCRYPT 2006. Lecture Notes in Computer Science, vol 4004. Springer, Berlin, Heidelberg, DOI 10.1007/11761679_23, 2016, . [SY16] Sasaki, Y. and K. Yasuda, "A New Mode of Operation for Incremental Authenticated Encryption with Associated Data", Selected Areas in Cryptography – SAC 2015. SAC 2015. Lecture Notes in Computer Science(), vol 9566. Springer, Cham, DOI 10.1007/978-3-319-31301-6_23, 2016, . Bozhko Expires 17 April 2023 [Page 12] Internet-Draft Properties of AEAD algorithms October 2022 Appendix A. Contributors Author's Address Andrey Bozhko (editor) CryptoPro Email: andbogc@gmail.com Bozhko Expires 17 April 2023 [Page 13]