Christina Boura
email: christina.boura@uvsq.fr

Nicolas David
email: nicolas.david@inria.fr

Patrick Derbez
email: patrick.derbez@irisa.fr

Gregor Leander
email: gregor.leander@rub.de

María Naya-Plasencia
email: maria.naya-plasencia@inria.fr

Differential Meet-In-The-Middle Cryptanalysis

Keywords: differential cryptanalysis, meet-in-the-middle cryptanalysis, SKINNY, AES

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

Introduction

Since the 1970's and the standarization of the DES block cipher hundreds of different symmetric primitives have been designed to address special needs and industrial requirements or to provide an answer to particular research problems. A fundamental procedure that permits to decide which among those primitives can be trusted and safely deployed is cryptanalysis. The first modern symmetric cryptanalysis techniques were developed in the late 1970's, 1980's and in the beginning of the 1990's. Among these first and most important attacks are, of course meet-in-the-middle [START_REF] Diffie | Special feature exhaustive cryptanalysis of the NBS Data Encryption Standard[END_REF], differential [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF] and linear cryptanalysis [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF],

©IACR 2023. This article is the final version submitted by the authors to the IACR and to Springer-Verlag on June 5, 2023. but also boomerang [START_REF] Wagner | The boomerang attack[END_REF] and rectangle attacks [START_REF] Biham | The rectangle attack -rectangling the Serpent[END_REF], impossible differential [START_REF] Knudsen | DEAL-a 128-bit block cipher[END_REF][START_REF] Biham | Miss in the middle attacks on IDEA and Khufu[END_REF], higher-order differential [START_REF] Knudsen | Truncated and higher order differentials[END_REF] or differential-linear attacks [START_REF] Langford | Differential-linear cryptanalysis[END_REF]. More attacks appeared in succession to new designs, as for example the square attack [START_REF] Daemen | The block cipher Square[END_REF], particularly well-adapted to AES-like constructions or the subspace invariant attacks [START_REF] Leander | A cryptanalysis of PRINTcipher: The invariant subspace attack[END_REF] that worked well against some particular lightweight ciphers. In parallel, some techniques, as the division property [START_REF] Todo | Structural evaluation by generalized integral property[END_REF], permitted to define a new algorithmic framework to generalize older attacks. As the field is well advanced, nowadays, it is more and more rare to come up with entirely new cryptanalysis techniques, while improvements of the known ones are more common.

Among the existing cryptanalysis techniques, differential attacks [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF] are among the oldest and the best studied cryptanalysis methods. Their idea is to exploit an input difference that propagates through the cipher to an output difference with a high probability. Through the years, these attacks have been refined and many improvements to different parts of the attack procedure have been introduced: the use of structures to build up the plaintext or ciphertext pairs [START_REF] Biham | Differential cryptanalysis of the full 16-round DES[END_REF], the use of truncated differentials [START_REF] Knudsen | Truncated and higher order differentials[END_REF], conditional differentials [START_REF] Knellwolf | Conditional differential cryptanalysis of NLFSR-based cryptosystems[END_REF], the technique of probabilistic neutral bits [START_REF] Choudhuri | Differential cryptanalysis of Salsa and ChaCha -An evaluation with a hybrid model[END_REF] or refinements in the key recovery process, to mention only a few. A first research question in link with our work is the following: Question 1. Do there exist alternative methods for doing the key recovery step of a differential attack more efficiently?

Another popular -and actually even older -technique that has been useful in many cryptanalysis applications, and the subject of a large number of improvements and further studies is meet-in-the-middle (MITM) cryptanalysis [START_REF] Diffie | Special feature exhaustive cryptanalysis of the NBS Data Encryption Standard[END_REF]. The idea of basic MITM attacks is to split the cipher into two parts, where each part can be computed with partial knowledge of the key. An attacker can then validate partial key guesses by checking for a match in the middle. Again, many extensions and refinements of the basic attack exist today: the technique of partial matching, where only a part of the middle state is known, guessing some bits of the internal state [START_REF] Dunkelman | Improved meet-in-the-middle attacks on reduced-round DES[END_REF], the all-subkeys approach [START_REF] Isobe | All subkeys recovery attack on block ciphers: Extending meet-in-the-middle approach[END_REF], the splice-and-cut technique [START_REF] Aoki | Preimage attacks on one-block MD4, 63-step MD5 and more[END_REF][START_REF] Aoki | Meet-in-the-middle preimage attacks against reduced SHA-0 and SHA-1[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] and the sieve-in-the-middle (SITM) approach [START_REF] Canteaut | Sieve-in-the-middle: Improved MITM attacks[END_REF] that permits to extend the length of a MITM attack by searching for a match through an extra S-box layer in the middle. Finally, the method of bicliques is a cryptanalysis technique [START_REF] Bogdanov | Biclique cryptanalysis of the full AES[END_REF] that aims at extending MITM attacks by some rounds. A second research problem of interest to us and that motivated our initial work is: Question 2. Can we find a new way to extend a MITM attack to more rounds?

In this paper we provide a positive answer to both questions simultaneously by proposing a new cryptanalysis technique that we call the differential meetin-the-middle attack. The idea of this new technique is to use a differential to cover several middle rounds of the cipher while running a meet-in-the-middle attack on its external rounds. In a nutshell, this combination has many potential advantages. In particular, with our new technique, a middle part of the cipher is covered by a differential and thus we have to apply MITM techniques on much less rounds than with all previous MITM-type attacks. Note that Demirci-Selçuk MITM attacks [START_REF] Demirci | A meet-in-the-middle attack on 8-round AES[END_REF] applied with the differential enumeration technique [START_REF] Dunkelman | Improved single-key attacks on 8-round AES-192 and AES-256[END_REF] also combine to some extent truncated differentials and the MITM approach, but in this case the guess is done in parallel on the inner part (with a truncation-based distinguisher) and the external part, trying to match some particular properties of the differential set. Interestingly, our new method can also be interpreted as a differential attack where the key recovery step is done in a different way. Indeed, starting from a given plaintext-ciphertext pair, we guess in parallel the input keys that allow us to compute a matching plaintext ensuring the given input difference of the differential, and the output keys that allow us to compute the ciphertext that ensures the output difference of the differential, and compute the associated plaintext for all these ciphertexts by making calls to the oracle. Next, we try to match the list of plaintexts computed with the guesses of the input key bits and the list of plaintexts computed with the list of output keys by finding a collision. We repeat this for enough plaintexts so that we can expect one of them to satisfy the differential. All collisions found will imply a potential candidate for the associated guess of keys. The matching can usually be done efficiently with list merging algorithms like the ones in [START_REF] Naya-Plasencia | How to improve rebound attacks[END_REF].

In order to demonstrate the efficiency of our new cryptanalysis technique, we provide two applications. First, we apply the attack in the single-key setting to the block cipher SKINNY and we show how to break 25 out of the 56 rounds of SKINNY-128-384, the 128-bit block variant employing a 384-bit key. Our attack improves by two the number of rounds of the previous best attack against this variant in the single-key model. A summary of the best attacks against SKINNY-128-384 is given in Table 1. 5 Then, we provide an application to AES-256 by breaking 12 rounds of the cipher in the related-key model. Our attack uses only 2 related keys, whereas the best previous attacks with this number of related keys could reach at most 10 rounds. A summary of the best attacks against AES-256 is given in Table 2.

The rest of the paper is organized as follows. Section 2 describes the general framework of our new cryptanalysis technique, compares it to both differential and MITM attacks and provides several improvements. Our attacks against SKINNY-128-384 are described in Section 3 and our application on AES-256 is given in Section 4. Finally, several open problems are discussed in Section 5.

The new attack: Differential MITM

