domain: info math

text:
Henri Gilbert

Rachelle Heim Boissier

Louiza Khati

Yann Rotella

Generic Attack on Duplex-Based AEAD Modes using Random Function Statistics

Keywords: Cryptanalysis, Symmetric cryptography, AEAD, Duplexbased constructions, NIST lightweight competition, Xoodyak, Random functions

Duplex-based authenticated encryption modes with a sufficiently large key length are proven to be secure up to the birthday bound 2 c 2 , where c is the capacity. However this bound is not known to be tight and the complexity of the best known generic attack, which is based on multicollisions, is much larger: it reaches 2 c α where α represents a small security loss factor. There is thus an uncertainty on the true extent of security beyond the bound 2 c 2 provided by such constructions. In this paper, we describe a new generic attack against several duplex-based AEAD modes. Our attack leverages random functions statistics and produces a forgery in time complexity O(2 3c 4 ) using negligible memory and no encryption queries. Furthermore, for some duplex-based modes, our attack recovers the secret key with a negligible amount of additional computations. Most notably, our attack breaks a security claim made by the designers of the NIST lightweight competition candidate Xoodyak. This attack is a step further towards determining the exact security provided by duplex-based constructions.

Introduction

Authenticated Encryption (AE), which allows to encrypt and authenticate a plaintext message in a combined way, is one of the main workhorses of symmetric cryptography. AE often offers the option to authenticate, in addition to the plaintext message, some extra data which, unlike the plaintext, are transmitted unencrypted. AE is then renamed Authenticated Encryption with Associated Data (AEAD). A considerable research effort was devoted during the last years to the design and analysis of efficient and secure AEAD algorithms. Examples of AEAD mechanisms largely deployed over the Internet are AES-GCM and Chacha20-Poly1305. In 2014-2019, the three-round process of the CAESAR competition for authenticated encryption resulted in the selection of a portfolio of six AEAD mechanisms chosen to address the needs of the three following use cases: lightweight applications, high-performance applications and provision of defense-in-depth features, e.g. nonce misuse resistance. Another symmetric algorithms selection initiative, the ongoing NIST lightweight cryptography standardization process, aims at selecting (families of) algorithms suitable for use in constrained environment that comprise at least an AEAD mechanism and optionally a cryptographic hashing mechanism. The process was launched in 2018 and has now reached its third round, where ten finalists are still being evaluated.

Most existing AEAD algorithms are either block cipher-based or permutationbased. In the first case, they result from the application of a suitable mode of operation to a block cipher or a tweakable block cipher. In the second case, they consist in the instantiation of a keyed mode of operation with a public permutation. In this paper, we focus on so-called duplex-based keyed modes. Seminal examples of such modes are SpongeWrap and MonkeyDuplex, both introduced by Bertoni, Daemen, Peeters and Van Assche [START_REF] Bertoni | Duplexing the sponge: Single-pass authenticated encryption and other applications[END_REF][START_REF] Bertoni | Permutation-based encryption, authentication and authenticated encryption[END_REF]. Duplex-based modes can be viewed as an adaptation to the AEAD context of the Sponge construction for hash functions introduced by the same authors in [START_REF] Bertoni | Sponge functions[END_REF][START_REF] Bertoni | On the indifferentiability of the sponge construction[END_REF]. After an initialization phase allowing to derive a b-bit state from a key and an IV value, they essentially iterate calls to a key-less public permutation P of the state space {0, 1} b in alternance with an injection and/or extraction of data blocks on/from a dedicated r-bit part (r < b) of the current state value in order to absorb additional data, encrypt and absorb the plaintext, and produce an authentication tag. 1 The sizes r and c = b -r bits of the state parts affected (resp. unaffected) by data injections or extractions are named the rate and the capacity. The corresponding state parts are referred to as the outer and the inner state.

The security of duplex-based constructions has been extensively studied during the last decade. Let us denote the total time complexity of an attack by T = σ e + σ d + q P + t extra-op , where σ e and σ d respectively represent the number of online calls to P caused by the adversary's encryption requests and forgery attempts and q P represents the number of offline queries to P or its inverse. The last term t extra-op represents the extra computations not taken into account in σ e + σ d + q P , e.g. computations of primitives involved in the initialization and finalization, basic read/write operations in memory, random samplings. It is measured as an equivalent number of P computations. 2 Let us further denote by q d the number of forgery attempts of the adversary. The initial security arguments for duplex constructions, which leveraged the indifferentiability of the sponge construction for hash functions, only allowed to guarantee the security of the duplex constructions as long as T ≪ min{2 c 2 , 2 κ } and q d ≪ 2 τ , where κ showed that in the nonce-respecting setting, the security of a series of duplex constructions can be ensured beyond the birthday bound 2 c 2 , namely as long as

T ≪ min{2 b 2 , 2 c α , 2 κ } and q d ≪ 2 τ , (1)
where α represents a small constant upper bounded by r in [START_REF] Jovanovic | Beyond 2 c/2 security in sponge-based authenticated encryption modes[END_REF] and a tighter, substantially smaller constant in [START_REF] Jovanovic | Beyond conventional security in sponge-based authenticated encryption modes[END_REF]. The detail of the security proofs sections of [START_REF] Jovanovic | Beyond 2 c/2 security in sponge-based authenticated encryption modes[END_REF][START_REF] Jovanovic | Beyond conventional security in sponge-based authenticated encryption modes[END_REF] indicates however that the bounds (1) are only valid under the assumption that σ d is strongly limited: if one wants to avoid implicit assumptions about σ d , the bounding conditions (1) must be replaced by the more complete (though still simplified) conditions:

T ≪ min{2 b 2 , 2 c α , 2 c σ d , 2 κ } and q d ≪ 2 τ . (2)
Unlike the conditions (1), the complete bounding conditions (2) can hardly be considered as 'beyond-birthday bounds'. For σ d ≥ 2 c 2 , the condition T ≪ 2 c σ d of (2) indeed implies T ≪ 2 c 2 . Thus, the security of the considered duplex-based constructions without assumptions on σ d can only be guaranteed as long as the birthday condition T ≪ 2 c 2 is met. The bounding conditions [START_REF] Aumasson | NORX v2. Submission to the Caesar competition[END_REF] were used for dimensioning the family of duplex AEADs NORX, and led since 2014 to several other AEAD design proposals based on duplex-like constructions with a claimed security level strictly larger than c 2 . Similar bounds were shown to still hold when instead of limiting the size of injected and extracted data blocks to r bits, one only limits the size of extracted data blocks to r bits but full-state data injections are permitted [START_REF] Mennink | Security of full-state keyed sponge and duplex: Applications to authenticated encryption[END_REF]. This leads to AEAD proposals where the efficiency of the associated data absorption phase is increased. A generalisation of the full-state keyed duplex of [START_REF] Mennink | Security of full-state keyed sponge and duplex: Applications to authenticated encryption[END_REF] with multi-user support, accompanied by a refined security analysis, was published in [START_REF] Daemen | Full-state keyed duplex with built-in multi-user support[END_REF].

Generic attacks on duplex-based constructions. The best currently known generic attacks on duplex-based constructions are based on multicollisions. These attacks match the security bound 2 c α where α represents a small security loss factor as stated before. They are presented in detail in [START_REF] Jovanovic | Beyond conventional security in sponge-based authenticated encryption modes[END_REF] and can be roughly outlined as follows. First, the adversary submits sufficiently many calls to an encryption oracle in order to find a multicollision among the outer state values of a number ρ of states. Once this has been achieved, an exhaustive search for a c-bit value matching the inner state value of one of these ρ states is likely to succeed after about 2 c ρ trials.

Our contribution. The end of the former discussion on the security of duplexbased constructions showed that in situations where the possibility of forgery attempts of non-negligible data complexity σ d is not precluded, the complete bounding conditions (2) only prevent the existence of generic attacks of total complexity T ≪ 2 ). We rely on the analysis of random function statistics to design a two-phase forgery attack with a precomputation phase of time complexity O(2 3c 4 ) essentially equal to q P and an actual forgery phase of time complexity O(2 3c 4 ) essentially equal to σ d . The value σ d can also be viewed as the data complexity of the attack measured in ciphertext blocks. The attack requires no encryption queries, i.e. σ e = 0, and t extra-op is negligible compared to q P and σ d . For some of these constructions, our attack recovers the secret key.

