André Schrottenloher

Marc Stevens

Simplified Modeling of MITM Attacks for Block Ciphers: New (Quantum) Attacks

Keywords: MITM Attacks, Key-recovery attacks, Quantum cryptanalysis, Preimage attacks, AES, Present

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Meet-in-the-middle (MITM) attacks are powerful attacks on symmetric primitives such as block ciphers [START_REF] Diffie | Special feature exhaustive cryptanalysis of the NBS data encryption standard[END_REF] and hash functions [START_REF] Sasaki | Meet-in-the-middle preimage attacks on AES hashing modes and an application to Whirlpool[END_REF]. The goal in both cases is to find an unknown value (the internal state or the key) which satisfies a certain set of constraints, e.g., between the inputs and outputs of a certain computational path.

If one guesses the entire unknown value, then the whole path can be recomputed and the constraints checked: this is the generic exhaustive search, which can always be applied. The MITM technique identifies some parts of the path which can be computed independently from others. Typically one defines a forward chunk (computed forwards) and an independent backward chunk (computed backwards), which start from a given starting point, and meet at several matching points. The values that they can take are computed independently. Afterwards, one selects among the pairs all those which satisfy the conditions set by the matching points.

MITM attacks have been successfully applied to many designs, using more and more refined techniques: guess-and-determine [START_REF] Orr Dunkelman | Improved meet-in-themiddle attacks on reduced-round DES[END_REF], splice-and-cut [START_REF] Aoki | Preimage attacks on one-block MD4, 63-step MD5 and more[END_REF][START_REF] Guo | Advanced meet-in-the-middle preimage attacks: First results on full tiger, and improved results on MD4 and SHA-2[END_REF], bicliques [START_REF] Khovratovich | Bicliques for preimages: Attacks on skein-512 and the SHA-2 family[END_REF], 3-subset MITM [START_REF] Bogdanov | A 3-subset meet-in-the-middle attack: Cryptanalysis of the lightweight block cipher KTANTAN[END_REF][START_REF] Sasaki | Integer linear programming for three-subset meet-in-the-middle attacks: Application to GIFT[END_REF], and so on. Even when they do not reach the best The results obtained with our tool are summarized in Table 1, compared with some results of previous works. We obtain full-round attacks on the block ciphers Future [START_REF] Kishan | FU-TURE: A lightweight block cipher using an optimal diffusion matrix[END_REF] and Pipo-256 [KJK + 20], both due to the simple key schedules of the ciphers. We also give new quantum attacks on reduced-round Saturnin-Hash and Saturnin, and observe that some Grover-meet-Simon attacks [START_REF] Leander | Grover meets simon -quantumly attacking the fx-construction[END_REF] are covered by the automatic search. This complements the automated search of Simon-based attacks previously proposed by Canale, Leander and Stennes [START_REF] Canale | Simon's algorithm and symmetric crypto: Generalizations and automatized applications[END_REF]. Though their tool can find more attacks than ours, as it allows to define periodic functions from a bigger class, it was limited to rather simple constructions. Our tool is more adapted to complex cipher designs.

Backward path

Figure 1: MITM attacks using the "splice-and-cut" technique (figure adapted from [START_REF] Schrottenloher | Simplified MITM modeling for permutations: New (quantum) attacks[END_REF]).

applications: 1) AES-like designs in Section 4, including Saturnin-Hash, Saturnin and Future; 2) Present-like designs in Section 5, including Present and Pipo.

The code used in this paper, including the generation of MILP models for all our examples, and the generation of figures, is available online1 . We used the Gurobi solver [START_REF] Optimization | [END_REF] on a desktop computer.

Preliminaries

In this section, we give a high-level overview of MITM attacks, with corresponding formulas for the time complexity. We also give preliminaries on quantum attacks.

As shown in Figure 1, we consider a block cipher E K , made of a sequence of r rounds (0 to r -1) which act on the internal state taking value s 0 (plaintext) to s r (ciphertext). A key schedule function transforms the master key K into a sequence of round keys k 0 , . . . , k r . Each k i is added before round i, and k r is the final key addition. We enforce some relation between s 0 and s r , which creates a closed computational path. We are searching for a pair (s 0 , K) satisfying this path.

In the case of a preimage or pseudo-preimage attack [START_REF] Sasaki | Meet-in-the-middle preimage attacks on AES hashing modes and an application to Whirlpool[END_REF], the block cipher E K is used as a compression function. For example, in the Matyas-Meyer-Oseas (MMO) mode, the function is f (m, h) = E h (m) for a chaining value h and a message block m. Given a target T , a pair h, m such that E h (m) = m ⊕ T is a preimage of the compression function. The degrees of freedom of both m and h may be used. If we fix h, we remove the key schedule; the block cipher becomes a permutation.

For a key-recovery attack, the relation between input and output ("wrapping" in Figure 1) is given by E K . On the forward path in Figure 1, we need to compute s 0 from s r , so we perform decryption queries.

AES-like and Present-like Designs

The AES [START_REF] Daemen | The Design of Rijndael -The Advanced Encryption Standard (AES), Second Edition[END_REF] is the standardized version of the block cipher Rijndael [START_REF] Daemen | AES Proposal: Rijndael[END_REF], and its design strategy has been followed by many ciphers and hash functions, forming a family that we will call "AES-like". AES-like designs are substitution-permutation networks (SPN) in which the internal states and round keys are represented as matrices of nibbles. The S-Box layers operate on nibbles independently. The linear layer can also be expressed as an operation on nibbles.

In the AES, the state is a 4 × 4 matrix of bytes, and the round function composed of: the key addition (ARK); the S-Box layer (SB); the ShiftRows operation (SR), which permutes bytes within rows of the matrix; and finally, the MixColumns operation (MC), which multiplies each column by an MDS matrix. Other AES-like designs typically have similar operations. Sometimes (like in Skinny [BJK + 16]) the MixColumns is not MDS, but we will not consider such cases in this paper. Key schedules of AES-like designs also typically operate at the nibble level, e.g., in the AES itself, the only operations are XORs of key bytes and S-Boxes.

Super S-Box and Present-like Ciphers.

It can be noticed that in the sequence of operations ARK → SB → SR → MC, the operation SB commutes with SR and ARK. Thus, an AES round can be rewritten as a permutation of bytes, followed by a key addition, and a layer of Super S-Boxes applying on columns. This abstraction is essential for us. Using the Super S-Box representation, an AES-like design becomes an SPN in which the linear layer is simply a permutation of nibbles, corresponding to the SR operation. We give an example in Figure 2, where the initial bytes are numbered from 0 to 15, and the columns of the state are the groups of bytes [0-3], [4-7], [8-11], [12][13][14][15].

We name Present-like the SPN ciphers which use only a nibble permutation as their linear layer, like the block cipher Present [BKL + 07]. Though Present uses a bit permutation, our structure considers nibbles of any size. Our modeling starts from this family of ciphers, and covers AES-like designs thanks to the Super S-Box representation.

Key Schedules.

The key schedule of a cipher is an in-place operation that transforms a set of internal key registers and extracts rounds keys. All variants of AES have a key schedule which offers quite a strong diffusion. This renders the AES itself immune to MITM key-recovery attacks2 . However, lightweight ciphers, whether AES-like (e.g., Saturnin [CDL + 20]) or Present-like (e.g., Present, Gift [BPP + 17]) can have much simpler key schedules. In this paper, we consider key schedules that operate nibble-wise using in-place operations, either: 1) a permutation of nibbles; or 2) an S-Box applied in place to some nibbles. This includes the key schedule of Present.

Overview of Techniques

Below we briefly review the techniques that will be contained in our automatic search. We consider both key-recovery and preimage attacks. While they are very different conceptually, the modeling is quite similar. Let E K be a block cipher with block length (in nibbles) n and key length |K|. We start with the key-recovery case.

We have query access to E K and wish to retrieve K in time less than 2 |K| computations of E. This is done by finding solutions to the closed computational path represented in Figure 1.

We formalize this using a forward path function f F (x, k F ) and a backward path function f B (x, k B ) that take a common starting state x (e.g., the plaintext), a forward (resp. backward) key guess k F of length |k F | (resp. k B of length |k B |) and compute the same set of nibbles at some round inside the cipher.

We see that k = k F ∪ k B can be a potential candidate3 for K only if there exists

x such that f F (x, k F ) = f B (x, k B ).
Typically, starting from a constant x, we compute E K (x), compute forwards from x and backwards from

E K (x). Either f F or f B includes a query to E K or E -1 K . Let |f | := |f F | = |f B |
be the output size of f F and f B . From now on, these sizes are counted in nibbles, and the complexity formulas would need to be re-scaled depending on the nibble size. The attack does:

1. fix the value x 2. compute the list of all k B , f B (x, k B ): time 2 |k B | (we neglect the time to sort the list by the second entry)

3. for each k F , compute f F (x, k F ) and enumerate all the pairs k F , k B such that f F (x, k F ) = f B (x, k B ): time 2 |k F | + 2 |k F ∪k B |-|f | .
For each pair, recompute the whole path and check if it matches.

Because we can swap the roles of forward and backward paths, the time complexity for key-recovery is 2

|k B | + 2 |k F | + 2 |k F ∪k B |-|f | and the memory complexity is min(2 |k B | , 2 |k F | ).
Varying the Cut Set / Initial Structure. The cut set [START_REF] Ahmadi | Low-data complexity biclique cryptanalysis of block ciphers with application to piccolo and HIGHT[END_REF] or more generally, the initial structure, is the start of the path, i.e., the starting state x defined above. It can take any value and any position within the closed path. It can also be scattered onto multiple rounds. If the cut set is moved inside the closed path, the query complexity of the MITM attack, which was initially 1, increases. Indeed, each computation of f F (resp. f B ) will potentially query E K on a new value, depending on the starting state x and on the current key guess k F (resp. k B ).

3-Subset MITM Attack. The 3-subset MITM attack [START_REF] Bogdanov | A 3-subset meet-in-the-middle attack: Cryptanalysis of the lightweight block cipher KTANTAN[END_REF] partitions the key space in three sets. Alongside the forward and backward key nibbles, we define shared key nibbles k S of length |k S |, and the forward and backward paths are now computed as:

f F (x, k F , k S ) and f B (x, k B , k S ),
where k F and k B are disjoint. The MITM attack now runs as follows: we fix x, and for each choice of k S , we compute the pairs (k

F , k B ) such that f F (x, k F , k S ) = f B (x, k B , k S ). The time complexity is 2 |k S |+|k B | + 2 |k S |+|k F | + 2 |k F |+|k B |+|k S |-|f | and the memory complexity is min(2 |k B | , 2 |k F | ).
Guess-and-Determine. Guess-and-determine (GAD) is a powerful technique both for keyrecovery [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF] and preimage attacks [START_REF] Sasaki | Investigating fundamental security requirements on whirlpool: Improved preimage and collision attacks[END_REF][START_REF] Bao | Superposition meet-inthe-middle attacks: Updates on fundamental security of AES-like hashing[END_REF]. We introduce nibble state guesses y F and y B in the definition of the forward and backward paths:

f F (x, y F , k F , k S ) and f B (x, y B , k B , k S ).
We then have to compute f F and f B not only for all k F and k B , but also y F and y B , and find quadruples (y

F , y B , k F , k B ) such that f F (x, y F , k F , k S ) = f B (x, y B , k B , k S )
. The time complexity becomes: Finally, we note that we can make x bigger than n nibbles, i.e., fix more than a full internal state. In that case we will need to repeat the merging operation |x| -n times before finding a valid pair of internal state and key. The time complexity becomes:

2 |k S |+|k B |+|y B | + 2 |k S |+|k F |+|y F | + 2 |k S |+|k B |+|y B |+|k F |+|y F |-|f | , ( 1
2 |k S | × 2 max(|x|-n,0) × 2 |k B |+|y B | + 2 |k F |+|y F | + 2 |k B |+|y B |+|k F |+|y F |-|f | .
(2)

Preimage Attack. In the preimage case, we want to find a pair (x, K) such that E K (x) ⊕ x = T for a fixed target T , in time less than 2 n computations of E. Informally, the problem remains the same: having fixed k S and x, find the pairs (y

F , k F ), (y B , k B ) such that f F (x, y F , k F , k S ) = f B (x, y B , k B , k S )
, among which a solution will be found. The main difference is the number of times that we need to repeat this operation.

If the path contains only one solution, and if the key is entirely fixed, we can see that we will have to repeat 2 |x| times to traverse all the possible internal states, and find the one that matches. If there are 2 t solutions (due to less "wrapping" between the input and output), then we need only 2 |x|-t repetitions.

The forward and backward key nibbles take 2 k B +k F different values. Assuming that changing these key nibbles re-randomizes properly the path, this means that we only have to repeat 2 |x|-t-k B -k F times to traverse 2 |x|-t different starting values for x. This gives the formula:

2 max(|x|-|k B |-|k F |-t,0) × 2 |k B |+|y B | + 2 |k F |+|y F | + 2 |k B |+|y B |+|k F |+|y F |-|f | .
(3)

All-subkey-recovery (ASR) and Parallel MITM (PMITM). The ASR technique was

proposed in [START_REF] Isobe | All subkeys recovery attack on block ciphers: Extending meet-in-the-middle approach[END_REF]. If the key schedule is complex, we cannot use the relations between round keys, and the effective key length increases. Any guess k F yields a value f F (x, k F , k S ) for the matching variable, and any guess k B yields a value f B (x, k B , k S ). However, the amount of matching may be too small and leave more than 2 |K| triples (k F , k B , k S ). The Parallel MITM technique overcomes this by increasing the effective output length of f F and f B : it computes in parallel for multiple starting states x. The time and memory complexities are increased by a small factor with respect to a single starting state. The PMITM is not very useful in our case, where the key schedule is simple. Furthermore, it is incompatible with GAD. Indeed, the internal state guesses y F , y B are dependent on the starting state x. Multiple parallel states would have multiple independent state guesses, and the complexity would increase faster than it decreases thanks to the PMITM.

Sieve-in-the-middle (SIM) and Bicliques. The sieve-in-the-middle technique [START_REF] Canteaut | Sieve-in-themiddle: Improved MITM attacks[END_REF] allows to sieve through an additional S-Box layer between the forward and backward path. This is done by means of an advanced list merging procedure. Sieve-in-the-middle is partially captured by GAD: though the merging procedure in the SIM attacks is more complex, it can be captured by making guesses on the forward or on the backward side. However, the modeling will not capture the fact that these guesses cost less than a recomputation of the full subpath, since they are made at the last moment.

Biclique cryptanalysis is an extension of MITM attacks used both against block ciphers [START_REF] Bogdanov | Biclique cryptanalysis of the full AES[END_REF] and hash functions [START_REF] Khovratovich | Bicliques for preimages: Attacks on skein-512 and the SHA-2 family[END_REF], where the initial structure is extended with the help of bicliques. We did not study bicliques in this paper. It is still an open question to extend the MILP models of MITM attacks with bicliques.

Quantum Computing

We assume basic knowledge of quantum computing in the quantum circuit model, such as the ket notation |• , qubits and basic operations (see, e.g., [START_REF] Michael | Quantum computation and quantum information[END_REF]). We use "time" to refer to gate counts in quantum circuits, and "quantum memory" for their width (number of qubits), in multiple of the time and memory required to implement the primitive attacked. We stress that we use only generic complexity formulas, and no technical knowledge of quantum computing is required to apply these formulas.

Quantum Memories. We use in this paper two types of quantum memory, which can be understood as a hardware assumption: QRACM (quantum-accessible classical memory) and QRAQM (quantum-accessible quantum memory). QRACM allows unittime access in superposition to a large classical memory. That is, given memory cells y 0 , . . . , y M -1 , the operation: |i |0 → |i |y i (memory access) can be implemented in time 1. Whereas QRAQM is a stronger model in which the following operation costs a time 1: |i |y 0 , . . . , y M -1 |x → |i |y 0 , . . . , y i-1 , x, y i+1 , . . . , y M -1 |y , which allows at the same time to read and write in superposition in the available quantum memory.

As can be seen in Table 1, our quantum MITM attacks require QRAQM, except Grover-meet-Simon (key-recovery) attacks.

Grover's Algorithm. Grover's search algorithm [START_REF] Lov | A fast quantum mechanical algorithm for database search[END_REF] solves the following problem: given a quantum oracle that implements a boolean function f : {0, 1} n → {0, 1}, find a preimage of 1. It is an iterative procedure that moves its internal state towards the uniform superposition of solutions. If there are t such preimages, then π x,f (x)=1 |x . Measuring this state allows to find a solution. For example, exhaustive key search uses a few plaintext-ciphertext pairs (p i , c i ) and tests:

f (k) = 1 ⇐⇒ ∀(p i , c i ), E k (p i ) = c i . With 1 expected solution, only O 2 |k|/2 calls to a quantum implementation of E k are required, instead of O 2 |k| classically (a quadratic speedup).
The calls to O f usually dominate the cost of the algorithm. Implementing the function f might require the QRACM or QRAQM model, for example when we need to access a large list.

Quantum Queries: the Q1 and Q2 model. The literature on quantum key-recovery attacks (e.g., [START_REF] Kaplan | Quantum differential and linear cryptanalysis[END_REF]) distinguishes two quantum attacker settings: Q1 (classical queries) and Q2 (quantum queries). In Q1, the quantum attacker has only access to classical secret-key oracles (decryption and / or encryption), whereas in Q2, the quantum attacker can use a quantum oracle, for example:

O E K : |x |0 → |x |E K (x) .
In particular, any computation that involves the secret-key cipher E K can now be done in superposition.

If the key length is twice the block size or more, then we can use QRACM to emulate the Q2 setting. Indeed, the cost of querying the entire codebook (classically) is lower than the cost of Grover search for the key. Thus, any quantum attacker can pre-compute the codebook, store it in QRACM, and implement O E K efficiently.

This relation between Q2 queries and QRACM will also dictate our benchmarking of the latter: while counting the time in block cipher evaluations, we will consider a Q2 query to cost 1, and a QRACM / QRAQM query to cost 1 as well.

Quantum Attacks

We reuse Theorem 4 from [SS22b, Appendix A.2], which converts a classical MITM into a quantum attack using quantum search (the exact variant of Amplitude Amplification [START_REF] Brassard | Quantum amplitude amplification and estimation[END_REF]). The quantum attack may benefit from up to a quadratic speedup with respect to the classical attack.

It considers a MITM attack that first makes g guesses, then merges two lists of size 2 F and 2 B into a list of size 2 M . It also assumes heuristically that there is a single solution, and that the subpaths leading to the solution are selected u.a.r. from all choices.

Theorem 1. Let T be the quantum time to compute an element of any of the three lists, or to recompute the full path given a partial match. There is a quantum algorithm of complexity:

2T π 4 2 g/2 + 1 2 F + π 4 2 B /2 + 1 π √ 2 max 1, 2 ( M -B )/2 + 6 , ( 4
)
that finds the key K with probability 1/2.

Intuitively, the algorithm uses a Grover search on the g guesses, under which a two-list merging is used. The two-list merging constructs the forward list first, then performs a quantum search in the backward and merged list elements. Note that the roles of forward and backward can be exchanged in this formula. We refer to [START_REF] Schrottenloher | Simplified MITM modeling for permutations: New (quantum) attacks[END_REF] for the details of this algorithm and its correctness.

In the following, like in [START_REF] Schrottenloher | Simplified MITM modeling for permutations: New (quantum) attacks[END_REF], we consider that T is smaller or equal to the quantum time necessary to implement the full primitive under attack, and we count the time in multiples of T . This simplifies the comparison with Grover search.

Q1 and Q2 Model. Though the procedure of [START_REF] Schrottenloher | Simplified MITM modeling for permutations: New (quantum) attacks[END_REF] remains valid for key-recovery attacks, the computation of one of the two lists now includes queries to the block cipher (or its inverse). For example, assume that we access the block cipher E itself. Let S be the space of plaintexts encountered during the attack. Often S becomes the full codebook, but for exhaustive search (which can be seen as a degenerate MITM attack), S contains only a constant number of elements. Let E : S → {0, 1} n be the cipher restricted to the space S.

In the classical attack, we compute the lists using classical access to E . In the quantum attack, the list elements are computed in superposition. This means that we need superposition query access to E . If S is small enough with respect to the total key size, this can be done via QRACM (sometimes at the expense of a bigger memory) in the Q1 model. Otherwise, this requires the Q2 model.

Grover-meet-Simon as a PMITM Attack

Simon's algorithm [START_REF] Daniel | On the power of quantum computation[END_REF] is a quantum algorithm that solves the boolean hidden period problem: given access to a two-to-one function f : {0, 1} n → {0, 1} m such that f (x ⊕ s) = f (x), for some secret s, find s. The algorithm runs in time O n 3 using O(n) Q2 queries to f . It has been analyzed in detail in multiple works (e.g. [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF][START_REF] Santoli | Using simon's algorithm to attack symmetric-key cryptographic primitives[END_REF]) and found to be quite robust, in particular it works well if f is a random periodic function [START_REF] Bonnetain | Tight bounds for simon's algorithm[END_REF], which models well the cases encountered in symmetric cryptography.

