domain: spi phys chim

text:
Didier Locq

C Ramusat

Jean-Michel Franchet

Alexandre Devaux

Ne rien écrire dans le pied de page Coarse grain C&W AD730 disk superalloy for high temperature applications

Coarse grain size is required for high temperature turbine disk or for the hotter zone of the disk. This work deals with the study of the effect of a supersolvus heat treatment on the microstructure, the microstructural stability and the mechanical properties of a new Ni-based superalloy disk.

Introduction

To improve the efficiency of new aircraft engines, the need of superalloys withstanding higher temperature for long duration is still constant. Studies to fulfill this requirement can focus on the development of new alloys or on the adjustment of existing materials. In the present paper, the second approach was applied to the disk superalloy AD730™ recently developed by Aubert & Duval [1].

First studies on this new cast and wrought (C&W) superalloy showed a set of promising features as: -Good workability (below or above the γ′ solvus temperature) due to moderate γ′ phase amount [1], -Combination of high mechanical properties for fine grain microstructures [2] compared with competing C&W superalloys, -High microstructural stability in regard to topologically close-packed (TCP) phases for a fine grain microstructure [1].

Material

The present work was conducted on samples and specimens machined out from a sector of a ring-rolled and close die forged disk provided by Aubert & Duval after applying a γ′ subsolvus heat treatment (1070°C, initial mean grain size of 4 µm). The aim of this study was to evaluate the potential of the coarse grain AD730™ alloy for high temperature disk application.

In a first step, to further complete the knowledge of this recent superalloy, several physical or metallurgical features were measured on the as-received material. These parameters include the density, the coefficient of thermal expansion and the thermal conductivity (calculated from specific heat capacity and thermal diffusivity measurements). Differential thermal analysis experiments were also carried out to determine characteristic temperatures of the AD730™ alloy to guide the heat treatment study.

Results

Microstructure

The quantification of microstructural parameters (grain and γ′ precipitate sizes) as a function of heat treatment conditions (solution treatments, cooling paths and ageing treatments) was realized. Based on metallurgical and practical criteria, a two-step solutioning treatment was selected. A two-step ageing treatment was also chosen on the basis of microhardness measurements. This work on heat treatment/microstructure relationships led to the following heat treatment sequence: 1120°C/1h/40°C⋅min -1 cooling + 1080°C/4h/100°C⋅min -1 cooling + 800°C/4h/air cooling + 760°C/16h/air cooling.

The resulting microstructure presents a mean grain size of 140 µm and a bimodal distribution of γ′ precipitates with mean diameters of 372 and 106 nm. Despite the population of relatively coarse γ′ precipitates, this type of microstructure showed an interesting combination of mechanical properties [3,4]. Finally, a third γ′ precipitate population was evidenced by high resolution SEM imaging (Figure 1). These precipitates are assumed to result from the cooling following the subsolvus resolutioning treatment and are adjusted during the aging steps.

Microstructural stability

Various long-term aging treatments (750°C/1500h, 800°C/500h, 850°C/500h and 900°C/100h) were applied on supersolvus AD730™ samples. The modification of the γ′ precipitates were quantified by particle size and hardness measurements. The evolutions of both first and second generation of secondary γ′ precipitates are presented in Figure 2. After these heat treatments, fine intergranular particles were more frequently observed than in the initial microstructure (BSE/SEM). EDX and EELS analyses on thin foils of AD730™ aged 500 hours at 850°C evidenced the joint presence of carbides and borides in the grain boundaries (Figure 3). No TCP phases were observed in the supersolvus AD730™, confirming the microstructural stability of this superalloy [1]. The severe aging treatment of 500 hours at 850°C was selected to evaluate the effect of long-term aging treatment on the mechanical properties.

Mechanical characterization

Tensile tests were conducted between room temperature and 800°C. Tensile stress-rupture tests were performed at 750°C/500 MPa and 850°C/200 MPa. The resulting data on supersolvus AD730™ (with or without 850°C/500h aging treatment) were compared with those obtained on subsolvus AD730™ [2] and supersolvus U720 [5] (Figure 4 and Figure 5). As expected, coarse grain size AD730™ presents lower tensile properties than those of fine grain size AD730™ but much better creep properties at low and medium stresses. Moreover, supersolvus AD730™ has better tensile strength than supersolvus U720 while its creep properties are close to those of supersolvus U720, confirming previous results [2]. Finally, despite the application of a severe aging treatment to supersolvus AD730™ leads to a moderate decrease of these mechanical properties. This is assumed to be due to the excellent microstructural stability of alloy AD730™.

Conclusion

The new C&W superalloy AD730™ is a relevant candidate for disk manufacture because of its production cost (alloy cost and workability) combined with high mechanical properties and excellent microstructural stability. Fine or coarser grain size can be used depending on the targeted application.

Figure 1 :

 1 Figure 1: γ′ precipitation microstructure observed after the selected heat treatment sequence (SEM image).

Figure 2 :

 2 Figure 2: secondary γ′ precipitate size vs aging treatment.

Figure 3 :

 3 Figure 3: TEM micrograph of grain boundary precipitates and the corresponding EELS map of boron, molybdenum, nickel, carbon, chromium and titanium.

Figure 4 :

 4 Figure 4: ultimate tensile strength of AD730™ with various microstructures compared with C&W supersolvus U720.

Figure 5 :

 5 Figure 5: Larson-Miller plot of rupture creep life for AD730™ and U720 alloys

Acknowledgements

The authors would like to gratefully thank F. Fossard and J.-S. Merot (LEM, Onera-CNRS) for TEM analyses and images.


Christophe Clavier

Leo Reynaud

Antoine Wurcker

Yet Another Side Channel Cryptanalysis on SM3 Hash Algorithm

Keywords: SM3, Side-channel, Hash functions, HMAC, Chosen input

SM3, the Chinese standard hash algorithm inspired from SHA2, can be attacker by similar means than SHA2 up to an adaptation to its differences. But this kind of attack is based on targeting point of interest of different kinds, some are end of computation results, that are stored when others are in intermediate computational data. The leakage effectiveness of the later could be subject to implementation choices, device type or device type of leakage. In this paper, we propose a new approach that targets only the first kind of intermediate data that are more susceptible to appear. As an example, we targeted the HMAC construction using SM3, where our method allows to recover the first half of the secret information. reducing the security of the HMAC protocol.

Introduction

Side-channels research field concerns the malicious usage of an involuntary leaked information during the execution of an algorithm, with the objective to retrieve a secret such as a cryptographic key. This was first introduced in [START_REF] Paul | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[END_REF], where the processing time of operations, that was secret-dependent, was revealing the secret information. Once the side-channels potential discovered, numerous channels where used to extract secret information, such as: power consumption [START_REF] Paul | Introduction to Differential Power Analysis and Related Attacks[END_REF], electromagnetic emissions [START_REF] Gandolfi | Electromagnetic Analysis: Concrete Results[END_REF], acoustic emissions [START_REF] Daniel Genkin | RSA key extraction via lowbandwidth acoustic cryptanalysis[END_REF] (extension of preliminary work of 2004), light emission [START_REF] Ferrigno | When AES blinks: introducing optical side channel[END_REF]. The subject is wide, as in 2014 was shown a new leak source can be used: the ground of a laptop could leak sensitive information along cables (USB, Ethernet, . . . ) in [START_REF] Daniel Genkin | Get Your Hands Off My Laptop: Physical Side-Channel Key-Extraction Attacks on PCs[END_REF].