Our attack takes advantage of the following property shared by several authenticated encryption modes based on the duplex construction: for a ciphertext built by concatenating a fixed block multiple times, the decryption of a message consists in the iteration of a public function with domain and co-domain F c 2 . This public function is fully determined by the value of the ciphertext block. We are therefore able to precompute some of its parameters offline. Forgery strategies that just assume a "near to average" behaviour of the iterated function, e.g a cycle length of the path generated by a random point of {0, 1} c close to the expected value π2 c /8, do not seem to lead to forgery attack complexities better than O(2 c ). We show that however, the following two-phase attack strategy allows an adversary to produce an existential forgery with a success probability close to 1 and a total (online and offline) computation time T = O(2 3c 4 ). 1) In an offline phase, a significant amount O(2 3c 4 ) of precomputation is dedicated to the detection of a c-bit to c-bit function that possesses exceptional characteristics that exponentially deviate from an average behaviour, thus rendering its use in a forgery attack more efficient. 2) In an online phase, the iteration of the function identified in the offline phase is used to produce forgery attempts whose success probability is exceptionally high.

In slightly more detail, the offline phase aims at selecting a ciphertext block that determines a function whose graph possesses a large component in which all paths are terminated by the same exceptionally small cycle, of length at most a small predefined multiple of 2 c 4 . This is shown to imply that for long ciphertexts obtained by repeating the selected ciphertext block, the tag is the image of one of the values of the former small cycle by a known function with a probability close to 1. This in turn allows to mount a forgery attack of offline, online and total time complexity O(2 3c 4 ). The precomputation phase needs to be run only once to break the same construction with as many different keys as desired. Further, we can adjust the trade-off between the precomputation phase and the online phase in order to bring the complexity of the latter closer to O(2 c 2 ) at the expense of significantly increasing the complexity of the former.

Previously published generic attacks against hash-based MACs or hash functions also rely on the statistics of random functions [START_REF] Peyrin | Generic related-key attacks for HMAC[END_REF][START_REF] Leurent | New generic attacks against hash-based MACs[END_REF][START_REF] Peyrin | Generic universal forgery attack on iterative hash-based MACs[END_REF][START_REF] Bao | Functional graphs and their applications in generic attacks on iterated hash constructions[END_REF]. Such attacks also model, as the AEAD attack introduced here, one function that the considered construction allows to iterate as a random function. Yet, while previous attacks generally assume and exploit a "near to average" behaviour of a function selected at random, an essential feature of the attack presented here is that it selects and leverages instances of a function whose behaviour exceptionally deviates from average.

Our attack is applicable to several duplex-based modes such as monkeyWrap, monkeyDuplex or Motorist. Most notably, our attack is applicable to Cyclist, the mode of the Lightweight Cryptography NIST competition finalist Xoodyak [START_REF] Daemen | Xoodyak, a lightweight cryptographic scheme[END_REF]. With a key recovery attack of complexity 2 148 applications of the state update function Xoodoo, we break the claim of achieving 184-bit security against plaintext recovery and forgery attacks made by the designers in [START_REF] Daemen | Xoodyak, a lightweight cryptographic scheme[END_REF]Corollary 2,p. 72]. Note that this does not threaten the 112-bit security level required by the NIST. Our results are detailed in Section 5 and displayed in Table 5.

Organization. The rest of this paper is organized as follows. Section 2 introduces definitions and results related to the statistics of random functions that are relevant for our attack and defines a 'vanilla' duplex-based AEAD mode that only captures those features of duplex-based constructions that are essential to understand our attack. Section 3 presents our attack and analyses its performance using the vanilla mode of Section 2 as the target in order to simplify its presentation. Section 4 presents experimental validations of essential features of the attack based on small scale implementations. Section 5 shows that the attack of Section 3 is applicable to several real-life duplex modes with minor adaptations. Section 5 also discusses variations encountered in AEADs such as Beetle [START_REF] Chakraborti | Beetle family of lightweight and secure authenticated encryption ciphers[END_REF] or Ascon [START_REF] Dobraunig | Ascon v1.2: Lightweight authenticated encryption and hashing[END_REF] that, on the other hand, prevent the attack.

Preliminaries

In this section, we start by introducing key definitions and results related to the statistics of random functions. Next, we describe a simplified duplex-based authenticated encryption mode on which we will rely to describe our attack. This is followed by a short subsection on the security model on which we rely.

Preliminaries on random functions

Let F n be the set of all functions which map a finite set of size n ∈ N * to itself. Without loss of generality, we consider the set {1, . . . , n}. Each function f in F n determines a directed graph G(f ) in which a vertex goes from node i to node j, i, j ∈ {1, . . . , n}, if and only if f (i) = j [START_REF] Moon | Counting Labelled Trees[END_REF][START_REF] Flajolet | Analytic Combinatorics[END_REF]. In the following, for simplicity reasons, we say that a node belongs to the graph of a function when it belongs to the set of nodes of this graph. We use the term "random function in F n " to refer to a function selected uniformly at random in the set F n .

For any f in F n and any node x in G(f ), we can iterate f and consider the set of successors of x

S(x) = {f i (x) | 0 ≤ i ≤ n -1} .
We denote by s(x) the size of this set. Since the graph has a finite number of nodes, the sequence {f i (x)} i≥0 is eventually periodic. Graphically, it thus corresponds to a path linked to a cycle defined as

C(x) = {f i (x) | ∃j > 0, f i (x) = f i+j (x)} .
We denote by µ(x) = #C(x) the length of this cycle or cycle length and by λ(x) = s(x) -#C(x) the length of this path or tail length. The tail length λ(x) is the smallest integer i such that f i (x) ∈ C(x). The set of all nodes y ∈ G(f ) such that C(y) = C(x) forms a connected component. Since all nodes in the same connected component have the same cycle, the cycle of a component is well-defined.

Our cryptanalysis relies on the attacker's ability to find functions which have a large component with a small cycle. We formally characterize what should be understood by "large component with a small cycle" later on. To do so, we will need the two following definitions.

Definition 1 (ν-component). Let 0 < ν < 1 2 . A ν-component is a component that has a cycle of size at most n 1 2 -ν . Definition 2 ((s, ν)-component). Let 0 < ν < 1 2 , 0 < s < 1. A (s, ν)- component is a ν-component
whose size is greater or equal to ns.

In order to estimate the complexity and success probability of our attack, we rely on the statistical analysis of random functions. Such an analysis has been extensively conducted in combinatorics [START_REF] Harris | Probability Distributions Related to Random Mappings[END_REF][START_REF] Moon | Counting Labelled Trees[END_REF][START_REF] Delaurentis | Components and cycles of a random function[END_REF][START_REF] Flajolet | Random mapping statistics[END_REF][START_REF] Flajolet | Analytic Combinatorics[END_REF]. In this paper, we will need the three following results.

Expectancy of cycle length and tail length for a random point [START_REF] Flajolet | Random mapping statistics[END_REF]. For a random node x in the graph of a random function f ∈ F n , Flajolet and Odlyzko have computed the asymptotic form of the expectancy of the cycle length µ(x) and tail length λ(x) using generating functions. They obtained an expectancy of πn 8 for both.

Probability for a random point to belong to a ν-component [START_REF] Harris | Probability Distributions Related to Random Mappings[END_REF]. For a random node x belonging to the graph of a random function f ∈ F n , Harris shows that the probability that µ(x) is smaller than n 1 2 -ν is asymptotically

p ν = 1 -e -1 2n 2ν + √ 2π n ν 1 -ϕ(n -ν ) = √ 2π 2n ν + O 1 n 2ν
where ϕ(y) = y -∞ (2π) -1 2 e -1 2 x 2 dx. This corresponds to the probability for a random node x of the graph of a random function to belong to a ν-component. For example, for ν = 1 4 and c a positive integer such that n

= 2 c , p ν = √ 2π 2 ×2 -c 4 .
Probability for a random function to have a (s, ν)-component [START_REF] Delaurentis | Components and cycles of a random function[END_REF].

For a random f ∈ F n , the probability p s,ν that G(f ) has a (s, ν)-component has been estimated by DeLaurentis in a paper published at Crypto 1987 [START_REF] Delaurentis | Components and cycles of a random function[END_REF]. It is shown to be

p s,ν = 2(1 -s) πs n -ν [1 + O (r n (s))]
where