Simon's algorithm is the key component of many quantum attacks in the Q2 setting [START_REF] Kaplan | Breaking symmetric cryptosystems using quantum period finding[END_REF] and more recently the Q1 setting [BHN + 19]. In this paper, we will focus on the Grover-meet-Simon (GMS) attack of Leander and May [START_REF] Leander | Grover meets simon -quantumly attacking the fx-construction[END_REF]. This is a Q2 attack that finds a periodic function in a family of functions:

     F : {0, 1} κ × {0, 1} n → {0, 1} m ∀z, F z = F (z, •) ∃!k ∈ {0, 1} κ , (∃s, ∀x, F k (x) = F k (x ⊕ s))
.

GMS uses a Grover search of the right k, which calls Simon's algorithm as a test. Its quantum complexity has been analyzed in detail in [START_REF] Bonnetain | Tight bounds for simon's algorithm[END_REF][START_REF] Bonnetain | Quantum period finding against symmetric primitives in practice[END_REF]. As for Simon's algorithm, the constant in the O(n) is close to 1 if we assume the functions to be random, and the gate count in O n 3 is usually smaller than the cost of n function computations.

Even if we restrict the functions' output to one bit, this only doubles the number of queries needed by Simon's algorithm [START_REF] May | Quantum period finding is compression robust[END_REF]. Therefore, we will approximate the complexity as:

4T π 4 2 |k|/2 n , ( 5
)
where T is the cost of a query to F .

GMS-based MITM Attacks.

Consider a PMITM attack. Starting from an initial state x, it looks for a collision between the forward and backward path:

(k F , k B , k S ) such that f F (x, k F , k S ) = f B (x, k B , k S ).
The functions f F and f B can have a single-bit output.

Assume that both f F and f B are of the form:

f F (x, k F , k S ) = g F (x ⊕ k F , k S ) and f B (x, k B , k S ) = g B (x ⊕ k B , k S )
where k F and k B , of size |x|, contain nibbles of k F and k B respectively (and zero nibbles for positions at which no key is added). We are then looking for (k S , k B , k F ) such that:

∀x, g F (x, k S ) = g B (x ⊕ k F ⊕ k B , k S ) .
Therefore, when looking for MITM attacks, we can also look for GMS-based attacks. In this case, we will remove the GAD technique. We separate the key nibbles into "shared" key nibbles k S (guessed with Grover search) and "middle" key nibbles k M (found with Simon's algorithm). The part of the input x on which there is no addition of k M is fixed.

Though we would have liked to use the offline-Simon algorithm [BHN + 19], which removes the need for Q2 queries or QRACM, a technical problem arises from the fact that the functions computing the forward and backward paths are not invertible.

Modeling

In this section, we describe the MILP modeling of MITM attacks used in this paper. It relies on a cell-based representation of a cipher, which is the same as in [START_REF] Schrottenloher | Simplified MITM modeling for permutations: New (quantum) attacks[END_REF].

Previous Work

An r-round Present-like cipher is abstracted as an r-layered, weighted, undirected graph. The nodes of the graph, named cells, correspond to the S-Box operations in the cipher. The edges of the graph correspond to the exchange of nibbles in the linear layer. The MITM input-output constraint that closes the path is enforced by edges between cells of layer 0 (first round) and layer r -1 (last round). Intuitively, this corresponds to the rewriting of the MITM problem as a system of linear relations between the cells, since all the nonlinear operations are local to them. Both cells and edges are weighted. For any pair (c, c ), we use w c and w c,c to denote these weights (we have w c,c = 0 if (c, c ) is not an edge). They correspond to the number of state nibbles that one should know to determine the value of this cell or edge. For example, in the graph representation of the AES, one has w c,c = 1 for edges and w c = 4 for 4-nibble cells.

Given any set of cells C, we define the reduced list R[C] which contains all assignments of values to these cells satisfying the linear constraints. It has size:

log 2 |R[C]| = c∈C w c - (c,c )∈C 2 w c,c . ( 6
)
Thanks to the Present-like structure, as long as C does not cover all the rounds, there is a streaming algorithm that produces the elements of edges of each cell are either fixed, determined by the previous round, or undetermined. Then they correspond to forward or backward guesses y F , y B , and can be arbitrarily filled. The MITM configuration is now defined using two sets of cells:

R[C] in time |R[C]|. Indeed, incoming c 0 0 c 0 1 c 0 2 c 0 3 c 1 0 k 0 k 5 k 10 k 15 c 1 1 k 4 k 9 k 14 k 3 c 1 2 k 8 k 13 k 2 k 7 c 1 3 k 12 k 1 k 6 k 11 c 2 0 c 2 1 c 2 2 c 2 3
forward (C F ) and backward (C B ), such that C M := C F ∪ C B contains a whole round. As shown in Equation 6, the respective sizes F , B , M of R[C F ], R[C B ], R[C M ] (in log 2 ) can be deduced from the choice of C F , C B by linear inequations.
To any choice of C F , C B , there corresponds a MITM algorithm of memory min( F , B ) and running time max( B , F , M ) (in log 2 ), which consists in constructing one list, streaming the other and re-computing the path for matching pairs. Global Guesses. Any edge (c, c ) where c ∈ C B , c ∈ C F can be turned into a "global guess", as shown in Figure 3. Indeed, by guessing these values before computing R[C F ] and R[C B ], the matching on these nibbles is precomputed. If there are g nibbles of global guess, the time complexity becomes: g + max( B , F , M ) (in log 2 ). The quantum time complexity is obtained by simplifying Equation 4:

g 2 + max min( F , B ), 1 2 max( F , B , M ) . ( 7
)
Forward cells are represented in blue , backward cells in red . Global guesses are represented in green ↔. It should be noted that they only impact the memory complexity of the attack and its quantum time complexity.

Matching through MixColumns.

The difference between the Present-like and AES-like cases lies in the following property of the Super S-Box, due to the MDS property of MixColumns. Let c be a Super S-Box of width w c .

Assume that we know f, b nibbles at the previous round, from the forward and backward path, respectively, and f , b nibbles at the next round. Then we can match a total of f + b + f + b -w c nibbles through the cell, i.e., even if it does not belong to C F ∪ C B . This is because we can write linear relations between these values. This is modeled by allowing to add such a cell in the merged list (we call it a new merged cell).

We can also precompute some of these relations, like global guesses of nibbles. With limitations: • we cannot precompute more than f + b + f + b -w c relations (the total amount of matching on this cell); • we cannot precompute more than f (the amount of forward nibbles at the next round) and more than b (the amount of backward nibbles at the previous round), otherwise this would create too many constraints.

Modeling. For each cell c, we create 3 boolean variables cell_col L [c] where L ∈ {F, B, M }. We always have cell_col

F [c] + cell_col B [c] ≤ cell_col M [c],
and this is an equality if the cell is not a Super S-Box.

The list sizes and precomputed matchings are deduced from these variables using linear inequalities. For each cell, we sum its contribution to the list size (as a new temporary variable), and the amount of global reduction that it allows. We deduce the time complexity (in log 2 ), which is minimized. A complete pseudocode of this model is given in Appendix A.

Modeling the Key Schedule

Now, we move further than [START_REF] Schrottenloher | Simplified MITM modeling for permutations: New (quantum) attacks[END_REF]. Including a key schedule path is a simple transformation to the graph, where each edge is now (possibly, but not necessarily) labeled by a key nibble, as in Figure 3. This is the key nibble that is XORed on this edge.

Let us start by the new variables and constraints related to the key schedule itself. We consider a key schedule like the one of Present, which starts by initializing a key register, and then: • creates new key nibbles by applying operations in place on the key register;

• extracts the round keys from the key register.

In a similar spirit as the cell-based modeling of the state update function, we start by considering all round key nibbles as independent. We assume that they all have the same size (e.g., a single bit for Present). For example, each round of Present-80 applies a single 4-bit S-Box on the key register, so after r rounds, the total amount of key nibbles is 80 + 4r.

The operations that were applied create relations between groups of key nibbles, e.g. k 4 |k 5 |k 6 |k 7 = S(k 0 |k 1 |k 2 |k 3 ). These relations can be modeled as key cells, on the same principle as state cells. For a key cell of width w (here 4), the knowledge of at least w key nibbles allows to deduce all others.

Modeling. For each key nibble k i , we create 3 boolean variables key_col L [k i ] for L ∈ {S, B, F }. The key nibble can be either: • forward (F), i.e., known only in the forward path; • backward (B), i.e., known only in the backward path; • shared (S), i.e., known in both paths. This corresponds to k F , k B , k S in the formulas of Section 2.2.

For each key cell c, we create 3 exclusive boolean variables: key_cell_col L [c], L ∈ {S, B, F }, which indicate whether the key cell is "active" in the list of shared, forward or backward key nibbles. These variables have the following constraints:

• if key_cell_col S [c] is true, then all key nibbles attached to this cell must be shared

• if key_cell_col B [c]
is true, then all key nibbles must be shared or backward

• if key_cell_col F [c]
is true, then all key nibbles must be shared or forward

The "activation" of a key cell means that we use its relation to reduce the number of effective key nibbles, either in the shared, the backward or forward sets. Thus we compute the number of effective shared, forward and backward key nibbles by a sum over all key nibble variables, minus the reduction of key cells.

Modeling the Key Addition

We observe that the key addition can be modeled using only constraints on the coloration of key nibbles. For any key nibble k i , consider any edge e = (c, c , w c,c , k i ) where k i is added:

• If both c and c are in the forward path, then k i should be either forward, or shared.

Indeed, in order to compute the next forward cell, we have the choice between guessing k i or guessing the state nibble. This costs the same, but guessing k i will always be more advantageous, since we might reuse this guess somewhere else in the path.

x 0 x 1 x 2 x 3 S S S S k 0 k 1 k 2 k 3 M C k 0 k 1 k 2 k 3 y 0 y 1 y 2 y 3
• Likewise, if both c and c are in the backward path, then k i should be either backward, or shared.

While it is not necessary for all the key nibbles to be colored, e.g., in the PMITM case, in practice this will be the case in our attacks, since we consider simple key schedules. So the forward-backward (matching) and backward-forward (global guess) relations do not create any constraint.

Computation of the Lists. The forward and backward lists now contain both partial states and key guesses. We will start in both cases by taking values for the key nibbles, using the key cells, then compute the states round by round as before. The constraint of having at least one round not covered by C still allows to enumerate the elements of R[C] efficiently.

The list sizes are computed as before (by the contribution of each cell individually), then increased by the amount of key nibbles that they contain. In the preimage case, the time complexity reflects Equation 3. In the key-recovery case, the time complexity is given by Equation 2. If there are |x| nibbles of global reduction, and if the key-less list sizes were B , F , M , then the times are respectively, in log 2 :

max(|x| -|k B | -|k F |, 0) |k S | + max(|x| -n, 0) + max(|k B | + B , |k F | + F , |k B | + |k F | + M ) . ( 8
)
In the quantum setting, these formulas are adapted using Equation 4:

1 2 max(|x| -|k B | -|k F |, 0) 1 2 (|k S | + max(|x| -n, 0)) + max min(|k F | + F , |k B | + B ), 1 2 max(|k B | + B , |k F | + F , |k B | + |k F | + M ) . (9)

Super S-Box Case.

To understand what happens if the cell c is a Super S-Box, we must separate the S-Box layer and the MixColumns operation, as shown in Figure 4. Following the usual layout of SPN ciphers, the S-Box layer is always performed between the key addition and the MC operation.

In this example, there are 6 nibbles known in input and output, so we can form two linear relations between them, of the form: L(S(k 0 ⊕x 0 ), S(k 1 ⊕x 1 ), S(k 3 ⊕x 3 ), y 0 ⊕k 0 , y 2 ⊕ k 2 , y 3 ⊕ k 3 ) = 0, where L is a linear function. One of these relations can be precomputed as follows: L F (S(k 0 ⊕ x 0 ), S(k 1 ⊕ x 1 ), y 0 , k 2 , k 3 ) = L B (S(k 3 ⊕ x 3 ), k 0 , y 2 , y 3 ) = t. That is, we can guess the value of t beforehand. During the forward path computation, we will obtain y 0 as a function of t and the other variables, and in the backward path, we obtain x 3 as a function of t and the other variables.

To enable this, we just need to ensure the following additional constraints for each edge (c, c , w c,c , k i ): • if c is forward and c is a new merged cell, then k i must be forward; • if c is backward and c is a new merged cell, then k i must be backward. These constraints allow to go through the upper S-Box layer and access the inputs to the MC layer. In particular, there are no constraints on the key nibbles below.

Remark 1 (Double key addition). In the path of a preimage attack of a compression function, we may have a key addition before the first round 0, and after the last round r -1. This means that two key nibbles are added on the edges that connect rounds 0 and r -1. Since our model does not allow two key additions on an edge, we add a new round of "dummy" single-nibble operations between the two additions.

Adaptation to the Key-recovery Setting

In the key-recovery case, going from round 0 to round r -1 requires a query to the block cipher. This is modeled by adding a new round with a single cell (the "cipher cell"), as large as the internal state, which is connected to round 0 and to round r -1. The cipher cell must belong either to C F (decryption queries) or to C B (encryption queries).

Role of the Global Reduction.

The nibbles of global reduction serve as a way to reduce the memory complexity in preimage attacks. In key-recovery attacks, the same variables correspond to the cut-set. This change of perspective is visible in Equations 8 and 9. While a preimage attack requires to loop over the values given to the global guesses, a key-recovery attack can fix n of these nibbles for free.

Data Complexity.

In key-recovery attacks, we may want to control or minimize the data complexity. This can be done as follows. Assume without loss of generality that the cipher cell c belongs to C B . We look at all the edges connecting c with cells at round 0, and count the weight of edges that: • connect with forward cells (thus, can be globally fixed);

• do not have a backward key nibble. The data complexity can be upper bounded by the state size, minus the sum of weights of all such edges: this corresponds to the total number of state bits that can vary when the queries are made. Similar constraints apply if c belongs to C F .

PMITM and Grover-meet-Simon. In the PMITM case, we add the constraints that all cells should have a zero contribution to the list sizes (which will only depend on the initial state, and on key bit guesses), and we do not count the merged list size. We only require some matching between the forward and backward paths to occur.

Grover-meet-Simon is a subcase of PMITM, as we have seen in Section 2.5. In this case, we can compute an approximation of the complexity by counting only the "shared" key nibbles of the path. The key nibbles XORed to the starting state are not colored. They are the "middle" key nibbles k M defined in Section 2.5.

Application to AES-like Designs

In this section, we detail two of our applications to AES-like designs (more can be found in Appendix C). In each case, we only give the details of one solution path, but several solutions actually lead to the same complexity. How these paths translate into attack algorithms was discussed previously in Section 2. For completeness, we include detailed descriptions of the attacks in Appendix B, and we only give here the main ideas.

The figures use the following color / symbol scheme: green ↔ for global guesses, shared key nibbles k S and matching through MixColumns; blue for the forward path and k F ; red for the backward path and k B . Additionally, matchings between forward and backward are displayed as cyan edges.

Pseudo-preimage Attack on SATURNIN-Hash

Saturnin is one of the second-round candidates of the NIST LWC competition [CDL + 20]. The block cipher has both a block and a key size of 256 bits, and it can be abstracted as an AES-like design operating on a 4×4 matrix of 16-bit nibbles. A single round of this representation is actually a "Super-round" that corresponds to two rounds in Saturnin. It adds a key which alternates between the master key and a rotated version of it, then applies either a transformation on the rows (MixRows) or the columns (MixColumns). This can be viewed equivalently as the composition of a transposition, followed by a MixColumns, but the key bytes have to be positioned appropriately.

The hash function Saturnin-Hash uses the block cipher as a compression function. In [DHS + 21], the authors gave a pseudo-preimage attack on 7 super-rounds (out of 16) of time 2 208 and memory 2 48 . We improve this time to 2 192 , at the expense of a larger memory, using the path of Figure 5.

We start by fixing the 4 key nibbles k 1,2,3,11 . In the forward list, we put 6 nibbles k 5,6,7,8,9,10 and in the backward list, we put the 6 others k 0,4,12,13,14,15 . We also fix the values of 14 state nibbles: 9 arrows, 2 linear relations through c 3 0 , 1 linear relation through c 5 0 , c 5 1 , c 5 2 respectively. The forward list is computed as follows: we start from c 2 2 , which needs 4 nibble guesses. Going through c 3 0 , the two nibbles are deduced using the two precomputed linear relations. The same is done through round 5, so there is nothing more to guess. The list is of size 2 6×16+4×16 = 2 160 . The backward list guesses 3 nibbles at round 5 (the other ones are deduced by the linear relations), then one nibble at round 3, so it has the same size.

There are 10 linear relations between backward and forward: 4 relations through MixColumns at round 1, 2 relations which hadn't been used yet in c 3 0 , and 4 matchings of nibbles. As we obtain a list of 2 160 partial (pseudo)-preimages on 4 nibbles (the blue nibbles going through round 7) there remains to repeat this operation 2 2×16 times.

In the quantum setting, our tool finds an attack on the same number of rounds, of complexity 2 115.55 and using 2 32 QRAQM. The path is quite different, and corresponds to a classical attack with reduced memory. For completeness we include it in Appendix C.2.

Key-recovery Attack on full FUTURE

Future [START_REF] Kishan | FU-TURE: A lightweight block cipher using an optimal diffusion matrix[END_REF] is an AES-like cipher with 64-bit blocks and 128-bit keys. Its internal state is represented as a 4 × 4 matrix of 4-bit nibbles. The round function applies the following operations: • SubCells (S-Boxes); • MixColumns; • ShiftRows; • AddRoundKey. One can note that the order of operations is different from the AES; also, ShiftRows rotates the rows to the right (and not to the left like in the AES). There are 10 rounds; MixColumns is omitted at the last round.

The key addition alternates between two 64-bit subkeys k 0 , k 1 , where k 0 is first added in the "pre-round", and then, the key added at round i is rotated by 5(i/2) bits.

Because the key bits are not aligned with the state nibbles, due to the rotations, we model the structure of Future at the bit level. The composition of SubCells and MixColumns is viewed as a Super S-Box operating on 16 bits. When matching through MixColumns, groups of key bits that belong to the same S-Box should not have incompatible colors (i.e., both backward and forward). But since they come from the same cell, this is already ensured by the coloring constraints.

c 0 0 k 5 k 6 k 7 k 8 k 0 k 1 k 2 k 3 c 0 1 k 9 k 10 k 11 k 12 k 4 k 5 k 6 k 7 c 0 2 k 13 k 14 k 15 k 0 k 8 k 9 k 10 k 11 c k 1 k 2 k 3 k 4 k 12 k 13 k 14 k 15 R 0 c 1 0 c 1 1 c 1 2 c R 1 c 2 0 k 5 k 6 k 7 k 8 k 0 k 1 k 2 k 3 c 2 1 k 9 k 10 k 11 k 12 k 4 k 5 k 6 k 7 c 2 2 k 13 k 14 k 15 k 0 k 8 k 9 k 10 k 11 c k 1 k 2 k 3 k 4 k 12 k 13 k 14 k 15 R 2 c 3 0 c 3 1 c 3 2 c R 3 c 4 0 k 5 k 6 k 7 k 8 k 0 k 1 k 2 k 3 c 4 1 k 9 k 10 k 11 k 12 k 4 k 5 k 6 k 7 c 4 2 k 13 k 14 k 15 k 0 k 8 k 9 k 10 k 11 c k 1 k 2 k 3 k 4 k 12 k 13 k 14 k 15 R 4 c 5 0 c 5 1 c 5 2 c R 5 c 6 0 k 5 k 6 k 7 k 8 k 0 k 1 k 2 k 3 c 6 1 k 9 k 10 k 11 k 12 k 4 k 5 k 6 k 7 c 6 2 k 13 k 14 k 15 k 0 k 8 k 9 k 10 k 11 c k 1 k 2 k 3 k 4 k 12 k 13 k 14 k 15 R 6 R 7
With our tool, we find an attack4 of time complexity 2 126 and memory 2 34 . The path is displayed in Figure 6. Due to space constraints, we have only represented the added key bits as color rectangles. Groups of 4 consecutive bits go through a single S-Box before the MixColumns operation.

In the forward path, we guess 14 key bits. In the backward path, we guess 22 key bits. The other 92 key bits are shared. There are 15 state nibbles guessed in total, and 1 nibble (4 bits) of linear relation at c 2 3 . Going forwards, we compute the states c 1 and then c 2 without having to make any state guess. At c 2 3 we use the single nibble of linear relation that we have precomputed; we have to guess 3 other nibbles. To compute c 5 we have to guess 2 nibbles. Thus the forward list is of total size: 2 14+5×4 = 2 34 .

Going backwards, we have immediately the value of c 1 1 (the single red state nibble remaining is deduced by the precomputed linear relation, which relates it to the backward key bits). There is no other guess to make until round 7, where we need to guess 3 nibbles. Thus the list size is also 2 34 .

In the merged list, we can note that there are 3 nibbles of matching at round 2, since we only precomputed one linear relation. There are also 3 nibbles at round 6, going through MixColumns. Finally, there are 3 nibbles of matching at round 8. This makes a total of 36 bits of matching, so the merged list is of size 2 32 .

In [START_REF] Kishan | FU-TURE: A lightweight block cipher using an optimal diffusion matrix[END_REF] the authors estimated that MITM attacks could reach up to 7 rounds of the cipher. However this estimate did not take into account the GAD technique. Indeed, in this attack, state guesses allow roughly to extend the forward path by two rounds, and the backward path by one round.

Application to Present-like Designs

In this section, we show some applications of our results to Present-like designs, where there is no Super S-Box. Because the designs attacked here involve either a large number of rounds or state nibbles, we only sketch briefly the structure of the attacks and give zoomed-out versions of some of the pictures. The full pictures can be automatically generated using our code.

Application to Present

Present [BKL + 07] is an SPN cipher with a state of 16 × 4 bits. It uses a 4-bit S-Box, and the linear layer is a permutation of the bits. While the best key-recovery attacks on the block cipher Present are linear attacks, they have a large data complexity. The main advantage of MITM attacks is a small data complexity.

The Sieve-in-the-middle technique introduced in [CNV13] allowed to find an attack on 7-round Present-80 in time 2 73.42 . Using bicliques, this attack can be extended to 8 rounds with the same time complexity, and 2 6 data complexity.

With our tool, we are able to obtain a GAD attack on 9 rounds with a comparable 2 8 data complexity, and a time complexity 2 78 . A bird's eye view of the attack path is represented in Figure 7. The data complexity appears clearly since all state bits except 8 are fixed between the first round and the encryption cell.

We detail the choice of backward and forward key bits. Since each round of key scheduling applies an S-Box, there are a total of 9 key cells relating the key bits, and a total of 80 + 9 × 4 = 116 key bits. In the forward key, we take k 20 , k 21 , k 24 , k 25 from the master key, and two key bits k 81 , k 82 that appear on the left at the second round. Four key bits k 15 , k 16 , k 17 , k 18 , which are the remaining forward key bits visible at the first round, are deduced with a key cell relation.

c 0 0 c 0 1 c 0 2 c 0 3 R 0 c 1 0 c 1 1 c 1 2 c 1 3 R 1 c 2 0 c 2 1 c 2 2 c 2 3 R 2 c 3 0 c 3 1 c 3 2 c 3 3 R 3 c 4 0 c 4 1 c 4 2 c 4 3 R 4 c 5 0 c 5 1 c 5 2 c 5 3 R 5 c 6 0 c 6 1 c 6 2 c 6 3 R 6 c 7 0 c 7 1 c 7 2 c 7 3 R 7 c 8 0 c 8 1 c 8 2 c 8 3 R 8 R 9 c 10 0 R 10
All other key cells reduce the shared key bits. In the backward list, we only guess two key bits k 41 , k 42 and there are no active key cells. Four bits of state guesses are required to activate the last two backward cells. All lists have size 2 6 . We can also fine-tune the trade-off between data and time, for example by taking a limit of 2 12 data, we find a slightly smaller complexity 2 77 .

Application to FLY and PIPO

The lightweight block ciphers Fly [START_REF] Karpman | The littlun s-box and the fly block cipher[END_REF] and Pipo [KJK + 20] are structurally similar with respect to MITM attacks. Both are Present-like SPN ciphers with 64-bit blocks, but 8-bit S-Boxes, where the linear layer is a bit-permutation. Though the S-Box and permutation differ between both designs, the cell-based representation will be the same. Indeed, what only matters for us is that between any pair of S-Boxes of two successive rounds, there is a single-bit linear relation.

This simplification is allowed by the simple key schedule of both ciphers. Fly uses a 128-bit master key which is equivalent to k 0 ||k 1 , where k 0 is used in even rounds and k 1 in odd rounds. Pipo-128 does the same, while Pipo-256 has a 256-bit key which is separated in 4 subkeys k = k 3 k 2 k 1 k 0 used alternatively. The only difference between Fly and Pipo-128 is the final key addition in Pipo-128. Furthermore, in the attacks, the final key is always entirely known in the backward path. Applying a final bit permutation or not will lead to the same attack paths and complexities.

To the best of our knowledge, our attacks are the best against Fly and Pipo, exceeding the differential and linear cryptanalysis performed by the authors of Pipo (who reported 9-round and 11-round attacks respectively). We defer the details of the 128-bit versions to Appendix C.6 and focus here on our attack on full Pipo-256 (18 rounds).

Our attack has a time complexity 2 252 and a memory complexity 2 60 . It uses the path given in Figure 8. There are 183 shared key bits, 13 forward and 60 backward. There are no state guesses backwards, as can be seen on the path. Forwards, we need to guess a total of 56 bits: 12 bits at round 7, 16 bits at round 8, 12 bits at round 11, 16 bits at round 12. Thus the list is of size 2 69 . In the middle, there are 64 bits of matching (a full state), so the merged list size is 2 65 . The overall complexity is dominated by the computation of the forward path: 2 69+183 = 2 252 .

Conclusion

In this paper, we extended the cell-based modeling of [START_REF] Schrottenloher | Simplified MITM modeling for permutations: New (quantum) attacks[END_REF] to find MITM attacks on ciphers and compression functions with simple key schedules. The attacks obtained show that the MITM technique is quite powerful when the key schedule is weak, even if the cipher itself has a good diffusion.

At the moment, we conjecture that our modeling is optimal when the key-schedule has only S-Boxes and permutations as defined in Section 2. A natural open question would be to extend this further to the case of key schedules with complex linear layers, like AES. However, this seems to induce complex linear relations between the key nibbles and complex relations between state and key, which only a more fine-grained modeling can capture [START_REF] Bao | Superposition meet-inthe-middle attacks: Updates on fundamental security of AES-like hashing[END_REF]. For example, in preimage attacks on AES variants, one would like to guess nibbles or enforce constraints on linearly modified round keys (to have no impacts through MixColumns for example). Our model cannot find such constraints.

Regarding quantum MITM attacks, we have encountered instances of the Grover-meet-Simon attack [START_REF] Leander | Grover meets simon -quantumly attacking the fx-construction[END_REF] which cannot be turned "offline" [BHN + 19]. Doing so would provide a valuable improvement of these attacks.

A Complete MILP Model with Keys

We give the generic MILP model for the GAD case, possibly with some matching through MixColumns. Matching through MC is possible only at the cells which are indicated to be Super S-Boxes. The pseudocode that we give below is a slightly different and simplified version of the file modeling.py available at https://github.com/AndreSchrottenloher/ key-mitm.

The input is given as a graph. We have a set of cells C with weights w c , a set of key nibbles K, a set of edges E ⊆ C × C × N × K which have both a weight and a key nibble attached, a set of key cells KC also with weights, and corresponding input and output key nibbles. We assume that all edges and key nibbles have weight 1.

Since this modeling is built over [START_REF] Schrottenloher | Simplified MITM modeling for permutations: New (quantum) attacks[END_REF], we indicate the new parts that are related to key nibbles in orange (lines 10-31). The variable names |x|, |k F |, |k S |, |k B |, F , B , M are taken in order to connect immediately to the formulas of Equation 8 and Equation 9.

Variables for the coloration of cells and basic constraints on the path 1: for all cell c ∈ C do 2:

Variable (boolean) cell_col L [c] for L ∈ {F, B, M, N } Forward, backward, merged cells and also "new merged" cells which can appear if the cell is a Super S-Box

3: Constraint cell_col M [c] = cell_col F [c] + cell_col B [c] + cell_col N [c] 4:
If c is not a Super S-Box, Constraint cell_col N [c] = 0 5: end for 6: For all round r, Constraint "no N cell for both r and r + 1" 7: Constraint "at least one round without B cell" 8: Constraint "at least one round without F cell" 9: Constraint "at least one round with all cells M " Variable and constraints on the coloration of key nibbles 10: for all key nibble k ∈ K do

Constraint 1+key_col F [k]+key_col S [k] ≥ cell_col F [c]+cell_col N [c ]+cell_col F [c ]
If both cells are backward (or "new merged" for the below cell) then key nibble is backward or shared 16: Variable global_red[c] (continuous, between 0 and w c )

Constraint 1+key_col B [k]+key_col S [k] ≥ cell_col B [c]+cell_col N [c ]+cell_col B [c ]
Global reductions only happen at forward (guessed edges) and "new merged" (through MC) cells. The following limit holds in both cases:

B Attack Algorithms

In this section, we illustrate the conversion of a MITM attack path (found with our model) into a MITM attack algorithm on the two examples of Section 4. The attacks of Section 5 are easier to write down since they do not involve matching through MixColumns.

B.1 Pseudo-preimage Attack on Saturnin-Hash

We detail the algorithm of the attack given in Section 4.1 (Figure 5). Recall that a single super-round of Saturnin applies the following operations: AddRoundKey, SubBytes, MixColumns (resp. MixRows). The attack does not depend on the definition of the (super) S-Box, nor the mixing layer (as long as it uses an MDS matrix). Below we simply need to write linear equations that relate the input and output nibbles of the mixing operation; we do not detail these equations and simply introduce linear functions of the nibbles. We use S to denote the super S-Box. We use the following notations to coincide with the figure: x j i for the column i after the key addition at round j (the arrows entering cell c j i ) and z j i after the mixing layer (the arrows exiting cell c j i ). We also reuse the forward / backward / {merged, shared} coloring scheme in the writing to make the separation of the forward and backward computations clearer. Forward and Backward Computations. The forward path (Algorithm 1) starts at round 2 and stops at round 0. The backward path (Algorithm 2) starts at round 4 and stops at round 2.

B.2 Key-recovery Attack on FUTURE

We detail the algorithm of the attack given in Section 4.2 (Figure 6). Recall that a single round of Future applies the following operations: SubCells, MixColumns, ShiftRows, AddRoundKey, and there is a "pre-round" key addition before round 0. The key addition alternates between k 0 and k 1 where k 0 is first added in the pre-round.

The attack does not depend on the specification of the S-Box nor the MixColumns, as soon as the matrix is MDS. Like above, we will introduce many linear functions L i , L i without giving their full specification. The S-Box is denoted S. Notation. Our notation coincides with Figure 6 as follows. Rounds are numbered from 0 to 9. We use (x i 0 , x i 1 , x i 2 , x i 3 ) to denote the 4 columns of the state at the beginning of round i, thus (x 0 0 , x 0 1 , x 0 2 , x 0 3 ) is the state after the pre-round key addition, and before the first S-Box layer. We denote by (z i 0 , z i 1 , z i 2 , z i 3 ) the state after the MC layer of round i. On the figure this means that x i j is the value on the top of cell c i j (incoming edges), and z i j the value on the bottom (outgoing edges). For a column x i j , we use x i j [u] (0 ≤ u < 4) to denote individual 4-bit nibbles in this column. The SR operation transforms the state as follows:

    z 0 [0] z 1 [0] z 2 [0] z 1 [0] z 0 [1] z 1 [1] z 2 [1] z 3 [1] z 0 [2] z 1 [2] z 2 [2] z 3 [2] z 0 [3] z 1 [3] z 2 [3] z 3 [3]     →     z 0 [0] z 1 [0] z 2 [0] z 3 [0] z 3 [1] z 0 [1] z 1 [1] z 2 [1] z 2 [2] z 3 [2] z 0 [2] z 1 [2] z 1 [3] z 2 [3] z 3 [3] z 0 [3]     (18)
We use x i j [u][v] (0 ≤ v < 4) to denote individual bits within a nibble. The key bits are denoted k j [i] for j ∈ {0, 1} and i ∈ {0, . . . , 63}. Finally, multiple bits (resp. nibbles) will be denoted either x[u, u ] or x[u-u ] for a range of values {u, . . . , u }. As an example, the state at the beginning of round 1 is related to the state at round 0 by:

    x 1 0 [0] x 1 1 [0] x 1 2 [0] x 1 3 [0] x 1 0 [1] x 1 1 [1] x 1 2 [1] x 1 3 [1] x 1 0 [2] x 1 1 [2] x 1 2 [2] x 1 3 [2] x 1 0 [3] x 1 1 [3] x 1 2 [3] x 1 3 [3]     =     z 0 0 [0] ⊕ k 1 [0-3] z 0 1 [0] ⊕ k 1 [16-19] z 0 2 [0] ⊕ k 1 [32-35] z 0 3 [0] ⊕ k 1 [48-51] z 0 3 [1] ⊕ k 1 [4-7] z 0 0 [1] ⊕ k 1 [20-23] z 0 1 [1] ⊕ k 1 [36-39] z 0 2 [1] ⊕ k 1 [52-55] z 0 2 [2] ⊕ k 1 [8-11] z 0 3 [2] ⊕ k 1 [24-27] z 0 0 [2] ⊕ k 1 [40-43] z 0 1 [2] ⊕ k 1 [56-59] z 0 1 [3] ⊕ k 1 [12-15] z 0 2 [3] ⊕ k 1 [28-31] z 0 3 [3] ⊕ k 1 [44-47] z 0 0 [3] ⊕ k 1 [60-63]    
Path Details. In the attack, the forward and backward key bits are:

k F := k 1 [13-15, 32-39, 57-59], |k F | = 14 k B := k 0 [17-24], k 1 [9-12, 30, 31, 49-56], |k B | = 22 (19)
and the shared key bits k S are the 92 remaining others. The 15 state nibbles which are fixed (cut set) are the following:

X := x 1 0 [0, 1, 2], x 1 0 [3][0], z 0 1 [3][1, 2, 3] , z 0 2 [0], z 0 1 [1], x 1 2 [2, 3], x 1 3 [0, 1, 3], x 1 3 [2][0], z 0 1 [2][1, 2, 3] , x 2 0 [3], x 2 1 [0], x 2 2 [1] . ( 20
)
Algorithm 3 Forward computation for the attack on Future. Global: k S , X, t Input: 14 bits of k F , 20 bits for state guesses Output: 9 nibbles for matching

1: procedure f F 2:
Using the value of X and the value of k F , compute: 3:

     x 1 0 = x 1 0 [0, 1, 2], x 1 0 [3][0]|(k 1 [13, 14, 15] ⊕ z 0 1 [3][1, 2, 3]) x 1 2 = k 1 [32-35] ⊕ z 0 2 [0], k 1 [36-39] ⊕ z 0 1 [1], x 1 2 [2, 3] x 1 3 = x 1 3 [0, 1, 2], x 1 3 [2][0]|(k 1 [57-59] ⊕ z 0 1 [2][1, 2, 3]) 3: Deduce x 2 0 , x 2 1 , x 2 2 except the nibbles x 2 0 [3], x 2 1 [0], x 2 2 [1] 4: Use X to complete x 2 0 [3], x 2 1 [0], x 2 2 [1]; guess x 3 0 [1], x 3 2 [3], x 3 3 [0]
Using the value of X and the value of k B , compute:

z 1 1 [0-3] = k 0 [21-24] ⊕ x 2 1 [0], k 0 [41-44] ⊕ x 2 2 [1], k 0 [61-63, 0] ⊕ x 2 3 [2], k 0 [17-20] ⊕ x 2 0 [3] 4:
Using the value of k B and k S , deduce

z 0 0 [1], z 0 1 [0], z 0 2 [3], z 0 3 [2]

C.2 Application to Saturnin-Hash

The path of our quantum pseudo-preimage attack on the Saturnin-Hash compression function, reduced to 7 Super-rounds, is given in Figure 10. The forward list is of size 2 16×4 , the backward list is of size 2 16×2 , and in both cases this comes only from the key nibbles. A total of 16 state nibbles are fixed: 6 green edges between R 3 and R 4 , 4 green edges between R 4 and R 5 , and 3 + 3 precomputed linear relations through c

C.3 Application to Saturnin

The best classical key-recovery attack (in the single secret-key model) on Saturnin is the DS-MITM attack on 7.5 Super-rounds reported in [CDL + 20], with time complexity 2 244 . This corresponds to 7 Super-rounds followed by another S-Box layer, and a key addition.

With our framework, we reach 6.5 Super-rounds with the path of Figure 11. The time complexity is 2 248 , and the data complexity is similar. The forward list contains half a key nibble (k 12 ) and two halves of state nibble guesses, so it has size 2 24 . The backward list contains 3.5 key nibbles (k 6,10,14 , k 12 ). There are 2 nibble conditions for merging (one through c 1 2 and one through c 4 0 ), so the merged list is of size 2 24 . For comparison, the best classical attack on 6.5 Super-round Saturnin would be a Square attack, which initially targets 6-round AES [FKL + 00]. State nibbles in Saturnin are twice the size of AES bytes, so the complexities are (roughly) squared. To accommodate the additional half Super-round, the time increases by a factor 2 64 (corresponding to the All lists are of size 2 20 . In the forward list, besides the 7 key bits, we need 8 bits of state guesses at round 4 and 5 bits at round 6. In the backward list, we need 4 bits at round 7. Then, because we know 4 backward cells at round 7 and 5 forward cells at round 6, there is 4 × 4 = 20 bits of matching between them, so the merged list is also of size 2 20 . A search for quantum attacks does not yield the same results. We find valid paths when removing two rounds. However, for Fly the number of rounds reached is smaller than quantum linear attacks [START_REF] Schrottenloher | Quantum linear key-recovery attacks using the QFT[END_REF] and for Pipo-128 this is only as good.

Column 0 k 0 k 5 k 10 k 15 Column 1 k 4 k 9 k 14 k 3 Column 2 k 8 k 13 k 2 k 7 Column 3 k 12 k 1 k 6 k 11 k 0 k 5 k 10 k 15 k 4 k 9 k 14 k 3 k 8 k 13 k 2 k 7 k 12 k 1 k 6 k 11 Figure 2 :

 123112 Figure 2: Two rounds of AES with two keys k and k , using the Super S-Box representation.

t

  calls to the oracle O f : |x |0 → |x |f (x) are sufficient to reach a state very close to: 1 √ t

Figure 3 :

 3 Figure 3: Two global guesses (green ↔ edges) in the path of an AES-like cipher.

Figure 4 :

 4 Figure 4: Key addition in the Super S-Box case.

Figure 5 :

 5 Figure 5: Path of a 7 Super-round pseudo-preimage attack on Saturnin-Hash.

Figure 6 :

 6 Figure 6: Path of the key-recovery attack on full Future. Individual edges correspond to S-Boxes, which are aligned with groups of 4 key bits.

Figure 7 :

 7 Figure 7: Low-data MITM attack on 9 rounds of Present-80.

Figure 8 :

 8 Figure 8: Path of the 18-round attack on Pipo-256.

Variable

  (boolean) key_col L [k] for L ∈ {F, B, S} 12: Constraint key_col B [k] + key_col F [k] + key_col S [k] = 1 13: end for 14: for all edge (c, c , w, k) do If both cells are forward (or "new merged" for the below cell) then key nibble is forward or shared 15:

  17: end for Constraints on the coloration of key cells 18: for all key cell kc do 19:Variable (boolean) key_cell_col L [kc] for L ∈ {F, B, S} 20: Constraint key_cell_col S [kc] + key_cell_col F [kc] + key_cell_col B [kc] ≤ 1 21:for k in input and output key nibbles of kc do 22:Constraint key_col S [k] ≥ key_cell_col S [kc] 23: Constraint key_col S [k] + key_col F [k] ≥ key_cell_col F [kc] 24: Constraint key_col S [k] + key_col B [k] ≥ key_cell_col B [kc]25: end for 26: end for Total amount of key nibbles 27: Variable (integer) |k L | for L ∈ {F, B, M, S} 28: for L ∈ {F, B, S} do 29: Constraint |k L | = k∈K key_col L [k] -kc∈KC w(kc)key_cell_col L [kc] 30: end for 31: Constraint |k M | = |k F | + |k B | "Global reduction" variables 32: for all cell c ∈ C do 33:

  ] ≤ (connections with backward cells at round before) "Connections" are computed by weighted sums of cell coloration variables35: if c is a super S-Box then 36: global_red[c] ≤ w c (cell_col N [c] + cell_col F [c])For a "new merged" cell, it depends on the number of connections to other backward and forward cells 37: global_red[c] ≤ (connections with colored cells) -w c cell_col N [c] 38: global_red[c] ≤ w c cell_col F [c]+(connections with forward cells at round after) 39: else 40: global_red[c] ≤ w c cell_col F [c] 41: end if 42: end for 43: |x| = c∈C global_red[c] List sizes 44: for c ∈ C do 45: Variable (continuous) cell_contrib L [c] for L ∈ {F, B, M } 46: cell_contrib L [c] = w c cell_col L [c] -connections with cells of the same color at round before 47: end for 48: L = ( c cell_contrib L [c]) -|x| 49: Memory complexity: min( F + |k F |, B + |k B |) 50: Time complexity: determined from F , B , M , |x|, |k B |, |k F |, |k S | using the formulas of Equation 8 and Equation 9.

c 0 0 k 0 k 5 k 10 k 15 c 0 1 k 4 k 9 k 14 k 3 c 0 2 k 8 k 13 k 2 k 7 c 0 3 k 12 k 1 k 6 k 11 R 0 c 1 0 k 0 k 5 k 10 k 15 c 1 1 k 4 k 9 k 14 k 3 c 1 2 k 8 k 13 k 2 k 7 c 1 3 k 1 k 4 k 9 k 14 k 3 c 2 2 k 8 k 13 k 2 k 7 c 2 3 kk 0 k 5 k 10 k 15 c 4 1 k 4 k 9 k 14 k 3 c 4 2 k 8 k 13 k 2 k 7 c 4 3 k 12 k 1 k 6 k 11 R 4 c 5 0 k 0 k 5 k 10 k 15 c 5 1 k 4 k 9 k 14 k 3 c 5 2 k 8 k 13 k 2 k 7 c 5 3 kFigure 9 :

 0123012312312301239 Figure 9: Path of a 7-round key-recovery attack on the 1k-AES structure.

k 5 k 6 k 7 k 8 k 0 k 1 k 2 k 3 c 0 1 k 9 k 10 k 11 k 12 k 4 k 5 k 6 k 7 c 0 2 k 13 k 14 k 15 k 0 k 8 k 9 k 10 k 11 c 0 3 k 1 k 2 k 3 k 4 kk 5 k 6 k 7 k 8 k 0 k 1 k 2 k 3 c 4 1 k 9 k 10 k 11 k 12 k 4 k 5 k 6 k 7 c 4 2 k 13 k 14 k 15 k 0 k 8 k 9 k 10 k 11 c 4 3 k 1 k 2 k 3 k 4 kk 5 k 6 k 7 k 8 k 0 k 1 k 2 k 3 c 6 1 k 9 k 10 k 11 k 12 k 4 k 5 k 6 k 7 c 6 2 k 13 k 14 k 15 k 0 k 8 k 9 k 10 k 11 c 6 3 k 1 k 2 k 3 k 4 kR 7 Figure 10 :

 812034812034812034710 Figure 10: Path of a 7 Super-round quantum pseudo-preimage attack on Saturnin-Hash.

c 0 0 k 5 k 6 k 7 k 8 k 0 k 1 k 2 k 3 c 0 1 k 9 k 10 k 11 k 12 k 4 k 5 k 6 k 7 c 0 2 k 13 k 14 k 15 k 0 k 8 k 9 k 10 k 11 c 0 3 k 1 k 2 k 3 k 4 kk 5 k 6 k 7 k 8 k 0 k 1 k 2 k 3 c 4 1 k 9 k 10 k 11 k 12 k 4 k 5 k 6 k 7 c 4 2 k 13 k 14 k 15 k 0 k 8 k 9 k 10 k 11 c 4 3 k 1 k 2 k 3 k 4 kFigure 11 :

 081203481203411 Figure 11: Path of a 6.5 Super-round key-recovery attack on Saturnin. The key nibble k 12 is half blue, half red.

Figure 12 :

 12 Figure 12: Path of the 10-round attack on Pipo-128.

Table 1 :

 1 Attacks overview. Complexities are given in log 2 . The 'time' column includes the generic attack time. In the 'memory' column, '*' means QRACM and '**' means QRAQM.

	Target	Rounds	Time	Memory	Data	Reference
			Classical
	1k-AES	7	112 / 128	40	80	Section C.1
	1k-AES	7	120 / 128	32	32	Section C.1
	2k-AES	10	248 / 256	48	128

  ) and the memory complexity is min(2 |k B |+|y B | , 2 |k F |+|y F | ). To have a valid attack, we need |y B | + |y F | < |f |, i.e., the guesses allow to deduce more matching state nibbles.

  Algorithm 1 Forward computation for the attack on Saturnin-Hash.Global: guess of t 5 to t 9 , 9 state nibbles Input: k F (6 key nibble guesses) and 4 state guesses

		Output: 10 nibbles for matching
	1: procedure f F
	2: 3: 4:	Guess x 2 2 (use 4 guesses) Deduce x 3 3 (use 3 global state nibbles) Use Equation 12 and Equation 13 to deduce both x 4 3 [0] and x edge z 2 2 [1]	[0] from the incoming

  12 bits of state guess These states are unknown because backward key nibbles were added to them

	Algorithm 4 Backward computation for the attack on Future.
		Global: k S , X, t
		Input: 22 bits for k B , 12 bits for state guesses
		Output: 9 nibbles for matching
	1: procedure f B
	2:	Using Equation 21, t and k B , deduce x 2 3 [2]
	5:

https://github.com/AndreSchrottenloher/key-mitm

Demirci-Selçuk Meet-in-the-middle attacks[START_REF] Demirci | A meet-in-the-middle attack on 8-round AES[END_REF], which do not rely as much on the key schedule as the simple MITM, are sometimes named "MITM" in the literature. We do not consider them here.

In this paper, the forward, backward (and shared) key nibbles will entirely cover the master key. It is not necessarily the case, but it happens when the key-schedule is very simple.

Actually, our optimization yields an even better attack with time complexity 2 124 and memory 2 84 , but the path is much more complicated.

Acknowledgments. We thank the reviewers of ToSC for their helpful feedback and comments. A.S. would like to thank Susanta Samanta for providing details on the specification of the block cipher FUTURE. Part of this work done at CWI by A.S. has been supported by ERC-ADG-ALGSTRONGCRYPTO (project 740972). This work has been partially supported by the French Agence Nationale de la Recherche through the DeCrypt project under Contract ANR-18-CE39-0007, and through the France 2030 program under grant agreement No. ANR-22-PETQ-0008 PQ-TLS.

Path Details. The forward, backward and shared key nibbles are:

We fix a total of 14 state nibbles, including 9 arrows and 5 linear relations through the mixing layer. We write equations depending on linear functions L i , L i , whose exact specification depends on the mixing layer. For example, for the matching through c 1 0 , we relate outputs of the cells at round 0 (z variables) with inputs of the cells at round 2 (x variables):