We propose in this work a new cryptanalysis technique against symmetric primitives. This new attack aims at combining meet-in-the-middle (MITM) attacks together with differential cryptanalysis, and we will call this new technique differential MITM. The original motivation of our work was to investigate whether there exists a method for reaching more rounds than the sieve-in-the-middle attack [START_REF] Canteaut | Sieve-in-the-middle: Improved MITM attacks[END_REF][START_REF] Canteaut | Sieve-in-the-middle: Improved MITM attacks (full version)[END_REF], an extension of classical MITM attacks. However, our technique can also be interpreted as a new key-recovery method to apply in differential cryptanalysis, that can be sometimes combined with MITM improvements for reaching more rounds. We will present in this section a high-level description of the new technique. More precisely, we will provide a general framework that describes how to mount a differential MITM attack in a generic and simple way, and we will show how to combine this generic method with two techniques: the parallel treatment of data partitions in order to add one round mostly for free (idea that inherits from MITM attacks, like bicliques, and that cannot be applied to classical differential attacks), as well as a technique to reduce the data complexity.

General framework

Consider a n-bit cipher E decomposed into three sub-ciphers:

E out • E m • E in , as
depicted in Figure 1. Let the number of rounds of E in , E m and E out be r in , r m and r out respectively. Finally, let ∆ x be the input difference to the middle part E m , ∆ y the output difference of E m and suppose that the differential ∆ x → ∆ y , covering the r m middle rounds, has probability 2 -p . We start our analysis with a first randomly chosen plaintext P and its associated ciphertext C, and we aim at generating a second plaintext-ciphertext pair ( P , C) such that together they satisfy the differential on the middle rounds. Our new idea is to generate ( P , C) with a meet-in-the-middle approach. For this, candidate plaintexts P are computed from both the plaintext P and the difference ∆ x for each possible value of the associated key k in , while candidate ciphertexts C are computed from C and ∆ y for each possible value of the involved key, k out . The match is then performed on the relation E( P ) = C (or P = E -1 ( C)). Note that the roles of the upper and lower part can be interchanged without loss of generality in order to optimize the data and memory complexity, if we consider that the access to both the encryption and the decryption oracles is granted.

Upper part. Given P , the aim is to guess the minimal amount of key information, that we will denote by k in , such that we can compute the associated P that ensures E in (P ) ⊕ E in ( P ) = ∆ x if the guess of k in corresponds to the secret key. For each guess i for k in , we obtain a different candidate for P , that we denote by P i , leading to a total of 2 |kin| such values. From them, we can compute the 2 |kin| associated ciphertexts C i = E( P i ) with calls to the encryption oracle and store them in a hash table H Number of pairs and match. For the correct key guess, the transition ∆ x → ∆ y will happen with a probability 2 -p . Therefore, we will repeat the upper and lower procedures 2 p times with 2 p different messages P ℓ so that we can expect one pair (P ℓ , P i ℓ ) to satisfy the differential together with the associated pair (C ℓ , C j ℓ ). When this is the case, we will find a collision for a certain ℓ between a C i ℓ computed in the upper part and stored in H and a C j ℓ computed from the lower part. Each collision (i, j) has an associated key guess k in = i, k out = j, that we will consider as a potential candidate. The number of expected collisions for each fixed P ℓ is 2 Complexity. The time complexity of this attack can be estimated as

T = 2 p × (2 |kin| + 2 |kout| ) + 2 |kin|+|kout|-|kin∩kout|-n+p ,
where the first term corresponds to the computations done in E in and E out , and the last one to the number of expected key candidates. With this, we recover k in ∪ k out , so if we expect fewer key candidates than the whole set

k in ∪ k out , (i.e |k in | + |k out | -|k in ∩ k out | -n + p < |k in ∪ k out |,
which holds as long as p < n), we can guess the remaining bits of the master key and test the guess with additional pairs. Thus we recover the whole key with a complexity smaller than the cost of an exhaustive key search, and an additional cost of

2 k-(|kin∪kout|) × max{1, 2 |kin|+|kout|-|kin∩kout|-n+p }
to be added to the time complexity T . In the expected case where

|k in | + |k out | - |k in ∩ k out | -n + p ≥ 0, the total time complexity is thus T = 2 p × (2 |kin| + 2 |kout| ) + 2 |kin∪kout|-n+p + 2 k-n+p .
The (naive) data complexity of this first version of the attack can be estimated as

D = min(2 n , 2 p+min(|kin|,|kout|) ).
Finally, the naive memory complexity is given by M = 2 min(|kin|,|kout|) , though it can be improved to 2 min(|kin|-|kin∩kout|,kout-|kin∩kout|) by first guessing the common key material before running the attack.

Improvement: Parallel partitions for layers with partial subkeys

We will show now that in the case where the round key addition does not affect the whole state but only a part of it (as is for instance the case in Feistel constructions [START_REF] Feistel | Cryptography and computer privacy[END_REF], or in the SKINNY [START_REF] Beierle | The SKINNY family of block ciphers and its low-latency variant MANTIS[END_REF] and GIFT [3] ciphers), we can extend the attack by one round. As we will show, if the m bits of the state affected by the key addition are such that m < p (where p is the -log 2 of the probability of the differential distinguisher), the time complexity of adding this round will not be affected. However, the exact data complexity of the attack has to be checked case-by-case, as it might depend on the configuration of the differences in the external states. A technique on how to reduce the data complexity will be further discussed in Section 2.3. The memory complexity might be a priori increased.

The main idea here is to consider, in addition to guessing in parallel the key bits intervening in the lower and upper parts, a partial parallel guess of the final states. More precisely, 2 m penultimate and final states (or the initial state, without loss of generality) will be guessed in parallel, without needing to guess the key that allows the transition from the penultimate one to the final. When performing the final match, we will take into account this key transition. Actually, it can be seen as considering 2 m plaintexts P i and ciphertexts C j in parallel, without knowing which ones would match together, as this transition is determined by the last round-key.

Since we expect to try on average 2 p plaintexts in order to find one that will satisfy the differential of probability 2 -p , we can divide the final state of size 2 n into two parts. The part without the key addition will take 2 p-m different values, and the attack will be repeated for each one of those.

On the other hand, the part affected by the key addition will take 2 m possible values for X, the state before the key addition, and for each we can compute the state S r-1 in Figure 2 from the output of the differential MITM attack. From this state, we will guess the k out bits, in order to compute the associated state potentially generating the output difference of the middle differential, obtaining 2 |kout|+m candidates to match. In parallel, the state Y after the key addition will also take all the 2 m possibilities, and with them we decrypt in order to obtain the plaintext, and do the upper key guessing procedure to deduce the good pairs, obtaining 2 |kin|+m candidates. The number of possible solutions might seem higher by a factor of 2 2m , but note that we have to match X and Y , as well as their associated pairs X ′ and Y ′ , and they must satisfy

X ⊕ X ′ = Y ⊕ Y ′ .
This adds m bit-conditions, or more if this final subkey was already determined by k in and k out , which is usually the case. This implies m additional conditions, and 2 2m 2 -m 2 -m = 1, so the cost, given by the number of solutions, stays exactly the same as the attack with one round less. We will see how this technique can be applied in practice in Section 3.

Improvement: Reducing data with imposed conditions

We explain here a way to obtain time-data-memory trade-offs for the original attack. If when choosing the plaintext P , we force x of its bits, that might have been active otherwise, to a certain value, and if we expect the same from the associated plaintext P , the overall probability of the attack will decrease to 2 -p-x , as we will have to repeat the procedure until a P that satisfies this constraint is found. More precisely, if P does not fit this condition, the corresponding tuple will not be stored in the hash table since we do not have access to its ciphertext. However by doing so, the data complexity will be reduced by a factor of 2 x as well as the memory complexity. When combining this technique with the previous one, we can derive the following two inequalities for x:

p + x ≤ n -x and 2 p+x (2 |kin| + 2 |kout| ) < 2 k .
This type of trade-off applies in particular when all the code book of size 2 n is needed before fixing the x bits, and the data complexity becomes 2 n-x .

Data reduction without time increase. As the total number of candidates for the key of the input part (respectively output) will be 2 |kin|-x (respectively 2 |kout|-x ), if we are able to find these candidates with their associated P (respectively C) in a complexity given by the number of solutions, the time complexity would become:

2 p+x (2 |kin|-x + 2 |kout|-x ) = 2 p (2 |kin| + 2 |kout| ),
which allows us to reduce the data complexity to 2 n-x while not increasing the time complexity. The optimal data complexity in this case will be 2 n+p 2 , obtained with x equal to n-p 2 . This can actually be done in many cases using rebound-like techniques [START_REF] Mendel | The rebound attack: Cryptanalysis of reduced Whirlpool and Grøstl[END_REF]. This is the case for all our attacks summarized in Table 1. An example can be seen in Section 3.

Discussion and Comparison

As argued before, our new cryptanalysis technique is closely related to two families of techniques: MITM attacks and differential attacks. In this section we will discuss similarities and differences between these families and will try to identify cases where our new technique might be efficient or cases where it permits to reach better results compared to the best known attacks.

Relation to MITM attacks

In relation to MITM attacks and its variants, like the sieve-in-the-middle technique, our attack, already if using a differential with probability one, could have, a priori, the potential of reaching more rounds. The starting point of our research was whether it was possible to add even more rounds in the middle of a MITM-like attack and this is how we came up with the new attack. The data complexity of the new attack could be higher than a classical MITM one as now we compute a new P from each guess of the key, and this plaintext can take many different values, besides the 2 p different plaintexts P ℓ taken as starting points in order to find one that satisfies the differential. On the other hand, despite the fact that the sets of bits k in or k out involved in the parallel computations of the differential MITM attack are not determined in the same way as the key bits involved in MITM attacks, we expect those quantities to be relatively close under similar settings, as this principally depends on the propagation properties of the round function. More precisely, it seems that more aligned [START_REF] Bordes | Thinking outside the superbox[END_REF] the round function is, closer the sets will be.

Therefore, we expect that ciphers where classical MITM attacks work well, can also be interesting targets for differential MITM attacks. This is actually how we found the application shown in Section 3 on SKINNY. Indeed, the best known attack against SKINNY-384-128 previous to ours was a MITM one [START_REF] Dong | Meet-in-the-middle attacks revisited: Key-recovery, collision, and preimage attacks[END_REF].

Relation to differential attacks Curiously enough, our new attack can also be seen as a new way of performing the key-recovery part associated to a differential distinguisher.

Classical differential attacks.

A differential attack starts with a differential distinguisher on r m rounds of relatively high probability 2 -p . One then typically extends the distinguisher by r in rounds to reach the plaintext state and by r out rounds to reach the ciphertext state, with probability 1 as depicted in Figure 3. Structures are then used to build plaintext (or ciphertext) pairs. A structure of size 2 s allows to build 2 2s-1 pairs (though building all these pairs is rarely needed), but for each structure we need to consider typically an additional probability so that the pairs from the structure satisfy the input difference of the distinguisher. If we are not considering truncated but fixed differentials, as it will be our case, the probability of reaching a fixed difference ∆ x is approximately 2 -s . In order to expect that at least one pair will satisfy the distinguisher, we will need to consider 2 p-s+1 structures, each of size 2 s , and for each structure, 2 s-1 pairs will reach the input difference ∆ x , leading to a total of 2 p-s+1+s-1 = 2 p pairs reaching ∆ x . Typically, for determining a priori potential good pairs, one performs some sieving that will allow not to try all the pairs from all the structures. This sieving is done by looking at the activity pattern of the ciphertexts and can be estimated as 2 -c = 2 -n+a , where a is the bit-size of the active part in the ciphertext. The key recovery part depends on the particular properties of the round function. Its complexity can be often accurately lower bounded by the number of the partial key candidates in the key-recovery rounds, thanks to early abort and divide-and-conquer techniques. The data complexity of such an attack is 2 p+1 and the time complexity can be estimated as

2 p+1 + 2 p-s+1 2 2s-1 2 -c C k ≈ 2 p+s-n+a , (1)
where C k is the average cost of determining the key bits for each candidate pair. This quantity can be lower bounded by the number of partial key candidates in the key-recovery rounds and this number can be much greater than 1 if the key is bigger than the state. We can see that if s and a are big enough, i.e. a + s ≫ n, which can happen when several rounds are appended, the complexity of a differential MITM attack for an equivalent number of rounds might be more interesting. Indeed, the influence of the input and output extensions to the complexity are added and not multiplied. In particular, our attack can become much more efficient when the key size of the cipher is bigger than the state size, otherwise 2 p might already be close to the limit.

Differential Meet-the-Middle attacks against SKINNY-128-384

We provide in this section our applications to SKINNY-128-384. We start by recalling the specifications of the SKINNY family of ciphers.

Specifications of SKINNY

The SKINNY family of tweakable block ciphers was designed by Beierle et al. [START_REF] Beierle | The SKINNY family of block ciphers and its low-latency variant MANTIS[END_REF].

It is a family of lightweight ciphers following a classical SPN structure but implementing a very compact S-box, a linear layer based on a sparse non-MDS binary matrix and a lightweight key schedule. The block size n can be 64 or 128 bits and for both versions the state is seen as a 4 × 4 matrix of 4-bit or 8-bit cells. Row 0 is considered the uppermost one and column 0 is taken to be the leftmost one. The numbering of the words inside the state matrix is as follows.

SKINNY follows the tweakey framework [START_REF] Jean | Tweaks and keys for block ciphers: The TWEAKEY framework[END_REF] and XORs a tweakey to the two upmost rows of the state. There exist three main variants for the tweakey size: t = n, t = 2n and t = 3n and the corresponding variant is denoted by SKINNY-n-t. Furthermore, the tweakey to block size ratio is denoted by z = t/n. The tweakey state is viewed also as a set of z 4 × 4 arrays of cells. For z = 3, which is the variant of interest to us, the three tweakey arrays are denoted by TK1, TK2 and TK3.

The round function of SKINNY is depicted on Figure 4, and the number of times this function is iterated depends on both n and t, as shown in Table 3.

One round of SKINNY is composed of five operations applied in the following order: SubCells (SC), AddConstants (AC), AddRoundTweakey (ART), ShiftRows (SR) and MixColumns (MC). We now briefly describe the operations that are of interest to us. .

AddRoundTweakey (ART)

We describe this step only for the variants with z = 3.

Here, the first and second rows of the 3 tweakey arrays TK1, TK2 and TK3 are extracted and XORed to the internal state, respecting the bit positions inside the arrays. More formally, if IS i,j is the cell at the intersection of row i and j of the state, we have that for (i, j) ∈ {0, 1} × {0, 1, 2, 3}:

IS i,j = TK1 i,j ⊕ TK2 i,j ⊕ TK3 i,j .

ShiftRows (SR)

This operation rotates the cells inside a row to the right by a certain offset that depends on the row. More precisely, cells in row i, where 0 ≤ i < 4, are rotated by i positions to the right.

MixColumns (MC)

This operation updates the state by multiplying each column by a binary matrix M. This matrix, as well as its inverse are as follows.