The paper is organized as follows. The remaining of Section 1 describe HMAC and SM3 designs and clas. The Section 2 shows how an attack against SHA2-256 can be adapted to SM3. Our contribution is given in Section 3 showing a new way to attack SM3. Finally we conclude in Section 4.

HMAC

The HMAC stands for keyed-Hash Message Authentication Code and is a NIST standard that can be found in [START_REF]NIST. Fips pub 198-1, the keyed-hash message authentication code (hmac)[END_REF]. It is using one eligible hash function (H) to combine an input text (T) and a key (K) into a HMAC that is used to authenticate the text T by a receiver that shares the key K with the sender.The process is as follow:

1. (K i , K o ) pair is derived from the key K 2. The text T is concatenated after K i .
3. The resulting data is hashed.

4. The output of this first hash is then concatenated after K o . The Figure 1 shows the HMAC of a Hash function that is taking 512-bit message blocks as input. We denote by H i (respectively H o ) the output of first compression function f of the first (respectively second) hash call. These values are constant (often pre-computed) and their knowledge is sufficent to forge valid HMAC. We consider these values as target of our attack.

SM3

The SM3 is the Chinese hash standard based on same structure than SHA2-256. The Figure 2 shows the main parts of the SM3 algorithm. A data to be hashed of a bit length between 0 and 2 64 -1 is taken as input. The data is then padded in such a way that it can be split in N blocks of 512 bits (same process than SHA2-256). Each block will be treated the same way: a function f () takes the current block and the current Initialisation Vector (IV ) to produce the IV used by next block. The first IV (IV 0 ) is a constant. The Last IV (IV N ) is the 256-bit hash given as output of the algorithm.

The function f (), that differs from the one of SHA2-256, is composed of several parts:

• Function T () convert 512-bit block of padded data into 64 32-bit words pairs, all known to an attacker who knows the input data.

• Each resulting pair (W i ,W * i ) is used during round R i that melts it into the 8 32-bit values given as input.

• The resulting 8 32-bit values are given as input of next round.

• Once the 64th round output is computed, a final transformation consists in applying addition (pairwise 32-bit modular addition) with the input used for first round.

In the loop process

IV i = f (IV i-1 , Block i ):
We initialize the 8 32-bit local variables

a 0 = IV i-1,0 b 0 = IV i-1,1 c 0 = IV i-1,2 d 0 = IV i-1,3 e 0 = IV i-1,4 f 0 = IV i-1,5 g 0 = IV i-1,6 h 0 = IV i-1,7
For round r ∈ [0, 63]:

SS1 r = ((a r ≪ 12) + e r + (T r ≪ r)) ≪ 7 (1) SS2 r = SS1 r ⊕ (a r ≪ 12) (2) T T 1 r = F F r (a r , b r , c r ) + d r + SS2 r + W * r (3) T T 2 r = GG r (e r , f r , g r ) + h r + SS1 r + W r ( 4
)
d r+1 = c r (5) c r+1 = b r ≪ 9 (6) b r+1 = a r ( 7
)
a r+1 = T T 1 r (8) h r+1 = g r (9) g r+1 = f r ≪ 19 ( 10
)
f r+1 = e r ( 11
)
e r+1 = P 0 (T T 2 r ) (12)
• Additions are done modulo 2 32 .

• ≪ n are rotation of n bits to the left of a 32-bit word.

• T r are constant values depending on the round number.

• P 0(), F F () and GG() are transformation functions giving 32-bit word as output.

We finish the f () function by the 32-bit xor with initial state:

IV i,0 = IV i-1,0 ⊕ a 64 IV i,1 = IV i-1,1 ⊕ b 64 IV i,2 = IV i-1,2 ⊕ c 64 IV i,3 = IV i-1,3 ⊕ d 64 IV i,4 = IV i-1,4 ⊕ e 64 IV i,5 = IV i-1,5 ⊕ f 64 IV i,6 = IV i-1,6 ⊕ g 64 IV i,7 = IV i-1,7 ⊕ h 64
In the following we will denote δ 1,r (respectively δ 2,r ) a part of the T T 1 r (respectively T T 2 r ) computation:

δ 1,r = F F r (a r , b r , c r ) + d r + SS2 r δ 2,r = GG r (e r , f r , g r ) + h r + SS1 r
One can remark that SM3 cannot be attacked because this is a hash function that processes raw data and then there is no secret to retrieve. But, its usage in protocols, such as HMAC, may introduce a secret information that will be processed and can be targetted by a side-channel attack.

Attack Adapted from State-of-the-Art

We can adapt SHA2-256 classical side-channel attack path to SM3, inspired by the one of SHA2-256:

The attack consists in 10 steps, 8 statistical attacks and two of simple computation.

Our Contribution

We considered that several step (steps 3 to 8) of the attack path are targeting intermediate computation results that leakage is very sensitive to choices in implementations and chosen device. Contrarily to step 1 and 2 that target computational result (δ 1,0 and δ 2,0 ) that must be stored for the next round and seems then more resilient as point of interest. We then designed an chosen text attack process that rely only on deltas leakages.

Attack Set 1

We let all byte of message vary and recover δ 1,0 and δ 2,0 as described in previous attack.

Attack Set 2

This time we let all bytes of message vary except the ones of W 0 and W 4 (32-bit words) that are fixed to any value. This choice will fix W 0 and W * 0 values and then all outputs of first loop are fixed too (T T 1 0 ,T T 2 0 , a 1 , b 1 , c 1 , d 1 , e 1 , f 1 , g 1 , h 1 ). Even if some remains unknown, the attacker knows that they are fixed and then induce the delta values of second round (δ 1,1 and δ 2,1 ) to be constant too. As they are constant, they can be attacked by statistical attacks using conserved variability of W 1 and W * 1 .

Attack Set 3

The same process than previously is applied to attack third round: W 0 and W 4 are kept fixed to have constancy in first round, and now W 1 and W 5 are fixed too to keep constancy in second round. This induce that δ 1,2 and δ 2,2 are now constants and then can be targeted using conserved variability of W 2 and W * 2 .

Attack Set 4

Again the same process than previously is applied to attack fourth round: W 0 , W 1 , W 4 and W 5 are kept fixed to have constancy in first and second rounds, and now W 2 and W 6 are fixed too to keep constancy in third round. This induce that δ 1,3 and δ 2,3 are now constants and then can be targeted using conserved variability of W 3 and W * 3 .