Similarly through c 1 1 , c 1 2 , c 1 3 respectively:

Through c 3 0 we have two linear relations to precompute, for which we select appropriate choices of input and output nibbles:

and we can write two additional equations for matching, using the rest of the nibbles. Finally we write the linear relations precomputed through c 5 0 , c 5 1 , c 5 2 :

The additional 9 state nibble guesses (green arrows) are:

Notice that we alternate between z and x nibbles depending on the color of the key nibble that is added. Indeed, if the key nibble added on the edge is forward, then the state nibble must be fixed before the key addition (otherwise we wouldn't be able to compute forwards).

If it is backward, the state nibble must be fixed after the key addition. Using the three linear relations through c 5 0 , c 5 1 , c 5 2 (Equation 14 to Equation 16) deduce x 6 3 8:

XOR with the target preimage and advance to x 0 3 9:

Return the following values:

Through

Two additional relations 10: end procedure Algorithm 2 Backward computation for the attack on Saturnin-Hash.

Global: guess of t 5 to t 9 , 9 state nibbles Input: k B (6 key nibble guesses) and 4 state guesses Output: 10 nibbles for matching

Guess z 4 0 [0, 1, 2] (use 3 guesses)

3:

Using the three linear relations through c 5 0 , c 5 1 , c 5 2 (Equation 14 to Equation 16) deduce z 4 1 [0, 1, 2] 4:

Complete z 4 0 and z 4 1 (use 2 global state nibbles)

5:

Compute z 3 1 and z 3 2 (use 4 global state nibbles)

Using the two precomputed relations through c 3 0 (Equation and Equation 13), deduce

Return the following values:

Two additional relations 10: end procedure In addition, we will precompute one linear relation through MixColumns. Here, notice that we cannot simply fix z 0 1 [3] and z 0 1 [2], because the key bits on this nibble have both forward and backward colors. The backward key bit addition needs to be placed before the cut set, and the forward key addition after.

Equations for Matching. We will match through MixColumns in the cells c 2 3 , c 6 1 , c 6 2 , c 6 3 , c 8 1 . Therefore we write linear equations between the input and output nibbles in these cells, and we introduce a nibble variable t. Note that in all these equations, we needed to separate the backward and forward / shared bits of the key nibbles, and the linearity of the MixColumns operation is essential. We will write for example:

) where the zeroes are zero bits and | denotes concatenation of bits.

