Skip to main content

Properties of AEAD Algorithms
draft-irtf-cfrg-aead-properties-09

Document Type Active Internet-Draft (cfrg RG)
Author Andrey Bozhko
Last updated 2024-11-02 (Latest revision 2024-10-11)
Replaces draft-bozhko-cfrg-aead-properties
RFC stream Internet Research Task Force (IRTF)
Intended RFC status Informational
Formats
IETF conflict review conflict-review-irtf-cfrg-aead-properties
Additional resources Mailing list discussion
Stream IRTF state Sent to the RFC Editor
Consensus boilerplate Yes
Document shepherd Alexey Melnikov
Shepherd write-up Show Last changed 2024-06-10
IESG IESG state I-D Exists
Telechat date (None)
Responsible AD (None)
Send notices to alexey.melnikov@isode.com
IANA IANA review state IANA OK - No Actions Needed
IANA action state No IANA Actions
RFC Editor RFC Editor state EDIT
Details
draft-irtf-cfrg-aead-properties-09
Crypto Forum                                            A.A. Bozhko, Ed.
Internet-Draft                                                 CryptoPro
Intended status: Informational                           11 October 2024
Expires: 14 April 2025

                     Properties of AEAD Algorithms
                   draft-irtf-cfrg-aead-properties-09

Abstract

   Authenticated Encryption with Associated Data (AEAD) algorithms
   provide both confidentiality and integrity of data.  The widespread
   use of AEAD algorithms in various applications has led to an
   increased demand for AEAD algorithms with additional properties,
   driving research in the field.  This document provides definitions
   for the most common of those properties, aiming to improve
   consistency in the terminology used in documentation.  This document
   is a product of the Crypto Forum Research Group.

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 14 April 2025.

Copyright Notice

   Copyright (c) 2024 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

Bozhko                    Expires 14 April 2025                 [Page 1]
Internet-Draft        Properties of AEAD algorithms         October 2024

   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 Algorithms . . . . . . . . . . . . . . . . . . . . . . .   4
   4.  AEAD Properties . . . . . . . . . . . . . . . . . . . . . . .   5
     4.1.  Classification of additional AEAD Properties  . . . . . .   5
     4.2.  Conventional Properties . . . . . . . . . . . . . . . . .   6
       4.2.1.  Confidentiality . . . . . . . . . . . . . . . . . . .   6
       4.2.2.  Data Integrity  . . . . . . . . . . . . . . . . . . .   7
       4.2.3.  Authenticated Encryption Security . . . . . . . . . .   7
     4.3.  Security Properties . . . . . . . . . . . . . . . . . . .   7
       4.3.1.  Blockwise Security  . . . . . . . . . . . . . . . . .   7
       4.3.2.  Full Commitment . . . . . . . . . . . . . . . . . . .   8
       4.3.3.  Key Commitment  . . . . . . . . . . . . . . . . . . .   8
       4.3.4.  Leakage Resistance  . . . . . . . . . . . . . . . . .   9
       4.3.5.  Multi-User Security . . . . . . . . . . . . . . . . .  10
       4.3.6.  Nonce-Hiding  . . . . . . . . . . . . . . . . . . . .  10
       4.3.7.  Nonce Misuse  . . . . . . . . . . . . . . . . . . . .  11
       4.3.8.  Quantum Security  . . . . . . . . . . . . . . . . . .  12
       4.3.9.  Reforgeability Resilience . . . . . . . . . . . . . .  12
       4.3.10. Release of Unverified Plaintext (RUP) Integrity . . .  13
     4.4.  Implementation Properties . . . . . . . . . . . . . . . .  13
       4.4.1.  Hardware efficient  . . . . . . . . . . . . . . . . .  13
       4.4.2.  Inverse-Free  . . . . . . . . . . . . . . . . . . . .  14
       4.4.3.  Lightweight . . . . . . . . . . . . . . . . . . . . .  14
       4.4.4.  Parallelizable  . . . . . . . . . . . . . . . . . . .  14
       4.4.5.  Setup-Free  . . . . . . . . . . . . . . . . . . . . .  15
       4.4.6.  Single Pass . . . . . . . . . . . . . . . . . . . . .  15
       4.4.7.  Static Associated Data Efficient  . . . . . . . . . .  15
       4.4.8.  Streamable  . . . . . . . . . . . . . . . . . . . . .  15
   5.  Security Considerations . . . . . . . . . . . . . . . . . . .  16
   6.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  16
   7.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  16
     7.1.  Normative References  . . . . . . . . . . . . . . . . . .  17
     7.2.  Informative References  . . . . . . . . . . . . . . . . .  17
   Appendix A.  AEAD Algorithms with Additional Functionality  . . .  25

Bozhko                    Expires 14 April 2025                 [Page 2]
Internet-Draft        Properties of AEAD algorithms         October 2024

     A.1.  Incremental Authenticated Encryption  . . . . . . . . . .  26
     A.2.  Robust Authenticated Encryption . . . . . . . . . . . . .  26
   Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . .  27
   Author's Address  . . . . . . . . . . . . . . . . . . . . . . . .  27

1.  Introduction

   An Authenticated Encryption with Associated Data (AEAD) algorithm
   provides confidentiality for the plaintext to be encrypted and
   integrity for the plaintext and some associated data (sometimes
   called Header).  AEAD algorithms play a crucial role in various
   applications and have emerged as a significant focus in cryptographic
   research.

1.1.  Background

   AEAD algorithms are formally defined in [RFC5116].  The main benefit
   of AEAD algorithms is that they simultaneously provide data
   confidentiality and integrity and have a simple unified interface.
   In contrast to generic compositions of Message Authentication Code
   (MAC) and encryption algorithms, an AEAD algorithm allows for a
   reduction in key and state sizes, improving the data processing
   speed.  Most AEAD algorithms come with security analysis, usage
   guidelines, and reference implementations.  Consequently, their
   integration into high-level schemes and protocols is highly
   transparent.  For instance, AEAD algorithms are mandatory in TLS 1.3
   [RFC8446], IPsec ESP [RFC4303][RFC8221], and QUIC [RFC9000].

   While confidentiality and data integrity, being the conventional
   properties of AEAD algorithms, suffice for many applications, some
   environments demand other uncommon cryptographic properties.  These
   often require additional analysis and research.  As the number of
   such properties and corresponding research papers grows, inevitable
   misunderstandings and confusion arise.  It is a common situation when
   related but formally different properties are named identically, or
   some security properties only have folklore understanding and are not
   formally defined.  Consequently, the risk of misusing AEAD algorithms
   increases, potentially resulting in security issues.