One can remark we could not get further and recover next round deltas (δ 1,4 and δ 2,4 ) by this methodology as it would require to have W 4 both fixed (to keep constancy of first round) and variable (to be able to attack delta values) that is impossible. But the acquired information is enough to gain the secret value involved. Indeed knowing pairs (δ 1,i , δ 2,i ), ∀i ∈ [0, 3] of SM3 hash lead to knowledge of Initial Vector (IV) used. First of all, the knowledge of such delta values {δ j,i } j∈ [1,2],i∈ [0,3] induce the knowledge of corresponding T T 1 and T T 2 values. We take the equation of the fourth set when {T T j i } j∈ [1,2],i∈[0,2] (of three first rounds only) are fixed constants and known. In the following equations we indicate in red the values that are unknown and in black the value that are known by the attacker:

δ 1,0 =(a 0 ⊕ b 0 ⊕ c 0 ) + d 0 + (((a 0 ≪ 12) + e 0 + Cte 0 ) ⊕ (a 0 ≪ 12)) δ 2,0 =(e 0 ⊕ f 0 ⊕ g 0 ) + h 0 + ((a 0 ≪ 12) + e 0 + Cte 0 ) δ 1,1 =(T T 1 0 ⊕ a 0 ⊕ (b 0 ≪ 9)) + c 0 + (((T T 1 0 ≪ 12) + P 0(T T 2 0 ) + Cte 1 ) ⊕ (T T 1 0 ≪ 12)) δ 2,1 =(P 0(T T 2 0 ) ⊕ e 0 ⊕ (f 0 ≪ 19)) + g 0 + ((T T 1 0 ≪ 12) + P 0(T T 2 0 ) + Cte 1 ) δ 1,2 =(T T 1 1 ⊕ T T 1 0 ⊕ (a 0 ≪ 9)) + (b 0 ≪ 9) + (((T T 1 1 ≪ 12) + P 0(T T 2 1 ) + Cte 2 ) ⊕ (T T 1 1 ≪ 12)) δ 2,2 =(P 0(T T 2 1 ) ⊕ P 0(T T 2 0 ) ⊕ (e 0 ≪ 19)) + (f 0 ≪ 19) + ((T T 1 1 ≪ 12) + P 0(T T 2 1 ) + Cte 2 ) δ 1,3 =(T T 1 2 ⊕ T T 1 1 ⊕ (T T 1 0 ≪ 9)) + (a 0 ≪ 9) + (((T T 1 2 ≪ 12) + P 0(T T 2 2 ) + Cte 3 ) ⊕ (T T 1 2 ≪ 12)) δ 2,3 =(P 0(T T 2 2 ) ⊕ P 0(T T 2 1 ) ⊕ (P 0(T T 2 0 ) ≪ 19)) + (e 0 ≪ 19) + ((T T 1 2 ≪ 12) + P 0(T T 2 2 ) + Cte 3 )
As we can see, the number of unknown values in equations decrease. The two last equations allows to recover the values of a 0 and e 0 . Then, these values can be used in the two previous equations to recover b 0 and f 0 and so on to the full recovery of all sought values {a 0 , . . . , h 0 }.

The main limitation of this methodology is that the attacker do not have control (only knowledge) over the second hash input and then cannot pursue the secret recovery by the same methodology.

Conclusion

SM3 scheme is sensitive to this attack due to its design particularities as this attack do not seems to be applicable "as is" on SHA2-256.

Even if this attack is limited to the first half of the secret of a HMAC, it still reduces its security. Furthermore, any scheme using only one hash would be subject to total recovery of the secret by this attack.

As a further work, we are currently working on adaptations of this attack to enable the recovery of the second part of the secret of HMAC protocol. Considering others hash functions would also be of interest.

Figure 1 :

 1 Figure 1: HMAC algorithm structure

Figure 2 :

 2 Figure 2: SM3 algorithm structure

1.

  Recover δ 1,0 constant by targeting the computation of T T 1 0 = δ 1,0 + W * 0 thanks to the knowledge of varying W * 0 2. Recover δ 2,0 constant by targeting the computation of T T 2 0 = δ 2,0 + W 0 thanks to the knowledge of varying W 0 3. Recover a 0 constant by targeting the computation of T T 1 0 ⊕ a 0 during T T 1 1 thanks to the knowledge of varying T T 1 0 4. Recover rotl9(b 0 ) constant by targeting the computation of T T 1 0 ⊕ a 0 ⊕ (b 0 ≪ 9) during T T 1 1 computation thanks to the knowledge of varying T T 1 0 5. Recover e 0 constant by targeting the computation of P 0 (T T 2 0 ) ⊕ e 0 during T T 2 1 computation thanks to the knowledge of varying T T 2 0 6. Recover rotl19(f 0 ) constant by targeting the computation of P 0 (T T 2 0 ) ⊕ e 0 ⊕ (f 0 ≪ 19) during T T 2 1 computation thanks to the knowledge of varying T T 2 0 7. Recover c 0 constant by targeting the computation of T T 1 1 = c 0 + . . . thanks to the knowledge of varying T T 1 0 and W * 1 8. Recover g 0 constant by targeting the computation of T T 2 1 = g 0 + . . . thanks to the knowledge of varying T T 2 0 and W 1 9. Recover d 0 constant by simply computing equation d 0 = δ 1,0 -(a 0 ⊕ b 0 ⊕ c 0 ) -SS2 0 10. Recover h 0 constant by simply computing equation h 0 = δ 2,0 -(e 0 ⊕ f 0 ⊕ g 0 ) -SS1 0


Christophe Clavier

Léo Reynaud

Systematic and Random Searches for Compact 4-Bit and 8-Bit Cryptographic S-Boxes

Keywords: S-box design, Hardware implementation, Threshold implementation, Genetic algorithms

come

Introduction

The study presented in this paper has been initiated while designing the 8-bit Sbox of Lilliput-TBC tweakable block cipher submitted to the NIST Lightweight Cryptography Standardization Process [START_REF]Lightweight Cryptography[END_REF]. This 8-bit permutation has been defined as a 3-round Feistel construction based on three 4-bit functions S 1 , S 2 ,

The research work presented in this paper has been supported by PACLIDO French funded research project. Computations needed for this research work have been realized on the CALI supercomputer funded by University of Limoges and XLIM, IPAM and GEIST institutes. S 3 . While outer round functions S 1 and S 3 are Almost Perfect Nonlinear (APN) functions borrowed from the SCREAM cipher [START_REF] Grosso | SCREAM v3[END_REF], we focused on optimizing the choice of the inner round permutation S 2 .

For finding compact 4-bit permutations with good cryptographic properties we chose to explore circuits systematically in a bottom-up manner by starting from the empty circuit which corresponds to the identity function, and adding gates successively in an optimized breadth-first search. Doing so, because all circuits are exhausted for increasing numbers of gates, when one finds a circuit that encodes a permutation with specific properties, then this circuit is the most compact to achieve these criteria. While this strategy has been used in previous works [START_REF] Ullrich | Finding Optimal Bitsliced Implementations of 4× 4-bit S-Boxes[END_REF][START_REF] Canteaut | Construction of Lightweight S-Boxes using Feistel and MISTY structures (Full Version)[END_REF], we decided to allow only gates from the restricted set {AND, XOR}. This choice corresponds to Boolean functions that are easy to share when one wants to derive a Threshold Implementation (TI) of the circuit for side-channel security. In other words, our search is directed toward finding good permutations whose associated circuits are both as most compact as possible (for a given quality and with this given set of gates) and TI-friendly for masked hardware implementations. These properties also give benefits in software if one choose to implement our S-boxes in the bit-slice manner: the reduced number of gates makes the execution time smaller, and the TI-friendly design remains a desirable property for software masked implementations also.

