Patrick Derbez
email: patrick.derbez@ens.fr

Pierre-Alain Fouque
email: pierre-alain.fouque@ens.fr

Exhausting Demirci-Selçuk Meet-in-the-Middle Attacks against Reduced-Round AES

In this paper, we revisit Demirci and Selçuk meet-in-the-middle attacks on AES. We find a way to automatically model SPN block cipher and meet-in-the-middle attacks that allows to perform exhaustive search of this kind of attacks. This search uses the tool developed by Bouillaguet, Derbez and Fouque at CRYPTO 2011 as a subroutine to solve specific systems. We also take into account ideas introduced by Dunkelman, Keller and Shamir at ASIACRYPT 2010 which can be seen as a new tradeoff of the classical time/memory tradeoff used by Demirci and Selçuk. As a result, we automatically recover all the recent improved attacks of Derbez, Fouque and Jean on AES and we show new improved attacks against 8-rounds of AES-192 and AES-256.

. The main technique is the differential enumeration which allows to reduce the high memory complexity. This is mainly the bottleneck of the previous attacks with the precomputation phase. The attack can be seen as a new time/memory tradeoff, while Demirci and Selçuk one was very simple. Indeed, in this latter basic attack the memory is greater than the time. Consequently, they reduce the data in memory by repeting the attack as many times as the inverse of the probability of being in the table. Dunkelman et al. tradeoff uses a specific differential path to reduce the memory. This saving allows to consider a new attack on 7 rounds of AES-128 with basically the same complexity as the impossible differential attack, which is the best attack on this version. They also improve the attacks on the two other versions. However, since these attacks rely on a differential technique, they require a huge amount of data. Basically, they show that the number of parameters can be reduced from 24 to 16 while the time complexity is constant. These attacks have been recently improved by Derbez et al. in [11] by showing that the table can be reduced since many sequences in the table are never reached. They exactly compute the size of the memory needed and show that the table can be described by 10 parameters. This leads to the best attack for 7 rounds of AES-128 and also to the other versions.

. For instance, we present on AES-128 an attack on up to 6 rounds using 256 data complexity and 2 106 in time and memory whereas Bouillaguet et al. were able to find attack on 5 rounds with complexity 2 120 . It is possible to extend this last attack to 7 rounds with a marginal improvement over exhaustive search. We refer the reader to table 1 for all the attacks. Organization of the Paper. In section 2, we describe the AES cipher and some properties useful to analyze its security for meet-in-the-middle techniques. Then, we present the previous attacks and ideas in section 3 before showing our ideas in section 4. In section 5, we discuss on the results and describe some of our new attacks requiring at most 2 32 chosen plaintexts. The section 6 is dedicated to the differential enumeration technique introduced by Dunkelman et al. and contains the description of new attacks on AES-192 requiring 2 104 data, 2 138 in memory and 2 140 in time and on AES-256 requiring 2 103 in data, 2 140 in memory and 2 156 in time.

AES and Observations

2.1 Description of the AES The Advanced Encryption Standard [19] is a Substitution-Permutation Network that can be instantiated using three different key sizes: 128, 192, and 256. The 128-bit plaintext initializes

Introduction

The AES encryption scheme [START_REF]NIST: Advanced Encryption Standard (AES), FIPS 197[END_REF] has been developed in the late nineties and has been specifically designed to resist against differential and linear cryptanalysis. Since 2008, the best attack for the 128-bit version was an impossible differential attacks by Lu et al. in [START_REF] Lu | New impossible differential attacks on AES[END_REF] going back to a remark of Biham and Keller [START_REF] Biham | Cryptanalysis of Reduced Variants of Rijndael[END_REF] improved by Bahrak and Aref in 2007. For the 192-bit and 256bit versions, Demirci and Selçuk have described generalization of the Gilbert-Minier attack [START_REF] Gilbert | A collision attack on 7 rounds of Rijndael[END_REF] which has also been discovered during the AES competition. During almost 10 years, there was no new cryptanalytic result and the first successful direction to analyze the AES encryption function comes from differential attacks in the related-key setting in 2009. This is a very powerful adversarial model in theory and it has recently been studied due to its applications in the analysis of hash functions. In this model, many other interesting results have been obtained by carefully studying the key schedule algorithms of AES-192 and AES-256 [START_REF] Biryukov | Distinguisher and related-key attack on the full aes-256[END_REF][START_REF] Biryukov | Related-Key Cryptanalysis of the Full AES-192 and[END_REF][START_REF] Biryukov | Key recovery attacks of practical complexity on aes-256 variants with up to 10 rounds[END_REF][START_REF] Biryukov | Automatic search for related-key differential characteristics in byte-oriented block ciphers: Application to aes, camellia, khazad and others[END_REF].

Despite important work on side-channel analysis on the AES, no real theoretical improvement on the first analysis performed during the AES competition [START_REF] Daemen | AES proposal: Rijndael[END_REF][START_REF] Gilbert | A collision attack on 7 rounds of Rijndael[END_REF][START_REF] Biham | Cryptanalysis of Reduced Variants of Rijndael[END_REF][START_REF] Ferguson | Improved cryptanalysis of rijndael[END_REF] has been made. In this paper we turn our attention to the standard single-key model using meet-in-the-middle attack since these attacks are very efficient and are now the most efficient on all version of AES [START_REF] Derbez | Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting[END_REF]. The first new theoretical result has been shown by Demirci and Selçuk at FSE 2008 using the old Meet-in-the-Middle cryptanalysis technique [START_REF] Demirci | A meet-in-the-middle attack on 8-round AES[END_REF]. They improve the Gilbert and Minier attack using meet-in-the-middle technique instead of collision ideas. These results at that time use a very small data complexity 2 34 but require high precomputation and memory in 2 216 . They need a hash table parameterized by 24 byte values. These attacks only work for the 256-bit and 192bit versions thanks to a time/memory tradeoff which significantly increases the data and time complexity. They have been improved by Dunkelman et al. in [START_REF] Dunkelman | Improved Single-Key Attacks on 8-Round AES-192 and AES[END_REF] and more recently by Derbez et al. in [START_REF] Derbez | Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting[END_REF]. Finally, recent biclique attacks [START_REF] Bogdanov | Biclique Cryptanalysis of the Full AES[END_REF] have been able to attack the full number of rounds of the AES at the price of using an exhaustive loop on all the key bits. the internal state viewed as a 4 × 4 matrix of bytes as 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: N r = 10 for AES-128, N r = 12 for AES-192 and N r = 14 for AES-256. Each of the N r AES round (Figure 1) applies four operations to the state matrix (except in the last round where the MixColumns operation is missing):