M =     1 0 1 1 1 0 0 0 0 1 1 0 1 0 1 0     , M -1 =     0 1 0 0 0 1 1 1 0 1 0 1 1 0 0 1     .
Next we describe the tweakey schedule of SKINNY-128-384, the variant we analyse in this work. Tweakey schedule of SKINNY-128-384 At each round, all tweakey arrays are updated as follows (see also Figure 5). First, the same permutation P T is applied on the cell positions of the 3 tweakey arrays: for all 0 ≤ i ≤ 15, we have that TK1 i ← TK1 P T [i] with P T = [9, 15, 8, 13, 10, 14, 12, 11, 0, 1, 2, 3, 4, 5, 6, 7],

and the same exact permutation is applied to the cells of TK2 and TK3. Finally, the cells of the first two rows of TK2 and TK3 are individually updated by the LFSR :

(x 7 ||x 6 ||x 5 ||x 4 ||x 3 ||x 2 ||x 1 ||x 0 ) → (x 0 ⊕ x 6 ||x 7 ||x 6 ||x 5 ||x 4 ||x 3 ||x 2 ||x 1 ),
where x 0 is the LSB in a byte. Property. In most attacks, including ours, it is more efficient to guess roundkey bits than key bits. Since the key-schedule of SKINNY is fully linear, guessing enough (e.g. 384 in the TK3 model) independent round-key bits allows to uniquely determine the master key and thus all remaining round-key bits. SKINNY has a unique property that makes the evaluation of the dimension of any set of round-key bytes easy: in the TKx model, a round-key byte K r [i] always depends on exactly x master key bytes, one from each TK key and they all have the same index. Furthermore, given x round-key bytes from the 30 first rounds and depending on the same x master key bytes, they are always independent and allow to uniquely determine their x corresponding master key bytes.

We present now 3 attacks against round-reduced variants of SKINNY-128-384 by using our new differential meet-in-the-middle technique. We first describe a simple attack against 23 rounds as well as several improvements and trade-offs. We then explain how this attack can be extended to an attack on 24 rounds without increasing the attack's overall complexity. Finally, we describe a new attack against 25 rounds.

An attack against 23-round SKINNY-128-384

As explained in Section 2, differential meet-in-the-middle attacks rely on two classical cryptanalysis techniques: differential attacks and meet-in-the-middle attacks. The main idea is to use a meet-in-the-middle attack to generate a pair following a given differential in the middle rounds. Thanks to this procedure, we are able to extend a differential distinguisher by more rounds than with a classical early-abort procedure, as discussed in Section 2.4. Differential. The truncated differential used in our attack against 23 rounds of SKINNY-128-384 is depicted in Figure 6. It has 56 active S-boxes, without counting those of the first and the last round. We verified that this truncated differential can be successfully instantiated by using the constrained programming Choco-solver [START_REF] Prud'homme | Choco Solver Documentation[END_REF], and more precisely the model developed by Delaune et al. to search for the best differential characteristics for the SKINNY family of block ciphers [START_REF] Delaune | Efficient methods to search for best differential characteristics on SKINNY[END_REF]. The best instantiation of this truncated differential has a probability of 2 -119 and there are in total 2048 instantiations with this same probability. These instantiations can be divided into four groups (∆

(i) x , ∆ (i)
y ), for i = 1, 2, 3, 4, each one having 512 trails inside, starting with the same difference ∆ (i)

x and terminating after 13 rounds with the same difference ∆ (i) y . We found as well many more differential trails with the same input/output differences but smaller probabilities: 2560 with probability 2 -120 , 7168 with probability 2 -121 , 18432 with probability 2 -122 and 44800 with probability 2 -123 . Thus the probability of the differential depicted on Figure 6 is higher than 2 -105.9 . The attack. We describe now our core attack against 23-round SKINNY-128-384.

1. Ask for the encryption of the whole codebook. 2. Randomly pick one plaintext/ciphertext pair (P, C). 3. For each possible value i of k in compute the tuple (P, P , i) so that the difference on the state after the 6th S-box layer is [0 0 0 2 0 0 0 0 0 0 0 0 2 0 0 0] (see Figure 6). Doing so requires to know the values of all the active S-boxes involved in the probability 1 transition ∆ x → ∆ P , where ∆ P is the plaintext difference, and k in is the set of subkey bytes needed to compute them from the plaintext. 4. Store all these tuples in a hash table. This step requires to guess 31 subkey bytes as depicted in Figure 7. 5. Similarly, for each possible value j of k out compute the tuple (C, C, j) so that the difference on the state before the 19th S-box layer is 0x64 on all active bytes. The set k out involves 32 bytes and thus there are 2 256 such tuples. 6. For each of them check for possible matches on the hash table. The match is performed on both the new ciphertext (i.e. ( P , C) must be a valid plaintext/ciphertext pair) as well as on the linear relations between the subkey bytes of the upper and lower guess. 7. Each match leads to a (full) key candidate that can be tried against very few additional plaintexts (3 in our case). 8. Repeat from Step 2 until the right key is retrieved.

K0[0], K2[2] K18[2], K20[4], K22[6] 2 1 K0[1], K2[0] K20[2], K22[4] 1 2 K0[2], K2[4] K20[6], K22[5] 1 3 K0[3], K2[7] K20[1], K22[0] 1 4 K0[4], K2[6] K20[5], K22[3] 1 5 K0[5], K2[3] K20[7], K22[1] 1 6 K0[6], K2[5], K4[3] K20[3], K22[7] 2 7 K0[7], K2[1], K4[0] K20[0], K22[2] 2 8 K1[2], K3[4] K19[4], K21[6] 1 9 K1[0] K19[2], K21[4] 0 10 K1[4] K19[6], K21[5] 0 11 K1[7], K3[1] K19[1], K21[0] 1 12 K1[6], K3[5] K21[3] 0 13 K1[3] K19[7], K21[1] 0 14 K1[5], K3[3] K19[3], K21[7] 1 15 K1[1], K3[0] K19[0], K21[2] 1
The data complexity of this attack is 2 128 since in Step 1 we ask for the encryption of the full codebook. The memory complexity is determined by Step 3 in which 2 248 words of 128 + 248 = 376 bits each are stored. Note that we do not need to store C 1 since it is common to all tuples. Thus the memory complexity is 2 249.5 128-bit words. The time complexity is 2 248 for computing the hash table, 2 256 for performing Step 4, and, as shown in Table 4, k in ∪ k out is the full key so that the complexity of Step 6 is 2 384-128 = 2 256 . Finally, the attack has to be repeated 2 105.9 times (the probability of the distinguisher) in order to construct one right differential pair. Hence, the overall complexity of our attack is 2 105.9 × 2 256 = 2 361.9 .

Decreasing memory complexity. It is possible to decrease the memory complexity of the attack by avoiding the match on the linear relations between both k in and k out . Indeed, since the key-schedule of SKINNY is fully linear, we can first guess the intersection of k in and k out , and only then run the attack. The dimension of the intersection is 248 + 256 -384 = 120 and thus the memory complexity can be decreased to 2 249.5-120 = 2 129.5 .

Data-time-memory trade-off. To decrease the data complexity of our attack, as described in Section 2.3, it is possible to only ask for the encryption of a portion of the whole codebook, let say 2 128-x plaintext/ciphertext pairs. In this case, the probability that we have access to the corresponding ciphertext of P is 2 -x and the attack has to be ran 2 x times to compensate. Overall, the complexity of our 23-round attack is then D = 2 128-x plaintext/ciphertext pairs, M = 2 129.5-x 128-bit words and T = 2 361.9+x encryptions. To expect at least one pair following the differential under the extra constraint on the plaintexts, x cannot be higher than (128 -105.9)/2 = 11.05.

As explained in Section 2.3, in practice, given any pair of ciphertexts, we can enumerate the possible values for both k in and k out with a complexity roughly equivalent to the number of solutions. Such a procedure is described in Section 3.3. Thus, the trade-off does not increase the time complexity and the overall complexity of our attack is D = 2 117 , T = 2 361.9 and M = 2 118.5 .

