Christina Jérémy

Thomas ×2

Virginie Gregor

Gaëtan

Yu Medhi

REMERCIEMENTS

Tout comme pour ma thèse, je tiens à remercier en premier lieu Pierre-Alain Fouque. Après avoir été mon directeur de thèse pendant 3 ans à l'ENS où j'ai pu bénéficier de son appui scientifique et de ses excellents conseils, je suis heureux qu'il soit aujourd'hui le responsable de mon équipe de recherche, mon plus proche collègue, mon co-bureau et aujourd'hui un ami. Je suis vraiment reconnaissant pour tout ce qu'il m'a apporté, pour toutes nos discussions scientifiques ou non, et j'espère sincèrement que notre collaboration ne s'arrêtera pas là.

Je suis très reconnaissant envers les trois rapporteurs de ce manuscrit, Anne Canteaut, Henri Gilbert et Willi Meier, pour avoir examiné mon travail en le peu de temps qui leur était imparti, et ce, malgré des emplois du temps parfois chargés. Notamment je remercie Anne qui en acceptant de participer à ce jury était sûre d'être rapporteur, Henri qui était déjà membre de mon jury de thèse et Willi qui m'a soutenu scientifiquement. J'associe également à ces remerciements Sylvain Duquesne et Maria Naya-Plasencia qui ont tout deux accepté de participer à ce jury.

Je remercie chaleureusement toute l'équipe CryptoLUX de l'Université du Luxembourg pour les 2 années de postdoc que j'ai passé avec eux. Je remercie également tous les membres des équipes EMSEC, SPICY et CAPSULE de l'IRISA. Une mention spéciale pour Gildas Avoine et Mohamed Sabt avec qui j'ai toujours pris plaisir à échanger, et une autre à Stéphanie Delaune avec qui j'ai en plus encadré des étudiants et participé aux évènements de l'école Bourgchevreuil.

Je n'oublie pas mes co-auteurs que je remercie également, ainsi que mes 4 doctorants: Baptiste, Victor, Arthur et Hoa. Je tiens aussi à remercier tous les collègues qui font que les conférences et les workshops sont toujours des moments agréables. Une dédicace spéciale à Pierre-Alain,

List of Publications

Bibliography

GENERAL INTRODUCTION

The results presented in this manuscript are a logical continuation of the research initiated during my PhD. I have continued to improve cryptanalysis techniques and to develop tools and algorithms dedicated to cryptography, leading to several new attacks against block ciphers.

One of my major interests is to develop tools and algorithms for cryptanalysis. This implies to well understand cryptanalysis techniques and most often to improve and generalize them as well. Because the search space is typically huge, a large part of my work is about exploiting the structure of primitives and/or techniques to reduce it, in order to make the search practical. So far I contributed to many tools including a very versatile one about meet-in-the-middle and impossible differential attacks, an ad-hoc tool to search for integral distinguishers based on division property (handling for the first time division tables of Super-Sboxes), a new MILP/CP/ad-hoc approach to find the best boomerang distinguishers on SKINNY (Best Paper Award) and a dynamic programming-based algorithm to exhaust truncated differential characteristics on SKINNY as well. They all led to interesting new results as for instance longer integral distinguishers on Midori-64, SKINNY-64 and HIGHT, or boomerang distinguishers on SKINNY holding with much higher probability than previously known ones (up to 2 30 times higher).

I also studied algorithms dedicated to the conception of symmetric primitives, aiming at generating optimal components regarding various parameters. For instance in [START_REF] Derbez | Variants of the AES Key Schedule for Better Truncated Differential Bounds[END_REF], our goal was to find the best permutation which could be used as key schedule for AES in order to obtain an optimal resistance against differential attacks. But my main result in this area is about optimal permutations for Generalized Feistel Networks (GFN). Indeed, in [START_REF] Derbez | Efficient Search for Optimal Diffusion Layers of Generalized Feistel Networks[END_REF] and together with Pierre-Alain Fouque and my two PhD students, Baptiste Lambin and Victor Mollimard, we solved a 10-year open problem regarding the optimal diffusion rounds for 16-block GFN with the help of an original algorithm.

Finally, I am also particularly interested by practical attacks against cryptographic

Chapter 1 -General Introduction primitives. I participated to several challenges organized by designers of the block ciphers PRINCE and SKINNY and won some of them, especially the ones related to breaking as many rounds as possible using only a limited amount of plaintext/ciphertext pairs. I also studied some of the proposals of white-box implementation of AES and proposed a generic (and practical) attack against Baek et al. scheme. Very recently I also participated to the first publicly available cryptanalysis of both GEA-1 and GEA-2 stream ciphers, used to encrypt GPRS traffic in 2G technology and still present on modern phones. Following those results, the organisation responsible for telecommunications standards (ETSI) stated that new smartphones should not support those stream ciphers anymore. , if one is able to prove that there exists a pair of differences ∆ in , ∆ out ∈ F n b 2 such that E(p ⊕ ∆ in , k) = E(p, k)⊕∆ out for all keys, then it gives a strong distinguisher for the encryption function E. Because of the non-linearity of E, such a differential relation could only hold with a certain probability and a lot of work has been put into designing algorithms that search for the best possible differential distinguishers of a given cipher. For instance, Matsui designed two such algorithms in [START_REF] Matsui | On Correlation Between the Order of S-boxes and the Strength of DES[END_REF]. Most of modern ciphers are now built as iterated ciphers, where a round function f is built and repeated several times, XOR-ing a round key between each application of f , see Figure 2.1. Thus, to search for such a pair (∆ in , ∆ out ), one often studies the propagation of the input difference through each round of the cipher, leading to a differential characteristic consisting of all differences in each state s i .

One can also choose to consider only truncated differences, that is, only look at whether or not the difference in one byte is zero. While this can also directly lead to various attacks, as impossible differential attacks [START_REF] Biham | Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials[END_REF][START_REF] Knudsen | DEAL-a 128-bit block cipher[END_REF], it can also be used to get some results in differential cryptanalysis. Indeed, in most cipher designs, the non-linear component consists of an S-box, a small non-linear function applied several times over all iterations. This S-box is the reason that differential characteristic only holds with a certain probability. Given an S-box S acting on a small number of s bits, and for each pair (∆ in , ∆ out ) ∈ F 2s 2 , one can easily compute how many x ∈ F s 2 verifies the relation S(x ⊕ ∆ in ) = S(x) ⊕ ∆ out . This allows to compute the Difference Distribution Table (DDT) of the S-box, which gives the probability that the above relation holds for each (∆ in , ∆ out ). Thus, given a differential characteristic, one can compute the probability that it holds, simply by multiplying the differential probabilities of all S-boxes together 1 . Hence, given a truncated differential characteristic, while we cannot determine the exact probability that this characteristic holds, we can deduce its maximal probability. Indeed, if the S-box has a maximal differential probability of p, and there are n S-boxes with a non-zero difference (called active S-boxes), then the truncated differential characteristic holds with a probability at most p n . Thus, given the maximal differential probability of the S-box used and the bit-length n k of the key, one can easily deduce the minimal number of active S-boxes n min that leads to p n min < 2 -n k . So, if for a given number of rounds, we can prove that there are at least n min active S-boxes, we know that there would be no differential characteristic with a probability better than 2 -n k , which would mean that finding a pair of plaintexts satisfying this characteristic would a priori cost more than an exhaustive search for the key.

Such differentials and truncated differentials can also be considered in the relatedkey model. First introduced in 2009 to attack AES-192 and AES-256 [BK09; BKN09], this model allows the attacker to inject differences in the plaintext, but also in the key. Another worth-mentionning model is the more recent related-tweak model for tweakable block ciphers, where the attacker fully controls an additional input for the block cipher called a tweak [START_REF] Liu | Security Analysis of SKINNY under Related-Tweakey Settings (Long Paper)[END_REF][START_REF] Zong | MILP-Aided Related-Tweak/Key Impossible Differential Attack and its Applications to QARMA, Joltik-BC[END_REF]. While this model is closer to chosen-plaintext attacks, the tweak is often (but not necessarily) used alongside the key and thus involved in the key schedule, such as in the TWEAKEY framework [START_REF] Jean | Tweaks and Keys for Block Ciphers: The TWEAKEY Framework[END_REF]. Since the attacker can now inject some differences in both the plaintext and the key, this causes a large increase in the complexity to search differential and truncated differential characteristics. Nonetheless, several tools have been designed to tackle this problem [BN10; FJP13; Gér+18].

Designing an optimal key schedule for AES

A few proposals were made to give another, more secure, key schedule for some primitives, such as [START_REF] Nikolic | Tweaking AES[END_REF][START_REF] Choy | AES Variants Secure against Related-Key Differential and Boomerang Attacks[END_REF] for AES and [START_REF] Nikolic | How to Use Metaheuristics for Design of Symmetric-Key Primitives[END_REF] for SKINNY and AES-based constructions from FSE 2016 [START_REF] Jean | Efficient Design Strategies Based on the AES Round Function[END_REF]. However, their main concern was mostly to design a more secure key schedule, without considering the possible loss in efficiency. To that regard, Khoo et al. [START_REF] Khoo | Human-readable Proof of the Related-Key Security of AES-128[END_REF] proposed a new key schedule for AES which consists of only a permutation at the byte level, based on their proof on the number of active S-boxes in the related-key model for AES. Using a permutation thus leads to a very efficient key schedule, both in software and hardware, and can also make the analysis easier. However, they did not provide any proof of optimality for this permutation but showed that it increases the minimal number of active Sboxes compared to the original key schedule. Thus our main objective was to prove the optimality of their permutation or to find a better one.

Generic Bounds

Before trying to find a permutation that reaches a certain number of active S-boxes, we need to study which number of S-boxes we can reach. From the fact that using a permutation as the key schedule implies that the number of active bytes in the round keys is constant, we can deduce several bounds on the number of active S-boxes. To demonstrate these bounds, we show that there is always a differential characteristic of a certain number of active S-boxes, independently from the permutation used in the key schedule.

Proposition 1. Using a permutation as the key schedule, there is always a truncated differential characteristic of with 1 (resp. 5) active S-box(es) for 2 (resp. 3) rounds. For 4 rounds, there is always a truncated differential characteristic of with either 8, 9 or 10 active S-boxes. Such characteristics are depicted in Figure 2.2.

If we try to extend the previous characteristic with one more round, we obtain that there is always a characteristic with either 19, 20, 21, 24 or 25 active S-boxes in the truncated differential setting. However, by considering a totally different truncated characteristic we have the following proposition. Proposition 2. For 5, 6 and 7 rounds, there is always a characteristic with respectively 14, 18 and 21 active S-boxes in the truncated differential setting. Such truncated characteristics are depicted in Figure 2.3. Now the first question that we may ask is whether or not there exists a permutation which reaches all those bounds. Fortunately, such a permutation was already found by

Better Model

The main issue regarding truncated differential characteristics is that some of them may be false, in the sense that it is impossible to find actual values satisfying the characteristic. In order to remove some of these impossible truncated characteristics we used the model proposed by Gérault et al. in [Gér+18]. They noticed that because the Mix-Columns operation is linear, the MDS property of the matrix also applies to the sum of two columns. More precisely we have the following property: Proposition 3. Let z and z be two state columns, w(z) and w(z ) the number of active bytes and M C the MixColumns matrix. Let y = M C(z) and y = M C(z ). Since the matrix M C is MDS we have the three constraints:

-w(z) + w(y) = 0 or ≥ 5 -w(z ) + w(y ) = 0 or ≥ 5 -w(z ⊕ z ) + w(y ⊕ y ) = 0 or ≥ 5
This proposition is highly effective when the key schedule of AES is replaced by a permutation as it may forbid differences on particular bytes to be the same or to be distinct. Actually we can go a bit further with the next proposition. Proposition 4. Let k, x, y, z be four state columns such that M C(z) = y, z contains at least one active byte and x = y ⊕ k . Denote by i y,z the number of inactive bytes in y and z (i.e., i y,z = 8 -w(y) -w(z) ) and c z,k,x the number of bytes from z that are cancelled by k in x . If i y,z + c y,z,k ≥ 5 , then there is at least one linear equation on some bytes of k . Moreover, this can only happens if c y,z,k ≥ 2.

Algorithms and Results

We used the two previous propositions to refine the definition of truncated differential characteristics. More precisely, they allow us to define a more sophisticated model in which extra linear constraints are added and have to be satisfied to expect a valid differential characteristic.

Model.