-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 column C of the state by M × C where M is a constant 4 × 4 maximum distance separable matrix over F 256 , 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 algorithms to produce the N r + 1 subkeys for AES-128 are described in Figure ?? for each keysize. We refer to the original publication [START_REF]NIST: Advanced Encryption Standard (AES), FIPS 197[END_REF] for further details. Notations. In this paper, we count the AES rounds from 0 and we refer to a particular byte of an internal state x by x[i], as depicted in Figure 1. Moreover, in the ith round, we denote the internal state after AddRoundKey by x i , after SubBytes by y i , after ShiftRows by z i and after MixColumns by w i . To refer to the difference in a state x, we use the notation ∆x. The first added subkey is the master key k -1 , and the one added after round i is denoted k i .

In some cases, we are interested in swapping the order of the MixColumns and AddRoundKey operations. As these operations are linear they can be interchanged, by first XORing the data with an equivalent key and only then applying the MixColumns operation. We denote the equivalent subkey for the altered version by:

u i = M C -1 (k i ) =     0e 0b 0d 09 09 0e 0b 0d 0d 09 0e 0b 0b 0d 09 0e     × k i

Observations on the Structure of AES

In this section we recall well-known observations on the structure of AES, that will be used later in our attacks. We first consider the propagation of differences through SubBytes layer.

Property 1 (the SubBytes property). Consider pairs (α = 0, β) of input/output differences for a single S-box in the SubBytes operation. For 129/256 of such pairs, the differential transition is impossible, i.e., there is no pair (x, y) such that x ⊕ y = α and S(x) ⊕ S(y) = β. For 126/256 of the pairs (α, β), there exist two ordered pairs (x, y) such that x ⊕ y = α and S(x) ⊕ S(y) = β, and for the remaining 1/256 of the pairs (α, β) there exist four ordered pairs (x, y) that satisfy the input/output differences. Moreover, the pairs (x, y) of input values corresponding to a given difference pattern (α, β) can be found instantly from the difference distribution table of the Sbox.

Property 1 means that given the input and output difference of an S-box, we can find in constant time the possible absolute values of the input, and there is only a single one on average.

The second observation is a necessary and sufficient condition for a matrix to be MDS applied to the matrix M C used in the MixColumns operation. The third observation concerns the AES key schedule and mainly exploits the fact that most of the operations in the key schedule algorithm are linear.

Property 3 (the key-schedule properties). Consider a sequence of consecutive subkeys k r , k r+1 , . . . . We have the following useful relations between the equivalent subkeys u r , u r+1 , . . . : We will also use the key bridging technique described by Dunkelman et al. in [13]. This observation exploits a weakness in keyschedule of AES-192 and can be stated as follows:

• AES-128 : 1) u r [4..7] = u r+1 [0..3] + u r+1 [4..7] 2) u r [8..
Property 4 (the key bridging technique). According to the key schedule of AES-192, knowledge of columns 0, 1, 3 of subkey k 7 allows to deduce column 3 of the whitening key k -1 (which is actually Column 3 of the master key).

Finally, in our attacks we consider the encryption of structured sets of 256 plaintexts in which one active byte takes each one of the 256 possible values exactly once, and each one of the other 15 bytes is a (possibly different) constant. Such a structure is called a δ-set.

Related Results from Previous Work

In this section, we remind Demirci and Selçuk attack together with its improvements which are the main results used in our attack. We refer the reader to [START_REF] Demirci | A meet-in-the-middle attack on 8-round AES[END_REF] and [START_REF] Dunkelman | Improved Single-Key Attacks on 8-Round AES-192 and AES[END_REF] for details.

The Demirci and Selçuk attack

At FSE 2008, Demirci and Selçuk described the following 4-round property for AES. Property 5. Consider the encryption of a δ-set through four full AES rounds. For each of the 16 bytes of the state, the ordered sequence of 256 values of that byte in the corresponding ciphertexts is fully determined by just 25 byte parameters. Consequently, for any fixed byte position, there are at most (2 8 ) 25 = 2 200 possible sequences when we consider all the possible choices of keys and δ-sets (out of the (2 8 ) 256 = 2 2048 theoretically possible 256-byte sequences).

The 25 parameters are intermediate state bytes for any message of the δ-set and their positions depend on the active byte of the δ-set and on which byte we want to build values. As depicted on Figure 2, if there are both at position 0 then the 25 parameters are the first column of x i+1 , the full state x i+2 , the first column of z i+3 and x i+4 [0]. Indeed, if those bytes are known for one of the messages, we can compute the value of x i+4 [0] for each message of the δ-set as follows:

1. Knowing the 256 differences in the full state z i we can compute the 256 differences in the full state x i+1 because ∆x j+1 = MC.∆z j for any round number j, where MC is the matrix used in the MixColumns operation. 2. Knowing the value of the first column of x i+1 for one message we can now compute the value of this column for all messages. 3. Then we apply the Sbox on those bytes and get the value of z i+1 [0], z i+1 [START_REF] Bouillaguet | Low-data complexity attacks on aes[END_REF], z i+1 [START_REF] Demirci | A meet-in-the-middle attack on 8-round AES[END_REF] and z i+1 [START_REF] Dunkelman | Improved Single-Key Attacks on 8-Round AES-192 and AES[END_REF] for each message of the δ-set. 4. The differences are null in all the other bytes of z i+1 so we know the 256 differences in the full state z i+1 . 5. In the same way we obtain the 256 differences in the full state z i+2 and then in the first column of z i+3 to finally compute the 256 values of x i+4 [0] They first use this property to mount a basic meet-in-the-middle attack on 7 rounds AES-256 depicted on Figure 3 and its procedure is roughly as follows:

• Preprocessing phase: Compute all the 2 200 possible sequences according to Property 5, and store them in a hash table. Note that the parameters of both the online and offline phases are state bytes which we shall refer in the sequel as respectively B on and B of f . The complexity of the attack depends directly on how many values can assume those state bytes and how fast can we enumerate them. Indeed, bytes of B of f (resp. B on ∪P ∪C) are related by the AES equations and thus lead to the knowledge of some linear combinations of the (sub)keys bytes. Then it may exist some relations derived from the key-schedule between them, allowing to reduce the number of assumed values. In the sequel, we will denote by K of f (resp. K on ) the vector space generated from these linear combinations. For instance, in the case of the described attack and if the last MixColumns is omitted,

• {k -1 [0], k -1 [5], k -1 [10], k -1 [15], k 0 [0], u 5 [0], k 6 [0], k 6 [7], k 6 [10], k 6 [13]} is a basis of K on , • {u 1 [0], u 2 [0], u 2 [7], u 2 [10], u 2 [13], k 3 [0], k 3 [5], k 3 [10], k 3 [15], k 4 [0]} is a basis of K of f .
All in all, this attack has a data complexity of 2 32 chosen plaintexts, a time complexity of 2 80 × 2 8 partial encryptions/decryptions, and a memory requirement of 2 200 256-byte sequences. The memory complexity of this attack is too high to apply it on the 128 and 192-bit versions. But its time complexity is low enough to mount an attack from it on 8 rounds AES-256. This is done by fully guessing the last subkey, decrypting the last round and applying the 7-round attack, which increases the time complexity by a factor 2 128 .

Previous improvements of the original attack

We summarize the main improvements to the original attack of Demirci and Selçuk.

Difference Instead of Value. Demirci and Selçuk showed that the number of parameters can be reduced to 24 in Property 5 by considering the sequence of the differences instead of values because in that case x i+4 [0] is not needed.

Data/Time/Memory Trade-Off. They also showed that one can do a classical trade-off by storing in the hash table only a fraction of the possible sequences. Then the attacker has to repeat the online phase many times to compensate the probability of failure if the sequence is not present in the table which will increase the data and time complexities. In other word, if the attack has a complexity (D, T, M ) (D for the data, T for the time complexity of the online phase and M for the memory) then it is possible to modify it to reach a complexity equal to (D×N, T ×N, M/N ) for any positive N such that D×N is smaller than the size of the codebook. This trade-off allows to adapt the attack on 7 rounds of AES-256 to attack the 192-bit version.

Data Recycling. The structure of 2 32 plaintexts used in the attack contains 2 24 δ-sets. Thus the data may be reused 2 24 times in the Data/Time/Memory Trade-Off.

Time/Memory Trade-Off. Kara observed that considering the sequence of the differences instead of values allows to remove x 5 [0] from B of f (as Demirci and Selçuk did) or from B on .

Multiset. A multiset is an unordered set in which elements can occur many times. Dunkelman et al. introduce them to replace the functional concept used in the DS attack and propose to store in the hash table unordered sequences of 256 bytes instead of ordered sequences. Moreover, they claim that a multiset still contains enough information to make the attack possible. Indeed they showed that given two random functions f, g : F 256 -→ F 256 , the multisets [f (0), . . . , f (255)] and [g(0), . . . , g(255)] are equal with a probability smaller than 2 -467,6 . Combined to the fact that the Sbox is a bijection, the main gain is to remove z 1 [0] from B on since it was used only to ordered the δ-set, and thus the time complexity is decreased by a factor 2 8 . Finally, we note that a multiset contains about 512 bits of information and its representation can be easily compressed into 512 bits of space while an ordered sequence needs 256 × 8 = 2048 bits. Differential Enumeration. In [START_REF] Dunkelman | Improved Single-Key Attacks on 8-Round AES-192 and AES[END_REF], Dunkelman et al. introduce a more sophisticated trade-off which reduces the memory without increasing the time complexity. The main idea is to add restrictions on the parameters used to build the table such that those restrictions can be checked (at least partially) during the online phase. More precisely, they impose that sequences stored come from a δ-set containing a message m which belongs to a pair (m, m ′ ) that follows a wellchosen differential path. Then the attacker first focus on finding such pair before to identify a δ-set and build the sequence. Section 6 is dedicated to this technique.

Generalization of the Demirci and Selçuk Attack

The basic attack of Demirci and Selçuk requires a huge memory and a relatively small time complexity. The classical data/time/memory trade-off allows to balance these complexities by increasing the data complexity and randomizing the attack. In this section we present new improvements to reduce the data complexity increase which leads to almost 2 16 variants of the Demirci and Selçuk attack and we explain how to find the best ones between them.

New improvements of the original attack

In this section we summarized our new improvements that allow us to reduce the increase of the data complexity and, sometimes, to keep the deterministic nature of the original attack.

Difference Instead of Value. The sequences stored in the table have the form [f (0) + f (0), . . . , f (0) + f (255)] where f is a function that maps the value of z i [0] to the value of

x i+4 [0] + k i+3 [0]
. But, as shown Section 3.1, the procedure used to build the table produces functions that map the value of ∆z i [0] to the value of ∆x i+4 [0] and then the only effect of mapping the value of z i [0] is to set the value of the subkey byte u i [0] (i.e. u i [0] ∈ K of f ). In another hand, if we store in the table sequences of the form [f (0), . . . , f (255)] where f is a function that maps the value of ∆z i [0] to the value of ∆x i+4 [0], then each δ-set can be ordered in 256 ways, saving data in the classical data/time/memory trade-off described Section 3.2. Furthermore, in the case of a δ-set encryption, each byte of the first columns of x i+1 assumes the 256 values. As a consequence, to set one of those bytes to 0 when building the hash table can be compensated by trying the 256 orders of a δ-set without randomizing the attack. 1), . . . , f (0)+f (255)] contains on average 162 different values out of 256. Thus we conclude that a δ-set can be reused 162 ≈ 2 7,34 times on average. This remark holds on for the multisets stored in the hash table during the precompution phase and so the memory requirement must be corrected by a factor 2 -0,66 . Time/Memory Trade-Off. To improve the attack of Demirci and Selçuk our idea is to store in the sequences the 256 differences in a linear combinations of bytes of x 5 instead of the 256 differences in a byte of x 5 . Thanks to Property 2, minimal equations involving ∆z i and ∆x i+1 contains exactly 5 variables such that k are on a column c of ∆z i and 5k are on the column c of ∆x i+1 , with 1 ≤ k ≤ 4 for any round number i. We emphase that Demirci and Selçuk only consider cases k = 1 and k = 4. The size of the set B on (resp. B of f ) is determined by k and it decreases (resp. increases) when k is increased. Thus we can trade time by memory and vice-versa without affecting the data complexity. Furthermore, contrary to the other data/time/memory trade-offs, the attack need not to be randomized. Attacks taking advantage of this trade-off are described Section 5.2 and 5.4.

New Data/Time/Memory Trade-Off. The idea of the previous trade-off can be applied to the δ-set. Instead of considering sets of 256 plaintexts such that one byte assumes the 256 values and the others are constant, we consider set of 256 plaintexts such that exactly 5 bytes of z i and x i+1 are active. We still call such a set a δ-set. The consequences on the attack are the same as the previous trade-off but it now affects the size of the structure needed and bytes of z i must be guessed in the online phase despite the use of unordered sequences. An attack taking advantage of this trade-off is described Section 5.3.

Finding the best attack

Once the round-reduced AES is split into three parts, the new improvements allow to mount (4 × 8 5 ) 2 ≈ 2 15.6 different attacks but there are only (4

× ( 4 1 + 4 2 + 4 3 + 4 4
)) 2 ≈ 2 11.8 possible sets B on (resp. B of f ) to study. To exhaust all of them and find the best attacks we decide to automatize the search. Thus for each set we need to answer to the two following questions:

• How many values can assume those state bytes?

• How fast can we enumerate them?

A priori, this is not an easy task because S-boxes are involved in the keyschedule. To perform it we used the tool developed in [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF], originally designed to find the best solver for an AES-like system of equations among a particular class of solvers based on the meet-in-the-middle technique.

Algorithm 1: OriginalTool

Data: System of equations E in variables X involving some S-boxes.

