Jiqiang Lu
email: lvjiqiang@hotmail.com

Yongzhuang ⋆⋆

Wei

Enes Pasalic
email: enes.pasalic6@gmail.com

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

Meet-in-the-Middle Attack on Reduced Versions of the Camellia Block Cipher ⋆

Keywords: Block cipher, Camellia, Meet-in-the-middle attack

The Camellia block cipher has a 128-bit block length and a user key of 128, 192 or 256 bits long, which employs a total of 18 rounds for a 128-bit key and 24 rounds for a 192 or 256-bit key. It is a Japanese CRYPTREC-recommended e-government cipher, a European NESSIE selected cipher, and an ISO international standard. In this paper, we describe a few 5 and 6-round properties of Camellia and finally use them to give meet-in-the-middle attacks on 10-round Camellia under 128 key bits, 11-round Camellia under 192 key bits and 12-round Camellia under 256 key bits, all of which include the FL/FL -1 functions but do not include whitening operations.

Introduction

Camellia [START_REF] Aoki | Camellia: a 128-bit block cipher suitable for multiple platforms -design and analysis[END_REF] is a 128-bit block cipher with a user key length of 128, 192 or 256 bits, which employs a total of 18 rounds if a 128-bit key is used and a total of 24 rounds if a 192/256-bit key is used. It has a Feistel structure with keydependent logical functions FL/FL -1 inserted after every six rounds, plus four additional whitening operations at both ends. Camellia became a CRYPTREC egovernment recommended cipher [7] in 2002, a NESSIE selected block cipher [START_REF]NESSIE -New European Schemes for Signatures, Integrity, and Encryption[END_REF] in 2003, and was adopted as an ISO international standard [16] in 2005. In this work, we consider the version of Camellia that has the FL/FL -1 functions, and for simplicity, we denote by Camellia-128/192/256 the three versions of Camellia that use 128, 192 and 256 key bits, respectively.

The security of Camellia has been analysed against a variety of cryptanalytic techniques, including differential cryptanalysis [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF], truncated differential cryptanalysis [START_REF] Knudsen | Truncated and higher order differentials[END_REF], higher-order differential cryptanalysis [START_REF] Knudsen | Truncated and higher order differentials[END_REF][START_REF] Lai | Higher order derivatives and differential cryptanalysis[END_REF], linear cryptanalysis [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF], integral cryptanalysis [START_REF] Daemen | The block cipher Square[END_REF][START_REF] Hu | Integral cryptanalysis of SAFER+[END_REF][START_REF] Knudsen | Integral cryptanalysis[END_REF], boomerang attack [START_REF] Wagner | The boomerang attack[END_REF], rectangle attack [START_REF] Biham | The rectangle attack -rectangling the Serpent[END_REF], collision attack and impossible differential cryptanalysis [START_REF] Biham | Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials[END_REF][START_REF] Knudsen | DEAL -a 128-bit block cipher[END_REF]; and many cryptanalytic results on Camellia have been published [2, 6, 11-13, 21-24, 27-29, 31, 32], of which impossible differential cryptanalysis is the most efficient technique in terms of the numbers of attacked rounds, that broke 11round Camellia-128, 12-round Camellia-192 and 14-round Camellia-256 [START_REF] Bai | New impossible differential attacks on Camellia[END_REF][START_REF] Liu | New observations on impossible differential cryptanalysis of reduced-round Camellia[END_REF], presented most recently at FSE 2012 and ISPEC 2012. 1 The meet-in-the-middle (MitM) attack was introduced in 1977 by Diffie and Hellman [START_REF] Diffie | Exhaustive cryptanalysis of the NBS data encryption standard[END_REF]. It usually treats a block cipher E : {0, 1} n × {0, 1} k → {0, 1} n as a cascade of two sub-ciphers E = E a • E b . Given a guess for the subkeys used in E a and E b , if a plaintext produces just after E a the same value as the corresponding ciphertext produces just before E b , then this guess for the subkeys is likely to be correct; otherwise, this guess must be incorrect. Thus, we can find the correct subkey, given a sufficient number of matching plaintext-ciphertext pairs in a known-plaintext attack scenario. In a chosen-plaintext attack scenario, things may get better, and as in [START_REF] Demirci | A meet-in-the-middle attack on 8-round AES[END_REF], by choosing a set of plaintexts with a particular property we may be able to express the concerned value-in-the-middle as a function of plaintext and a smaller number of unknown constants than the number of unknown constants (of the same length) from the subkey involved.

In 2011 Lu et al. [START_REF] Lu | The higher-order meet-in-the-middle attack and its application to the Camellia block cipher[END_REF] proposed an extension of the MitM attack, known as the higher-order MitM (HO-MitM) attack, which is based on using multiple plaintexts to cancel some key-dependent component(s) or parameter(s) when constructing a basic unit of "value-in-the-middle". The HO-MitM attack technique can lead to some better cryptanalytic results than the MitM attack technique in certain circumstances. In particular, Lu et al. found some 5 and 6-round HO-MitM properties of Camellia that were used to break 10-round Camellia-128, 11-round Camellia-192 and 12-round Camellia-256, but the corresponding 5 and 6-round MitM properties can enable us to break only 12-round Camellia-256.

In this paper, we analyse the security of Camellia (with the FL/FL -1 functions) against the MitM attack in detail, following the work in [START_REF] Lu | The higher-order meet-in-the-middle attack and its application to the Camellia block cipher[END_REF]. In all those 5 and 6-round (higher-order) MitM properties of Camellia due to Lu et al. [START_REF] Lu | The higher-order meet-in-the-middle attack and its application to the Camellia block cipher[END_REF], the basic unit of value-in-the-middle is one byte long. Nevertheless, we observe that if we consider only a smaller number of bits of the concerned byte, instead of the whole 8 bits, a few 5 and 6-round MitM properties with a smaller number of unknown 1-bit constant parameters can be obtained. This is due to the fact that an output bit of the FL -1 function only relies on a small fraction of the bits of the subkey used in the FL -1 function (as well as a few input bits to FL -1 ), thus reducing the number of unknown 1-bit constant parameters when we consider a fraction of the bits of the concerned byte. As a consequence, the 5 and 6-round MitM properties can be used to conduct MitM attacks on 10-round Camellia-128, 11-round Camellia-192 and 12-round Camellia-256, (all of which include the FL/FL -1 functions). Table 1 summarises previous, our and the newly emerging main cryptanalytic results on Camellia (with FL/FL -1 functions), where CP, ACPC and CC refer respectively to the numbers of chosen plaintexts, adap-tively chosen plaintexts and ciphertexts, and chosen ciphertexts, Enc. refers to the required number of encryption operations of the relevant reduced version of Camellia, and MA refers to the required numbers of memory accesses.

The remainder of the paper is organised as follows. In the next section, we describe the notation and the Camellia block cipher. We give the 5 and 6-round MitM properties in Section 3, and present our cryptanalytic results on Camellia-128/192/256 in Sections 4-6, respectively. Concluding remarks are given in Section 7.

Preliminaries

In this section we give the notation used throughout this paper, and then briefly describe the Camellia block cipher.

Notation

The bits of a value are numbered from left to right, starting with 1. We use the following notation throughout this paper.

⊕

P =       1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 1 0 0 0 1 1 1 0 1 1 0 1 0 1 1 0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 0       , P -1 =       0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1 0 1 1 1       . -F : {0, 1} 64 × {0, 1} 64 → {0, 1} 64 is a Feistel function. If X and Y are 64-bit blocks, F(X, Y ) = P(S(X ⊕ Y )). -FL/FL -1 : {0, 1} 64 ×{0, 1} 64 → {0, 1} 64 are key-dependent linear functions. If X = (X L ||X R ) and Y = (Y L ||Y R ) are 64-bit blocks, then FL(X, Y ) = ((((X L ∩ Y L ) ≪ 1 ⊕ X R ) ∪ Y R ) ⊕ X L )||((X L ∩ Y L ) ≪ 1 ⊕ X R ), and FL -1 (X, Y ) = (X L ⊕ (X R ∪ Y R ))||(((X L ⊕ (X R ∪ Y R )) ∩ Y L ) ≪ 1 ⊕ X R ).
Camellia uses a total of four 64-bit whitening subkeys KW j , 2⌊ Nr-6 6 ⌋ 64bit subkeys KI l for the FL and FL -1 functions, and N r 64-bit round subkeys

K i , (1 j 4, 1 l 2⌊ Nr-6 6 ⌋, 1 i N r
), all derived from a N k -bit key K, where N r is 18 for Camellia-128, and 24 for Camellia-192/256, N k is 128 for Camellia-128, 192 for Camellia-192, and 256 for Camellia-256. The key schedule is as follows. First, generate two 128-bit strings K L and K R from K in the following way: For Camellia-128, K L is the 128-bit key K, and K R is zero; for Camellia-192, K L is the left 128 bits of K, and K R is the concatenation of the right 64 bits of K and the complement of the right 64 bits of K; and for Camellia-256, K L is the left 128 bits of K, and K R is the right 128 bits of K. Second, depending on the key size, generate one or two 128-bit strings K A and K B from (K L , K R ) by a non-linear transformation (see [START_REF] Aoki | Camellia: a 128-bit block cipher suitable for multiple platforms -design and analysis[END_REF] for its detail). Finally, the subkeys are as follows.2 -For Camellia-128:

K 2 = (K A ≪ 0)[65 ∼ 128], K 3 = (K L ≪ 15)[1 ∼ 64], K 9 = (K A ≪ 45)[1 ∼ 64], K 10 = (K L ≪ 60)[65 ∼ 128], K 11 = (K A ≪ 60)[1 ∼ 64], • • •. -For Camellia-192/256: K 7 = (K B ≪ 30)[1 ∼ 64], K 8 = (K B ≪ 30)[65 ∼ 128], K 13 = (K R ≪ 60)[1 ∼ 64], K 14 = (K R ≪ 60)[65 ∼ 128], K 15 = (K B ≪ 60)[1 ∼ 64], K 16 = (K B ≪ 60)[65 ∼ 128], K 17 = (K L ≪ 77)[1 ∼ 64], K 18 = (K L ≪ 77)[65 ∼ 128], K 21 = (K A ≪ 94)[1 ∼ 64], K 22 = (K A ≪ 94)[65 ∼ 128], K 23 = (K L ≪ 111)[1 ∼ 64], • • •.
Below is the encryption procedure Camellia, where P is a 128-bit plaintext, represented as 16 bytes, and L 0 , R 0 , L i , R i , L i and R i are 64-bit variables.

