Vincent Monchiet
email: vincent.monchiet@u-pem.fr

Nicolas Auffray
email: nicolas.auffray@u-pem.fr

Julien Yvonnet

Strain-gradient homogenization: a bridge between the asymptotic expansion and quadratic boundary condition methods

Keywords: Strain Gradient Elasticity, Homogenization, Quadratic Boundary Conditions, Asymptotic Expansion, Composite Material

In this paper we deal with the determination of the strain gradient elasticity coefficients of composite material in the framework of the homogenization methods. Particularly we aim to eliminate the persistence of the strain gradient effects when the method based on quadratic boundary conditions is considered. Such type of boundary conditions is often used to determine the macroscopic strain gradient elastic coefficients but leads to contradictory results, particularly when a RVE is made up of a homogeneous material. The resulting macroscopic equivalent material exhibits strain gradient effects while it should be expected of Cauchy type. The present contribution is to provides new relationship to correct the approach based on the quadratic boundary condition. To this purpose, we start from the asymptotic homogenization approach, we establish a connection with the method based on quadratic boundary conditions and we highlight the correction required to eliminate the persistence of the strain gradient effects. An application to a composite with fibers is provided to illustrate the method.

Introduction

The derivation of strain gradient elasticity theory in the framework of homogenization approaches has been the subject of intense research during the last years but, in fact, has begun earlier with the works of Diener et al. [START_REF] Diener | Bounds for the non-local effective properties of random media[END_REF][START_REF] Diener | Bounds for the non-local effective properties of random media ii[END_REF][START_REF] Diener | Bounds on the non-local effective elastic properties of composites[END_REF]. Starting from the variational principles of Hashin-Shtrikmann [START_REF] Hashin | On some variational principles in anisotropic and nonhomogeneous elasticity[END_REF][START_REF] Hashin | A variational approach to the theory of the elastic behavior of polycrystals[END_REF], Dederichs and Zeller [START_REF] Dederich | Variational treatment of the elastic constants of disordered materials[END_REF] and Kroener and Koch [START_REF] Kröner | Effective properties of disordered materials[END_REF] derived new bounds for the elastic coefficients when a random medium is subjected to non homogeneous mean fields. As a consequence the homogenized elastic coefficients depend on the wave vector of the mean field and, due to the emergence of internal lengths, the macroscopic behavior turns out to be non-local. The link with strain-gradient elasticity has been established later by [START_REF] Drugan | A micromechanics-based nonlocal constitutive equation and estimates of representative volume element size for elastic composites[END_REF] who assumed a polynomial representation for the mean field. By doing so, the overall behavior shows dependence on the gradient(s) of the macroscopic strain and, based on the usual energy principle, the authors derive the elastic coefficients of the Toupin [START_REF] Toupin | Elastic materials with couple-stresses[END_REF] and Mindlin [START_REF] Mindlin | Micro-structure in linear elasticity[END_REF] strain-gradient model. However, such an approach only provides bounds for the higher-order elastic coefficients and not their exact values, and is restricted to some particular microstructures (examples can be found in [START_REF] Drugan | Micromechanics-based variational estimates for a higherorder nonlocal constitutive equation and optimal choice of effective moduli for elastic composites[END_REF][START_REF] Drugan | Two exact micromechanics-based nonlocal constitutive equations for random linear elastic composite materials[END_REF]). Strain gradient elasticity models have also been derived using asymptotic series expansion methods. Periodic homogenization approaches have been introduced and developed by Auriault and Sanchez-Palencia [START_REF] Auriault | Study of macroscopic behavior of a deformable porous medium[END_REF], Bensoussan et al. [START_REF] Bensoussan | Asymptotic Analysis for Periodic Structures[END_REF], Sanchez-Palencia [START_REF] Sanchez-Palencia | Nonhomogeneous Media and Vibration Theory[END_REF], Suquet [START_REF] Suquet | Plasticité et homogénéisation[END_REF]... They are based on the introduction of a small parameter, the scale factor, and the determination of the solution by means of polynomial expansion series in power of this small parameter. By accounting for the second-order term of the series, Bakhvalov and Panasenko [START_REF] Bakhvalov | Homogenization: Averaging processes in periodic media[END_REF], Gambin and Kroener [START_REF] Gambin | High order terms in the homogenized stressstrain relation of periodic elastic media[END_REF], Boutin [START_REF] Boutin | Microstructural effects in elastic composites[END_REF], Triantafyllidis and Bardenhagen [START_REF] Triantafyllidis | The influence of scale size on the stability of periodic solids and the role of associated higher order gradient continuum models[END_REF] found that the local solution exhibits a dependence with the macroscopic strain gradient (and also higher-order derivatives of the macroscopic strain gradient when accounting for higher-order local solutions). The connection with the Toupin and Mindlin strain gradient elasticity model has been really established by Smyshlyaev and Cherednichenko [START_REF] Smyshlyaev | On rigorous derivation of strain gradient effects in the overall behaviour of periodic heterogeneous media[END_REF], Peerlings and Fleck [START_REF] Peerlings | Numerical analysis of strain gradient effects in periodic media[END_REF], Tran et al. [START_REF] Tran | A micromechanics-based approach for the derivation of constitutive elastic coefficients of straingradient media[END_REF]. The strain gradient elasticity coefficients are computed by solving unit cell problems with Periodic Boundary Conditions (PBC). The first problem provides the fundamental solution and, by only keeping this term in the series expansion, the macroscopic description of the material remains of Cauchy type. Higher-order cell problems introduce the microstructural effects, i.e. the macroscopic description depends on an internal length scale that is characteristic of the microstructure and of the dependence of the elastic relationship with higher order derivatives of the macroscopic strain. The numerical implementation of the higher-order cell problems and the determination of strain-gradient elasticity coefficients have been already addressed in [START_REF] Peerlings | Numerical analysis of strain gradient effects in periodic media[END_REF] using the Finite Element Method (FEM) or in [START_REF] Tran | A micromechanics-based approach for the derivation of constitutive elastic coefficients of straingradient media[END_REF] considering iterative schemes based on Fast Fourier Transform (FFT). It has been observed that when the scaling of elastic coefficients of the constituents have the appropriate order with respect to the scale factor, the effective material may exhibit strong strain gradient effects. This effect has been evidenced in the case of elastic composites reinforced by highly rigid slender inclusions by Pideri and Seppecher [START_REF] Pideri | Un résultat d'homogénéisation pour un matériau élastique renforcé périodiquement par des fibres élastiques de très grande rigidité[END_REF][START_REF] Pideri | A second gradient material resulting from the homogenization of an heterogeneous linear elastic medium[END_REF] and Boutin and Soubestre [START_REF] Boutin | Generalized inner bending continua for linear fiber reinforced materials[END_REF]. More recently, it has been demonstrated that the effective elastic energy of lattice materials having soft modes of deformation can be of generalized type [START_REF] Alibert | Truss modular beams with deformation energy depending on higher displacement gradients[END_REF]. Some general results have been obtained in [START_REF] Abdoul-Anziz | Strain gradient and generalized continua obtained by homogenizing frame lattices[END_REF][START_REF] Abdoul-Anziz | Homogenization of periodic graphbased elastic structures[END_REF] combining asymptotic analysis and Γ-convergence method. However even if a method to determine the higher-order parameters was proposed in this last reference it fails when the first order elasticity is not degenerated. Another attractive method for the computation of strain-gradient elasticity coefficients is based on the use of the Quadratic Boundary Conditions (QBC) on the Representative Volume Element (RVE). It generalizes the classic approach based on Uniform Strain Boundary Conditions (USBC) by applying a displacement that has a quadratic dependence with the position vector. The enforcing term is the macroscopic gradient of strain (or equivalent the macroscopic double gradient of displacement). The method is generally attributed to Besdo et al. [START_REF] Besdo | Inelastic behaviour of plane frictionless blocksystems described as Cosserat media[END_REF][START_REF] Besdo | Zur Modellierung von Verbundmaterialien als homogenes Cosserat -Kontinuum[END_REF] but has been really introduced in the context of homogenization by Gologanu et al. [START_REF] Gologanu | Recent extensions of Gurson's model for porous ductile metals[END_REF] who derived the strain-gradient version of the Gurson model [START_REF] Gurson | Continuum theory of ductile rupture by void nucleation and growth. Part I. -Yield criterion and flow rules for porous ductile media[END_REF]. As already mentioned in [START_REF] Fleck | Strain gradient plasticity[END_REF], the results are however somewhat surprising in that the dominant effect of strain-gradient effects is not influenced by the void volume fraction or void spacing and the strain gradient effects persist even when the void volume fraction tends to zero. Indeed, the strain gradient effects are due to the presence of a microstructure at a lower scale and when the volume fraction tends to zero, the solid becomes homogeneous and no microstructural effects should be observed. Later, the method of Gologanu et al. [START_REF] Gologanu | Recent extensions of Gurson's model for porous ductile metals[END_REF] has been applied in the context of elasticity by Zybell et al. [START_REF] Zybell | Constitutive equations for porous plane-strain gradient elasticity obtained by homogenization[END_REF] with the same result: when radii of the inclusions tend to zero, the resulting microstructural effects still persist instead of vanishing as they should. The method has been later used in the case of elasticity and non linear constituents [START_REF] Forest | Mechanics of generalized continua: construction by homogenization[END_REF][START_REF] Forest | Generalized continua and non-homogeneous boundary conditions in homogenisation methods[END_REF][START_REF] Bouyge | A micromechanically based couple-stress model of an elastic two-phase composite[END_REF][START_REF] Bouyge | A micromechanically based couple-stress model of an elastic orthotropic two-phase composite[END_REF][START_REF] Kouznetsova | Multi-scale constitutive modeling of heterogeneous materials with gradient enhanced computational homogenization scheme[END_REF][START_REF] Kouznetsova | Multi-scale second-order computational homogenization of multi-phase materials: a nested finite element solution strategy[END_REF] but in each case, the persistence of the strain gradient is retrieved for a homogeneous material at the local scale. This has been again reported in [START_REF] Yuan | A micromechanical approach of nonlocal modeling for media with periodic microstructures[END_REF] who suggested that the method surely over evaluates the macroscopic energy density and probably exaggerates the strain gradient effects. It is important to notice that such observation does not concern the periodic homogenization based on asymptotic series expansion. Indeed, when the medium is homogeneous at the local scale, the source term in the second order cell problem, which depends only on the fluctuation, vanishes and the macroscopic behavior remains Cauchy elastic. Note that another approach based on QBC has been used by Bigoni and Drugan [START_REF] Bigoni | Analytical derivation of Cosserat moduli via homogenization of heterogeneous elastic materials[END_REF], Bacca et al. [START_REF] Bacca | Mindlin second-gradient elastic properties from dilute two-phase Cauchy-elastic composites. Part I: Closed form expression for the effective higher-order constitutive tensor[END_REF][START_REF] Bacca | Mindlin second-gradient elastic properties from dilute two-phase Cauchy-elastic composites. Part II: Higher-order constitutive properties and application cases[END_REF]. However their method is quite different in the sense that it is based on a small perturbation of the elastic properties and by approximating its effects on the macroscopic behavior by a strain gradient term. The approach is more related to the statistical method developed in [START_REF] Drugan | A micromechanics-based nonlocal constitutive equation and estimates of representative volume element size for elastic composites[END_REF].

The paper is organized as follows. To evidence the issue with the QBC based method, we start from the periodic homogenization with the asymptotic series expansion and we establish the connection between the two methods. To this end, we give a brief overview of the homogenization method based on asymptotic series expansion in section 3. The first two unit cell problems, that lead to the reference solution and the first corrector, are detailed. In section 4, using an appropriate change of variables, a bridge between the two homogenization procedures is established. In section 5, we discuss the results and we provide a new method to determine correctly the strain gradient elastic coefficients in the QBC based approach. Finally, in section 6, we propose an illustration for a composite with fibers. FEM computations with QBC are compared to FFT simulations for the problem with PBC.