Result: An optimal algorithm to enumerate all the solutions of E with predictable time and memory complexities.

The problem we seek to solve is very close to the problem solved by this tool but is still different and so we have slightly tweaked it.

Algorithm 2: TweakedTool (naive implementation)

Data: System of equations E in variables X involving some S-boxes and a subset Y ⊆ X.

Result: A list of optimal algorithms to enumerate all the possible values of Y according to the system of equations E with predictable time and memory complexities.

L ← ∅; foreach Y ⊆ Z ⊆ X do F ← the biggest subspace of E in variables Z; A ← OriginalTool(F ); L ← best algorithms from L ∪ {A}; end return L
The output of our tweaked tool is a list because the number of possible values of Y enumerated by considered algorithms is not necessary constant and if an algorithm is slower than an other but finds less possible values for Y than it then both of them must be studied. Note that the tweaked tool can be applied directly to the set B of f (resp. B on ) and the system of equations describing the AES but it is faster to apply it on a basis of K of f (resp. K on ) and the keyschedule equations since the complexity of the original tool is exponential in the number of S-box.

Finally we were able to perform an exhaustive search over all the parameters for all roundreduced versions of AES for the three key lengths in less than an hour on a personal computer. Furthermore we automatically rediscovered the observations made in Section 2.2, including the non-trivial key bridging technique.

Results

In this section we present the results obtained by exhausting the variants of the attack of Demirci and Selçuk. We give an overview of the complexities reached and describe three new attacks requiring at most 2 32 chosen plaintexts and minimizing the maximum between the time complexity (counted in AES encryption) and the memory complexity (counted in 128-bit block).

Overview of the results

Our best results on 7 and 8 rounds are summarized on Figures 4, 5 and6. They give the (log 256 of) data complexity reached as a function of the number of guess to perform in the online phase and in the offline phase. A gray cell means that the corresponding attack is deterministic while the other attacks are obtained by applying the classical data/time/memory trade-off.

We observe that almost all the best attacks work with only 2 32 chosen-plaintexts. For comparison, to reach balanced complexities on seven rounds from the original attack by using the classical data/time/memory trade-off, the amount of data needed will be approximately 2 71 chosen plaintexts. Furthermore, we have been able to increase by one the number of rounds attacked with 2 32 chosen-plaintexts for the three key length but with time and memory complexities very number of guess in the offline phase number of guess in the online phase last mixcolumns performed close to the natural bound of the exhaustive search. We also obtained competitive results in the very low data complexity league with, for instance, attacks on 8 rounds of AES-256 requiring only 2 8 chosen plaintexts.

5.2 Attack on six rounds AES-128 with 2 8 chosen-plaintexts.

If the data available is limited to 2 8 chosen-plaintexts, the best attack found is based on the attack depicted on Figure 7 and the meet-in-the-middle is performed on the equation 03.∆z 3 [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF] + ∆z 3 [START_REF] Daemen | AES proposal: Rijndael[END_REF] = 07.∆x 4 [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF] + 07.∆x 4 [START_REF] Daemen | AES proposal: Rijndael[END_REF] + 02.∆x 4 [START_REF] Derbez | Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting[END_REF].

Let be e in = 03.z 3 [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF] + z 3 [START_REF] Daemen | AES proposal: Rijndael[END_REF] and e out = 07.x 4 [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF] + 07.x 4 [9] + 02.x 4 [START_REF] Derbez | Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting[END_REF]. The bytes of B of f are the first column of x 1 , the two last columns of z 2 , and bytes 8 and 9 of z 3 . They can assume 2 8×14 different values and so the memory requirement is 2 112-0,66 = 2 111,34 multisets on average according to the remark made in Section 4.1.

As the S-box is a bijection and as we consider a δ-set in which only one byte is active, we do not need to guess x 0 [0] in order to identify the corresponding set of 256 plaintexts to build the multiset. As a consequence, the bytes of B on are the entire state x 5 except the first column, and the third column of x 4 except byte 10. Thanks to the keyschedule equations, they can take only 2 8×12 values instead of 2 8×15 since we have the three equations u 4 [START_REF] Biryukov | Automatic search for related-key differential characteristics in byte-oriented block ciphers: Application to aes, camellia, khazad and others[END_REF] [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF] and u 4 [START_REF]Advances in Cryptology -EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques[END_REF] = u 5 [START_REF] Derbez | Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting[END_REF] + u 5 [START_REF]Advances in Cryptology -EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques[END_REF].

= u 5 [1] + u 5 [5], u 4 [8] = u 5 [4] + u 5
All in all this leads to the following attack:

• Preprocessing phase:

1. Set ∆ i z 0 [0] to i for 0 ≤ i ≤ 255.
Then ∆ i z 0 is known since the other differences are null. 2. Guess x 1 [0..3] (for one of the 256 messages) and use

∆ i z 0 to compute ∆ i z 1 [0], ∆ i z 1 [7],
∆ i z 1 [START_REF] Demirci | A meet-in-the-middle attack on 8-round AES[END_REF] and ∆ i z 1 [START_REF] Dunkelman | Improved Single-Key Attacks on 8-Round AES-192 and AES[END_REF]. Then ∆ i z 1 is known since the other differences are null. 3. Guess bytes 1, 2, 6, 7, 8, 11, 12 and 13 of x 2 . Use them with ∆ i z 1 to compute ∆ i z 2 [8..15]. 4. Guess x 3 [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF] then compute ∆ i z 3 [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF] using ∆ i z 2 [8..11]. 5. Guess x 3 [START_REF] Dunkelman | Improved Single-Key Attacks on 8-Round AES-192 and AES[END_REF] then compute ∆ i z 3 [START_REF] Daemen | AES proposal: Rijndael[END_REF] using ∆ i z 2 [12..15]. 6. Compute the multiset [∆ 0 e in , . . . , ∆ 255 e in ] and store it in a hash table (if it was not already in it). • Online phase:

1. Ask for a structure of 256 plaintexts such that byte 0 assume the 256 possible values and others bytes are constant. 2. Choose one of them to be the one from which difference will be computed. 3. Guess bytes 1, 2, 4, 5, 8, 11, 14 and 15 of u 5 . Compute u 4 [START_REF] Biryukov | Automatic search for related-key differential characteristics in byte-oriented block ciphers: Application to aes, camellia, khazad and others[END_REF] and u 4 [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF] and then partially decrypt the ciphertexts to obtain ∆ i x 4 [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF] and ∆ i x 4 [START_REF] Daemen | AES proposal: Rijndael[END_REF] for 0 ≤ i ≤ 255.

4. Guess bytes 3, 6 and 9 of u 5 , and continue to partially decrypt the ciphertexts. 5. Guess byte 12 of u 5 . Compute u 4 [START_REF]Advances in Cryptology -EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques[END_REF] and then partially decrypt the ciphertexts to obtain ∆ i x 4 [START_REF] Derbez | Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting[END_REF]. 6. Build the multiset [∆ 0 e out , . . . , ∆ 255 e out ] and check whether the multiset exists in the hash table . If not, discard the key guess.