At c 2 3 :

And similarly, with a different separation of the values:

At c 6 2 :

At c 6 3 :

And finally at c 8 1 :

and two similar equations where we replace S(

)) and L 8 by another linear function L 9 (resp. L 10 ).

Forward and Backward Computations. The forward and backward computations are detailed in Algorithm 3 and Algorithm 4. There are 9 nibble conditions of matching, i.e., 36 bits (so the merged list is of expected size 2 32 ). One can note that some of the matching conditions are independent from others; for example the three first equations on the backward path depend only on the key, and not on the state guesses.

C Details on Applications

In this section, we give some details of applications which were omitted from Section 4 and Section 5.

C.1 Application to 1k-AES and 2k-AES

We illustrate the power of GAD with the following structures: • 1k-AES: the AES block cipher with a 128-bit key k, without key schedule; • 2k-AES: the AES block cipher with alternating 128-bit keys k 0 , k 1 .

For 1k-AES, we are able to attack 7 rounds (without the final linear layer) with the path of Figure 9. Recall that each cell x i j represents the column j of the state at the end of round i. We start by guessing the values of the 11 key bytes k 0,1,2,3,4,6,7,8,9,10,11 . In the forward list, we guess the values of k 5,13,14,15 (4 bytes). In the backward list, we guess the value of k 12 (one byte).