Tensorial notations:

Vectors, second order and third order tensors are denoted by bold letters, usually lower case for microscopic quantities u, and upper case for the associated macroscopic ones U . Fourth-and higher-order tensors are denoted by blackboard letters such as C. ⊙ n stands for the generalized dot product between two tensors of order ≥ n over n indices. For example, considering the second order tensors A and B we have A ⊙ 2 B = A ij B ij and for third order tensors S and T we have S ⊙ 3 T = S ijk T ijk . The gradient operator with respect to the variable α is denoted by ∇ α and the divergence operator with respect to α by div α . By extension ε α is the symmetric gradient operator defined as:

ε α (v) = 1 2 (∇ α v + ∇ T α v) ( 1 )
The averaging of a tensorial quantity T over a spatial domain V is denoted by:

< T > V = 1 |V | V T dV (2)
where (A i ) T represents the transpose of A i obtained by the permutation of the two first and the i + 2 last indices: (A 0 ) T ijpq = A 0 pqij and (A 1 ) T ijpqr = A 1 pqrij .

3 Brief review of the periodic homogenization approach Asymptotic methods in periodic homogenization, initially introduced by Sanchez-Palencia [START_REF] Sanchez-Palencia | Comportements local et macroscopique d'un type de milieux physiques hétérogènes[END_REF], Bensoussan et al. [START_REF] Bensoussan | Asymptotic Analysis for Periodic Structures[END_REF], have been later considered by Bakhvalov and Panasenko [START_REF] Bakhvalov | Homogenization: Averaging processes in periodic media[END_REF], Gambin and Kroener [START_REF] Gambin | High order terms in the homogenized stressstrain relation of periodic elastic media[END_REF], Boutin [START_REF] Boutin | Microstructural effects in elastic composites[END_REF] to evaluate the deviation from the standard elastic description. The rigorous convergence of the method in the classical situation has been demonstrated by Allaire in [START_REF] Allaire | Homogenization and two-scale convergence[END_REF]. In this section, only the main and necessary results are recalled, all the details can be found in the above cited papers. Consider the composite structure occupying an open set Ω of R d whose characteristic length is L. As a periodic composite material, the (macro) domain Ω is supposed to be paved with unit cells. The domain of the elementary cell is denoted by ω and h indicates the characteristic length of this underlying microstructure (see Fig. 1). The main feature of the asymptotic expansion method consist in the introduction of two space variables x = X/L and y = X/h where L and h are two characteristic lengths of the macro and the microstructure. The separation ratio between the two scales of the problem is measured by the scale factor ϵ = h/L. The elastostatic problem can be formulated as follows:

⎧ ⎪ ⎨ ⎪ ⎩ div(σ(x, y)) = f (x, y) σ(x, y) = C(y) : ε(x, y) (3)
with some boundary conditions on ∂Ω. In this formulation it is worth noting that the elasticity tensor is a periodic function of y with period h, meaning that the elastic properties are considered as macroscopically homogeneous (no global dependence on x) but varying at the scale of the microstructure. The principle of the asymptotic method consists to search the solution in term of power series in ϵ:

u(x, y) = ∞ n=0 ϵ n u n (x, y) ( 4 )
in which each term u n (x, y) is periodic with respect to y with period h. It involves the following series expansions for the strain and stress fields:

ε(x, y) = ϵ -1 ε y (u 0 (x, y)) + ∞ n=0 ϵ n [ε x (u n (x, y)) + ε y (u n+1 (x, y))] (5)
σ(x, y) = ∞ n=0 ϵ n σ n (x, y) (6)
It has been demonstrated that the displacement u 0 (x, y) is independent of y and only depends on x. It can be interpreted as a macroscopic displacement U (x). The higher-order terms u n≥1 (x, y), which are the fluctuations due to the local heterogeneity, are determined by solving elementary cell problems over ω. For instance, the displacement u 1 (x, y) is solution of the set of equations:

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ div y (σ 0 (x, y)) = 0 σ 0 (x, y) = C(y) : ε 0 (x, y) ε 0 (x, y) = ε y (u 1 (x, y)) + E(x) ε y (u 1 (x, y)) = 1 2 (∇ y u 1 (x, y) + ∇ T y u 1 (x, y)) (7)
with the following periodic boundary conditions over the unit cell ω

u 1 y-periodic, σ 0 .n y-antiperiodic (8)
The solution at first order linearly depends on the applied macroscopic strain

E(x) = 1 2 (∇ x U (x) + ∇ T x U (x))
. The localization rule is defined in the form:

ε 0 (x, y) = A 0 (y) ⊙ 2 E(x) (9)
Higher-order terms of the series expansion account for the microstructural effects which are expected when the scale factor ϵ is not small enough. By neglecting all higher-order terms of the series, the macroscopic description is of Cauchy type. Consider the first higher-order term of the series given by the displacement u 2 . It is determined by solving the following unit cell problem:

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ div y (σ 1 (x, y)) + div x (σ 0 (x, y)-< σ 0 (x, y) > ω ) = 0 σ 1 (x, y) = C(y) : ε 1 (x, y) ε 1 (x, y) = ε y (u 2 (x, y)) + ε x (u 1 (x, y)) ε y (u 2 (x, y)) = 1 2 (∇ y u 2 (x, y) + ∇ T y u 2 (x, y)) ε x (u 1 (x, y)) = 1 2 (∇ x u 1 (x, y) + ∇ T x u 1 (x, y)) (10)
where the periodic boundary conditions ( 8) are still considered for the displacement u 2 and the stress σ 1 . The loading parameters are the solution of the unit cell problem at previous order: the displacement u 1 and the stress σ 0 . Since these fields linearly depend on the applied macroscopic strain, when we apply the differential operator "div x ()" and "ε x ()", these terms linearly depend on the macroscopic gradient of strain ∇ x E. As a consequence, the displacement field u 2 linearly depends on the macroscopic gradient of strain ∇ x E.

The localization rule for the first corrector can be read in the form:

ε 1 = A 1 (y) ⊙ 3 ∇ x E(x) (11)
An energy based upscaling approach can be employed to determine the Mindlin strain gradient elasticity tensor following Tran et al. [START_REF] Tran | A micromechanics-based approach for the derivation of constitutive elastic coefficients of straingradient media[END_REF]. For instance, if only the two first terms are kept in the series expansion for the strain, the latter reads ε = ε 0 + ϵε 1 in which ε 0 and ε 1 linearly depend on the macroscopic strain and gradient of strain respectively (see Eq. ( 9) and Eq. ( 11)). As a consequence the macroscopic elastic energy W computed with the first two terms of the series reads:

W = 1 2 < σ : ε > ω = 1 2 E ⊙ 2 C 0,0 ⊙ 2 E + ϵE ⊙ 2 C 0,1 ⊙ 3 ∇ x E + 1 2 ϵ 2 ∇ x E ⊙ 3 C 1,1 ⊙ 3 ∇ x E (12)
in which the tensors C i,j are defined by:

C i,j =< (A i (y)) T ⊙ 2 C(y) ⊙ 2 A j (y) > ω (13)
In the expression of the macroscopic elastic energy W , the macroscopic gradient of strain ∇ x E can be replaced by L∇ χ E where χ = xL is the true macroscopic space variable (x being the dimensionless macroscopic space variable). Therefore, the macroscopic energy density becomes:

W = 1 2 E ⊙ 2 C 0,0 ⊙ 2 E + hE ⊙ 2 C 0,1 ⊙ 3 ∇ χ E + 1 2 h 2 ∇ χ E ⊙ 3 C 1,1 ⊙ 3 ∇ χ E (14)
which depends on the size h which defines the period of the microstructure. It must be pointed out that the present method is based on a truncated description that is certainly questionable. By keeping only the first two terms of the series, we just approximate the solution, and this approximation is quite uncontrolled. The reader could refer to the discussion in [START_REF] Boutin | Homogenization Methods and Generalized Continua in Linear Elasticity[END_REF].

4 Reformulation of cell problems with linear and quadratic boundary condition

First order problem

Consider the first order problem, defining the displacement u 1 (see equations ( 7) with ( 8)). Let us apply the following change of variable:

u 1 = u L -E(x).y, σ 0 = σ L (15)
With this definition, the displacement contains (i) the periodic part u L due to the local heterogeneities (the latter vanishes for a homogeneous material at the local scale) and (ii) a linear displacement E(x).y. With this change of variable, the first local problem becomes:

⎧ ⎪ ⎨ ⎪ ⎩ div y (σ L ) = 0 σ L = C(y) : ε y (u L ) (16)
The usual homogenization problem with the uniform strain boundary condition is retrieved if we replace the periodic condition for u 1 by the condition u 1 = 0 on the boundary ∂ω. This leads to:

u L = E.y (17)
that is also called linear condition in the sense that u L linearly depends on the space variable y. The solution of the problem can be read:

ε L = A L (y) ⊙ 2 E ( 18
)
where A L (y) is the fourth order localisation tensor.

Second order problem

We aim to provide the same analogy for the second order problem. Let us start from the set of Eqs. [START_REF] Bensoussan | Asymptotic Analysis for Periodic Structures[END_REF]. Let us recall that the stress field σ 0 is divergence-free with respect to the coordinate y (see Eq. ( 7) ). As a consequence, this stress satisfies:

∂σ 0 ij ∂x j = ∂ ∂y j ∂σ 0 ij ∂x k y k (19)
Let us introduce the stress σ Q defined by:

σ Q = σ 1 + ∂σ 0 ∂x k y k (20)
Owing to Eq. ( 19) and the first equation in [START_REF] Bensoussan | Asymptotic Analysis for Periodic Structures[END_REF], we deduce that:

div y (σ Q ) = div x (< σ L > V ) ( 2 1 )
Note that the term on the right-end of the equality in Eq. ( 21) is constant at the local scale and can be interpreted as a constant body force. Now, replacing in Eq. ( 20) the expressions of σ 0 (cf. second equation in ( 7)) and σ 1 (cf. second equation in ( 10)), we obtain:

σ Q = C(y) : (ε y (u 2 ) + ε x (u 1 )) + ∂ ∂x k C(y) : (ε y (u 1 ) + E(x)) y k (22)
Let us now use in the above equation the following property:

∂ε y (u 1 ) ∂x k y k = ε y ∂u 1 ∂x k y k -ε x (u 1 ) ( 2 3 )
It leads to:

σ Q = C(y) : ε y u 2 + ∂u 1 ∂x k y j + ∇ x E(x).y (24)
We also introduce the displacement u Q defined by:

u Q = u 2 + ∂u 1 ∂x k y k + 1 2 ∇ 2 x U : (y ⊗ y) ( 2 5 )
where ∇ 2

x U is the double gradient of macroscopic displacement. The components of ∇ 2

x U are related to that of the macroscopic gradient of strain ∇ x E by:

E ij,k = 1 2 (U i,jk + U j,ik ) ⇔ U i,jk = E ik,j + E ij,k -E jk,i (26)
where E ij,k are the components of the macroscopic gradient of strain ∇ x E and U i,jk are the components of the double gradient of the macroscopic displacement, ∇ 2 x U . The components U i,jk are invariant by any permutation of the indices j and k, while E ij,k is invariant by any permutation of the indices i and j. Both tensors depend on 18 independent coefficients in R 3 , and 6 in R 2 . Owing to Eq. ( 25), Eq. ( 24) can be written as:

σ Q = C(y) : ε y (u Q ) ( 2 7 )
Following the previous section we now aim to identify the relation between the second order problem coming from the asymptotic homogenization and the problem with the quadratic boundary condition (QBC). To this end, we replace the periodic boundary conditions for the displacements u 1 and u 2 by the conditions u 1 = 0 and u 2 = 0 on ∂ω. Therefore, we observe that the displacement u Q satisfies:

u Q = 1 2 ∇ 2 x U : (y ⊗ y) ∀y ∈ ∂ω (28)
To sum up, the second-order problem can be summarized as:

div y (σ Q ) = div x (< σ L > V ) ∀y ∈ ω (29)
σ Q = C(y) : ε y (u Q ) ∀y ∈ ω (30)
u Q = 1 2 ∇ 2 x U : (y ⊗ y) ∀y ∈ ∂ω (31)
with σ L computed from the first-order problem (with the linear boundary condition). This problem is almost equivalent to the one used by many authors to evaluate the strain gradient elastic properties [START_REF] Forest | Mechanics of generalized continua: construction by homogenization[END_REF][START_REF] Bouyge | A micromechanically based couple-stress model of an elastic two-phase composite[END_REF][START_REF] Bouyge | A micromechanically based couple-stress model of an elastic orthotropic two-phase composite[END_REF][START_REF] Kouznetsova | Multi-scale constitutive modeling of heterogeneous materials with gradient enhanced computational homogenization scheme[END_REF][START_REF] Kouznetsova | Multi-scale second-order computational homogenization of multi-phase materials: a nested finite element solution strategy[END_REF] but differs by the presence of the body force term div x (< σ L > V ) in the equilibrium equation [START_REF] Diener | Bounds for the non-local effective properties of random media[END_REF].

The localization rule associated with the problem corresponding to the QBC is:

ε Q = A Q (y) ⊙ 3 ∇ x E (32)

Discussion

Let us first give the relation that exists between the strain field ε y (u Q ) computed with the QBC and the first corrector ε 1 . For the sake of simplicity, ε L will stand for ε y (u L ) and ε Q for ε y (u Q ). The first corrective term for the strain is ε 1 that reads (owing to Eq. ( 5)):

ε 1 = ε y (u 2 ) + ε x (u 1 ) (33)
Owing to Eq. ( 25), the displacement u 2 can be read:

u 2 = u Q - ∂u 1 ∂x k y k - 1 2 ∇ 2 x U : (y ⊗ y) (34)
Replacing in Eq. ( 33) the displacements u 1 and u 2 by Eq. ( 15) and Eq. ( 34) respectively, we deduce after some elementary manipulations:

ε 1 = ε Q - ∂ε L ∂x k y k (35)
By multiplying the above expression by the elastic tensor C(y), we obtain a similar expression for the stress field:

σ 1 = σ Q - ∂σ L ∂x k y k (36)
In the previous relations, the solution of the problem with QBC provides the strain ε Q and the stress σ Q while ε 1 and σ 1 are the first correctors to the strain and the stress obtained by the asymptotic expansion method. As obvious from formula, the correctors are obtained by eliminating from ε Q and σ Q an elastic part represented by the tensors (∂ε L )/(∂x k )y k and (∂σ L )/(∂x k )y k in order to keep only the gradient effects. Hence, the solution of the unit cell problem with the QBC cannot be interpreted as the first corrector. Further, as previously discussed, the first corrector vanishes as soon as the material is homogeneous at the local scale preventing spurious persistence of strain-gradient effects at the macroscopic scale. However, neither ε Q nor σ Q are null for a homogeneous material. To understand what is at work, consider the case of a homogeneous material in the unit cell. In such a case, tensor C(y) is constant, its spatial dependence with respect to y drops down in the notation and can be just denoted C. The solution at zeroth-order, corresponding to linear boundary condition [START_REF] Bouyge | A micromechanically based couple-stress model of an elastic two-phase composite[END_REF], is ε L = E and the stress σ L = C : E. The solution with applied macroscopic gradient of strain at first-order must satisfy the QBC ( 28) and can then be taken into the form:

u Q = 1 2 ∇ 2 x U : (y ⊗ y), ∀y ∈ ω (37)
everywhere in the unit cell. The associated strain and stress fields are ε Q = ∇ x E.y and σ Q = C : ∇ x E.y, respectively. It is observed that the stress is linear with the coordinate y. Getting back to the linear momentum equation [START_REF] Diener | Bounds for the non-local effective properties of random media[END_REF], it can directly be verified that the former stress is statically admissible as soon as a constant body force term div x (σ ′ ) with σ L = C : E is considered. This particular case illustrates the importance of the body force term in the equilibrium equation [START_REF] Diener | Bounds for the non-local effective properties of random media[END_REF], without it the first-order cell problem would not have ε Q = ∇ x E.y as trivial solution. Now, injecting the solutions ε L = E and ε Q = ∇ x E.y in Eq. ( 35), leads to the vanishing of ε 1 and σ 1 . The physical requirement that first correctors are null for local homogeneous materials is hence satisfied. Note that without the body force "div x (σ Q )", the equilibrium equation reduces to:

C ijkl E kl,j = 0 [START_REF] Peerlings | Numerical analysis of strain gradient effects in periodic media[END_REF] which suggests that all the components of the macroscopic strain-gradient cannot be chosen arbitrarily.

Introducing the localization rules ( 18) and ( 32) in the expression (35) leads to:

ε 1 = [A Q (y) -A L (y) ⊗ y] ⊙ 3 ∇ x E ( 39
)
which also gives the equality:

A 1 (y) = A Q (y) -A L (y) ⊗ y ( 40
)
As a consequence, the components of strain-gradient elastic tensors can be determined from Eq. ( 13), in which the localization tensor A 0 (y) is replaced by A L (y) and A 1 (y) is replaced by A Q (y) -A L (y) ⊗ y.

Application to a composite with fibers

As an illustration purpose, we consider a composite with fibers. The fibers are aligned in the x 3 direction and are periodically distributed in the (x 1 , x 2 ) plane. By R we denote the radius of the fiber and by h the distance between two neighboring fibers (the period). The strain-gradient elastic properties are determined by considering the two kind of boundary conditions, periodic and quadratic. When the periodic boundary conditions are used, the solution is computed with the FFT method provided in [START_REF] Tran | A micromechanics-based approach for the derivation of constitutive elastic coefficients of straingradient media[END_REF]. The solution with quadratic boundary conditions is computed with the Finite Element Method (FEM). The elastic coefficients of the matrix are denoted by E 1 , ν 1 and those of the inclusions are denoted E 2 and ν 2 . The following values are considered for the numerical applications:

E 1 = 1GPa, E 2 = 100GPa, ν 1 = ν 2 = 0.3 ( 4 1
)

Basic results with periodic boundary conditions

The solution for a composite with fibers has been provided in Tran et al. [START_REF] Tran | A micromechanics-based approach for the derivation of constitutive elastic coefficients of straingradient media[END_REF]. In this work, the computations have been performed for one irreducible unit cell. More recently, in Barboura and Li [START_REF] Barboura | Establishment of strain gradient constitutive relations by using asymptotic analysis and the finite element method for complex periodic microstructures[END_REF], the authors claim that the strain gradient elastic coefficients depend on the choice of the unit cell. Particularly, they depend on the number of irreducible cells considered for their evaluation.

In other words, if the calculations are performed on a unit cell containing 1, 4, 9, 16... irreducible cells and with periodic boundary conditions, they lead to different values for the strain gradient elastic coefficients. Our results show that the strain gradient elastic response is independent of the number of periods used for the computation of the strain gradient elastic coefficients.

In order to avoid any confusion, the unit cell is still denoted ω, its dimension along each space direction is still denoted by h. The unit cell can contain multiple periods, i.e. multiple irreducible unit cells denoted ω 0 and having the dimension h 0 . In Fig. 2, we show three unit cells containing 1, 4, 9 irreducible cells. Considering first the case of classic homogenization, the macroscopic elastic coefficients are determined by computing the solution of the first order cell problem given by Eq. ( 7). These coefficients remains unchanged if we consider one or multiple periods for ω. It can be easy proved. Note first that the rapid variable y is obtained by dividing the true space variable χ by the dimension of the unit cell h. As a consequence, for a 2D problem with a squared unit cell, the non dimensional variable vary from -0.5 to 0.5 along each space direction, and this whatever the number of periods considered in the unit cell (ω can contain 1,4,9... irreducible cells). Consider an irreducible cell which paves the unit cell ω and let us denote by Y 0 the position of its center. We introduce the following coordinate change variable y = N(y -Y 0 ) where N is the number of unit cells considered along each space direction. With this definition, the variable y vary from -0.5 to 0.5 in the irreducible cell. The two space variables y and y are illustrated in Fig. By applying in the first order cell problem given by Eq. ( 7) the following change of variables:

1 × 1 2 × 2 3 × 3 1
u 1 (x, y) = 1 N u 1 (x, y) (42)
ε 0 (x, y) = ε 0 (x, y) (43)
σ 0 (x, y) = σ 0 (x, y) (44)
y ′ = N(y -Y 0 ) (45)
we obtain:

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ div y (σ 0 (x, y)) = 0 σ 0 (x, y) = C(y) : ε 0 (x, y) ε 0 (x, y) = ε y (u 1 (x, y)) + E(x) ε y (u 1 (x, y)) = 1 2 (∇ y u 1 (x, y) + ∇ T y u 1 (x, y)) (46)
The equations of the problem then remain unchanged. This confirms that the strain and the stress computed with one or multiple unit cells remain unchanged. As for example, we show in Fig. 4 the distribution of the stress component σ 0 11 , due to the macroscopic strain E 11 = 1, along a horizontal line which passes through the centers of the inclusions (see the dashed line in Fig. 2) in the case of 1, 4 and 9 irreducible cells. It is observed that the solution remains the same for each case. The solution for multiple periods is obtained by the repetition of the solution obtained with one irreducible cells.

-0. As consequence, the classic homogenized elastic coefficients (components of C 0,0 ) also remain unchanged if we make the computations with one or multiple periods. Now, if we consider the higher order problem given by Eq. ( 10) in which we apply the change of variable ( 42)-( 45) for the displacement u 1 , the stress σ 0 and the position vector y, we obtain:

⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ N div y (σ 1 (x, y)) + div x (σ 0 (x, y)-< σ 0 (x, y) > ω ) = 0 σ 1 (x, y) = C(y) : ε 1 (x, y) ε 1 (x, y) = Nε y (u 2 (x, y)) + 1 N ε x (u 1 (x, y)) ε y (u 2 (x, y)) = 1 2 (∇ y u 2 (x, y) + ∇ T y u 2 (x, y)) ε x (u 1 (x, y)) = 1 2 (∇ x u 1 (x, y) + ∇ T x u 1 (x, y)) (47)
It is observed that the problem remains unchanged for 1 unit cell or multiple unit cells if we apply the following change of variables for u 2 , ε 1 and σ 1 :

u 2 (x, y) = 1 N 2 u 1 (x, y) (48)
ε 1 (x, y) = 1 N ε 1 (x, y) (49)
σ 1 (x, y) = 1 N σ 1 (x, y) (50)
As a consequence, the strain ε 1 and the stress σ 1 are the same for multiple periods but their amplitudes are divided by a factor N. This is confirmed in Fig. 5. The distribution of the stress component σ 1 11 due to a prescribed macroscopic gradient of strain E 11,1 = 1 is given for 1, 4 and 9 irreducible cells. It is observed that the amplitude of the stress is divided by a factor 2 in the case of a unit cell with 4 irreducible cells and by a factor 3 for 9 irreducible cells. Since the strain ε 1 and the stress σ 1 are divided by a factor N in the case of a unit cell containing N × N irreducible cells, the corresponding energy is divided by a factor N 2 . As a consequence the sixth order elastic tensor C 1,1 is divided by a factor N 2 . However, let us recall that the relation between the hyperstress and the macroscopic gradient of strain involves the term h 2 C 1,1 in which h = Nh 0 , h 0 being the dimension of the irreducible unit cell. As a consequence, the quantity h 2 C 1,1 = h 2 0 N 2 C 1,1 is independent of the number of periods and can be determined by considering only one irreducible cell. For instance, we provide in Fig. 6 the value of C 1,1 111111 as function of the number of periods. It is observed that the component C 1,1 111111 decreases with the number of periods while the quantity N 2 C 1,1 111111 is independent.