1. L 0 ||R 0 = P ⊕ (KW 1 ||KW 2 ) 2. For i = 1 to N r : if i = 6 or 12 (or 18 for Camellia-192/256), L i = F(L i-1 , K i ) ⊕ R i-1 , R i = L i-1 ; L i = FL( L i , KI i 3 -1 ), R i = FL -1 ( R i , KI i 3 ); else L i = F(L i-1 , K i ) ⊕ R i-1 , R i = L i-1 ; 3. Ciphertext C = (R Nr ⊕ KW 3 )||(L Nr ⊕ KW 4 ).
We refer to the ith iteration of Step 2 in the above description as Round i, and write K i,j for the j-th byte of

K i , (1 j 8). ⊕ ⊕ ⊕ X (i) L X (i) R ⊕ ⊕ ⊕ P S ⊕ K4 Z (i) L Z (i) R FL FL -1 Y (i) 4 W (i) 4
L (i) 3
L (i) 7
L (i) 6
L (i) 6
L (i) 5
L (i) 4
R (i) 6 R (i) 4 R (i) 5
R (i) 7 R (i) 3 R (i) 6 P S ⊕ K5 Y (i) 5 W (i) 5 P S ⊕ K6 Y (i) 6 W (i) 6 P S ⊕ K7 Y (i) 7 W (i) 7 P S ⊕ K8 Y (i) 8 W (i) 8 P S ⊕ K3 Y (i) 3 W (i) 3
5 rounds: 6 rounds:

Properties for 5 and 6-Round Camellia

We assume the 5-round Camellia is from Rounds 4 to 8 (including the FL/FL -1 functions between Rounds 6 and 7), and the 6-round Camellia is from Rounds 3 to 8; see Fig. 1. These properties are given below, and their proof is given in the Appendix.

Proposition 1. Suppose a set of 256 sixteen-byte values