1.2.  Scope

   In this document, in Section 4, we provide the list of the most
   common additional properties of AEAD algorithms.  The properties are
   divided into two categories, namely security properties (see
   Section 4.3) and implementation properties (see Section 4.4).  We
   provide a high-level definition for each property.  For security
   properties, we also reference an informative source where a formal
   game-based security notion is defined; we do not consider security

Bozhko                    Expires 14 April 2025                 [Page 3]
Internet-Draft        Properties of AEAD algorithms         October 2024

   properties for which no game-based formalization exists.  When
   possible, we offer additional information: synonymous names, examples
   of algorithms that provide the property, applications that might
   necessitate such property from an AEAD algorithm, references for
   further reading, and additional notes containing information outside
   these categories.

   The objective of this document is to enhance clarity and establish a
   common language in the field.  In particular, the primary application
   of the document lies in the following two use cases within the IRTF
   or the IETF documents development process:

   *  For an RFC or I-D that defines an AEAD algorithm, it is
      recommended to use the notations of Section 4 when listing
      additional properties of the algorithm.

   *  For an RFC or I-D that defines a generic protocol based on an AEAD
      algorithm, it is recommended to use the notations of Section 4 if
      any additional properties are required from the algorithm.

   This document represents the consensus of the Crypto Forum Research
   Group (CFRG).  This document is not an IETF product and is not a
   standard.

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 Algorithms

   This section gives a conventional definition of an AEAD algorithm
   following [RFC5116].

   Definition: An AEAD algorithm is defined by two operations, which are
   authenticated encryption and authenticated decryption:

   *  A deterministic operation of authenticated encryption has four
      inputs, each a binary string: a secret key K of a fixed bit
      length, a nonce N, associated data A, and a plaintext P.  The
      plaintext contains the data to be encrypted and authenticated, and
      the associated data contains the data to be authenticated only.
      Each nonce value MUST be unique in every distinct invocation of
      the operation for any particular value of the key.  The
      authenticated encryption operation outputs a ciphertext C.

Bozhko                    Expires 14 April 2025                 [Page 4]
Internet-Draft        Properties of AEAD algorithms         October 2024

   *  A deterministic operation of authenticated decryption has four
      inputs, each a binary string: a secret key K of a fixed bit
      length, a nonce N, associated data A, and a ciphertext C.  The
      operation verifies the integrity of the ciphertext and associated
      data and decrypts the ciphertext.  It returns a special symbol
      FAIL if the inputs are not authentic; otherwise, the operation
      returns a plaintext P.

   We note that specifications of AEAD algorithms that use
   authentication tags to ensure integrity MAY define it as an
   independent output of the encryption operation and as an independent
   input of the decryption operation.  Throughout this document, by
   default, we will consider the authentication tag as part of the
   ciphertext.

   For more details on the AEAD definition, please refer to [RFC5116].

   Throughout this document, by default, we will consider nonce-based
   AEAD algorithms, which have an interface from the definition above,
   and give no other restrictions on their structure.  However, some
   properties considered in the document apply only to particular
   classes of such algorithms, like block cipher-based AEAD algorithms
   (such algorithms use block cipher as a building block).  If that is
   the case, we explicitly point that out in the corresponding section.

4.  AEAD Properties

4.1.  Classification of additional AEAD Properties

   In this document, we employ a high-level classification of additional
   properties.  This classification aims to provide insight into how one
   can benefit from each property.  The additional properties in this
   section are categorized into one of these two groups:

   *  Security properties: We classify a property as a security property
      if it either takes into account new threats or extends adversarial
      capabilities, in addition to those posed by the typical nonce-
      respecting adversary whose goal is to compromise confidentiality
      or data integrity.

   *  Implementation properties: We classify a property as an
      implementation property if it enables more efficient
      implementations of the AEAD algorithm in specific cases or
      environments.

   We note that some additional properties of AEAD algorithms found in
   the literature could not be allocated to either of these two groups.
   The observation is that such properties require an extension of the

Bozhko                    Expires 14 April 2025                 [Page 5]
Internet-Draft        Properties of AEAD algorithms         October 2024

   conventional AEAD interface.  We refer to these properties as
   'additional functionality properties' and define the corresponding
   group as follows:

   *  Additional functionality properties: We classify a property as an
      additional functionality property if it introduces new features in
      addition to the standard authenticated encryption with associated
      data.

   With the extension of the conventional AEAD interface, each
   additional functionality property defines a new class of
   cryptographic algorithms.  Consequently, the basic threats and
   adversarial capabilities must be redefined for each class.  As a
   result, additional functionality properties consider the basic
   threats and adversarial capabilities for their class of algorithms,
   in contrast to security properties, which consider the extended ones.
   For this reason, we do not focus on additional functionality
   properties in this document.  However, for the sake of completeness,
   in Appendix A, we briefly present two classes of AEAD algorithms with
   additional functionality.

4.2.  Conventional Properties

   In this section, we recall the conventional properties of an AEAD
   algorithm.  Active nonce-respecting adversaries in a single-key
   setting are considered.

   We say that an AEAD algorithm provides security if it provides
   conventional properties listed in this section.

4.2.1.  Confidentiality

   Definition: An AEAD algorithm guarantees that the plaintext is not
   available to an active, nonce-respecting adversary.

   Security notion: IND-CCA [BN2000] (or IND-CCA2 [S04]).

   Synonyms: Message privacy.

   Notes: Confidentiality against passive adversaries can also be
   considered.  The corresponding security notion is IND-CPA
   [BN2000][R02].

   Further reading: [R02], [BN2000], [S04].

Bozhko                    Expires 14 April 2025                 [Page 6]
Internet-Draft        Properties of AEAD algorithms         October 2024

4.2.2.  Data Integrity

   Definition: An AEAD algorithm allows one to ensure that the
   ciphertext and the associated data have not been changed or forged by
   an active, nonce-respecting adversary.

   Security notion: IND-CTXT [BN2000] (or AUTH [R02]).

   Synonyms: Message authentication, authenticity.

   Further reading: [R02], [BN2000], [S04].

4.2.3.  Authenticated Encryption Security

   Definition: An AEAD algorithm provides confidentiality and data
   integrity against active, nonce-respecting adversaries.

   Security notion: IND-CPA and IND-CTXT [BN2000][R02] (or equivalently
   IND-CCA3 [S04]).

   Notes: Please refer to [I-D.irtf-cfrg-aead-limits] for usage limits
   on modern AEAD algorithms used in IETF protocols.

   Further reading: [R02], [BN2000], [S04].

4.3.  Security Properties