It takes as input a permutation P k to use as the key schedule and a number of rounds, and output the minimal number of active S-boxes with these parameters in the truncated differential setting. We do take into account the equations coming from the MixColumns operation, resulting in a more reliable result, albeit being slower.

Bound on 5 Rounds

Using our new model we were able to refine the bound for 5 AES rounds. We showed there is no permutation that, when used as key schedule, can reach a minimal number of active S-boxes of 18 or higher over 5 rounds. To get this result we mainly used the decomposition of permutations into cycles, identifying the cycles which could belong to a permutation with a number of minimal active Sboxes of 18, i.e. removing cycles leading to a truncated characteristic with less than 18 active Sboxes. Once all such cycles were obtained we tried to compose them and searched for the minimal number of active Sboxes for each resulting permutation.

Unfortunately, our algorithm was too slow to exhaust the case with 17 active Sboxes. However, we were able to perform it partially with 16 active Sboxes and found one permutation which has a minimal number of active S-boxes of 16 over 5 rounds, namely: (15 0 2 3 4 11 5 7 6 12 8 10 9 1 13 14) .

Bound on 6 Rounds

Due to the huge space search, we used a totally different approach for 6 rounds. Inspired by the work of Nikolic [START_REF] Nikolic | How to Use Metaheuristics for Design of Symmetric-Key Primitives[END_REF], we used a meta-heuristic called simulated annealing. Metaheuristics are a class of search algorithms which aim to find an (almost) optimal solution to an optimization problem, often inspired by some real-life phenomenon. To be more precise, unlike Constraint Programming or Integer Linear Programming which aims at recovering an optimal solution, meta-heuristics only look for a good enough solution: it may not be optimal, but it should be rather close to an optimal solution. We first launched our algorithm for 20 active S-boxes, and were able to find the permutation P k (given below) reaching this minimal number of S-boxes in about 2 16 tries: P k := (8 1 7 15 10 4 2 3 6 9 11 0 5 12 14 13) Reaching 21 S-boxes is still an open question and for reference, we were able to test about 2 24 permutations in several days.

Tweaking Both ShiftRows and the Key Schedule

Finally, we tried to see if by changing the ShiftRows operation in the AES-128, we could reach a better number of active Sboxes, namely 21 or 22. Obviously, we cannot try all possible permutations for ShiftRows as there are 2 44 permutations over 16 elements, and trying 1 permutation takes a non-marginal time.

Relying on some equivalence relations and restricting ourself to permutations achieving full diffusion in at most 3 rounds, we got 3288 possible candidates for the permutation P s .

We used our meta-heuristic algorithm on several of them and found a pair of permutation (P s , P k ) reaching 21 active Sboxes after an hundred of trials, trying 2 25 permutations P k for each of them. We also searched for a pair of permutations reaching 22 active Sboxes but were not able to find one after trying a thousand of permutations P s .

Chapter 2 -Computer-aided Design of Optimal Components

The fact that we were able to build a more resistant cipher from a non-optimal ShiftRows operation (achieving full diffusion in 3 rounds instead of 2) is quite interesting as it shows that combining optimal cipher components is not the necessarily optimal.

Optimal Diffusion Layers of Generalized Feistel

Networks

The Feistel network is one of the main generic designs for building modern block ciphers. It was initially proposed in the data encryption standard DES [START_REF] Des | Data Encryption Standard[END_REF], and is still used in more recent ciphers such as Twofish [START_REF] Schneier | Twofish: A 128-bit block cipher[END_REF], Camellia [START_REF] Aoki | Camellia: A 128-Bit Block Cipher Suitable for Multiple Platforms -Design and Analysis[END_REF] or SIMON [START_REF] Beaulieu | The SIMON and SPECK Families of Lightweight Block Ciphers[END_REF]. The idea behind this construction is to split the plaintext into two halves x 0 , x 1 , and build the round function which sends (x 0 , x 1 ) to (x 1 , x 0 ⊕ F i (x 1 )), where F i is a non-linear function for the i-th round. In 1989 at CRYPTO, Zheng et al. [START_REF] Zheng | On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses[END_REF] proposed some generalizations of the Feistel construction. Especially, they defined the Type-2 Feistel2 construction, which splits the message into 2k blocks and uses a round function of the form (x 0 , . . . , x 2k-1 ) → (x 2k-1 , x 0 ⊕ F i,0 (x 1 ),

x 1 , x 2 ⊕ F i,1 (x 3 ), x 3 , . . . , x 2k-2 ⊕ F i,k-1 (x 2k-1 )),
where each F i,j is a pseudorandom function for the i-th round (Figure 2.4). This is essentially a parallel application of k Feistels followed by a cyclic shift of the blocks. An interesting property is that when all F i,j are pseudorandom functions, then 2k + 1 rounds are enough to make the corresponding block cipher indistinguishable from a random permutation. At ASIACRYPT'96, Nyberg [START_REF] Nyberg | Generalized Feistel Networks[END_REF] studied a variant of the Type-2 Feistel construction using a different permutation than the cyclic shift, called Generalized Feistel Network (GFN). Definition 1. Let 2k be an even number, n, r be positive integers, and {F i,j } i∈{1,...,r},j∈{0,...,k-1} be a set cryptographic keyed functions from F n 2 to F n 2 . Let π be a permutation over 2k elements. A Generalized Feistel Network is a block cipher built as

R r • • • • • R 1 , where R i is the round function R i : (X 0 , . . . , X 2k-1 ) → π(X 0 ⊕ F i,0 (X 1 ), X 1 , . . . , X 2k-2 ⊕ F i,k-1 (X 2k-1 ), X 2k-1 )

Optimal Diffusion Layers of Generalized Feistel Networks

X i 0 X i 0 X i 1 X i 1 S X i+1 0 X i+1 1 X i 2 X i 2 X i 3 X i 3 S X i+1 2 X i+1 3 X i 2k-4 X i 2k-4 X i 2k-3 X i 2k-3 S X i+1 2k-4 X i+1 2k-3 X i 2k-2 X i 2k-2 X i 2k-1 X i 2k-1 S X i+1 2k-2 X i+1 2k-1 π Figure 2.4 -Generalized Feistel Network
Such a construction was used to design more recent block ciphers as for instance TWINE [START_REF] Suzaki | TWINE : A Lightweight Block Cipher for Multiple Platforms[END_REF] and Piccolo [START_REF] Shibutani | Piccolo: An Ultra-Lightweight Blockcipher[END_REF].

In the following neither the exact definition of the keyed functions F i,j nor their sizes are relevant. We thus consider all of them as an arbitrary S-box S, leading to the framework depicted in Figure 2.4. As the only variable parameters are thus k and π, we denote by GFN k π a GFN with 2k blocks that uses the permutation π.

The Problem

It is easy to see from Definition 1 that X 1 π(0) depends on X 0 0 and X 0 1 . More generally, any block X r j depends on several blocks from the round 0, i.e. computing X r j requires some blocks {X 0 j 0 , . . . , X 0 j l }. We say in that case that any of these X 0 j i diffuses to X r j , and we focus our study on the number of rounds needed to reach full diffusion. Definition 2. Let π be a permutation over 2k elements. We say that a block X 0 j fully diffuses after r rounds if for all i ∈ {0, . . . , 2k -1}, X 0 j diffuses to X r i . We say that π reaches full diffusion after r rounds if for all j ∈ {0, . . . , 2k -1}, X 0 j fully diffuses after r rounds. The smallest r that verifies this property for the block X 0 i is called the diffusion round of the block X 0 i .

Note that we need to study both the diffusion over the encryption and the decryption process. Indeed, there is no guarantee that an encryption function with good diffusion also keeps this property for its inverse. Since we have (GFN k π ) -1 = GFN k π -1 , we need to study both the diffusion of π and π -1 . Naturally, we would like both π and π -1 to fully diffuse as quickly as possible, which leads to the following definition. Definition 3. Let π be a permutation over 2k elements. Denote by DR i (π) the minimum number of rounds r such that X 0 i fully diffuses after r rounds in GF N k π . The diffusion round of a permutation π is:

DR max (π) = max 0≤i≤2k-1 DR i (π), DR i (π -1 ) (2.1)
This definition gives the same importance to the total diffusion of both π and π -1 . Definition 3 defines a natural partial order on the permutations: a permutation π 1 is better (at diffusing) than a permutation π 2 if DR max (π 1 ) ≤ DR max (π 2 ). A natural problem regarding GFN is thus to determine the optimal permutations, the ones leading to the most secure constructions.

Suzaki and Minematsu [SM10]

Searching for the best permutations (for the diffusion) directly can be difficult. A naive way to search for optimal permutations would be to simply go through all of them and check the diffusion one permutation by one. However, there are (2k)! permutations, which quickly grows beyond practical means. For example with 2k = 32, approximately 2 117 permutations should be checked.

In [START_REF] Suzaki | Improving the Generalized Feistel[END_REF], Suzaki and Minematsu did an exhaustive search for 1 ≤ k ≤ 8, and made the observation that every optimal permutation (for such k) mapped even-number input blocks to odd-number output blocks and vice versa. We call such permutations even-odd.

An even-odd permutation π of size 2k is denoted by a pair of permutations (p, q) of size k verifying ∀i ∈ [0, k -1], π(2i) = 2 • p(i) + 1 and π(2i + 1) = 2 • q(i). The search space is now reduced to (k!) 2 permutations.

Cauchois et al. [CGT19]

To further reduce the size of the search space, Cauchois et al. observed that given two even-odd permutations π = (p, q) and π = (p , q ), if p and p share the same cycle structure and if q = q then the corresponding block ciphers do share the same diffusion round. This directly comes from the fact that the diffusion round is invariant by block reordering.

As a consequence, there are only N k .k! permutations to consider instead of (k!) 2 , where N k is the number of partitions of the integer k (which is equal to the number of cycle structures for p). This is a significant improvement and it allowed Cauchois et al. to perform an exhaustive search up to 2k ≤ 24.

A New Algorithm

While Cauchois et al. significantly reduced the search space, they checked the remaining permutations one by one. In [START_REF] Derbez | Efficient Search for Optimal Diffusion Layers of Generalized Feistel Networks[END_REF], a joint work with Pierre-Alain Fouque and my two PhD students Baptiste Lambin and Victor Mollimard, we proposed a new algorithm to exhaust this restricted search space in a more clever way.

New representation

The first step of our approach is to give a better representation of the problem for even-odd permutations. Let π = (p, q) be an even-odd permutation, r a positive integer and J r the set of all permutations σ such that σ

= p α 1 • (p • q) β 1 • . . . • p αn • (p • q) βn with α 1 + . . . + α n + 2β 1 + . . . 2β n = r. Let us also define J r i as the set {σ(i) | σ ∈ J r }. We show that π fully diffuses after R rounds if and only if |J R-3 i | = k for all integers i ∈ [0, k -1].
For example, we give in Table 2.2 the diffusion tables for the cyclic shift (p = (7, 0, 1, 2, 3, 4, 5, 6) and q = (0, 1, 2, 3, 4, 5, 6, 7)) and one of the optimal permutations proposed by [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF] (p = (6, 3, 7, 1, 0, 2, 4, 5) and q = (3, 5, 1, 6, 4, 0, 2, 7)) for k = 8 and R = 8.

New algorithm

Let us pick a permutation p and assume we want to find q such that |J r x | = k for all x ∈ [0, k -1]. We can first pick x 0 ∈ [0, k -1], guess enough images of q to compute J r x 0 and then check whether |J r x 0 | = k or not before repeating the process. To minimize the number of guesses between each check we propose the following strategy:

-Pick x 0 on the smallest cycle of p; -If not already processed, set x i+1 = p(x i ).

To support this strategy, let us study the case r = 5 as an example. Computing J 5

x requires to guess the images of 11 elements by q: {x, p(x), p 2 (x), p 3 (x), p 4 (x), pq(x), p 2 q(x), p 3 q(x), pqp(x), p 2 qp(x), pqp 2 (x)}.

If x belongs to a small cycle of p then several of those elements will be the same, decreasing the number of guesses to perform. For instance, if x is a fixed point of p then we have to Chapter 2 -Computer-aided Design of Optimal Components i 0 1 2 3 4 5 6 7 p 5 3 4 5 6 7 0 1 2 p 4 q 4 5 6 7 0 1 2 3 p 3 qp 4 5 6 7 0 1 2 3 p 2 qp 2 4 5 6 7 0 1 2 3 pqp 3 4 5 6 7 0 1 2 3 qp 4 4 5 6 7 0 1 2 3 p 2 qpq 5 6 7 0 1 2 3 4 pqp 2 q 5 6 7 0 1 2 3 4 qp 3 q 5 6 7 0 1 2 3 4 pqpqp 5 6 7 0 1 2 3 4 qp 2 qp 5 6 7 0 1 2 3 4 qpqp 2 5 6 7 0 1 2 3 4 qpqpq 6 7 0 1 2 3 4 5