Comparison between PBC and QBC

When the QBC is used, the results for the homogenized elastic properties depend on the number of periods. The FEM-based approach uses the correction with the body force "div x (σ L )". The effective strain-gradient elasticity properties are computed with the modified average rule [START_REF] Bigoni | Analytical derivation of Cosserat moduli via homogenization of heterogeneous elastic materials[END_REF]. The results are provided only for the component 111111 of the sixth-order strain-gradient elasticity tensor and are given in Fig. 7. The variations of the strain gradient elastic component are given as function of the radius of the fiber. The result is compared with that obtained with the periodic boundary condition (and computed with the FFT). It can be observed in Fig. 7 that for R = 0 the component of the strain-gradient elastic coefficient is null, this result clearly shows that the new method eliminates the persistence of spurious strain-gradient effects. It can also be observed that the FEM solution depends on the number of irreducible unit cells in the RVE and, by increasing their number, that the QBC-based solutions converge to FFT-based one. One explanation is that, considering the Saint-Venant principle, the solution at distance from the boundary of the RVE is independent of the choice of the kind of boundary conditions. For a RVE constituted of a large number of irreducible cells, the periodicity is almost recovered for the cells in the bulk. Since there is a high number of strain gradient elastic coefficients, we only present the results for one component. Other coefficients have been computed with the same conclusion: (i) no persistence when the inclusion radius return to zero with QBC and PBC, (ii) the solution with QBC tends to the solution with PBC when we increase the number of irreducible cells. If we deal with periodic composites, the method based on PBC is more accurate. Indeed, the homogenized elastic coefficients are determined by the computations over one irreducible cell while, with the QBC, it requires the computation on multiple periods and the number of irreducible cells must be increased in order to obtain the convergence. Obviously, this allows higher computational requirements. However, the scope of the present paper is to develop a new method based on QBC to deal with non-periodic microstructures.

No examples have been provided in the present paper but applications to the case of non-periodic microstructures have to be considered in a future work. For comparison purpose, we also provide the strain-gradient elastic coefficient computed by the FEM on an irreducible unit cell with the older definition for the elastic energy. The results are provided in Fig. 8 by accounting for the constant body force "div x (σ L )" and in Fig. 9 without the body force. First, in both cases (with or without the body force), the persistence of the straingradient elasticity is observed when the radius of the fibre is R = 0. It must be also noted that, comparatively to the results provided on Fig. 7, the straingradient coefficients computed with the older method largely overestimate the strain-gradient effects. Additionally, the presence of the body force in the equilibrium equation has a significant influence on the value of the straingradient elasticity coefficients.

Conclusion

In this paper, we have provided a unified approach to the determination of the strain-gradient elasticity properties. Two methods have been investigated. The first is based on asymptotic series expansion within the framework of periodic homogenization, the second consider the quadratic condition (QBC) on the boundary of the representative volume element (RVE). A bridge between the two methods has been established and a modification of the QBC-based method has been provided in order to be consistent with the periodic homogenization. The main significant result of the paper is that the new method based on QBC allows to eliminate the persistence of the strain-gradient effects: for a homogeneous material at the local scale the macroscopic description remains of Cauchy type, so that all the components of the strain-gradient elastic tensor must be equal to zero. Strain-gradient effects only appears when the material is heterogeneous at the local scale. This results has been confirmed by the numerical implementation of the two methods in the particular case of a composite material with fibers.

Fig. 1 .

 1 Fig. 1. (a) Heterogeneous structure, (b) unit cell, (c) Equivalent homogeneous strain gradient medium

Fig. 2 .

 2 Fig. 2. Unit cells for the considered numerical computations.

Fig. 3 .

 3 Fig. 3. Definition of the two coordinates y and y. y lies in the unit cell ω, and y lies in an irreducible unit cell ω 0 .

Fig. 4 .

 4 Fig. 4. Distribution of the stress component σ 0 11 , due to the macroscopic strain E 11 = 1, along a horizontal line which passes through the centers of the inclusions.

Fig. 5 .

 5 Fig.5. Distribution of the stress component σ1 11 , due to the macroscopic strain E 11,1 = 1, along a horizontal line which passes through the centers of the inclusions.

Fig. 6 .

 6 Fig. 6. Variations of C 1,1 111111 and N 2 C 1,1 111111 with the number of periods N .

Fig. 7 .

 7 Fig. 7. Variation of the strain-gradient elastic coefficient C 1,1 111111 as function of the ratio R/L. Comparison between the solution with PBC (FFT) and QBC (FEM).

Fig. 8 .Fig. 9 .

 89 Fig. 8. Variation of the strain-gradient elastic coefficient C 1,1 111111 as function of the ratio R/L. Computation including the body force in the equilibrium equation


INTRODUCTION

1.1 Presentation of Inria and the Team SECRET Inria is the main french public research institute in computer science. It is composed with more than 2500 researchers regrouped in 200 project-teams that work in specific advanced areas of digital science. In total, it implies more than 3000 scientists around the globe to meet the challenges of a constant evolving society and economy. Inria has also been supporting more than 160 start-ups, and is closely connected to numerous companies on state of the art problematics. Inria is divided into 8 etablissments implanted in France, among which Inria de Paris, previously located in Rocquencourt.

Team SECRET is a project-team of Inria de Paris, directed by Anne Canteaut and dedicated to symmetric cryptography, code-base cryptography, quantum information theory and post-quantum cryptanalysis. As modern cryptography is in jeopardy because of advanced cryptanalysis and the threat of quantum computers, new cryptographic primitives are being analysed and conceived by researchers of the team. I have mostly worked with my tutor Gaëtan Leurent on symmetric cryptography, but I was able to discuss with all the members of the team about crypto-related issues.

My Work in Inria

I started my internship studying KIASU-BC, a tweakable block cipher designed in 2014 by J. Jean et al. in the TWEAKEY framework [START_REF] Jean | Tweaks and keys for block ciphers: The TWEAKEY framework[END_REF] based on AES-128. I had to go through the entire paper to deeply understand the stakes behind every detail of the primitive. Then I studied existing attacks on the primitive, for example the square attack [START_REF] Dobraunig | Square attack on 7-round kiasu-BC[END_REF], impossible differential and boomerang attacks [START_REF] Dobraunig | Impossible-differential and boomerang cryptanalysis of roundreduced kiasu-BC[END_REF]. I also took a close look to existing attacks on AES-128, because most of the attacks on KIASU-BC are variants of AES attacks. After more than two weeks, I could try to think by myself and started searching for attacks with a pencil and a notebook. Gaëtan Leurent advised me to study forkAES, as it is really close to KIASU-BC, but with a lack of diffusion which could lead to a vulnerability. I read the specifications of ForkAES by E. Andreeva et al. [START_REF] Andreeva | Forking a blockcipher for authentificated encryption of very short messages[END_REF]. They created ForkAES as a primitive belonging to their forkcipher framework, using a block cipher to produce an authentificated encryption for very short messages. In response to this proposal, careful cryptanalysis was performed in "Cryptanalysis of ForkAES" by S. Banik et al. [BBJ + 19]. The authors found really low complexity differential attacks on reduced-round ForkAES, which I found really interesting. I came up, with the crucial help of Gaëtan Leurent, with an attack on full ForkAES. Even though this attack is theoretical because the complexities are too high to be applicable, recovering the key requires less operations than the exhaustive search. ForkAES has not been standardized, but their designers produced another candidate based on the forkcipher framework for the NIST Lightweight Competition, ForkAE, using the ForkSkinny primitive.

I have a technical description of our attack on full ForkAES, which you will find in this report. We plan to submit this paper to the FSE conference in march 2020, the main conference in symmetric cryptography.

During the remaining month of my insternship, I will study different candidates of the NIST Lightweight Competition, which started in May. More than 50 candidate cryptography algorithms are being cryptanalyzed, and the winner of the competition will be standardized, like AES in the early 2000s.

Introduction to Tweakable Block Ciphers and Forkciphers

There are two types of cryptosystems : private key systems (a.k.a. symmetric cryptology) and public key systems (a.k.a. asymmetric cryptology). In symmetric cryptology, the paramount hypothesis is that the sender (Alice) and the receiver (Bob) of a message share a common piece of information: a secret key. This key is only known by them, and the length of the key defines the maximum level of security they can achieve. In order to know this shared secret key, Alice and Bob have to use an algorithm based on asymmetric cryptology. In asymmetric cryptology, each individual knows a private secret key, linked with a mathematical relation to a public key known by everyone. Recovering the private key from the public key is considered as impossible, as the number of computations needed is too high. If Alice wants to safely send data to Bob via an insecure channel, she can encrypt the data with Bob's public key, and Bob will be able to decrypt the data with his private key. Because the private key is needed during the decryption, Bob is the only one that can recover Alice's message. Asymmetric cryptography algorithms can serve different purposes, among them the safe share of a common secret key. As I did not study asymmetric cryptography during my internship, we will now suppose that Alice and Bob share a common secret key K. Now let's suppose that Alice wants to send a message (M ) to Bob. Alice transforms M with the help of a encryption algorithm (E) and the key (K) into a ciphertext: C = E(K, M ). Bob then decrypts the ciphertext with the corresponding decryption algorithm D and the key and obtains the message: M = D(K, C). For Bob to be able to decrypt the message, x → E(K, x) needs to be injective for a fixed K. The encryption and decryption algorithms have the same signature, which is

E : {0, 1} k × {0, 1} * → {0, 1} * .
There are two main families of encryption algorithms : stream ciphers and block ciphers. I have mainly worked on block ciphers during my internship. They are low-level algorithms, called primitives, whose careful analysis ensure the security of the global algorithm. The most famous one is the AES, standardized in 2000 by the NIST and still widely used today in TLS 1.3 for example. There exist no formal proof of the security of primitives, but they are chosen so that known attacks do not threaten them. In addition, cryptanalysis is operated on these primitives to evaluate their security. Block ciphers (E) take a key and a n-bit plaintext as input and return a n-bit ciphertext. Their signature is

E : {0, 1} k × {0, 1} n → {0, 1} n .
Then, to encrypt a full message M , we pad the message so that its length reaches a multiple of n, and divide it into n-bit blocks. The block cipher is inherently deterministic: encrypting the same message under the same key will give the same result. Encrypting all blocks independently from one another and concatenating the result directly leads to collisions if the plaintext blocks are repeated, in which case the attacker knows that input blocks were equal.

To avoid that problem, a mode of operation uses the primitive to safely encrypt data. It usually takes a randomly chosen n-bit input vector (IV) as input. For instance, in the Cipher Block Chaining mode of operation (CBC), the first block is XORed with the IV before being encrypted. The resulting ciphertext block is XOR-ed with the second plaintext block etc... A collision is still possible theoretically, but it only happens after 2 n/2 blocks, even if the plaintext is controlled by the attacker. The common modes of operations (CBC, CTR, GCM,...) have a proof of security up to 2 n/2 blocks of data under the hypothesis that the primitive is secure. However these modes of operation are often difficult to design and to prove secure. [START_REF] Liskov | Tweakable block ciphers[END_REF]. Like block ciphers, these primitives take a key and a n-bit plaintext input, but they take an additional t-bit tweak as input. The combination of the tweak and the key material is called tweakey. Their signature is This aims at simplifying the proofs and the designs of modes of operation, without loosing known results about primitives, as the extra-cost of making a block cipher "tweakable" is small. New modes of operation emerge from tweakable block ciphers : changing the tweak between different blocks of the same message ensures that collisions give no information to the attacker. Indeed E(K, T, M ) = E(K, T , M ) if T = T gives no relation between M and M for a secure tweakable primitive E. This gives a security of up to 2 n blocks of data.