4.3.1.  Blockwise Security

   Definition: An AEAD algorithm provides security even if an adversary
   can adaptively choose the next part of the plaintext depending on
   already computed ciphertext parts during an encryption operation.

   Security notion: D-LORS-BCPA for confidentiality against passive
   adversaries, B-INT-CTXT for integrity [EV16]; OAE1 [HRRV15] (a
   stronger notion; originally OAE (Online Authenticated Encryption) in
   [FFL12]).

   Examples: Deoxys [JNPS21], SAEF [ABV21].

   Notes: Blockwise security is highly relevant for streamable AEAD
   algorithms (see Section 4.4.8).  The OAE1 security notion [HRRV15],
   and the OAE2 notion [HRRV15] are tailored for streamable AEAD
   algorithms.  OAE1 was first defined in [FFL12] under the name OAE;
   however, it contained a glitch, and the reformulated definition was
   presented in [HRRV15].  Blockwise security follows from security in
   the OAE notion [EV16].  For a discussion on security notions for
   streamable AEAD algorithms see [HRRV15].

Bozhko                    Expires 14 April 2025                 [Page 7]
Internet-Draft        Properties of AEAD algorithms         October 2024

   Applications: Real-time streaming protocols, encryption on resource-
   constrained devices.

   Further reading: [EV16], [JMV2002], [FJMV2004], [HRRV15].

4.3.2.  Full Commitment

   Definition: An AEAD algorithm guarantees that it is hard to find two
   or more different tuples of the key, nonce, associated data, and
   plaintext such that they encrypt to the same ciphertext.  In other
   words, an AEAD scheme guarantees that a ciphertext is a commitment to
   all inputs of an authenticated encryption operation.

   Security notion: CMT-4 [BH22], generalized CMT for a restricted
   setting (see the notes below) [MLGR23].

   Examples: Ascon [DEMS21a][DEMS21b][YSS23], full committing versions
   of GCM and GCM-SIV [BH22], generic constructions [BH22][CR22].

   Notes: Full commitment can be considered in a weaker setting, where
   certain restrictions on the tuples produced by an adversary are
   imposed [MLGR23].  For instance, an adversary must find tuples that
   all share the same associated data value.  In such cases, an AEAD
   algorithm is said to provide full commitment in a restricted setting.
   The imposed restrictions MUST be listed.

   Applications: Message franking [GLR17].

   Further reading: [BH22], [CR22], [MLGR23].

4.3.3.  Key Commitment

   Definition: An AEAD algorithm guarantees that it is hard to find two
   or more different keys and the same number of potentially equal
   triples of nonce, associated data, and plaintext such that they
   encrypt to the same ciphertext under corresponding keys.  In other
   words, an AEAD scheme guarantees that a ciphertext is a commitment to
   the key used for an authenticated encryption operation.

   Security notion: CMT-1 [BH22].

   Synonyms: Key-robustness, key collision resistance.

   Examples: Ascon [DEMS21a][DEMS21b][YSS23], generic constructions from
   [BH22] [CR22].

   Notes: Key commitment follows from full commitment.  Full commitment
   does not follow from key commitment [BH22].

Bozhko                    Expires 14 April 2025                 [Page 8]
Internet-Draft        Properties of AEAD algorithms         October 2024

   Applications: Password-Authenticated Key Exchange, password-based
   encryption [LGR21], key rotation, envelope encryption [ADGKLS22].

   Further reading: [BH22],[CR22], [FOR17], [LGR21], [GLR17].

4.3.4.  Leakage Resistance

   Definition: An AEAD algorithm provides security even if some
   additional information about computations of an encryption (and
   possibly decryption) operation is obtained via side-channel leakages.

   Security notion: CIL1 [GPPS19] (CIML2 [BPPS17] with leakages in
   decryption) for integrity, CCAL1 [GPPS19] (CCAmL2 [GPPS19] with
   leakages in decryption) for Authenticated Encryption security.

   Examples: Ascon [DEMS21a][DEMS21b] (security under CIML2 and CCAL1
   notions [B20]), TEDT [GPPS19].

   Notes: Leakages during AEAD operation executions are implementation-
   dependent.  It is possible to implement symmetric algorithms in a way
   that every possible physical leakage is entirely independent of the
   secret inputs of the algorithm (for example, with a masking technique
   [CJRR99]), meaning the adversary doesn't gain any additional
   information about the algorithm's computation via side-channel
   leakages.  We say that an AEAD algorithm doesn't provide leakage
   resistance if it can achieve leakage resistance only with such an
   implementation.  Leakage-resistant AEAD algorithms aim to place as
   mild requirements on implementation as possible to achieve leakage
   resistance.  These requirements SHOULD be listed.

   Confidentiality of plaintext in the presence of leakages in the
   encryption operation is unachievable if an adversary can repeat the
   nonce used to encrypt the plaintext in other encryption queries.
   Confidentiality can be achieved only for plaintexts encrypted with
   fresh nonces (analogously to nonce-misuse resilience, see
   Section 4.3.7).  For further discussions, see [GPPS19] and [B20].

   For primitive-based AEAD algorithms, key evolution (internal re-
   keying [RFC8645]) can contribute to achieving leakage resistance with
   leakages in encryption.  Confidentiality in the presence of
   decryption leakages can be achieved by two-pass AEAD algorithms with
   key evolution, which compute independent ephemeral key values for
   encryption and tag generation, where the computation of these keys is
   implemented without any leakages.  For more discussions on achieving
   leakage resistance see [B20].

Bozhko                    Expires 14 April 2025                 [Page 9]
Internet-Draft        Properties of AEAD algorithms         October 2024

   A well-known weaker property, Leakage Resilience, introduced in
   [BMOS17], can also be considered.  However, this document makes a
   conscious choice to focus on the stronger Leakage Resistance,
   following the framework established in [GPPS19], [B20], for its
   enhanced practicality and comprehensiveness.

   Applications: Encryption on smart cards, Internet-of-things devices,
   or other constrained devices.

   Further reading: [GPPS19], [B20], [BPPS17], [BMOS17].