r n (s) = s -2 n -1 2 -3ν + s -1 2 n -ν + n -1 3 . Thus, p s,ν ≈ 2(1-s)
πs n -ν . For example, if we take ν = 1 4 , s = 0.65 as in Section 3.6, and c a positive integer such that n = 2 c , p s,ν ≃ 0.6 × 2 -c 4 .

Probability for a random point to belong to its component's cycle after l -1 applications of f . Let x be a random point of a random function.

Harris [START_REF] Harris | Probability Distributions Related to Random Mappings[END_REF] gives the asymptotic density function of the number of successors s(x). More precisely, he provides the asymptotic density function

f 1 of s √ n for x > 0 f 1 (x) = xe -x 2 2 .
For l a positive integer, let p l be the probability that f l-1 (x) is in the cycle, that is, the probability that λ(x) ≤ l -1. Since the number of successors is greater than the tail length, p l is greater or equal to the probability for x to have strictly less than l successors. Thus, we have

p l ≥ 1 -e -l 2 2n .
Notational conventions. For simplicity and readability reasons, when it comes to estimates resulting from statistics on random functions, we will use the sign "≤" where it would be more rigorous to use the smaller or equivalent sign "⪅" in the rest of the paper.

Description of a vanilla duplex-based AEAD mode

The duplex construction was designed by the Keccak team as a tool to build authenticated encryption modes [START_REF] Bertoni | Duplexing the sponge: Single-pass authenticated encryption and other applications[END_REF][START_REF] Bertoni | Cryptographic sponge functions[END_REF]. The first proposal of such a mode is SpongeWrap [START_REF] Bertoni | Duplexing the sponge: Single-pass authenticated encryption and other applications[END_REF], published in 2011. Today, many modes are based on this construction. In this paper, we define the simplified authenticated encryption mode DuplexAEAD. DuplexAEAD shares its structure with the modes of several duplex-based AEAD schemes. This mode is not meant to be used in practice. It is defined for readability reasons: its sole purpose is to make the description of our attack simpler. We show in Section 5 how our attack can be adapted to several real-life duplex-based modes.

DuplexAEAD is instantiated with a permutation P which operates on a b-bit state S divided into two parts. The first r bits of the state form the outer state S, whilst the next c = b -r bits form the inner state S. The state can thus be written as S = S|| S. As stated in Section 1, the parameter r is called the rate and the parameter c is called the capacity. DuplexAEAD also involves two other public functions, namely, an initialisation function P init and a finalisation function P f inal . The encryption algorithm E takes as input a κ-bit key K, a η-bit nonce N , a plaintext M and associated data A of variable length and returns a ciphertext C and a τ -bit tag T . The decryption algorithm D takes as input (K, N, A, C, T ) and returns the plaintext M if the tag is valid. Otherwise, it returns ⊥.

We assume for simplicity reasons that the length in bits of the plaintexts processed by DuplexAEAD is always divisible by r. 4 Thus, any plaintext M can be split into r-bit blocks,

M = M 0 || • • • ||M l-1
, where l is the plaintext length in number of r-bit blocks. The ciphertext's length is equal to the plaintext's length, and can thus also be written

C = C 0 || • • • ||C l-1 .
The mode works as follows (see Figure 1): Initial phase. The encryption and decryption algorithms start by an initial phase. The key, the nonce and the associated data are processed by the initialisation function P init . The state is set to the output of P init .

Plaintext processing. In encryption mode, DuplexAEAD then processes the plaintext and generates the ciphertext block by block as follows:

1. The ciphertext block C i is generated by XORing the outer state to the plaintext block

M i . That is, C i ← S ⊕ M i . 2.
The outer state is set to the just computed ciphertext block. That is, S ← C i . 3. The permutation P is applied to the state. That is, S ← P (S).

Ciphertext processing. In decryption mode, DuplexAEAD then processes the ciphertext. The plaintext M is constructed as the ciphertext is processed but will only be outputted at the end of the final phase if the tag is valid. This phase works as follows:

1. A plaintext block M i is generated by XORing the outer state to the ciphertext block

C i . That is, M i ← S ⊕ C i . 2.
The outer state is set to the value of the ciphertext block. That is, S ← C i . 3. The permutation P is applied to the state. That is, S ← P (S).

Final phase. During encryption (resp. decryption), plaintext (resp. ciphertext) processing is followed by a final phase in which the finalisation function P f inal takes as input the state and computes a τ -bit tag. The encryption algorithm returns a ciphertext and the corresponding tag. The decryption algorithm checks whether the tag is valid. If so, it returns the plaintext M . Otherwise, it returns ⊥. Domain separation. Actual duplex-based AE modes generally rely on domain separation for their security. In the case of DuplexAEAD, we assume that the way P init and P f inal are constructed from P ensures domain separation between the processing of (K, N ), the processing of A, the processing of M and the computation of T . This can be done for example by XORing distinct constants to the inner state before P invocations in each phase.

Security model

For authenticated encryption, two security notions are involved, namely privacy and integrity. Since our attack aims at breaking integrity, we leave privacy aside. We do not fully formalise the security model but give some simplified reminders to the reader. 5 In the integrity setting, we have an adversary A who has access to the following oracles:

-A primitive oracle O P that allows to call the public permutation P or its inverse P -1 . It takes as input a value v ∈ F b 2 and outputs P (v) ∈ F b 2 (resp.

P -1 (v) ∈ F b
2 ) for a call made to P (resp. P -1 ). -An encryption oracle O enc that takes as inputs a nonce N , associated data A and a plaintext M and returns a ciphertext C and a tag T computed with a secret key K which is randomly sampled once for all (the same key is used by the decryption oracle). 6 It implements the encryption algorithm of the analysed AEAD scheme based on P . -A decryption oracle O dec that takes as input a nonce N , associated data A, a ciphertext C and a tag T and, using the key K, returns the corresponding plaintext if the verification is correct, ⊥ otherwise. Similarly to the previous oracle, it implements the decryption algorithm of the analysed AEAD scheme.

We assume that the adversary A is nonce-respecting. Her goal is to provide a forgery, that is, an input (N, A, C, T ) such that O dec (N, A, C, T ) ̸ = ⊥ where (C, T ) was not outputted by the encryption oracle O enc on an input (N, A, •) (for any plaintext). The probability to provide a forgery has to be negligible. As already mentioned in Section 1, we denote by q e , q d and q P the number of queries done to respectively the encryption oracle, the decryption oracle and the primitive oracle. We denote by σ e the total number of plaintext blocks processed by the encryption oracle and by σ d the total number of ciphertext blocks processed by the decryption oracle.

In this paper, we construct a generic forgery attack against several duplexbased authenticated encryption modes. Our attack is generic in the sense that we do not exploit the properties of the permutation P but only properties of the mode itself [START_REF] Bertoni | Cryptographic sponge functions[END_REF]. It does not rely on nonce misuse or the release of unverified plaintext. For some modes, our attack also recovers the secret key with a negligible amount of extra computation.

Description of the attack

In this section, we present a generic forgery attack against duplex-based authenticated encryption modes. For the sake of clarity, we first describe how the attack works on the simplified mode DuplexAEAD defined in Section 2.2. We show how to apply our attack to other authenticated encryption modes in Section 5.

Observation on duplex-based AEAD modes

We describe a simple property of DuplexAEAD that is shared with many other duplex-based AE modes: for a ciphertext built by concatenating a fixed block multiple times, the decryption of a plaintext consists in the iteration of a known function with domain and co-domain F c 2 . This property is at the core of our attack. It is depicted in Figure 2.

Let ℓ ∈ N * and β ∈ F r 2 . Let β ℓ be the ciphertext equal to the concatenation of ℓ r-bit blocks of constant value β, that is

β ℓ = β|| • • • ||β ℓ .
During the ciphertext decryption, the value of the outer state at the input of the state update function P is equal to the current ciphertext block. Thus, the decryption of β ℓ corresponds to the iteration of the function P β defined as

P β : F c 2 -→ F c 2 x -→ P (β||x) .
Indeed, let x 0 ∈ F c 2 be the value of the inner state obtained at the end of the initial phase from the key, the nonce and the associated data. After processing the first plaintext block, the value of the outer state is equal to the first ciphertext block β. Thus, the input of the state update function is exactly β||x 0 . As a consequence, the value of the inner state going into the second application of P is β||x 1 where x 1 = P β (x 0 ). In turn, the third one is β||x 2 where x 2 = P β (x 1 ) = P 2 β (x 0 ). When the last plaintext block is constructed, right before the final phase, the state is thus of the form