|J 5 i | 4 4 4 4 4 4 4 4
i 0 1 2 3 5 6 7 p 5 4 3 5 1 7 0 2 p 4 q 3 2 1 4 6 7 5 p 3 qp 2 6 7 5 3 4 0 p 2 qp 2 6 7 4 0 2 3 1 pqp 3 1 4 3 2 6 7 5 qp 4 2 5 7 6 1 4 0 p 2 qpq 7 1 0 6 5 2 4 pqp 2 q 4 5 2 1 0 6 3 qp 3 q 5 0 6 2 3 1 7 pqpqp 5 0 6 3 4 1 7 qp 2 qp 0 3 1 7 5 2 4 qpqp 2 3 1 2 4 0 5 6 qpqpq 1 6 4 3 7 0 2 {x, pq(x), p 2 q(x), p 3 q(x)}.

|J 5 i | 8
Next, computing J 5 p(x) requires to guess the images of 11 elements by q:

{p(x), p 2 (x), p 3 (x), p 4 (x), p 5 (x), pqp(x), p 2 qp(x), p 3 qp(x), pqp 2 (x), p 2 qp 2 (x), pqp 3 (x)}.
We observe that several of them were already required to compute J 5

x and thus we have to guess at most 4 new images:

{p 5 (x), p 3 qp(x), p 2 qp 2 (x), pqp 3 (x)}.
However, if p does not have a small enough cycle, the overall complexity is quite close to k! since q has to be almost fully guessed to compute the first set J r x 0 . To lower the number of guesses one have to perform, we can adopt a different strategy. Because of the structure of J r we can define P r x and Q r x such that J r x = P r x ∪ Q r x and J r+1 x = q(P r x ) ∪ p(J r x ) for any integers r and x. Now let us assume we guessed enough 20

Optimal Diffusion Layers of Generalized Feistel Networks

images of q to compute J r-1 . Instead of guessing images of each element from P r-1

x by q we keep the constraint:

[0, k -1] \ (p(J r-1 x ) ∪ q(P r-1 x \ A)) ⊂ q(P r-1 x ∩ A),
where A is the set of unset elements by q. This is very effective to decrease the number of guesses made between each check. For instance, with r = 5, we now need to guess the images of only 7 elements:

{x, p(x), p 2 (x), p 3 (x), pq(x), p 2 q(x), pqp(x)}.
Note that the constraint should be checked in two steps and updated each time a new guess is performed. First we verify that

| [0, k -1] \ (p(J r-1 x ) ∪ q(P r-1 x \ A))| ≤ |P r-1 x ∩ A| and then that |p(J r-1 x ) ∪ q(P r-1 x \ A) ∪ I| = k where I is the set of unset images of q.
To reduce further the number of guesses, we can write

J r x = p 2 (J r-2 x ) ∪ qp(J r-2 x ) ∪ pq(P r-2
x ) and keep the constraint:

[0, k -1] \ (p 2 (J r-2 x ) ∪ pq(P r-2 x \ A) ∪ q(p(J r-2 x ) \ A)) ⊂ pq(P r-2 x ∩ A) ∪ q(p(J r-2 x ) ∩ A).
But verifying this constraint is complicated and thus our idea is to only verify a weaker version. More precisely, we verify that there exist two sets S 1 ⊂ p(I) and S 2 ⊂ I such that

|S 1 | = |P r-2 x ∩ A|, |S 2 | = |p(J r-2 x ) ∩ A| and [0, k -1] \ (p 2 (J r-2 x ) ∪ pq(P r-2 x \ A) ∪ q(p(J r-2 x ) \ A)) ⊂ S 1 ∪ S 2 .
In practice it is rare for the weaker constraint to be satisfied while the original one is not. Furthermore it is very fast to check it as it requires computing the size of only few intersections of sets.

It seems natural to try writing J r x using J r-3

x and P r-3

x but unfortunately the corresponding weaker constraint does not filter enough to reduce the overall complexity.

Results

Using our new approach, we were able to prove that with even-odd permutations:

-For k = 14, 15, 16 and 18, the optimal number of rounds for full diffusion is 9.

-For k = 17, the optimal number of rounds for full diffusion is 10.

-For k = 19, 20 and 21, the optimal number of rounds for full diffusion is at least 10 and at most 11. In particular we solved the 10-year-old problem of finding optimal permutations for 32 blocks GFN.

Open problems

There are still many open problems regarding optimal permutations for GFN. In our opinion, the most interesting one would be to show that for any value of k there is at least one optimal permutation which is even-odd. To evaluate the security of cryptographic primitives, cryptographers aim at finding the best possible attacks and distinguishers, which typically means the ones covering as many rounds as possible with the smallest complexity. Doing so most often requires to explore a large search space in order to find the best parameters for the technique. The help of a computer is thus becoming mandatory in cryptanalysis works to support researchers. I dedicated a large part of my research in developing tools for this purpose and I will present three of them ([DF16; DF20; DDV20]) in this chapter.

Demirci-Selçuk Meet-in-the-Middle Attacks

During my PhD I mainly worked on improving the Demirci-Selçuk attacks [START_REF] Demirci | A Meet-in-the-Middle Attack on 8-Round AES[END_REF], a type of advanced meet-in-the-middle attacks, and obtained some of the best known

Generalized Demirci-Selçuk (GDS) Attack

To design the tool we needed to generalize the original attack of Demirci and Selçuk against AES. We thus proposed a generic view of this cryptanalysis technique applicable to any block ciphers. Let E = E 3 • E 2 • E 1 be an encryption function split into three parts. For the first step we pick a truncated difference ∆ X with b i active bits, propagate it through

E -1 1 (resp. E 3 • E 2 )
with probability 1 and denote the set of active bits by I P (resp. I C ). Then, for the second step, we mount a basic meet-in-the-middle attack against To explain further the GDS attack we introduce the definition of a b-δ-set:

E = E 3 • (E 2 • E 1 ): let Y be the output state of E 2 • E 1 ,
Definition 4 (b-δ-set). A b-δ-set is a set of 2 b
states such that b bits are active and take all the possible values while the others bits are constant. We also assume that the states of a b-δ-set are sorted according to differences.

Demirci-Selçuk Meet-in-the-Middle Attacks

The structure of the Generalized Demirci-Selçuk attack is then as follows:

-Offline phase:

1. Consider the encryption of a b i -δ-set {x 0 , x 1 , . . .} corresponding to the truncated difference ∆ X through E 2 .

2. Guess the value of internal bits from I C ∩ O P for message x 0 .

3. Deduce the differences in the b o chosen bits of Y for the b i -δ-set.

4. Store them as a sequence of

2 b i -1 b o -bit values in a hash table.
-Online phase:

1. Pick a plaintext P .

2. Guess the value of I P for P and identify a set {P, P 1 , P 2 , . . .} leading to a b i -δ-set associated to ∆ X .

3. Ask for the corresponding ciphertexts.

Remarks:

-In the case where the truncated difference ∆ X does not make ∆ P fully active, i.e. differences in some plaintext bits are null, the attack can be turned into a chosen-plaintext attack by asking either for a structure of plaintexts. Actually this is (almost) always better to do so since, in general, (2 b i -1) • S(I P ) is greater than 2 |∆ P | .

Chapter 3 -Tools for Cryptanalysis

-Some extra memory can be used to map each sequence to its corresponding value of I C ∩ O P . -Given two invertible matrices M 1 and M 2 , we can rewrite the encryption function

E = (E 3 • M -1 2 ) • (M 2 • E 2 • M -1 1 ) • (M 1 • E 1 )
. Hence the sentences "with b i active bits" or "pick b o bits of Y " should be understood as "with b i active linear combinations of bits" or "pick b o linear combinations of bits of Y ".

A New Ad-hoc Tool

To handle as many block ciphers as possible we used a generic representation of a block cipher. Namely, it has to be represented using equations as:

α i S i,j (x σ(0) , . . . , x σ(j) ) + β j x j + c = 0,
where the α i 's, β j 's and c belong to the same finite field and where the S i,j are seen as black box Sboxes. We then faced several problems to design an efficient tool.

Linear combinations. A priori, to fully explore the search space, we have to try all pairs of invertible matrices M 1 and M 2 and write

E = (E 3 • M -1 2 ) • (M 2 • E 2 • M -1 1 ) • (M 1 • E 1 )
. But the size of internal states of typical block ciphers forbids such a naive approach. Instead we developed a branch-and-cut algorithm in which minimal equations (i.e. equations involving a minimal set of variables regarding the inclusion) are exhausted using an early abort strategy, removing the ones that would not lead to an optimal attack. We refer the interested readers to [START_REF] Derbez | Automatic Search of Meet-inthe-Middle and Impossible Differential Attacks[END_REF] for more details on the algorithm.

Evaluating the complexities. As explained above, determining the data, time and memory complexities requires an algorithm computing S(X) and T (X) under the constraints of the block ciphers equations for any set of variables X. While the generic problem is complicated, in our case it is only about finding relations between the (linear combinations of) round key bits involved in the attack. To solve the problem we used an adapted version of the tool we developed with Charles Bouillaguet during my PhD [START_REF] Bouillaguet | Automatic Search of Attacks on Round-Reduced AES and Applications[END_REF].

AND and OR.

Handling multi-variables S-boxes naturally leads to the particular case of AND and OR. While until now S-boxes were considered as black boxes, both those functions have a special property that can be properly handled. Indeed, the following equation holds for any variables x and y: AND(x, y) ⊕ AND(x ⊕ ∆x, y ⊕ ∆y) = AND(x, ∆y) ⊕ AND(∆x, y) ⊕ AND(∆x, ∆y).

In particular, if ∆y = 0 then AND(x, y) ⊕ AND(x ⊕ ∆x, y) = AND(∆x, y), meaning that computing the difference after the AND requires ∆x and y but not the actual value of x. This is also true for the OR operator since OR(x, y) = AND(x, y) ⊕ x ⊕ y. As a consequence, in the previous algorithms, we have to define new sets I P , I C , O P and O C containing the variables required to compute the differences in each variable of I P , I C , O P and O C respectively, and use them instead for the complexity computations.

Applications

Our tool handles a large class of block ciphers and allowed us to find several new attacks. For instance it found the best known attacks against the block cipher mCrypton, breaking one more round for all the three key sizes.

Interestingly, the building blocks of our tool can be used in a straightforward way to search for basic meet-in-the-middle attacks and impossible differential attacks. For instance we automatically recovered the 6-round meet-in-the-middle attack described by Biham et al. in [START_REF] Biham | New Attacks on IDEA with at Least 6 Rounds[END_REF] against IDEA and found better impossible differential attacks against SIMON than Boura et al. in [START_REF] Boura | Scrutinizing and Improving Impossible Differential Attacks: Applications to CLE-FIA, Camellia, LBlock and Simon[END_REF].

Algorithms for Division Property

Integral cryptanalysis exploits distinguishers computing the sum of ciphertexts corresponding to a set of plaintexts spanning a linear subspace. This technique was originally introduced by Knudsen in [START_REF] Daemen | The Block Cipher Square[END_REF] as a specific attack against the byte-oriented structure of the block cipher SQUARE and unified by Knudsen and Wagner in [START_REF] Knudsen | Integral Cryptanalysis[END_REF]. In 2000, Ferguson et al. [START_REF] Ferguson | Improved Cryptanalysis of Rijndael[END_REF] presented at FSE powerful attacks based on integral distinguishers against round-reduced versions of AES, named Partial Sum attacks. In particular they described a practical attack against 6 rounds which is still one of the best known attacks against AES. Integral distinguishers [START_REF] Biryukov | Structural Cryptanalysis of SASAS[END_REF] were found by propagating through the round functions simple properties on words composing the internal states: ALL (the word takes all the possible values once), BALANCED (the word sums to zero), CONSTANT (the value of the word is constant).

Chapter 3 -Tools for Cryptanalysis