Finally, the time complexity is equivalent to 2 × 2 -6 × 2 8 × 2 96 = 2 99 encryptions and the memory requirement is 2 113,34 AES-blocks. The probability for a wrong guess to succeed is approximatively 2 111,34 × 2 -467,6 = 2 -356,26 and, as we try 2 96 key guess, we expect that only the right value remains after the last step.

Trade-Off. Since the memory is higher than the time complexity, the data/time/memory tradeoff presented Section 3.2 is possible. This leads to an attack using 2 8 chosen plaintexts (as the data is reused 2 7,17 times), with a time complexity equivalent to 2 106,17 encryptions and requiring 2 106,17 128-bit blocks.

Key Recovery. This attack retrieves the right value of u 5 except on bytes 0, 7, 10 and 13 and so can easily be turned into a key-recovery attack. The attacker guesses the four missing bytes of u 5 to retrieve the master key and try it. This step has a negligible complexity compared to the previous one.

Attack on 7 rounds AES-256 with 2 16 chosen-plaintexts

The best attack on seven rounds AES-256 with 2 16 chosen-plaintexts is depicted on Figure 8. The bytes of B of f are bytes 0,2 and 3 of x 1 , the three first columns of x 2 and the third column of z 3 . The bytes of B on are bytes 0 and 15 of x 0 , the entire state x 6 , the second column of x 5 and byte 9 of x 4 . The number of values assumed by the bytes of B on is reduced by a factor 2 8 using the equation u 4 [START_REF] Biryukov | Automatic search for related-key differential characteristics in byte-oriented block ciphers: Application to aes, camellia, khazad and others[END_REF] = u 6 [1] + u 6 [START_REF] Biryukov | Automatic search for related-key differential characteristics in byte-oriented block ciphers: Application to aes, camellia, khazad and others[END_REF]. The time complexity is equivalent to 2 178 encryptions and the memory is 2 153,34 AES-blocks.

Key Recovery. This attack can easily be turned into a key-recovery attack without increasing the complexity since only 12 key bytes are sufficient to recover the master key.

Attack on 7 rounds AES-192 with 2 32 chosen-plaintexts

The best attack on seven rounds AES-192 with 2 32 chosen-plaintexts is depicted on Figure 9.

The bytes of B of f are the first column of x 2 , the three first columns of z 3 , and bytes 0, 1 and 2 of z 4 . The bytes of B on are the first column of z 0 , the second and third columns of x 6 and bytes 2 and 3 of x 5 . Thanks to Property 3, we can reduce the number of possible values assumed by them by a factor 2 8 since u 5 [START_REF] Bouillaguet | Low-data complexity attacks on aes[END_REF] = u 6 [START_REF] Derbez | Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting[END_REF] + u 6 [START_REF]Advances in Cryptology -EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques[END_REF]. The time complexity is equivalent to 2 106 encryptions and the memory requirement is 2 153,34 AES-blocks.

Trade-Off. Applying the classical data/time/memory trade-off leads to an attack using 2 32 chosen plaintexts, with a time complexity equivalent to 2 129,67 encryptions and a memory requirement of 2 129,67 AES-blocks. Note that the data complexity remains 2 32 because the structure may be divided into 2 24 δ-sets and each of them may be reused 2 7,34 times on average. Key Recovery. This attack can easily be turned into a key-recovery attack without increasing the complexity since only 15 key bytes are sufficient to recover the master key.

The Differential Enumeration Technique

We present here our results using the differential enumeration technique first introduced by Dunkelman et al. in [START_REF] Dunkelman | Improved Single-Key Attacks on 8-Round AES-192 and AES[END_REF] and improved by Derbez et al. in [START_REF] Derbez | Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting[END_REF]. We explain how this technique works by describing a new attack on 8 rounds and then we give an overview of our results.

Attack on 8 rounds AES-192

Without restriction on data, the best attack on eight rounds AES-192 begins by considering the attack depicted on Figure 10. The bytes of B of f are the first column of x 2 , the entire state x 3 , the two last columns of z 4 and bytes 2 and 3 of z 5 . The bytes of B on are the second column of z 0 , the three first columns of x 7 , and the first column of x 6 excepted byte 1. Thanks to Property 3, they take only 2 8×17 = 2 136 values because u 6 [0] = u 7 [4] + u 7 [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF] and u 6 [START_REF] Bouillaguet | Low-data complexity attacks on aes[END_REF] = u 7 [START_REF] Derbez | Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting[END_REF] + u 7 [START_REF]Advances in Cryptology -EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques[END_REF]. Finally, the time complexity is equivalent to 2 138 encryptions and the memory requirement is 2 241,34 AES-blocks. Differential Enumeration. The idea of Dunkelman et al. is to store in the hash table only the multisets built from a δ-set containing a message m that belongs to a pair (m, m ′ ) following a well-chosen differential path. In our case this is the truncated differential for such a pair. Indeed, if we guess the differences in circled bytes then we obtain the difference before and after the S-box for each bytes of B of f and thus we can derive their absolute value thanks to Property 1. As a consequence, the memory requirement is decreased by a factor 2 112 . However, we now need to find a pair that follows this truncated differential path and so the procedure of the online phase becomes:

4 → 1 → 4 → 16 → 8 → 2 → 3 →
1. Ask for a structure of 2 32 plaintexts such that the second diagonal assume the 2 32 possible values and others bytes are constant. 2. Store the corresponding ciphertexts in a hash table to identify the pairs that have a non-zero probability to follow the differential path. 3. For each of these pairs:

(a) Guess ∆z 6 [0], ∆z 6 [START_REF] Bouillaguet | Low-data complexity attacks on aes[END_REF] and ∆z 6 [START_REF] Demirci | A meet-in-the-middle attack on 8-round AES[END_REF] and compute the difference in the three first columns of x 7 . (b) Deduce the value of the three first columns of x 7 using ∆z 7 . (c) Deduce u 6 [0] and u 6 [7] using u 7 [START_REF] Biryukov | Distinguisher and related-key attack on the full aes-256[END_REF], u 7 [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF], u 7 [START_REF] Derbez | Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting[END_REF] and u 7 [START_REF]Advances in Cryptology -EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques[END_REF]. (d) Deduce z 6 [0] and z 6 [START_REF] Bouillaguet | Low-data complexity attacks on aes[END_REF] and compute ∆x 6 [0] and ∆x 6 [START_REF] Biryukov | Related-Key Cryptanalysis of the Full AES-192 and[END_REF]. (e) Check if the equation between ∆x 6 [0] and ∆x 6 [START_REF] Biryukov | Related-Key Cryptanalysis of the Full AES-192 and[END_REF] is satisfied. (f) Deduce ∆x 6 [START_REF] Biryukov | Key recovery attacks of practical complexity on aes-256 variants with up to 10 rounds[END_REF] and then compute x 6 [2] using ∆z 6 [START_REF] Demirci | A meet-in-the-middle attack on 8-round AES[END_REF]. (g) Guess ∆x 1 [START_REF] Biryukov | Automatic search for related-key differential characteristics in byte-oriented block ciphers: Application to aes, camellia, khazad and others[END_REF] and compute the difference in the second column of z 0 . (h) Deduce the value of the second column of z 0 using ∆x 0 . (i) Get the δ-set associated to one of the message of the pair and build the multiset from the corresponding ciphertexts. (j) Check whether the multiset exists in the hash table. If not, discard the key guess. 4. Restart with a new structure if no check found.