During our systematic search for compact 4-bit S-boxes we noticed that in most interesting circuits an AND gate was quite often followed by a XOR taking as one of its inputs the output of the AND. While we could not give any explanation for this, we thought that this structure may favor the quality/compactness goal. We thus defined a new "AND-XOR" three-input composite gate and decided to extend our search to 8-bit circuits with only gates of types AND-XOR and XOR.

Contrarily to the 4-bit case, the huge number of 8-bit permutations (256! ≈ 2 1684 ) prevents our systematic approach to reach sufficiently long circuits to obtain interesting permutations. While finding good S-boxes directly in the set of 8-bit permutations is considered as a difficult task -it is commonly preferred to construct 8-bit permutations from 4-bit functions by means of Feistel, MISTY, Lai-Massey or SPN schemes -we still decided to undertake two kinds of guided random searches for 8-bit permutations. The first approach was to modify the systematic search tool that we used for 4-bit circuits: apart from redefining the set of gates as explained above and the number of bits to 8, we also left apart the systematic breadth-first approach and adopted a (still bottom-up) random depth-first search. The second approach was to use a genetic algorithm (GA) based on our same encoding of circuits as an ordered list of gates.

Previous Work As the S-box is the only non linear part of most encryption algorithms, finding permutations with good cryptographic properties has been widely studied. The three main principles of building such permutations are the random generation, the algebraic and the heuristic constructions. The first one fails to give good results as the exploration space is wide and suitable cryptographic properties very scarce [START_REF] Perrin | Cryptanalysis, Reverse-Engineering and Design of Symmetric Cryptographic Algorithms[END_REF]Table 9.2]. The second principle consists in finding expressions leading to good properties. The most illustrative design concerns inversion in the finite field with the S-box of AES being a famous example. The third one uses guided search in order to evolve permutations to find even better ones. It involves notably genetic algorithms principle (see [START_REF] Knezevic | Combinatorial Optimization in Cryptography[END_REF] for an overview on evolutionary techniques) and other techniques such as hill climbing [START_REF] Millan | How to Improve the Nonlinearity of Bijective S-Boxes[END_REF], gradient descent [START_REF] Kazymyrov | A Method For Generation Of High-Nonlinear S-Boxes Based On Gradient Descent[END_REF] and simulated annealing [START_REF] Clark | The Design of S-Boxes by Simulated Annealing[END_REF]. All those techniques aim to find as good as possibles permutations without considering their implementations. From an hardware point of view, in order to reduce the implementation cost, these techniques must be followed by an optimization phase which tries to find a cheap implementation of a particular table. Lot of work has been done in this path, particularly to be applied to the AES S-box (e.g. [START_REF] Canright | A Very Compact S-Box for AES[END_REF][START_REF] Boyar | New logic minimization techniques with applications to cryptology[END_REF]). While there exist some works that optimize and prove the optimality on 4-bit circuits [START_REF] Jean | Optimizing Implementations of Lightweight Building Blocks[END_REF][START_REF] Ko Stoffelen | Optimizing S-Box Implementations for Several Criteria Using SAT Solvers[END_REF], these techniques do not find the smallest circuit in general. A different approach to fulfill compactness of a circuit is to build small circuits that instantiate S-boxes with sufficient cryptographic properties. Ullrich et al. [START_REF] Ullrich | Finding Optimal Bitsliced Implementations of 4× 4-bit S-Boxes[END_REF] explore systematically all 4-bit circuits of a given number of gates before increasing this number, finding the optimal circuit for some classes of equivalence [START_REF] De | Analysis and Design of Symmetric Encryption Algorithms[END_REF][START_REF] Leander | On the Classification of 4 Bit S-Boxes[END_REF] with their set of gates. In order to reduce the size, Canteaut et al. [START_REF] Canteaut | Construction of Lightweight S-Boxes using Feistel and MISTY structures (Full Version)[END_REF] build 8-bit S-boxes from optimal 4-bit ones using results of [START_REF] Ullrich | Finding Optimal Bitsliced Implementations of 4× 4-bit S-Boxes[END_REF] in structures like Feistel or MISTY, until they obtain satisfactory results. Other works [START_REF] Begül Bilgin | Threshold Implementations of Small S-Boxes[END_REF][START_REF] Boss | Strong 8-bit Sboxes with Efficient Masking in Hardware (extended version)[END_REF] mainly reduce masking costs of such small S-boxes by decomposing cubic permutations into quadratic ones.

Our Contribution Inspired by the work of Ullrich et al. [START_REF] Ullrich | Finding Optimal Bitsliced Implementations of 4× 4-bit S-Boxes[END_REF] we developed our own tool that builds 4-bit circuits by adding successive instructions (gates) to the empty circuit. While they used {AND, OR, XOR, NOT, MOV} as their set of instructions, we restricted our search to use only AND and XOR1 . One can wonder whether this reduced set of instructions still allows to find a representative of an optimal class with as few instructions as them. Actually we answer positively to this question by exhibiting circuits belonging to the same optimal class with the same smallest gate count. Our first contribution thus shows that the TI-friendly property can be added to the more compact optimal 4-bit S-boxes with no penalty in term of circuit area for unmasked hardware implementations. Besides, our main contribution are two kinds of intensive search for compact circuits directly in the 8-bit permutations space. This led to a list of best S-box qualities that we can reach, ordered by the number of gates of their circuit. This list -which helps the S-box designer to answer the question What cryptographic quality can I expect for this given number of gates? -is provided in Table 1. These "records" are not absolute (some qualities may well be reached by smaller circuits in the future) but as far as we know this is the first attempt to provide a reference status of such a compactness-oriented search. It gives a large picture of the relation between quality and compactness in the range of rather small circuits for 8-bit permutations. Regarding our search by genetic algorithm, we encoded permutations by their hardware description. To the best of our knowledge, this is the first work that uses this encoding. Beside being gate count aware, it preserves structural portions of the circuit and seems to us more relevant than the encoding by table content of previous works.

Outline The paper is organized as follows. We define our cryptographic criteria, affine equivalence, and give background on threshold implementations in Section 2. Then we present our different searches for good and compact S-boxes: the systematic bottom-up search for 4-bit S-boxes is presented in Section 3, while Section 4 presents both the random bottom-up search and the GA-based search for 8-bit S-boxes, as well as a comparison with already known S-boxes. Finally Section 5 concludes this paper.

Preliminaries

Cryptographic Criteria to Optimize

Apart from optimizing our circuits with respect to their gate count, we also target good cryptographic quality based on the following criteria: Algebraic Degree Given a Boolean function f defined on F n 2 , its algebraic degree is defined as the maximal degree of the terms of its Algebraic Normal Form (ANF). The algebraic degree d of a permutation S of F n 2 is defined as the maximum algebraic degree of all its n component functions. We want to maximize d in order to better resist to algebraic or structural attacks.