The so-called division property, introduced by Todo at Eurocrypt'15 [START_REF] Todo | Structural Evaluation by Generalized Integral Property[END_REF], is a method to find more sophisticated integral distinguishers. The idea behind the division property technique is actually quite simple. Let f and g be two n-bit functions and assume the goal is to find an integral distinguisher on g • f without computing it explicitly. Let y i = f i (x 0 , . . . , x n-1 ) and z i = g i (y 0 , . . . , y n-1 ) be the intermediate and final expressions of the coordinate functions of f and of g, and let m z be a monomial in the z i 's, and so m z is a polynomial consisting of some monomials m y . Division property actually captures that if for a subset X of F n 2 each monomial m y appearing in m z satisfies x∈X m y (x) = 0 then x∈X m z (x) = 0. Several variants of this property were used to find integral distinguishers. For instance, in [START_REF] Todo | Bit-Based Division Property and Application to Simon Family[END_REF], Todo and Morii used that if all monomials m y but one sum to zero then x∈X m z (x) = 1. And more recently, in both [START_REF] Hao | Modeling for Three-Subset Division Property Without Unknown Subset -Improved Cube Attacks Against Trivium and Grain-128AEAD[END_REF] and [START_REF] Hebborn | Lower Bounds on the Degree of Block Ciphers[END_REF], the exact relation was used: x∈X m z (x) = 0 if and only if the number of monomials m y for which x∈X m y (x) = 1 is even.

In practice we cannot try all possible sets X nor compute the corresponding sums for all monomials involved in the description of a cryptographic primitive. Furthermore we typically want integral distinguishers independent from the key, adding an extra complexity to the problem. However it is easy to show that if P is a polynomial in variables (x 1 , . . . , x n ) then (x 1 ,...,x i )∈F i 2 P (x 1 , . . . , x n ) = 0 for each value of (x i+1 , . . . , x n ) if and only if P does not involve a monomial containing all the variables x 1 , . . . , x i . This property can be understood more easily using higher-order differential and means that if we derive i times w.r.t. to the first i variables, a multivariate polynomial P that does not contain a monomial involving the x 1 x 2 . . . x i monomial, then we get the 0 polynomial. Thus integral distinguishers are highly related to the maximal monomials involved in a polynomial and division property can be seen as a method to track them through an iterated function.

Searching for integral distinguishers

The main difficulty is to efficiently modelize the propagation of division property through the round functions of a cipher. Except in [START_REF] Todo | Bit-Based Division Property and Application to Simon Family[END_REF] where Todo and Morii used an ad-hoc tool to exhaust division trails on SIMON-32, searching for integral distinguishers based on division property usually relies on generic solvers for MILP, SAT or SMT models. In [START_REF] Xiang | Applying MILP Method to Searching Integral Distinguishers Based on Division Property for 6 Lightweight Block Ciphers[END_REF] Xiang et al. show that it is possible to describe transitions through small Sboxes with inequalities by computing the convex hull of points. This work has been extended by Zhang and Rijmen [START_REF] Zhang | Division cryptanalysis of block ciphers with a binary diffusion layer[END_REF] to binary linear mapping. Eskandari et al. in [START_REF] Eskandari | Finding Integral Distinguishers with Ease[END_REF] have built a tool called Solvatore to find such division property trails using a SAT solver and found many new integral distinguishers. The difficulty of the search procedure depends on the cipher and on the variant of division property implemented. The original variant is the simplest to search for but is also the less accurate as it may miss some cancellations of monomials and thus miss distinguishers. In [START_REF] Hebborn | Lower Bounds on the Degree of Block Ciphers[END_REF], Hebborn et al. worked with the exact variant and described a new method dedicated to (small) block ciphers aiming at proving that for each linear combination of the ciphertext bits and for each monomial of degree n -1 in the plaintexts bits, there is at least one key (considering independent round keys) for which the monomial appears in the ANF of the linear combination. They used a heuristic approach to find round keys for which evaluating the parity of division trails is the cheapest. As a result they found that 13round SKINNY-64, 11-round Gift and 11-round PRESENT are all immune to integral distinguishers if considering independent round keys.

Several Improvements

I worked on division property with Pierre-Alain Fouque and my PhD student Baptiste Lambin and we published two papers [LDF20; DF20] related to this topic. We proposed several refinements of the cryptanalysis technique which allowed us to find new distinguishers requiring either less data or covering more rounds. We present two of them in this section and refer the interested readers to the original publications for more details. Linear combinations. We observed that for a given block cipher E, one should consider L out • E • L in , where both L out and L in are linear mappings, since division property is not linearly invariant contrary to differential nor linear cryptanalysis. For instance, let f k be the encryption function

f k (x, y) = (p 0 (k)x ⊕ p 1 (k)y, p 2 (k)x ⊕ p 3 (k)y)
where p 0 , . . . , p 3 are non-zero polynomials and x, y ∈ F 2 . In that case classical application of division property would conclude that no output bit is balanced. But if either p 0 = p 2 or p 1 = p 3 then the xor of both output bits is balanced. This may lead to new distinguishers but the drawback is that the search space is greatly increased. However we showed that not all linear mappings have to be considered. Regarding the output and since we are looking for integral distinguishers, we are only interested in knowing whether the i-th bit is balanced or not. Hence there is no reason to consider invertible matrices, linear combinations are enough, reducing the number of mappings to try for an n-bit cipher from O(2 n 2 ) to O(2 n ). As for the output, it is not required to try all invertible matrices at the input to cover the whole search space. Actually, what matters for integral distinguishers is the vector space spawn by constant (linear combinations of) bits (more precisely, bits that will be constant in the integral distinguisher). Indeed, let P (x 1 , . . . x n ) be a polynomial and let H(i, j) be the property that a polynomial does not contain any monomial greater than or equal to (i.e. multiple of) x i . . . x j . We know there exist two polynomials P 1 and

Q 1 such that P (x 1 , . . . , x n ) = x 1 P 1 (x 2 , . . . , x n ) ⊕ Q 1 (x 2 , . . . , x n ).
In particular, for any k ∈ {1, . . . , n}, P satisfies H(1, k) if and only if P 1 satisfies H(2, k). Now let be j ∈ {2, . . . , n} and consider polynomial P (x 1 , . . . , x n ) = P (x 1 ⊕ x j , x 2 , . . . , x n ). We have the following equalities:

P (x 1 , . . . , x n ) = P (x 1 ⊕ x j , x 2 , . . . , x n ) = (x 1 ⊕ x j )P 1 (x 2 , . . . , x n ) ⊕ Q 1 (x 2 , . . . , x n ) = x 1 P 1 (x 2 , . . . , x n ) ⊕ (x j P 1 (x 2 , . . . , x n ) ⊕ Q 1 (x 2 , . . . , x n )) = x 1 P 1 (x 2 , . . . , x n ) ⊕ Q 1 (x 2 , . . . , x n )
As a consequence, P satisfies H(1, k) if and only if P 1 satisfies H(2, k) and thus P satisfies H(1, k) if and only if P satisfies H(1, k). Hence, any invertible matrix that does not modify the vector space of constant bits does not modify the integral distinguisher. In particular, when looking only for the existence of an integral distinguisher i.e. without optimizing the data complexity, it is enough to exhaust the only linear combinations of bits that will be constant, reducing the number of mappings to test from O(2 n 2 ) to O(2 n ).

Propagation table of Super-Sboxes. At ASIACRYPT'16, Xiang et al. [START_REF] Xiang | Applying MILP Method to Searching Integral Distinguishers Based on Division Property for 6 Lightweight Block Ciphers[END_REF] proposed an algorithm to compute the propagation table of an n-bit to n-bit function f . The propagation table of f is a table T such that for any m ∈ F n 2 , T [m] contains all possible monomials m such that the transition m f → m is valid, fully describing the propagation rules through f . The algorithm produces the propagation table in roughly O(2 3n ) operations which is practical up to n ≈ 16. To improve the precision of division property our goal was to remove false trails, which correspond to valid trails m 0

f 0 → m 1 f 1 → m 2 for which the transition m 0 f 1 •f 0 -→ m 2 is
actually invalid because of monomial cancellations. Thus, our idea was to build the propagation table of Super-Sboxes. Introduced in [START_REF] Gilbert | Super-Sbox Cryptanalysis: Improved Attacks for AES-Like Permutations[END_REF] by Gilbert and Peyrin, Super-Sboxes are Sboxes operating on columns and equivalent to a first application of the simple Sbox on each word of the column, an application of the MixColumns operation, a XOR with a key and a second application of the simple Sbox.

Because of the key addition between the two layers of Sboxes, a naive approach would require to run the previous algorithm for all possible values of the (part of) round key used in the Super-Sbox and then merge the propagation tables. This would quickly make the computation untractable. Instead we proposed a new algorithm, taking as input a collection of k n-bit functions and outputting the propagation table containing all the valid transitions for at least one of the function. We mainly reorganized the computations to avoid redundant ones and its complexity is in O(kn2 2n + 2 3n ). Note that typical value for k is 2 n and so our algorithm has complexity O(n2 3n ), to be compared to O(2 4n ), the cost of calling 2 n times the original algorithm.

A New Tool for Division Property

In [START_REF] Todo | Bit-Based Division Property and Application to Simon Family[END_REF], Todo and Morii proposed a way to search for integral distinguishers based on the division property, with a complexity upper bounded by 2 n , where n is the block size of the block cipher. In practice, they said that their algorithm is not suitable for block ciphers with block size beyond 32 bits, and thus the number of possible targets is very limited. However, a lot of work has been done towards efficiently searching such distinguishers, based on either MILP or SAT/SMT solvers.

Regarding MILP-based search algorithms, the main point is to generate sets of inequalities describing all the propagation tables involved in the decomposition of the cipher. But the number of inequalities required to describe a 16-bit propagation table seems too large to be handled efficiently by any MILP solver. For instance, the propagation table of the Super-Sbox of Midori-64 contains approximately 2 23 elements. Hence we developed a dedicated algorithm to search for integral distinguishers based on a branch-and-bound approach. This was the first time one showed a practical algorithm to search for division trails on 64-bit block ciphers not relying on generic solvers for MILP, SAT or SMT models.

Results

Using our tool we found new integral distinguishers against the three well-studied block ciphers SKINNY-64 [START_REF] Beierle | The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS[END_REF], Midori-64 [START_REF] Banik | Midori: A Block Cipher for Low Energy[END_REF] and HIGHT [START_REF] Hong | HIGHT: A New Block Cipher Suitable for Low-Resource Device[END_REF], increasing the number of rounds covered compared to previously best known integral distinguishers. We also experimentally verified some distinguishers found on smaller instances in order to validate our tool. For instance, we searched for low data distinguishers by fixing some input bits of the Super-Sboxes to constant and we found integral distinguishers requiring Chapter 3 -Tools for Cryptanalysis only 2 15 chosen plaintexts against both 8-round SKINNY-64 and 6-round Midori-64.

Boomerang Characteristics

Nowadays we know how to design ciphers resistant to differential cryptanalysis, ciphers for which we can give upper bounds on the probability of the best differential characteristics. To go further, Wagner proposed the boomerang attack in [START_REF] Wagner | The Boomerang Attack[END_REF]. The main idea introduced by Wagner is that combining two short differentials may lead to a higher probability than one long differential. In boomerang attacks, a cipher E is regarded as the composition of two sub-ciphers E 0 and E 1 so that E = E 1 • E 0 . Suppose there exist both a differential α → β for E 0 and a differential γ → δ for E 1 with probabilities p and q respectively. If we assume the two differentials are independent then we obtain a boomerang distinguisher of probability:

P E -1 (E(P ) ⊕ δ) ⊕ E -1 (E(P ⊕ α) ⊕ δ) = α = p 2 q 2 .
However, in practice the independence assumption usually does not hold, especially at the junction of both the lower and upper differentials. At SAC'07, Wang et al. [START_REF] Wang | The Delicate Issues of Addition with Respect to XOR Differences[END_REF] first gave some evidences for non-returning boomerangs (i.e. P = 0 instead of p 2 q 2 ). In 2011, Murphy [START_REF] Murphy | The Return of the Cryptographic Boomerang[END_REF] propose a method to precisely evaluate the probability of a boomerang. They reevaluated the probability of several boomerang distinguishers from [START_REF] Liu | Security Analysis of SKINNY under Related-Tweakey Settings (Long Paper)[END_REF] against both SKINNY and AES, showing their exact probability was much higher than expected.

Searching Boomerangs

One natural question when facing a new cryptanalysis technique is how to find the best distinguishers. For boomerang distinguishers, the classical approach is to first search for two short characteristics with high probability and to combine them. But we believe this approach should now be deprecated since the dependency in the middle rounds may hugely affect the probability of the distinguisher and thus it seems sub-optimal to search for both the lower and upper differentials independently.