Enumeration Procedure of k out for the 23-round Attack

In this section we describe a procedure to retrieve the possible values of k out in the case where the pair of ciphertexts is given. Its complexity is 2 128 simple operations, showing that the data/time/memory trade-off described in Section 2.3 can be applied without increasing the time complexity. Since the key is not applied on the full state, the procedure is more complex than a classical rebound but still relies on the fact that, on average, knowing the differences at both the input and output of an Sbox leads to one pair of actual values.

The steps of our enumeration procedure are depicted on Figure 3.3. The main idea is to propagate differences from the ciphertexts to Round 18, get the actual values since differences in this internal state are fully known, and propagate them back to the ciphertexts to obtain the key material we want. Except from

Step 1 in which we guess 8 values, all following steps perform one guess each.

Steps 7 and 8 have both a probability of success of 2 -8 and thus we expect only 2 13×8 = 2 104 partial solutions at the end of Step 8.

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 SR 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 MC Round 22 1 1 1 1 1 1 1 1 SC 1 1 1 1 1 1 1 1 K 22 SR 21

Extension to 24 rounds

Our differential meet-in-the-middle attack against 23-round SKINNY can be extended to an attack against 24 rounds without increasing its overall complexity by using the generic improvement presented in Section 2.2. This can be achieved since on one hand the key-schedule is linear (and enough subkey bytes are involved in our attack so that the master key is fully retrieved) and on the other hand the subkey is only applied on half of the state in each round. The scenario of this new attack is quite similar to the original one:

1. Ask for the encryption of the whole codebook. 2. Pick 2 64 plaintext/ciphertext pairs (P ℓ , C ℓ ) such that MC -1 (C ℓ ) is constant on the last two rows as depicted in Figure 9. Here we exploit the fact that the round key is only applied on the first two rows of the internal state.

3. As for this original attack, compute all possible tuples (P ℓ , P i ℓ , i) for each value i of k in and each P ℓ from the structure defined at the previous step such that the state difference after the 6th S-box layer is 0x02 on both active bytes. 4. Store them in a hash table. Note that the tuples are computed for all the 2 64 plaintexts selected at Step 2 so the memory complexity is 2 248+64 = 2 312 504-bit words. 5. For each value j of k out and each state S 23,ℓ coherent with Step 2 (i.e. 2 64 states, one for each possible value of the subkey K 23 ), compute all possible tuples (S 23,ℓ , S j 23,ℓ , j) so that the difference on the state before the 19th S-box layer is 0x64 on the four active bytes. [START_REF] Biham | The rectangle attack -rectangling the Serpent[END_REF]. Check for possible matches on the hash table. The match is now performed on three quantities:

the difference between the last states:

C ⊕ C = MC•SR(SC(S 23 )⊕SC( S 23 )).
This is a 64-bit filter because the difference is zero on the two last rows since MC -1 (C) is constant on these rows. the filter on the keys (from key schedule equations): a 120-bit filter as for the original attack against 23 rounds (15 equations on 8 bits each, see Table 4). the filter on the keys (from equations describing the last round). Indeed, since k in ∪k out generates the master key, K 23 can be rewritten as The attack has to be repeated enough times so that the structure contains at least one pair following the differential. Since during Step 2 we generate 2 64 pairs and since the probability of the differential is 2 -105.9 , the procedure has to be repeated 2 41.9 times. Thus the data complexity is 2 128 (i.e. the whole codebook is needed), the memory complexity is around 2 314 128-bit words and the time complexity 2 256+64+41.9 = 2 361.9 encryptions.

f (k in )⊕ g(k out )
Note that previous improvements regarding both the memory and data complexities still apply and thus our attack has complexity: D = 2 128-11 = 2 117 plaintext/ciphertext pairs, M = 2 194-11 = 2 183 128-bit words and T = 2 361.9 encryptions.

An attack against 25 rounds of SKINNY-128-384

To mount a differential meet-in-the-middle attack against 25 rounds of SKINNY, we used the differential depicted in Figure 10. The best instantiation of this truncated differential has a probability of 2 -131 . By fixing the difference of the active bytes to 0x32 at the input and to 0x64 at the output, we found several instantiations with a high enough probability: 2048 with probability 2 -131 , 10240 with 2 -132 , 28672 with 2 -133 and finally 73728 trails with probability 2 -134 . Thus, the probability of the depicted differential is higher than 2 -116. 5 . This differential is then extended by 4 rounds to the plaintext and 5 rounds to the ciphertext to reach 24 rounds as depicted in Figure 11. The key bytes involved in the attack are given in Table 5, leading to a complexity of D = 2 128 data, T = 2 256 × 2 116.5 = 2 372.5 encryptions and M = 2 249.5 128-bit words. Furthermore, the dimension of the intersection between both k in and k out is once again 248 + 256 -384 = 120, which allows to reduce the memory complexity to 2 129.5 128-bit words.

As for the 23-round attack described above, this attack can be extended by one round without increasing its overall complexity. As a consequence, and after applying the data/time/memory trade-off presented in Section 2.3, the complexity of our attack against 25 rounds is D = 2 128-x plaintext/ciphertext pairs, M = 2 194-x 128-bit words and T = 2 372.5+x encryptions. In this case, x cannot be higher than (128 -116.5)/2 = 5.75. Furthermore, we can again apply this trade-off without increasing the time complexity and thus the final complexity is D = 2 122.3 , T = 2 372.5 and M = 2 188.3 .

Comparison of the attacks on SKINNY-128-384 with differential attacks

One may wonder whether the improved attacks on SKINNY-128-384 and in particular the one reaching 25 rounds, are exclusively due to the quality and the Table 5. Subkey bytes involved in the 24-round core attack.

Byte kin kout # equations 0 K0[0], K2[2] K20[4], K22[6] 1 1 K0[1], K2[0] K20[2], K22[4] 1 2 K0[2], K2[4] K20[6], K22[5] 1 3 K0[3], K2[7] K20[1], K22[0] 1 4 K0[4], K2[6] K20[5], K22[3] 1 5 K0[5], K2[3] K22[1], K24[0] 1 6 K0[6], K2[5] K20[3], K22[7] 1 7 K0[7], K2[1] K20[0], K22[2] 1 8 K1[2], K3[4] K21[6], K23[5] 1 9 K1[0], K3[2] K21[4], K23[6] 1 10 K1[4], K3[6] K21[5], K23[3] 1 11 K1[7], K3[1] K21[0], K23[2] 1 12 K1[6] K21[3], K23[7] 0 13 K1[3], K3[7] K21[1], K23[0] 1 14 K1[5], K3[3] K21[7], K23[1] 1 15 K1[1], K3[0] K19[0], K21[2], K23[4] 2
length of the differential distinguisher used. In this section we show that this is not the case, and that the best classical differential attacks that we could build using the same differential reached strictly less rounds than our attack. We show that even when considering optimal lower bounds for the complexities of classical differential attacks, it is not possible to reach more than 24 rounds for SKINNY-128-384 this way. This shows that differential MITM attacks can reach more rounds than differential ones in certain scenarios.

A lower bound on the complexity of differential attacks can be determined in part by the number of partial key candidates. When the key schedule is linear, as in SKINNY, the partial candidates for the key can be obtained optimally and in parallel for the input and the output, and can then be merged with respect to the common information between both partial keys, given by the key schedule.

In particular, for 24 rounds of SKINNY-128-384 starting from the differential of Figure 10, and considering all the possible combinations for the number of input, r in , and output, r out rounds, the complexity, given by Eq.(1), cannot be smaller than:

2 116+128 (2 120 + 2 128 + 2 120+128-120 ) = 2 373 ,
where the parameters (with respect to Eq.( 1)) are p = 116, s = 128, c = 0, and