Differential Uniformity

The differential uniformity δ of a permutation S is defined as:

δ(S) = max a =0,b |δ S (a, b)| where δ S (a, b) = #{x ∈ F n 2 : S(x ⊕ a) = S(x)
⊕ b} is related to the probability that an input difference a gives an output difference b. As we want to minimize this probability in the worst case (w.r.t. a and b) in order to make differential cryptanalysis [START_REF] Biham | Differential Cryptanalysis of DES-like Cryptosystems[END_REF] more difficult, we want to minimize δ(S).

Linearity The linearity L of a permutation S is defined as:

L(S) = max a,b =0 |W S (a, b)|
where the Walsh transform

W S (a, b) = x∈F n 2 (-1) a•x ⊕ b•S(x)
is related to the quality of the linear approximation f a,b (x) = a • x ⊕ b • S(x). The higher |W S (a, b)| the better the approximation. As we want to minimize the correlation in the worst case (w.r.t. a and b) in order to make linear cryptanalysis [START_REF] Matsui | Linear Cryptanalysis Method for DES Cipher[END_REF] more difficult, we also want to minimize L(S).

Affine Equivalence Classes

Two S-boxes S 1 and S 2 are said affine equivalent if there exist two invertible linear mappings A and B and two constants a and b such that

S 1 (x) = B • (S 2 (A • x ⊕ a) ⊕ b) ∀x ∈ F n 2 .
This defines affine equivalence classes which preserve the algebraic degree, the differential uniformity and the linearity coefficient of S-boxes. De Cannière [START_REF] De | Analysis and Design of Symmetric Encryption Algorithms[END_REF] has classified all 4-bit permutations in 302 classes. Leander et al. [START_REF] Leander | On the Classification of 4 Bit S-Boxes[END_REF] define an optimal S-box as one that has optimal resistance against differential and linear cryptanalysis (minimal values of δ and L). There exist 16 optimal classes of 4-bit S-boxes which correspond to the 16 first classes of [START_REF] De | Analysis and Design of Symmetric Encryption Algorithms[END_REF]. In the sequel we borrow the notation of [START_REF] Begül Bilgin | Threshold Implementations of Small S-Boxes[END_REF] for affine equivalence classes (A i , Q j , C k ) which gives the information whether the class contains affine, quadratic or cubic functions

Background on Threshold Implementations

Threshold implementation is a form of countermeasure aiming to prevent leakages provoked mainly by glitches in a hardware implementation of an algorithm [START_REF] Nikova | Secure Hardware Implementation of Nonlinear Functions in the Presence of Glitches[END_REF][START_REF] Bilgin | Threshold implementations: as countermeasure against higher-order differential power analysis[END_REF]. It consists in sharing variables and computations like in multiparty computation. A TI implementation of a function F (x) = a is done as follow: the variable x is split into s in input shares thanks to Boolean masking resulting in the sharing x = {x 1 , . . . , x sin } such that x = sin i=1 x i . Then, s out component functions F j (x 1 , . . . , x sin ) are calculated for j = 1, . . . , s out , each one giving an output share such that a = {F 1 (x), . . . , F sout (x)}. A TI implementation must fulfill the three following properties:

-Correctness: the XOR of output shares gives the intended result sout i=1 F i (x) = F (x), -Non completeness: each component function should be independent of at least one input share in order to provide first-order security, -Uniformity: for a permutation and s in = s out , then each sharing a is given by exactly one sharing x through functions F j .

The first property ensures that the result is correct and the second that no attacker is able to retrieve information about any variable when observing an output share. Both properties are relatively easy to implement. The last property is more difficult to fulfill but is only needed if other protected calculations use those outputs. Uniformity of sharing of input variables is mandatory, then if two calculations are done in a row, the first one must be uniform on its outputs in order for the second to have uniformity on its inputs. It may require to rearrange each output share without breaking the first two properties, or use fresh randomness. Notice that the TI of a function of degree d needs at least d + 1 shares in order to fulfill these three properties.

Systematic Search for Compact 4-Bit S-Boxes

We describe here the study and development of a tool dedicated to the finding of compact 4-bit S-boxes with good cryptographic properties. Beside its cryptographic quality, we also require our selected S-box to provide an easy and efficient threshold implementation for side-channel security.

This search has been done by exploring 4-bit circuits with a small number of gates in a systematic way, and selecting some that satisfy some given criteria to use them as part of a Feistel structure. The resulting candidates for the Lilliput-TBC 8-bit S-box were checked whether they have suitable cryptographic properties. We focused on 4-bit permutations that belong to optimal classes since these are the only ones that reach δ = 42 .

Our systematic bottom-up approach is very similar to that described in [START_REF] Ullrich | Finding Optimal Bitsliced Implementations of 4× 4-bit S-Boxes[END_REF]. Starting from the empty circuit that encodes identity function, we progressively add gates to build more complex circuits. Since we investigate all possible ways of adding a gate before adding another one -that means exhausting all kinds of gates, and all their input and output bits -, we thus explore a tree in a breadth-first way where each node corresponds to a circuit and each level to its number of gates. This method implies that each equivalence class is found with the least gate count with certainty. Note that even if a particular representative of a class is found with a given number of gates, it is not proven that any other representative could be expressed with the same amount of gates.

During the exploration, each node may have up to N g * Nr 2 * N r children, where N g is the number of gate types (in our case N g = 2) and N r is the number of registers 3 . To contain the exponential grows of the exploration, we use several tricks that either forbid some ways of adding gates, or prevent some nodes from further exploration. For instance, a gate should be added only if the following conditions are satisfied:

its output should not overwrite a register that has not yet been used as input of the current or of a previous gate, the result of a gate should not be 0, a gate should change the value of its output register. Also, we take care of the bit-permutation equivalence of circuits. We define that two circuits C 1 and C 2 , represented by tables T 1 and T 2 , are bit-permutation equivalent if there exist a permutation P 1 of the input bits and a permutation P 2 of the output bits such that

T 1 (x) = P 2 • T 2 • P 1 (x) ∀x ∈ F n 2 .
We keep only one representative circuit of each class of bit-permutation equivalence. To this end, we managed to define a canonical index of a circuit such that two circuits share the same index if and only if they are bit-permutation equivalent. Then when a circuit is considered, we compute its index and decide to not include it to the list of to-be-further-explored circuits if this index has already been encountered.

Results

We explored up to the 8-gate level with 5 registers with this approach, resulting in a list of smallest circuits (up to the bit-permutation equivalence).

We then only kept circuits resulting in a permutation. As the bit-permutation equivalence clearly does not change the affine equivalence class, we were able to find all circuits of smallest number of gates for some affine equivalence classes.

In the limit of 8 gates, we encountered 62 affine equivalence classes among which all quadratic ones as well as three optimal classes -namely C 223 , C 296 and C 297 -from one of which we identified a satisfactory permutation.