4.3.5.  Multi-User Security

   Definition: An AEAD algorithm security degrades slower than linearly
   with an increase in the number of users.

   Security notion: mu-ind [BT16].

   Examples: AES-GCM [D07], ChaCha20-Poly1305 [RFC8439], AES-GCM-SIV
   [RFC8452], AEGIS [I-D.irtf-cfrg-aegis-aead].

   Notes: It holds that for any AEAD algorithm security degrades no
   worse than linearly with an increase in the number of users [BT16].
   However, for some applications with a significant number of users,
   better multi-user guarantees are required.  For example, in the TLS
   1.3 protocol, to address this issue, AEAD algorithms are used with a
   randomized nonce (deterministically derived from a traffic secret and
   a sequence number).  Using nonce randomization in block cipher
   counter-based AEAD modes can contribute to multi-user security
   [BT16].  Multi-user usage limits for AES-GCM and ChaCha20-Poly1305
   are provided in [I-D.irtf-cfrg-aead-limits].

   A weaker security notion, multi-user key recovery, is also introduced
   and thoroughly studied in [BT16].  While this document focuses on
   indistinguishability for security notions, key recovery might be
   relevant and valuable to study alongside indistinguishability.

   Applications: Data transmission layer of secure communication
   protocols (e.g., TLS, IPSec, SRTP, etc.)

   Further reading: [BT16], [HTT18], [LMP17], [DGGP21], [BHT18].

4.3.6.  Nonce-Hiding

   Definition: An AEAD algorithm provides confidentiality for the nonce
   value used to encrypt plaintext.  The algorithm includes information
   about the nonce in the ciphertext and doesn't require the nonce as
   input for the decryption operation.

Bozhko                    Expires 14 April 2025                [Page 10]
Internet-Draft        Properties of AEAD algorithms         October 2024

   Security notion: AE2 [BNT19].

   Examples: Hide-Nonce (HN) transforms [BNT19].

   Notes: As discussed in [BNT19], adversary-visible nonces might
   compromise message and user privacy, similar to the way any metadata
   might do.  As pointed out in [B13], even using a counter as a nonce
   value might compromise privacy.  Designing a privacy-preserving way
   to manage nonces might be a challenging problem for an application.

   Applications: Any application that can't rely on a secure 'out-of-
   band' nonce communication.

   Further reading: [BNT19].

4.3.7.  Nonce Misuse

   Definition: An AEAD algorithm provides security (resilience or
   resistance) even if an adversary can repeat nonces in its encryption
   queries.  Nonce misuse resilience and resistance are defined as
   follows:

   *  Nonce misuse resilience: Security is provided for messages
      encrypted with non-repeated (fresh) nonces (correctly encrypted
      messages).

      Security notion: CPA resilience (confidentiality), authenticity
      resilience (integrity), CCA resilience (authenticated encryption)
      [ADL17].

      Examples: ChaCha20-Poly1305 [RFC8439], AES-GCM [D07] (only
      confidentiality).

   *  Nonce misuse resistance: Security is provided for all messages
      that were not encrypted with the same nonce value more than once.

      Security notion: MRAE [RS06].

      Examples: AES-GCM-SIV [RFC8452], Deoxys-II [JNPS21].

      Notes: SIV construction [RS06] is a generic construction that
      provides nonce misuse resistance.

   Notes: Nonce misuse resilience follows from nonce misuse resistance.
   Nonce misuse resistance does not follow from nonce misuse resilience.

Bozhko                    Expires 14 April 2025                [Page 11]
Internet-Draft        Properties of AEAD algorithms         October 2024

   Applications: Any application where nonce uniqueness can't be
   guaranteed, security against fault-injection attacks and
   malfunctions, processes parallelization, full disk encryption.

   Further reading: [RS06], [ADL17].

4.3.8.  Quantum Security

   Definition: An AEAD algorithm provides security (in a Q1 or Q2 model)
   against a quantum adversary.  Q1 and Q2 models are defined as
   follows:

   *  Q1 model: An adversary has access to local quantum computational
      power.  It has classical access to encryption and decryption
      oracles.

      Synonyms: Post-quantum security.

      Examples: AES-GCM [D07], ChaCha20-Poly1305 [RFC8439], OCB
      [RFC7253], MGM [RFC9058], AES-GCM-SIV [RFC8452], AEGIS
      [I-D.irtf-cfrg-aegis-aead].

   *  Q2 model: An adversary has access to local quantum computational
      power.  It has quantum access to encryption and decryption
      oracles, i.e., it can query encryption and decryption oracles with
      quantum superpositions of inputs to receive quantum superpositions
      of the outputs.

      Synonyms: Superposition-based quantum security.

      Examples: QCB [BBCLNSS21].

   Notes: Most symmetric cryptographic algorithms that are secure in the
   classical model provide quantum security in the Q1 model, i.e., they
   are post-quantum secure.  Security in the Q1 setting corresponds to
   security against "harvest now, decrypt later" attacks.  Security in
   Q1 follows from security in Q2, the converse does not hold.  For
   discussions on the relevance of the Q2 model please see [G17].

   Further reading: [KLLNP16], [BBCLNSS21], [G17].

4.3.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.

   Security notion: j-Int-CTXT [FLLW17].

Bozhko                    Expires 14 April 2025                [Page 12]
Internet-Draft        Properties of AEAD algorithms         October 2024

   Examples: Deoxys [JNPS21], AEGIS [I-D.irtf-cfrg-aegis-aead], Ascon
   [DEMS21a][DEMS21b].

   Applications: VoIP, real-time streaming in a lightweight setting,
   applications that require small ciphertext expansion (i.e., short
   tags).

   Further reading: [BC09], [FLLW17].

4.3.10.  Release of Unverified Plaintext (RUP) Integrity

   Definition: An AEAD algorithm provides data integrity even if
   plaintext is released for every ciphertext, including those with
   failed integrity verification.

   Security notion: INT-RUP [A14].

   Examples: GCM-RUP [ADL17].

   Applications: Decryption with limited memory [FJMV2004], real-time
   streaming protocols.

   Notes: In [ADL17] a generic approach to achieve INT-RUP security is
   introduced.

   In the provided definition, we only consider integrity in the RUP
   setting, since confidentiality, in the usual sense, is unachievable
   under RUP.  In [A14], the notion of 'Plaintext Awareness' is
   introduced, capturing the best possible confidentiality under RUP in
   the following sense: 'The adversary cannot gain any additional
   knowledge about the plaintext from decryption queries beyond what it
   can derive from encryption queries'.

   Further reading: [A14], [ADL17].

4.4.  Implementation Properties

4.4.1.  Hardware efficient

   Definition: An AEAD algorithm ensures optimal performance when
   operating on hardware that complies with the specified requirements.

Bozhko                    Expires 14 April 2025                [Page 13]
Internet-Draft        Properties of AEAD algorithms         October 2024

   Notes: Various classes of hardware may be taken into consideration.
   Certain algorithms are tailored to minimize the area of dedicated
   hardware implementations, while others are intended to capitalize on
   general-purpose CPUs, with or without specific instruction sets.  It
   is RECOMMENDED to specify the minimum platform requirements for the
   AEAD to fulfill its intended purpose, as well as to match its
   performance and security claims.