β||P ℓ-1 β (x 0 ) = β||x ℓ-1 .
Since the outer part of the state is equal to β, it is known to the attacker. In particular, to recover the value of the state before the final phase, an attacker only needs to determine the value of x ℓ-1 . Since T = P f inal (β||x ℓ-1 ), it is sufficient for the attacker to recover the value of x ℓ-1 to find a forgery (N, A, C, T ). As we will show more rigorously later on, our cryptanalysis relies on the fact that without knowing x 0 , an attacker is able to select β and ℓ such that she is able to both restrict and predict the space of all possible x ℓ-1 = P ℓ-1 β (x 0 ) with good probability.

High level description of the attack

Our attack aims at recovering the value of x ℓ-1 . It was devised relying on the random functions statistics introduced in Section 2.1. Indeed, let n = 2 c . P is a random permutation on F b 2 and c = b-r is significantly smaller than b. Thus, for any β randomly drawn from F r 2 , we expect P β to behave as a function randomly drawn from F n .

The attack consists of two phases.

Precomputation phase. First, in a precomputation phase, an offline algorithm finds a value β such that G(P β ) has a large component with a small cycle, that is, a (s, ν)-component with great s and ν. Online phase. Second, in an online phase, (N, A, C, T ) queries are submitted to a decryption oracle, where the ciphertext is C = β ℓ with ℓ sufficiently large and β is the output of the precomputation algorithm. Recall that β is chosen such that G(P β ) has a large component with a small cycle. Since this component is large, it contains the unknown node x 0 with good probability. In that case, for a great enough value of ℓ, x ℓ-1 belongs to the cycle of this component, which is small. Thus, the number of all possible values for x ℓ-1 is reduced and can be efficiently exhausted by submitting (N, A, β ℓ , T ) queries to the decryption oracle where 1. tags are produced by applying P f inal to a state such that S = β and such that the inner state S belongs to the small cycle of P β 's large component; 2. nonces are either randomly sampled or arbitrary distinct values; 7 3. the associated data is set to the empty string ε. 8Our final attack, which balances the computational cost of the offline and online phases, provides a forgery in time O(2 3c 4 ) with a negligible amount of memory. In the rest of this section, we provide a detailed description together with an analysis of the complexity and success probability of our full attack.

In our complexity and success probability analysis, significant efforts were put towards limiting the use of heuristic assumptions. This is illustrated for example by the use of the probability p s,ν [START_REF] Delaurentis | Components and cycles of a random function[END_REF] that a random function has a (s, ν)component rather than a heuristic estimation of this value from the probability 7 In decryption queries, nonces can be repeated even in a nonce-respecting setting. For the purpose of our attack, x0 needs to behave as a point randomly sampled in the graph of P β . Thus, we can either require nonces to be randomly sampled or to be arbitrary distinct values.

p ν that it has a ν-component. Although we did not manage to get entirely rid of all heuristic assumptions, we intended to back each assumption with heuristic reasoning and/or small scale experiments.

Precomputation phase

In this section, we show how to construct an offline algorithm which outputs β such that G(P β ) has a large component with a small cycle. By 'having a large component with a small cycle', we mean having a (s, ν)-component as defined in Section 2.1. We will set the parameters s and ν to their final values later in the paper. The offline algorithm also outputs the length µ of the (s, ν)-component's cycle, as well as an element e of this cycle.

Our algorithm samples random values β from F r 2 and random values x in F c 2 and investigates whether or not the component on which