As each structure contains 2 63 pairs and each of these pairs follows the differential with probability 2 -144 , we need 2 81 structures on average. Then, for each structure we have to study only 2 63-32 = 2 31 pairs and for each of them we have to perform 2 24 × 2 8 partial encryptions that is equivalent to 2 28 encryptions. All in all, this leads to an attack with 2 113 chosen plaintexts, a time complexity equivalent to 2 140 encryptions and a memory requirement of 2 130 AES-blocks.

Reducing the data complexity. Note that for each possible choice of the active diagonal in the plaintext we found 96 attacks with the same complexity. As the corresponding differential paths are different it is possible to perform many attacks in parallel to save data in exchange of memory. For instance, if we use structure with three active diagonals, it is possible to reach a complexity of 2 104,83 chosen plaintexts and 2 138,17 AES-blocks, the time remaining unchanged.

Key Recovery. This attack can easily be turned into a key-recovery attack without increasing the complexity since only 9 key bytes are sufficient to recover the master key. AES-256. This attack can be applied to the AES-256 excepted that the keyschedule does not allow us to reduce the time complexity anymore. This leads to an attack with 2 113 chosen plaintexts, a time complexity equivalent to 2 156 encryptions and a memory requirement of 2 130 AES-blocks. For each possible choice of the active diagonal in the plaintext we found 384 attacks with the same complexity so it is possible to save more data than previously. For instance, if we use structure with three active diagonals, it is possible to reach a complexity of 2 102,83 chosen plaintexts and 2 140,17 AES-blocks, the time remaining unchanged.

Results

As in the previous section, we have exhausted the almost 2 16 variants to find the best attacks. Some of our results are summarized on Figures 12,[START_REF] Dunkelman | Improved Single-Key Attacks on 8-Round AES-192 and AES[END_REF] Limitations. To save more data, Dunkelman et al. propose to consider differential paths with a bigger probability. We have exhausted the simple case where the new differential paths do not have active new bytes in the middle rounds. However, we did not try interesting cases where the active bytes of the pair and bytes of B on and B of f are desynchronized since, besides the number of cases to handle, the complexity of our tweaked tool tends to explode as we cannot apply it to the keyschedule only.

Conclusion

We have presented new attacks on AES by generalizing Demirci and Selçuk meet-in-the-middle attacks. We took into account various time/memory tradeoffs including more advanced techniques introduced by Dunkelman et al. in [START_REF] Dunkelman | Improved Single-Key Attacks on 8-Round AES-192 and AES[END_REF]. We automatized the search of the best attacks of this kind using the tool developed by Bouillaguet et al. in [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF] solving linear systems of equations involving S-boxes. As a result, we recovered all best attacks on AES-128, including the recent one of Derbez et al. in [START_REF] Derbez | Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting[END_REF] and found new more efficient attacks for AES-192 and AES-256. Finally, applying the trade-off leads to an attack using 2 8 chosen plaintexts, with a time complexity equivalent to 2 170,34 encryptions and a memory requirement of 2 186 AES-blocks. If we allow more data it is possible to reach a complexity of 2 15,84 chosen plaintexts, 2 178,17 encryptions and 2 178,17 AES-blocks, to compare to the attack with 2 16 chosen plaintexts described Section 5.3. It can be easily turned into a key-recovery attack without increasing the complexity since only 12 key bytes are needed to recover the master key.

A.2 Attack on eight rounds AES-256 with 2 8 plaintexts

The best attack found with 2 8 chosen plaintexts is based on the attack depicted on Figure 16 which has a time complexity equivalent to 2 227 encryptions and a memory requirement of 2 241,34 AES-blocks. Indeed, since u 5 and u 6 are independent we may expect to reduce the number of possible values of B on by a factor 2 3×8 only, and this is reached by using the equations u 4 [START_REF] Bouillaguet | Low-data complexity attacks on aes[END_REF] = u 6 [3] + u 6 [START_REF] Bouillaguet | Low-data complexity attacks on aes[END_REF], u 4 [10] = u 6 [6] + u 6 [START_REF] Demirci | A meet-in-the-middle attack on 8-round AES[END_REF] and u 4 [START_REF] Dunkelman | Improved Single-Key Attacks on 8-Round AES-192 and AES[END_REF] = u 6 [9] + u 6 [START_REF] Dunkelman | Improved Single-Key Attacks on 8-Round AES-192 and AES[END_REF]. Finally, applying the trade-off leads to an attack using 2 8 chosen plaintexts, with a time complexity equivalent to 2 234,17 encryptions and a memory requirement of 2 234,17 AES-blocks. It can be easily turned into a key-recovery attack without increasing the complexity since only 4 key bytes are needed to recover the master key.

A.3 Attack on eight rounds AES-192 with 2 32 chosen plaintexts

The best attack found is based on the seven rounds attack described section A.1 extended by one round at the beginning. Thus the memory requirement remains the same as 2 193,34 AES-blocks. In another hand, we need to guess four more key bytes in the online phase and the keyschedule equations used have changed.

The bytes of B on are the entire state x 7 , the last column of x 6 and byte 1 of x 5 . However, the knowledge of u 7 allows to compute u 6 [0..7], u 5 [12..15] and k -1 [12..15], thanks to Property 3 and the key bridging technique. Thus the online phase can be performed as follows:

1. Ask for a structure of 2 32 chosen plaintexts such that bytes 0, 5, 10 and 15 assume the 2 32 possible values and the rest of the bytes are constant. 2. Guess the subkey u 7 and compute k -1 [START_REF]Advances in Cryptology -EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques[END_REF]. 3. Guess bytes 0, 5 and 10 of k -1 and then choose a δ-set. 4. Compute u 6 [START_REF] Biryukov | Related-Key Cryptanalysis of the Full AES-192 and[END_REF] and u 6 [START_REF] Bogdanov | Biclique Cryptanalysis of the Full AES[END_REF] and then partially decrypt the ciphertexts. 5. Guess u 6 [START_REF] Daemen | AES proposal: Rijndael[END_REF] and u 6 [START_REF] Derbez | Meet-in-the-middle and impossible differential fault analysis on aes[END_REF] and then partially decrypt the ciphertexts. 6. Compute u 5 [START_REF] Dunkelman | Improved Single-Key Attacks on 8-Round AES-192 and AES[END_REF] and then partially decrypt the ciphertexts to obtain ∆ i x 5 [START_REF] Daemen | AES proposal: Rijndael[END_REF] for 0 ≤ i ≤ 255. 7. Build the corresponding multiset and check whether it exists in the hash table. If not, discard the key guess.