As we obtained many 8-gate circuits belonging to the above three optimal classes, we decided to select one that is particularly suited for threshold implementation (beside producing a good quality 8-bit S-box). We used the same trick as in [START_REF] Begül Bilgin | Threshold Implementations of Small S-Boxes[END_REF] to decompose a cubic permutation into two quadratics so that we can implement TI with only 3 shares. From their composition Another criterion to minimize the number of gates of the TI is to make sure that the quadratic circuits have a direct uniform sharing. This particular sharing is the simplest and does not require additional gates or randomness unlike when needing correction terms or re-masking. From [START_REF] Begül Bilgin | Threshold Implementations of Small S-Boxes[END_REF] only Q 4 , Q 294 and Q 299 can be directly shared. Using both previous observations, we composed 4-gate circuits of the class Q 294 with no permutation in between to avoid extra gates. We obtained several permutations of the class C 223 , and among all these solutions we had the opportunity to choose a permutation that results from the same quadratic circuit used twice (see Figure 1). As the search is exhaustive, there is no smaller circuit for each quadratic class. We used two circuits of 4 gates which is the minimum according to the composition table, and each one can be directly uniform shared resulting in the minimum of additional cost for the thresholding. Note that 8 gates is the minimum that we found for an optimal class without composition, C 223 being one of them. Referring to [START_REF] Ullrich | Finding Optimal Bitsliced Implementations of 4× 4-bit S-Boxes[END_REF], they also reach this class with 8 gates (they count 9 as they include the MOV instruction) with a larger set of gates 4 . We thus demonstrate that their exist TI-friendly representatives of this C 223 record class that do not need any extra gate.

Breadth-First Search with Level As we did not find all 302 classes with this method due to memory issues brought by the size of the heap of circuits to be explored, we chose to split the exploration on several parallel processes. This time, each process would not start the exploration with the empty circuit, but rather with an 8-gate portion of circuit, hence reducing the size of the heap to explore. This results in an increased number of circuits explored as these processes are independent and run in parallel. As a drawback, we lose some early-abort opportunities as circuits already explored in other parallel process are not detected. Nevertheless, this method allowed us to go as far as 10 gates (not exhaustively) and to find more classes including optimal ones.

Random Searches for Compact 8-Bit S-Boxes

Low implementation cost of 8-bit S-boxes is an important matter in lightweight cryptography. A number of already used implementations are based on Feistel, MISTY or SPN structures [START_REF] Canteaut | Construction of Lightweight S-Boxes using Feistel and MISTY structures (Full Version)[END_REF][START_REF] Boss | Strong 8-bit Sboxes with Efficient Masking in Hardware (extended version)[END_REF]. Here we try to find interesting permutations without these structures, directly in the 8-bit permutations space. We also keep the TI-friendly set of gates. Unlike for 4-bit circuits, it is unfeasible to systematically explore 8-bit ones, even for a few gates. We therefore tried two kinds of random explorations, a bottom-up and a genetic oriented one. Before describing those explorations, we introduce a particular gate setting that allows to speed up the search. A problem of generating circuits by adding random gates is that a very low proportion of them are permutations. This becomes particularly noticeable when changing from 4-bit to 8-bit circuits. Thanks to some observations from our 4-bit exploration, and from some S-box schemes presented by other authors, we have noticed that AND and OR gates are very likely to be followed by a XOR in low cost implementations. We thus chose to explore circuits using mostly a so-called "AND-XOR" gate that simply consists in a AND followed by a XOR. This composite gate takes three inputs -two for the AND and one for the XOR as its second input is the AND output -and gives one output. An interesting observation is that if the third input register is the same as the output register, then such a gate preserves the permutation property5 (see Figure 2). As this is also trivially the case for the XOR, we thus have a way to systematically explore into the permutations space. A drawback of this trick is that the set of reachable permutations is reduced, but this is largely compensated by the advantage that we do not have to waste most of computation time to consider non-permutation circuits.

Random Bottom-Up Search

We adapted the search tool described in Section 3. To this end, beside increasing the number of bits from 4 to 8, we changed the gate set to {AND-XOR, XOR}. Also, the search is no more a breadth-first systematic exploration, but an in-depth random process. It consists in repeating a huge number of times the generation of a random circuit, still in the bottom-up way by adding successive gates randomly. Notice that since the AND-XOR gate already includes a XOR, we put basic XOR gates only with a marginal probability.

We randomly built circuits using eight registers 6 . Each time we add a gate, cryptographic properties are evaluated and a list of best found figures is maintained for each gate count. After some tries, we noticed that the probability that a circuit gives good cryptographic results vanishes as the number of gates grows. More precisely, consider two generated circuits of the same size, one of low quality and one of higher quality. Then if we add a same few number of random gates to each of them, it is unlikely that the first resulting circuit becomes better than the second one. This led us to proceed by stages. First we generate from scratch many circuits of some size n 1 . We then select the better of them, and we pursue by adding gates to these promising circuits up to size n 2 > n 1 . We can continue this way by progressively adding gates stage by stage.

Indeed, this strategy gives rather better results than generating long circuits from the beginning in one shot. We had to make many runs, and try different ways of selecting circuits, as well as different number of stages and stage levels. After several weeks of computations on dozens of independent computing nodes, we have obtained "record" circuits ranging from about 10 to 50 gates that are presented in Table 1 in the "random search" column. For each gate count, the cell gives the best cryptographic quality we obtained -in terms of differential uniformity (δ) and linearity (L) 7 . For some sizes, we obtained several record circuits that are not comparable to each others. This happens when one circuit is better for some criteria while the other is better for the other criteria. In such cases, we provide all these non-comparable records.

Genetic Algorithm Search

Genetic algorithms (GA) are heuristic methods that mimic biologic processes of the evolution of life. They aim at finding as good solutions as possible to nonlinear and possibly multi-dimensional problems that are not possible to solve by deterministic methods. A genetic algorithm makes evolving a population of individuals represented by chromosomes which encode a particular solution to the problem to optimize. It typically comprises the following phases :

-Generate a random population of solutions -Randomly draw couples of individuals based on their fitness (quality) and create children by crossing parts of their parents (and eventually transform these children back into solutions if it is not the case) -Randomly mutate children -Mimic natural selection by preferentially selecting better solutions from the pool of parents and children and "killing" low fitness individuals -Iterate until a sufficiently good solution is found Genetic algorithms rely on the fact that crossing parts of medium or good quality individuals may give birth to a better solution by mixing together interesting parts of each parent. The mean quality of each generation is thus expected to increase over time, at least during the first generations.

A particularly important aspects of a genetic algorithm is the way chromosomes encode solutions to the problem to solve. Previous uses of GA [START_REF] Knezevic | Combinatorial Optimization in Cryptography[END_REF] were made to search good S-boxes but only focused on their cryptographic properties and did not considered the underlying circuit. On the contrary, we have chosen to encode S-boxes by their circuit rather than by their representative table. In our case, a chromosome is thus the ordered list of gates that defines the circuit. We see two advantages to proceed this way: First, it is possible to take into account the size of the circuit in the fitness of individuals, which allows our search to be compactness oriented. Also, there may exist structural aspects of the circuit which make sense from a cryptographic point of view. These will be preserved in most cases from one generation to the next.