C k = (2 120 + 2 128 + 2 120+128-120 ).
As the number of pairs needed to find one pair that verifies the input difference and also the differential path is 2 116+128 , we need a structure of size 2 122 . If we solve both parts sequentially, the complexity will exceed exhaustive search, as the most of the external keys are independent of those in the other part. Instead, considering both parts in parallel, we have 64 + 64 + 64 + 56 keybits involved in the input for a condition on 128 bits of recovering the input difference (so 2 120 key candidates), and 64 + 64 + 64 + 56 + 8 keybits involved in the output part, with 128-bit conditions (so 2 128 key candidates). The memory need is 2 128 for the parallel computation. The linear relations between both partial keys are 64 + 56, given by the even and odd subkeys respectively. So the previous result provides a lower bound on the complexity that such an attack would obtain. If we try to add one extra round and attack 25 rounds, a minimal additional factor of 2 64 has to be added to one of the parallel computations, as the number of partial solutions will increase by this amount. This would be too expensive and we can therefore conclude that we cannot build classical differential attacks on 25 rounds of SKINNY-128-384 based on this distinguisher. This extra round can be added in our case due to the different nature of the attack, and its relation to MITM cryptanalysis. Therefore, it is fair to conclude that in this case, differential meet-in-the-middle attacks are more powerful than classical differential attacks, reaching one extra round while having a similar complexity.

4 New attack against 12-round AES-256 in the related-key setting

To show how powerful our new cryptanalysis technique is, we propose an application against AES-256 in the related-key model. It is well known that this version of AES was fully broken by Biryukov and Khovratovich in [START_REF] Biryukov | Related-key cryptanalysis of the full AES-192 and AES-256[END_REF]. However, this attack is a boomerang one and thus requires 4 related keys as well as both encryption and decryption oracles. In our case, we propose an attack in the chosen plaintext setting and requiring only 2 related keys. It is depicted in Figure 14 and uses a differential characteristic similar to the one from [START_REF] Biryukov | Key recovery attacks of practical complexity on AES-256 variants with up to 10 rounds[END_REF].

In this section we first give a short description of AES-256, then we explain the key generation process that has to be performed by the adversary and finally we explain the whole attack.

Description of AES-256

The Advanced Encryption Standard [26] is a Substitution-Permutation Network (SPN) that can be instantiated using three different key sizes: 128, 192, and 256 bits. The 128-bit plaintext initializes the internal state viewed as a 4 × 4 matrix of bytes, i.e. values in the finite field F 256 , which is defined using the irreducible polynomial x 8 + x 4 + x 3 + x + 1 over F 2 . Depending on the version of the AES, N r rounds are applied to that state and N r = 14 for the 256-bit version. Each of the N r rounds (see Figure 12) applies four operations to the state matrix (except in the last round where the MixColumns operation is omitted):

-AddRoundKey (AK) adds a 128-bit subkey to the state.

-SubBytes (SB) applies the same 8-bit to 8-bit invertible S-Box S 16 times in parallel on each byte of the state. -ShiftRows (SR) shifts the i-th row left by i positions.

-MixColumns (MC) replaces each of the four columns C of the state by M × C where M is a constant 4 × 4 maximum distance separable matrix over F 256 .

wi-1 After the N r -th round has been applied, a final subkey is added to the internal state to produce the ciphertext. The key expansion algorithm to produce the N r + 1 subkeys is described in Figure 13. We refer to the original publication [26] for further details.

AK xi SB S yi SR X X X X An AES round applies MC • SR • SB • AK to the state. X X X X C ← M × C zi MC wi 3

Generation of the related keys

Because the key schedule of AES involves S-boxes, it is impossible to control the difference of each key byte, otherwise the possible values of some key bytes would be restricted, limiting the choice of the master key for the adversary and thus leading to weak-key attacks.

In our attack, the adversary is free to pick any master key K and we assume that he can then perform the following procedure to generate a related key K ′ . First, we choose the difference a to any non-zero value and another value b such that the differential transition b → a through the S-box happens with probability 2 -6 . In the case of our attack, as depicted in Figure 14, the adversary applies the difference b on the first byte of k 8 and the difference MC((a, 0, 0, 0)) to the first column of k 9 . He finally reconstructs K ′ from (k ′ 8 , k ′ 9 ).

The attack

The distinguisher we use for the attack starts from columns 0 and 3 of state w 0 and columns 1 and 2 of z 1 and stops at state x 11 . Both transitions ∆x 1 [0] → ∆z 1 [0] and ∆x 2 [0] → ∆z 2 [0] depend on uncontrollable differences from the key and thus there is a probability of 2 -2 that the characteristic does not hold. However, if it does, the average probability of the distinguisher is 2 -(7×2+6×12) = 2 -86 .

Step 1. The difference on P belongs to a vector space of dimension 11 since the differences on bytes 10, 11, 12 and 15 have to be 0 and ∆P [START_REF] Aoki | Preimage attacks on one-block MD4, 63-step MD5 and more[END_REF] = ∆P [START_REF] Biham | Miss in the middle attacks on IDEA and Khufu[END_REF] (because they are both equal to ∆k 2 [START_REF] Aoki | Preimage attacks on one-block MD4, 63-step MD5 and more[END_REF]). Thus, we start by asking for the encryption of a structure of 2 88 messages under the key K and a similar one under the key K ′ .

Step 2. We then pick a message P and the goal is to generate all the possible P and to associate to each of them the corresponding key values. First, we guess 9 bytes of k 0 and 2 bytes of k 1 to compute z 0 [0] and both z 1 [START_REF] Aoki | Preimage attacks on one-block MD4, 63-step MD5 and more[END_REF] and z 1 [START_REF] Aoki | Meet-in-the-middle preimage attacks against reduced SHA-0 and SHA-1[END_REF]. We then guess the difference in the first column of k 2 and propagate backwards the differences and values to obtain P . Furthermore, guessing the difference of k 2 gives us the values of the last column of k 3 since both the difference at the input and output of the S-box would be known for each byte of this column. As a result, we generate 2 (9+2+4)×8 = 2 120 tuples for

( P , k 0 [0, 2 , 3, 4, 7, 8, 9, 13, 14]
, k 1 [START_REF] Biham | Miss in the middle attacks on IDEA and Khufu[END_REF][START_REF] Biryukov | Key recovery attacks of practical complexity on AES-256 variants with up to 10 rounds[END_REF], k 3 [START_REF] Bogdanov | Biclique cryptanalysis of the full AES[END_REF][START_REF] Bordes | Thinking outside the superbox[END_REF][START_REF] Canteaut | Sieve-in-the-middle: Improved MITM attacks[END_REF][START_REF] Canteaut | Sieve-in-the-middle: Improved MITM attacks (full version)[END_REF]).

Step 3. Starting from the same message P as above and taking its corresponding ciphertext C, the goal is now to generate all the possible C. Step 4. We now look at matches between both lists of tuples so that ( P , C) is a valid plaintext-ciphertext pair. We expect around 2 Using a simple Gaussian elimination, we found that it is enough to guess 9 extra key bytes to fully reconstruct the master key, which then has to be checked against few additional data.

Complexity. The time complexity of Steps 2 to 4 is max(2 120 , 2 64 , 2 72 ) = 2 120 and the memory complexity is around 2 64 tuples of 128 + 64 = 192 bits since only the list built at Step 3 has to be stored. The attack has to be repeated 2 86 times (the probability of the distinguisher), leading to an overall complexity of 2 206 . The data complexity is 2 89 chosen plaintexts, 2 88 messages for each of both keys.

Note that the probability that the trail holds is 2 -2 because of the transitions ∆x

1 [0] → ∆z 1 [0] and ∆x 2 [0] → ∆z 2 [0]
. Thus, it might be needed to repeat the attack several times to retrieve the key, either by asking another key K ′ computed with another value of (a, b) or by modifying the position of the zero difference on the first column of z 1 (3 possible choices).