In [START_REF] Cid | A Security Analysis of Deoxys and its Internal Tweakable Block Ciphers[END_REF], Cid et al. used a MILP model to study the ladder switch for a boomerang attack on Deoxys. A more generic approach was proposed in [START_REF] Liu | Related-Key Boomerang Attacks on GIFT with Automated Trail Search Including BCT Effect[END_REF], where Liu et al. describe a MILP model to directly search for the best boomerang distinguisher against the block cipher GIFT. The cipher is decomposed into three parts E 0 , E m and E 1 where E m is restricted to one single round, the junction of both differentials which handles the BCTs. With this model they found a new boomerang distinguisher on 19-round GIFT, achieving a better probability than when merging two optimal short trails.

A New Tool

In [START_REF] Delaune | Catching the Fastest Boomerangs Application to SKINNY[END_REF], a joint work with Stephanie Delaune and the Master student Mathieu Vavrille, we proposed to go further than both [START_REF] Song | Boomerang Connectivity Table Revisited. Application to SKINNY and AES[END_REF] and [START_REF] Liu | Related-Key Boomerang Attacks on GIFT with Automated Trail Search Including BCT Effect[END_REF] by providing a new tool to search for boomerang distinguishers. One limitation of the MILP model of Liu et al. is that it handles only one round for the middle part while Song et al. have shown that dependencies could affect much more rounds, for instance up to 6 rounds for SKINNY. First, we proposed a new approach to turn a MILP model to search for truncated characteristics into a MILP model to search for truncated boomerang characteristics. The main novelty was that this model handles the dependencies in the middle rounds automatically. Furthermore, there is no need to specify which rounds are the middle ones, this is also directly handled by the model. Second, we proposed a new Constraint Programming (CP) model to search for the best instantiation of a truncated boomerang characteristic. This model even goes further by clustering instantiations to improve the probabilities. Finally, we systematized the method from [START_REF] Song | Boomerang Connectivity Table Revisited. Application to SKINNY and AES[END_REF] to precisely compute the probability of a boomerang.

From truncated differentials to truncated boomerangs. The most interesting technique described in this paper is certainly the process to turn a MILP model to search for truncated characteristics into a MILP model to search for truncated boomerang character-Chapter 3 -Tools for Cryptanalysis istics. Let E be a classical SPN cipher with R rounds operating on an n-cell internal state and such that the round function is composed of a SubCell operation, a key addition and a linear layer which multiplies the internal state by a matrix M (at the cell level). We also assume the key schedule is fully linear. The first part of the model consists in writing twice the MILP model for truncated differential, once for the upper characteristic and once for the lower one. Such models are somehow easy to write and are already available for several block ciphers [START_REF] Zhu | MILP-Based Differential Attack on Round-Reduced GIFT[END_REF][START_REF] Beierle | The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS[END_REF]. We consider for each cell of each internal state of the upper (resp. lower) characteristic a binary variable isActiveUp (resp. isActiveLo) indicating whether the cell is active or not. To represent the fact that some differences will take any value uniformly, we introduce free variables (non free variables will be called controlled variables). Controlled variables are the differences that will be set to a fixed value in the characteristic.

We introduce two sets of binary variables for each characteristic: isFreeXup and isFreeS-Bup (resp. isFreeXlo and isFreeSBlo) to indicate whether a difference will be free before and after the Sbox respectively. For the upper characteristic if a difference is free before an Sbox (i.e. isFreeXup = 1), then it is free after the Sbox (isFreeSBup = 1). For the lower characteristic, if a difference is free after an Sbox, then it is free before the Sbox (because the propagation is done in the opposite direction). This leads to the constraints:

∀0 ≤ r < R, 0 ≤ i < n, isFreeSBup[r][i] ≥ isFreeXup[r][i] isFreeXlo[r][i] ≥ isFreeSBlo[r][i]
Those variables are also related to both isActiveUp and isActiveLo because a difference can be set to 0 only if the difference is controlled. Thus we have the constraints:

∀0 ≤ r < R, 0 ≤ i < n, isActiveUp[r][i] ≥ isFreeSBup[r][i] isActiveLo[r][i] ≥ isFreeXlo[r][i]
Another important constraint is the one stating that a free difference propagates with probability 1 (i.e. no cancellations occur). For the upper characteristic we define depsU(i) as the set of all the indexes j such that the coefficient m i,j of the matrix M (of the linear layer) is non-zero. For the lower one, we define depsL in a similar way but for the matrix M -1 . Then the constraints of propagation of free variables are simply:

∀0 < r < R, 0 ≤ i < n, isFreeXup[r][i] = j∈depsU(i) isFreeSBup[r -1][j] isFreeSBlo[r -1][i] = j∈depsL(i) isFreeXlo[r][j]
In order to apply the differential tables as the DDT or the BCT, we need an extra constraint to ensure that the probability of each Sbox can be computed. More precisely, we require that at most 2 variables can be free for each Sbox (considering upper and lower characteristic, before and after the Sbox). This leads to the constraints:

∀0 ≤ r < R, 0 ≤ i < n, isFreeSBup[r][i] + isFreeSBlo[r][i] ≤ 1 isFreeXup[r][i] + isFreeXlo[r][i] ≤ 1
With all these constraints, the solutions generated will lead to truncated boomerang characteristics. We emphasize with our new set of constraints there are no middle rounds defined for our truncated boomerang characteristics. In particular, the BCTs are not necessarily all on the same round but may be spread over several rounds. Thus our modelization is more generic than the previous ones, in particular than the modelization proposed by Liu et al. in [START_REF] Liu | Related-Key Boomerang Attacks on GIFT with Automated Trail Search Including BCT Effect[END_REF].

Results and Open Problems

We applied our tool to the block cipher SKINNY [START_REF] Beierle | The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS[END_REF] and found many new distinguishers on all versions of the ciphers. Our results are given in Table 3.1. All previous results from [START_REF] Song | Boomerang Connectivity Table Revisited. Application to SKINNY and AES[END_REF] were improved, in particular we found a new boomerang distinguisher on 18-round SKINNY-128/256 (i.e. on the TK2 model) with probability 2 -47.37 while the previous best distinguisher had probability 2 -77.83 . We experimentally verified some of the distinguishers to confirm the probabilities.

Open problems. We found two main limitations regarding our MILP model. First it is possible to have truncated boomerangs that differ only on some f ree variables. These truncated boomerangs are duplicates in the point of view of distinguishers, and thus instantiations will be almost the same. Moreover, when applying the procedure to compute the probability of the boomerang, they will have exactly the same probability because the input and output will be the same. This also makes the number of solutions growing exponentially. The tool was configured to find the N best solutions and thus would find non optimal solutions. But as there were too many of them, it was not able to go much further than optimal objective (in a reasonable time limit). The second limitation is related to the key schedule. We force it to be linear to be able to implicitly set all differences in the round keys as controlled. Thus a natural question is how to modify the model to handle more complex key schedule as for instance the one of AES.

Chapter 4 Many attacks and distinguishers proposed against cryptographic primitives do not threaten their security in real-life situation and are mainly theoretical weaknesses, highlighting unexpected behavior and meaning it should be possible to reach better security level. For instance, the block cipher MYSTI1 [Mat97] is considered broken since Todo showed an attack against it [START_REF] Todo | Integral Cryptanalysis on Full MISTY1[END_REF]. However this attack requires the knowledge of almost the full codebook (2 63.994 chosen plaintexts among a codebook of size 2 64 ) and to run an algorithm performing around 2 107 non-trivial operations. The requirement is so high that in practice MYSTI1 can still be used safely but we would recommend to use a block cipher for which knowing the full codebook does not decrease the time complexity of retrieving the key. Thus it is interesting to study the resistance of a cipher against During my PhD I studied low-data-complexity attacks against round-reduced AES and found some of the best attacks in this setting. During my PostDoc I participated to the PRINCE Challenge in which the goal was to mount the fastest attacks against round-reduced versions of the blockcipher PRINCE using at most 2 20 chosen plaintexts or 2 30 known plaintexts. I won some of those challenges and the results were published in [START_REF] Derbez | Meet-in-the-Middle Attacks and Structural Analysis of Round-Reduced PRINCE[END_REF] and [START_REF] Derbez | Meet-in-the-Middle Attacks and Structural Analysis of Round-Reduced PRINCE[END_REF].

REAL-LIFE AND PRACTICAL CRYPTOGRAPHY

In this chapter I describe the results obtained in 3 recent papers ([DLU19; Der+18b; Bei+21]) regarding practical attacks and real-life cryptography.

Cryptanalysis of SKINNY in the Framework of the SKINNY 2018-2019 Cryptanalysis Competition

In order to motivate external cryptanalysis of their family of ciphers, SKINNY designers launched several one-year competitions. The first one started in 2016 and called for cryptanalysis of small-scaled variants of 18 up to 26 rounds of SKINNY-64-128, and of 22 up to 30 rounds of SKINNY-128-128. The two papers that won the competition are [START_REF] Ankele | Related-Key Impossible-Differential Attack on Reduced-Round Skinny[END_REF] for being the first submission that attacks up to 20 rounds of SKINNY-64-128 and [START_REF] Liu | Security Analysis of SKINNY under Related-Tweakey Settings (Long Paper)[END_REF] for being the first submitted work to successfully attack up to 23 rounds of SKINNY-64-128.

The challenges launched in 2017 were similar, except that the number of rounds one has to break was higher. Nobody won these contests.

The last competition started on the 1 st of April 2018 and ended on February 28, 2019. This time, the goal was to mount a practical key-recovery attack of small-scaled versions of SKINNY for which sets of only 2 20 pairs (plaintext, ciphertext) were provided. The designers offered rewards for the teams that would break the maximum number of rounds for SKINNY-64-128 or SKINNY-128-1281 .

Remark on the Provided Messages

While looking for messages with specific patterns, we realized that the plaintexts provided for the challenges were not uniformly distributed.

Cryptanalysis of SKINNY in the Framework of the SKINNY 2018-2019 Cryptanalysis Competition

To illustrate this, we provide in Figure 4.1 the distribution of the value of nibble 0 (top left corner in the Skinny internal state) and of nibble 15 (bottom right) in the set provided for the 12-round attack on SKINNY-64-128. It is rather direct to make the link between this distribution and the one of a text in UTF-8 code: indeed, the first hint comes from the fact that the UTF-8 code of the lower-case letters goes from 0x61 to 0x7a, which explains the overwhelming occurrence of the nibble 0x6 (followed by the nibble 0x7) in the distribution of nibbles at even positions. Also, a character that is ought to appear frequently is the space, encoded by 0x20. This one explains the third dominant higher nibble value (0x2) and the high number of occurrences of 0x0 in the lower nibbles.

This guess was confirmed once we printed the plaintexts. For instance, looking at the messages given for the challenge on 4 rounds SKINNY-64-128, we read: Project Gutenberg's Alice's Adventures in Wonderland, by Lewis Carroll This eBook is for the use of anyone anywhere at no cost and with almost no restrictions whatsoever.

And few lines later, confirming that this is the book, one can read: [...] when suddenly a White Rabbit with pink eyes ran close by her. There was nothing so VERY remarkable in that; nor did Alice think it so VERY much out of the way to hear the Rabbit say to itself, 'Oh dear! Oh dear! I shall be late!'

Other data sets correspond to other books (for instance Metamorphosis, by Franz Kafka or The Prince, by Nicolo Machiavelli). This high bias in the messages implies that we have some collisions on the plaintext values. In the file provided for 12 rounds of SKINNY-64-128 we counted 925615 different pairs (2 19.82 , so 2 16.90 collisions) out of the 2 20 provided. The plaintext that appears the most corresponds to ." " (dot (0x2e), closed quote (0xe2809d), space (0x20), open quote (0xe2809c)) with 289 occurrences.

Results

Any human-readable text has a low entropy and so does the book whose encryption was provided in the SKINNY 2018-2019 cryptanalysis competition. This fact can be exploited by a cryptanalyst, who can devise attacks that would be ineffective in the classic knownplaintext scenario with uniformly distributed plaintexts. In this case, we showed that many pairs or even quadruples of plaintext blocks can be found in the provided datasets for which particular (differential) zero-sum properties hold with probability 1 after 6 rounds of SKINNY-64-128 and 7 rounds of SKINNY-128-128.

As a result, we were able to mount practical key recovery attacks up to 12-round SKINNY-64-128 and 10-round SKINNY-128-128 from given sets of 2 20 messages. Our attacks consist in leveraging distinguishers based on a probability-1 truncated first-order and second-order differential paths. The attacks are possible because the provided sets of messages give much more exploitable pairs than what one could have expected from a random set. This also highlights the importance of the mode of operation used with a cipher.

On Recovering Affine Encodings in White-Box Implementations