Liskov et al. introduced in 2002 the notion of Tweakable block ciphers

E : {0, 1} k × {0, 1} t × {0, 1} n → {0, 1} n .
Designing a secure tweakable block cipher primitive is harder than a normal block cipher one, because it gives the attacker an additional degree of freedom, which is the choice of the tweak. Indeed we want the result of two encryptions under different tweaks to be completely independant.

The forkcipher framework was designed in 2018 by Andreeva et al. [START_REF] Andreeva | Forking a blockcipher for authentificated encryption of very short messages[END_REF] for very short messages. It aims at producing authentificated encryption (AE) primitives. In addition to the privacy offered by an encryption algorithm, an AE ensures the integrity of the data. Usually, this is done by combining an encryption algorithm and a message authentification code (MAC). However, for very short messages, the size of the MAC is approximately the size of the encrypted message. Therefore having seperate algorithms to compute the MAC and the ciphertext is expensive. The clever idea behind the forkcipher framework is to be more efficient than a standard AE algorithm because of common computations of both ciphertexts and parallelization. A forkcipher outputs two ciphertexts, for redundancy, both leading to the plaintext. Once both ciphertexts were obtained, the reciever of the data can check if both ciphertexts lead to the same plaintext, and when appropriate, he knows that the data comes from a sender knowing the key. Forkciphers are built upon secure block ciphers, and their specifications depend on the block cipher used. We will only work on forkciphers based on tweakable block ciphers.

A forkcipher takes a n-bit plaintext, a k-bit key and a t-bit tweak input and returns two n-bit ciphertexts C 0 and C 1 derived from the same plaintext. The signature of this primitive is the following:

F : {0, 1} k × {0, 1} t × {0, 1} n → {0, 1} n × {0, 1} n .
Block ciphers consist generally of a round function applied a specific number of times r tot to the plaintext. A forkcipher applies this round function r i times to the plaintext, then forks the state, and compute independently both ciphertexts, applying r 0 rounds with the tweakey material T K 0 (derived from the initial tweakey) in the first branch and r 1 rounds with the tweakey T K 1 (also derived from the initial tweakey) in the second branch. In most cases, r 0 = r 1 and r i + r 0 = r tot . Figure 3 shows how a forkcipher operates.

P r

i T K i r 0 C 0 T K 0 r 1 C 1 T K 1

Introduction to Cryptanalysis

The word cryptanalysis refers to the study of a primitive from the attacker's perspective. As seen in Section 1.3, the security of the mode of operation is based on the security of the primitive, therefore careful analysis of the primitive is required. We assume that the attacker can choose part of the plaintext or ciphertext, and model this as oracles. For instance, the encryption oracle allows the attacker to query the ciphertext corresponding to a specific chosen plaintext, encrypted under the key K. Different types of oracles exist when cryptanalysing a standard block cipher, but the usual ones are the encryption and the decryption oracles. For tweakable block ciphers, an encryption oracle can let the attacker choose the tweak in addition to the plaintext. In symmetric cryptology, block ciphers frequently consist of a round function, applied a certain number of times to the plaintext. A natural way to analyse block ciphers is to find attacks on the round reduced primitive, with the highest number of rounds as possible. If the number of rounds attacked is close to the total number of rounds of the full primitive, the block cipher is considered as unsecure. As we can add an undeterminate number of rounds to a block cipher, there is naturally a compromise between security and performance. Consequently, good primitives are not only secure but also very efficient.

We intuitively describe the level of security offered by a cryptographic primitive as the logarithm of the number of encryptions needed to recover the key K. The level of security is at most k for a k-bit key, as the attacker can ask the oracle for one couple Plaintext/Ciphertext (M ,C), then iterate over all 2 k keys and compute the ciphertext for the corresponding message M under each key. After 2 k-1 encryptions in average, the attacker has a matching ciphertext, then tests the candidate key with another couple Plaintext/Ciphertext to confirm his guess (it is possible that two different keys have the same matching M → C for one couple, but very unlikely for two chosen plaintexts). The attacker can be sure to recover the key after 2 k encryptions, which induces a maximum level of security of k. This is called the brute-force attack. Typical values of k are 80, 128,196 or 256. However some attacks target weak keys, and therefore have a marginal probability of success. If is the probability of success of an attack, and T is its complexity, we can extend the definition of level of security (l) of an algorithm as:

l = log 2 (T / ) (1)
The complexity of an attack is divided into three different complexities: time, memory and data. The first two correspond to standard complexities used in computer science algorithms, that is respectively the number of computations and the maximum memory storage needed for the attack. The data complexity is the number of call to the encryption oracle of the attack.

We will show in our report that despite the designers claim of security, adding some features to existing encryption algorithms often lowers the security in a unexpected manner.

PRELIMINARIES

During my internship, I focused on KIASU-BC, a tweakable block cipher based on AES, and ForkAES, the forkcipher based on KIASU-BC. We'll therefore start with a presentation of AES block cipher, along with known attacks against it, then we will introduce KIASU-BC and ForkAES. We will then show the notation used for our paper.

Presentation of AES

AES is a block cipher designed by J. Daemen and V. Rijmen in 1998 [START_REF] Daemen | Specification for the advanced encryption standard (aes)[END_REF], selected in 2000 after the NIST competition. It was standardized in 2000, and is widely believed to be a secure block cipher. Three versions of the algorithm were standardized although the designers proposed more versions in their original paper. The three versions offer different key size : 128, 196 and 256, with 128-bit blocks. We will only work on AES-128 (128-bit keys). AES is based on a design principle known as a substitution-permutation network, and is efficient in both software and hardware. AES-128 takes a 128-bit plaintext and a 128-bit key input and returns a 128-bit ciphertext. First, the 128-bit message is placed into a 4x4-byte array, called the state. For example, if

M = b 0 b 1 ...b 15 , the initial state will be b 0 b 1 b 2 b 3 b 4 b 5 b 6 b 7 b 8 b 9 b 10 b 11 b 12 b 13 b 14 b 15 .
The encryption consists of 10 rounds, each of which is a combination of 4 operations: SubBytes (SB), ShiftRows (SR), MixColumns (MC) and AddKey (AK). The final round omits the MixColumns operation, and an initial round key is XORed to the state before the first round.

• The SubByte operation performs a permutation on each byte of the state.

• The ShiftRow operation shifts the second line of the state by 1 cell on the left, the third line by 2 cells on the left, and the last line by 3 cells on the left.

• The MixColumn operation multiply each column of the state by a matrix M in the field

F 2 8 = F 2 [X]/(X 8 + X 4 + X 3 + X + 1
), defined by :

M =     2 3 1 1 1 2 3 1 1 1 2 3 3 1 1 2     .
• The AddKey operation XORs the state with the round key. Round keys are different from round to round, computed from the initial key with a key schedule.

After applying 10 rounds to the plaintext, the state is returned. Because every step is invertible, decrypting the message consists of applying 10 inverse rounds to the matrix and returning the state, which is the plaintext. AES resists differential attacks because of its very strong diffusion. This means that a single byte difference in the plaintext propagates very quickly to the entire state, and therefore leads to a completely different and unpredictable ciphertext. Indeed, the MixColumn operation spreads a single byte difference to an entire column difference, and the ShiftRow operation ensure that every column is affected. See the following scheme, where the grey cells correspond to non-zero differences and the white cells to zero difference: There is no attack on 10 rounds of AES-128 to this day. However cryptanalysts deeply studied reduced-round AES. Though it does not represent the real AES-128, it allows the cryptography community to think about ways to attack the full primitive, if there exists any. The most successful attacks are on 7 rounds. They are showed in Table 1, along with their complexities.

∆ IN KS k0 AK x 0 SB y 0 SR z 0 MC w 0 Round 0 KS k1 AK x 1 SB y 1 SR z 1 MC w 1 Round 1 k2 AK x 2

Description of KIASU-BC and ForkAES

KIASU-BC is a tweakable variant of AES-128 designed by J.Jean et al. [START_REF] Jean | Kiasu v1.1. First-round submission to the CAESAR competition[END_REF]. It has the same number of round as AES-128 and the round functions are very similar, but has an additional 64-bit input. The only change between the two primitives is the AddTweak (AT) operation after the AddKey operation of each round, in which the 64-bit tweak is XORed to the first two rows of the state. Note that unlike the key of AES-128, the tweak does not go through a tweak schedule, and is the same on each round.

The tweak can be chosen by the attacker, therefore an attacker can offset a state difference with a tweak difference for example. Despite the designers initial claim, for most of the existing attacks on AES-128 there exists an equivalent attack on KIASU-BC reaching one more round. ForkAES is an authentificated encryption algorithm, based on the forkcipher framework designed by Andreeva et al. [START_REF] Andreeva | Forking a blockcipher for authentificated encryption of very short messages[END_REF] for very short messages. It takes a 128-bit plaintext, a 128-bit key and a 64-bit tweak input and returns two 128-bit ciphertexts C 0 and C 1 derived from the same plaintext. The encryption of the data works almost exactly like KIASU-BC. To compute C 0 and C 1 , five Kiasu-BC rounds are applied to the plaintext. Then we duplicate the state and compute 5 more Kiasu-BC rounds with different round keys, ob-tained with an extension of the Kiasu-BC tweakey schedule. This way, we efficiently obtain two ciphertexts that both went through 10 rounds of KIASU-BC, for a total cost of 15 KIASU-BC round encryptions. Although the designers of ForkAES state "Since we do not introduce any novel design complexities, the security of our forkcipher design can be reduced to the security of the AES and KIASU ciphers for further type of attacks", this type of encryption provides the attacker with a new oracle: the reconstruction oracle. In this model, the attacker can ask for the second ciphertext C 1 obtained from a chosen ciphertext C 0 . Unlike KIASU-BC, the path from C 0 to C 1 consists of 5 decryption rounds followed by 5 encryption rounds, which lowers the diffusion around the middle round. We denote ForkAES-r init -r 0 -r 1 the round reduced ForkAES version composed of r init rounds before the forking point, and respectively r 0 and r 1 rounds in each banch. Full ForkAES is therefore ForkAES-5-5-5. If r init is not used and can take any value, we denote the round reduced version ForkAES- * -r 0 -r 1 . Banik et al. applied several known attacks on ForkAES [BBJ + 19] and found interesting results, such as very low complexity differential attacks on ForkAES- * -4-4. They exploited the lack of diffusion, which inspired us for our improved differential attack. Our attack does directly endangers the full ForkAES level of security, but the complexity of the attack is high enough not to be fatal for the primitive. The different complexities of key recovery attacks for 128-bits key are lower than 2 128 × where is the probability of success. These are the first attacks on full ForkAES.

P 5R T, K i 5R C 0 T, K 0 5R C 1 T, K 1

ForkAES Version

Notations and Mathematics