All in all, the time complexity is equivalent to 2 × 2 8×25 × 2 -8×4 × 2 -6 × 2 8 = 2 171 encryptions and the memory requirement is 2 193,34 AES-blocks. Then we apply the data/time/memory trade-off to reach a complexity of 2 32 chosen plaintexts, 2 182,17 encryptions and 2 182,17 AESblocks. Finally, this attack can easily be turned into a key-recovery attack without increasing the complexity since only 8 key bytes are sufficient to recover the master key.

A.4 Attack on eight rounds AES-256 with 2 32 chosen plaintexts

The best attack found is the same as the 192-bit version. The only difference is that there is only one equation between the key bytes guessed during the online phase. Indeed, the only relation we have is u 5 [START_REF] Dunkelman | Improved Single-Key Attacks on 8-Round AES-192 and AES[END_REF] = u 7 [9] + u 7 [START_REF] Dunkelman | Improved Single-Key Attacks on 8-Round AES-192 and AES[END_REF]. Thus the time complexity of this attack is 2 195 encryptions and its memory requirement about 2 193,34 AES-blocks. Finally, this attack can be easily turned into a key-recovery attack without increasing the complexity since only 12 key bytes are sufficient to recover the master key.

  applies MC • SR • SB • AK to the state.

Figure 1 :

 1 Figure 1: Description of one AES round and the ordering of bytes in an internal state.

Figure 2 :

 2 Figure 2: Key schedules of the variants of the AES: AES-128, AES-192 and AES-256.

Property 2 (

 2 MixColumns property). Consider a pair (a, b) of 4-byte vectors, such that a = M C(b), i.e. the input and the output of a MixColumns operation applied to one column. Denote a = (a 0 , a 1 , a 2 , a 3 ) and b = (b 0 , b 1 , b 2 , b 3 ) where a i and b j are elements of F 256 . Then there is no equation involving less than five bytes and for each choice of five bytes among the eight bytes (a 0 , a 1 , a 2 , a 3 , b 0 , b 1 , b 2 , b 3 ) there is a linear equation between them.

Figure 3 :

 3 Figure 3: 4 AES-rounds. The 25 black bytes are the parameters of Property 5. Hatched bytes play no role. The differences are null in white squares

  Multiset. Note that, given a sequence of 256 bytes b 0 , . . . , b 255 , b i = b j implies that the multisets [b i + b 0 , . . . , b i + b 255 ] and [b j + b 0 , . . . , b j + b 255 ] are equal too. But Dunkelman et al. shown that given a random function f : F 256 -→ F 256 , the multiset [f (0)+f (

Figure 8 :

 8 Figure 8: Attack on 6 AES rounds. Bytes of B of f are in black. Bytes of Bon are in gray. Hatched bytes play no role. The differences are null in white squares

Figure 9 :

 9 Figure 9: Attack on 7 AES rounds (key length : 256 bits). Bytes of B of f are in black. Bytes of Bon are in gray. Hatched bytes play no role. The differences are null in white squares

Figure 10 :

 10 Figure 10: Attack on 7 AES rounds (key length : 192 bits). Bytes of B of f are in black. Bytes of Bon are in gray. Hatched bytes play no role. The differences are null in white squares

Figure 11 :

 11 Figure 11: Attack on 8 AES rounds. Bytes of B of f are in black. Bytes of Bon are in gray. Hatched bytes play no role. The differences are null in white squares

Figure 12 :

 12 Figure12: Differential characteristic on 8 AES rounds. The differences are null in white squares. The value of bytes of B of f can be derived from the differences in circled bytes.

  and 14. As expected we have automatically rediscovered the attacks found by Dunkelman et al. and the ones found by Derbez et al., but we have also obtained many new attacks including the best known attacks on 8 rounds for both AES-192 and AES-256 described Section 6.1. number of guess in the offline phase last mixcolumn performed number of guess in the online phase

Figure 13 :

 13 Figure 13: Differential Enumeration: results on 7 rounds AES-128. All attacks have a data complexity of 2 113 chosen plaintexts. Numbers in cells are the log 2 of the numbers of attacks found with the same complexity.

Figure 15 :

 15 Figure 15: Differential Enumeration: results on 9 rounds AES-256. All attacks have a data complexity of 2 113 chosen plaintexts. Numbers in cells are the log 2 of the numbers of attacks found with the same complexity.

Figure 17 :

 17 Figure 17: Attack on 8 AES rounds. Bytes of B of f are in black. Bytes of Bon are in gray. Hatched bytes play no role. The differences are null in white squares

  ii) the knowledge of u r+1[4..7] and u r+1[8..11] allows to compute u r [0..3] • AES-256 : 1) u r [4..7] = u r+2 [0..3] + u r+2 [4..7], 2) u r [8..11] = u r+2 [4..7] + u r+2 [8..11], 3) u r [12..15] = u r+2 [8..11] + u r+2 [12..15].

11] = u r+1 [4..7] + u r+1 [8..11] 3) u r [12..15] = u r+1 [8..11] + u r+1 [12..15] • AES-192 : 1) u r [4..7] = u r+1 [8..11] + u r+1 [12..15] 2) u r [12..15] = u r+2 [0..3] + u r+2 [4..7] 3) if r is even: i) u r [0..3] = u r+1 [4..7] + u r+1 [8..11] ii) the knowledge of u r+1 [12..15] and u r+2 [0..3] allows to compute u r [8..11] 4) if r is odd: i) u r [8..11] = u r+1 [12..15] + u r+2 [0..3]