Historically, cryptanalysis is performed within the black-box model: the cryptographic algorithm under attack is executed in a trusted environment, and the view of the attacker is limited to the input-output behavior of the algorithm. Depending on the type of attack under consideration, the attacker may be able to observe the inputs and outputs of encryption or decryption queries, and perhaps choose the corresponding inputs, but nothing more. Such attack models are particularly relevant in scenarios where the attacker does not have direct access to an implementation of the scheme, either because it is executed remotely, or within a protected hardware environment such as a secure enclave.

Since the advent of side-channel attacks however, new attack models have come into the light, wherein the attacker has access to some auxiliary information leaked by the implementation. These models are sometimes called gray-box models, in contrast with the black-box model outlined in the previous paragraph. Attacks in the gray-box model may exploit physical leakage such as computation time, power consumption, or electromagnetic leakage, among many others. Such attacks can result in practical breaks against schemes that would otherwise appear secure in the standard black-box model.

White-box Cryptography

Going one step further, in 2002, Chow et al. introduced the white-box model [START_REF] Chow | A White-Box DES Implementation for DRM Applications[END_REF][START_REF] Chow | White-Box Cryptography and an AES Implementation[END_REF]. In this model, the attacker has full access to an implementation of the target cryptographic algorithm, including the ability to control its execution environment. Therefore he can observe memory content, set breakpoints in the execution flow, change arbitrary values in the code or the memory, etc. In this setting, the security assumptions of the black-box model clearly no longer hold. However, it may still be desirable that the adversary should be unable to extract the secret key of the cryptographic algorithm under attack.

This model is relevant in the context of software distribution, whenever a piece of software containing sensitive cryptographic information (such as an encryption algorithm) is to be widely distributed, and hence can be downloaded and analyzed by adverse parties. The most prominent application occurs in Digital Rights Management, where attackers may wish to recover a decryption key used to protect copyrighted content (digital music, TV broadcasts, video games, etc). A successful attacker is then able to distribute the secret key to unauthorized users, providing them with illegitimate access to the protected content. In effect, the goal is to protect sensitive functions within the deployed software, such as cryptographic algorithms, in much the same way that a trusted environment would protect security-critical functions in a hardware context. Ideally, white-box cryptography would thus achieve the software equivalent of trusted enclaves, specialized to particular cryptographic algorithms.

In order to achieve this goal, white-box cryptography techniques attempt to obfuscate the implementation of the target cryptographic algorithm. Ideally, an attacker in possession of the obfuscated cipher should be unable to interact with it in any meaningful way, beside simply executing it on chosen inputs. While Barak et al. have shown that general program obfuscation is impossible [START_REF] Barak | On the (Im)possibility of Obfuscating Programs[END_REF], the context of white-box cryptography presents two key differences. The first is that white-box cryptography merely attempts to obfuscate particular function families (such as block ciphers), which Barak et al.'s result has no bearing on. Another key difference is that white-box models do not generally require guarantees as strong as those offered by black-box obfuscation: in the case of a white-box implementation of AES for instance, it may be enough that the adversary is unable to recover the secret key (for a detailed discussion of white-box models, see [START_REF] Delerablée | White-Box Security Notions for Symmetric Encryption Schemes[END_REF][START_REF] Fouque | Efficient and Provable White-Box Primitives[END_REF]).

The CEJO framework

In their original 2002 articles, Chow et al. proposed such a white-box scheme for DES and AES [START_REF] Chow | A White-Box DES Implementation for DRM Applications[END_REF][START_REF] Chow | White-Box Cryptography and an AES Implementation[END_REF]. While their proposals were quickly broken [JBF02; BGE04], their work opened the path to white-box encryption. Follow-up works often reused the same general framework, which we will call the "CEJO framework".

In the CEJO framework, round functions are obfuscated by being composed with carefully crafted input and output encodings. In the white-box implementation of a cipher, each round function E (r) at round r is replaced by f (r+1) -1 • E (r) • f (r) , where f (r+1) -1 , f (r) are bijections called respectively the input and output encoding. By design, the output encoding of each round is canceled out by the input encoding of the next round.

• • • • f (r+1) -1 • E (r) • f (r) F (r) • f (r) -1 • E (r-1) • f (r-1) F (r-1)
• . . . For each round, the white-box implementation gives access to the encoded version of the round function r) , but not directly to the underlying round function E (r) . The full implementation of the cipher can thus be written as

F (r) = f (r+1) -1 • E (r) • f (
E (R) •• • ••E (1) .
Chow et al. proposed to define the encodings f (r) as the composition of a non-linear mapping and an affine mapping. The idea is to follow a classic concept in symmetric cryptography : the non-linear mapping will add some confusion on the intermediate values of the state, while the affine mapping will add some diffusion (see Sec. 3.3 and 3.4 in [START_REF] Chow | White-Box Cryptography and an AES Implementation[END_REF]). In addition, in a typical SPN block cipher, round keys are XORed into the inner state of the cipher. In that case, whenever the constant of the affine encoding is uniformly random, a single obfuscated round completely hides the value of the round key, which implies that a successful key-recovery attack must target multiple rounds simultaneously. Thus the CEJO framework is a natural approach to attempt to obfuscate a block cipher, especially an SPN cipher such as AES.

In addition to the above, some external input/output encodings M out /M in can be added before and after the cipher. In that case, the implementation provides a map from encoded plaintexts to encoded ciphertexts. These encodings are merged into the tables used for the initial and final encoded round function. The implementation is then equivalent to an encoded version of the cipher, which can be expressed as

M out • E (R) • • • • • E (1) • M in .
External encodings can be used to increase security, as the attacker is denied direct access to raw plaintexts/ciphertexts. On the other hand, external encodings assume that the implementation surrounding the white-box cipher takes these encodings into account. As such, a white-box implementation with external encodings is not properly speaking an implementation of the cipher it contains. For this reason, in this work, we shall explicitly signal the presence of external encodings, and use the term white-box implementation with external encodings when appropriate.

It is crucial that, given the encoded round function F (r) , the adversary should be unable to compute and peel off the encodings f (r+1) -1 and f (r) . Indeed, for typical ciphers such as AES, granting direct access to a single round E would allow the adversary to easily recover the corresponding round key, and from there the secret key of the cipher. However attacks on white-box implementations typically achieve precisely this, by taking advantage of the specific structure of the encodings A and B. In white-box implementations following the CEJO framework, encodings are composed of a very simple non-linear layer, together with a more complex affine layer. Attacks generally peel off the non-linear component, then proceed to recover the affine layer. This is typically achieved in an ad-hoc way, by exploiting specific properties of the scheme under attack.

Results

In a joint work with Fouque, Lambin and Minaud published at TCHES [START_REF] Derbez | On Recovering Affine Encodings in White-Box Implementations[END_REF], we proposed a generic algorithm to recover affine encodings for any white-box implementation of a cipher following the CEJO framework, independent of the way the encodings are built. More generally, our algorithm solves the affine equivalence problem (given two maps F and S with the promise that they are affine equivalent, compute affine maps A, B, such that F = B • S • A) whenever one of the two maps is composed of the parallel application of distinct S-boxes.

Our main algorithm is very similar to one of the steps of the structural cryptanalysis of SASAS by Biryukov and Shamir [START_REF] Biryukov | Structural Cryptanalysis of SASAS[END_REF], combined with a generic affine equivalence algorithm; for this purpose, we use the recent algorithm by Dinur [START_REF] Dinur | An Improved Affine Equivalence Algorithm for Random Permutations[END_REF], but the same attack would also work with the classic affine equivalence algorithm by Biryukov, De Cannière, Braeken and Preneel [START_REF] Biryukov | A Toolbox for Cryptanalysis: Linear and Affine Equivalence Algorithms[END_REF]. Thus the components we use are not essentially new. However, to the best of our knowledge, the fact that they enable breaking all whitebox schemes following the design of Chow et al. in a generic way has not yet been explicitly pointed out in the literature, or analyzed in detail, despite the fact that the SASAS algorithm predates both these schemes and their attacks. As a result, in our experience, this fact is also largely ignored by practitioners in the industry.

By design, our attack applies to a large class of white-box schemes following the CEJO framework, including [START_REF] Chow | A White-Box DES Implementation for DRM Applications[END_REF][START_REF] Chow | White-Box Cryptography and an AES Implementation[END_REF][START_REF] Karroumi | Protecting White-Box AES with Dual Ciphers[END_REF]. Beyond the previously cited schemes, which were already broken by ad-hoc attacks, we illustrate our attack on a new whitebox design by Baek, Cheon and Hong [START_REF] Hun | White-box AES implementation revisited[END_REF]. One distinctive feature of this design that makes it particularly attractive to illustrate our attack (beside not being previously cryptanalyzed) is that it increases the state size by obfuscating two parallel rounds of AES, precisely to prevent generic attacks from being able to recover the affine encodings of the scheme. Indeed Baek et al. estimated the security level of their proposal to 110 bits based on their own specialized version of an affine equivalence algorithm. However our generic attack on this scheme requires only about 2 35 basic operations.

As a second contribution, we analyzed the scheme by Baek et al. more closely, and introduced another technique able to break this scheme. This new technique extracts and solves a standalone problem from the scheme by Baek et al.. Ultimately, it is able to recover the secret key of the scheme in time complexity 2 31 . This is verified with an implementation. This dedicated attack on Baek et al.'s scheme is also more powerful as it allows us to fully recover the key, while the generic attack only creates a decryption function without recovering the key.

Affine Equivalence Problem

In an SPN cipher, a round function is composed of an affine layer (in which we include key addition), and a non-linear S-box layer. The S-box layer S consists of the application of k parallel m-bit S-boxes, where n = km is the block size. As a result, when encoding a round function using affine encodings, the encoded round function may be written as F = B • S • A, folding the affine layer into one of the encodings. A natural problem in this setting is the affine equivalence problem: namely, to recover affine encodings A and B, given F = B • S • A, and knowing S. More precisely, since A and B may not be uniquely defined, the problem can be stated as: given S and F as before, find affine maps A , B such that

F = B • S • A .
The general affine equivalence algorithm by Dinur [START_REF] Dinur | An Improved Affine Equivalence Algorithm for Random Permutations[END_REF] solves precisely this problem whenever the degree of S is maximal while the classic algorithm by Biryukov et al. [START_REF] Biryukov | A Toolbox for Cryptanalysis: Linear and Affine Equivalence Algorithms[END_REF] assumes no special structure on S). However its complexity is O (n 3 2 n ), which makes it unsuitable for recovering encodings on a typical block size of 128 bits. In contrast, we focused on the case where S is made up of k parallel m-bit S-boxes. In this setting, we proposed an algorithm that solves the affine equivalence problem with a (typically much lower) time complexity of O 2 m n 3 + n 4 m + 2 m m 2 n . For the AES parameters n = 128, As noted earlier, due to its genericity, our attack applies to essentially all white-box schemes following the CEJO framework: this includes the original designs by Chow et al. [Cho+02a;[START_REF] Chow | White-Box Cryptography and an AES Implementation[END_REF], and later proposals [XL09; Kar10]. In the case of Karroumi's scheme [START_REF] Karroumi | Protecting White-Box AES with Dual Ciphers[END_REF], while it does not seem to follow the CEJO framework at first glance, it has been later shown that this scheme is equivalent to the CEJO framework [START_REF] Lepoint | Two Attacks on a White-Box AES Implementation[END_REF][START_REF] Mulder | Revisiting the BGE Attack on a White-Box AES Implementation[END_REF], and hence our technique applies directly.

The main limitation of our attack is that it only targets affine encodings, whereas most white-box schemes following the CEJO framework also use non-linear encodings in addition to affine encodings [Cho+02a; Cho+02b; Kar10; BCH16]. When non-linear encodings are used, our attack does not break the scheme by itself. However, even in the presence of non-linear encodings, the first step of attacks typically consists in peeling off the non-linear encoding layer first [BGE04; BCH16], which does not apply to the state as a whole, and leaves the attacker with an instance of the previous problem. In this context, our algorithm provides a powerful tool, which is able to recover affine encodings in a very general setting.

Dedicated attack

As a second contribution, we took a closer look at the scheme by Baek et al.. We identified another angle from which the scheme can be attacked. At the core of this second approach lies the following problem. Let F , h 1 , h 2 be three non-linear mappings from m bits to m bits, and let A 1 , A 2 be two linear mappings on m bits. Given oracle access to

G(x, y) = F (A 1 (x) ⊕ A 2 (y)) ⊕ h 1 (x) ⊕ h 2 (
y), recover A 1 and A 2 (up to equivalence). We solved this problem and deduced an attack against the white-box scheme by Baek et al. with time complexity ∼ 2 31 operations. We implemented the full attack, and were able to recover the secret key (and external encodings) in about 12 seconds on a standard desktop computer.

Cryptanalysis of the GPRS Encryption Algorithms

GEA-1 and GEA-2

Cryptanalysis of the GPRS Encryption Algorithms

GEA-1 and GEA-2

General Packet Radio Service (GPRS) is a mobile data standard based on the GSM (2G) technology. With its large deployments during the early 2000s worldwide, GPRS (including EDGE) was the technology for many of us, which provided us the first mobile Internet connection. While some countries are about to sunset 2G technology (or have already done so), other countries rely on GPRS as a fallback data connection. Consequently, the security of those connections was and is still relevant for a large user base. In the wireless medium, an attacker conducts an eavesdropping attack by merely sniffing the traffic in the victim's vicinity. To protect against eavesdropping GPRS between the phone and the base station, a stream cipher is used and initially two proprietary encryption algorithms GEA-1 and GEA-2 were specified.

In 2011, Nohl and Melette analyzed the security of GPRS traffic and showed that GPRS signals could easily be eavesdropped [START_REF] Nohl | GPRS Intercept: Wardriving your country, Chaos Communication Camp[END_REF]. This was reported as a serious weakness, especially since some providers did not activate encryption at all. However, according to the authors, most operators at that time employed the proprietary encryption algorithms GEA-1 or GEA-2 for encrypting the GPRS traffic. They also reported the reverseengineering of those encryption algorithms. Without presenting all of the specification details, the following properties of the design of GEA-1 have been shown:

-It is a stream cipher which works on an internal state of 96 bits and uses a 64-bit key. -A non-linear function is employed for initialization. 3-The state is kept in three registers of sizes 31, 32, and 33 bits. 4-The state update function is linear, i.e., the registers are LFSRs.

-The function that generates the output stream has algebraic degree 4.

For GEA-2, it was reported that it employs a similar algebraic structure to its predecessor GEA-1. While the key size for GEA-2 is 64 bits as well, the internal state was reported to be of size 125 bits.

Nohl and Melette claimed that GEA-1 has severe weaknesses against algebraic attacks, mainly due to the linearity of the state update function and the availability of a long keystream to the adversary. Live on stage, a state-recovery attack was performed that took less than 15 minutes using "a Gaussian equation solver based on some SAT solver ideas" (minute 48:40 of the recorded talk). However, details of this attack are not available.

Interestingly, the ETSI prohibited the implementation of GEA-1 in mobile phones in 2013, while GEA-2 and the non-encrypted mode are still mandatory to be implemented today [START_REF]ETSI, Digital cellular telecommunications system (Phase 2+) (GSM); Security related network functions[END_REF].

Description of GEA-1 and GEA-2

Despite the hints of deliberately weakening GEA-1 for export and a demonstrated attack, a public cryptanalysis of GEA-1 and GEA-2 was still missing. Hopefully, we obtained the detailed description of the two algorithms GEA-1 and GEA-2 from an anonymous source. Therefore we verified the correctness of the algorithms by a) using test vectors that are available on github [Med] and b) checking the interoperability with commercial phones using the osmocom project [osm]. Both experiments confirmed the correct functionality; thus, we can assume that the provided algorithms are accurate with a high degree of certainty.