X (i) = (X (i) L ||X (i) R ) = (m 1 , m 2 , m 3 , m 4 , m 5 , m 6 , m 7 , m 8 , x (i) , m 9 ,
(i = 1, • • • , 256). Then: 1. If Z (i) = (Z (i) L ||Z (i) R
) is the result of encrypting X (i) using Rounds 4 to 8 with the FL/FL -1 functions between Rounds 6 and 7, then

P -1 (Z (i) R )[49 ∼ (49 + ω)] can be expressed with a function of x (i) and 100 + 15 × ω constant 1-bit parameters c 1 , c 2 , • • • , c 100+15×ω , written Θ c1,c2,•••,c100+15×ω (x (i) )
, where 0 ω 6.

If Z

(i) = (Z (i) L ||Z (i) R
) is the result of encrypting X (i) using Rounds 3 to 8 with the FL/FL -1 functions between Rounds 6 and 7, then P -1 (Z

(i) R )[41 ∼ (41 + ω)] can be expressed with a function of x (i) and 164 + 15 × ω constant 1-bit parameters c ′ 1 , c ′ 2 , • • • , c ′ 164+15×ω , written Υ c ′ 1 ,c ′ 2 ,•••,c ′ 164+15×ω (x (i) )
, where 0 ω 6.

Note that it can be seen from the proof that several 1-bit constants can be cancelled if we take XOR under two different inputs, but such a resulting attack is termed a HO-MitM attack [START_REF] Lu | The higher-order meet-in-the-middle attack and its application to the Camellia block cipher[END_REF], which has a slightly different tradeoff on data/time/memory compared with our attack given below, mostly on memory.

Attacking 10-Round Camellia-128

A simple analysis on the key schedule of Camellia-128 reveals the following property.

Property 1 For Camellia-128, given a value of (K 2,1 , K 2,2 , K 2,3 , K 2,5 , K 2,8 , K 3,1 ) there are only 60 unknown bits of (K 9,7 , K 10,3 , K 10,4 , K 10,5 , K 10,6 , K 10,8 , K 11 ).

The 5-round property given in Proposition 1-1 can enable us to break 10round Camellia-128 with FL/FL -1 functions. Below is the procedure for attacking Rounds 2 to 11, where the 5-round property with ω = 0 is used from Rounds 4 to 8, and the approach used to choose plaintexts with δ was introduced in [START_REF] Lu | Cryptanalysis of reduced versions of the Camellia block cipher[END_REF].

1. For each of 2 100 possible values of the 100 one-bit parameters

c 1 , c 2 , • • • , c 100 , precompute Θ c1,c2,•••,c100 (z) sequentially for z = 0, 1, • • • ,
δ = γ 4 ⊕ γ 5 ⊕ γ 6 ⊕ S 4 (γ 1 ⊕ K 2,4 ) ⊕ S 6 (γ 2 ⊕ K 2,6 ) ⊕ S 7 (γ 3 ⊕ K 2,7 ).
3. Guess a value for (K 2,1 , K 2,2 , K 2,3 , K 2,5 , K 2,8 , K 3,1 , δ), and we denote the guessed value by

(K * 2,1 , K * 2,2 , K * 2,3 , K * 2,5 , K * 2,8 , K * 3,1 , δ * ). Then for x = 0, 1, • • • , 255, choose plaintext P (x) = (P (x) L , P (x) R ) in the following way (x = 0, 1, • • • , 255), where α 1 , α 2 , • • • , α 5 , β 1 , β 2 , • • • , β 7 are randomly chosen 8-bit constants: P (x) L =        S1(x ⊕ K * 3,1 ) ⊕ α1 S1(x ⊕ K * 3,1 ) ⊕ α2 S1(x ⊕ K * 3,1 ) ⊕ α3 γ1 S1(x ⊕ K * 3,1 ) ⊕ α4 γ2 γ3 S1(x ⊕ K * 3,1 ) ⊕ α5        T , P (x) R = P        S1(S1(x ⊕ K * 3,1 ) ⊕ α1 ⊕ K * 2,1 ) S2(S1(x ⊕ K * 3,1 ) ⊕ α2 ⊕ K * 2,2 ) S3(S1(x ⊕ K * 3,1 ) ⊕ α3 ⊕ K * 2,3 ) γ4 S5(S1(x ⊕ K * 3,1 ) ⊕ α4 ⊕ K * 2,5 ) γ5 γ6 S8(S1(x ⊕ K * 3,1 ) ⊕ α5 ⊕ K * 2,8 )        T ⊕       x ⊕ δ * β1 β2 β3 β4 β5 β6 β7       T .
In a chosen-plaintext attack scenario, obtain the ciphertexts for the plaintexts; we denote by C (x) the ciphertext for plaintext P (x) . 4. Guess a value for (K 9,7 , K 10,3 , K 10,4 , K 10,5 , K

T (x) = P -1 (L (x) 9 )[49] ⊕ S 7 (R (x) 9,7 ⊕ K * 9,7 )[49].
Finally, check whether the sequence (T (0) , T (1)

(0) , • • • , T (255) ) matches a sequence in L Θ is 1- ( 2 100 0 ) (2 -256 ) 0 (1- 2 -256 ) 2 100 ≈ 2 -256 × 2 100 = 2 -156
, (assuming the event has a binomial distribution). Consequently, it is expected that at most 2 56+60 × 2 -156 = 2 -40 values for (K 2,1 , K 2,2 , K 2,3 , K 2,5 , K 2,8 , K 3,1 , K 9,7 , K 10,3 , K 10,4 , K 10,5 , K 10,6 , K 10,8 , K 11 ) are recorded in Step 4. Since a total of 40 bits of K L can be known from (K 10,3 , K 10,4 , K 10,5 , K 10,6 , K 10,8 ), Step 5 takes at most 2 88 10-round Camellia-128 encryptions to find the correct 128-bit user key.

Therefore, the attack has a memory complexity of 2 105 bytes and a total time complexity of approximately 2 121.5 10-round Camellia-128 encryptions.

Note that we can also attack Rounds 8 to 17 by applying the 5-round property with ω = 0 from Rounds 10 to 14, where we guess (K 8,1 , K 8,2 , K 8,3 , K 8,5 , K 8,8 , K 9,1 , K 15,7 , K 16,3 , K 16,4 , K 16,5 , K 16,6 , K 16,8 , K 17 ), plus a secret 8-bit parameter δ (which has a similar meaning as the δ defined above). Similarly, the attack has the same data and memory complexity as the above 10-round Camellia-128 attack, but a total time complexity of approximately 2 56+65 × 256 × 8+5+1 8×10 ≈ 2 126.5 10-round Camellia-128 encryptions.

Attacking 11-Round Camellia-192

Both the 5 and 6-round properties given in Proposition 1 can be used to attack 11-round Camellia-192 with FL/FL -1 functions. We first describe such an attack based on the 5-round property. The following property holds for Camellia-192.

Property 2 For Camellia-192, there is no overlapping bit between (K 13 , K 14 , K 15,1 ) and (K 21,7 , K 22,3 , K 22,4 , K 22,5 , K 22,6 , K 22,8 , K 23 ).

Then we can give the following procedure for attacking Rounds 13 to 23 of Camellia-192 with FL/FL -1 functions, where we choose where we choose ω = 0.

1. For each of 2 100 possible values of the 100 one-bit parameters

c 1 , c 2 , • • • , c 100 , precompute Θ c1,c2,•••,c100 (z) sequentially for z = 0, 1, • • • ,
P (x) L = P        S1(S1(x ⊕ K * 15,1 ) ⊕ α1 ⊕ K * 14,1 ) S2(S1(x ⊕ K * 15,1 ) ⊕ α2 ⊕ K * 14,2 ) S3(S1(x ⊕ K * 15,1 ) ⊕ α3 ⊕ K * 14,3 ) S4(α4 ⊕ K * 14,4 ) S5(S1(x ⊕ K * 15,1 ) ⊕ α5 ⊕ K * 14,5 ) S6(α6 ⊕ K * 14,6 ) S7(α7 ⊕ K * 14,7 ) S8(S1(x ⊕ K * 15,1 ) ⊕ α8 ⊕ K * 14,8 )        T ⊕       x β1 β2 β3 β4 β5 β6 β7       T . P (x) R = F(P (x) L , K * 13 ) ⊕        S1(x ⊕ K * 15,1 ) ⊕ α1 S1(x ⊕ K * 15,1 ) ⊕ α2 S1(x ⊕ K * 15,1 ) ⊕ α3 α4 S1(x ⊕ K * 15,1 ) ⊕ α5 α6 α7 S1(x ⊕ K * 15,1 ) ⊕ α8        T ,
In a chosen-plaintext attack scenario, obtain the ciphertexts for the plaintexts; we denote by C (x) the ciphertext for plaintext P (x) . 3. Guess a value for (K

T (x) = P -1 (L (x) 21 )[49] ⊕ S 6 (R (x) 21,7 ⊕ K * 21,7 )[49].
Finally, check whether the sequence (T (0) , T (1) ) is correct, the sequence (T (0) , T (1) , • • • , T (255) ) must match a sequence in L Θ ; for a wrong guess of (K 13 , K 14 , K 15,1 , K 21,7 , K 22,3 , K 22,4 , K 22,5 , K 22,6 , K 22,8 , K 23 ), the probability that the sequence (T (0) , • • • , T (255) ) matches a sequence in L Θ is approximately 1-

( 2 100 0 ) (2 -256 ) 0 (1-2 -256
) 2 100 ≈ 2 -256 ×2 100 = 2 -156 , (assuming the event has a binomial distribution). Consequently, it is expected that about 2 72+112 ×2 -156 = 2 28 values for (K 13 , K 14 , K 15,1 , K 21,7 , K 22,3 , K 22,4 , K 22,5 , K 22,6 , K 22,8 , K 23 ) are recorded in Step 3. Since 64 bits of K L can be known from K 23 and K R can be known from K 13 , Step 4 takes at most 2 64 × 2 28 = 2 92 11-round Camellia-192 encryptions.

Therefore, the attack has a memory complexity of 2 105 bytes, and has a total time complexity of 2 189. 4 11-round Camellia-192 encryptions.

Next, we briefly describe a 11-round Camellia-192 attack based on that 6round property, where we choose ω = 0. We attack Rounds 13 to 23, and the attack procedure is similar to the 12-round Camellia-256 attack presented in Section 6, except the following two points: (1) There are 164 one-bit parameters

c ′ 1 , c ′ 2 , • • • , c ′
164 in the off-line precomputation phase; and (2) We append only three rounds (i.e., Rounds 21 to 23) after the 6-round property. There are only 2 40 possible values for (K 13,1 , K 13,2 , K 13,3 , K 13,5 , K 13,8 , K 14,1 ). After a similar analysis, we get that the off-line precomputation requires a memory of 2 We can obtain a data-memory-time tradeoff [START_REF] Hellman | A cryptanalytic time-memory trade-off[END_REF] version from this 11-round Camellia-192 attack, which has a data complexity of 2 59.4 chosen plaintexts, a memory complexity of 2 167.6 bytes and a total time complexity of 2 169.8 11-round Camellia-192 encryptions.

Attacking 12-Round Camellia-256

We have the following property for Camellia-256.

Property 3 For Camellia-256, given a value for (K 7,1 , K 7,2 , K 7,3 , K 7,5 , K 7,8 , K 8,1 ) there are only 158 unknown bits for (K 15,6 , K 16,2 , K 16,3 , K 16,5 , K 16,7 , K 16,8 , K 17 , K 18 ).

We can use the 6-round property given in Proposition 1-2 to mount an attack on 12-round Camellia-256 with FL/FL -1 functions. We attack Rounds 7 to 18, and use the property with ω = 1. The attack procedure is as follows.

1. For each of 2 179 possible values of the 179 one-bit parameters

c ′ 1 , c ′ 2 , • • • , c ′ 179 , precompute Υ c ′ 1 ,c ′ 2 ,•••,c ′ 179 (z) sequentially for z = 0, 1
δ = γ 4 ⊕ γ 5 ⊕ γ 6 ⊕ S 4 (γ 1 ⊕ K 7,4 ) ⊕ S 6 (γ 2 ⊕ K 7,6 ) ⊕ S 7 (γ 3 ⊕ K 7,7 ).
3. Guess a value for (K 7,1 , K 7,2 , K 7,3 , K 7,5 , K 7,8 , K

T (x) = P -1 (L (x) 15 )[41 ∼ 42] ⊕ S 6 (R (x) 15,6 ⊕ K * 15,6 )[41 ∼ 42].
Finally, check whether the sequence (T (0) , T (1) ), the sequence (T (0) , T (1) , • • • , T (255) ) must match a sequence in L Υ ; for a wrong guess of (K 7,1 , K 7,2 , K 7,3 , K 7,5 , K 7,8 , K 8,1 , δ, K 15,6 , K 16,2 , K 16,3 , K 16,5 , K 16,7 , K 16,8 , K 17 , K 18 ), the probability that the sequence (T (0) , T (1)

, • • • , T (255) ) matches a sequence in L Υ is approximately 1 - ( 2 179 0 ) (2 -512 ) 0 (1-2 -512 ) 2 179 ≈ 2 -512 ×2 179 = 2 -333
, (assuming the event has a binomial distribution). Consequently, it is expected that at most 2 56+158 ×2 -333 = 2 -119 values for (K 7,1 , K 7,2 , K 7,3 , K 7,5 , K 7,8 , K 8,1 , K 15,6 , K 16,2 , K 16,3 , K 16,5 , K 16,7 , K 16,8 , K 17 , K 18 ) are recorded in Step 4. Since K L can be known from (K 17 , K 18 ),

Step 5 takes at most 2 128 12-round Camellia-256 encryptions.

Therefore, the attack has a memory complexity of 2 185 bytes and a total time complexity of approximately 2 219.9 12-round Camellia-256 encryptions.

It is worthy to observe that we can also apply the 6-round property with ω = 1 to break two other series of 12-round Camellia-256 with FL/ FL -1 functions, namely Rounds 1 to 12 and Rounds 13 to 24. Similarly, the attack has the same data and memory complexity as the above 12-round Camellia-256 attack, but has a total time complexity of approximately 2 56+176 × 256 × 8+8+5+1 8×12 ≈ 2 237.9 12-round Camellia-256 encryptions.

Concluding Remarks

In this paper, we have analysed the security of Camellia against the MitM attack in detail, following the work in [START_REF] Lu | The higher-order meet-in-the-middle attack and its application to the Camellia block cipher[END_REF]. We have presented 5 and 6-round properties of Camellia, that can be used to conduct MitM attacks on 10-round Camellia-128, 11-round Camellia-192 and 12-round Camellia-256, all of which include the FL/FL -1 functions but do not include whitening operations. The presented attacks are theoretical, like most cryptanalytic attacks on block ciphers.

Our results show that as far as Camellia is concerned, the semi-advanced MitM attack technique is more efficient than or at least as efficient as the advanced cryptanalytic techniques studied, except impossible differential cryptanalysis; in this latter case the MitM attacks are now one or two rounds inferior to the best newly emerging impossible differential cryptanalysis results in [START_REF] Bai | New impossible differential attacks on Camellia[END_REF][START_REF] Liu | New observations on impossible differential cryptanalysis of reduced-round Camellia[END_REF].

We attribute these MitM attacks to the fact that the FL -1 function does not have a good avalanche effect (i.e., an output bit relied on a large number of the bits of the input and the subkey used). If the FL -1 function were modified to have a good avalanche effect, then those MitM properties would involve a large number of unknown 1-bit constant parameters, and the resulting MitM attacks would be ineffective for the resulting cipher, but nevertheless it does not necessarily resist the HO-MitM attack technique, for those HO-MitM attacks described in [START_REF] Lu | The higher-order meet-in-the-middle attack and its application to the Camellia block cipher[END_REF] work as long as that integral property of Camellia holds (canceling the FL -1 function). Actually, if the FL/FL -1 functions had had a good avalanche effect, the Camellia cipher could have withstood the best currently known cryptanalytic results that are the newly emerging impossible differential cryptanalysis results [START_REF] Bai | New impossible differential attacks on Camellia[END_REF][START_REF] Liu | New observations on impossible differential cryptanalysis of reduced-round Camellia[END_REF]. In this sense, the FL/FL -1 functions do play an important role in the security of Camellia.

+Fig. 1 .

 1 Fig. 1. 5/6-round Camellia with FL/FL -1

Table 1 .

 1 Main cryptanalytic results on Camellia with FL/FL -1 functions

	Cipher Attack Type	Rounds Data	Memory Time	Source
	Camellia-Square	9	2 48 CP	2 53 Bytes 2 122 Enc.	[11]
	128	Impossible differential 10	2 118 CP	2 93 Bytes 2 118 Enc.	[23]
			11	2 120.5 CP	2 115.5 Bytes 2 123.8 Enc. [2] §
			11 †	2 122 CP	2 102 Bytes 2 122 Enc.	[22] §
		HO-MitM	10	2 93 CP	2 109 Bytes 2 118.6 Enc. [24]
		MitM	10	2 64 CP	2 105 Bytes 2 121.5 Enc. Sect. 4
	Camellia-Boomerang	9	2 123.9 ACPC 2 72 Bytes 2 169.9 MA [27]
	192	Impossible differential 10	2 121 CP	2 155.2 Bytes 2 144 Enc.	[6]
			10 †	2 121 CP	2 155.2 Bytes 2 175.3 Enc. [6]
			11	2 118 CP	2 141 Bytes 2 163.1 Enc. [23]
			12	2 120.6 CP	2 171.6 Bytes 2 171.4 Enc. [2] §
			12 †	2 123 CP	2 160 Bytes 2 187.2 Enc. [22] §
		HO-MitM	11	2 78 CP	2 174 Bytes 2 187.4 Enc. [24]
			11	2 94 CP	2 174 Bytes 2 180.2 Enc. [24]
		MitM	11	2 80 CP	2 105 Bytes 2 189.4 Enc. Sect. 5
			11	2 59.4 CP	2 167.6 Bytes 2 169.8 Enc. Sect. 5
	Camellia-Rectangle	10	2 126.5 CP	2 126.5 Bytes 2 240.9 MA [27]
	256	Integral	10	2 60.5 CP	2 63 Bytes 2 254.3 Enc. [23, 32]
		Higher-order differential 11 ‡	2 93 CP	2 98 Bytes 2 255.6 Enc. [13, 23]
		Impossible differential 11 †	2 121 CP	2 166 Bytes 2 206.8 Enc. [6]
			13 †	2 123 CP	2 208 Bytes 2 251.1 Enc. [22] §
			14	2 121.2 CP	2 180.2 Bytes 2 238.3 Enc. [2] §
			14	2 120 CC	2 125 Bytes 2 250.5 Enc. [22] §
		HO-MitM	12	2 94 CP	2 174 Bytes 2 237.3 Enc. [24]
		MitM	12	2 64 CP	2

185

Bytes 2 219.9 Enc. Sect. 6 §: Newly emerging results; †: Include whitening operations; ‡: Can include whitening operations by making use of an equivalent structure of Camellia.

2.2 The Camellia Block Cipher

		bitwise logical exclusive OR (XOR) of two bit strings of the same
		length
	∩	bitwise logical AND of two bit strings of the same length
	∪	bitwise logical OR of two bit strings of the same length
	≪	left rotation of a bit string
	||	bit string concatenation
	•	functional composition. When composing functions X and Y, X • Y
		denotes the function obtained by first applying X and then Y
	X	bitwise logical complement of a bit string X
	X[i 1 ,• • •, i j ]the j-bit string of bits (i 1 , • • • , i j ) of a bit string X
	Camellia [1] has a Feistel structure, a 128-bit block length, and a user key length
	of 128,

192 or 256 bits. It uses the following five functions: -S : {0, 1} 64 → {0, 1} 64 is a non-linear substitution constructed by applying

  eight 8 × 8-bit S-boxes S 1 , S 2 , S 3 , S 4 , S 5 , S 6 , S 7 and S 8 in parallel to the input, where S 1 and S 8 are identical, S 2 and S 5 are identical, S 3 and S 6 are identical, and S 4 and S 7 are identical.-P : GF (2 8 ) 8 → GF (2 8 ) 8 is a linear permutation which is equivalent to premultiplication by a 8 × 8 byte matrix P; the matrix P and its reverse P -1 are as follows.

  m 10 , m 11 , m 12 , m 13 , m 14 , m 15 ) with x (i) taking all the possible values in {0, 1} 8 and the other 15 bytes m 1 , m 2 , • • • , m 15 fixed to arbitrary values,

  255. Store the 2 100 256-bit sequences in a hash table L Θ . 2. Randomly choose six 8-bit constants γ 1 , γ 2 , • • • , γ 6 , and define a secret parameter δ to be

  [START_REF] Diffie | Exhaustive cryptanalysis of the NBS data encryption standard[END_REF][START_REF] Chen | New impossible differential attacks of reducedround Camellia-192 and Camellia-256[END_REF] , K 10,8 , K 11 ), and we denote the guessed value by (K *

	9,7 , K * 10,3 , K * 10,4 , K * 10,5 , K * 10,6 , K * 10,8 , K * 11 ). Then par-
	tially decrypt every ciphertext C (x) with (K * 10,3 , K * 10,4 , K * 10,5 , K * 10,6 , K * 10,8 , K * 11 ) to get the corresponding value for bytes (1, 2, • • • , 8, 15) just before
	Round 10; and we denote it by (L (x) 9 , R	(x) 9,7 ). Next, compute

  , • • • , T (255) ) matches a sequence in L Θ ; if so, record the guessed value (K * Step 1 with another subkey guess (if all the subkey possibilities are tested in Step 4, repeat Step 3 with another subkey guess). 5. For every recorded value for (K 10,3 , K 10,4 , K 10,5 , K 10,6 , K 10,8 ), exhaustively search the remaining 11 key bytes. The attack requires 256 × 2 56 = 2 64 chosen plaintexts. The one-off precomputation requires a memory of 2 100 × 256 × 1 8 = 2 105 bytes, and has a time complexity of 2 100 × 256 × 2 × 1 10 ≈ 2 109.7 10-round Camellia-128 encryptions under the rough estimate that a computation of Θ c1,c2,•••,c100 (z) equals 2 one-round Camellia-128 encryptions in terms of time. If the guessed value ) is correct, the input to Round 4 must have the form (m 1 , m 2 , m 3 , m 4 , m 5 , m 6 , m 7 , m 8 , x, m 9 , m 10 , m 11 , m 12 , m 13 , m 14 , m 15 ), where m 1 , • • • , m 15 are indeterminate constants.

	2,1 , K * 2,2 , K * 2,3 , K * 2,5 , K * 2,8 , 11 ) and execute Step 5; other-10,8 , K * 10,6 , K * 10,5 , K * 10,4 , K * 10,3 , K * 9,7 , K * 3,1 , K * K *
	wise, repeat (K * 2,1 , K * 2,2 , K * 2,3 , K * 2,5 , K * 2,8 , K * 3,1 , δ The time complexity of Step 3 is 2 56 × 256 × 1+5 8×10 ≈ 2 60.3 10-round Camellia-
	128 encryptions. Folllowing Property 1, we learn that the time complexity of
	Step 4 is approximately 2 56+60 × 256 × 8+5+1 8×10 ≈ 2 121.5 10-round Camellia-128
	encryptions.
	In Step 4, if the guessed value (K * 2,1 , K * 2,2 , K * 2,3 , K * 2,5 , K * 2,8 , K * 3,1 , δ * , K * 9,7 ,
	K * 10,3 , K * 10,4 , K * 10,5 , K * 10,6 , K * 10,8 , K * 11 ) is correct, the sequence (T (0) , • • • , T (255) ) must match a sequence in L Θ ; if the guessed value (K * 2,1 , K * 2,2 , K * 2,3 , K * 2,5 , K * 2,8 , K * 3,1 , δ * , K * 9,7 , K * 10,3 , K * 10,4 , K * 10,5 , K * 10,6 , K * 10,8 , K * 11 ) is wrong, the probability that
	the sequence (T

*

  255. Store the 2 100 256-bit sequences in a hash table L Θ . 2. Guess a value for (K 13 , K 14 , K 15,1 ), and we denote the guessed value by (K R ) in the following way, where α 1 , α 2 , • • • , α 8 , β 1 , β 2 , • • • , β 7 are randomly chosen 8-bit constants:

		(x) L ,
	P	(x)

* 13

, K * 14 , K * 15,1 ). Then for x = 0, 1, • • • , 255, choose plaintext P (x) = (P

  21,7 , K 22,3 , K 22,4 , K 22,5 , K 22,6 , K 22,8 , K 23 ), and we de-

	K * 23 ) to get the corresponding value for bytes (1, 2, • • • , 8, 14) just before
	Round 22; and we denote it by (L (x) 21 , R	(x) 21,7 ). Next, compute
	note the guessed value by (K * 21,7 , K * 22,3 , K * 22,4 , K * 22,5 , K * 22,6 , K * 22,8 , K * 23 ). Then,
	partially decrypt every ciphertext C (x) with (K * 22,3 , K * 22,4 , K * 22,5 , K * 22,6 , K * 22,8 ,

  * 23 ) and execute Step 4; otherwise, repeat Step 3 with another subkey guess (if all the subkey possibilities are tested in Step 3, repeat Step 2 with another subkey guess). 4. For every recorded value for (K 13 , K 23 ), exhaustively search the remaining 64 key bits. There are 2 64+8 = 2 72 possible values for (K 13 , K 14 , K 15,1 ), and thus the attack requires 256 × 2 72 = 2 80 chosen plaintexts. The one-off precomputation requires a memory of 2 100 × 256 × 1 8 = 2 105 bytes, and has a time complexity of 2 100 × 256 × 2 × 1 11 ≈ 2 106.6 11-round Camellia-192 encryptions under the rough estimate that a computation of Θ c1,c2,•••,c100 (z) equals 2 one-round Camellia-192 encryptions in terms of time. If the guessed value (K * 13 , K * 14 , K * 15,1 ) is correct, the input to Round 16 must have the form (m 1 , m 2 , m 3 , m 4 , m 5 , m 6 , m 7 , m 8 , x, β 1 , β 2 , β 3 , β 4 , β 5 , β 6 , β 7 ), where m 1 , m 2 , • • • , m 8 are indeterminate constants. The time complexity of Step 2 is 2 72 ×256× 1+8+8 8×11 ≈ 2 77.7 11-round Camellia-192 encryptions. By Property 2, the time complexity of Step 3 is about 2 72+112 × 256 × 8+5+1 8×11 ≈ 2 189.4 11-round Camellia-192 encryptions. In Step 3, if the guessed value (K *

	, • • • , T (255) ) matches a se-
	quence in L Θ ; if so, record the guessed (K * 13 , K * 14 , K * 15,1 , K * 21,7 , K * 22,3 , K * 22,4 , K * 22,5 , K * 22,6 , K * 22,8 , K 13 , K * 14 , K * 15,1 , K * 21,7 , K * 22,3 , K * 22,4 , K * 22,5 ,
	K * 22,6 , K * 22,8 , K * 23

  164 × 256 × 1 8 = 2 169 bytes and has a time complexity of 2 164 × 256 × 3 × 1 11 ≈ 2 170.2 11-round Camellia-192 encryptions. The attack requires 256 × 2 40+8 = 2 56 chosen plaintexts, and the time complexity in the key-recovery phase is approximately 2 48+112 ×256× 8+5+1 8×11 ≈ 2 165.4 11-round Camellia-192 encryptions.

  , • • • , 255. Store the 2 179 512-bit sequences in a hash table L Υ . 2. Randomly choose six 8-bit constants 1 , γ 2 , • • • , γ 6 , and define a secret parameter δ to be

  • • • , 255). In a chosenplaintext attack scenario, obtain the ciphertexts for the plaintexts; we denote by C (x) the ciphertext for plaintext P (x) . 4. Guess a value for (K 15,6 , K 16,2 , K 16,3 , K 16,5 , K 16,7 , K 16,8 , K 17 , K 18 ), and we denote the guessed value by (K *

				8,1 , δ), and we denote the
	guessed value by (K * 7,1 , K * 7,2 , K * 7,3 , K * 7,5 , K * 7,8 , K * 8,1 , δ * ). Then for x = 0, 1, • • • ,
	255, choose plaintext P (x) = (P	(x) L , P	(x) R ) in the same way as in the 10-round
	Camellia-128 attack described in Section 4, (x = 0, 1, 15,6 , K * 16,2 , K * 16,3 , K * 16,5 , K * 16,7 , K * 16,8 , K * 17 , K * 18 ).
	Then partially decrypt every ciphertext C (x) with (K * 16,2 , K * 16,3 , K * 16,5 , K * 16,7 , K * 16,8 , K * 17 , K * 18 ) to get the corresponding value for bytes (1, 2, • • • , 8, 14) just
	before Round 16; and we denote it by (L (i,x) 15 , R	(i,x) 15,6 ). Next, compute

  For every recorded value for (K 17 , K 18 ), exhaustively search the remaining 16 key bytes. The attack requires 256 × 2 56 = 2 64 chosen plaintexts. The one-off precomputation requires a memory of 2 179 × 256 × 2 8 = 2 185 bytes, and has a time complexity of 2 179 × 256 × 3 × 1 12 = 2 185 12-round Camellia-256 encryptions under the rough estimate that a computation of Υ c ′ ) is correct, the input to Round 9 must have the form (m 1 , m 2 , m 3 , m 4 , m 5 , m 6 , m 7 , m 8 , x, m 9 , m 10 , m 11 , m 12 , m 13 , m 14 , m 15 ), where m 1 , m 2 , • • • , m 15 are indeterminate constants. The time complexity of Step 3 is 2 56 × 256 × 1+5 8×12 = 2 60 12-round Camellia-256 encryptions. By Property 3, the time complexity of Step 4 is approximately 2 56+158 × 256 × 8×12 ≈ 2 219.9 12-round Camellia-256 encryptions. In Step 4, for the correct guess of (K 7,1 , K 7,2 , K 7,3 , K 7,5 , K 7,8 , K 8,1 , δ, K 15,6 , K 16,2 , K 16,3 , K 16,5 , K 16,7 , K 16,8 , K 17 , K 18

	5. 1 ,c ′ 2 ,•••,c ′ 179 (z) equals
	3 one-round Camellia-256 encryptions in terms of time. If the guessed value
	(K * 7,1 , K * 7,2 , K * 7,3 , K * 7,5 , K * 7,8 , K * 8,1 , δ
	, • • • , T (255) ) matches a se-
	quence in L Υ ; if so, record the guessed value (K * 7,1 , K * 7,2 , K * 7,3 , K * 7,5 , K * 7,8 , K * 8,1 , K * 15,6 , K * 16,2 , K * 16,3 , K * 16,5 , K * 16,7 , K * 16,8 , K * 17 , K * 18 ) and execute Step 5; other-
	wise, repeat Step 4 with another subkey guess (if all the subkey possibilities
	are tested in Step 4, repeat Step 3 with another subkey guess).

*

Here we give only the subkeys concerned in this paper, (KA ≪ 0)[65 ∼ 128] represents bits (65, 66, • • • , 128) of (KA ≪ 0), and so on.

Acknowledgments. The authors are grateful to the anonymous referees for their comments on this paper.

⋆ The work was supported by the French ANR project SAPHIR II (No. ANR-08-VERS-014), the Natural Science Foundation of China (No. 61100185), Guangxi Natural Science Foundation (No. 2011GXNSFB018071), and the Foundation of Guangxi Key Lab of Wireless Wideband Communication and Signal Processing (No. 11101). ⋆⋆ The author was with École Normale Supérieure (France) when this work was done.

Appendix: Proof of Proposition 1

First, we have the following property for the FL/FL -1 functions.

Property 4 (from [START_REF] Lu | The higher-order meet-in-the-middle attack and its application to the Camellia block cipher[END_REF]) Let x 1 , x 2 , • • • , x 8 , y 1 , y 2 , • • • , y 8 be 8-bit blocks and KI be a 64-bit subkey. [START_REF] Aoki | Camellia: a 128-bit block cipher suitable for multiple platforms -design and analysis[END_REF]) ∩ KI [10 ∼ 17]) ⊕ x 6 ) ∪ KI[41 ∼ 48]) ⊕ x 2 , y 3 = ((((x 3 [2 ∼ 8]||x 4 [START_REF] Aoki | Camellia: a 128-bit block cipher suitable for multiple platforms -design and analysis[END_REF]) ∩ KI [18 ∼ 25]) ⊕ x 7 ) ∪ KI[49 ∼ 56]) ⊕ x 3 , y 4 = ((((x 4 [2 ∼ 8]||x 1 [START_REF] Aoki | Camellia: a 128-bit block cipher suitable for multiple platforms -design and analysis[END_REF]) ∩ KI [26 ∼ 32, 1]) ⊕ x 8 ) ∪ KI[57 ∼ 64]) ⊕ x 4 , y 5 = ((x 1 [2 ∼ 8]||x 2 [START_REF] Aoki | Camellia: a 128-bit block cipher suitable for multiple platforms -design and analysis[END_REF]) ∩ KI [2 ∼ 9]) ⊕ x 5 , y 6 = ((x 2 [2 ∼ 8]||x 3 [START_REF] Aoki | Camellia: a 128-bit block cipher suitable for multiple platforms -design and analysis[END_REF]) ∩ KI [10 ∼ 17]) ⊕ x 6 , y 7 = ((x 3 [2 ∼ 8]||x 4 [START_REF] Aoki | Camellia: a 128-bit block cipher suitable for multiple platforms -design and analysis[END_REF]) ∩ KI [18 ∼ 25]) ⊕ x 7 , y 8 = ((x 4 [2 ∼ 8]||x 1 [START_REF] Aoki | Camellia: a 128-bit block cipher suitable for multiple platforms -design and analysis[END_REF]) ∩ KI [26 ∼ 32, 1]) ⊕ x 8 .