Conclusion and open problems

We introduced in this work a new cryptanalysis technique, that we called the differential MITM attack. We managed to successfully apply this new technique to SKINNY-128-384 and AES-256 in two different settings. Our attack against SKINNY allowed us to provide the best single-key attack against the analyzed variant by reaching two more rounds than the previously best known attack. Our application on AES-256 permitted to break 2 rounds more than the previously best attack that used two related keys or less.

The introduction of this new technique releases naturally numerous questions and opens many new research directions. First, we would like to further understand the link between the new attack and classical MITM attacks and how these two attacks can be compared. For example, we would like to identify for what kind of primitives the quantity of the involved key material in the differential MITM attack would be typically smaller compared to a classical MITM attack applied to the same cipher in a similar setting. We did some preliminary experiments on different ciphers by mounting both types of attacks in a comparable way and in some cases the amount of key bits to be guessed was smaller for the new attack while in some other cases this same amount was smaller for a classical MITM attack. It would therefore be interesting to be able to predict in an easy way, how this quantity compares for the two attacks. It would also be interesting to understand the details that allow our technique to be more performant than classical differential attacks and the other way round.

As MITM attacks combine particularly well with the technique of bicliques, another natural question is whether differential MITM attacks combine well with bicliques as well. Furthermore, is it possible to find any concrete application where the combination of a differential MITM with bicliques could improve previous MITM or other attacks? Finally, can the technique of bicliques be combined with the method of partitions we proposed in the case of partial subkey additions, and how do they compare?

A last open question is whether instead of combining MITM techniques with differential attacks, one could successfully combine MITM with some other wellknown family of cryptanalysis, such as for example linear or differential-linear attacks.

A Automatic detection of involved keys

We provide here a simple algorithm to search, given a differential, for efficient applications of the new attack. Indeed, in many cases, it is technically very easy to exactly determine which information about the key is required in the forward or backward computation. As often, when it comes to the question of dependency only, the easiest and less error-prone method is to experimentally determine which bits have an actual influence. Assume we are given (the implementation of) a function F : F n 2 → F m 2 and want to determine if the ith input bit of x has an influence on the output of F (x), that is if there exist an input x such that

F (x) ̸ = F (x ⊕ e i ),
where e i is the vector that has a one exactly at position i.

For this, we could simply take a random input x and compute F (x)⊕F (x⊕e i ). If the result is non-zero, we know that the output depends on the ith input bit. After repeating this process a few times and if we always get zero as a result, we conclude that the ith bit does not have an influence on the output. The later decision might of course be wrong (while the former never is). However, for our applications this is (i) very unlikely to happen due to the construction of the round functions and (ii) irrelevant for the attacks as a key bit that influences the output only in one out of many outputs usually does not have to be guessed.

Focusing on our target, given the implementation of the cipher, i.e. in particular the (round-reduced) encryption and decryption procedures along with the key schedule, we can easily process as represented in Algorithm 2.

Algorithm 2 Check Dependencies

Input: An Implementation of the round reduced encryption and decryption Er, a difference ∆ Output: The set of key bits K required to propagate ∆ through E -1 r 1: K ← ∅ 2: for each i from 0 to n -1 do 3:

for each t from 1 to tries do 4:

x ← random message 5:

k ← random key 6:

y1 ← Er(k, x) ▷ Query Encryption 7:

z1 ← E -1 r (k, y1 ⊕ ∆) ▷ Query Decryption 8:

y2 ← Er(k ⊕ ei, x) ▷ Query Encryption with bit flipped 9:

z2 ← E -1 r (k ⊕ ei, y2 ⊕ ∆) ▷ Query Decryption with bit flipped 10:

if z1 ̸ = z2 then 11:

Include key bit i to K 12:

end if 13:

end for 14: end for 15: Return K The nice feature of the algorithm is that it works for any cipher structure and without the need to know or implement any internal details. However, on this generality we might miss many possible improvements. As an example, consider the key schedule of SKINNY. Here, every round-tweak-key bit is the sum of three bits of (updated) master tweak-key bits. The algorithm above would (correctly) detect the dependence of the output on those three bits, but obviously guessing the sum of the bits is enough. We can easily adopt the above algorithm to take into account linear (tweak) key-schedules. The main idea is not to flip master key-bits directly, but rather round-key bits.

Let us denote the linear key schedule by L : F κ 2 → F n ṙ 2 . The ith bit of the expanded key can thus be written as ⟨L i , k⟩ where L i denotes the ith row of the matrix corresponding to L. Furthermore we denote by E r the encryption excluding the key schedule, i.e. E r (k, x) = E r (L(k), x).

Instead of master key-bits, we now aim at computing the round-key bits that the encryption depends on and collecting the corresponding linear combinations of the master-key.

R 1 R 2 R 3 R -1 3 R -1 2 R -1 1 k x L ∆ x
Algorithm 3 Check Linear-Dependencies

Input: An Implementation of the round reduced encryption and decryption Er, the key-schedule L and a difference ∆ Output: A linear subspace of key bits K required to propagate ∆ through E -1 r 1: K ← {} 2: for each i from 0 to n . . . r -1 do 3:

for each t from 1 to tries do 4:

x ← random message 5:

k ← random key 6:

y1 ← Er(L(k), x) ▷ Query Encryption 7:

z1 ← E -1 r (L(k), y1 ⊕ ∆) ▷ Query Decryption 8:

y2 ← Er(L(k) ⊕ ei, x) ▷ Query Encryption with bit flipped 9:

z2 ← E -1 r (L(k) ⊕ ei, y2 ⊕ ∆) ▷ Query Decryption with bit flipped 10:

if z1 ̸ = z2 then 11:

Include Li to K 12:

end if 13:

end for 14: end for 15: Return span(K) ▷ Vector space spanned by the corresponding Li

The vector-space contains the information that is sufficient to guess in order to compute the upper part of the attack. The dimension of K corresponds to the amount of information that has to be guessed, its Gauss-Jordan-basis contains information on which master key bits can be guessed equivalently. This algorithm again is easy to adapt given an implementation of a cipher. In practice, given a differential ∆ x → ∆ y , we can apply this algorithm on both (E in , ∆ x ) and (E -1 out , ∆ y ) to respectively get the sets k in and k out required in our new framework.

For SKINNY, Algorithm 3 allows to complete both the differential trails given in Section 3 into attacks against 23 and 24 rounds, that we will finally extend by one additional round at the end to get the currently best known results on SKINNY-128-384.

Fig. 1 .

 1 Fig. 1. A high-level description of the Differential MITM technique.

Fig. 2 .

 2 Fig. 2. Partial guess of the final state to add one round for free. Sr-1 is the final state of the simple differential MITM attack.

Fig. 3 .

 3 Fig. 3. Framework of a classical differential attack.

Fig. 4 .

 4 Fig. 4. Round function of SKINNY [4].

Fig. 5 .

 5 Fig.5. Tweakey schedule of SKINNY. All tweakey arrays TK1, TK2 and TK3 follow the same transformation with the only exception that no LFSR is applied to TK1.[START_REF] Beierle | The SKINNY family of block ciphers and its low-latency variant MANTIS[END_REF]

Fig. 6 .

 6 Fig. 6. Truncated differential trail for the attack on 23 rounds.

Fig. 7 .

 7 Fig. 7. Core attack against 23 rounds of SKINNY-128/384. Knowledge of blue key bytes allows to compute values of green ones and thus to propagate differences. No difference in both white and red bytes, but the red ones are required to compute green bytes. Indexes in subkey bytes are the indexes of the corresponding master key bytes. The equivalent subkeys Ui are computed as MC(SR(Ki)), from the original subkeys Ki.