For the encryption, the GEA algorithms take the following input parameters: the plaintext, which is the GPRS LLC (Logical Link Control) frame, the key (K), the direction bit (uplink/downlink), and the IV (Input) that consists of an increasing counter for each frame.

As we will see, GEA-2 is an extension of GEA-1 -with slight but crucial modifications. For this reason, we describe GEA-1 first and explain the differences and extensions for GEA-2 in a second step. An overview of the keystream generation of GEA-1 and GEA-2 is shown in Figure 4.3.

GEA-1

GEA-1 is built from three linear feedback shift registers over F 2 , called A, B and C, together with a non-linear filter function, called f . The registers A, B, C have lengths 31, 32 and 33, respectively, and f is a Boolean function of seven variables of degree 4. The registers work in Galois mode. This means that if the bit that is shifted out of a register is 1, the bits in a specified set of positions in the register are flipped. The specification of f = f (x 0 , x 1 , . . . , x 6 ) is given in algebraic normal form as follows:

Cryptanalysis of the GPRS Encryption Algorithms

GEA-1 and GEA-2 f f f f a i b i c i d i z i D A B C
x 0 x 2 x 5 x 6 + x 0 x 3 x 5 x 6 + x 0 x 1 x 5 x 6 + x 1 x 2 x 5 x 6 + x 0 x 2 x 3 x 6 + x 1 x 3 x 4 x 6 + x 1 x 3 x 5 x 6 + x 0 x 2 x 4 + x 0 x 2 x 3 + x 0 x 1 x 3 + x 0 x 2 x 6 + x 0 x 1 x 4 + x 0 x 1 x 6 + x 1 x 2 x 6 + x 2 x 5 x 6 + x 0 x 3 x 5 + x 1 x 4 x 6 + x 1 x 2 x 5 + x 0 x 3 + x 0 x 5 + x 1 x 3 + x 1 x 5 + x 1 x 6 + x 0 x 2 + x 1 + x 2 x 3 + x 2 x 5 + x 2 x 6 + x 4 x 5 + x 5 x 6 + x 2 + x 3 + x 5
Initialization. The cipher is initialized via a non-linear feedback shift register of length 64, denoted as S. This register is filled with 0-bits at the start of the initialization process. The input for initializing GEA-1 consists of a public 32-bit initialization vector IV , one public bit dir (indicating direction of communication), and a 64-bit secret key K. The initialization starts by clocking S 97 times, feeding in one input bit with every clock. The input bits are introduced in the sequence IV 0 , IV 1 , . . . , IV 31 , dir, K 0 , K 1 , . . . , K 63 . When all input bits have been loaded, the register is clocked another 128 times with 0-bits as input. The feedback function consists of f , xored with the bit that is shifted out and the next bit from the input sequence. See Figure 4 After S has been clocked 225 times, the content of the register is taken as a 64-bit string s = s 0 , . . . , s 63 . This string is taken as a seed for initializing A, B and C as follows. First, all three registers are initialized to the all-zero state. Then each register is clocked 64 times, with an s i -bit xored onto the bit that is shifted out before feedback. Register A inserts the bits from s in the natural order s 0 , s 1 , . . . , s 63 . The sequence s is cyclically shifted by 16 positions before being inserted to register B, so the bits are entered in the order s 16 , s 17 , . . . , s 63 , s 0 , . . . , s 15 . For register C the sequence s is cyclically shifted by 32 positions before insertion starts. Keystream Generation. When all registers have been initialized, the actual keystream generation starts. This is done by taking the bits in seven specified positions in each register to be the input to f . The three outputs from the f -functions are xored together to produce one bit of the keystream. Figure 4.3 shows the particular feedback positions of each register, as well as showing which positions form which input to f . In Figure 4.3, the topmost arrow in the input to f represents x 0 , and the input at the bottom is x 6 . After calculating the keystream bit, all registers are clocked once each before the process repeats.

GEA-2

The cipher GEA-2 is a simple extension of GEA-1. A fourth register of length 29, called D, is added to the system together with an instance of f . During keystream generation, the output of f from the D register is added to the keystream together with the three others at each clock, as shown in Figure 4.3. The initialization process of GEA-2 follows the same mode as for GEA-1, but it is done in a longer register that is clocked more times.

Initializing GEA-2. As for GEA-1, the initialization of GEA-2 is done via a non-linear feedback shift register, called W . The length of W is 97, and uses f as its feedback function. The inputs to GEA-2 are the same as for GEA-1; a 32-bit IV and a direction bit dir that are public, and a secret 64-bit key K.

Initialization starts with W being set to the all-zero state. Next, it is clocked 97 times, inserting one bit from the input sequence for each clock. The order for inserting IV, dir and K is the same as for GEA-1. After K 63 is inserted, W is clocked another 194 times, with 0 as input. This process, together with the particular tap positions for f , is shown in Figure 4 The content of W is now taken as a 97-bit string w = w 0 , . . . , w 96 , and inserted in A, B, C and D in much the same way as with GEA-1. The four registers start from the all-zero state, and are filled with the bits of w in the same way as shown in Figure 4.5. The offsets of where in the sequence w each register starts is different than for GEA-1. Register D inserts the bits of w in the natural order w 0 , . . . , w 96 , whereas the registers A, B and C start with bits w 16 , w 33 and w 51 , respectively. Again, if any of the registers happens to end up in the all-zero state after initialization, the bit in position 0 is hard-coded to 1 before key generation starts.

An Attack on GEA-1

First we recall some basic facts about LFSRs in Galois mode, as depicted in . . . Given an LFSR L in Galois mode of length n with entries in F 2 , clocking the inner state l = l 0 , . . . , l n-1 is equivalent to the matrix-vector multiplication

∧ ∧ ∧ ∧ ∧ . . . l 0 l 1 l n-2 l n-1 a 0 a 1 a n-3 a n-2 a n-1
G L • l :=               a 0 1 0 . . . 0 a 1 0 1 . . . 0 . . . . . . . . . . . . . . . a n-2 0 0 . . . 1 a n-1 0 0 . . . 0               •               l 0 ł 1 . . . l n-2 l n-1               =               a 0 l 0 + l 1 a 1 l 0 + l 2 . . . a n-2 l 0 + l n-1 a n-1 l 0              
and the characteristic polynomial of G L is g(X) := X n + a 0 X n-1 + • • • + a n-2 X + a n-1 .

Throughout this work, we consider the case in which g is primitive. The characteristic polynomial g(X) is equal to the minimal polynomial of G L if and only if a n-1 = 1. Vice versa, given a primitive polynomial g(X) := X n + a 0 X n-1 + • • • + a n-2 X + a n-1 , then is the companion matrix of an LFSR in Galois mode with minimal polynomial g. We call such a matrix the Galois matrix and the corresponding minimal polynomial the Galois polynomial in the sequel. Moreover, given an LFSR L in Galois mode with minimal (primitive) polynomial g, we denote the Galois matrix by G g . In the case of GEA-1 the Galois polynomials are g A (X) = X 31 + X 30 + X 28 + X 27 + X 23 + X 22 + X 21 + X 19 + X 18 + X 15 + X 11 + X 10 + X 8 + X 7 + X 6 + X 4 + X 3 + X 2 + 1 , g B (X) = X 32 + X 31 + X 29 + X 25 + X 19 + X 18 + X 17 + X 16 + X 9 + X 8 + X 7 + X 3 + X 2 + X + 1 , g C (X) = X 33 + X 30 + X 27 + X 23 + X 21 + X 20 + X 19 + X 18 + X 17 + X 15 + X 14 + X 11 + X 10 + X 9 + X 4 + X 2 + 1 .

G L :=              
The initialization process of the registers A, B and C with the string s is obviously linear. Hence there exist three matrices where α, β and γ denote the states of the three LFSRs after the initialization phase. We exclude here the unlikely case that α, β or γ is still in the all-zero state after the shifted insertion of s.

M A ∈ F 31×64 2 , M B ∈ F 32×64
We are now interested in the number of possible starting states of the registers after this initialization. The first observation is that all the three matrices have full rank. This implies that the number of possible starting states after initialization is maximal when each LFSR is considered independently, i.e. there are 2 31 possible states for register A, 2 32 possible states for register B, and 2 33 possible states for register C, as should be expected. However, when considering pairs of registers, the picture changes drastically. In particular, the number of possible joint states after initialization of the registers A and C is much smaller than expected. For this it is convenient to consider the kernels of the linear mappings. Clearly, the corresponding linear mappings represented by M A , M B and M C have kernels of dimension of at least 33, 32 and 31, respectively. If we denote From this it directly follows that F 64 2 can be decomposed into the direct sum U B ⊕T AC ⊕V , where V is of dimension 8. Thus, for the key-dependent and secret string s, there exists a unique representation s = u + t + v with u ∈ U B , t ∈ T AC , v ∈ V and

β = M B (u + t + v) = M B (t + v) α = M A (u + t + v) = M A (u + v) γ = M C (u + t + v) = M C (u + v) .
From this decomposition, s can be computed with a Divide-and-Conquer attack with a complexity 5 of 2 37 GEA-1 evaluations to build (and sort) 2 8 tables with 2 24 entries of size 89 bits and a brute-force step of complexity 2 40 GEA-1 evaluations for each new session key K 0 , . . . , K 63 . In other words, the joint state of A and C can be described with only 40 bits and thus can take only 2 40 possible values. This is the key observation of the attack and such weakness is highly unlikely to occur unintentionally.