If (y 1 ||y 2 || • • • ||y

When encrypting X (i) , we denote by

the value immediately after the S operation of Round t, and by W (i) t the value immediately after the P operation of Round t, (3 t 8).

We have Eq. ( 1) for Rounds 4 to 8 and have Eq. ( 2) for Rounds 3 to 8.

(1)

We first prove Proposition 1-1, and focus on encrypting X (i) through Rounds 4 to 8 below. The output of Round 4 is as follows, where a 1 , a

The output immediately before the FL/FL -1 functions is as follows, where

By Property 4-1, we know that FL( L

Since

6 , by Property 4-2 we know that P -1 (FL -1 (X

), a total of 100 + 15 × ω constant 1-bit parameters. Proposition 1-1 follows from Eq. ( 1).

We next prove Proposition 1-2. The output (L

3 ) of Round 3 is as follows, where a 1 , a 2 , • • • , a 8 are 8-bit constants completely determined by m 1 , m 2 , • • • , m 15 and K 3 .

By Property 4-1, we know that FL( L

6,6 , KI 1 [10 ∼ 17], where

Letting n l = e l ⊕ K 6,l and o 1 = b 6 ⊕ K 7,6 , (l = 1, 2, • • • , 8), then we can learn that Y (i,j) 7

[41 ∼ (41+ω)] is determined only by (x


Patrick Derbez
email: patrick.derbez@ens.fr

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

Jérémy Jean
email: jeremy.jean@ens.fr

Faster Chosen-Key Distinguishers on Reduced-Round AES

Keywords: AES, Open-key Model, Chosen-key Distinguisher, Practical Complexities

In this paper, we study the AES block cipher in the chosen-key setting. The adversary's goal of this security model is to find triplets (m, m ′ , k) satisfying some properties more efficiently for the AES scheme than generic attacks. It is a restriction of the classical chosen-key model, since as it has been defined originally, differences in the keys are possible. This model is related to the known-key setting, where the adversary receives a key k, and tries to find a pair of messages (m, m ′ ) that has some property more efficiently than generic attacks. Both models have been called open-key model in the literature and are interesting for the security of AES-based hash functions. Here, we show that in the chosen-key setting, attacking seven rounds (resp. eight rounds) of AES-128 can be done in time and memory 2 8 (resp. 2 24 ) while the generic attack would require 2 64 computations as a variant of the birthday paradox can be used to predict the generic complexity. We have checked our results experimentally and we extend them to distinguisers of AES-256.

Introduction

The Advanced Encryption Standard (AES) [START_REF]NIST: Advanced Encryption Standard (AES), FIPS 197[END_REF] is nowadays the subject of many attention since attacks coming from hash function cryptanalysis have put its security into question. Related-key attacks and meet-in-the-middle attacks that begin in the middle of the cipher (also known as splice-and-cut attacks) have been proposed to attack the full number of rounds for each AES versions [START_REF] Biryukov | Related-Key Cryptanalysis of the Full AES-192 and AES-256[END_REF][START_REF] Biryukov | Distinguisher and Related-Key Attack on the Full AES-256[END_REF][START_REF] Bogdanov | Biclique Cryptanalysis of the Full AES[END_REF], while other techniques exist for smaller version [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF]. This interesting connection between hash functions and block ciphers shows that any improvement on hash function cryptanalysis can be useful for attacking block ciphers and vice-versa.

In this work, we study another model that has been suggested to study the security of hash functions based on AES components. Knudsen and Rijmen [START_REF] Knudsen | Known-Key Distinguishers for Some Block Ciphers[END_REF] have proposed to consider known-key attacks since in the hash function domain, the key is usually known and the goal is to find two input messages that satisfy some interesting relations. In some setting, a part of the key can also be chosen (for instance when salt is added to the hash function) and therefore, cryptanalysts have also consider the model where the key is under the control of the adversary. The latter model has been called chosen-key model and both models belong to the open-key model. The chosen-key model has been popularized by Biryukov et al. in [START_REF] Biryukov | Distinguisher and Related-Key Attack on the Full AES-256[END_REF], since a distinguisher in this model has been extended to a related-key attack on the full AES-256 version.

Related Work. Knudsen and Rijmen in [START_REF] Knudsen | Known-Key Distinguishers for Some Block Ciphers[END_REF] have been the firsts to consider known-key distinguishers on AES and Feistel schemes. The main motivations for this model are the following:

if there is no distinguisher when the key is known, then there will also be no distinguisher when the key is secret, -if it is possible to find an efficient distinguisher, finding partial collision on the output of the cipher more efficiently than birthday paradox would predict even though the key is known, then the authors would not recommend the use of such cipher, -finally, such model where the key is known or chosen can be interesting to study the use of cipher in a compression function for a hash function.

In the same work, they present some results on Feistel schemes and on the AES. Following this work, Minier et al. in [START_REF] Minier | Distinguishers for Ciphers and Known Key Attack against Rijndael with Large Blocks[END_REF] extend the results on AES on the Rijndael scheme with larger block-size.

In [START_REF] Biryukov | Distinguisher and Related-Key Attack on the Full AES-256[END_REF], Biryukov et al. have been the firsts to consider the chosen-key distinguisher for the full 256-bit key AES. They show that in time q • 2 67 , it is possible to construct qmulticollision on Davies-Meyer compression function using AES-256, whereas for an ideal cipher, it would require on average q • 2 q-1 q+1 128 time complexity. In these chosen-key distinguishers, the adversary is allowed to put difference also in the key. Later, Nikolic et al. in [START_REF] Nikolic | Known and Chosen Key Differential Distinguishers for Block Ciphers[END_REF], describe known-key and chosen-key distinguishers on Feistel and Substitution-Permutation Networks (SPN). The notion of chosen-key distinguisher is more general than the model that we use: here, we let the adversary choose the key, but it has to be the same for the input and output relations we are looking for. We do not consider related-keys in this article. Then in [START_REF] Mendel | Improved Cryptanalysis of the Reduced Grøstl Compression Function, ECHO Permutation and AES Block Cipher[END_REF], rebound attacks have been used to improve known-key distinguishers on AES by Mendel et al. and in [8], Gilbert and Peyrin have used both the SuperSBox and the rebound techniques to get a known-key distinguisher on 8-round AES-128. Last year at FSE, Sasaki and Yasuda show in [START_REF] Sasaki | Known-Key Distinguishers on 11-Round Feistel and Collision Attacks on Its Hashing Modes[END_REF] an attack on 11 Feistel rounds and collision attacks in hashing mode also using rebound techniques, and more recently, Sasaki et al. studied the known-key scenario for Feistel ciphers like Camellia in [START_REF] Sasaki | Improved known-key distinguishers on feistel-sp ciphers and application to camellia[END_REF].

Our Results. In this paper, we study 128-and 256-bit reduced versions of AES in the (single) chosen-key model where the attacker is challenged to find a key k and a pair of messages (m, m ′ ) such that m ⊕ m ′ ∈ E and AES k (m) ⊕ AES k (m ′ ) ∈ F , where E and F are two known subspaces. On AES-128, we describe in that model a way to distinguish the 7-round AES in time 2 8 and the 8-round AES in time 2 24 . In the case of the 7-round distinguisher, our technique improves the 2 16 time complexity of a regular rebound technique [START_REF] Mendel | The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl[END_REF] on the SubBytes layer by computing intersections of small lists. The 8-round distinguisher introduces a problem related the SuperSBox construction where the key parameter is under the control of the adversary. As for AES-256, the distinguishers are the natural extensions of the ones on AES-128. Our results are reported in Table 1. We have experimentally checked our results and examples are provided in the appendices. We believe our practical distinguishers can be useful to construct non-trivial inputs for the AES block cipher to be able to check the validity of some theoretical attacks, for instance [START_REF] Dunkelman | Improved Single-Key Attacks on 8-Round AES-192 and AES[END_REF].

Outline of the paper. The paper is organized as follows. We begin in Section 2 by recalling the AES and the concept of SuperSBox. Then in Section 3.1, we precise the chosen-key model in the ideal case to be able to compare our distinguishers to the ideal scenario. Section 3.1 describes the main results of the AES-128 and Section 4 shows how to apply similar results to the AES-256.

Description of the AES

The Advanced Encryption Standard [START_REF]NIST: Advanced Encryption Standard (AES), FIPS 197[END_REF] is a Substitution-Permutation Network that can be instantiated using three different key bit-lengths: 128, 192, and 256. The 128-bit plaintext initializes the internal state viewed as a 4 × 4 matrix of bytes as values in the finite field GF (2 8 ), which is defined via the irreducible polynomial x 8 + x 4 + x 3 + x + 1 over GF [START_REF] Biryukov | Distinguisher and Related-Key Attack on the Full AES-256[END_REF]. 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 the last one where we omit the MixColumns):

-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 circulant matrix over the field GF (2 8 ), M = circ(2, 3, 1, 1). After the N r -th rounds 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 for AES-128 is described in Figure 2(a), and in Figure 2(b) for the AES-256. We refer to the official specification document [START_REF]NIST: Advanced Encryption Standard (AES), FIPS 197[END_REF] for further details.

AK SB S x x x x SR C ← M × C x x x x MC wi-1 xi yi zi wi
SuperSBox. In [START_REF] Daemen | Understanding Two-Round Differentials in AES[END_REF], Rijmen and Daemen introduced the concept of SuperSBox to study two rounds of AES. This transformation sees the composition SB • AK(k) • MC • SB as four parallel applications of a 32-bit S-Box, and has been useful for several cryptanalysis works, see for instance [START_REF] Gilbert | Super-Sbox Cryptanalysis: Improved Attacks for AES-Like Permutations[END_REF][START_REF] Lamberger | Rebound Distinguishers: Results on the Full Whirlpool Compression Function[END_REF]. Abusing notations, in the sequel, we call SuperSBox keyed by the key k the transformation that applies this composition to a single AES-column. In that context, the key k which parameterized the SuperSBox is also a 32-bit AES-column. We denote that operation by SuperSBox k .

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 2(c). Moreover, as shown in Figure 1, 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.

3 Chosen-key distinguishers

Limited Birthday Distinguishers

In this section, we precise the distinguishers we are using. Our first goal is to distinguish the AES-128 from an ideal keyed-permutation in the chosen-key model. We will derive distinguishers for AES-256 afterwards. We are interested in the kind of distinguishers where the attacker is asked to find a key and a pair of plaintext whose difference is constrained in a predefined input subspace such that the ciphertext difference lies in an other predefined subspace.

Property 1 Given two subspaces E in and E out , a key k and a pair of messages (x, y) verify the property on a permutation P if x + y ∈ E in and P (x) + P (y) ∈ E out .

This type of distinguisher looks like the limited birthday distinguishers introduced by Gilbert and Peyrin in [START_REF] Gilbert | Super-Sbox Cryptanalysis: Improved Attacks for AES-Like Permutations[END_REF] with a very close lower bound proved in [START_REF] Nikolic | Known and Chosen Key Differential Distinguishers for Block Ciphers[END_REF], except that we allow the attacker more freedom; namely, in the choice of the key bits. To determine how hard this problem is, we need to compare the real-world case to the ideal scenario. In the latter, the attacker faces a family 1 of pseudo-random permutations F : K × D -→ D, and would run a limited birthday distinguisher on a particular random permutation F k to find a pair of messages that conforms to the subspace restrictions of Property 1. The additional freedom of this setting does not help the attacker to find the actual pair of messages that verifies the required property, because the permutation F k has to be chosen beforehand. Put it another way, the birthday paradox is as constrained as if the key were known since no difference can be introduced in the key bits.

Therefore, even if we let the key to be chosen by the attacker, the limited birthday distinguisher from [START_REF] Gilbert | Super-Sbox Cryptanalysis: Improved Attacks for AES-Like Permutations[END_REF] applies in the same way. For known E in and E out , we denote n i = dim(E in ) and n o = dim(E out ). In terms of truncated differences, n i (resp. n o ) represents the number of independent active truncated differences in the input (resp. output) of a random permutation F k ∈ F (see Figure 3). Both n i and n o range in the interval between 0 and n, where n = 16 in the case of AES. Without loss of generality, we assume that n i ≤ n o : the attacker thus considers F k rather than its inverse, as it is easier to collide on n -n o differences than on n -n i . The attacker continues by constructing two lists L and 2 8n i plaintexts each by choosing a random value for the n -n i inactive bytes of the input and considering all the n i active ones in E in . With a birthday paradox on the two lists L and L ′ , she expects a collision on at most 2n i bytes of the ciphertexts. In the event that n -n o ≥ 2n i , then n -2n i bytes have not a zero-difference in the ciphertext. Hence, we need to restart the birthday paradox process about 2 8(n-no-2n i ) times, which costs 2 8(n-no-n i ) in total. Otherwise, if n -n o < 2n i , then a single birthday paradox with lists of size 2 8(n-no)/2 is sufficient to get a collision on the n -n o required bytes in time 2 8(n-no)/2 .

L ′ of ni n n0 n -n0 F k

Distinguisher for 7-round AES-128

We consider the 7-round truncated differential characteristic of Figure 4, where the differences in both the plaintext and the ciphertext lie in subspaces of dimension four. Indeed, the output difference lies in a subspace of dimension four since all the operations after the last SubBytes layer are linear. With respect to the description of the distinguisher (Section 3.1), the time complexity to find a pair of messages that conforms to those patterns in a family of pseudo-random permutations is 2 64 basic operations.

The following of this section describes a way to build a key and a pair of messages that conform to the restrictions in time 2 8 basic operations using a memory complexity of 2 8 bytes. This complexity has to be compared to 2 16 operations, which is the time complexity expected for a straightforward application of the rebound attack [START_REF] Mendel | The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl[END_REF] on the SubBytes layer of the AES. In that case, there are 16 random differential transitions around the AES S-Box, which happens to be all compatible2 with probability 2 -16 . Repeating with random differences 2 16 times, we expect to find a pair of internal states that conforms to the randomized differences. In the following, we proceed slightly differently to reach a solution in time 2 8 .

In terms of freedom degrees, we begin by estimating the number of solutions that we expect to verify the truncated differential characteristic. There are 16 bytes in the first message, 4 more independent ones in the second message and 16 others in the key: that makes 36 freedom degrees at the input. On a random input, the probability that the truncated differential characteristic being followed depends on the amount of freedom degrees that we loose in probabilistic transitions within the MixColumns transitions: 3 in round 0 to pass one 4 → 1 truncated transition, 12 in round 3 to pass four 4 → 1 transitions and 3 again in round 4 for the last 4 → 1 transition. In total, we thus expect

2 8×(16+4+16) 2 -8×(3+12+3) = 2 8×18
triplets (m, m ′ , k) composed by a pair (m, m ′ ) of messages and a key k to conform to the truncated differential characteristic of Figure 4. Hence, we have 18 freedom degrees left to find such a triplet. First, we observe that whenever we find such a solution for the middle rounds (round 1 to round 4), we are ensured that all the rounds will be covered as in the whole truncated differential characteristic due to an outward propagation occurring with probability 1. Hence, our strategy focuses on those rounds. The context is similar to the rebound scenario, where we first solve the inbound phase and then propagate it into the outbound phase. To reduce the number of valid solutions, we begin by fixing some bytes (Figure 5) to a random value: ∆z 1 and x 2 [0..3]. Therefore, we can deduce the values and differences in the first column of x 2 and y 2 , as well as the difference ∆x 3 by linearity. Let [∆ 0 , ∆ 1 , ∆ 2 , ∆ 3 ] T be the column-vector of deduced differences in ∆y 2 and diag(δ 0 , δ 1 , δ 2 , δ 3 ) the differences in the diagonal of ∆x 4 . Linearly, we can express the differences around the SubBytes layer of round 3 (see Figure 6). As a consequence, from the differential properties of the AES S-Box, for i, j ∈ {0, . . . , 3}, ∆ j suggests 2 7 different values for δ i : we store them in the list L i,j .

L i,j = δ i ∆ j → δ i is possible . (1)
Once done, we build the list L i , for i ∈ {0, . . . , 3}:

L i = 3 j=0 L i,j = δ i ∀j ∈ {0, . . . , 3}, ∆ j → δ i is possible . (2)
Each L i,j being of size 2 7 , we expect each L i to contain 2 4 elements.

We continue by setting ∆x 4 [0] to random value in L 0 and x 4 [0] to a random value, which allow to determine the value and difference in y 4 [0]. Since the difference ∆y 4 can only take 2 8 values due to the MixColumns transition of round 4, we also deduce ∆w 4 and the remaining differences in ∆y 4 . The knowledge of ∆y 4 suggests 2 7 possible values for δ i . As before, we store them in lists called T i , and we select a value for δ i in L i ∩ T i (Figure 7). We expect each intersection to contain about 2 3 elements. More rigorously, if we assume that the lists L i,j and T i are uniformly distributed, then the probability that L 0 , L 1 ∩ T 1 , L 2 ∩ T 2 and L 3 ∩ T 3 are not empty is higher than 99.96% (see proof in Appendix C). Finally, we compute the values in x 3 and in the diagonal of x 4 . We now need to find a key that matches the previous solving in the internal states: we build a partial pair of internal states that conforms to the middle rounds, but that sets 8 bytes on constraints in the key. Namely, if we denote k i the subkey introduced in round i and u i = MC -1 (k i ), then both u 3 and k 4 have four known bytes (see Figure 8). We start by fixing all the bytes marked by 1 in u 3 to random values: this allows to compute the values of all 2's in the two last columns of k 3 . By the column-wise operations of AES key schedule, we can get the values of all bytes marked by 3. As for the 4's, we get them since there are four known bytes among the eight in the first columns of u 3 and k 3 . Again, the key schedule gives the 5's and 6's, and the MixColumns the 7's. Finally, we determine values for all the byte tagged by 8 from the key schedule equations. By inverting the key schedule, we are thus able to compute the master key k.

All in all, we start by getting a partial pair of internal states that conforms to the middle rounds, continue by deriving a valid key that matches the partial known bytes and determine the rest of the middle internal states to get the pair on input messages. The bottleneck of the time and memory complexity occurs when handling the lists of size at most 2 8 elements to compute intersections. Note that those intersections can be done in roughly 2 8 operations by representing lists by 256-bit numbers and then perform a logical AND.

In the end, we build a pair of messages (m, m ′ ) and a key k that conforms to the truncated differential characteristic of Figure 4 in time 2 8 basic operations, where it costs 2 64 in the generic scenario. We note that among the 18 freedom degrees left for the attack, we used only 10 by setting 10 bytes to random values, such that we expect 2 8×8 = 2 64 solutions in total. All those solutions could be generated in time 2 64 by iterating over all the possibilities of the bytes marked by 1 in Figure 8.

We implemented the described algorithm to verify that it indeed works, and we found for instance the triplet (m, m ′ , k) reported in Appendix A.

Distinguisher for 8-round AES-128

We consider the 8-round truncated differential characteristic of Figure 9, where the matrices of differences in both the plaintext and the ciphertext lie in the same matrix subspaces of dimension four as before. Indeed, the output difference lies in a subspace of dimension four since all the operations after the last SubBytes layer are linear. Again, the distinguisher previously described (Section 3.1) claims that the time complexity to find a pair of messages that conforms to those patterns in a family of pseudo-random permutations runs in time 2 64 operations. The following of this section describes a way to build a key and a pair of messages that conform to the restrictions in time and memory complexity 2 24 . We note that it is possible to optimize the memory requirement to 2 16 . As in the previous section, there are 36 freedom degrees at the input, which shrink to 18 after the consideration of the truncated differential characteristic. Therefore, we also expect 2 8×18 solutions in the end.

First of all, we observe that finding 2 24 triplets (m, m ′ , k) composed by a key and a pair of internal states that conform to the rounds 2 to 5 is sufficient since the propagation in the outward rounds is done with probability 2 -24 due to the MixColumns transition of round 1. The following analysis consequently focuses of those four middle rounds.

We now describe an instance of a problem that we use as a building block in our algorithm, which is related to the keyed SuperSBox construction.

Problem 1. Let a and b two bytes. Given a 32-bit input and output differences ∆ in and ∆ out of a SuperSBox k for a unknown k, find all the pairs of AES-columns (c, c ′ ) and keys k such that:

i. c + c ′ = ∆ in , ii. SuperSBox k (c) + SuperSBox k (c ′ ) = ∆ out , iii. SuperSBox k (c) = [a, b, ⋆, ⋆] T .
Considering the key k known and the case where there is no restriction on the output bytes (iii ), we would expect this problem to have one solution on average. Finding it would naively require 2 32 computations by iterating over the 2 32 possible inputs and check whether the output has the correct ∆ out known difference. The additional constraints on the two output bytes reduce the success of finding a pair (c, c ′ ) of input to 2 -16 , but if we allow the four bytes in the key k to be chosen, then we expect 2 16 solutions to this problem.

To find all of them in 2 16 simple operations, we proceed as follows (Figure 10): the two output bytes a and b being known, we can deduce the values of the two associated bytes before the last SubBytes, ã and b respectively. We can also deduce the difference in those bytes since the output difference is known. Then, we guess the two unset differences at the input of the last SubBytes: the differences then propagate completely inside the SuperSBox. At both SubBytes layers, by the differential properties of the AES S-Box, we expect to find one value on average for each of the six unset transitions. Consequently, the input and output of the AddRoundKey operation are known, which determines the four bytes of k. In the end, we find the 2 16 solutions of Problem 1 in time 2 16 operations. To apply this strategy to the 8-round truncated differential characteristic of Figure 9, we start by randomizing the difference ∆y 2 , the difference ∆w 5 and the values in the first column of w 5 . Due to the linear operations involved, we deduce ∆x 3 = ∆w 2 from ∆y 2 and ∆y 4 from ∆w 4 . To use the previous algorithm, we randomize the values of the two first columns of w 4 (situtation in Figure 11). Doing so, the four columns of y 4 are constrained on two bytes each and have fixed differences. Consequently, the four SuperSBoxes between x 3 and y 4 keyed by the four corresponding columns of k 4 conforms to the requirements 3 of Problem 1. In time and memory complexity 2 16 , for i ∈ {0, 1, 2, 3}, we store the 2 16 solutions for the ith SuperSBox associated to the ith column of x 4 in the list L i .

We continue by observing that the randomization of the bytes in w 4 actually sets the value of two diagonal bytes in k 5 , k 5 [0] and k 5 [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF], which imposes constraints of the elements in the lists L i . We start by considering the 2 16 elements of L 3 , and for each of them, we 3 The positions of the known output bytes differ, but the strategy applies in the same way. At this point, we constructed 2 16+8 = 2 24 solutions in time 2 24 that we store in a list L 0,3 . As k 5 [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF] has been previously determined, we can deduce k 4 [5] = k 5 [5] + k 5 [START_REF] Biryukov | Related-Key Cryptanalysis of the Full AES-192 and AES-256[END_REF] from the AES key schedule for each of the entry of L 0,3 . Again, this adds an 8-bit constraint on the elements of L 1 : we expect 2 8 of them to match the condition on k 4 [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF]. In total, we could construct a list L 0,1,3 of size 2 24+8 = 2 32 , whose elements would be the columns 0, 1 and 3 of x 4 and k 4 , but as soon as we get 2 24 elements in that list, we stop and discard the remaining possibilities.

Finally, to ensure the correctness of the choice in the remaining column 2, we need to consider the MixColumns operation in round 4 and the subkey k 5 . Indeed, as soon as we choose an element in both L 0,1,3 and L 2 , x 4 , k 4 and k 5 become fully determined, but we need to ensure that the values x 5 [10] and x 5 [START_REF] Nikolic | Known and Chosen Key Differential Distinguishers for Block Ciphers[END_REF] equal to the known ones. In particular, for x 5 [START_REF] Lamberger | Rebound Distinguishers: Results on the Full Whirlpool Compression Function[END_REF], we have:

k 4 [10] + k 5 [6] = k 5 [10] (3)
= w 4 [10] + x 5 [10] (4)
= z 4 [8] + z 4 [9] + 2z 4 [10] + 3z 4 [11] + x 5 [10], (5)
and for x 5 [START_REF] Nikolic | Known and Chosen Key Differential Distinguishers for Block Ciphers[END_REF]:

k 4 [11] + k 5 [7] + k 4 [15] = k 5 [11] + k 4 [15] (6)
= k 5 [15] (7)
= w 4 [15] + x 5 [15] (8)
= 3z 4 [12] + z 4 [13] + z 4 [14] + 2z 4 [15] + x 5 [15], (9)
where ( 3), ( 6) and ( 7) come from the key schedule, ( 4) and ( 8) from the AddRoundKey and ( 5) and ( 9) use the equations from the MixColumns. Hence, for each element of L 0,1,3 , we can compute:

S(x 4 [8]) + k 4 [10] := x 5 [10] + k 5 [6] + S(x 4 [13]) + 2 S(x 4 [2]) + 3 S(x 4 [7]), (10)
k 4 [11] + 2 S(x 4 [11]) := k 5 [7] + k 4 [15] + 3 S(x 4 [12]) + S(x 4 [1]) + S(x 4 [6]) + x 5 [15] (11)
and lookup in L 2 to find 2 16 2 -8×2 = 1 element that match those two byte conditions. We create the list L by adding the found element from L 2 to each entry of L 0,1,3 .

All in all, in time and memory complexity 2 24 , we build L of size 2 24 and we now exhaust its elements to find one that passes the 2 -24 probability of the 4 → 1 backward transition in the MixColumns of round 1. Indeed, an a → b transition in the MixColumns layer cancels 4 -b output bytes, so that it would happen with probability 2 -8(4-b) for a random input a. Consequently, we expect to find a pair (m, m ′ ) of messages and a key k that conforms to the 8-round truncated differential characteristic of Figure 9 in time 2 24 when it requires 2 64 computations in the ideal case.

Among the 18 available freedom degrees available to mount the attack, we uses 17 of them, which means that we expect to have 2 8 solutions. We could have them in time 2 32 , but since we discarded 2 8 elements in the algorithm described, we get only 1 in time 2 24 . We note that it is possible to gain a factor 2 8 in the memory requirements of our attack since we can implement the algorithm without storing the lists L 0 , L 0,3 and L 0,1,3 , by using hash tables for L 1 , L 2 and L 3 .

We also implemented the described algorithm to verify that it indeed works, and we found for instance the triplet (m, m ′ , k) reported in Appendix B.

Extention to AES-256

The two distinguishers described in the previous section can be easily extended in distinguishers on the AES-256. The main idea is to use the 16 additional freedom degrees in the key to extend the truncated differential characteristics by introducing a new fully active round in the middle.

Distinguisher for 7-round AES-256

The first step of the attack described in the 7-round distinguisher on AES-128 (Section 3.2) still applies in the case of AES-256 since it does not involve the key schedule. Then, we can generate a compatible key easily since there are only two subkeys involved: we can just choose bytes of k 3 and k 4 as we want, except the imposed ones, and deduce the master key afterwards. This yields to a distinguisher with time and memory complexities around 2 8 .

Distinguisher for 8-round AES-256

We use a similar approach as the 7-round distinguisher on AES-128 of Section 3.2, but the truncated differential characteristic has one more fully active round in the middle 4 .

We begin by choosing values for ∆z 1 and x 2 [0..3]. This allows to deduce ∆x 2 , ∆y 2 , and ∆x 3 . Then, we also set random values for ∆w 5 and for the diagonal of x 5 to obtain both ∆x 5 and ∆y 4 . Now, we find a value for ∆x 4 , which is compatible with ∆x 3 and ∆y 4 . Indeed, we can not take an arbitrary value for ∆x 4 because the probability that it fits is very close to 2 -32 . However, we can find a correct value with the following steps:

1. Store the 2 7 possible values for ∆x 4 [0] in a list L 0 . 2. In a similar way, make lists L 1 with ∆x 4 [START_REF] Biryukov | Related-Key Cryptanalysis of the Full AES-192 and AES-256[END_REF], L 2 with ∆x 4 [START_REF] Biryukov | Distinguisher and Related-Key Attack on the Full AES-256[END_REF] and L 3 with ∆x 4 [START_REF] Biryukov | A New Security Analysis of AES-128[END_REF]. 3. Choose a value for (x 3 [0], x 3 [START_REF] Bouillaguet | Automatic search of attacks on round-reduced AES and applications[END_REF], x 3 [START_REF] Lamberger | Rebound Distinguishers: Results on the Full Whirlpool Compression Function[END_REF], x 3 [START_REF] Nikolic | Known and Chosen Key Differential Distinguishers for Block Ciphers[END_REF]) and compute ∆x 4 [0.

.3]. 4. If ∆x 4 [0..3] is not in L 0 × L 1 × L 2 × L 3 ,
then go back to step 3.

On average, we go back to the step 3 only 2 8-7 4 = 2 4 times since lists are of size 2 7 . In the same way, we can obtain values for the other columns of x 4 .

At this point, we computed actual values in all those internal states, and we need to generate a compatible key. Finding one can be done using the procedure described in Figure Figure 12. Bytes tagged by 1 are chosen at random, odd steps use the key schedule equations and even steps the properties of MixColumns.

Distinguisher for 9-round AES-256

We begin as in Section 3.3 by choosing the difference ∆y 2 , the difference ∆w 6 and the values in the first column of w 6 . Then, we deduce ∆w 2 = ∆x 3 from ∆y 2 and ∆y 5 from ∆w 5 . In addition, we set x 3 to a random value, which allows to determine ∆x 4 . In order to apply the result from Problem 1 again, we set the values in two first columns of w 5 to random values.

As before, for i ∈ {0, 1, 2, 3}, we store in the list L i the 2 16 possible values of the i-th column of x 5 and the i-th column of k 5 . Unlike previously, we also obtain values of the i-th column of SR(k 4 ), but the scenario of the attack still applies. We start by observing that bytes of L 0 allow to compute k 4 [START_REF] Biryukov | Related-Key Cryptanalysis of the Full AES-192 and AES-256[END_REF] and k 4 [START_REF] Mendel | The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl[END_REF], which are bytes of L 3 . Thus, we can merge L 0 and L 3 in a list L 0,3 containing 2 16 elements. Then, we construct the list L 0,2,3 containing 2 24 elements of L 0,3 × L 2 . Finally, from bytes of L 0,2,3 , we can compute:

3z 5 [11] := k 4 [2] + S(k 5 [15]) + k 4 [6] + k 4 [10] + z 5 [8] + z 5 [9] + 2z 5 [10] + x 6 [10], (12) z 5 [14] + k 4 [3] := S(k 5 [12]) + k 4 [7] + k 4 [11] + k 4 [15] + 3z 5 [12] + z 5 [13] + 2z 5 [15] + x 6 [15]. (13)
As a consequence, we expect only one element of L 1 to satisfy those two byte conditions and so, we obtain 2 24 solutions for the middle rounds. All in all, this yields to a distinguisher with a time complexity around 2 24 and a memory requirement around 2 16 using the same trick given in Section 3.3.

Conclusion

In this paper, we study the Advanced Encryption Standard and show how to find a pair of messages and a key that satisfy some property a lot more efficiently than a generic attack based on the birthday paradox for both AES-128 and AES-256. Our new results improve the previous claimed ones by reaching very practical complexities, and give new insights of the open-key model for block ciphers, and hash functions based on block ciphers.

On AES-128, we show efficient distinguishers for versions reduced to seven and eight rounds, and verified in practice that they indeed work by implementing the actual attacks. We describe precisely the algorithms to get the valid inputs, and by applying the same strategy, we deduce similar results for AES-256. Namely, we get efficient distinguishers on versions reduced to seven, eight and nine rounds.

A Solution for the 7-round truncated differential characteristic on AES-128 B Solution for the 8-round truncated differential characteristic on AES-128

Table 3: Example of a pair of messages (m, m ′ ) that conforms to the 8-round truncated differential characteristic for AES-128 of Section 3.3. The master key found by the attack is:

98C45623 6CA00686 301E836D 614DFAB0. The lines in this array contains the values of two internal states before entering the corresponding round, as well as their difference.

Round m m ′ m ⊕ m ′ Init. 9588B342 D43D04D4 AB298AE1 E43687DB 0B88B342 D46904D4 AB29D0E1 E4368728 9E000000 00540000 00005A00 000000F3 0 0D4CE561 B89D0252 9B37098C 857B7D6B 934CE561 B8C90252 9B37538C 857B7D98 9E000000 00540000 00005A00 000000F3

C Probability of success

We are interested in the probability that the intersection of four or five subsets of {1, . . . , 255} each of size 128 being empty.

To evaluate it, let P denote the set of subsets X ⊂ {1, . . . , 255} such that |X| = 128. We also define:

⊓ ⊔

Using Maple, we found that the probability of failure of the distinguisher described in Section 3.

Figure 1 :

 1 Figure 1: An AES round applies MC • SR • SB • AK to the state. There are Nr = 10 rounds in AES-128.

Figure 2 :

 2 Figure 2: Key schedules of the variants of the AES (AES-128 and AES-256) -Naming of bytes in a state.

Figure 3 :

 3 Figure 3: Assuming ni ≤ no, the attacker searches for a pair of input to the random permutation F k differing in ni known byte positions such that the output differs in no known byte positions. A gray cell indicates a byte with a truncated difference.

Figure 4 :

 4 Figure 4: The 7-round truncated differential characteristic used to distinguish the AES-128 from a random permutation. Black bytes are active, white bytes are not.

Figure 5 :

 5 Figure 5: The 7-round distinguishing attack focuses of the middle rounds. Black bytes have known values and differences, gray bytes have known values, hatched bytes have known differences and white bytes have unknown values and/or differences.

Figure 6 :

 6 Figure 6: Differences around the SubBytes layer of round 3: each ∆j is fixed, whereas the δi are yet to be determined.

Figure 7 :

 7 Figure 7: The 7-round distinguishing attack focuses of the middle rounds. Black bytes have known values and differences, gray bytes have known values, hatched bytes have known differences and white bytes have unknown values and/or differences.

Figure 8 :

 8 Figure 8: Generating a compatible key: gray bytes are known, and numbers indicate the order in which we guess or determine the bytes.

Figure 9 :

 9 Figure 9: The 8-round truncated differential characteristic used to distinguish the AES-128. Black bytes are active, white bytes are not.

Figure 10 :

 10 Figure 10: Black bytes have known values and differences, hatched bytes have known differences and white bytes have unknown values and/or differences.

Figure 11 :

 11 Figure 11: Black bytes have known values and differences, gray bytes have known values, hatched bytes have known differences and white bytes have unknown values and/or differences.

Figure 12 :

 12 Figure 12: Generating a compatible key: gray bytes are known, and numbers indicate the order in which we guess or determine the bytes.

TProperty 2

 2 (n, k) := {(X 1 , . . . , X n ) ∈ P n | |X 1 ∩ . . . ∩ X n | = k} for n ≥ 1, k ≥ 0.In others words, |T (n, k)|/|P n | is the probability that the intersection of n elements from P has a size equal to k. The cardinality of T (n, k) satisfies the following recurrence relation:|T (1, k)| = |P| if k = 128, 0 otherwise |T (n + 1, k)| = 128 l=k |T (n, l)| l k 255-l 128-k for n ≥ 1, k ≥ 0.Proof. First, we note that we can partition P n by the sets:T (n, Y ) := {(X 1 , . . . , X n ) ∈ P n | X 1 ∩ . . . ∩ X n = Y } for any subset Y ⊂ {1, . . . , 255}.Then, we have:|T (n + 1, k)| = Y | {(X 1 , . . . , X n+1 ) ∈ T (n, Y ) × P | |Y ∩ X n+1 | = k} | = Y |T (n, Y )| × | {X ∈ P | |Y ∩ X| =k} | If we fix a set Y ⊂ {1, . . . , 255}, then a set X ∈ P such that |X ∩ Y | = k is obtained by choosing k elements in Y and 128 -k elements in Y c . As a consequence, we obtain:|T (n + 1, k)| = Y |T (n, Y )| (n, Y )|Finally, we remark that {T (n, Y )} |Y |=l is a partition of T (n, l) and thus:|T (n + 1, k)| =

3 ≈

 3 0.04%.

Table 1 :

 1 Comparison of our results to previous ones on reduced-round distinguishers of the AES-128 in the open-key model. Results from[START_REF] Biryukov | Related-Key Cryptanalysis of the Full AES-192 and AES-256[END_REF] are not mentioned since we do not consider related-keys in this paper. Claimed by the authors as a very inaccurate estimation of the [ideal] complexity.

	Target	Model	Rounds	Time	Memory	Ideal	Reference
		Known-key	7	2 56	-	2 58 ⋆	[9]
		Known-key	7	2 24	2 16	2 64	[12]
		Single-chosen-key	7	2 22	-	2 64	[3]
	AES-128	Single-chosen-key	7	2 8	2 8	2 64	Section 3.2
		Known-key	8	2 48	2 32	2 64	[8]
		Single-chosen-key	8	2 44	-	2 64	[3]
		Single-chosen-key	8	2 24	2 16	2 64	Section 3.3
		Single-chosen-key	7	2 8	2 8	2 64	Section 4.1
	AES-256	Single-chosen-key	8	2 8	2 8	2 64	Section 4.2
		Single-chosen-key	9	2 24	2 16	2 64	Section 4.3
	⋆

Table 2 :

 2 Example of a pair of messages (m, m ′ ) that conforms to the 7-rounds truncated differential characteristic for AES-128 of Section 3.2. The master key found by the attack is: 93CA1344 10A7EBDF B659C8AF ECC59699. The lines in this array contains the values of two internal states before entering the corresponding round, as well as their difference.

	Round	m	m ′	m ⊕ m ′
	Init. E5FC5DFE 79A851F7 7EB9E366 51C3D9C5 F8FC5DFE 79C951F7 7EB96566 51C3D96E 1D000000 00610000 00008600 000000AB
	0	76364EBA 690FBA28 C8E02BC9 BD064F5C 6B364EBA 696EBA28 C8E0ADC9 BD064FF7 1D000000 00610000 00008600 000000AB
	1	65CC94D1 85BE1AD3 F3D75BF1 ACCBB8BD 8DCC94D1 85BE1AD3 F3D75BF1 ACCBB8BD E8000000 00000000 00000000 00000000
	2	E93319CD 88F41390 10623230 F66BFBAD C92309FD 88F41390 10623230 F66BFBAD 20101030 00000000 00000000 00000000
	3	89C79074 E09E6F44 F1DBAB2F F984FCC4 1404532A 09774F8D 24BF1AFA CD551921 9DC3C35E E9E920C9 D564B1D5 34D1E5E5
	4	867A12E6 BF19139C 1C848362 400030D3 047A12E6 BF5B139C 1C847C62 400030D7 82000000 00420000 0000FF00 00000004
	5	84606BEA 0E22D904 3BF29061 9F454807 4B606BEA 0E22D904 3BF29061 9F454807 CF000000 00000000 00000000 00000000
	6	FF867544 274436AF 75ECC287 A6BF72F6 3C6A996B 274436AF 75ECC287 A6BF72F6 C3ECEC2F 00000000 00000000 00000000
	End C49E4CB3 0C944043 D5ED6D3B 247E3843 2563B1AF 68F0EC8B A6788B48 EEF27E05 E1FDFD1C 6464ACC8 7395E673 CA8C4646

where both K and D are {0, 1} 128 in the case of AES-128.

By compatible, we mean that we can find at least a pair of values that conforms to the differential transition. In the case of the AES S-Box, for a random differential transition δ → δ ′ , this is known to be possible with probability close to 1/2.

In that case, the truncated differential characteristic is thus the one from Figure9.