4.4.2.  Inverse-Free

   Definition: An AEAD algorithm based on a given primitive can be
   implemented without invoking the inverse of that primitive.

   Examples: AES-GCM [D07], ChaCha20-Poly1305 [RFC8439], OCB [RFC7253],
   MGM [RFC9058], AEGIS [I-D.irtf-cfrg-aegis-aead].

   Notes: In a sponge-based AEAD algorithm, an underlying permutation is
   viewed as a primitive.

4.4.3.  Lightweight

   Definition: An AEAD algorithm can be efficiently and securely
   implemented on resource-constrained devices.  In particular, it meets
   the criteria required in the NIST Lightweight Cryptography
   competition [MBTM17].

   Examples: OCB [RFC7253], Ascon [DEMS21a][DEMS21b].

   Further reading: [MBTM17].

4.4.4.  Parallelizable

   Definition: An AEAD algorithm can fully exploit the parallel
   computation infrastructure.  In other words, a parallelizable AEAD
   algorithm allows for the computation of ciphertext segments
   (plaintext segments for decryption) in parallel, meaning that
   ciphertext segments are computed independently.

   Synonyms: Pipelineable.

   Examples: AES-GCM [D07], ChaCha20-Poly1305 [RFC8439], OCB [RFC7253],
   MGM [RFC9058], AEGIS [I-D.irtf-cfrg-aegis-aead].

   Further reading: [C20].

Bozhko                    Expires 14 April 2025                [Page 14]
Internet-Draft        Properties of AEAD algorithms         October 2024

4.4.5.  Setup-Free

   Definition: An AEAD algorithm's operations can be implemented in a
   way that using a new key incurs either no overhead or negligible
   overhead compared to the reuse of a previous key.  Overhead may
   involve additional computations or increased storage space, such as
   precomputing a key schedule for a block cipher.

   Examples: ChaCha20-Poly1305 [RFC8439], AEGIS
   [I-D.irtf-cfrg-aegis-aead], Ascon [DEMS21a][DEMS21b].

4.4.6.  Single Pass

   Definition: An AEAD algorithm encryption (decryption) operation can
   be implemented with a single pass over the plaintext (ciphertext).

   Examples: AES-GCM [D07], ChaCha20-Poly1305 [RFC8439], OCB [RFC7253],
   MGM [RFC9058], AEGIS [I-D.irtf-cfrg-aegis-aead].

4.4.7.  Static Associated Data Efficient

   Definition: An AEAD algorithm allows pre-computation for static (or
   repeating) associated data so that static associated data doesn't
   significantly contribute to the computational cost of encryption.

   Examples: AES-GCM [D07], ChaCha20-Poly1305 [RFC8439], OCB [RFC7253].

4.4.8.  Streamable

   Definition: An AEAD algorithm encryption (decryption) operation can
   be implemented with constant memory usage and a single one-direction
   pass over the plaintext (ciphertext), writing out the result during
   that pass.

   Synonyms: Online.

   Examples: AES-GCM [D07], ChaCha20-Poly1305 [RFC8439], OCB [RFC7253],
   MGM [RFC9058], AEGIS [I-D.irtf-cfrg-aegis-aead], Ascon
   [DEMS21a][DEMS21b].

   Applications: Real-time streaming protocols, resource-constrained
   devices.

   Notes: Blockwise security (see Section 4.3.1) and RUP integrity (see
   Section 4.3.10) might be relevant security properties for streamable
   AEAD algorithms in certain applications.

   Further reading: [HRRV15], [FJMV2004].

Bozhko                    Expires 14 April 2025                [Page 15]
Internet-Draft        Properties of AEAD algorithms         October 2024

5.  Security Considerations

   This document gives high-level definitions of AEAD properties.  For
   each security property, we provide an informational reference to a
   game-based security notion (or security notions if there are separate
   notions for integrity and confidentiality) that formalizes the
   property.  We only consider game-based notions and security
   properties that can be formalized using this approach.  However,
   there are different approaches to formalizing AEAD security, like the
   indifferentiability framework [BM18]; security in such notions should
   be studied separately.

   For some properties, examples of AEAD algorithms that provide them
   are given, with standardized AEAD algorithms preferred for commonly
   encountered properties.  However, for certain properties, only non-
   standardized algorithms exist.  Implementing such algorithms requires
   careful consideration, and it is advised to contact the algorithm
   designers for reference implementations and implementation
   guidelines.

   Every claimed security property of an AEAD algorithm MUST undergo
   security analysis within a relevant notion.  It's RECOMMENDED to use
   the security notions referenced in the document.  If an alternative
   notion is used, there MUST exist proof of equivalence or it SHOULD be
   indicated that a non-equivalent notion is used.  For security
   properties that extend adversarial capabilities, consideration of
   integrity and confidentiality separately may be relevant.  If the
   algorithm provides only one of these, that SHOULD be indicated.

   When specifying security requirements for an AEAD algorithm in an
   application, it SHOULD be indicated, for every required security
   property, whether only integrity or confidentiality is necessary.
   Additionally, for each security property, it SHOULD be specified
   whether an analysis in an alternative security notion is required.
   We also note that some additional properties come with trade-offs in
   terms of classical security and efficiency, and may only be supported
   in non-standardized or modified AEAD algorithms.  This immediately
   implies challenges in deployment and interoperability.  In an
   application, the requirements for additional AEAD properties SHOULD
   be highly motivated and justified, as should all trade-offs be
   carefully considered.

6.  IANA Considerations

   This document has no IANA actions.

7.  References

Bozhko                    Expires 14 April 2025                [Page 16]
Internet-Draft        Properties of AEAD algorithms         October 2024