•

  Online phase: 1. Ask for a structure of 2 32 chosen plaintexts such that the main diagonal can take the 232 possible values and the remaining bytes are constant. 2. Choose one plaintext and guess the first column of its intermediate state z 0 and bytez 1 [0]. 3.For each of the 255 non-zero values of ∆z 1 compute the corresponding difference in the plaintext using the guessed bytes. 4. Order the obtained δ-set according to the value of the state byte z 1 [0]. 5. Guess the first column of x 6 and the byte x 5 [0] for one of the message and deduce those state bytes for the 256 ciphertexts. 6. Build the sequence and check whether it exists in the hash table. If not, discard the guess. Online phase of Demirci and Selçuk attack. Bon is composed by gray and black bytes. Gray bytes are used to identify a δ-set and to order it. Black bytes are used to build the sequence from ciphertexts. Hatched bytes play no role. The differences are null in white squares.

	x0	z0	x1	z1	x5	z5	x6	z6
	P			4 rounds				C
	Figure 4:

  Figure 14: Differential Enumeration: results on 8 rounds AES-192. All attacks have a data complexity of 2 113 chosen plaintexts. Numbers in cells are the log 2 of the numbers of attacks found with the same complexity.

					number of guess in the offline phase
			10 11 12 13 14 15 16 17 18 19 20 21 22
		12					6.0				number of guess in the offline phase
	number of guess in the online phase	13 14 15 16 17 18 19 20 21 22 23	6.6 8.0 7.3 10.8 13.4	8.6 9.6 10.7 10.5 4.2 7.7 13.3 10.0 5.2 6.5 10.9 8.4 3.3 4.3 12.2 11.9	7.0 10.9 9.9 9.2 9.9 6.6 7.6 11.0 6.6 7.6 11.0 7.6 10.2 13.6 6.2 8.0 8.5 8.5 7.6 8.6 10.0 8.5 6.9 6.9 10.1 8.0	number of guess in the online phase	14 15 16 17 18 19 20 21 22 23	10 11 12 13 14 15 16 17 18 19 20 21 22 11.1 9.9 9.2 9.9 6.2 7.2 10.6 8.6 8.3 10.4 13.9 10.3 10.5 6.2 8.0 8.5 8.5 4.2 7.7 13.4 10.0 7.6 8.6 10.0 8.5 6.6 8.0 5.2 6.5 10.9 8.4 6.9 6.9 10.1 7.3 11.0 3.3 4.3 12.2 8.0 13.3 11.9
					last mixcolumn performed				last mixcolumn omitted
					number of guess in the offline phase				number of guess in the offline phase
					21 22 23 24 25 26 27 28 29 30 31				21 22 23 24 25 26 27 28 29 30 31
				19			9.5 10.3			19	9.5 10.3
		number of guess in the online phase	20 21 22 23 24 25 26 27 28 29 30	9.8 7.6 10.1 8.3 9.9 13.3	8.0 7.6 6.0 14.2 12.2 12.2 12.5	9.6 9.6 9.6 10.4 7.6 7.6 7.0 7.0 8.6 8.6	number of guess in the online phase	20 21 22 23 24 25 26 27 28 29 30	9.8 7.6 10.1 11.9 9.9 12.7	8.0 11.2 6.0 14.0 12.2 12.2 12.5	9.6 9.6 9.6 10.4 7.6 7.6 7.0 7.0 8.6 8.6
				31	6.8 12.9	11.8				31	6.8 12.9	11.8
						last mixcolumn performed				last mixcolumn omitted

Table 1 :

 1 Current cryptanalysis of (reduced-round) AES variants in the single-key model. .1 Attack on seven rounds AES-256 with 2 8 chosen plaintextsThe best attack found with 2 8 chosen plaintexts is based on the attack depicted on Figure15which has a time complexity equivalent to 2 163 encryptions and a memory requirement of 2 193,34 AES-blocks. Indeed, since u 5 and u 6 are independent we may expect to reduce the number of possible values of B on by a factor 2 8 only, and this is done by using the equation u 4[START_REF] Dunkelman | Improved Single-Key Attacks on 8-Round AES-192 and AES[END_REF] = u 6 [9] + u 6[START_REF] Dunkelman | Improved Single-Key Attacks on 8-Round AES-192 and AES[END_REF]. Attack on 7 AES rounds (key length : 256 bits). Bytes of B of f are in black. Bytes of Bon are in gray. Hatched bytes play no role. The differences are null in white squares

	Target	Rounds	Data (CP)	Memory	Time	Technique	Reference
		6	2 8	2 106.17	2 106.17	MITM	Section 5.2
		7	2 90.4	2 106	2 117.2 MA	Impossible Diff.	[18]
	AES-128	7 7	2 116 2 97	2 116 2 98	2 116 2 99	MITM MITM	[13] [11]
		7	2 32	2 126.47	2 126.47	MITM	Full version
		8	2 88	2 8	2 125.3	Bicliques	[6]
		10 (full)	2 88	2 8	2 126.2	Bicliques	[6]
		6	2 8	2 109.67	2 109.67	MITM	Full version
		7	2 116	2 116	2 116	MITM	[13]
		7	2 97	2 98	2 99	MITM	[11]
		7	19 • 2 32	19 • 2 32	2 155	Square	[14]
		7	2 95	2 143	2 143	MITM	[10]
	AES-192	7 7	2 91.2 2 8	2 139.2 2 153.34	2 101 2 163	Impossible Diff. MITM	[17] Full version
		7	2 32	2 129.67	2 129.67	MITM	Section 5.4
		8	2 41	2 186	2 187.63	MITM	[20]
		8	2 113	2 129	2 172	MITM	[13]
		8	2 113	2 82	2 172	MITM	[11]
		8	2 113	2 130	2 140	MITM	Section 6.1
		8	2 107	2 96	2 172	MITM	[11]
		8	2 104.83	2 138.17	2 140	MITM	Section 6.1
		8	2 32	2 182.17	2 182.17	MITM	Section A.3
		9	2 80	2 8	2 188.8	Bicliques	[6]
		12 (full)	2 80	2 8	2 189.4	Bicliques	[6]
		6	2 8	2 114.34	2 122	MITM	Full version
		7	21 • 2 32	21 • 2 32	2 172	Square	[14]
		7	2 95	2 143	2 143	MITM	[10]
		7	2 116	2 116	2 116	MITM	[13]
		7	2 97	2 98	2 99	MITM	[11]
		7	2 8	2 186	2 170.34	MITM	Section A.1
	AES-256	7	2 16	2 153.34	2 178	MITM	Section 5.3
		7	2 32	2 133.67	2 133.67	MITM	Full version
		8	2 34.2	2 205.8	2 205.8	MITM	[10]
		8	2 113	2 129	2 196	MITM	[13]
		8	2 113	2 82	2 196	MITM	[11]
		8	2 113	2 130	2 156	MITM	Section 6.1
		8	2 107	2 96	2 196	MITM	[11]
		8	2 102.83	2 140.17	2 156	MITM	Section 6.1
		8	2 8	2 234.17	2 234.17	MITM	Section A.2
		8	2 32	2 193.34	2 195	MITM	Section A.4
		9	2 120	2 8	2 251.9	Bicliques	[6]
		9	2 120	2 203	2 203	MITM	[11]
		9	2 32	2 254.17	2 254.17	MITM	Full version
		14 (full)	2 40	2 8	2 254.4	Bicliques	[6]
	CP: Chosen-plaintext
	MA: Memory Accesses
	Time complexity measures the online time in encryption units unless mentioned otherwise.
	Memory complexity is measured in AES blocks.

A

A More optimal attacks

In this section we describe some attacks minimizing the maximum between the time complexity (counted in AES encryption) and the memory complexity (counted in 128-bit block). For each of them we assume that the last MixColumns is performed.