As solutions are encoded by circuits that give permutations, the crossing over step of two individuals is simply done by swapping parts of their circuits. Actually, the main issue of applying GA principles to circuits is that the mating of two parents that encode permutations, may well result in a child that is no more a permutation. In this case we have to find a way to transform it back into a permutation. Fortunately we did not have to mind with this issue thanks to the use of our special kind of AND-XOR gates with particular output (XOR gate with result in place) as swapping parts of two circuits always ends up in permutations.

We present the main options and parameters that we used in our GA search for permutations.

First generation

The first generation is generated by random circuits of a given length. As an option, we can also insert some good solutions found from previous executions (or from circuits found with the random search). Fitness The definition of the fitness is also an important feature of a genetic algorithm. In our case, this was not straightforward as we had to solve a multi-criteria optimization: we want to minimize the number of gates, the differential uniformity and the linearity, and to maximize the algebraic degree. We ended up using two types of fitness computation. The first is based on the very simple weighted sum of those criteria. The second consists in ranking individuals with a derivative of dominance, and then giving an equal score to all individuals of a same rank. Our derivative of dominance is defined as follow: given two individuals I 1 and I 2 and their sets of n respective criteria {c 1 1 , . . . , c n 1 } and {c 1 2 , . . . , c n 2 }, we consider that

I 1 dominates I 2 if #{i : c i 1 > c i 2 } > n 2
, that is the number of criteria for which I 1 is better to I 2 is more than the half. Then individuals of rank 1 are defined as those who are dominated by no others. Individuals of rank 2 are those who are dominated by no other which are not of rank 1, and so on.

Selection of parents Parents are drawn thanks to two techniques. The first one is the roulette where each individual is being attributed a probability proportional to its fitness. Parents are then drawn repeatedly according to this probability law, with or without the possibility that an individual may be parent several times. The second consists in drawing uniformly two individuals, selecting the one with best fitness to be parent, and repeat until enough parents are obtained.

Crossover The crossover is done by randomly splitting circuits in three parts. Both intermediate parts are then swapped to give two children. Note that we require they have same length, but not necessarily same starting index (position in the circuit description).

Mutations Mutations are done with small probability. Four types of mutations are considered. The first one adds a random gate at a random indice in the circuit. The second removes a random gate. The third replaces a gate by a random one. The last swaps two consecutive gates if this does not change the resulting permutation.

Next generation

We use an elitist selection as the next generation is composed of the best individuals from both current generation and children. Each generation keeps the same number of individuals.

Diversity In order to keep the diversity of the population, we sometimes remove identical individuals, and can incorporate random individuals to be part of the next generation.

Results We searched by using many combinations of these options and parameters. We have made many tries and observed that like with the random bottomup search it was a good practice to use previously found good solutions. This was done by joining some of them to random individuals for the first generation.

Overall we have dedicated a bit less computation time to the genetic algorithm search than to the random bottom-up one. Though, interesting solutions have also been found as depicted in the column "genetic search" of Table 1. Here also each cell contains the best qualities (couples δ -L) that have been reached for this number of gates. We also highlighted in bold those qualities that have been found by one method while the other did not reached it for the same number of gates. As we can see results are globally about the same for both methods. Though, genetic algorithms are sightly better in the range of medium size circuits (27 to 46 gates) while the random bottom-up search tends to show advantageous for smaller and larger ones. Appendices A and B present two illustrative circuits alongside with their tables. They are the smallest ones we found that reach δ = 10 and δ = 8, with respectively 37 and 40 gates. As a curiosity, notice that the circuit of Appendix B is made of only AND-XOR gates.

• • • • • • • • • • • • 51 7 10 -56 8 -64 10 -60 • • • • • • • • • • • • 54 7 8 -60 8 -64 10 -56 • • • • • • • • • • • • 57 7 8 -

Comparison with Known S-Boxes

We refer to the S-box quality as the vector (d,δ,L). We only compare to relevant S-boxes, discarding qualities that we did not reached, or S-boxes with very low degree. Canteaut et al. [START_REF] Canteaut | Construction of Lightweight S-Boxes using Feistel and MISTY structures (Full Version)[END_REF] built an 8-bit S-box with quality [START_REF] De | Analysis and Design of Symmetric Encryption Algorithms[END_REF][START_REF] Canteaut | Construction of Lightweight S-Boxes using Feistel and MISTY structures (Full Version)[END_REF]64) in 38 gates, counting 3 × 4 XOR for the 3-round Feistel structure. We found a nearly equivalent solution (see Appendix B) that provides the optimal algebraic degree d = 7 at the cost of only two extra gates. Note that they particularly take into account the number of non-linear gates, whereas we have an equal number of AND and XOR gates.

Compared to the S-box proposed for Lilliput-TBC the picture is about the same. It is also a 3-round Feistel that achieves the same quality as [START_REF] Canteaut | Construction of Lightweight S-Boxes using Feistel and MISTY structures (Full Version)[END_REF]. It requires 39 gates but provides an optimized TI-oriented design. Again our S-box of Appendix B gives maximal degree for about the same size.

Referring to Table 1 of [START_REF] Canteaut | Construction of Lightweight S-Boxes using Feistel and MISTY structures (Full Version)[END_REF], we can also compare to S-boxes of Robin and Fantomas. These ciphers use (6,16,64) S-boxes that cost 36 gates while we achieve (7,16,64) with 30 gates.

In [START_REF] Boss | Strong 8-bit Sboxes with Efficient Masking in Hardware (extended version)[END_REF], Boss et al. propose several structured S-boxes. Unfortunately, they provide area figures rather than gate counts. We can somehow still manage to compare with some educated guesses on their raw implementations. As we found optimal circuits for quadratic 4-bit permutations, we will use them to estimate their circuit sizes. SB 1 uses 8 iterations of Q 294 which can be built with 4 gates. It ends up requiring roughly 32 gates to achieve (6,16,64), while we obtain [START_REF] Canright | A Very Compact S-Box for AES[END_REF][START_REF] Millan | How to Improve the Nonlinearity of Bijective S-Boxes[END_REF]64) with 30 gates only. SB 3 uses Q 293 , Q 299 and a matrix multiplication in a SPN like structure with 4 iterations. Only counting the two quadratics, both achievable in 6 gates, this results in more than 48 gates for a (7,8,60) permutation. We obtain the same quality with 54 gates. For SB 6 , that has quality (7,10,60), they use the same structure with 4 iterations. Only counting the quadratics Q 293 and Q 294 , it ends up with more than 40 gates while we found the same quality with 45 ones. Again this is not counting the cost of the matrix multiplication. SB 5 provides the same quality but without matrix multiplication, and uses 9 iterations of Q 4 and Q 294 which results in 54 gates, but on their Table 1 its area is less than that of SB 6 . We can guess that their multiplication is rather costly.

Notice that some of the above comparisons may not be totally fair. Indeed we have compared circuit sizes for unmasked implementations only. While our designs are TI-friendly (only AND and XOR gates), their size has not been optimized for a masked implementation. This sometimes results in circuits with more non-linear gates for a same gate count8 , which shows disadvantageous for protected implementations. Nevertheless we notice that in most cases, our results compare very well with -and are sometime better than -structured dedicated designs. We may expect that interesting results would have also been obtained if we had chosen to optimize the cost of a first-order protected TI implementation.