Notations We denote x i ,y i ,z i and w i the states after respectively the AddTweaKey, SubByte, ShiftRows and MixColumn operations of round i. For a 128-bit state s, we denote s[j] the j-th byte of the state, following the byte ordering given by: The tweak byte ordering will follow the key byte ordering, as we do not use other tweak bytes than byte 0. ForkAES forks the state after 5 rounds and transforms it through two different branches into two ciphertexts. The first branch takes round keys k 5 to k 10 and the second branch takes round keys k 11 to k 16 , derived from k with an extended key schedule. We denote the ciphertext obtained from the first branch C 0 and the ciphertext obtained from the second branch C 1 .

For the following attacks, we denote C 0 the state after partial inversion of the tenth round (we inverted AddTweak, MixColumn and ShiftRows), and k 10 the equivalent key of the real subround key k 10 . The equivalent operation is denoted AK eq 10 . In other words,

C 0 = SR -1 (M C -1 (AT (C 0 ))) k 10 = SR -1 (M C -1 (k 10 )).
Similarly, we denote C 1 the equivalent output ciphertext and k 16 the equivalent ultimate round key. The equivalent operation is denoted AK eq 16 . They verify :

C 1 = SR -1 (M C -1 (AT (C 1 ))) k 16 = SR -1 (M C -1 (k 16 )).
We denote by ( C 0 , T ) the ciphertext C 0 with the tweak T . We denote AT K i the AddTweaKey operation, which gathers the AddKey and the AddTweak operations of round i. We denote the associated tweakey tk i = T + k i where T is the tweak and k i the round key of round i. We denote C x a column such that it contains 0 on the three last rows, and a certain value x in the first row.

Mathematics Every byte of the states we consider are elements from the field

F 2 8 = F 2 [X]/(X 8 + X 4 + X 3 + X + 1).
Additions, multiplications and divisions of bytes should always be interpreted as operations in the field F 2 8 . Explicit elements of the field are represented as integers. For instance 2 represents the polynom X of the field.

We denote by P(δ i , δ o ) the probability of having an output difference through the AES S-Box of δ o if the input difference is δ i . If SB denotes the AES SubByte permutation, we have:

P(δ i , δ o ) = |{x ∈ F 2 8 , SB(x) + SB(x + δ i ) = δ o }| × 2 -8 .
Note that an important cryptographic property of SB is that for δ i = 0, P(δ i , δ o ) is either 2 -7 , 2 -6 or 0, and for every non zero δ i , there exists a unique δ o ∈ F 2 8 such that P(δ i , δ o ) = 2 -6 . SB -1 also has this property.

In the following proof of the attack, Θ will denote a tweak difference such that Θ is only active on the first byte and P(Θ[0], Θ[0]/2) = 2 -6 . Three such differences exist.

The three possibles values for Θ[0] are 33, 127 and 227.

We will denote Pr(s → s ) the probability of going from state s to state s of the characteristic.

For the rest of the proof a 0 , a 1 , a 2 , a 3 will be the 4 distinct values such that a 0 + a 1 = a 2 + a 3 = Θ[0]/2 and SB -1 (a 0 ) + SB -1 (a 1 ) = SB -1 (a 2 ) + SB -1 (a 3 ) = Θ[0], and such that a 0 < a 1 , a 2 < a 3 and a 0 < a 2 where the comparisons are operated on integer representations of the bytes. This way, the four values are uniquely defined. Let us denote δ x = a 0 + a 2 . Furthermore, we denote b i = SB -1 (a i ) for i ∈ {0, 1, 2, 3}.

We denote τ the tweak active only on the first byte, such that τ [0] = Θ[0]/28. For example, for Θ[0] = 33, we have Θ[0]/2 = 158, a 0 = 99, a 1 = 253, a 2 = 104, a 3 = 246, δ x = 11.

EXISTING ATTACK AGAINST FORKAES- * -4-4

In this section, we describe the existing reflection differential attack presented by Banik et al. [BBJ + 19]. This attack on round reduced ForkAES inspired us for our attacks presented in Section 4, 5 and 6. This attack is a truncated differential.

Presentation of Truncated Differential Characteristics

A differential characteristic is a specific trail of differences from an input difference to an output difference, going through each round of the block cipher. We choose a pair of input plaintexts such that the plaintext difference equals the input difference of the characteristic. The pair has a certain probability of satisfying the characteristic, say > 2 -k , where k is the size of the key. We then ask for their encryption. If the encrypted pair have the expected difference, we save the pair. If we repeat this operation 1/ times, we have in average one pair that satisfies the characteristic. Then, we need a way to deduce some key bytes from a pair satisfying the characteristic. Once we have reduced the key space, we can proceed to an exhaustive search and test all possible keys over the reduced key space. That operation needs less computations than the exhaustive search on the entire key space, so we can recover the key more efficiently than the exhaustive search.

Differential characteristics are interesting in AES because most of the operations are linear and differences in output of linear operations can be computed from differences in input with probability 1. The SubByte operation is the only one that is not linear, and the uncertainty of the differential characteristic comes from this operation.

Truncated differential characteristics regroup several differential characteristics. Usually, for AES and its variants, we do not specify the value of the difference, but we only distinguish inactive (zero difference) bytes and active (non-zero difference) bytes. Not only this significantly increases the probability of the characteristic, but this allows us to build some plaintext sets, in which most of the pairs of plaintexts have the truncated input difference of the characteristic. For a set of n plaintexts, we create n 2 pairs. Therefore, we need a lower number of encrypted data to find one pair that satisfies the characteristic.

Differential Trail and Probability

Because we consider ForkAES- * -4-4, round keys of the first branch are k 5 ,k 6 ,k 7 ,k 8 and k 9 , and round keys of the second branch are k 10 ,k 11 ,k 12 ,k 13 and k 14 . We define k 9 and k 14 similarely to Section 2.3: The input difference of the characteristic is only active on bytes 0,1,2,3, and the difference in tweaks is active only on the first byte.

k 9 = SR -1 (M C -1 (k 9 )) k 14 = SR -1 (M C -1 (k 14 )).
• Pr(w 8 → z 8 ) = 2 -24 since three bytes become inactive after the inverted MixColumn operation.

• Pr(x 8 → w 7 ) = 2 -8 since the byte difference in position 0 cancels out with the tweak difference.

• Pr(z 10 → w 10 ) = 2 -24 since three bytes become inactive after the MixColumn operation.

• Pr(w 10 → x 11 ) = 2 -8 since the byte difference in position 0 cancels out with the tweak difference.

In total, the probability of the characteristic is 2 -64 .

Attack Procedure

Unlike the attack described in "Cryptanalysis of ForkAES" [BBJ + 19], we will not consider the tweak difference as fixed. Fixing the tweak, as we will show in Section 5.1, does not ensure the above probability of going through the characteristic, as the middle rounds can only be satisfied if the tweak and the key are compatible.

Construction of the pairs: First, we choose arbitrary values for the last three columns of the plaintext, along with arbritrary values for all bytes of the tweak except the first one. Iterating over the first byte of the tweak and the values of the first column of the plaintext gives us a set of 2 40 tweak/plaintexts. Among them, we query 2 32.5 randomly chosen plaintexts. This gives us 2 32.5 × (2 32.5 -1)/2 = 2 64 pairs of input verifying the characteristic input difference. In average, one pair satisfies the characteristic.

Filtering the pairs:

We can distinguish the right pair from the wrong ones by storing the corresponding ciphertexts into a hashtable, indexed by the values of the three last columns. If a pair of plaintext satisfies the characteristic, there is a collision in the hashtable between them. For random pairs of ciphertexts, there is a collision with probability 2 -96 . As we have 2 64 pairs stored in the hashtable, a random collision occurs with probability 2 -32 , which can be neglected. The only collision is therefore the right pair.

Reducing the key space:

The pair went through the characteristic so the difference in state x 12 is exactly the tweak difference. Because of a property of S-boxes in F 2 8 , there are only 2 7 (and not 2 8 ) possible differences of the output values through SB if the input values have a fixed difference. We can compute these differences from the known tweak difference. We can propagate these differences through SR, M C and AT K 13 since they are linear operations, in order to get 2 7 candidates for x 13 . We also know the difference in C 1 , therefore the difference in y 13 . The following property of S-boxes in F 2 8 reduces the key space: for random non-zero δ i and δ o , there is in average one solution x ∈ F 2 8 to the equation

SB(x) + SB(x + δ i ) = δ o .
Thus, for each 2 7 column difference in x 13 , there is in average one column value that verifies the difference conditions around the S-box. Knowing the first column value in y 13 and in C 1 , we deduce in average one value for the first column of k 14 . In total, we end up with 2 7 possible values for the first column of k 14 .

End of the attack

No operation depends specifically on the column position in AES, KIASU-BC and ForkAES. Consequently, we can iterate this attack by shifting the entire characteristic to another column. We can therefore recover 2 7 candidates for each column of k 14 . We can invert the key schedule to recover the master key from k 14 The 2 28 candidates are ultimately tested exhaustively.

Complexity Evaluation

We proceed to 2 32.5 data queries per column, which induces a data complexity of 2 34.5 . The memory complexity is 2 32.5 AES states to store 2 32.5 values of C 0 in the hashtable. The time complexity is 2 28 encryptions for the final exhaustive search and 2 34.5 memory accesses for the data processing. Eventually the (Data,Time,Memory) complexity will be: Round 9

z 9 M C -1 2 -72 y 9 SR -1 x 9 SB -1 KS tk7 AT K 7 w 8 Round 8 z 8 M C -1 2 -24 y 8 SR -1 x 8 SB -1 2 -6 tk6 AT K 6 w 7
Round 7

z 7 M C -1 y 7 SR -1 x 7 SB -1
Round 10 to 6 This attack targets weak keys such that k 5 + k 11 only has zero values on the diagonal. This happens with probability 2 -32 . We will show an attack on such keys with complexity under 2 96 = 2 128 × 2 -32 . This attack uses a differential characteristic with high probability. The particularity of this characteristic is that if one pair satisfies this characteristic, then it is easy to construct another pair that has a very high chance of satisfying the characteristic as well.

Differential Characteristic for the First Pair

First, we guess the first byte of the equivalent key k 10 and denote it K. The pairs that we are going to focus on are pairs of the form :

p =             a 0 + K u 0 u 4 u 8 0 u 1 u 5 u 9 0 u 2 u 6 u 10 0 u 3 u 7 u 11     , 0     ,         a 1 + K v 0 v 4 v 8 0 v 1 v 5 v 9 0 v 2 v 6 v 10 0 v 3 v 7 v 11     , Θ        
for any 96-bits vectors u and v. We built the pair so that the first byte difference at state x 10 is exactly the tweak difference, so that the state w 9 has an inactive first column.

• Pr(w 9 → z 9 ) = 2 -72 since 9 bytes become inactive after the MixColumn operation.

• Pr(w 8 → z 8 ) = 2 -24 since 3 bytes become inactive after the MixColumn operation.

• Pr(y 8 → x 8 ) = P(Θ[0], Θ[0]/2) = 2 -6 by definition of the tweak.

• Round 7 is then inactive.

• Values in the diagonals of both elements of the pair in state x 6 do not change with the AK eq 5+11 operation, because of the hypothesis we made on the key. Consequently, both elements of the pair have the same diagonal values in state y 6 and in state y 11 . The difference in state w 11 is therefore the tweak difference with probability 1.

• Round 12 is then inactive.

• Pr(x 13 → y 13 ) = 2 -6 by definition of the tweak.

• Pr(x 15 → y 15 ) = 2 -6 because we filter the pair on the first byte difference and we want a Θ[0]/2 difference.

In summary, for the first pair, Pr( C 0 → C 1 ) = 2 -72-24-3×6 = 2 -114

Construction of the Twin Pair

The twin pair p twin associated with the pair p will be constructed so that the first three rounds follows the characteristic with probability 1 knowing that p follows it. The probability of the total characteristic for p twin will therefore be 2 -12 .