We fix the 16 green ↔ bytes on the figure, which contain 12 bytes of the plaintext, and 4 bytes of the state after one round. The forward list contains 2 4×8 elements, as it depends only on the key bytes. The backward list also contains 2 4×8 elements, as 3 state bytes need to be guessed. There are 4 bytes of matching between them, so the merged list is also of size 2 4×8 . Thus the time, memory and data complexities are respectively 2 11×8 × 2 4×8 = 2 120 , 2 4×8 = 2 32 , 2 4×8 = 2 32 . We also obtained an attack of complexity 2 112 on this variant, but with a larger data complexity.

While DS-MITM and Impossible Differential attacks would also reach 7 rounds, both would require a much larger memory and data complexity. For 2k-AES, we are able to attack 10 rounds, including the final linear layer. Compared to the DS-MITM attack on 10-round AES-256 [START_REF] Li | Meet-in-the-middle attacks on 10-round AES-256[END_REF], our attack also benefits from a reduced memory complexity.

Compute forwards to x 4 1 , x 4 2 , x 4 3 using k S 7:

8 bits of state guess 8:

Deduce x 5 0 , x 5 1 9:

Return the following values: They correspond to the left hand sides of the matching equations Equation 22:

Complete the state at round 0:

Compute backwards (using a query to the block cipher) to z 9 ; compute z 8 0 , z 8 2 , z 8 3 7:

12 bits of state guess 8:

Deduce the entire z 7 0 , z 7 1 , z 7 2 9:

Return the following values: They correspond to the right hand sides of matching equations Equation 22:

) 10: end procedure guess of 4 key nibbles).

The best quantum key-recovery attack on Saturnin, as suggested in [CDL + 20], is given by adapting the quantum Square attack of [START_REF] Bonnetain | Quantum security analysis of AES[END_REF]. On 6 Super-rounds it will reach a time complexity 2 88 , with roughly 2 50 quantum memory and using 2 70 classical chosen-plaintext queries (and classical memory). To reach 6.5 Super-rounds, the quantum time increases to approximately 2 120 Saturnin evaluations.

In the quantum setting, our attack reaches a time complexity 2 127.55 by Equation 4 which is almost at the generic limit of 2 128 (roughly corresponding to a Grover search with large probability of success).

Grover-meet-Simon Attack. While 6 full Super-rounds are unreachable, we find a 5.5 Super-round Grover-meet-Simon attack which guesses all key nibbles except 3. By Equation 5, it has a complexity: π 2 2 104 × 48 2 110.24 . Furthermore, the data complexity is only of 2 64 , meaning that we can use Q1 queries and store them in a QRACM of size 2 64 .

C.4 Application to Haraka-v2

Haraka-v2 is a small-range hash function defined in [START_REF] Kölbl | Haraka v2 -efficient short-input hashing for post-quantum applications[END_REF] in two variants: Haraka-256 and Haraka-512, with respectively 256 and 512 bits of internal state. Both variants hash an input of respectively 256 and 512 bits using an AES-based permutation followed by a feedforward, and a truncation for Haraka-512.

The permutation is made in both cases of 5 rounds. Each round applies two AES rounds on the substates, followed by a MIX layer, which permutes the columns between substates.

Bao et al. [BDG + 21] showed an attack on 4.5-round Haraka-256 and 5.5-round (extended) Haraka-512. The latter was subsequently improved in [START_REF] Schrottenloher | Simplified MITM modeling for permutations: New (quantum) attacks[END_REF] by reducing the memory used.

Since our model subsumes the one of [START_REF] Schrottenloher | Simplified MITM modeling for permutations: New (quantum) attacks[END_REF], we verify that it finds the same attacks on Haraka. Moreover, we were able to improve the attack on Haraka-512 and to devise an attack on 6.5-rounds Haraka-512. This shows that matching in many rounds (instead of a single round as in [BDG + 21]) gives an advantage even greater than previously estimated. Note that both results were already covered by the previous model. Yet these attacks were not found in [START_REF] Schrottenloher | Simplified MITM modeling for permutations: New (quantum) attacks[END_REF], perhaps due to additional constraints used in [START_REF] Schrottenloher | Simplified MITM modeling for permutations: New (quantum) attacks[END_REF] to limit the search space. In our work, we used the Gurobi solver instead of SCIP which made the search more efficient.

C.5 Application to Gift-64

Gift-64 [BPP + 17] is a lightweight block cipher aiming at optimizing the Present design strategy, with a state of 64 bits, S-Boxes of 4 bits, and a linear layer which is a simple bit permutation. Gift-64 has a key of 128 bits.

The authors proposed a MITM key-recovery attack on 15 rounds, which was optimized by Sasaki [START_REF] Sasaki | Integer linear programming for three-subset meet-in-the-middle attacks: Application to GIFT[END_REF] using an automatic search based on MILP. We checked that in GAD mode, our model recovers the time (2 112 ) and memory (2 16 ) complexities of Sasaki's attack.

We also find a Parallel MITM attack with a slightly improved complexity. The path of this attack is actually the same as a Grover-meet-Simon attack that guesses 108 key bits, and has thus a complexity π 2 2 54 × 20 2 58.97 block cipher calls, using the same amount of Q2 queries. It only requires a small number of qubits.

C.6 Application to Pipo-128

On 11-round Fly and 10-round Pipo-128, we use a path that fixes 105 key bits, that is, all of k 0 except 8 bits, and all of k 1 except 7 forward bits and 8 backward bits.


Anaïs Bertaud

Thierry Cens

Matthieu Rousset

Jean-Baptiste Thibaud

Claudine Ménard

Janique Guiramand

Michel Vignes

Michel Vivaudou

Pierre Charnet

Identification of signaling pathways of octopamine receptors in Apis mellifera and Varroa destructor

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Title: IDENTIFICATION OF SIGNALING PATHWAYS OF OCTOPAMINE RECEPTORS IN APIS MELLIFERA AND VARROA DESTRUCTOR

Anaïs Bertaud 1,2 , Thierry Cens 1 , Matthieu Rousset 1 , Jean-Baptiste Thibaud 1 , Claudine Ménard 1 , Janique Guiramand , although no precise characterization has been done yet. Amitraz, a synthetic OctoR agonist is used extensively in the hive worldwide to fight against the Varroa destructor, a parasite mite partly responsible for the increasing number of colonies collapse disorders recorded last years. The specificity of amitraz for the honeybee or varroa OctoR is however is not really known as well as the precise pharmacology and signaling profiles of the mite OctoRs.

We have cloned the 5 honeybee and 2 varroa OctoR and expressed them in oocytes to (1) analyze their pharmacological profile (octopamine, tyramine, dopamine and amitraz) and ( 2) identified the signaling pathway they activate.

Our data show that these OctoR can activate multiple G-protein dependent pathways (Gi/o, Gs, Gq) but can also activate directly (G-protein independent) a cation channel that is tentatively identified as TRPC in Xenopus oocyte. The presence of these different types of responses is dependent upon the type of receptors expressed and the agonist used. We now verify the existence of these OctoR-specific signaling pathways in bee neurons from the antennal lobes and mushroom bodies.

  1 , Michel Vignes 1 , Michel Vivaudou 2 & Pierre Charnet 1 1 Pharmacochemistry of synaptic transmission and neuroprotection group, IBMM, Montpellier, France 2 Channels group, Institut de Biologie Structurale, Grenoble, France Abstract: Octopamine receptors (OctoR) are G protein-coupled receptors specific to invertebrate, which are expressed in many neurons in Apis mellifera. They control or regulate neuromuscular transmission, learning, memory or responses to odorant by modulating responses of odorant receptors, interneurons or motoneurons. In honeybee, 5 types of OctoR have been identified, with functional homology to  or  adrenoreceptors, able to activate different intracellular signaling pathways (Gs, Gi/o, Gq)