Fig. 8 .

 8 Fig. 8. Enumeration procedure of kout for the 23-round attack. Differences in blue cells and actual values in red cells are known. No difference in white cells.

Fig. 9 .

 9 Fig. 9. Last round of the attack against 24 rounds.

Fig. 10 .

 10 Fig. 10. Truncated differential trail for the attack on 25 rounds.

Fig. 11 .

 11 Fig. 11. Core attack against 24 rounds of SKINNY-128-384. Knowledge of blue key bytes allows to compute values of green ones and thus to propagate differences. No difference in both white and red bytes, but the red ones are required to compute green bytes. Indexes in subkey bytes are the indexes of the corresponding master key bytes.

Fig. 12 .

 12 Fig. 12. Description of one AES round and the ordering of bytes in an internal state

Fig. 13 .

 13 Fig. 13. Key schedule of AES-256

Fig.

  Fig. Differential characteristic used in our 12-round attack. No difference in white cells. Transitions in blue belong to the distinguisher.

Table 1 .

 1 Best attacks against SKINNY-128-384 in the single-key (SK) model together with the results presented in this paper. ID stands for impossible differentials, MITM for meet-in-the-middle attacks and DS-MITM for Demirci-Selçuk-type MITM. 361.9 2 118.5 Diff-MITM Section 3.2 24 2 117 2 361.9 2 183 Diff-MITM Section 3.4 24 2 122.3 2 372.5 2 123.8 Diff-MITM Section 3.5 25 2 122.3 2 372.5 2 188.3 Diff-MITM Section 3.5

	# Rounds Data Time Memory	Type	Ref.
	21	2 123 2 353.6 2 341	ID	[47]
	21	2 122.89 2 347.35 2 336	ID	[30]
	22	2 96 2 382.46 2 330.99 DS-MITM	[43]
	22	2 92.22 2 373.48 2 147.22	ID	[45]
	23	2 104 2 376	2 8	MITM	[22]
	23	2 117 2

Table 2 .

 2 Best

	# Rounds Data Time Memory # Related-key	Type	Ref.
	9	2 120 2 203	2 203	0	MITM	[20]
	10	2 114 2 173	2 64	64	Rectangle	[7, 33]
	14	2 99.5 2 99.5	2 56	4	Boomerang	[11]
	14	2 91+s 2 92+s 2 89-s	2 19-s	Boomerang	[29] †
	14	2q q2 66	-	2q	q-multicollisions	[27]
	14	2 125 2 125	2 65	2 32	basic RK differential	[27]
	12	2 89 2 206 2 71.6	2	Diff-MITM	Section 4

attacks against AES-256 together with the results presented in this paper. † The parameter s should be such that 0 ≤ s ≤ 7.5.

.

  Lower part. Similarly, given C, we can guess some key material k out , of bitlength |k out |, and compute a new ciphertext C that satisfies the equationE -1 out (C)⊕ E -1 out ( C) = ∆ y ifthe key guess is correct. We obtain 2 |kout| values for C j , each associated to a guess j for k out .

  |kin|+|kout|-|kin∩kout|-n .

	Algorithm 1 Differential MITM attack
	while right key not found do	▷ 2 p trials expected
	Randomly pick P
	C ← E(P )	▷ Oracle call
	H ← ∅	▷ hash table initialization
	for each guess i for kin do	▷ Forward computation
	Compute P i from i and P
	C i ← E( P i )	▷ Oracle call
	H[ C i ] ← H[ C i ] ∪ {i}
	end for
	for each guess j for kout do	▷ Backward computation
	Compute C j from j and C
	for each i ∈ H[ C j ] do
	Complete (i, j) to retrieve the master key
	Try candidates against extra data
	end for
	end for
	end while

Table 3 .

 3 Number of rounds for each of the main variants SKINNY-n-t. This operation applies an S-box to all cells of the state. The table representation of the 8-bit S-box S used in the 128-bit variants is

	Block size n t = n t = 2n t = 3n
	64	32	36	40
	128	40	48	56
	SubCells (SC) S = [ 65 4c 6a 42 4b 63 43 6b 55 75 5a 7a 53 73 5b 7b
	35 8c 3a 81 89 33 80 3b 95 25 98 2a 90 23 99 2b
	e5 cc e8 c1 c9 e0 c0 e9 d5 f5 d8 f8 d0 f0 d9 f9
	a5 1c a8 12 1b a0 13 a9 05 b5 0a b8 03 b0 0b b9
	32 88 3c 85 8d 34 84 3d 91 22 9c 2c 94 24 9d 2d
	62 4a 6c 45 4d 64 44 6d 52 72 5c 7c 54 74 5d 7d
	a1 1a ac 15 1d a4 14 ad 02 b1 0c bc 04 b4 0d bd
	e1 c8 ec c5 cd e4 c4 ed d1 f1 dc fc d4 f4 dd fd
	36 8e 38 82 8b 30 83 39 96 26 9a 28 93 20 9b 29
	66 4e 68 41 49 60 40 69 56 76 58 78 50 70 59 79
	a6 1e aa 11 19 a3 10 ab 06 b6 08 ba 00 b3 09 bb
	e6 ce ea c2 cb e3 c3 eb d6 f6 da fa d3 f3 db fb
	31 8a 3e 86 8f 37 87 3f 92 21 9e 2e 97 27 9f 2f
	61 48 6e 46 4f 67 47 6f 51 71 5e 7e 57 77 5f 7f
	a2 18 ae 16 1f a7 17 af 01 b2 0e be 07 b7 0f bf
	e2 ca ee c6 cf e7 c7 ef d2 f2 de fe d7 f7 df ff ].

Table 4 .

 4 Subkey bytes involved in the 23-round core attack.

	Byte	kin	kout	# equations
	0

  The procedure is quite straightforward. First, we guess the difference of k 11 [0] as well as the difference on the first column of k 12 . This gives us the difference on both k 11 and k 12 . Then we guess the first line of k 12 except the last byte (which is obtained by computing k

[START_REF] Bogdanov | Biclique cryptanalysis of the full AES[END_REF]

[START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF]

⊕ k 10

[START_REF] Bogdanov | Biclique cryptanalysis of the full AES[END_REF]

) and we can compute C. As a result, we generate 2 (5+3)×8 = 2 64 tuples for ( C, k 10

[START_REF] Bogdanov | Biclique cryptanalysis of the full AES[END_REF]

, k 11

[START_REF] Bogdanov | Biclique cryptanalysis of the full AES[END_REF][START_REF] Bordes | Thinking outside the superbox[END_REF][START_REF] Canteaut | Sieve-in-the-middle: Improved MITM attacks[END_REF][START_REF] Canteaut | Sieve-in-the-middle: Improved MITM attacks (full version)[END_REF]

, k 12 [0,

[START_REF] Beierle | The SKINNY family of block ciphers and its low-latency variant MANTIS[END_REF][START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF][START_REF] Bogdanov | Biclique cryptanalysis of the full AES[END_REF]

).

Note that[START_REF] Hadipour | Finding the impossible: Automated search for full impossible-differential, zero-correlation, and integral attacks[END_REF] provides a 26-round integral attack against SKINNY-128-384 but it relies on differences in the tweak.

Acknowledgements. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 714294 -acronym QUASY-Modo). It was also partially supported by the French Agence Nationale de la Recherche through the SWAP project under Contract ANR-21-CE39-0012, through the DeCrypt project under Contract ANR-18-CE39-0007, and by the Deutsche Forschungsgemeinschaft (DFG, German Research Foudation) under

Germany's Excellence Strategy -EXC 2092 CASA -390781972. Finally, the authors would like to thank the Dagstuhl Seminar 22141 on Symmetric Cryptography that gave the opportunity to the authors to advance this collaboration.