Conclusion

We have implemented and studied different methods for searching good and compact 4-bit and 8-bit S-boxes.

For 4-bit S-boxes we adapted a systematic search that has been investigated in previous works [START_REF] Ullrich | Finding Optimal Bitsliced Implementations of 4× 4-bit S-Boxes[END_REF][START_REF] Canteaut | Construction of Lightweight S-Boxes using Feistel and MISTY structures (Full Version)[END_REF] by restricting the set of gates to only AND and XOR in order to obtain circuits for which it is easy to find a threshold implementation. We found TI-friendly circuits of an optimal class still with the same smallest number of gates. Such a circuit has been used in the design of the 8-bit permutation of Lilliput-TBC lightweight block cipher.

For 8-bit S-boxes we chose to explore in the whole space of permutations rather than to restrain ourselves to structured designs. Beside giving more opportunities to find good solutions, this allowed us to easily obtain permutations with maximal algebraic degree. We have presented a random search that builds circuits in the bottom-up manner, and a genetic algorithm designed to optimize both cryptographic quality and circuit size for unmasked implementations. It happens that both methods give results that are competitive with previously known S-boxes. While we optimized our searches for the compactness of unmasked implementations, we managed to generate only TI-friendly circuits. We think that an interesting future work will be to adapt the genetic search by modifying the definition of the fitness in order to optimize the cost of a circuit protected by threshold implementation.

We hope that this work will convince that searching for unstructured S-boxes may be a promising approach, and will motivate further works in this direction.

A S-Box Reaching 7-10-80 Quality with 37 Gates

The 8-bit S-box of Table 2 reaches δ = 10 and L = 80 with a maximal algebraic degree d = 7. Figure 3 presents a 37-gate TI-friendly circuit of this S-box.

Fig. 1 .

 1 Fig. 1. The inner 4-bit S-box component of Lilliput-TBC

Fig. 2 .

 2 Fig. 2. Two AND-XOR composite gates: ordinary (left), preserving the permutation property (right)

Fig. 4 .

 4 Fig. 4. A 40-gate TI-friendly circuit of the 7-8-64 S-box of Table 3

  table, four optimal classes -namely C 223 , C 266 , C 296 and C 297 -can result from the composition of two quadratics. We hence decided to search representatives of the 6 quadratic classes with the least amount of gates to compose them and see if any optimal S-box can be built. As a result Q 4 is very small as it needs only 2 gates. Q 12 and Q 294 come next with 4 gates, and Q 293 , Q 299 and Q 300 need 6 gates. A composition of two of them would result in either 4, 6, 8, 10 or 12 gates. Looking at their composition table, no optimal class can result from compositions with as few as 4 or 6 gates. All four optimal classes need a minimum of 8 gates.

Table 1 .

 1 Best 8-bit S-boxes w.r.t. circuit size found by random and genetic searches

	60	8 -60

Table 2 .

 2 Table representation of an S-box with d = 7, δ = 10 and L = 80.Fig. 3. A 37-gate TI-friendly circuit of the 7-10-80 S-box of Table 2B S-Box Reaching 7-8-64 Quality with 40 Gates The 8-bit S-box of Table 3 reaches δ = 8 and L = 64 with a maximal algebraic degree d = 7. Figure 4 presents a 40-gate TI-friendly circuit of this S-box.

	0 1 2 3 4 5 6 7 8 9 A B C D E F
	00 00 63 02 11 06 BD 04 93 0B 09 08 5A 85 14 87 6F
	10 30 13 52 21 DB 91 B8 DE 5B 39 38 0A AD 2C EE 16
	20 20 01 64 FD EF 07 C3 A2 6B 6A AF 37 5E BC 40 4E
	30 31 10 ED 74 EA 92 7B 2A 1A 1B 47 FF 84 17 23 5C
	40 44 BE CC 27 22 43 E1 C2 CF 75 46 CD A3 58 60 6D
	50 54 CE DC 77 7F 2E 49 3B BF 65 36 DD 4A C0 7C 41
	60 EC 45 62 53 42 61 AC A9 26 AE 28 19 C1 78 3D 86
	70 55 FC 03 12 4D 3F 05 90 FE 76 29 18 E0 69 DF 15
	80 99 A8 9A 1F 1E E6 1D 9C 83 96 81 A0 8C 8A 8F 25
	90 2D 1C 6E EB 57 9F 35 A4 D7 E2 B5 94 B0 67 D2 89
	A0 DA 88 3E C4 A5 0F 4B 59 A1 D6 E5 BB 24 B1 F9 70
	B0 3C 0E D0 CA 56 8D F5 B6 82 95 4F F1 9D 98 E8 51
	C0 7D E4 C5 6C D9 CB 2B 7A C7 FB 7E F2 68 D5 BA 50
	D0 E9 F0 D1 F8 71 32 F6 B7 B3 2F AA A6 F4 79 73 C8
	E0 A7 4C B9 5F FA AB E7 34 5D B2 E3 80 48 F7 66 9E
	F0 D8 F3 8B 0D 72 33 0C 8E C6 C9 B4 97 3A D4 D3 9B

Table 3 .

 3 Table representation of an S-box with d = 7, δ = 8 and L = 64.

Actually, we also implicitly allow the MOV instruction, but we do not count it for 1 gate since this can been seen as a free wiring in hardware implementations. Regarding the NOT instruction, similarly to[START_REF] Ullrich | Finding Optimal Bitsliced Implementations of 4× 4-bit S-Boxes[END_REF], we observed that allowing it does not result in smaller circuits. If the fixed point 0 is a concern, one can just add a NOT gate at the beginning or at the end of the circuit at a quite small cost (even negligible for threshold implementations).

According to[START_REF] Canteaut | Construction of Lightweight S-Boxes using Feistel and MISTY structures (Full Version)[END_REF] an 8-bit S-box derived from a

3-round Feistel construction can reach δ = 8 only if both outer-round functions are APN and the inner-round function is a 4-bit permutation with differential uniformity equal to 4.[START_REF] Begül Bilgin | Threshold Implementations of Small S-Boxes[END_REF] The notion of register is particularly relevant for software implementations. Though, as in[START_REF] Ullrich | Finding Optimal Bitsliced Implementations of 4× 4-bit S-Boxes[END_REF] we decided to use Nr = 5.

If we add such a gate to a circuit that encodes a permutation, then the resulting circuit also encodes a permutation.

Actually, using the AND-XOR gate, an extra register is implicitly required to temporarily store the AND output.

[START_REF] Canright | A Very Compact S-Box for AES[END_REF] It happened that our best circuits (w.r.t. δ and L) always had maximal algebraic degree (except for quite small ones).

Notably, S-box of Appendix B uses 20 non-linear gates compare to only 12 for the S-box of[START_REF] Canteaut | Construction of Lightweight S-Boxes using Feistel and MISTY structures (Full Version)[END_REF] or that of Lilliput-TBC.