p twin =             SB(b 0 + τ [0]) + K u 0 u 4 u 8 0 u 1 u 5 u 9 0 u 2 u 6 u 10 0 u 3 u 7 u 11     , τ     ,         SB(b 1 + τ [0]) + K v 0 v 4 v 8 0 v 1 v 5 v 9 0 v 2 v 6 v 10 0 v 3 v 7 v 11     , τ + Θ         .
As a twin pair p twin associated with a pair p is introduced, s, s , s, s will respectively denote the values of state s for the first element of p, the second element of p, the first element of p twin and the second element of p twin .

We remind the reader that τ is a tweak active only on the first byte such that τ [0] = Θ[0]/28. p twin is constructed such that

w 9 [0] = AT K 9 (SB -1 (AK eq 10 (SB(a 0 + X) + K))) = a 0 + k 9 [0] = w 9 [0] w 9 [0] = AT K 9 (SB -1 (AK eq 10 (SB(a 1 + X) + K))) = a 1 + k 9 [0] = w 9 [0].
Up to this point, neither MixColumn nor ShiftRows have been applied on the states, therefore each byte of the state has a specific value depending only on the corresponding byte of the input. We chose p twin such that all bytes but the first one have exactly the same input value as the first pair, so we know that w 9 [1, ..., 15] = w 9 [1, ..., 15] and w 9 [1, ..., 15] = w 9 [1, ..., 15], which implies

w 9 = w 9 w 9 = w 9 .
This equality of states is satisfied for the whole round 9, up to x 9 . After the next tweak addition, we have the following property :

w 8 = w 8 + τ [0] w 8 = w 8 + τ [0].
The values of state w 8 of both elements of p twin only differ from those of p on the first byte. Since p satisfies the characteristic, we have z 8 [0] + z 8 [0] = Θ[0]/2 This implies:

z 8 [0] = z 8 [0] + M C -1 (C τ [0] )[0] = z 8 [0] + 14 * τ [0] = z 8 [0] + Θ[0]/2 = z 8 [0] z 8 [0] = z 8 [0] + M C -1 (C τ [0] )[0] = z 8 [0] + 14 * τ [0] = z 8 [0] + Θ[0]/2 = z 8 [0]. Ultimately, we have x 8 [0] = x 8 [0] = Θ[0] + x 8 [0] = Θ[0] + x 8 [0]. (2)
Furthermore, since w 9 = w 9 and w 9 = w 9 , the differences of both pairs in state w 9 are equal. Because w 9 → z 8 consists only in linear operations, the differences in state z 8 of both pairs are equal, in particular the difference z 8 + z 8 is only active on the first byte.

The twin pair has therefore a difference in state x 8 active only on the first byte, and the first byte difference is exactly the tweak difference Θ[0] as we showed in Equation (2). So the twin pair has an inactive round 7, and satisfies the first three rounds of the characteristics with probability 1.

Filtering Twin Pairs

The differential characteristic for twin pairs has a total probability of 2 -126 . Now, we want to distinguish the pairs that satisfy the characteristic from other pairs. First, both pairs must have inactive bytes 1,2 and 3 in the final state, and the first byte difference must be exactly Θ[0]/2. These conditions are verified with probability 2 -64 on random pairs of pairs. Furthermore, we will add another condition to the filter : for both pairs, we can deduce the possible values of k 16 [0], and they should have a common value for k 16 [0]. The differential condition between x 15 and y 15 has 4 possible output values, and these values are a 0 , a 1 , a 2 and a 3 as seen in section 2.3. If both pairs went through the characteristic, the ouput of every element of each pair will be one of the 4 possible Both hashtables have 64-bit hash keys. However, they only filter 58 bits of data due to redundancy, in addition to the 12 bits filter corresponding to values excluded from the tables. Indeed, knowing that

C 1 (u)[0] = C 1 (v)[0] + Θ[0]/2 Q( C 1 (u)[0]) = Q( C 1 (u)[0]) Q( C 1 (v)[0]) = Q( C 1 (v)[0]) implies that there exists δ ∈ {0, Θ[0]/2, δ x , Θ[0]/2 + δ x } such that C 1 (u)[0] = C 1 (v)[0] + δ. Due to previously checked conditions, C 1 (u)[0] = C 1 (v)[0]
therefore has a 2 -2 probability of happening for a random pair of pairs instead of the naively expected 2 -8 probability.

We finally have our 70-bit filter implemented with a first 12-bit condition filter and two 64-bit hashtables. The filter has a memory complexity of only 2 × n × 2 -6 96 bits blocks if n is the number of candidate vectors u.

Processing the Remaining Pairs

The probability that twin pairs satisfy the characteristic is 2 -126 . Therefore, we need 2 63 96-bit vectors to form 2 126 twin pairs. We expect one right pair. After the 70-bit filter, we will still have to process 2 126-70 = 2 56 pairs. Further filtering is required in order to distinguish the right pair from the wrong ones. The difference value of z 13 is Θ[0]/2, and z 13 → x 14 is composed of linear operations, so we can compute the fixed difference values in state x 14 . Then, we preventively compute the 2 7 possible difference values of a byte difference in state y 14 , say y 14 [1]. We then compute the possible differences of the last column of the state x 15 . Knowing the differences in C 1 , we can deduce 2 7 possible values for the last column of AK eq . Doing that for pairs p and p twin , we can check whether the intersection of these possible values is empty or not. If it is, the pairs are incompatible. This costs 2 8 operations at most, and the probability of having a non-empty intersection is appoximately 2 7 × 2 7 × 2 -32 = 2 -18 . When this happens, there is in average one element in the intersection. Doing this with the last column, then the two other columns, we have another filter, which a random pair passes with probability 2 3×(-18) = 2 -54 .

After this extended filter, we still have 2 56-54 = 2 2 pairs of pairs. For each of them, there are in average one key guess for the three last columns and four key guesses for the first byte. We then iterate over the bytes AK eq [1, 2, 3] to proceed in an exhaustive search for the key. This has a complexity of 2 2+2+24 = 2 28 which is clearly lower than the complexities of other steps of this attack.

Complexity of the Attack

First, we guessed the value K of the first byte of the equivalent round key k 10 . Then, for each value, we needed to create 2 126 pairs and filter them. We therefore needed 2 63 vectors u, and asked for 2 65 encryptions, which makes a total data complexity of 2 73 . The memory complexity is 2 58 , because the average number of vectors written in each hashtable is 2 57 . The time complexity is 2 64 for pair processing, therefore the final time complexity lies in the data processing which gives us a time complexity of 2 73 . Our (Data,Time,Memory) complexity will therefore be:

(D, T, M ) = (2 73 , 2 73 , 2 58 ).

ATTACK AGAINST FULL FORKAES FOR 2 122 WEAK KEYS

A Focus on the Middle Rounds

The authors of the paper "Cryptanalysis of ForkAES" [START_REF] Andreeva | Forking a blockcipher for authentificated encryption of very short messages[END_REF] showed a truncated differential attack on ForkAES- * -4-4, using the same scheme for middle rounds. Their attack used a unique tweak difference. However, this unique tweak difference can possibly never go through the middle rounds: Let us note the values of the state s respectively s and s for the first and the second element of the pair and k = k 5 + k 11 . Let us suppose that we have a tweak difference ∆T between the elements of the pair, only active on the first byte. Additionaly, the state difference in x 7 is inactive. We want the whole state difference to be inactive again in x 12 . These two conditions imply that the differences in w 6 and w 11 are exactly the tweak difference ∆T . Therefore, the differences in states z 6 and z 11 are equal. Hence, y 6 and y 11 should also have the same difference, which can directly be computed from ∆T . Only diagonal bytes are active, and

SB(x 6 [i]) =y 6 [i] SB(k[i] + x 6 [i]) =y 11 [i] SB(x 6 [i]) =y 6 [i] SB(k[i] + x 6 [i]) =y 11 [i].
Now, because of equation ( 7), a simple combination of the above equations gives the following property :

SB(x 6 [i]) + SB(x 6 [i])) =δ ∆T [i] SB(k[i] + x 6 [i]) + SB(k[i] + x 6 [i]) =δ ∆T [i]. (8)
Therefore the pairs of byte p 1 = (x 6 [i], x 6 [i]) and p 2 = (x

6 [i] + k[i], x 6 [i] + k[i]
) have the same difference x 6 [i] + x 6 [i] and their output difference through the AES S-box is for both pairs δ ∆T [i].

Three possibilities emerge:

• P(x 6 [i] + x 6 [i], δ ∆T [i]) = 0.
In this case, the pair can obviously not satisfy the characteristic.

• P(x 6 [i] + x 6 [i], δ ∆T [i]) = 2 -7
. There is a unique pair verifying an input difference of x 6 [i] + x 6 [i] and an output difference of δ ∆T [i] through the AES S-box. In order to pass the characteristic, p 1 and p 2 should have the same elements (switched or not). Therefore,

x 6 [i] = k[i] + x 6 [i] or x 6 [i] = k[i] + x 6 [i] which implies k[i] = 0 or k[i] = x 6 [i] + x 6 [i]. • P(x 6 [i] + x 6 [i], δ ∆T [i]) = 2 -6
. There are two pairs verifying an input difference of x 6 [i] + x 6 [i] and an output difference of δ ∆T [i] through the AES S-box. Suppose (q 0 , q 1 ) and (q 2 , q 3 ) are such pairs. Let's pose δ p = q 0 +q 2 . Then either

x 6 [i] = k[i]+x 6 [i], x 6 [i] = k[i]+x 6 [i], x 6 [i] = k[i]+x 6 [i]+δ p , x 6 [i] = k[i]+x 6 [i]+δ p .
Therefore k[i] can take 4 different values in order for the pair to possibly pass the characteristic.

For each active value of δ ∆T [i], there are exactly 2 7 possible key bytes k[i] such that there exist values x 6 [i] and x 6 [i] verifying Equation (8). That implies that if we choose a unique ∆T , then there is a probability of 2 -4 that the key is compatible with the tweak (2 -1 for each diagonal byte). In other cases, the probability of passing the total characteristic is 0. Additionally, if diagonal key bytes are compatible with the tweak, Pr(x 7 → x 12 ) >= 2 -28 , because at least two values x 6 [i] satisfy Equation 8 for i ∈ {0, 5, 10, 15}.

In summary, if we take a random tweak difference and a random key, there is an average probability of 2 -32 of satisfying the characteristic on the middle rounds. However, for a fixed tweak difference and a fixed key, there is a 2 -4 chance that they are compatible, in which case the probability of going through the middle rounds is 2 -28 . If they are not compatible, the pair can not satisfy the characteristic.

Our New Weak Key Hypothesis

Now, we will suppose that the key has at least one diagonal byte equal to zero. This happens with probability 2 -6 . To avoid irrelevant complications, we will suppose that the first byte of the key is 0. We will also suppose that the tweak difference taken is compatible with the key, as seen in Section 5.1. This compatibility happens with probability 2 -3 (2 -1 for each non zero diagonal key byte).

The New Differential Characteristic

Like for the previous attack, we start by guessing the first byte of k 10 , denoted K. The main change between this characteristic and the previous one is the addition of a 2 -21 probability of passing the middle rounds (2 -7 for each of the three rightmost columns). The probability of passing the characteristic is 2 -135 for the first pair and 2 -33 for its twin pair, which induces a total probability of 2 -168 . We therefore need 2 84 96-bits vectors u to expect that one pair of pairs passes the characteristic. The same filter filters 70 bits to give us 2 98 remaining pairs. The same advanced filtering costing 2 8 operations per pair, filters 54 other bits, which gives us 2 44 remaining twin pairs. In average, each remaining twin pair has one key guess for the three last columns, four key guesses for the first byte, and 2 24 key guesses for bytes 1,2,3. Exhaustively testing the remaining possible keys has a complexity of 2 40+2+24 = 2 70 .