7.1.  Normative References

   [D07]      Dworkin, M., "Recommendation for Block Cipher Modes of
              Operation: Galois/Counter Mode (GCM) and GMAC", NIST
              Special Publication 800-38D, DOI 10.6028/NIST.SP.800-38D,
              2007, <https://csrc.nist.gov/pubs/sp/800/38/d/final>.

   [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.rfc-editor.org/info/rfc2119>.

   [RFC5116]  McGrew, D., "An Interface and Algorithms for Authenticated
              Encryption", RFC 5116, DOI 10.17487/RFC5116, January 2008,
              <https://www.rfc-editor.org/info/rfc5116>.

   [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.rfc-editor.org/info/rfc8174>.

7.2.  Informative References

   [A14]      Andreeva, E., Bogdanov, A., Luykx, A., Mennink, B., Mouha,
              N., and K. Yasuda, "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,
              <https://doi.org/10.1007/978-3-662-45611-8_6>.

   [ABV21]    Andreeva, E., Bhati, A.S., and D. Vizár, "Nonce-misuse
              security of the SAEF authenticated encryption mode",
              Selected Areas in Cryptography: 27th International
              Conference, Halifax, NS, Canada (Virtual Event), October
              21-23, 2020, Revised Selected Papers 27. Springer
              International Publishing, 2021,
              DOI 10.1007/978-3-030-81652-0_20, 2021,
              <https://doi.org/10.1007/978-3-030-81652-0_20>.

   [ADGKLS22] Albertini, A., Duong, T., Gueron, S., Kölbl, S., Luykx,
              A., and S. Schmieg, "How to abuse and fix authenticated
              encryption without key commitment", 1st USENIX Security
              Symposium (USENIX Security 22), pp. 3291-3308. 2022, 2022.

Bozhko                    Expires 14 April 2025                [Page 17]
Internet-Draft        Properties of AEAD algorithms         October 2024

   [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,
              <https://doi.org/10.1007/978-3-319-63697-9_1>.

   [B13]      Bernstein, D. J., "Re: secret message numbers", Message in
              Google group on cryptographic competitions, October 2013.,
              2013, <https://groups.google.com/d/msg/crypto-
              competitions/n5ECGwYr6Vk/bsEfPWqSAU4J>.

   [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,
              <https://doi.org/10.1007/978-3-030-56784-2_13>.

   [BBCLNSS21]
              Bhaumik, R., Bonnetain, X., Chailloux, A., Leurent, G.,
              Naya-Plasencia, M., Schrottenlohe, A., and Y. Seurin,
              "QCB: Efficient Quantum-Secure Authenticated Encryption",
              Advances in Cryptology – ASIACRYPT 2021. ASIACRYPT 2021.
              Lecture Notes in Computer Science(), vol 13090. Springer,
              Cham., DOI 10.1007/978-3-030-92062-3_23, 2021,
              <https://doi.org/10.1007/978-3-030-92062-3_23>.

   [BC09]     Black, J. and M. Cochran, "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,
              <https://doi.org/10.1007/978-3-642-03317-9_21>.

   [BH22]     Bellare, M. and V.T. Hoang, "Efficient schemes for
              committing authenticated encryption", Advances in
              Cryptology – EUROCRYPT 2022. EUROCRYPT 2022. Lecture Notes
              in Computer Science, vol 13276. Springer, Cham.,
              DOI 10.1007/978-3-031-07085-3_29, 2022,
              <https://doi.org/10.1007/978-3-031-07085-3_29>.

   [BHT18]    Bose, P., Hoang, V.T., and S. Tessaro, "Revisiting AES-
              GCM-SIV: multi-user security, faster key derivation, and
              better bounds", Annual International Conference on the
              Theory and Applications of Cryptographic Techniques, pp.

Bozhko                    Expires 14 April 2025                [Page 18]
Internet-Draft        Properties of AEAD algorithms         October 2024

              468-499. Cham: Springer International Publishing, 2018,
              DOI 10.1007/978-3-319-78381-9_18, 2018,
              <https://doi.org/10.1007/978-3-319-78381-9_18>.

   [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, <https://doi.org/10.1007/3-540-45473-X_9>.

   [BM18]     Barbosa, M. and P. Farshim, "Indifferentiable
              authenticated encryption", Advances in Cryptology–CRYPTO
              2018: 38th Annual International Cryptology Conference,
              Santa Barbara, CA, USA, August 19–23, 2018, Proceedings,
              Part I 38, pp. 187-220. Springer International Publishing,
              2018., DOI 10.1007/978-3-319-96884-1_7, 2018,
              <https://doi.org/10.1007/978-3-319-96884-1_7>.

   [BMOS17]   Barwell, G., Martin, D.P., Oswald, E., and M. Stam,
              "Authenticated encryption in the face of protocol and side
              channel leakage.", Advances in Cryptology – ASIACRYPT
              2017. ASIACRYPT 2017. Lecture Notes in Computer Science,
              vol 10624. Springer, Cham,
              DOI 10.1007/978-3-319-70694-8_24, 2017,
              <https://doi.org/10.1007/978-3-319-70694-8_24>.

   [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,
              <https://doi.org/10.1007/s00145-008-9026-x>.

   [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,
              <https://doi.org/10.1007/978-3-030-26948-7_9>.

   [BPPS17]   Berti, F., Pereira, O., Peters, T., and F.X. Standaert,
              "On leakage-resilient authenticated encryption with
              decryption leakages", IACR Transactions on Symmetric
              Cryptology (2017): 271-293,
              DOI 10.13154/tosc.v2017.i3.271-293, 2017,
              <https://doi.org/10.13154/tosc.v2017.i3.271-293>.

Bozhko                    Expires 14 April 2025                [Page 19]
Internet-Draft        Properties of AEAD algorithms         October 2024

   [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,
              <https://doi.org/10.1007/978-3-662-53018-4_10>.

   [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,
              <https://doi.org/10.13154/tosc.v2019.i4.81-118>.

   [CJRR99]   Chari, S., Jutla, C.S., Rao, J.R., and P. Rohatgi,
              "Towards sound approaches to counteract power-analysis
              attacks.", Advances in Cryptology—CRYPTO'99: 19th Annual
              International Cryptology Conference Santa Barbara,
              California, USA, August 15–19, 1999 Proceedings 19, pp.
              398-412. Springer Berlin Heidelberg, 1999.,
              DOI 10.1007/3-540-48405-1_26, 1999,
              <https://doi.org/10.1007/3-540-48405-1_26>.

   [CR22]     Chan, J. and P. Rogaway, "On Committing Authenticated-
              Encryption", Computer Security – ESORICS 2022. ESORICS
              2022. Lecture Notes in Computer Science, vol 13555.
              Springer, Cham., DOI 10.1007/978-3-031-17146-8_14, 2022,
              <https://doi.org/10.1007/978-3-031-17146-8_14>.

   [DEMS21a]  Dobraunig, C., Eichlseder, M., Mendel, F., and M.
              Schläffer, "Ascon v1.2: Lightweight Authenticated
              Encryption and Hashing", Journal of Cryptology 34 (2021):
              1-42., DOI 10.1007/s00145-021-09398-9, 2021,
              <https://doi.org/10.1007/s00145-021-09398-9>.

   [DEMS21b]  Dobraunig, C., Eichlseder, M., Mendel, F., and M.
              Schläffer, "Ascon v1.2", Submission to the NIST LWC
              Competition, 2021.

   [DGGP21]   Degabriele, J.P., Govinden, J., Günther, F., and K.
              Paterson, "The security of ChaCha20-Poly1305 in the multi-
              user setting", In Proceedings of the 2021 ACM SIGSAC
              Conference on Computer and Communications Security, pp.
              1981-2003. 2021., DOI 10.1145/3460120.3484814, 2021,
              <https://doi.org/10.1145/3460120.3484814>.

Bozhko                    Expires 14 April 2025                [Page 20]
Internet-Draft        Properties of AEAD algorithms         October 2024

   [EV16]     Endignoux, G. and D. Vizár, "Linking Online Misuse-
              Resistant Authenticated Encryption and Blockwise Attack
              Models", IACR Transactions on Symmetric Cryptology,
              DOI 10.13154/TOSC.V2016.I2.125-144, 2016,
              <https://doi.org/10.13154/TOSC.V2016.I2.125-144>.

   [FFL12]    Fleischmann, E., Forler, C., and S. Lucks, "McOE: A family
              of almost foolproof on-line authenticated encryption
              schemes", Fast Software Encryption: 19th International
              Workshop, FSE 2012, Washington, DC, USA, March 19-21,
              2012. Revised Selected Papers. Springer Berlin Heidelberg,
              2012, DOI 10.1007/978-3-642-34047-5_12, 2012,
              <https://doi.org/10.1007/978-3-642-34047-5_12>.

   [FJMV2004] Fouque, 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,
              <https://doi.org/10.1007/978-3-540-24654-1_11>.

   [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,
              <https://doi.org/10.1007/978-3-319-59870-3_2>.

   [FOR17]    Farshim, P., Orlandi, C., and R. Rosie, "Security 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,
              <https://doi.org/10.13154/tosc.v2017.i1.449-473>.

   [G17]      Gagliardoni, T., "Quantum Security of Cryptographic
              Primitives", Ph.D. Thesis, Technische Universität
              Darmstadt, 2017,
              <https://tuprints.ulb.tu-darmstadt.de/6019/>.

   [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,
              <https://doi.org/10.1007/978-3-319-63697-9_3>.

Bozhko                    Expires 14 April 2025                [Page 21]
Internet-Draft        Properties of AEAD algorithms         October 2024

   [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, <https://doi.org/10.1007/978-3-030-30530-7_8>.

   [HKR2015]  Hoang, VT., Krovetz, T., and P. Rogaway, "Robust
              Authenticated-Encryption AEZ and the Problem That It
              Solves", Advances in Cryptology -- EUROCRYPT 2015.
              EUROCRYPT 2015. Lecture Notes in Computer Science, vol
              9056. Springer, Berlin, Heidelberg.,
              DOI 10.1007/978-3-662-46800-5_2, 2015,
              <https://doi.org/10.1007/978-3-662-46800-5_2>.

   [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,
              <https://doi.org/10.1007/978-3-662-47989-6_24>.

   [HTT18]    Hoang, V.T., Tessaro, S., and A. Thiruvengadam, "The
              multi-user security of GCM, revisited: Tight bounds for
              nonce randomization", Proceedings of the 2018 ACM SIGSAC
              Conference on Computer and Communications Security, pp.
              1429-1440. 2018, DOI 10.1145/3243734.3243816, 2018,
              <https://doi.org/10.1145/3243734.3243816>.

   [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-09, 9 October 2024,
              <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-
              aead-limits-09>.

   [I-D.irtf-cfrg-aegis-aead]
              Denis, F. and S. Lucas, "The AEGIS Family of Authenticated
              Encryption Algorithms", Work in Progress, Internet-Draft,
              draft-irtf-cfrg-aegis-aead-12, 23 September 2024,
              <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-
              aegis-aead-12>.

   [JMV2002]  Joux, A., Martinet, G., and F. Valette, "Blockwise-
              Adaptive Attackers Revisiting the (In)Security of Some
              Provably Secure Encryption Modes: CBC, GEM, IACBC",

Bozhko                    Expires 14 April 2025                [Page 22]
Internet-Draft        Properties of AEAD algorithms         October 2024

              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,
              <https://doi.org/10.1007/3-540-45708-9_2>.

   [JNPS21]   Jean, M., Nikolić, I., Peyrin, T., and Y. Seurin, "The
              Deoxys AEAD family", Journal of Cryptology 34, no. 3
              (2021): 31., DOI 10.1007/s00145-021-09397-w, 2021,
              <https://doi.org/10.1007/s00145-021-09397-w>.

   [KLLNP16]  Menda, M., Leurent, G., Leverrier, A., and M. Naya-
              Plasencia, "Quantum Differential and Linear
              Cryptanalysis", IACR Transactions on Symmetric Cryptology,
              2016(1), 71–94., DOI 10.13154/tosc.v2016.i1.71-94, 2021,
              <https://doi.org/10.13154/tosc.v2016.i1.71-94>.

   [LGR21]    Len, J., Grubbs, P., and T. Ristenpart, "Partitioning
              Oracle Attacks", 30th USENIX Security Symposium (USENIX
              Security 21), 195--212, 2021.

   [LMP17]    Luykx, A., Mennink, B., and K. Paterson, "Analyzing multi-
              key security degradation", Conference on the Theory and
              Applications of Cryptology and Information Security, Hong
              Kong, China, December 3-7, 2017, Proceedings, Part II 23,
              pp. 575-605. Springer International Publishing, 2017.,
              DOI 10.1007/978-3-319-70697-9_20, 2017,
              <https://doi.org/10.1007/978-3-319-70697-9_20>.

   [M05]      McGrew, D., "Efficient authentication of large, dynamic
              data sets using Galois/Counter Mode (GCM).", Third IEEE
              International Security in Storage Workshop (SISW'05), pp.
              6-pp. IEEE, 2005., DOI 10.1109/SISW.2005.3, 2005,
              <https://doi.org/10.1109/SISW.2005.3>.

   [MBTM17]   McKay, K., Bassham, L., Turan, MS., and N. Mouha, "Report
              on Lightweight Cryptography", DOI 10.6028/NIST.IR.8114,
              2017, <https://doi.org/10.6028/NIST.IR.8114>.

   [MLGR23]   Menda, S., Julia, J., Grubbs, P., and T. Ristenpart,
              "Context Discovery and Commitment Attacks: How to Break
              CCM, EAX, SIV, and More", Advances in Cryptology –
              EUROCRYPT 2023. EUROCRYPT 2023. Lecture Notes in Computer
              Science, vol 14007. Springer, Cham.,
              DOI 10.1007/978-3-031-30634-1_13, 2023,
              <https://doi.org/10.1007/978-3-031-30634-1_13>.

Bozhko                    Expires 14 April 2025                [Page 23]
Internet-Draft        Properties of AEAD algorithms         October 2024

   [R02]      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,
              <https://doi.org/10.1145/586110.586125>.

   [RFC4303]  Kent, S., "IP Encapsulating Security Payload (ESP)",
              RFC 4303, DOI 10.17487/RFC4303, December 2005,
              <https://www.rfc-editor.org/info/rfc4303>.

   [RFC7253]  Krovetz, T. and P. Rogaway, "The OCB Authenticated-
              Encryption Algorithm", RFC 7253, DOI 10.17487/RFC7253, May
              2014, <https://www.rfc-editor.org/info/rfc7253>.

   [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,
              <https://www.rfc-editor.org/info/rfc8221>.

   [RFC8439]  Nir, Y. and A. Langley, "ChaCha20 and Poly1305 for IETF
              Protocols", RFC 8439, DOI 10.17487/RFC8439, June 2018,
              <https://www.rfc-editor.org/info/rfc8439>.

   [RFC8446]  Rescorla, E., "The Transport Layer Security (TLS) Protocol
              Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018,
              <https://www.rfc-editor.org/info/rfc8446>.

   [RFC8452]  Gueron, S., Langley, A., and Y. Lindell, "AES-GCM-SIV:
              Nonce Misuse-Resistant Authenticated Encryption",
              RFC 8452, DOI 10.17487/RFC8452, April 2019,
              <https://www.rfc-editor.org/info/rfc8452>.

   [RFC8645]  Smyshlyaev, S., Ed., "Re-keying Mechanisms for Symmetric
              Keys", RFC 8645, DOI 10.17487/RFC8645, August 2019,
              <https://www.rfc-editor.org/info/rfc8645>.

   [RFC9000]  Iyengar, J., Ed. and M. Thomson, Ed., "QUIC: A UDP-Based
              Multiplexed and Secure Transport", RFC 9000,
              DOI 10.17487/RFC9000, May 2021,
              <https://www.rfc-editor.org/info/rfc9000>.

   [RFC9058]  Smyshlyaev, S., Ed., Nozdrunov, V., Shishkin, V., and E.
              Griboedova, "Multilinear Galois Mode (MGM)", RFC 9058,
              DOI 10.17487/RFC9058, June 2021,
              <https://www.rfc-editor.org/info/rfc9058>.

Bozhko                    Expires 14 April 2025                [Page 24]
Internet-Draft        Properties of AEAD algorithms         October 2024

   [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,
              <https://doi.org/10.1007/11761679_23>.

   [S04]      Shrimpton, T., "A Characterization of Authenticated-
              Encryption as a Form of Chosen-Ciphertext Security",
              Cryptology ePrint Archive, Paper 2004/272, 2004,
              <https://eprint.iacr.org/2004/272>.

   [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,
              <https://doi.org/10.1007/978-3-319-31301-6_23>.

   [YSS23]    Naito, Y., Sasaki, Y., and T. Sugawara, "Committing
              Security of Ascon: Cryptanalysis on Primitive and Proof on
              Mode", IACR Transactions on Symmetric Cryptology 2023, no.
              4 (2023): 420-451, DOI 10.46586/tosc.v2023.i4.420-451,
              2023, <https://doi.org/10.46586/tosc.v2023.i4.420-451>.

Appendix A.  AEAD Algorithms with Additional Functionality

   In this section, we briefly discuss AEAD algorithms that provide
   additional functionality.  As noted in Section 4.1, each additional
   functionality requires a redefinition of the conventional AEAD
   interface; thus, each additional functionality property defines a new
   class of cryptographic algorithms.

   Most importantly, for every Additional Functionality AEAD class,
   conventional security properties must be redefined concerning the
   targeted additional functionality and the new interface.  Although it
   might be possible to consider a particular Additional Functionality
   AEAD algorithm as a conventional AEAD algorithm and study it for the
   conventional confidentiality and integrity, security (or insecurity)
   in that sense won't be sufficient to label that algorithm as a secure
   (or insecure) Additional Functionality AEAD.  Only security in the
   sense of the redefined conventional properties would suffice.

   For the examples given in this section, we leave it out of scope how
   to concretely redefine conventional security for these classes; we
   only briefly describe the additional functionality they offer and
   provide further references.

Bozhko                    Expires 14 April 2025                [Page 25]
Internet-Draft        Properties of AEAD algorithms         October 2024

A.1.  Incremental Authenticated Encryption

   Definition: An AEAD algorithm allows re-encrypting and authenticating
   a message (associated data and a plaintext pair), which only partly
   differs from some previous message, faster than processing it from
   scratch.

   Examples: Incremental AEAD algorithm of [SY16].

   Security notion: Privacy, Authenticity [SY16].

   Notes: The interface of an incremental AEAD algorithm is usually
   expanded, when compared with conventional AEAD, with several
   operations, which perform different types of updates.  For example,
   one can consider such operations as "Append" or "Chop", which provide
   a straightforward additional functionality.  A comprehensive
   definition of an incremental AEAD interface is provided in [SY16].

   Further reading: [SY16], [M05], [BKY02].

A.2.  Robust Authenticated Encryption

   Definition: An AEAD algorithm allows users to choose a desired
   ciphertext expansion (the difference between the length of plaintext
   and corresponding ciphertext) along with an input to the encryption
   operation.  This feature enables the regulation of desired data
   integrity guarantees, which depend on ciphertext expansion, for each
   particular application while using the same algorithm implementation.

   Examples: AEZ [HKR2015].

   Security notion: RAE [HKR2015].

   Notes: The security goal of robust AEAD algorithms is to ensure the
   best possible security, even with small ciphertext expansion
   (referred to as stretch).  For instance, analyzing any AEAD algorithm
   with a one-byte stretch for conventional integrity reveals
   insecurity, as the probability of forging a ciphertext is no less
   than 1/256.  Nonetheless, from the robust AEAD perspective, an
   algorithm with such forgery probability for a one-byte ciphertext
   expansion is secure, representing the best achievable security in
   that scenario.

   Further reading: [HKR2015].

Bozhko                    Expires 14 April 2025                [Page 26]
Internet-Draft        Properties of AEAD algorithms         October 2024

Acknowledgments

   This document benefited greatly from the comments received from the
   CFRG community, for which we are very grateful.  We would also like
   to extend special appreciation to Liliya Akhmetzyanova, Evgeny
   Alekseev, Alexandra Babueva, Frank Denis, Kirill Kutsenok, Sergey
   Kyazhin, Samuel Lucas, Grigory Marshalko, Christopher Patton, and
   Christopher Wood for their thoughtful comments, proposals, and
   discussions.

Author's Address

   Andrey Bozhko (editor)
   CryptoPro
   Email: andbogc@gmail.com

Bozhko                    Expires 14 April 2025                [Page 27]