Since GEA-1 was designed to be exportable within the export restrictions in European countries in the late 1990s, this might be an indication that a security level of 40 bits was a barrier for cryptographic algorithms to obtain the necessary authorizations. Ultimately, the weak design of GEA-1 brings security problems for today's communication, even if it is not being actively used by the operators.

An Attack on GEA-2

GEA-2 does not suffer from the same problems as GEA-1 for initialization. However, it is still possible to mount an attack on GEA-2 that does not target initialization, but keystream generation.

The algebraic degree of the filtering function f is 4. The filtering function also has an algebraic immunity of 4. But, as the 4 registers are never mixed, the number of monomials present in the system of equations formed by the relations between the keystream and the initial state is very limited. More precisely, this number is upper bounded by 5. The complexity will be measured by the amount of operations that are roughly as complex as GEA-1 evaluations (for generating a keystream of size ≤ 128 bit).

This relatively small number would directly imply a powerful attack, just by using a linearisation technique, or, even more powerful, by applying the Berlekamp-Massey algorithm [START_REF] Berlekamp | Algebraic coding theory, McGraw-Hill series in systems science[END_REF][START_REF] James | Shift-register synthesis and BCH decoding[END_REF], as this value is naturally an upper bound to the linear complexity of the output sequence (a direct consequence of Blahut's Theorem [START_REF] Blahut | Theory and practice of error control codes[END_REF]).

However, each session in GEA-2 (or GEA-1) is limited to 1600 bytes, that is 12800 bits. This data limitation frustrates direct algebraic cryptanalysis, as the linearization technique is impossible when we have less equations than monomials.

Hopefully, combining a guess-and-determine algorithm, the linearisation technique as well as a clever organization of computations, we were able to fully break GEA-2. Our attack requires approximately 1468 consecutive keystream bits to be faster than an exhaustive search of the key and reaches a complexity equivalent to 2 45.1 GEA-2 encryption if the 1600 keystream bytes of one session are all known.

Title: Tools and Algorithms for Cryptanalysis

Abstract: The security of symmetric-key primitives as block ciphers and hash functions is established in an empiric manner, by the non-discovery of any attacks or unexpected behavior. More precisely, a symmetric primitive must be secure against all known cryptanalysis techniques and none of its security claims should be broken. The main difficulty is that finding the optimal settings in which a cryptanalysis technique should be applied against a primitive is far from being trivial. In this thesis, I describe several tools and algorithms to efficiently solve this problem for several cryptanalysis techniques and classes of primitives. I present as well several algorithms to design core components of block ciphers providing optimal resistance against various types of attacks. Finally, I give practical attacks against symmetric primitives, including both the stream ciphers used to protect data in 2G protocols.

Chapter 2 -Figure 2 . 1 -

 221 Figure 2.1 -Generic iterated cipher construction

2. 1 .Figure 2 . 3 -

 123 Figure 2.3 -Truncated differential characteristic always valid for 5, 6 and 7 rounds.

3 . 1

 31 Demirci-Selçuk Meet-in-the-Middle Attacks . . . . . . . . . . 23 3.1.1 Generalized Demirci-Selçuk (GDS) Attack . . . . . . . . . . . . 24 3.1.2 A New Ad-hoc Tool . . . . . . . . . . . . . . . . . . . . . . . . 26 3.1.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2 Algorithms for Division Property . . . . . . . . . . . . . . . . . 27 3.2.1 Searching for integral distinguishers . . . . . . . . . . . . . . . 28 3.2.2 Several Improvements . . . . . . . . . . . . . . . . . . . . . . . 29 3.2.3 A New Tool for Division Property . . . . . . . . . . . . . . . . 31 3.2.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3 Boomerang Characteristics . . . . . . . . . . . . . . . . . . . . . 32 3.3.1 Searching Boomerangs . . . . . . . . . . . . . . . . . . . . . . . 33 3.3.2 A New Tool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3.3 Results and Open Problems . . . . . . . . . . . . . . . . . . . . 35

Chapter 3 -

 3 Tools for Cryptanalysis attacks against round-reduced AES [DF13; DFJ13]. Since then I continued to work on this cryptanalysis technique and published several works related to it [DP15; BDP15; DF16; Shi+18; Der+18c]. At CRYPTO'16, in a joint work with Pierre-Alain Fouque, we proposed a new tool to automatically search for the best Demirci-Selçuk attacks against a large class of block ciphers.

Figure 3 . 1 -

 31 Figure 3.1 -Example of GDS attack (on 6-round AES). I P is in blue, I C in green, O P in red and O C in yellow. Hatched bytes play no roles and white bytes are constant.

4 . 5 .

 45 Guess the value of internal bits in O C and partially decrypt the ciphertexts to compute the differences in the b o chosen bits of Y . Check whether the sequence belongs to the hash table. If not, discard the guess. The complexity of this procedure depends directly on how many values the sets I P and I C ∩O P can assume (denoted by S), and on how fast all the possible values of sets I P ∪O C and I C ∩ O P can be enumerated (denoted by T ): -Data: (2 b i -1) • S(I P ) adaptively chosen plaintexts, -Time (online): 2 b i • T (I P ∪ O C ) partial encryptions, -Memory: b o • (2 b i -1) • S(I C ∩ O P ) bits, -Time (offline): 2 b i • T (I C ∩ O P ) partial encryptions. At the end of this attack we expect min(1, S(I C ∩ O P ) • 2 -bo(2 b i -1) ) • S(I P ∪ O C ) candidates to remain for I P ∪ O C . Thus b i and b o have to be chosen such that they provide enough filtration, but expanding them also increases the size of the sets I P , I C , O P and O C which then may rise the complexity of the resulting attack.

Chapter 4 -

 4 Real-life and Practical Cryptography practical attacks.

  0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xa 0xb 0xc 0xd 0xe 0xf occurence (relative frequency, %) value of the nibble Distribution of the value of nibble number 0 over the set of plaintexts 0x3 0x4 0x5 0x6 0x7 0x8 0x9 0xa 0xb 0xc 0xd 0xe 0xf occurence (relative frequency, %) value of the nibble Distribution of the value of nibble number 15 over the set of plaintexts

Figure 4 . 1 -

 41 Figure 4.1 -Distribution of the value of nibble 0 (left) and of nibble 15 (right) of the 2 20 plaintexts provided for the 12-round attack on SKINNY-64-128.

Figure 4 . 2 -

 42 Figure 4.2 -The CEJO framework.

Chapter 4 -

 4 Real-life and Practical Cryptography m = 8, k = 16, this yields a time complexity of 2 32 basic operations 2 (to be compared with 2 149 basic operations if the generic algorithm by Dinur were applied naively).

Figure 4 . 3 -

 43 Figure 4.3 -Overview of the keystream generation of GEA-1 and GEA-2. The D register is only present in GEA-2.

Figure 4 . 4 -

 44 Figure 4.4 -Initialization of register S

Figure 4 .

 4 5 depicts the process for register B. If any of the registers A, B or C end up in the all-zero state, the bit in position 0 of the register is forcibly set to 1 before keystream generation starts.

s 16 ,

 16 s 17 , . . . , s 63 , s 0 , s 1 , . . . , s 15

Figure 4 . 5 -

 45 Figure 4.5 -Initialization of register B

Figure 4 . 6 -

 46 Figure 4.6 -Initialization of register W

Figure 4 . 7 .

 47 For further reading we refer to ([Sch96, p. 378 ff.],[START_REF] Hoffman | Linear Algebra, PHI Learning[END_REF] p. 227]).

Figure 4 . 7 -

 47 Figure 4.7 -An LFSR in Galois mode.

2 and M C ∈ F 33×64 2

 22 such that α = M A s , β = M B s , γ = M C s ,

T

  AC := ker(M A ) ∩ ker(M C ) and U B := ker(M B ) then, curiously enough, we have 1. dim(T AC ) = 24 and dim(U B ) = 32 , 2. U B ∩ T AC = {0} .

Figure 4 . 8 -

 48 Figure 4.8 -Time complexity of our attack against GEA-2 as a function of the number of consecutive keystream bits available.

  4.1.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 On Recovering Affine Encodings in White-Box Implementations . . . . . . 4.2.1 White-box Cryptography . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2 . . 4.3.1 Description of GEA-1 and GEA-2 . . . . . . . . . . . . . . . . . . . 4.3.2 An Attack on GEA-1 . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.3 An Attack on GEA-2 . . . . . . . . . . . . . . . . . . . . . . . . . .

  Chapter 2 -Computer-aided Design of Optimal Components Truncated differential characteristic always valid for 2, 3 and 4 rounds. x(y) means that there are x active S-boxes somewhere in the state, with y columns containing at least one active bytes. Multiple x(y) in a state means that one of them must be true

			3 rounds
			2 rounds
	x 0	y 0	x 1	y 1	x 2	y 2	x 3
	SB SR MC		SB SR MC		1(1) SB SR MC	4(1)	3(1) 4(1) 5(2)
				1		1
	Figure 2.2 -

Table 2 .

 2 1 -Minimal number of S-boxes that our permutation P k reaches on a given number of rounds compared to the one from[START_REF] Khoo | Human-readable Proof of the Related-Key Security of AES-128[END_REF]. † No instantiation with a better probability than 2 -128 .

	Number of rounds	2	3	4	5	6	7
	Original key schedule	1	3	9	11	13 †	15
	P KLPS	1	5	10	14	18 †	22
	P k	1	5	10	15	20 †	23

  provided several examples for both AES and DES of boomerangs never coming back. Similar results were obtained by Kircanski in [Kir15]: a SAT solver is used to show that previous rectangle/boomerang attacks on XTEA [Lu09], SM3 [WKD07] and SHACAL-1 [DKK06] primitives were based on incompatible characteristics. Recently, in [Cid+18], Cid et al. proposed a new tool named boomerang connectivity table (BCT) to overcome the dependency issues. The BCT is actually a precomputation of all boomerangs through one single Sbox. Its main advantage is to provide a unified view of the switches previously introduced to refine the computation of the probability [BK09; DKS14]. In [SQH19], Song et al. give a generalized framework for the BCT and

Table 3 .

 3

1 -Results for different versions and number of rounds on skinny. Probabilities marked with asterisks have been validated experimentally. The four previous results from

[START_REF] Song | Boomerang Connectivity Table Revisited. Application to SKINNY and AES[END_REF]

are also given in parenthesis.

Contents 4.1 Cryptanalysis of SKINNY in the Framework of the SKINNY 2018-2019 Cryptanalysis Competition

. . . . . . . . . . . . . . 38 4.1.1 Remark on the Provided Messages . . . . . . . . . . . . . . . . 38 4.1.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.2 On Recovering Affine Encodings in White-Box Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2.1 White-box Cryptography . . . . . . . . . . . . . . . . . . . . . 41 4.2.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.3 Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.3.1 Description of GEA-1 and GEA-2 . . . . . . . . . . . . . . . . 48 4.3.2 An Attack on GEA-1 . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3.3 An Attack on GEA-2 . . . . . . . . . . . . . . . . . . . . . . . . 54

Table 4 .

 4 1 -Complexities of our attacks: the data complexity corresponds to the number of messages that are actually exploited in the attack, while time complexity is expressed in number of basic operations.

	Version	Rounds	Technique	Data Time Memory
	SKINNY-64-128	12	Truncated diff.	64	2 51.95 256 GB
	SKINNY-128-128	10	2nd-order truncated diff.	24	2 52	0.5 GB

  .4 for particular tap positions.

		0, . . . , 0, 0, K 63 , . . . , , K 0 , dir, IV 31 , . . . , IV 0
	3	12	22	38	42	55	63
	. . .	. . .	. . .	. . .	. . .	. . .
							f

  .6.

		0, . . . , 0, 0, K 63 , . . . , , K 0 , dir, IV 31 , . . . , IV 0
	4	18	33	57	63	83	96
	. . .	. . .	. . .	. . .	. . .	. . .
							f

Note that some papers use the term Type-2 Generalized Feistel to denote this construction

3.2. Algorithms for Division Property

All the information on the competitions and on the cipher in general can be found on https://sites.google.com/site/skinnycipher/home.

In practice the constants hidden in the O notation for our algorithm are quite small, and we disregard them when giving complexity estimates.

See minute 32:15 of the recorded talk.

The size of the registers are visible in the live state-recovery attack, see minute 48:25 of the recorded talk.

LIST OF PUBLICATIONS

Journal Articles