Complexity of the Attack

If the key value k 5 + k 11 has a zero value on the diagonal and the other diagonal values are compatible with the tweak difference, we have a complexity in data of 2 84 × 4 per key guess, a complexity in memory of 2 85 96-bits blocks, and a time complexity of 2 8 × 2 98 per key guess. This attack works with probability 2 -9 . In addition, Round 9 we can try this attack with the 3 tweak differences values that verify ∆(T [0], T [0]/2) = 2 -6 , and we can rotate the columns, to finally give a probability of success of 3/2 -7 , for a total (Data,Time,Memory) complexity of (D, T, M ) = (2 97.58 , 2 117.58 , 2 85 ). We can still trade 2 8 in time complexity for a 2 11 factor in memory with the intermediate filter described in the next attack.

z 9 M C -1 2 -72 y 9 SR -1 x 9 SB -1 KS tk7 AT K 7 w 8 Round 8 z 8 M C -1 2 -24 y 8 SR -1 x 8 SB -1 2 -6 tk6 AT K 6 w 7 Round 7 z 7 M C -1 y 7 SR -1 x 7 SB -1 Round 10 to 6 w 6 Round 6 z 6 M C -1 y 6 SR -1 x 6 SB -1 0 k5+k11 AK eq 5+11 x

ATTACK AGAINST FULL FORKAES FOR 2 127 KEYS

Our New Key Hypothesis

In this attack, we want to attack any key. The only condition on the key is that it should be compatible with the tweak used during the attack. This has a probability of 2 -1 on every diagonal byte, which makes a total probability of 2 -4 .

The New Differential Characteristic

The characteristic is similar to attack of Section 5, with an additionnal 2 -7 probability of passing the middle rounds. We first guess the value K of the first key byte of k 10 . The first pair satisfies the total characteristic with probability 2 -142 , and the twin pair with probability 2 -40 . The pair of pairs satisfies the characteristic with probability 2 -182 . We therefore need to create 2 182 pairs with the hope that one satisfies the characteristic, requiring a set of 2 91 96-bits vectors. In this case, we are left with 2 112 twin pairs after the 70 bits filter. We will introduce a new efficient intermediate filter that will filter enough pairs to apply the complete filter on every remaining pair without exceeding 2 128 computations. Figure 10: Differential characteristic under the hypothesis that the tweak is compatible with the key.

Intermediate Filter

This intermediate filter aims at reducing the number of possible pairs that we get at the end of the 70 bits filter, with a small cost per pair. We construct a table as follows :

1. First, we consider the 2 7 possible difference values of y 14 [1], considering that the difference x 14 [1] is fixed and can be computed with linear operations from the tweak difference. After spreading this difference to the last column of x 15 , we come out with a table of 2 7 column differences. Now, we only keep the first 3 bytes of each column difference.

2. The second step consists in iterating over all possible values of bytes 12,13,14 of both elements of a pair of ciphertext. In total, there are 2 6×8 possible values. For every possible value and for each column difference computed in the last step, we store possible three-byte key values AK eq [12, 13, 14], deduced from the differential condition before and after the S-box operation x 15 → y 15 with in average one solution.

For each 48-bit value, we store in average 2 7 guesses for AK eq [12, 13, 14].

3. Eventually, we create a hashtable taking 12 bytes of input, corresponding to a 6-byte value for each pair, and returning one bit of output, 1 if and only if the two pairs have a common three byte value AK eq [12,13,14]. If this is not the case, the pairs are incompatible. Because in average every pair has 2 7 possible values for the 3 bytes AK eq [12, 13, 14], two random pairs have a common key value with probability 2 7 × 2 7 × 2 -24 = 2 -10 . This table is precomputed at the beginning of the algorithm and uses 2 96 bits of memory.

End of the Attack

For the 2 112 remaining twin pairs that we have at the end of the 70 bits filter, we call the above table to check if they are compatible. This intermediate filter directly reduces the number of remaining pair to 2 102 , and at this point we use the previous complete filter. The intermediate filter being a subfilter of the complete filter, we are left with 2 112 × 2 -54 = 2 58 remaining pairs. We proceed to a final exhaustive search of complexity 2 58 × 2 26 = 2 84 .

Complexity of the Attack

The data complexity of the attack is 4×2 91 ×2 8 to create the 2 182 pairs of pairs for each key guess. The memory complexity is 2 96 bits for the precomputed table, and 2 86 for the hashtables storage. The time complexity corresponds to the beginning of the pair processing, which is 2 112 memory accesses per key guess, which makes 2 120 memory accesses. In addition, this attack has a 2 -4 probability of success, because the key must be compatible with the tweak difference in the middle round. We can use this attack with the three different tweaks values seen in Section 2.3, and we can rotate the columns to have 12 tries in total. We have a time complexity of 12 × 2 120 memory accesses. The time complexity of the complete attack is therefore 2 120 × 12 = 2 123.58 memory accesses. The average total data complexity of the attack is 2 101 × 12 = 2 104.58 . The memory complexity does not change.

(D, T, M ) = (2 104.58 , 2 123.58 , 2 96 ).

Probability of Success

The probability that a tweak difference is compatible with the key is 2 -4 , and the probability to have a right pair among our 2 182 pairs is 1-(1-2 -182 ) 2 182 ≈ 1-1/e. Therefore, the probability to find a right key is (1-1/e)×2 -4

for each of our twelve tweak differences, so in total the probability of success is 1 -(1 -(1 -1/e) × 2 -4 ) 12 ≈ 0.38 for a total time complexity of 2 123.58 . Note that there is a possible tradeoff between data/time complexities and the probability of success. A fixed key has a probability 1 -(1 -1 × 2 -4 ) 12 ≈ 0.54 of being compatible with one of the 12 tweak differences. Increasing the data increases the probability that a compatible tweak leads to a right pair. To reach a success probability of 1/2, we need to increase the data complexity to 2 105.2 and the time complexity to 2 124.8 .

Figure 1 :

 1 Figure 1: Cipher Block Chaining (CBC) mode of operation.

Figure 2 :

 2 Figure 2: (a) Standard block cipher encrypts a message M under control of a key K to yield a ciphertext C. (b) Tweakable block cipher encrypts a message M under control of not only a key K but also a tweak T to yield a ciphertext C. The tweak can be changed quickly, and often is public. (c) Another way of representing a tweakable block cipher, here the key K shown inside the box.

Figure 3 :

 3 Figure 3: Illustration of an encryption by a forkcipher. Each box corresponds to several rounds of a block cipher round function.

Figure 4 :

 4 Figure 4: Propagation of an input difference on a single byte, through 2 rounds of AES.

Figure 5 :

 5 Figure 5: Illustration of an encryption by ForkAES. Each box corresponds to 5 Rounds of Kiasu-BC, with different round keys.

Figure 6 :

 6 Figure 6: Truncated differential characteristic scheme for ForkAES- * -4-4.

(

  D, T, M ) = (2 34.5 , 2 34.5 , 2 32.5 ). ATTACK AGAINST FULL FORKAES FOR 2 96 WEAK KEYS 4.1 Core of the Attack

Figure 7 :

 7 Figure 7: Differential characteristic for very weak keys.

Figure 8 :

 8 Figure 8: Middle rounds of the characteristic.

(y 11

 11 + y 11 )[0, 5, 10, 15] = M C -1 (C ∆T )[0, 1, 2, 3] = (y 6 + y 6 )[0, 5, 10, 15]. (7) Let us denote δ ∆T def ≡ [i](y 11 + y 11 )[i] = (y 6 + y 6 )[i] = M C -1 (C ∆T )[i/5] for i ∈ {0, 5, 10, 15}. If the pair goes from differential state y 6 to y 11 , there are certain values x 6 [i], for i ∈ {0, 5, 10, 15} such that:

Figure 9 :

 9 Figure 9: New differential characteristic for weak keys.

Table 1 :

 1 Table 1 sums up the attacks and their complexities Comparison of existing attacks on AES-128 and KIASU-BC.

	Algorithm	Attack Type	Rds.	Data	Time	Memory	Reference
	AES-128	Impossible Diff.	7	2 106.2	2 110.2	2 90.2	[MDRMH10]
	AES-128	Meet in the Middle	7	2 97	2 99	2 98	[DFJ13]
	AES-128	Square	6	2 32	2 71	2 32	[DKR97]
	KIASU-BC	Impossible Diff.	8	2 118	2 120.2	2 102	[DL17]
	KIASU-BC	Boomerang	8	2 103	2 103	2 60	[DL17]
	KIASU-BC	Meet in the Middle	8	2 116	2 116	2 86	[MAY16]
	KIASU-BC	Square	7	2 48.5	2 43.6	2 41.7	[DEM16]

Table 2 :

 2 Comparison of complexities and probabilities of success of attacks on ForkAES versions using reconstruction queries.

		Attack Type	Data	Time	Memory	Pr. of Success	Reference
	ForkAES- * -4-4	Impossible Diff.	2 39.5	2 47	2 35	1	[BBJ + 19]
	ForkAES- * -4-4	Reflection Diff.	2 35	2 35	2 33	1	[BBJ + 19]
	ForkAES- * -5-5	Truncated Diff.	2 73	2 73	2 58	2 -32	Sect. 4
	ForkAES- * -5-5	Truncated Diff.	2 97.6	2 117.6	2 85	2 -5.4	Sect. 5
	ForkAES- * -5-5	Truncated Diff.	2 104.6	2 123.6	2 96	0.38	Sect. 6

Acknowledgments I would like to thank Gaëtan LEURENT for all the pertinent explanations he provided me with and for the time we spent together working on very interesting problems. I would also like to thank Anne CANTEAUT who helped me find this internship in Inria, and all other members of the team SECRET for their caring, as they gently introduced me to the research sphere.

values a i + AK eq 16 [0] for i ∈ {0, 1, 2, 3}. The set {a 0 + AK eq 16 [0], a 1 + AK eq 16 [0], a 2 + AK eq 16 [0], a 3 + AK eq 16 [0]} is furthermore uniquely determined by the polynomial defined on F

(3) applied on any element a i + AK eq 16 [0] of the set. Indeed ∀i ∈ {0, 1, 2, 3},

No other element that one of the a i +AK eq [0] have such a value through Q, because a non constant polynomial of degree 4 does not have more than 4 roots. By checking if those polynomial values are the same for values of the first element of each pair, we can check whereas AK eq [0] can possibly be the same for both pairs, and a random pair of pairs passes this filter with probability 2 -6 .

Note that after simple computations,

because polynomials X 4 and X 2 are linear on F 2 8 , Q(X) is linear and can be computed efficiently with a 64 bit matrix.

Random twin pairs pass the complete filter with probability 2 -70 .

Efficient Implementation of the Filter

We will dress two hashtables and find collision between the two tables to find twin pairs that satisfy the above filter.

For every vector u, we first ask for the encryptions of the inputs:

First, we compare the values of

), where Q is the previously defined polynomial. We add the following hash to the first hashtable:

We then compare the values of

). If the values are equal, we have the same property as above, and we add the following hash to the second HashTable :

(5)

There is, for every 96-bit vector u that we take, a 2 -6 chance that we write it inside the first table, and the same probability for the second table, which produces a 12-bits filter on the total number of pairs. Let's suppose we have a match between an element of the first table and an element of the second one, corresponding to vectors u and v. Our twin pairs will be

Having H 0 (u) = H 1 (v) implies that the difference in bytes 1,2,3 of both pairs are inactive. Furthermore, we have the right difference of Θ[0]/2 in the first byte of each pair. Colliding pairs satisfy the 70-bit filter.