x is located is a (s, ν)-component of G(P β ).
When a random β and a random x are generated, we start by investigating the cycle length of the component on which x is located, that is, whether or not it is a ν-component. Cycle-finding algorithms such as Floyd's or Brent's algorithm provide a straightforward way to determine the component's cycle length. These algorithms are typically used to find collisions on functions with a negligible amount of memory. In fact, the collisions found by these algorithms are located within the functions' cycles. Thus, given a random β ∈ F r 2 , which selects a random P β ∈ F n , and a random x ∈ F c 2 , cycle-finding algorithms can be used to construct an algorithm which outputs both µ(x), the cycle length of the connected component on which x is located, and the value of a node in the cycle [START_REF] Joux | Algorithmic Cryptanalysis[END_REF]. We call such an algorithm cycle. The algorithm cycle allows the attacker to determine whether or not the component on which x is located is a ν-component, i.e. a component with a cycle of the desired length µ(x) ≤ n 1 2 -ν . To construct our final precomputation algorithm, two main issues remain to be solved. Issue 1. If the random β and the random x investigated are such that the component on which x is located is not a (s, ν)-component, it does not necessarily mean that G(P β ) does not have a (s, ν)-component. There could be an x ′ ̸ = x such that x ′ belongs to a different component that has the desired cycle length and size. In particular, we must determine whether or not it is worth trying a different x ′ ̸ = x when cycle returns a cycle length value that is greater than n 1 2 -ν (x's component is not a ν-component). There are two imaginable strategies. The first strategy consists in trying a single random x for each β, and, whenever x has a component with a cycle size smaller than n 1 2 -ν , investigate whether or not the component has size greater or equal than sn. The second strategy would be to try several x's for each β. We stick to the first strategy. The following argument indeed suggests that the second strategy would be more costly. When conditioned by the failure of the first drawn x, the probability that a second x ′ succeeds with the same β is at most ps,ν (1-s) 1-ps,ν whilst for a new random (β ′ , x ′ ), the probability of success is at least p s,ν s. Thus, the first strategy is better whenever s > 1 2-ps,ν which is always true for our values of s (which are always greater than 0.5) and ν.

Issue 2. Although cycle allows to detect ν-components, it does not provide a way to detect (s, ν)-components. Being fully certain that a ν-component has the desired size would be prohibitingly costly. A strategy allowing to estimate that a ν-component is a (s, ν)-component with a sufficiently large probability has to be devised. 9 The algorithm is_big implements this strategy. Note that in this algorithm, the notation '(., z)' in Step 4 means that the first output (corresponding to the cycle length) is ignored. Each time the algorithm detects a small cycle, it checks whether or not ω other random nodes belong to the same component. It then computes the proportion s obs of these new randomly chosen points which belong to the desired component. If this number is above a threshold value s + δ strictly larger than s, it decides that x is likely to belong to a (s, ν)component and returns β and the values of the cycle. We show that for δ = 2.33 2 √ ω , a selected component has size greater than s with great probability. Suppose that we have drawn a value β such that β has a ν-component of unknown size s β n. In that case, the random variable s obs is the mean of ω Bernoulli variables which are equal to 1 with probability s β and 0 with probability 1 -s β . By the Central Limit Theorem (CLT), we have that for all ϵ ∈ R,

p s obs -s β ≤ ϵ s β (1 -s β ) ω = p (Y ≤ ϵ)
where Y ⇝ N (0, 1). Thus, since δ = 2.33

s β ≥ s obs -δ ≥ s + δ -δ = s .
As a conclusion, when our final offline algorithm offline_search returns a β, then it is such that G(P β ) has a ν-component with probability 1, and the component considered has at least the desired size with probability p δ ≥ 0.99.

has been selected. It takes as input β, µ = µ(x) ≤ n 1 2 -ν , an element e of the cycle of x's component, s and an integer ω. It performs ω times a computation that essentially consists in the generation of a random point of G(P β ), one computation of the cycle algorithm, and at most µ point comparisons and µ -1 P β invocations. The average complexity of is_big is thus upper bounded by

T cycle + n 1 2 -ν ω .
The following estimation is heuristic, and implicitly relies on the assumption that the average complexity of cycle for a random point of a random function does not significantly differ from the average complexity of cycle for a random point of a fixed random function that has a ν-component. We provide a reasoning to justify why it seems very unlikely that this assumption would significantly distort the complexity at the end of the section.

We now compute the complexity of offline_search. First, we compute the complexity of one single iteration of a Step 1 loop of offline_search. Recall that p ν is the probability for a random node x ∈ F c 2 of a random function to belong to a ν-component. Each time a pair (β, x) is generated, the algorithm cycle is executed. Then, the algorithm executes is_big when a pair is such that x belongs to a ν-component of G(P β ), which happens with probability p ν . Finally, we need to compute after how many Step 1 iterations the algorithm returns a block β on average. At each iteration, the probability to generate a random β ∈ F r 2 such that G(P β ) has a (s, ν)-component is p s,ν . Given such β, the probability that the randomly drawn x ∈ F c 2 also belongs to this component is greater than s. Thus, on average, we select a node x in a (s, ν)-component after less than 1 ps,ν s iterations. Heuristically, one can thus expect the overall complexity of our algorithm to be of the following form:

1 p s,ν s T cycle + p ν T cycle + n 1 2 -ν ω .
Yet, we need to adjust this expression. Recall that a (s, ν)-component is a νcomponent of size greater or equal to sn. However, drawing a node in a νcomponent of size exactly sn10 is not enough to make the algorithm stop. Indeed, if a randomly drawn β ∈ F r 2 is such that G(P β ) has a ν-component of size exactly sn, the probability that s obs is greater than s + δ is smaller than 1% (here, we use the central limit theorem again). We thus need to adjust our computation. To do so, we lower bound the probability that a random pair (β, x) is selected by the probability that it satisfies the two following conditions:

(a) G(P β ) has a (s + , ν)-component with s + ≥ s + 2δ (recall that δ = 2.33 2 √ ω ). (b)
x belongs to the (s + , ν)-component, so that the algorithm offline_search randomly draws ω other values in F c 2 and computes s obs . Indeed, we show that satisfying these two conditions implies that s obs ≥ s + δ with great probability, which is exactly the condition that needs to be satisfied for the algorithm to return β.

Assume that the algorithm randomly draws β ∈ F r 2 and x ∈ F c 2 such that conditions (a) and (b) are satisfied. Then by the central limit theorem, we have that for any ϵ ∈ R,

p s obs -s + ≥ ϵ s + (1 -s + ) ω = p (Y ≥ ϵ)
where Y ⇝ N (0, 1). For ϵ = -2.33, we thus have that with probability p δ ≥ 0.99,

s obs ≥ s + -δ ≥ s + δ .
Thus, the probability that a randomly chosen β is selected is lower bounded by p s + ,ν s + p δ . It comes that the average complexity of the offline phase satisfies

T offline ≤ 1 p s + ,ν s + p δ T cycle + p ν T cycle + n 1 2 -ν ω = T cycle 0.99 π 2(1 -s + )s + n ν 1 + p ν ω 1 + n 1 2 -ν T cycle ≤ n 1 2 +ν 2π (1 -s + )s + 1 + p ν ω 1 + O(n -ν = n 1 2 +ν 2π (1 -s + )s + 1 + √ 2πω 2n ν + O 1 n 2ν = 1 (1 -s + )s + n 1 2 +ν √ 2π + n 1 2 ωπ + O n 1 2 -ν
.

For s + = 0.73, ν = 1 4 , the last expression is equivalent to

2π (1-s + )s + n 3 4 < 6n 3
4 . The previously mentioned heuristic assumption on the similarity of the average tail length of a random point of a random function that has a ν-component and the average tail length of a random point of a random function only underlies the second appearance of T cycle in the first bound on T offline above. Even if these two statistics differed non-negligibly, this would not significantly distort the complexity. Since is_big is executed only when a ν-component is detected, T cycle in its second occurence is multiplied by p ν ω ≪ 1 whilst it appears otherwise on its own. Success probability of the offline algorithm. We consider that the algorithm is successful if the value β outputted by the offline algorithm is such that P β has a (s, ν)-component. We have seen in Section 3.3 that when a β is selected (that is, s obs ≥ s + δ), the central limit theorem guarantees that the real size of the ν-component investigated is greater than sn with probability p δ . It comes that the success probability of the offline algorithm p offline is equal to p δ ≥ 0.99.

Online phase

In this section, we describe and analyse the online algorithm online_algo. The online phase consists in submitting (N, A, C, T ) queries to the decryption oracle O dec with C = β ℓ where β has been outputted by the offline algorithm. In the following, we describe how the tags are constructed and how we choose the value of ℓ.

Algo. online_algo(β, e, µ, ℓ, m)

1 : for i = 1..m do 2 : N $ ← -F η 2 ; y ← e 3 :
for j = 1..µ do

:

T ← P f inal (β||y)

5 : if O dec (N, ε, β ℓ , T ) ̸ = ⊥ 6 : return (N, ε, β ℓ , T ) 7 : else y ← P β (y) 8 : return false
Recall that we denote by x 0 the inner state at the end of the decryption's initial phase, and that when the ciphertext C is equal to β ℓ , the state before the final phase is equal to β||P ℓ-1 β (x 0 ). Recall that β, which has been outputted by the offline algorithm, is such that G(P β ) has a large component with a small cycle of this large component's cycle. Since this component is large, x 0 belongs to it with great probability. In that case, one can choose ℓ large enough for P ℓ β (x 0 ) to be likely to reach the small cycle of G(P β )'s large component. The number of candidates for the state before the final phase, and thus for the possible tags, is thereby reduced.

More formally, assume that the offline algorithm has been successful, that is, it has outputted β, µ and e such that G(P β ) has a (s, ν)-component with a cycle of length µ and such that e is an element of this cycle. If G(P β ) has a (s, ν)component, x 0 belongs to this component with probability greater than or equal to s. If x 0 belongs to the (s, ν)-component, P ℓ-1 β (x 0 ) reaches the cycle with the probability p ℓ introduced in Section 2.1. It comes that with probability at least p ℓ s, P ℓ-1 β (x 0 ) belongs to the cycle. Here, we implicitly rely on the assumption that the random variable tail length of a random point of a random function such that this random point belongs to a (s, ν)-component has the same distribution as the tail length of a random point of a random function. Although we do not believe this assumption to be true in the sense that the distributions are not strictly equal, we believe that they are close enough for it not to impact our attack significantly. Small scale experiments described in Section 4 corroborate this assumption.

We now analyse Algorithm online_algo. For a nonce N ∈ F η 2 , this online phase consists in submitting the following (N, A, C, T ) queries to the decryption oracle:

N, ε, β ℓ , P f inal (β||P i β (e)) for i = 0, . . . , µ -1 .

Time complexity. For each nonce, the attacker submits µ decryption queries with a ciphertext of ℓ blocks, and for each decryption query, she must also apply P f inal to the current state β||y where y is the current cycle element and apply P β to y in order to try exhaustively all the cycle elements. Since ℓ = O(n

2 ), the time complexity incurred by the above invocations of P β and P f inal at each decryption query is negligible compared to the time complexity of a decryption query with C = β ℓ , that can be approximated by ℓ applications of P . The time complexity for each nonce is thus well approximated by µℓ and thus upper bounded by

n 1 2 -ν ℓ .
Thus, for m nonces, the average complexity of the online phase in number of calls to P verifies

T online ≤ n 1 2 -ν mℓ .
Probability of success. For each nonce, the probability of success is exactly the probability that P ℓ-1 β (x 0 ) belongs to the cycle which we showed to be at least p ℓ s. If we repeat this experiment with m nonces, the probability of success is thus at least

p online = 1 -(1 -p ℓ s) m .

Complexity and success probability of the attack

The complexity of the attack is the sum of the complexities of the online algorithm and the offline algorithm. Note that in practice, the attacker only needs to run the precomputation offline algorithm once in order to be able to execute the online phase to attack the same duplex-based mode with any secret key. The average complexity T online + T offline of the attack can be upper bounded by

n 1 2 -ν mℓ + 1 (1 -s + )s + n 1 2 +ν √ 2π + n 1 2 ωπ + O n 1 2 -ν .
Similarly, the overall success probability of the attack is of the form

p success = p offline p online ≥ p δ [1 -(1 -p ℓ s) m ] ≥ 0.99(1 -e -mp ℓ s ) (since ∀x ∈ R, e -x > 1 -x) .
In order to have an overall probability of success p success greater than 0.95, we want 1 -e -mp ℓ s to be greater than 0.96. Recall from Section 2.1 that

p ℓ ≥ 1 -e -l 2
2n . We set ℓ = 3 √ n so that p ℓ ≥ 0.988. We also set the following values:

• ω = 2 10 ; thus 2δ = 2.33 √ ω < 0.08; • s + = 0.73; thus s = s + -2δ = 0.65.

Since p ℓ ≥ 0.988 and s = 0.65, p online is greater than 0.96 for m ≥ 5. We thus set m = 5. Thus, the complexity has the form

15n 1-ν + 6n 1 2 +ν + 4π2 10 √ 3 n 1 2 + O n 1 2 -ν .
To balance the above expression, we set ν = 1 4 , we get an attack of complexity at most 21n

3 4 + O( √ n) = 21 × 2 3c 4 + O( √ n
) in number of calls to P .11 Note that the complexity of the online phase is at most 15n 1-ν . In particular, given β such that G(P β ) has a component of size greater than ns with a cycle length close to 1, the online complexity can be brought close to 2 c 2 +4 .

Key-recovery

For modes such that P init is reversible for known nonce and associated data, our forgery attack also recovers the secret key with ℓ = O( √ n) extra applications of P , which is negligible compared to the complexity of the forgery. Indeed, if the decryption oracle receives a forgery (N, A, C, T ), it returns the corresponding plaintext. This allows the attacker to recover the state at the end of the initial phase with ℓ = O( √ n) extra applications of P -1 . 12 As a consequence, if the function P init is reversible for known nonce and associated data, the attacker recovers the secret key.

Small scale experiments

Our attack relies on the assumption that the P β 's derived from a public permutation P defined on F b 2 behave as random functions on F c 2 . To statistically verify this assumption, we implemented some experiments using the permutation Xoodoo [START_REF] Bertoni | Ketje v2. Round 3 candidate for the Caesar competition[END_REF] as P . The main reason behind this choice is its use in the finalist of the NIST lightweight cryptography competition Xoodyak, but another permutation used in practice with a reasonably large value of b would have done just as well. We took toy values compared to Xoodyak for the capacity (c ≤ 40) in order for computer experiments to remain easy to achieve. Since our attack relies mainly on the random function statistics results introduced in Section 2.1, we designed a test for each of these results. We also implemented the algorithm offline_search for small values of c.

mean ∈ πn 8 - 2.58σ µ √ Ω ; πn 8 + 2.58σ µ √ Ω .
Setting Ω = 14000, we verify whether mean is in this interval in our tests (see Table 1). We use a similar algorithm and reasoning for the tail length. 13 As shown in Table 1, all our experimental results match the theory. Probability for a random point to belong to a ν-component. We wish to verify that for a random β ∈ F r 2 and for a random node x ∈ G(P β ), the probability that x belongs to a ν-component is p ν . To do so, we use the algorithm nu_components and focus in practice on experiments where ν = 1 4 as it is the value used in our attack. Drawing Ω random (x, β) pairs and computing the proportion of such pairs such that x belongs to a ν-component of P β amounts to computing the mean of Ω Bernoulli variables equal to 1 with probability p ν and 0 with probability 1 -p ν . By the Central Limit Theorem, since the standard variation of the above variables is σ ν = p ν (1 -p ν ), we have that

proportion ∈ p ν - 2.58σ ν √ Ω ; p ν + 2.58σ ν √ Ω
with probability ≥ 0.99. We verify in our experiments that proportion is indeed in this confidence interval for various values of c and Ω. Our results, which match the theory, are displayed in Table 2. Table 2. Probability for a random node in the graph of a random function to belong to a ν-component and experimental verification of (the detection of) the occurence of (s, ν)-components.

c
Probability for a random function to have a (s, ν)-component. Verifying that for a random β ∈ F r 2 , the probability that G(P β ) has a (s, ν)-component is p s,ν is hard in practice as it is too costly to determine with probability 1 whether or not G(P β ) has a (s, ν)-component. Instead, we make an indirect verification. We draw Ω random (x, β) pairs and compute the proportion frequency of such pairs such that:

-P β has a ν-component (the component to which x belongs); the estimated size s obs of this component (given by the proportion, among ω = 1000, of newly chosen random points that belong to this component) is at least s + δ with δ = 2.33 2 √ ω , so that the actual size of the component is very likely to be at least sn. 14We compare the found frequency values with two values:

the lower bound p s,ν s on the probability that P β has a (s, ν)-component and x belongs to it; the conservative lower bound p s + ,ν s + p δ on the average value of frequency used in the complexity estimate of the offline algorithm of Section 3.4, where

s + = s + 2δ.
This algorithm is easy to derive from the algorithm offline_search introduced in Section 3.3. We make this experiment for various values of Ω and c and with s = 0.65, s + = 0.73, as they are the values used in our attack. Our results match the theory and are displayed in 3.

Probability for a random point to belong to its component's cycle after ℓ -1 applications of the random function. In order to verify the applicability of Harris' result on the number of successors provided in Section 2.1 to points randomly drawn in a (s, ν)-component, a fortiori when the function is randomly sampled from the set of all P β 's rather than randomly sampled in F n , we also conducted the following experiment. For all β values displayed in Table 3, we checked whether the points that were found to be in the (s, ν)-component had a tail length smaller than ℓ = 3 √ n. For all these β, 100% of the points found to be in the (s, ν)-component have a tail length smaller than ℓ. This gives us reasonable confidence in the fact that this assumption is realistic and does not lead to a significant overestimation of the success probability of the attack.

Application to concrete duplex-based modes

In this section, we apply the attack previously described on the simplified Du-plexAEAD mode to concrete AEAD duplex-based modes. Whilst our attack can be easily adapted to many of them as summarized in Table 5, others frustrate our attack. For all the modes presented in Table 5, our attack enables key recovery.

Highlights

For the attack to succeed, we identify two requirements:

1. In decryption mode, the ciphertext blocks must overwrite the outer state at least in part; 2. The tag must be determined by the state before the final phase, in such a way that a correct guess on this state gives us the correct tag.

As a consequence, we will show that in all modes for which the attack is applicable, the padding rule applied to the message does not matter, even though when the padding rule is made block by block the complexity of our attack can be slightly greater.

As a main concrete implication, we provide an attack on Xoodyak that breaks the claim of achieving 184-bit security against plaintext recovery and forgery attacks made by the designers in [18, Corollary 2, p. 72] but does not threaten the 112-bit security level required by NIST for the lightweight competition. The attack also breaks the penultimate NORX version NORX v2 [START_REF] Aumasson | NORX v2. Submission to the Caesar competition[END_REF] but not the more recent version NORX v3 [START_REF] Aumasson | NORX v3. Submission to the Caesar competition[END_REF].

Secondly we highlight two reasons that prevent our attack from applying to modes such as Beetle [START_REF] Chakraborti | Beetle family of lightweight and secure authenticated encryption ciphers[END_REF], Ascon [START_REF] Dobraunig | Ascon v1.2: Lightweight authenticated encryption and hashing[END_REF] or NORX v3 [START_REF] Aumasson | NORX v3. Submission to the Caesar competition[END_REF] in Section 5.3. We mainly identify two reasons: (2) Claimed plaintext integrity security level for a key and tag of sufficient, potentially maximal, length; (3) Note that a more efficient (although not generic) attack has been devised in [START_REF] Chaigneau | Cryptanalysis of NORX v2.0[END_REF].

the use of a linear application that prevents outer state overwriting such as the feedback function proposed in the Beetle mode [START_REF] Chakraborti | Beetle family of lightweight and secure authenticated encryption ciphers[END_REF] (requirement 1 is not fulfilled);15 the use of the secret key in the final phase to produce the tag such as in Ascon and NORX v3 [START_REF] Dobraunig | Ascon v1.2: Lightweight authenticated encryption and hashing[END_REF][START_REF] Aumasson | NORX v3. Submission to the Caesar competition[END_REF]. Indeed, in that case, a correct guess on the state before the final phase does not determine the tag (requirement 2 is not fulfilled).

Schemes to which the attack can be applied

The attack is applicable to the following duplex-based constructions: the Cyclist, monkeyDuplex and Motorist modes. Therefore, the attack is applicable to Xoodyak, Ketje, KNOT, NORX v2 and Keyak. This section is made to help the reader check attack details for all AEAD algorithms on which the attack is applicable.

Cyclist mode. A well known representative of the family of duplex-based ciphers is Xoodyak [START_REF] Daemen | Xoodyak, a lightweight cryptographic scheme[END_REF], a finalist of the NIST lightweight cryptography competition. 16 Xoodyak uses the permutation Xoodoo as its state update function.

As explained in Section 3.5, the specification of the initial phase does not influence the applicability of the attack. Hence, we only focus on the ciphertext processing and the final phase. After the initial phase, a byte is set to '80' and is XORed into the state, but this is only the case for the first block. Thus, we consider that the processing of the first ciphertext block belongs to the initial phase. Moreover, each time a ciphertext block overwrites the outer state, a byte set to '01' is XORed into the state at the bit positions r + 1, . . . , r + 8 17 , where r = 24 bytes = 192 bits [18, p. 68]. Thus, the permutation P on which we need to apply offline_search is

P : F 384 2 -→ F 384 2 s -→ Xoodoo[12](s ⊕ 0 192 ||0 7 ||1||0 184 ) .
If one considers the padding rule 10 * together with the interface provided by the Xoodyak authors, one can notice that all those transformations are deterministic in the value of the inner state just before processing the last ciphertext block. Hence, we can guess the last state value, and apply the final phase (considering the padding for the last block inside this transformation) to the last block and apply the attack. This means that for any tag length, our attack strategy provides a forgery with a complexity of 2 148. 4 . When a valid decryption query is provided to the decryption oracle, the corresponding plaintext is returned. The plaintext allows the attacker to check that her guess on the state before the final phase is correct as she can invert the whole process. Doing so, she can also recover the state just after processing the key. As long as the key is smaller than 44 bytes, it is copied entirely in the state and then A, N and M are processed. Thus, P init is reversible for known N and A. As described in Section 3.7 the attack can thus be turned into a key recovery for Xoodyak.

For a t-byte tag and a κ-bit secret key with κ ≤ 192, the authors claim that Xoodyak has a security strength level in bits of min(184, κ, 8t) in computation where the data is limited to 96+κ/2. Our attack breaks this claim for κ ≥ 152 and t ≥ 19. Our attack not only produces a forgery but also recovers the secret key. Typically, for κ = 192 and t = 24, there should be no attack with a complexity under 2 184 in time and 2 192 in data. Yet, our attack has a complexity of 2 148.4 .

MonkeyDuplex: Ketje, KNOT and NORX v2. Ketje [START_REF] Bertoni | Ketje v2. Round 3 candidate for the Caesar competition[END_REF], KNOT-AEAD [START_REF] Zhang | KNOT. Round 2 candidate for the NIST Lightweight Cryptography project[END_REF] and NORX v2 [START_REF] Aumasson | NORX v2. Submission to the Caesar competition[END_REF] use the mode monkeyDuplex defined originally in 2014 for 16 For more details on Xoodyak's specification, we refer to [START_REF] Daemen | Xoodyak, a lightweight cryptographic scheme[END_REF] at page 62 for the keyed mode together with pages 67 and 68 for the full description of what is relevant for our analysis. https://csrc.nist.gov/Projects/lightweight-cryptography/ 17 Note that the rate called r in this paper is denoted by n in Xoodyak's specification.

Ketje [START_REF] Bertoni | Ketje v1. Submission to Caesar competition[END_REF]. However, those algorithms differ in the padding rule applied to the message.

-In KNOT-AEAD, the padding is made by 'appending a single 1 and the smallest number of 0's to the bit string such that the length of the padded bit string is a multiple of r bits'. Thus, the technique used for Xoodyak can be applied. -In Ketje and in NORX, the padding is made block by block [12, 1.3, p. 4] and [1, p. 9-10] with the rule pad10 * 1[r](|M |) which is the multi-rate padding as defined in [START_REF] Bertoni | Duplexing the sponge: Single-pass authenticated encryption and other applications[END_REF]. Both ciphers allow to process bit strings of length smaller or equal 18 to r ′ = r -2. To deal with this padding rule, we consider that every plaintext block is of length exactly r ′ , meaning that the padding rule is just the concatenation of 11 to each block. By doing the same technique together with the domain separation as for Xoodyak, that is considering that the position corresponding to those two bits are in fact inside the inner state and that the XOR of 11 is part of the Ketje inner permutation P (or part of the NORX inner permutation), we can apply our attack, by considering the effective rate to be r ′ = r -2 instead of r.

For these three constructions, the final phase is deterministic in the inner state after processing the plaintext or the ciphertext so our attack can be applied. Both ciphers come with 4 different instances and our attack leads to the complexities listed in Table 5. Moreover, when the decryption oracle sends back the plaintext, a key recovery is possible as the state is directly initialized with key and nonce without applying any transformation.

Motorist: Keyak. Keyak [START_REF] Bertoni | Keyak v2. Submission to the Caesar competition[END_REF] is a family of authenticated encryption schemes which is a third-round candidate of the CAESAR competition. The features of the Motorist mode that are of interest for our attack are:

-Decryption overwrites the outer state with ciphertext blocks values and in between there are applications of P where P is a Keccak-p permutation. -An encoding (in byte) of the size of the processed message blocks is XORed into the state at the R a + 1 byte position, where R a is the absorbing rate in bytes (R a = r 8 ). -For the tag generation, given a (public) tag length, the tag is determined by the state before the final phase.

Thus, the attack can also be applied on Keyak instances by just changing the function that is iterated and considering the XOR of the bytes that encode the length of ciphertext and associated data to be part of the decryption function.

However, Keyak comes with instances that can work independently (Pistons), in order to highly parallelize encryption and decryption of large amount of data. To do so, the authors of Keyak propose to do several initialization in parallel, process independently 4, 8 or more strings and then mix everything together at the end. However, if one would like to guess the tag, one would have to guess independently every inner state in all parallel instances as they are all initialized differently. So, our attack on Keyak is also applicable on all instances but make sense only for the non-parallelized instances, that is River Keyak and Lake Keyak. For these instances, the key can also be recovered.

Modes that frustrate our attack

In this section, we will look into authenticated encryption modes to which the attack cannot be applied. Two main features frustrate our cryptanalysis. The first one consists of a final key addition just at the beginning of the final phase and the second one is the use of a feedback function as proposed in the mode Beetle [START_REF] Chakraborti | Beetle family of lightweight and secure authenticated encryption ciphers[END_REF].

Key-dependent final phase. Our attack allows to reduce the space of all possible values of the final state before the final phase. For the modes to which the attack applies, a correct guess on this state can be transformed into a forgery, and, under certain conditions, into a key recovery. However, some proposals such as Ascon [START_REF] Dobraunig | Ascon v1.2: Lightweight authenticated encryption and hashing[END_REF] or the third version of NORX [START_REF] Aumasson | NORX v3. Submission to the Caesar competition[END_REF] for the CAESAR competition slightly change the final phase by making it not only dependent on the state after processing the plaintext or ciphertext, but also key dependent. As explained at the beginning of this section, the final tag must be fully determined by the state just before the final phase. When the key is involved in the final phase, even if the correct state value is guessed, an attacker does not know a priori the secret key and so the state recovery does not lead to a forgery attack.

Absence of outer state overwriting. In another line of research, Chakraborti et al. proposed in 2018 a family of AEAD constructions named Beetle [START_REF] Chakraborti | Beetle family of lightweight and secure authenticated encryption ciphers[END_REF]. Beetle is not strictly speaking a duplex-based construction as the use of a feedback function between two consecutive invocations of the permutation P avoids, when both a data injection and a data extraction take place, that the r-bit outer state value after the data injection be equal to the extracted data block as in traditional duplexing, and allows to render both values almost independent. Thus, the use of a feedback function prevents the attack by making the outer state overwriting impossible. Unlike duplex-based constructions which do not use a feedback function twist, the Beetle construction is claimed to provide a security level min{ b 2 , c -log(r), r} without any restriction on decryption queries [START_REF] Chakraborti | Beetle family of lightweight and secure authenticated encryption ciphers[END_REF][START_REF] Banik | GIFT-COFB[END_REF]. The Beetle construction is used in the Beetle and SPARKLE [START_REF] Beierle | Lightweight AEAD and hashing using the Sparkle permutation family[END_REF] finalists of the NIST lightweight cryptography standardization process.

The same effect also occurs in Subterranean 2.0 [START_REF] Daemen | The subterranean 2.0 cipher suite[END_REF] which is a second round candidate of the NIST-lightweight competition and a duplex-like proposal. In order to generate the ciphertext blocks, two bits of the state are XORed to serve as a keystream. It prevents the attack in the same way that the feedback function of the Beetle mode does, as the attacker can not predict the value of the outer state before the next application of the update function.

Conclusion

In this paper, we provided a generic attack against several duplex-based AEAD modes. Constructed as a forgery attack, our cryptanalysis can be transformed into a key recovery for most modes to which it applies. It has a complexity equivalent to O(2 3c 4 ) applications of the state update function and thus represents an improvement from previous generic attacks against duplex-based modes. It is also memory-less. Further, the complexity of the online phase can be brought close to 2 c 2 at the cost of increasing the time complexity of the pre-computation phase (which needs to be run only once) above O(2 3c 4 ).

c 2 . 2 c 2

 222 It is therefore an open question whether there exists a generic attack of total complexity T strictly comprised between and the complexity 2 c α of multicollision-based attacks. 3 In this paper, we provide a positive answer to the former open question by exhibiting a generic attack against a large family of duplex-based constructions of total time complexity T in O(2 3c 4

Fig. 1 .

 1 Fig. 1. DuplexAEAD in encryption mode.

Fig. 2 .

 2 Fig. 2. Decrypting β ℓ .

c 4 .

 4 Although we only provide one for each c, several values of β are available for each c. Some values of β. Lastly, we implemented the algorithm offline_search for small values of c and for s = 0.65. A few examples of obtained β values are displayed in Table

Table 1 .

 1 Expectancy of cycle length and tail length

	c	28	32	36	40
	Expectancy	10267	41068	164274	657098
	Confidence interval [10080, 10454] [40321, 41817] [161283, 167266] [645130, 669065]
	tail mean	10323	40971	163732	654775
	cycle mean	10255	41620	164445	650156

Table 2 .

 2 The difference (in favour of the adversary) between theoretical bounds and experimental values for frequency in Table2can be at least partially explained as follows. The value p s,ν is the probability that a component is a ν-component of size greater or equal to s. The probability that a random point belongs to a (s, ν)-component is thus strictly greater than p s,ν s as the proportion of the points belonging to a component of size greater than s is greater than s.

	c	β (b -c bits)	µ
	28	1473b86a 2607d6e5 5234df22 4c111c51 122e188f 37586e28	10
		5b74f306 40ac1d69 2bb9c59f 6e8479b7 3d6ec314 7
	32	67b9632a 032ec1a3 1f3b4f8c 7c641f59 39e3cab6 3aaa4444	4
		73bf377d 7f1f6b35 6412ffb2 523d5180 54465a4f
	36	59189691 3e3769f2 293b1b6f 0cc0af85 7d96b0a4 0e1c201b	122
		137523e8 11f61a60 6c06c85f 762716b7 276c730
	40	7b2fb641 7874c3d6 171abbc2 231ebf22 4e6e1ad3 2d6df079	18
		7e6457aa 7816dd2a 011fe0f3 1de6ee24 56f1ed

Table 3 .

 3 We provide a few examples of obtained β values such that P β has a (s, ν)component with µ ≪ 2

Table 4 .

 4 198 2 144 2 282 2 506 2 1014 2 148 2 148 2 220 2 292 2 148 2 196 2 196 Summary of our results. Our attack is the best known generic attack against the modes displayed in blue; (1) r ′ is the length of the outer state part that is overwritten by ciphertext blocks taking into a account a potential block by block padding such as in monkeyDuplex;

	Mode		monkeyWrap/monkeyDuplex	Cyclist	Motorist
	Scheme NORX v2 (3)	Ketje	KNOT	Xoodyak Keyak
	Instance N-32 N-64 Jr Sr Mi Ma	KNOT-AEAD Xoodyak River Lake
	b	512 1024 200 400 800 1600 256 384 384 512	384	800 1600
	r	384 768 16 32 128 256 64 192 96 128	192	544 1344
	r ′ (1)	382 766 14 30 126 254 64 192 96 128	192	544 1344
	c	128 256 184 368 672 1344 192 192 288 384	192	256 256
	Sec. level (2) 128 256 96 128 128 128 125 128 189 253	184	128 128
	T	2 102 2

The name "duplex", that conveys the idea of a bidirectional process, reflects the fact that in such constructions both a data block injection and a data block extraction to/from the current state can potentially take place between two consecutive invocations of P .

[START_REF] Aumasson | NORX v3. Submission to the Caesar competition[END_REF] Note that in the attack considered in the sequel, textra-op will in practice be negligible compared to σe + σ d + qP .

In other words, the questions whether the "birthday term" 2 c σ d is an artifact of the proofs and whether the capacity value c can be safely dimensioned well below 2s, where s denotes the targeted security level remain open.

In practice, our cryptanalysis can be easily adapted to attack modes which can process plaintexts of arbitrary length, but this requires a short case-by-case analysis which we provide in Section

Note that the resulting adjustments have a negligible impact on the complexity of our attack and do not impact its success probability.

For more details see for example[START_REF] Jovanovic | Beyond 2 c/2 security in sponge-based authenticated encryption modes[END_REF].

Each parameter space is well defined according to the analysed AEAD scheme.

For modes other than the full-state duplex, we could set the associated data to any value. In the case of the full-state duplex, the associated data must be chosen carefully (typically, the attack applies when the AD is set to the empty string).

Given a point of the graph x, the introduction of an algorithm which estimates x's component's size is going to significantly complicate our attack's complexity analysis. We believe that we could have designed an attack without this extra algorithm by relying on the fact that a random component is large with great probability. However, unless increasing the complexity of the online phase, we would have then obtained lower success probabilities (roughly around 0.5 rather than close to 1).

or greater than sn, but too close to sn to make the algorithm stop.

Note that ν = 1 4 is not the fully optimal choice in general. Rather, the optimal choice for ν is ν = 1 2 1 2 -log n √ 2π/( s + (1 -s + )15) . For example, for n = 2

, the optimal choice is approximately 0.256.[START_REF] Bertoni | Ketje v2. Round 3 candidate for the Caesar competition[END_REF] The plaintext also allows to verify that the recovered state before the final phase is correct, making the key recovery possible with only a negligible amount of extra computations regardless of the tag length.

Here, we make the assumption that the standard deviation for the tail length is the same as the cycle length's. This assumption does not affect our attack, it only affects how to interpret our test results.

To reduce the execution time of the implementation, to detect whether or not two points x, x ′ are in the same component, we checked whether µ(x) = µ(x ′ ) instead of doing the exhaustive verification made in is_big.

Although the first mode that uses a feedback function is COFB[START_REF] Chakraborti | Blockcipher-based authenticated encryption: How small can we go?[END_REF], this mode is out of scope as it is not duplex-based (in fact, it is not even permutation-based but block-cipher based).

This value is called ρmax in[7, p. 335]

Acknowledgements. We wish to thank Jérôme Plût and Hugues Randriam for our insightful conversations on the statistics of random functions.

Algo. offline_search(ω, s, ν)

Analysis of the offline algorithm

In this section, we analyse the success probability and complexity of the offline algorithm. As stated in Section 2.3, the complexity is expressed as a number of calls to P . This algorithm is at the core of our attack. It only needs to be executed once. Indeed, once it has succeeded in finding β such that G(P β ) has a (s, ν)-component, a duplex-based mode with any key using the permutation P can be attacked.

Complexity of the cycle-finding algorithm. We start by investigating the average complexity of the algorithm cycle. To construct this algorithm, we use Brent's cycle-detection algorithm as a tool [START_REF] Brent | An improved monte carlo factorization algorithm[END_REF]. For a random β ∈ F r 2 and a random x ∈ F c 2 , Brent's algorithm recovers the cycle length µ(x) and a node of the cycle e ∈ C(x) after at most 2 max(µ(x), λ(x)) + µ(x) applications of P β . For a random x, the cycle length µ(x) and the tail length λ(x) have the same expectation of πn 8 [START_REF] Flajolet | Analytic Combinatorics[END_REF] (See Section 2.1). Thus, we estimate the average complexity of cycle in number of calls to P to be upper bounded by

Complexity of the offline algorithm. We wish to compute the complexity of the offline algorithm offline_search. First, the memory complexity is negligible. As for the time complexity, we compute the average number of applications of P after which the algorithm returns a block β ∈ F r 2 . First, we upper bound the average complexity of is_big. This algorithm is executed when a pair (β, x) such that x is located on a ν-component of G(P β )

Algo. cycle_expectancy(Ω)

Algo. nu_components(Ω, ν)

Expectancy of cycle/tail length. We wish to verify that for a random β ∈ F r 2 and for a random node x ∈ G(P β ), the expectancy of the cycle length µ(x) and tail length λ(x) are both equal to πn 8 , with n = 2 c . Note that the variance of the cycle length and tail length for a random node of a random function is equal to σ 2 µ = n 2 3 -2π 16 [START_REF] Harris | Probability Distributions Related to Random Mappings[END_REF]. Regarding the cycle length, we use the algorithm cycle_expectancy. After Ω tries, by the Central Limit Theorem, the observed average cycle length mean outputted by the algorithm cycle_expectancy is such that with probability about 0.99: