Adeline Barbara

Gildas

Mohamed Alexandre

Annelie Joseph David

REMERCIEMENTS

Je tiens tout d'abord à remercier Pierre-Alain et Patrick de m'avoir accompagné pendant toutes les étapes de cette thèse, et ce, jusqu'à la rédaction et la soutenance, périodes hautes en couleurs. J'exprime également ma reconnaissance à

INTRODUCTION ET RÉSUMÉ EN FRANÇAIS

La cryptographie du grec kryptos, « secret, caché » et graphein, « écrire » est un vieux sujet d'étude concernant en premier lieu la manière de cacher le sens d'un message à un tiers écoutant les communications. La première utilisation ( en un certain sens ) remonte à 1900 av. J.-C. dans une inscription de la tombe de Khnumhotep II où des hiéroglyphes inhabituels sont utilisés. Environ 1850 ans plus tard, Jules César utilise pour ses affaires militaires un chiffrement auquel il a donné son nom. Le chiffrement de César consiste à transformer un message ( aussi appelé clair ) en une séquence inintelligible de lettres appelée un chiffré en changeant chaque lettre du message en la n-ième ( fixe ) lettre suivante dans l'alphabet. Le receveur peut alors retrouver le message originel en appliquant la transformation inverse à chaque lettre du chiffré. Au cours du temps, les chiffrements se sont complexifiés avec par exemple l'utilisation de plusieurs alphabets et sur le plan pratique avec des mécanismes propres aux schémas comme des règles de conversions. Au xvi e siècle, Giovan Battista Bellasi crée le chiffrement de Vigenère ( faussement attribué au diplomate Blaise de Vigenère ). Le chiffrement de Vigenère peut être compris comme l'application de plusieurs chiffrements de César ( avec différentes translations ) sur le message. Plus précisément, une séquence secrète de n lettres appelée une clé connue uniquement par l'envoyeur et le receveur est utilisée pour chiffrer le message préalablement découpé en blocs de taille n. Pour chaque bloc, la i-ème lettre du bloc est translatée dans l'alphabet de r lettres où r est la position dans l'alphabet de la i-ème lettre de la clé. Un exemple de chiffrement est donné en Figure 1.

À la fin du xix e siècle, la cryptographie a aussi été affectée par la vague de formalisme logique présente dans les différents milieux universitaires. En particulier, en 1883, Kerckhoff dans La Cryptographie Militaire proposa une liste de principes qu'un bon chiffrement devrait suivre. Les principes de Kerchkoff sont toujours utilisés de nos jours dans le design de primitives cryptographiques particulièrement au regard de la sécurité : le système devrait être en pratique indéchiffrable ( sans connaissance de la clé ) ou dit autrement, le système devrait garantir la confidentialité du message ; le seul paramètre Depuis cette formalisation par Kerchkoff, deux révolutions suivirent en cryptographie. La première se passe durant la Deuxième Guerre mondiale avec la construction du premier ordinateur électronique programmable, le Colossus. Avec les puissances modernes de calcul, la cryptographie a largement adopté le modèle binaire pour les clairs, clés et chiffrés qui sont des séquences binaires de tailles arbitraires notées F * 2 . L'autre révolution en cryptographie a été l'invention de la cryptographie asymétrique avec le chiffrement RSA [START_REF] Ronald L Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF]. L'adoption de la cryptographie moderne avec les ordinateurs dans la vie civile à petits pas depuis les années 60 avec les réseaux bancaires et les communications téléphoniques. Au début des années 70, le gouvernement américain identifie un besoin pour un algorithme de chiffrement standardisé pour les informations sensibles mais nonclassifiées. Ce besoin fut comblé par le Data Encryption Standard (DES) ouvert au puvi blic en 1977 jusqu'à son remplacement par le fameux Advanced Encryption Standard (AES) en 2002. Pendant son utilisation, la sécurité du DES fut mise en doute notamment par le rôle qu'ont joué certains services secrets dans sa création ( en particulier la NSA ). Dans une optique naturelle vers plus de confiance pour les acteurs extérieurs, le processus de développement a complètement changé depuis et de nos jours existe une collaboration publique entre différents acteurs gouvernementaux, étrangers, scientifiques... Quand un nouveau schéma est jugé nécessaire, les agences de standardisation lancent un appel à contributions envers la communauté de la recherche cryptographique. Les candidats sont alors étudiés par la communauté pour aider à une première sélection par l'organisme standardisateur. Différentes sélections sont réalisées ( selon des critères différents ) jusqu'à obtenir un finaliste ou une liste de finalistes publiés avec des recommandations d'utilisation. Actuellement, deux compétitions majeures par le National Institute of Science and Technology (NIST) des États-Unis sont en cours : la compétition pour le chiffrement léger adapté aux objets connectés et la compétition post-quantique qui cherche à préparer la dépréciation de nombreux chiffrements asymétriques avec l'arrivée des ordinateurs quantiques.

v A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B B C D E F G H I J K L M N O P Q R S T U V W X Y Z A C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B D D E F G H I J K L M N O P Q R S T U V W X Y Z A B C E E F G H I J K L M N O P Q R S T U V W X Y Z A B C D F F G H I J K L M N O P Q R S T U V W X Y Z A B C D E G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F H H I J K L M N O P Q R S T U V W X Y Z A B C D E F G I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H J J K L M N O P Q R S T U V W X Y Z A B C D E F G H I K K L M N O P Q R S T U V W X Y Z A B C D E F G H I J L L M N O P Q R S T U V W X Y Z A B C D E F G H I J K M M N O P Q R S T U V W X Y Z A B C D E F G H I J K L N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M O O P Q R S T U V W X Y Z A B C D E F G H I J K L M N P P Q R S T U V W X Y Z A B C D E F G H I J K L M N O Q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U W W X Y Z A B C D E F G H I J K L M N O P Q R S T U V X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Z Z A B C D E F G H I J K L M N O P Q R S T U V W X Y
Durant cette thèse, nous nous sommes focalisés sur l'étude des primitives symétriques ( certaines intervenant dans la compétition légère du NIST ) selon différents points de vue nous permettant de voir la cryptanalyse de différents objets en allant d'une étude complémentaire d'une attaque générale ( présenté en Chapitre 1 ) à l'étude d'un critère dans une construction générale ( Chapitre 2 ) et à l'étude précise d'une primitive ( Chapitre 3 ). Pour introduire aussi clairement que possible les travaux de cette thèse, nous donnons une définition générale d'un chiffrement ( Définition 0.1 ) en gardant le vocabulaire déjà utilisé dans cette introduction. Le reste de cette introduction donne plus de détails à propos des constructions étudiées et leur sécurité. Idéalement, en plus d'assurer la confidentialité, un bon chiffrement symétrique devrait aussi garantir l'intégrité, c'est à dire la capacité à détecter un changement sur le chiffré et à le corriger si nécessaire ainsi que l'authenticité, c'est à dire le fait d'avoir une preuve de la provenance du chiffré. Essayer de construire directement des chiffrements ayant ces trois propriétés est un vrai défi demandant de nombreuses compétences pour chaque propriété vii mais aussi pour toutes leurs interactions afin de garder un schéma sécurisé. En pratique, pour simplifier la création de schéma en cryptographie symétrique, les chiffrements sont découpés en plusieurs couches. La première couche consiste à construire une primitive, une fonction cryptographique qui assure la confidentialité du message. Les deux autres propriétés voulues ( ou d'autres propriétés plus mineures ) sont obtenues en intégrant une primitive dans une construction plus grosse appelée un mode d'opération. Cependant, la cryptographie moderne a tendance à ne pas considérer l'intégrité comme une propriété que doit apporter cette deuxième couche car elle est obtenue par d'autres biais loin du sujet de cette thèse. Dans ce manuscrit, nous présentons nos travaux concernant différentes primitives cryptographiques et continuons cette introduction avec la présentation de différentes constructions classiques de primitives dans la partie I, en donnant des éléments pour comprendre leur sécurité dans la partie II et nous terminons cette introduction avec la partie III par un résumé des différents chapitres correspondant aux travaux de cette thèse.

Avant d'introduire les différentes primitives, voici un bref aparté sur le chiffrement à masque jetable, un très célèbre schéma qui peut s'assimiler à un chiffrement de Vigenère où la clé est exactement de la même taille que le message et qui sert souvent de base de comparaison ou d'inspiration à d'autres schémas. Dans le chiffrement à masque jetable, pour chaque clair m ∈ F * 2 , une clé k jetable ( à utilisation unique ) de la même taille que m est générée en tirant uniformément une valeur dans F |m| 2 où |m| est la taille de m. Le chiffré c est calculé simplement de la manière suivante : c = m ⊕ k où ⊕ représente le ou exclusif (XOR) bit à bit entre m et k. En 1949, Shannon [START_REF] Shannon | Communication theory of secrecy systems[END_REF] prouva que le chiffrement à masque jetable a une confidentialité parfaite ( pour être précis, il prouve que le schéma a une sécurité qui est plus forte que la sécurité calculatoire utilisée maintenant ) c'est à dire que même avec une puissance et un temps de calcul infinis, il n'est pas possible de retrouver le message depuis le chiffré sans connaissance de la clé. Malheureusement, le chiffrement à masque jetable a plusieurs défauts à commencer par le fait que la clé doit être de la même taille que le message et utilisée seulement une fois, ce qui le rend inadapté dans la vie réelle. Pour le remplacer, les cryptographes ont inventé plusieurs constructions reprenant certains aspects du chiffrement à masque jetable tout en introduisant des petites clés ( composées de 2 n bits avec 5 ≤ n ≤ 10 ) réutilisables. Bien que la sécurité sémantique de ces constructions ne soit pas prouvée ( aucune méthode n'est connue pour l'obtenir dans le cas symétrique ), la sécurité calculatoire qu'elles mettent en jeu font d'elles les principaux outils utilisés dans les communications modernes. Dans la viii partie suivante, nous introduisons les constructions rencontrées lors des travaux de cette thèse : les chiffrements par bloc et les chiffrements par flot.

I Chiffrement symétrique

Pour se rapprocher de la confidentialité apportée par le chiffrement à masque jetable, les cryptographes utilisent principalement deux familles de constructions imitant différents aspects de celui-ci. Nous réintroduisons dans cette partie ces deux familles en commençant par les chiffrements par bloc en sous-partie I.i et en continuant avec les chiffrements par flot en sous-partie I.ii. Pour compléter cette introduction sur les schémas de chiffrements symétriques, nous terminons cette partie avec un bref paragraphe ( sous-partie I.iii ) sur les modes d'opération.

I.i Chiffrement par bloc

Dans une construction de chiffrement par bloc, le clair n'est plus de taille arbitraire mais précise notée n : on parle alors de blocs qui contiennent le clair. Il en va de même pour la clé qui a une taille k et pour le chiffré de taille m. En général, les chiffrés et les clairs sont de même taille ( m = n ) et souvent la clé est aussi de même taille que le clair. Dans ce cas (m = n), la fonction de chiffrement est donc une famille de permutations sur les blocs paramétrées par la clé comme formellement donné en Définition 0.2. Définition 0.2 (Chiffrement par bloc). Un chiffrement par bloc est une fonction E :

F k 2 × F n 2 → F n 2 telle que pour tout κ ∈ F k 2 , les fonctions E(κ, •) sont des permutations.
Plus récemment, [START_REF] Liskov | Tweakable block ciphers[END_REF] propose une formalisation d'une variante des chiffrements par bloc appelée chiffrement par bloc paramétrable qui prennent un paramètre public supplémentaire appelé naturellement un paramètre. Ce paramètre est utilisé, dans certains cas, pour obtenir l'authenticité plus facilement dans certains modes d'opération ou pour réduire les coûts de chiffrements lorsque le paramètre peut être changé plus facilement que la clé comme dans le chiffrement d'un disque dur. Nous donnons une définition formelle de cette construction que nous avons rencontrée dans nos travaux avec la Définition 0.3.

Définition 0.3 (Chiffrement par bloc paramétrable). Un chiffrement par bloc paramétrable est une famille de fonctions

E : F t 2 × F k 2 × F n 2 → F n
2 telle que pour tout τ ∈ F t 2 , les fonctions E(τ, •, •) sont des chiffrements par bloc. ix La construction de chiffrements par bloc comme fonction prenant une entrée et renvoyant une sortie est rarement donnée dans la littérature en faveur des constructions itératives ( comme illustré dans la Figure 2 ) qui transforment en plusieurs tours le clair s 0 en chiffré s r . Dans une construction itérative, la clé est utilisée en premier lieu pour générer une séquence k 0 , . . . , k r de clés de tour qui seront mélangées une à une ( par tour ) à l'état i.e. le clair partiellement transformé à ce tour. L'autre composant d'une construction itérative est la fonction de tour qui va comme son nom l'indique, transformer le bloc à chaque tour. La première itération calcule s 1 = f (s 0 ⊕ k 0 ), la deuxième calcule s 2 = f (s 1 ⊕ k 1 ) et ainsi de suite pour les r tours. Dans la littérature, le tampon qui va contenir au tour i la valeur s i est appelé état interne de la construction. Deux objectifs nécessaires à la sécurité sont réalisés par la fonction de tour à savoir la diffusion, le mélange en position dans l'état interne des bits de clair et de chiffrés et la confusion, le mélange en complexité ( du point de vue du calcul de l'inverse ) des bits de clé et de clair. Plusieurs constructions concrètes adoptent cette forme itérative et les deux plus courantes sont présentes dans les travaux de cette thèse, à savoir les réseaux de permutation-substitution et les constructions de Feistel.

Algorithme optionnel d'expansion

k s 0 f s 1 . . . f s r s r+1 k 0 k 1 k r-1 k r
Figure 2 -Construction itérative d'un chiffrement par bloc de [START_REF] Jean | TikZ for Cryptographers[END_REF] Réseaux de Permutation-Substitution. Les réseaux de Permutation-Substitution sont peut-être les constructions itératives pour les chiffrements par bloc les plus connues par le standard AES proposé par Daeman et Rijmen [START_REF] Daemen | AES proposal: Rijndael[END_REF] et consistent à découper la fonction de tour en deux parties : la couche de substitution apportant la confusion et la couche de permutation apportant la diffusion. Il n'y a pas de méthode connue pour créer une bonne couche de substitution pour un état de 64 ou 128 bits. Pour combler ce manque, la stratégie adoptée dans la littérature est de morceler l'état en plus petites cellules de 4, 8 bits généralement et d'appliquer sur chaque cellule une bonne substitution appelée une x boite-S. La couche de permutation mélange l'information entre les cellules de l'état. Deux paradigmes sont possibles pour cette couche : le premier consiste à permuter et appliquer une opération linéaire aux cellules et est utilisé dans AES ou SKINNY [START_REF] Beierle | The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS[END_REF]. Le second paradigme possible est de permuter directement les bits de l'état comme dans PRESENT [START_REF] Bogdanov | PRESENT: An ultra-lightweight block cipher[END_REF] ou Gift [START_REF] Banik | GIFT: a small present[END_REF]. Un exemple de chiffrement ( jouet ) orienté au niveau des bits est donné en Figure 3. Constructions de Feistel. Les constructions de Feistel sont l'autre construction générique utilisée pour les chiffrements par bloc itératifs que nous avons étudiés lors de cette thèse. Dans la plus simple construction de Feistel ( Figure 4 ), le message est séparé en deux moitiés ( égales ) appelées parfois branches. La branche de droite passe par une fonction F paramétrée par la clé et est ajoutée à la branche de gauche puis les deux branches sont échangées. La fonction F est souvent une couche de boites-S suivie d'un ajout de la clé ( de tour ). Plusieurs généralisations de cette construction ont été proposées dans la littérature et en particulier l'une d'elle sera plus précisément étudiée pour l'un des travaux de cette thèse dans la partie 2.

xi

f 1 f 2 f 3 L 0 R 0 L 3 R 3
Figure 4 -Trois tours d'un réseau de Feistel de [START_REF] Jean | TikZ for Cryptographers[END_REF] où les fonctions f 1 , f 2 , f 3 sont obtenues à partir de la fonction F avec les clés de tours une, deux et trois.

I.ii Chiffrement par flot

L'autre grande famille de chiffrements symétriques est celle des chiffrements par flot. À la différence des chiffrements par bloc, il n'y a pas un bloc de taille fixe mais un flot de bits à chiffrer. L'idée pour ce faire est de générer un flot de clé de même taille que le flot de message et d'ajouter (XOR) les deux ( voir Figure 5 ). Dit autrement, un chiffrement par flot consiste à créer l'équivalent d'une clé de bonne taille pour un chiffrement à masque jetable à partir d'une clé de taille fixe. La confidentialité pour un chiffrement par flot passe donc par la difficulté à retrouver la valeur de l'état interne ou la clé originale depuis le flot de clé. En pratique, le flot de clé est généré bit à bit à mesure que le flot de message est reçu. On parle de top d'horloge du chiffrement à flot pour chaque bit de flot de clé généré.

Registre à décalage à rétroaction linéaire (LFSR). Si les boites-S étaient l'un des éléments les plus élémentaires des chiffrements par bloc, son remplacement dans le contexte des chiffrements par flot est le registre à décalage à rétroaction linéaire (LFSR). Un LFSR peut être vu comme un registre organisé en cases contenant des bits ( souvent un bit ). À chaque top d'horloge, le registre est décalé d'une position vers la droite et la première case prend comme valeur le résultat d'une fonction linéaire, la fonction de rétroaction appliquée à l'état ( avant le décalage ). Un schéma général de LFSR est donné dans la Figure 6. Délinéariser. Les LFSRs sont très pratiques dans la création de chiffrement à flot avec le top d'horloge du LFSR s'étendant naturellement au top d'horloge du chiffrement. Cependant, comme la fonction de rétroaction est linéaire, si elle est la seule composante utilisée, le système est facilement inversible, ce qui n'est pas idéal pour la sécurité. Deux stratégies différentes existent dans la littérature pour ajouter une opération non-linéaire aux LFSRs : transformer une fonction de rétroaction linéaire en fonction de rétroaction non-linéaire comme dans Grain [START_REF] Hell | Grain: a stream cipher for constrained environments[END_REF] ou Trivium [START_REF] De | Trivium[END_REF]. L'autre solution est de désynchroniser le top d'horloge de plusieurs LFSRs avec une fonction non-linéaire dépendant des états de chaque LFSR comme dans A5/1 [START_REF] Briceno | A pedagogical implementation of A5/1[END_REF] ou MICKEY [START_REF] Babbage | The MICKEY stream ciphers[END_REF].

I.iii Mode d'opération

Une primitive peut être placée dans une plus grande construction appelée mode d'opération pour obtenir de nouvelles propriétés. Dans la plupart des utilisations actuelles, la seule confidentialité est souvent insuffisante et l'authenticité est ajoutée avec le mode d'opération contrairement à l'intégrité qui vient d'autres procédés. Les modes d'opération qui, en plus de la confidentialité, apportent l'authenticité sont appelés chiffrement authentifié (AE) ou chiffrement authentifié avec données associées (AEAD), si des données publiques sont associées au message. C'est ce type de chiffrement qui est demandé par la compétition de cryptographie symétrique légère du NIST.

En général, lorsqu'elle existe, une preuve de sécurité ou portant sur une autre propriété est donnée sur le mode d'opération. Dans ces preuves, la primitive considérée est une primitive idéale. Dans la réalité, les primitives pratiques utilisées introduisent des biais dans la preuve qui affaiblissent la sécurité de la construction. Les travaux de cette thèse portent en partie sur l'étude de certains de ces biais trouvés à partir de méthodes générales. Pour mieux les comprendre, dans la partie suivante, nous introduisons les notions de sécurité nécessaires à la présentation de nos travaux.

II Analyse et sécurité des chiffrements symétriques

II.i Modèle de sécurité

Pour comprendre la notion de sécurité dans les chiffrements symétriques, il est d'abord nécessaire de comprendre ce que l'attaquant recherche et ce qu'il peut faire. Trivialement, si un attaquant peut directement demander la valeur de la clé et l'obtenir, il pourra lire les messages à partir des chiffrés mais la primitive n'est pas, dans ce cas, considérée comme cassée. En pratique, le pouvoir donné à l'attaquant est modélisé par sa capacité à demander le chiffrement ou déchiffrement à un oracle. Un oracle peut être vu comme une boîte noire qui contient une clé adaptée au chiffrement qu'il représente et répond aux demandes de chiffrements et de déchiffrements envoyées par l'attaquant. Son but, la plupart du temps, est de retrouver la clé cachée dans l'oracle en utilisant seulement les demandes permises par celui-ci. xiv Dans la littérature, il y a plusieurs types d'oracles en fonction des demandes considérées comme permises. Le plus faible des oracles permet uniquement la requête de chiffrés décidés sans connaitre les clairs associés. Dans ce cas, le modèle d'attaque appelé chiffrés connus est le niveau le plus bas de sécurité demandé par les chiffrements à tel point qu'il est souvent négligé en faveur de preuves ou de raisonnements avec des modèles plus forts. Dans ces derniers, le pouvoir de l'attaquant est augmenté en demandant des paires clairs/chiffrés décidées, puis en demandant pour le chiffrement de clairs choisis ( par l'attaquant ) et finalement le chiffrement et déchiffrement de clairs et chiffrés arbitraires. Ces modèles sont appelés respectivement clairs connus (KP), clairs choisis (CPA) et chiffrés choisis (CCA).

Dans la littérature, l'autre facteur nécessaire à la description des attaques est la définition et la quantification des buts et succès de l'attaquant. Dans le formalisme actuel, l'attaquant va jouer à un jeu où il gagne lorsqu'il récupère une information précise qu'il devrait obtenir avec une probabilité faible. Une attaque peut être interprétée comme une stratégie pour l'attaquant telle que la probabilité de gagner est meilleure ( par un facteur polynomial en la taille du secret ) que la probabilité de choisir au hasard sa réponse. Un des jeux utilisés dans la littérature consiste à initialiser l'oracle uniformément et aléatoirement entre deux protocoles d'opération : le premier correspondant au fait de choisir correctement une clé et de l'utiliser normalement dans le schéma de chiffrement ; le deuxième au fait de renvoyer uniformément et aléatoirement une réponse de forme correcte. Le but dans ce jeu pour l'attaquant est de déterminer le protocole d'opération utilisé par l'oracle. Lorsqu'aucun attaquant ne peut gagner à ce ce jeu avec un avantage conséquent, le chiffrement est qualifié d'indistinguable (IND) et il est utilisé avec les précédents modèles d'attaquants pour définir complètement la sécurité d'un schéma en parlant par exemple de schéma IND-CCA.

Dans la cryptographie symétrique, de telles preuves de sécurité sont rarement faites pour les primitives et par extension, la sécurité des primitives est conceptualisée par un point de vue très pratique : elles sont sûres si aucune attaque pratique n'existe contre elles. La sécurité peut, dans ce cas, être comprise comme l'effort continu pour casser des primitives avec des techniques classiques ou de nouvelles attaques jusqu'à leur défaillance et remplacement par de nouvelles primitives plus sûres. Lors de leur travail, les cryptographes en symétrique ne cherchent pas toujours des attaques contre des primitives mais des composants de certaines attaques appelés distingueurs qui peuvent être compris comme des tests qui permettent de casser efficacement l'indistinguabilité des primitives.

xv

II.ii Distingueur

Un distingueur est un algorithme qui casse ( avec une bonne probabilité ) le caractère d'indistinguabilité de chiffrements avec l'accès seul à des paires clairs/chiffrés en décidant si les paires sont générées honnêtement ou aléatoirement. Les distingueurs sont cherchés essentiellement en observant dans les chiffrements des comportements qui ne devraient pas exister dans des fonctions aléatoires. Un exemple de propriétés observées pour trouver des distingueurs est la propagation de différences dans le chiffrement dont nous parlons plus en détail dans la sous-partie II.iii. Pour les constructions itératives, un distingueur sur r -1 tours peut être étendu facilement en une attaque sur r tours, ce qui explique pourquoi une fois que les distingueurs sont obtenus lors d'une étude, les attaques correspondantes sont rarement données dans la littérature. En effet, en assumant que la clé de tour est plus petite que la clé, un attaquant peut demander un ensemble de chiffrés ( sur r tours ) et deviner la dernière sous-clé. La clé de tour devinée est utilisée pour déchiffrer un tour et le distingueur peut être testé sur l'ensemble des chiffrés partiellement déchiffrés avec l'idée que si la clé de tour est incorrecte, le distingueur devrait considérer l'ensemble testé comme généré par de l'aléatoire et non par une clé. Ce processus peut être répété avec un tour de moins jusqu'à obtenir assez de sous-clés pour reconstruire la clé maître. En conséquence, une bonne justification pour la sécurité d'une primitive est de montrer qu'aucune méthode classique comme des analyses différentielles ou linéaires ne permettent d'obtenir de bons distingueurs. Dans la sous-partie suivante, nous introduisons la cryptanalyse différentielle, la théorie principale que nous avons utilisée pour nos travaux dans cette thèse.

II.iii Cryptanalyse différentielle

À CRYPTO'90, Biham et Shamir [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF] présentaient leur analyse du Data Encryption standard, le standard de chiffrement américain avec une nouvelle méthode, la cryptanalyse différentielle où une différence est observée dans son passage par le système. À la même période, des attaques différentielles sont montées contre d'autres chiffrements par bloc comme FEAL [START_REF] Biham | Differential Cryptanalysis of Feal and N-Hash[END_REF]. En 1998, Vaudenay et al. proposent un nouveau cadre appelé théorie de la décorrélation qui permet a priori ( entre autres ) de prévenir les attaques différentielles ( directes ), elle est appliquée pour la première fois pour construire les chiffrements COCONUT et PEANUT [START_REF] Vaudenay | Provable security for block ciphers by decorrelation[END_REF]. La même année Wagner, [START_REF] Wagner | The boomerang attack[END_REF] prouve que la théorie de la décorrélation n'est pas suffisante pour esquiver toutes les attaques différentielles en exhibant une nouvelle attaque, les boomerangs. Depuis, de nouvelles attaques xvi et variantes n'ont cessé d'apparaître dans la littérature comme les attaques sandwich [START_REF] Orr Dunkelman | A practical-time relatedkey attack on the KASUMI cryptosystem used in GSM and 3G telephony[END_REF], rectangle [START_REF] Biham | The rectangle attack-rectangling the Serpent[END_REF] ou les attaques différentielles impossibles [START_REF] Knudsen | DEAL-a 128-bit block cipher[END_REF]. La cryptanalyse différentielle est maintenant une méthode classique pour l'étude de nouvelles primitives qui, pour être sérieusement considérées, doivent avoir prouvé leur résistance contre différentes attaques différentielles.

La cryptanalyse différentielle étudie la transformation de différences au cours du chiffrement. Pour une paire de messages p 0 et p 1 , la différence ∆p entre les deux messages est définie par ∆p = p 0 ⊕ p 1 . Trivialement, une différence est facilement propagée à travers une opération linéaire L puisque L(∆p) = L(p 0 ) ⊕ L(p 1 ). Cependant, on ne peut pas dire la même chose du passage par des opérations non-linéaires où cette égalité devient en général fausse. Pour décrire les diverses différences en sortie possibles pour une différence en entrée après une opération non-linéaire, la communauté parle de probabilité d'observer une différence de sortie précise calculée avec le dénombrement du nombre de paires p 0 , p 0 ⊕ ∆p qui atteignent cette différence ( divisé par le nombre total de paires ). Un modèle d'attaquant plus fort peut en plus des différences dans le message ou état interne introduire des différences dans la clé pour les constructions itératives, on parle alors de modèle d'attaque à clés reliées. Si dans tous ces cas, le chiffrement se comporte comme une fonction aléatoire au regard des différences, alors la probabilité d'observer une valeur particulière de différence en sortie devrait être de 2 -n où n est la taille du message. Sinon, nous venons de décrire un distingueur particulier contre le chiffrement qui peut être utilisé pour monter une attaque.

Faire une analyse différentielle complète d'une primitive est difficile et plusieurs sousproblèmes ont été proposés pour la simplifier dans la littérature. Pour les chiffrements itératifs, la différence peut être suivie tour par tour pour obtenir une caractéristique différentielle qui peut se décrire par la séquence de différences (∆ 0 , . . . , ∆ r ) observées au début de chaque tour plus la différence finale en sortie. La probabilité d'une caractéristique est compliquée à calculer directement mais peut être approximée en considérant que toutes les transitions d'un tour à l'autre sont indépendantes les unes des autres. Dans ce cas, la probabilité de la caractéristique est

r i=1 P(∆ i-1 , ∆ i ) où P(∆ i-1 , ∆ i ) est
la probabilité que la différence ∆ i-1 devienne ∆ i après un tour. Le calcul de la probabilité d'une caractéristique peut aussi être simplifié en utilisant la structure de la fonction de tour, comme nous allons le montrer pour les SPNs. En effet, comme dit précédemment, la couche linéaire et l'addition de clé sont des couches où les différences vont se propager de manière déterministe ( i.e. avec une probabilité 1 ). Il ne reste donc que la couche de substitution xvii à prendre en compte pour le calcul de la probabilité. Or, la couche de substitution est composée d'applications parallèles de boites-S qui sont donc les objets à considérer pour l'étude de différences à travers le tour. Puisque les boites-S sont bien plus petites que le bloc, la probabilité exacte d'observer une paire de différences d'entrée sortie (∆ in , ∆ out ) peut être calculée et l'information est souvent condensée dans une table appelée table de distribution des différences (DDT). La DDT est une table à double entrée qui pour une entrée correspondant à la paire de différences (∆ in , ∆ out ) donne la probabilité d'observer ∆ out = S(x) ⊕ S(x ⊕ ∆ in ) pour les différentes valeurs de x et où S correspond à la boîte-S.

Pour simplifier une nouvelle fois la recherche de caractéristiques différentielles dans les SPNs, Knudsen [START_REF] Lars R Knudsen | Truncated differentials and Skipjack[END_REF] a proposé d'ignorer la valeur exacte des différences pour ne garder que la présence ( active ) ou l'absence ( inactive ) de différence pour une boîte-S à un tour donné. Le terme adopté par la communauté pour décrire cet objet est caractéristique différentielle tronquée. Elles se sont révélées très utiles pour le construction de primitives en particulier pour donner des preuves simples pour la résistance contre les attaques différentielles. Pour être plus précis, pour une caractéristique différentielle tronquée donnée avec n boites-S actives, et pour la propagation à travers la boite-S avec la meilleure probabilité p, une borne supérieure facile à calculer pour la probabilité d'une caractéristique ayant la forme tronquée ( pour un nombre donné de tours ) est donc p n . Le même raisonnement peut être appliqué pour les caractéristiques ayant le minimum de boites-S actives pour obtenir une borne supérieure sur les caractéristiques différentielles pour un nombre de tours donné. Si cette borne supérieure est plus petite que 2 -m où m est la taille de bloc, alors le chiffrement semble au premier abord être résistant à la cryptanalyse différentielle. Dans cette dernière décennie ( depuis 2009 pour être exact ), de nouvelles méthodes fondées sur les solveurs ont été présentées pour la recherche de caractéristiques différentielles tronquées [SNC09 ; MP13 ; Mou+12 ; Sun+14 ; KLT15]. Les solveurs sont des algorithmes génériques qui prennent en entrée la description d'un problème et cherche automatiquement une solution à celui-ci. Dans cette thèse, nous avons aussi utilisé des solveurs pour calculer de nouvelles caractéristiques différentielles. Des détails supplémentaires sur nos travaux concernant ces aspects sont présentés au Chapitre 3.

xviii

III Résumé des chapitres

Pendant cette thèse, nos travaux ont essentiellement porté sur de la cryptanalyse différentielle grâce à des algorithmes particuliers à travers différentes perspectives allant d'une étude détaillée d'une attaque récente avec des expériences algorithmiques à l'analyse d'un critère particulier des réseaux de Feistel avec un algorithme constructif ainsi que l'étude d'une primitive particulière SKINNY avec des solveurs. Dans cette partie, nous donnons un résumé de chacun de ces travaux présentés un à un dans les différents chapitres.

Dans le Chapitre 1, nous revisitons les attaques rapides par collision proche ( "Fast Near Collision Attack" (FNCA) ), un nouveau type d'attaque proposé par Zhang et al. [START_REF] Zhang | Fast Near Collision Attack on the Grain v1 Stream Cipher[END_REF]. Les FNCAs ont été appliquées à deux chiffrements : Grain v1 ( dans le papier original ) et A5/1 [Zha19] pour obtenir de nouvelles attaques plus rapides que les meilleures connues jusqu'alors. Cependant, nous avons trouvé des incohérences dans ces attaques et avons en conséquence publié des versions corrigées prouvant que les FNCAs ne sont pas des attaques efficaces pour les exemples donnés.

Dans le Chapitre 2, nous résolvons un problème ouvert depuis 10 ans et nous présentons les nouveaux résultats sur les réseaux de Feistel généralisés que nous avons obtenus. Plus précisément, nous avons étudié en particulier une propriété des permutations des réseaux de Feistel généralisés appelée tour de diffusion.

Pour finir, dans le Chapitre 3, nous présentons nos travaux sur les caractéristiques différentielles du chiffrement par bloc SKINNY. Nous utilisons une approche très classique de séparation de la recherche de caractéristiques différentielles. Grâce à des outils adaptés, nous avons trouvé des et parfois les meilleures caractéristiques différentielles de SKINNY.

III.i Revisiter les attaques rapides par collision proche

En 2018, Zhang et al. dans [START_REF] Zhang | Fast Near Collision Attack on the Grain v1 Stream Cipher[END_REF] proposent une nouvelle attaque générique, les attaques rapides par collision proche, et la première application de celle-ci sur le chiffrement à flot Grain v1. Puis, dans [START_REF] Zhang | Cryptanalysis of GSM Encryption in 2G/3G Networks Without Rainbow Tables[END_REF] Zhang et al. l'appliquent une nouvelle fois avec succès contre A5/1 pour obtenir une meilleure attaque de récupération de clé. Les FNCAs sont des attaques "diviser pour régner" pour retrouver l'état interne du chiffrement à flot depuis le flot de clé. Elles séparent l'état interne en deux parties : la partie cruciale (CP) et la partie restante (RP). Une fois la CP connue, il est facile de retrouver la RP. La partie cruciale est retrouvée grâce à la partie collision proche de l'attaque à partir d'un petit échantillon de flot de clé. xix Lors de cette thèse, nous avons essayé d'implémenter l'attaque contre A5/1 et après une étude du processus pour confirmation, nous avons trouvé plusieurs incohérences du point de vue de la théorie de l'information dans la description de l'attaque et des erreurs dans le code donné par Zhang et

III.ii Recherche efficace de couche de diffusion pour les réseaux de Feistel généralisés

Les Feistels sont une des constructions les plus classiques pour les chiffrements par bloc. À CRYPTO'89, Zheng et al. [START_REF] Zheng | On the construction of block ciphers provably secure and not relying on any unproved hypotheses[END_REF] proposèrent différentes généralisations de la construction de base des Feistels. L'une d'entre elles consiste à appliquer en parallèle plusieurs constructions de Feistel de base puis à glisser toutes les branches vers la droite. Comme remarqué dans [Nyb96 ; SM10], la translation vers la droite n'est pas la seule permutation qui peut être employée ici. La construction où la permutation utilisée est arbitraire est maintenant appelée réseau de Feistel généralisé (GFN).

Cependant, lors de l'introduction des GFNs en 1996, aucune famille de permutations à préférer n'est donnée pour des constructions a priori plus sûres. En 2010 à FSE, Suzumaki et Minematsu [START_REF] Suzaki | Improving the generalized Feistel[END_REF] proposent un nouveau critère, le tour de diffusion, qui peut être utilisé pour informer dans le choix d'une permutation à privilégier. Le tour de diffusion peut être compris comme une mesure de la vitesse nécessaire en nombre de tours pour qu'une différence sur n'importe quelle branche se diffuse sur toutes les branches du réseau. Avec leur travail, Suzumaki et Minematsu sont capables de manière exhaustive d'évaluer toutes les permutations jusqu'à 16 branches pour trouver toutes les permutations optimales ( selon ce critère ). De plus, après avoir remarqué que pour toutes les tailles de réseau qu'ils testent, il y a une permutation optimale qui est paire-impaire, c'est-à-dire qui transforme tous les pairs en impairs et inversement. Ils proposent à partir de cette xx observation une méthode de construction générale pour trouver de bonnes permutations paires-impaires lorsque le nombre de branches est une puissance de deux. En particulier, ils ont trouvé une bonne permutation paire-impaire avec 32 branches et un tour de diffusion de 10. En 2019, Cauchois et al. [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF] publient une nouvelle méthode pour la construction de permutations optimales paire-impaires leur permettant d'en trouver jusqu'à 26 branches.

Pendant cette thèse, nous avons étudié le problème de la recherche de permutations optimales pour le tour de diffusion pour les GFNs. Nous avons trouvé une nouvelle caractérisation du tour de diffusion qui permet de développer un algorithme efficace pour la recherche de permutations paires-impaires optimales entre 28 et 42 branches en testant si le tour de diffusion est à 9. En l'utilisant, nous avons exhibé toutes les permutations paires-impaires optimales pour The Vigenère cipher can be understood as multiple uses of the Caesar cipher on the message. More precisely, a secret sequence of letters of size n that is now called a key known only by the sender and receiver is used in the scheme. To encrypt, the message is split in block of size n. For each block, the i-th letter is shifted to the right by r in the alphabet where r is the position in the alphabet of the i-th letter of the key. An example of encryption following this scheme is given in Figure 7. In practice, another permutation table can be used and only the key must be kept secret, the table can be published.

At the end of the 19th century, cryptography was also changed by the formalism that swept the different intellectual disciplines. In particular, in 1883 Kerckhoff in La Cryptography Militaire [START_REF] Kerckhoff | La cryptographie militaire[END_REF] proposed a list of principles that a cipher should follow. Kerckhoff's principles are still being followed nowadays in the design of cryptographic primitives particularly regarding the security: the system should be practically indecipherable or said in an another manner the system should guarantee the confidentiality of the message and the only secret should be the key.

Since this formalization, two important revolutions happened in cryptography. The first being the computing revolution during the second World War with the construction

Introduction A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B B C D E F G H I J K L M N O P Q R S T U V W X Y Z A C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B D D E F G H I J K L M N O P Q R S T U V W X Y Z A B C E E F G H I J K L M N O P Q R S T U V W X Y Z A B C D F F G H I J K L M N O P Q R S T U V W X Y Z A B C D E G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F H H I J K L M N O P Q R S T U V W X Y Z A B C D E F G I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H J J K L M N O P Q R S T U V W X Y Z A B C D E F G H I K K L M N O P Q R S T U V W X Y Z A B C D E F G H I J L L M N O P Q R S T U V W X Y Z A B C D E F G H I J K M M N O P Q R S T U V W X Y Z A B C D E F G H I J K L N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M O O P Q R S T U V W X Y Z A B C D E F G H I J K L M N P P Q R S T U V W X Y Z A B C D E F G H I J K L M N O Q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U W W X Y Z A B C D E F G H I J K L M N O P Q R S T U V X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Z Z A B C D E F G H I J K L M N O P Q R S T U V W X Y Key L A T I N L A T I N L A T I N L A T I N L A Plaintext L O R E M I P S U M D O L O R S I T A M E T ciphertext W O K M Z T P L C Z O O E W E D I M I Z P T
Figure 7 -Example of encryption with the Vigenère cipher. The upper table gives the correspondence between the plaintext letter (column), the key letter (row) and the ciphertext (entry). The lower table gives the ciphertext when the key is "LATIN" and the plaintext is "LOREM IPSUM DOLOR SIT AMET". of the first programmable electronic and digital computer, the Colossus. With modern computational power appearing, cryptography has completely adopted the binary framework: the message, key and ciphertext are now arbitrary length bitstrings in F * 2 . The other breakthrough in cryptography was the invention of asymmetric cryptography with the RSA cipher by Rivest, Shamir and Adleman in [START_REF] Ronald L Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF]. In asymmetric cryptography, the secret key is replaced by a pair of keys: the public key and the private key. Adopting modern cryptography on computer in civilian life begins little by little in the 60's with banking and communication networks. In the early 70's, the US government identified a need for a standard encryption algorithm for unclassified but still sensitive information. The Data Encryption Standard (DES) was then opened to public uses in 1977 and kept as a standard up to its replacement in 2002 by the famous Advance Encryption Standard (AES). During its uses, the security of DES was doubted from its conception in relation to various US agencies (most famously the NSA) involved in the design process. As a natural evolution towards more confidence, the way new primitives are developed changed completely (like AES for example) and nowadays it is a sort of public collaboration between several actors. When a new design is wished for, standardization agencies call for public contributions from the cryptographer community. Candidates are then studied by the community to inform a first sieving of the list which is studied again in the same way up to the point where one finalist or a portfolio of finalists are published with recommendations of uses. The organizers select during each round some candidate in light of these studies and justify their choices with public reports on the process of selection. Right now, two major competitions by the National Institute of Science and Technology (NIST) of the USA are taking places: the lightweight competition for new symmetric primitives adapted to IoT and the post-quantum competition to prepare the replacement of RSA necessary from the rapidly approaching quantum computer.

During this thesis, we focus essentially on analyzing the existing primitives with different algorithms and focusing on different aspects from properties that could be considered in their designs to studying criteria informing on potential attacks and to reviewing attacks against them. To introduce as clearly as possible the works of this thesis, we now give Definition 0.1, a general definition of the primitives we studied, the encryption ciphers by keeping the vocabulary already used here about ciphers. We will give more details regarding their constructions and security in the rest of this introduction.

Definition 0.1 (Encryption). An encryption function is a function

E : F * 2 × F * 2 → F * 2
such that for any key in F * 2 , the function E(key, •) is a surjection and its inverse function D(key, •) is efficiently computable when the key is known.

Ideally in addition to ensuring confidentiality, a good symmetric cipher should give integrity meaning it should be possible to detect a tempering of the message and authenticity meaning there should be a process to verify that the source (of the ciphertext) is who it pretends to be. Trying to design directly a cipher offering this three properties is hard and asks for numerous competences, knowledge and various security proofs for each property but also for their interactions. To simplify the conception and verification of new designs, a layered strategy of conception is widely used in symmetric cryptography. The first layer consists in constructing, designing primitives, ciphers that ensure confidentiality for the messages. The missing two properties (or other properties for particular cases) are obtained by integrating a good primitive in a bigger construction although Introduction modern cryptography is centered essentially on confidentiality and authenticity, integrity being granted from other processes. In this thesis, we will present our works concerning different primitives and for greater clarity, we will begin by reviewing classical ways to construct primitives in Section I, we give some elements to understand their resistance and security in Section II and introduce the works presented in each chapter in Section III.

Before introducing the different ways of constructing primitives, we review right now the one time pad, a well known scheme which can be assimilated to a Vigenère cipher where the key has the same size as the message that will serve as a basis to explain the other constructions. In the one time pad, for each message m ∈ F * 2 , a key k of the same size as m is generated by uniformly taking a value in

F |m| 2
where |m| is the size of m and computing the corresponding ciphertext c with c = m ⊕ k. In 1949, Shannon [START_REF] Shannon | Communication theory of secrecy systems[END_REF] proved that the one time pad cipher has perfect confidentiality (to be precise this is called perfect secrecy which can be opposed to computational security or to semantic security, weaker security notions) that is to say that even given infinite time and computational power, it would be impossible to retrieve the message from the ciphertext without knowledge of the key. Unfortunately, the one time pad presents multiple defaults beginning with the fact that the key must be of the same size as the message and unique for each communication. As a result, cryptographers invented different constructions to approach the one time pad while keeping in a reasonable measure reusable small keys of 2 n bits with 5 ≤ n ≤ 10. Although, the semantic security of those constructions is not proven, the computational security they exhibit made them the primary symmetric tools in use in modern communications. In the next Section, we review well known constructions that we encounter during the works of this thesis.

I Symmetric Cipher

To approach the one time pad in term of confidentiality, cryptographers now use principally two families of constructions miming different aspects of the one time pad. We review these two families of constructions beginning with the block ciphers in Subsection I.i and following in Subsection I.ii with stream ciphers. Finally, to complete this presentation, we briefly introduce in Subsection I.iii modes of operation corresponding to the general way to complete primitives that is used to obtain the integrity and authenticity or more peculiar properties in certain use cases.

I.i Block cipher

In block cipher construction, the message is not anymore of arbitrary length but limited to a block of size n. The same can be said about the key with a fix size k. The encryption is then a family of permutations of the block of size n parameterized by the key as can be seen in Definition 0.2.

Definition 0.2 (Block cipher). A block cipher is a function

E : F k 2 × F n 2 → F n 2 such that for all κ, the function E(κ, •) is a permutation.
More recently, in [START_REF] Liskov | Tweakable block ciphers[END_REF] a slightly different construction was proposed: the tweakable block ciphers which contain an additional public parameter called a tweak (or tweaks if multiple are possible). The tweak can be used in different scenarios to add more easily some new properties like integrity or authenticity. We give a formal description of this construction in Definition 0.3.

Definition 0.3 (Tweakable block cipher). A tweakable block cipher is a family of functions

E : F t 2 × F k 2 × F n 2 → F n 2 such that for all τ ∈ F t 2 , the functions E(τ, •, •) are block ciphers.
Since constructing directly a block cipher is hard, modern constructions mostly adopt an iterative process, see Figure 8. In an iterated construction, the key is used to first generate a sequence (k 0 , . . . , k r ) of round keys that will be added little by little to the message at each round. The other component of an iteration is the round function f that transforms the message at each round. The first iteration computes s1 = f (s 0 ⊕ k 0 ), the second iteration iteration corresponds to s 2 = f (s 1 ⊕ k 1 ) and the process is repeated for r rounds. In the literature, we talk about the internal state of a construction for a buffer s that will contain in order the values s 0 , s 1 , . . . , s r . Two objectives are realized by the round function namely the diffusion, shuffling every bits of message and key together and the confusion, making the inversion of the shuffle of key and message bits hard to inverse in a mathematical sense. Multiple generic constructions adopt this strategy of repeating rounds. During this thesis, we work with two of them: the Substitution-Permutation Networks and the Feistel constructions.

Substitution-Permutation Network (SPN).

The Substitution-Permutation network is maybe the most well known iterative construction of block cipher from its use in the AES proposal by Daeman and Rijmen [START_REF] Daemen | AES proposal: Rijndael[END_REF] and consists in applying a substitution layer followed by a permutation layer to the internal state. There is no well known method for

Introduction Optional Expansion Algorithm k s 0 f s 1 . . . f s r s r+1 k 0 k 1 k r-1 k r Figure 8 -Iterative construction of a block cipher from [Jea16]
finding a good substitution for a state of 64 or 128 bits. As a result, the strategy adopted is to split the state in smaller cells of 4, 8 bits and applied in parallel to each of them a good substitution called a S-box. The permutation layer is the linear layer that will shuffle the bits of each cell in the state between different S-boxes for the next iteration. Two different shuffles are used in the literature: the first consists in a cell shuffle where the position of the cell will be permuted and a linear operation is applied to a set of cells to internally shuffle the bits presented in them. This is the solution adopted in AES and SKINNY [START_REF] Beierle | The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS[END_REF]. The second shuffle possible for a SPN is a direct shuffle of the bits of the internal state which sends some bits going from a S-box to another S-box in the next round like the block ciphers PRESENT [START_REF] Bogdanov | PRESENT: An ultra-lightweight block cipher[END_REF] or Gift [START_REF] Banik | GIFT: a small present[END_REF]. An illustration of a bit-wise toy cipher is given in Figure 9.

Feistel constructions. The Feistel construction is the other generic construction of iterated block ciphers we encounter during this thesis. In the most basic Feistel construction, the message is split in two halves sometimes called branches. The right branch goes through a keyed function F and is xored to the left branch then the two branches are swapped. This keyed function is generally obtained by using a layer S-boxes followed by a xor with a round key. From this basic construction, multiple generalizations were proposed and one in particular is studied further in Chapter 2 for one of the works of this thesis.

I.ii Stream cipher

Apart from block ciphers, the other generic ciphers in symmetric cryptography are the stream ciphers. Whereas block ciphers imitate the one time pad from a permutation

f 1 f 2 f 3 L 0 R 0 L 3 R 3
Figure 10 -3 rounds of the basic Feistel construction from [START_REF] Jean | TikZ for Cryptographers[END_REF] where the f 1 , f 2 , f 3 are obtained with the function F with respectively the first round key, the second and the third.

point of view, the stream cipher imitates it from its structure. More precisely, the key of a stream cipher is used to generate an arbitrary long sequence of bits called the keystream which will play the role of the secret key in an one time pad construction (see Figure 11). As a result, confidentiality for a stream cipher is ensured either by the difficulty from

Introduction key, IV Stream cipher 0 1 = 1 1 1 = 0 • • • • • • 0 ⊕ 0 = 0 message ciphertext Figure 11 -Generic stream cipher
retrieving the key from the keystream sequence or by retrieving the internal state from the keystream.

In practice, the keystream is generated as needed as bit (or byte or other given quantity...) of the message need to be encrypted. When a new keystream bit is generated, the stream cipher is said to be clocked one time.

Linear Feedback Shift Register (LFSR).

If the S-boxes and permutations were the basic building blocks for the SPN, the most basic object that composed stream ciphers are Linear Feedback Shift Registers. A LFSR can be seen as a rolling register containing a finite number of bits in each of its cell. At each clocking, a fix linear combination of some cells of the register called the feedback function is applied to the register to compute a new cell x. Then, the register is shifted discarding the last value of the register and freeing the first cell of the register which will take the value x. An example of a general LFSR is given in Figure 12.

S (t) -1 S (t) -2 S (t) 1 S (t) 0 c 1 c 2 . . . . . . . . . . . . . . . . . . c -1 c Figure 12 -General LFSR from [Jea16]
Non-linearization. LFSRs are quite practical to use for constructing stream cipher with the clocking of the LFSR extending well to the clocking of the stream cipher. However, since their operations are linear only the diffusion of the information exists if used alone and as a result, the system can easily be inverted. Two strategies were adopted to add confusion to the system and preventing an easy inversion: adding a non-linear function to a feedback function of a LFSR like Trivium [START_REF] De | Trivium[END_REF] or Grain [START_REF] Hell | Grain: a stream cipher for constrained environments[END_REF]. The other solution is to change the clocking mechanism of multiple LFSRs to be a non-linear function of the state of the registers like in A5/1 [START_REF] Briceno | A pedagogical implementation of A5/1[END_REF] or MICKEY [START_REF] Babbage | The MICKEY stream ciphers[END_REF].

I.iii Modes of operation

A mode of operation takes a primitive and uses it in a bigger construction to obtain a bigger cipher that can have more properties. The first use of mode of operation for block ciphers is to encrypt messages of greater size than the block. The most basic mode of operation for block ciphers is the Electronic CodeBook (ECB) consisting in splitting the message in blocks of the size considered by the block cipher. Each block is then encrypted with the same key through the block cipher and the resulting ciphertext are concatenated to obtain the whole ciphertext. Unfortunately, while being quite simple it does not offer security against multiple attacks like to name only this one tempering: switching the position of two ciphertext blocks creates a valid ciphertext.

In most uses nowadays, only confidentiality is not enough and authenticity is added with the mode of operation unlike integrity which is ensured with other methods that developed as an independent research topic from cryptography. The lightweight symmetric cryptographic competition of the NIST asked for AEAD primitives for this reason. Ciphers (with their mode of operation) which give authenticity in addition to confidentiality are called authenticated encryption (AE) or if a further public associated data is given, authenticated encryption with associated data (AEAD).

In general, a proof of the security or regarding other properties is given when a new mode of operation is published. Those proofs of security suppose that the primitives pasted in their modes have good properties regarding their securities. In the next section of this introduction, we revisit the necessary notions to understand the security of the primitives.

Introduction

II Analysis and Security of symmetric ciphers II.i Model of security

To understand the security of a symmetric cipher it is important to define the power of an attacker. Trivially, an attacker could ask for the key directly to one of the participants but obtaining it this way is not considered a break of the primitive.

In practice, the power given to the attacker is modeled as its capacity to query encryption or decryption requests to an oracle. An oracle can be understood as a black box that contains a random key for the targeted cipher and answers requests corresponding to the encryption or decryption of given or known messages or ciphertexts. The goal of the attacker is to retrieve the key using only the authorized queries of the oracle.

In the literature, there are multiple levels of oracle with varying types of queries that give varying security. The weakest oracle (with respect to the power of the attacker) consists in being able for the attacker to ask for ciphertexts selected by the oracle without knowing the corresponding plaintexts. This model is called the known ciphertexts oracle and is such a basic requirement for the security that it is most of the time skipped in favor of more powerful attacker models. The power of the attacker is increased with in order giving access to known plaintext ciphertext pairs, choosing arbitrary plaintexts to encrypt and finally choosing in addition arbitrary ciphertext to decrypt. Those models are called in order the known plaintexts, chosen plaintexts and chosen ciphertexts models.

In the literature, after defining the power of the attacker, the other necessary parameter needed to understand security are to define and quantify the goal and success of the attacker. The attacker will play a game where it can query the oracle (in function of the model) and try to win the game by finding the goal like the key. An attack can be understood as a strategy in this game for the attacker such that its probability of winning is greater by a polynomial term (in the security parameter) than a random selection of the answer.

One of the basic game of this type in the literature consists at the beginning of the game to have the oracle chooses secretly between two modes: a first corresponding to what was described previously and a second where the oracle answer to query with random strings (of the good form). The goal of the attacker is to find which of these cases is running for the oracle. When no attacker can win with a good advantage, the cipher is said to be indistinguishable and with the previous model for the power of the attacker, it is defined for example as IND-CCA.

In symmetric cryptography, such proofs of security are rarely done for primitives and their security is conceptualized from a practical point of view: no known practical attacks exist against them. Security can then be understood as a continuous effort in breaking primitives with classical or sometimes new techniques. When studied, cryptographers don't search first for attacks against ciphers but for a smaller component that exists in most attacks called a distinguisher that is used to build a general attack scheme.

II.ii Distinguishers

A distinguisher is an algorithm that breaks (with a good advantage) the indistinguishibility property of ciphers with only access to plaintexts ciphertexts pairs by deciding if the pairs are randomly generated or generated from a cipher. Distinguishers are mostly searched by observing ciphers and finding behaviors that should not exist in random functions.

For iterative constructions, a general extension of distinguishers over r -1 rounds into an attack over r rounds is well known in the community and explains why the last step (to obtain the attack) is rarely detailed in research papers. Indeed, if you assume that the last roundkey is smaller than the master key, an attacker can ask for a set of ciphertexts (over r rounds) and can guess the last roundkey. Using the guessed roundkey for a one round decryption, the distinguisher can be tested on the obtained partially decrypted set with the idea that if the roundkey is incorrect, the distinguisher should consider the set as originating from randomness. This process can be repeated (with one less round) up to the point where enough roundkeys have been found to retrieve the master key. By extension, a good justification used by the designers of primitives for the security of their constructions is to argue that no classical methods like linear or differential cryptanalysis produced a good distinguisher. In the following subsection, we introduce differential cryptanalysis, the principal theory we used to realized the different works of this thesis.

II.iii Differential cryptanalysis

At CRYPTO'90, Biham and Shamir [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF] presented an analysis of the Data Encryption Standard, the encryption standard of the standardization organism of the USA. In the same period, differential attacks were mounted against other block ciphers like FEAL [START_REF] Biham | Differential Cryptanalysis of Feal and N-Hash[END_REF] to obtain new attacks. In 1998, Vaudenay et al. proposed a new framework called the decorrelation theory to prevent differential attacks (among others) applied for the first time in the ciphers COCONUT and PEANUT [START_REF] Vaudenay | Provable security for block ciphers by decorrelation[END_REF]. The next year, Wagner in Introduction [START_REF] Wagner | The boomerang attack[END_REF] proved that decorrelation theory is not enough to ensure security against differential attacks by exhibiting a new type of differential attack, the boomerang attack [START_REF] Wagner | The boomerang attack[END_REF].Since then new variants of differential attacks appeared in the literature like the sandwich [START_REF] Orr Dunkelman | A practical-time relatedkey attack on the KASUMI cryptosystem used in GSM and 3G telephony[END_REF], rectangle [START_REF] Biham | The rectangle attack-rectangling the Serpent[END_REF] or impossible differential [START_REF] Knudsen | DEAL-a 128-bit block cipher[END_REF] attacks. Differential cryptanalysis is now a classical way to study ciphers and new primitives to be seriously considered must have been analyzed against the classical differential attacks.

Differential cryptanalysis studies the transformation of differences through a cipher. Given a pair of messages p 0 and p 1 , the difference ∆p between the two messages is ∆p = p 0 ⊕ p 1 . Trivially, a difference is easily propagated through a linear transformation L since L(∆p) = L(p 0 ) ⊕ L(p 1 ). However, the same cannot be said about the passage through the non-linear operations where this equation becomes false. To describe the multiple outputs that can be obtained after a non-linear operation, the community talks about the probability of observing an output difference for a given input difference computed by counting the number of input pairs p 0 and p 0 + ∆p that reached the targeted output difference. In addition to differences in the message/state, more powerful attackers who can add (or know) differences in the key are sometimes considered for iterative constructions. If the cipher behaves like a random function regarding differential analysis then the probability to observe a particular output difference should be 2 -n where n is the size of the message. If it is not the case, we just described a particular distinguisher against this cipher allowing us to mount an attack. Doing a complete differential analysis of primitives is hard and to simplify this studies for different primitives multiple sub-problems have been proposed in the literature. For iterative block ciphers, the difference can be followed through each round to obtain a differential characteristics. A differential characteristic can be described as the sequence (∆ 0 , ∆ 1 , . . . , ∆ r ) of differences at the beginning of each round and the output difference. The exact probability of a differential characteristic is hard to compute but can be decently (most of the time) approximated by considering that the transition of each round is independent from the others. In this case, the probability of the differential is

r i=1 P(∆ i-1 , ∆ i )
where P(∆ i-1 , ∆ i ) is the probability that difference ∆ i-1 becomes difference ∆ i through the round function. Computing differential characteristics can also be simplify be leveraging the structure of the round function essentially for SPN constructions. Indeed, as said previously, the linear layer and the key addition are layers where the differences will deterministically propagate with probability 1. It leaves only the substitution layer to take into consideration to compute the probability through the round. Or the substitu-tion layer is composed of parallel applications of the S-box which can then be the size considered for the study of the difference in the round. Since S-boxes are usually far smaller than block sizes, the exact probability for every pair (∆ in , ∆ out ) can be computed and the information can be regrouped in a table called the differential distribution table (DDT). The DDT is a double entry table which gives for entry (∆ in , ∆ out ) the probability of observing ∆ out = S(x) ⊕ S(x ⊕ ∆ in ) over every possible value of x.

To simplify further the task of finding differential characteristics in SPN, Knudsen [START_REF] Lars R Knudsen | Truncated differentials and Skipjack[END_REF] proposed to ignore the precise value of the differences to only keep the presence (active) or absence (inactive) of differences for S-boxes at a given round. The term adopted by the community for this object is truncated differential characteristic. They show themselves to be very useful for a design perspective and more precisely to argue in favor of the resistance of new designs against differential cryptanalysis. More precisely, consider a truncated differential characteristic with n active S-boxes and the propagation with the best probability p for the S-box, an easy upper bound on the probability of differential characteristics following this truncated form is then p n . The same reasoning can be done for the truncated differential characteristics with the minimum number of active S-boxes to obtain an upper bound on the probability of differential characteristics on a given number of rounds. If this upper bound is lower than 2 -m where m is the block size, the cipher should be at first sight resistant against differential cryptanalysis. In the last decade (since 2009 to be exact), new methods based on solvers were presented to find truncated differential characteristics [SNC09; MP13; Mou+12; Sun+14; KLT15]. Solvers are algorithms taking as input a description of a problem and searching automatically a solution to this problem. In this thesis, we also use solvers to compute differential characteristics. More details concerning this part of our work can be found in Chapter 3.

III Overview of the manuscript

Introduction

Grain v1 [START_REF] Zhang | Fast Near Collision Attack on the Grain v1 Stream Cipher[END_REF] and A5/1 in [START_REF] Zhang | Cryptanalysis of GSM Encryption in 2G/3G Networks Without Rainbow Tables[END_REF] yielding a new key recovery attack against Grain v1 and a new attack against A5/1 that should be faster than the state of the art up to their publications. However, we found incoherences in the attack and proposed a correct version of the FNCA that proves the attack is not useful.

In Chapter 2, we solve a 10-year old open problem and give new results concerning Generalized Feistel networks. We especially studied a particular property called the diffusion round concerning the permutation of Generalized Feistel networks.

Finally, in Chapter 3, we studied the differential characteristics of the block cipher SKINNY. We used the very classical approach of splitting the search of differential characteristics in two parts. By using this classical approach with carefully selected tools we were able to find new best and good differential characteristics for SKINNY.

III.i Revisiting Fast Near Collision Attacks (FNCA)

In 2018, Zhang et al. in [START_REF] Zhang | Fast Near Collision Attack on the Grain v1 Stream Cipher[END_REF] proposed a new general attack, the Fast Near Collision Attack, and gave as a first application an attack the stream cipher Grain v1. Then, in [START_REF] Zhang | Cryptanalysis of GSM Encryption in 2G/3G Networks Without Rainbow Tables[END_REF] Zhang et al. applied successfully the FNCA to A5/1 to obtain a better key recovery attack against this primitive. The FNCA is a divide-and-conquer attack to retrieve the internal state of a stream cipher from the keystream. It splits the internal state in two parts the crucial part (CP) and the rest part (RP). Once the crucial part is known, the rest part can efficiently be recovered. The crucial part is retrieved with a near collision attack based on a small sample of the keystream.

During the PhD, we tried to implement the FNCA against A5/1 and after a careful review of the process, we found incoherences from an information theoretical point of view in the description of the attack and some error in the code that Zhang used to test component of his attack on A5/1. As a result, we reevaluated the complexity of the FNCA and verified experimentally that no bias exists in the two targets that could explain the complexities announced by Zhang et al.. We also give the corrected complexity of the FNCA and prove that Zhang et al. severely underestimated the real cost of their attacks.

Introduction

III.ii Efficient Search for Optimal Diffusion Layers of Generalized Feistel Networks

Feistels are one of the most classical way to construct block ciphers. At CRYPTO'89, Zheng et al. [START_REF] Zheng | On the construction of block ciphers provably secure and not relying on any unproved hypotheses[END_REF] proposed different generalizations of the basic Feistel construction. One of them consists in applying in parallel multiple Feistel constructions then shifting all branches to the right. As remarks in [Nyb96; SM10], the shift to the right is not the only permutation that can be used. They named the construction with an arbitrary permutation as Generalized Feistel Networks.

However, no family of permutations to use for a better scheme was given. In 2010 at FSE, Suzumaki and Minematsu [START_REF] Suzaki | Improving the generalized Feistel[END_REF] proposed one criteria, the diffusion round, which can help for the choice of a particular permutation. The diffusion round of a permutation can be understood as a measure of the speed necessary in number of rounds for a difference on any branches to diffuse to every branches of the Feistel construction. In their work, Suzumaki and Minematsu were able to exhaust and evaluate every permutations for up to 16 branches to find all optimal permutations. Furthermore, after remarking that for every number of branches they studied, there was always an optimal even-odd permutation, defined as a permutation that transforms even numbers in odd numbers and the converse. As a result, they proposed a generic construction to find a good even-odd permutation when the number of branches is a power of two. In particular, they found a good evenodd permutation for 32 branches with a diffusion round of 10. In 2019, Cauchois et al. [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF] presented a new method to construct optimal even-odd permutations allowing them to find them up to 26 branches.

During this PhD, we studied the problem of finding optimal permutations for GFN. We presented a new characterization of the diffusion round and we used it in an efficient algorithm searching for optimal even-odd permutation with a diffusion round of 9 for GFN of 28 to 42 branches. As such, we were able to find all optimal even-odd permutations for 28, 30, 32, 34 and 36 branches as well as found good candidate permutations for 38, 40 and 42 branches.

III.iii Efficient Methods to Search for Best Differential Characteristics on SKINNY

SKINNY is a family of tweakey SPNs designed in 2016 by Beierle et al. [START_REF] Beierle | The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS[END_REF]. There are six versions grouped in terms of size in two families: SKINNY-64 and SKINNY-128 using respectively blocks of 64 and 128 bits. To give a first idea of its security against differential cryptanalysis, its designer included in its specification [START_REF] Beierle | The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS[END_REF] a model to search for the minimum number of active S-boxes in a truncated differential characteristics. The model is solved by a constraint solver and more precisely a MILP solver. A constraint solver is a generic algorithm that takes in input a description of a problem, containing variables and relations between them and searches a solution of this problem. In MILP, the variables' values are numbers and the constraint are linear inequalities between those variables.

Since then few results were published concerning the differential characteristics of SKINNY. To the best of our knowledge, only two papers present results on them: Liu et al. in [START_REF] Liu | Security Analysis of SKINNY under Related-Tweakey Settings (Long Paper)[END_REF] needed some good differential characteristics to study the resistance of SKINNY against boomerang and rectangle attacks in the tweakey settings. Using a MILP modeling of SKINNY-64 and an ad-hoc tools for SKINNY-128, there were able to find in the different tweakey settings the best differential characteristics up to 13 rounds for SKINNY-64 and some good differential characteristics (but on a small number of rounds) for SKINNY-128.

The second result we found concerning the differential characteristics of SKINNY was published by Abdelkhalek et al. in [START_REF] Abdelkhalek | MILP Modeling for (Large) S-boxes to Optimize Probability of Differential Characteristics[END_REF]. They found the best differential characteristics of SKINNY-128 in the single key settings up to 13 rounds using a MILP model containing an efficient description up to now thought impossible of the 8-bit S-box of SKINNY-128. Moreover, they showed that no differential characteristic with a better probability than 2 -128 exist for 14 rounds (and more) in the single key setting.

We complete the knowledge concerning the differential characteristics of SKINNY. In this work, we adopted a very classical approach of splitting the search in two steps. The Step 1 consists in searching truncated differential characteristics and the Step 2 consists in instantiating in value the solutions found in the first step. The contributions of this work other than the new results are the way the two steps are solved. We proposed a new tool to complete the Step 1 search based on dynamic programming. For the Step 2 process, we used a constraint programming solver, another type of constraint solver that allows more types of constraints than the MILP and obtained a faster resolution of the Step 2 process than the MILP modeling of [START_REF] Abdelkhalek | MILP Modeling for (Large) S-boxes to Optimize Probability of Differential Characteristics[END_REF]. In this way, we were able to compute every optimal differential characteristics with a probability greater than 2 -64 in the round reduced version of SKINNY-64. Concerning SKINNY-128, we retrieved the results of [START_REF] Abdelkhalek | MILP Modeling for (Large) S-boxes to Optimize Probability of Differential Characteristics[END_REF] within of few minutes (compared to 16 days) and found new best differential related-tweakey characteristics in the different related-tweakey settings. Furthermore, we found in some of those tweakey settings good differential characteristics on a greater round reduced versions and proved that none could exist for some given numbers of rounds.

REVISITING THE FAST NEAR COLLISION ATTACK

Introduction

Recently, the fast near collision attack (FNCA), a new general attack was applied to both Grain [ZXM18] and A5/1 [Zha19], two stream ciphers. During the PhD to study in more details A5/1, we try to implement completely this new attack against A5/1 but we were not able to do so. Then, we did a review of the attack and found some incoherences in the published results. By extension, we also reviewed the FNCA against Grain and found the same incoherences. As a result, we decided to formally review and checked the results of these two papers using some algorithms containing elements of information theory.

A5/1 was designed in 1987 for the Global System for Mobile Communication (GSM) and became public in 1994 with a leak of the general design before being completely reverse engineer in 1999 by Marc Briceno. Ross Anderson reported a "terrific row between NATO signal intelligence agencies in the mid-1980 over whether GSM encryption should be strong or not". Germany wanted a strong design to protect its communication against possible interception by the Warsaw Pact, the other allies wanted a weaker design. Finally, a French design was adopted. Without surprise, attacks and vulnerabilities were found beginning with Anderson in 1994 [START_REF] Anderson | A5 (was: Hacking digital phones)[END_REF] based on guessing majority of the state. In 1997, Golic [START_REF] Dj | Cryptanalysis of alleged A5 stream cipher[END_REF] proposed an attack with a complexity of 2 41.16 where some guesses on the clock are used to generate a linear system of equations. A more efficient version of Golic attack was proposed by Biryukov et al. [START_REF] Biryukov | Real Time Cryptanalysis of A5/1 on a PC[END_REF] in 2000 with a well adapted time-memory trade-off. In the same year, Biham et Barkan et al. in [BB05] to yield an Chapter 1 -Revisiting the Fast Near Collision Attack attack needing a few minutes. Although multiples vulnerabilities were found, counter measures were adopted in the GSM standard to ensure security. Nevertheless, A5/1 is still an important target of study with its preponderant role in some legacy systems (G2).

Gain v1 is another stream cipher and is part of the eSTREAM portfolio [START_REF] Robshaw | New stream cipher designs: the eS-TREAM finalists[END_REF] with the rest of the Grain stream cipher family. As a more modern stream cipher, a considerable effort to cryptanalyse Grain v1 exists in the literature. Since 2009 and its invention by Dinur et al. in [START_REF] Dinur | Cube attacks on tweakable black box polynomials[END_REF], cube attacks were increasingly successfully applied to Grain to cite only some of those works [DS11; Wan+13; Ban14; Rah+16]. This last cube attack is a key recovery attack on reduced version of Grain v1 where initialization is reduced to 100 rounds with a complexity reduced from the exhaustive search by a 2 32 factors. Other methods of attacks against Grain in the literature are among others an algebraic attack [START_REF] Afzal | Algebraic cryptanalysis of a nlfsr based stream cipher[END_REF], internal state recovery attacks [Mih+12b; Mih+12a] or a near collision attack [START_REF] Zhang | Near collision attack on the grain v1 stream cipher[END_REF]. Nevertheless, the complete Grain is still seen as a secure stream cipher for the numerous keystream bits necessary for the attacks. In this context, the attack proposed by Zhang et al. in [START_REF] Zhang | Fast Near Collision Attack on the Grain v1 Stream Cipher[END_REF] that we revisit in this Chapter is even more impressive as an efficient key recovery attack on the whole scheme.

Checking results is in some sciences such as experimental physics as important as the result itself. In these research domains, results have to be validated by two separate and independent teams before being published. In some computer sciences areas where results can depend on the input data set, it is also highly important to give access to these data and to the code. In data mining for example the reproducibility of results has been acknowledged as mandatory before publishing work in order to ease the checking and/or comparison of this work with further research works.

In symmetric cryptography, where usually the complexities of attacks and distinguishers can be out of reach with experiments, a well-known method consists in experimentally checking only some parts of the attack and/or by targeting a toy cipher. Indeed attacks can usually be split in two parts: the adversary has to guess some bits and then he evaluates some distinguishers. The evaluation of the distinguisher cannot be exhaustive since it would have been tested for all guess bits. If we checked that the distinguisher is working for random guess, we declare that the attack is validated. However, it is the authors' accountability to check carefully the experiments and reviewers usually verified the fact that the authors seem to have correctly performed their results. Nevertheless, sometimes it is not sufficient to ensure the correctness of some proposed attacks and it is up to the community to revisit and discuss previous works to offer new insights on their contribu-1.1. Introduction tions. For instance in [START_REF] Granboulan | Flaws in differential cryptanalysis of Skipjack[END_REF] Granboulan showed that differential attacks on SKIPJACK proposed in [START_REF] Lars R Knudsen | Truncated differentials and Skipjack[END_REF] were flawed because the probabilities of some differential characteristics were not correctly evaluated. In 2007, Wang, Keller and Dunkelman [WKD07] caught a similar error for an impossible differential used in several attacks on SHACAL-1. Such errors may also come from hypothesis which do not hold for all ciphers as exemplified by Murphy [START_REF] Murphy | The return of the cryptographic boomerang[END_REF] with boomerangs on both DES and AES.

Symmetric cryptography is not the only place where mistakes can be made. In publickey cryptography and provable cryptography, it is also possible to discover errors as the famous bug in the OAEP paper [START_REF] Bellare | Optimal Asymmetric Encryption[END_REF], which has been corrected in [START_REF] Shoup | OAEP Reconsidered[END_REF][START_REF] Fujisaki | RSA-OAEP Is Secure under the RSA Assumption[END_REF]. The same kind of problems appeared in proofs in symmetric cryptography for the equivalence between the random oracle model and ideal cipher model [START_REF] Coron | The Random Oracle Model and the Ideal Cipher Model Are Equivalent[END_REF] corrected in [START_REF] Holenstein | The equivalence of the random oracle model and the ideal cipher model, revisited[END_REF] and more recently in the security proof of the OCB-2 mode of operation [START_REF] Inoue | Cryptanalysis of OCB2: Attacks on Authenticity and Confidentiality[END_REF]. Consequently, Barthe et al. have developed tools to verify these proofs as in [Bar+11b; Bar+11a] and even on the corrected proofs they have been able to spot some errors or imprecisions since these tools do not accept unclear arguments or logical flaws. As a consequence, they design the EasyCrypt tool to help the verification of cryptographic proofs to reason about code-based proofs as these tools were first developed to verify programs. There is no such tool to check symmetric-key cryptanalysis. The verification of these attacks boils down to checking the complexity analysis of the cryptanalytic algorithm. The main difficulty is that some parts are heuristic and the verification of these heuristics are not easy to automatize and to perform rigorously. Moreover, understanding the problems is not always an easy task since it requires to reverse engineer the experiments performed which are subject to statistical effects and it is less easy than reading a proof.

Contributions.

In this Chapter, we look at the recent fast near collision attacks proposed by Zhang, Xu and Meier against the Grain v1 [ZXM18] stream cipher and by Zhang against A5/1 [Zha19]. The main idea behind fast near collision attack consists in a divideand-conquer partition of the full internal state into the crucial part (CP) and the rest part (RP). The latter part can be efficiently recovered using only the CP, while the former one is retrieved using a near collision attack based on a small number of bits of the keystream.

Our first goal was to implement the attack on the A5/1 stream cipher since the time and memory complexities seem within our reach and practical. However, during this process we discovered several issues in the claimed probabilities, leading to an overall complexity much worst than expected. In fact, we came up to implement a slower version of the attack proposed by Golić at Eurocrypt'97 [START_REF] Dj | Cryptanalysis of alleged A5 stream cipher[END_REF]. Consequently, we scrutinized Chapter 1 -Revisiting the Fast Near Collision Attack this article and decided to reevaluate the time complexity to 2 28 calls to (the end of) Golić's attack, for an overall complexity around 2 42 . Since this attack is a bit difficult as it is flooded with the details of the stream cipher under attack, we decided to present its basic ideas in a self-contained manner. The details can be found in Section 1.3. Finally, we decided to also verify the previous attack on Grain v1 as proposed at Eurocrypt'18 and we discovered similar problems in the analysis. In particular, the correct overall complexity is 2 113 and so the attack is less efficient than the naive exhaustive search in 2 87.4 ticks on Grain v1. The complete analysis is presented in Section 1.4.

More importantly, we show in Section 1.2 that fast near collision attacks, as described in both [START_REF] Zhang | Fast Near Collision Attack on the Grain v1 Stream Cipher[END_REF] and [START_REF] Zhang | Cryptanalysis of GSM Encryption in 2G/3G Networks Without Rainbow Tables[END_REF], are intrinsically erroneous. Replacing the refined selfcontained method, which is the core of those attacks and the only algorithm relying on near collisions, by an algorithm outputting a random set (of fixed size) of pre-images would lead to the exact same complexities. Thus such attacks are illusive.

Fast Near Collision

At Eurocrypt'18, Zhang et al. described a new powerful cryptanalysis technique called fast near collision attack. This technique was specially designed to analyze stream ciphers and was successfully applied to both Grain v1 [START_REF] Hell | A Stream Cipher Proposal: Grain-128[END_REF] and A5/1 [START_REF] Briceno | A pedagogical implementation of A5/1[END_REF]. It combines both a divide-and-conquer approach and near collisions. The core idea is to use near collisions to restrict the possible values of some bits of the internal state.

The refined self-contained method

Let f be a public function from n to m bits, x s be a secret n-bit word and k s the output of f (x s ). A classical objective is to retrieve x s from the knowledge of both f and k s . In the following we will explain how the fast near collision technique claims to restrict the search space for x s .

The process is composed of 3 procedures which aim at computing a set X containing x s with a high enough probability.

Precomputation. The first step in a fast near collision attack is to construct a differential table T d mapping each pair (∆k, k) to all possible ∆x such that:

• |∆x| ≤ d • there exists x such that f (x) = k and f (x ⊕ ∆x) = k ⊕ ∆k.
In other words, the table T d is a variant of the classical differential distribution table associated to an S-box. The number of times ∆x is solution for (∆k, k) is also stored as extra information. This allows for each value of k to select ∆k to maximize the probability of f

(x ⊕ ∆x) = k ⊕ ∆k knowing both f (x) = k and ∆x ∈ T d [∆k, k].
Note that in case it would be too costly to fully compute T d , x and ∆x can be sampled.

Online. The second step of the procedure uses the precomputed table to generate a set X containing x s with a good probability. The process is described in Algorithm 1. The idea is to randomly generate

x, compute k = f (x), look into T d [k ⊕ k s , k s ]
for possible ∆x's and check whether f (x ⊕ ∆x) = k s . If the last equality holds then x ⊕ ∆x is added to the set X as a possible value for x s .

Algorithm 1 The refined self-contained method

1: Data: keystream k s , difference ∆k, table T d , 2: Result: a set X such that x s ∈ X has high probability 3: X ← ∅ 4: for i = 0 to N do 5:
randomly generate x such that f (x) = k s ⊕ ∆k 6:

for all ∆x ∈ T d [∆k, k s ] do 7: if f (x ⊕ ∆x) = k s then 8: X ← X ∪ {x ⊕ ∆x} 9:
end if 10:

end for 11: end for 12: return X Amplifying phase. In order to increase the probability that X contains x s , Zhang et al. propose to run N × M times Algorithm 1 , each random invocation outputting a set denoted X i,j (i = 1 to N and j = 1 to M ). Then a new set is outputted by computing

X = N i=1   M j=1 X i,j   .

About probabilities

While we could discuss on the interest of this construction, we are only interested by the probability that x s belongs to the constructed set X.

Chapter 1 -Revisiting the Fast Near Collision Attack

Grain v1. In [ZXM18], Zhang et al. used the fast near collision technique to mount an attack against Grain v1. They applied the refined self-contained method to a function f such that n = 12 and m = 2. They obtained a set X of size 848 and claimed the probability for x s to belong to X is around 89.64% which is a bit higher than the 848/1024 = 82.81% expected. Note that here the function f is such that z = f (x) can be rewritten as z = x 1 ⊕ h(x 2 ) and thus, the refined self-contained method was applied on h(x 2 ) = 0. In particular this means that the search space is restricted without the knowledge of any bit of keystream.

A5/1. In [START_REF] Zhang | Cryptanalysis of GSM Encryption in 2G/3G Networks Without Rainbow Tables[END_REF], the function f is such that n = 15 and m = 2. Zhang obtained a set X of size 7835 and claimed the probability for x s to belong to X is around 99.09% which is higher than the 7835/8192 = 95.64% expected.

We claim all those claimed probabilities are wrong or, more precisely, cannot be true without a big enough bias in the initialization phases of both A5/1 and Grain v1. This is supported by the following theorem: Theorem 1.1. Let A be an algorithm which takes as input a function f and an element k s and outputs a subset X of f -1 (k s ). Let x s be an element of f -1 (k s ) drawn uniformly at random. The probability that x s belongs to X is exactly

|X|/|f -1 (k s )|.
The refined self-contained method fulfils the requirements of Theorem 1.1 but Zhang et al. claim the set X output by the algorithm contains the secret x s which generated k s with a good probability. Note that the algorithm can be run before the secret was actually generated and thus Zhang et al. claim can be invalidated by the following experiment:

1. randomly generate k s 2. run the refined self-contained method on f and k s and obtain the subset X 3. draw x s uniformly at random in f -1 (k s ) 4. check whether x s belongs to X Hence, the probabilities given in both [START_REF] Zhang | Fast Near Collision Attack on the Grain v1 Stream Cipher[END_REF] and [START_REF] Zhang | Cryptanalysis of GSM Encryption in 2G/3G Networks Without Rainbow Tables[END_REF], and by extension the complexity of corresponding attacks, are quite suspicious. Actually, they would hold if and only if it is not possible to draw x s uniformly at random in f -1 (k s ) which would imply bias in the initialization process.

Fast Near Collision

Several issues

We found several issues and unreproducible results in both [START_REF] Zhang | Fast Near Collision Attack on the Grain v1 Stream Cipher[END_REF] and [START_REF] Zhang | Cryptanalysis of GSM Encryption in 2G/3G Networks Without Rainbow Tables[END_REF]. The first and most important one is about the set outputted by Algorithm 1 and, more precisely, about its average size and the average probability for the right value to belong to this set. For both Grain v1 and A5/1, they were obtained experimentally from unspecified procedures and do not satisfy Theorem 1.1. Since Zhang et al. state to have conducted extensive experiments, either the whole experiments were flawed or the pseudo-random generators they used were biased.

Another issue lies in the amplifying phase. First the computations are all based on the wrong results regarding Algorithm 1 and so are unlikely to be correct. But there is another issue with this phase. Authors used two independent theorems to exhibit the claimed special behavior of the set X constructed in the amplifying phase: one to compute the size of X and one to compute the probability for the right value to belong to X. While using two different avenues to prove two properties on the same set is not important in regards to the truth of the statement, the theorem they used to compute the size of X (Statement 1.1 in this chapter) is flawed. As a consequence, there is a decorrelation between the computation of the probability that X contains the correct value and the computation of the size X, explaining again the incorrect complexities they found for their attacks.

Statement 1.1 (Theorem 3 of [START_REF] Zhang | Fast Near Collision Attack on the Grain v1 Stream Cipher[END_REF]). Let V be a set and let draw uniformly at random a collection (U i ) of subsets of V . Let F i = k≤i U k . Then on average the following relation holds:

|F i+1 | = |F i | + |U i+1 | - |U i+1 | j=0 |F i | j • |F i+1 |-|F i | |U i+1 |-j |F i+1 | |U i+1 | • j
The sum in the formula is expected to compute the average size of the intersection between both the sets F i and U i+1 and this is where the error lies. The main idea is correct as they count the number of configurations such that j elements of U i+1 belong to F i and |U i+1 | -j elements do not. But actually, at this point, not in F i does not mean in F i+1 -F i but means in V -F i . Indeed, U i+1 is drawn as a subset of V not as a subset of F i+1 . Hence the corrected version of the Statement 1.1 is proposed in Theorem 1.2.

|F i+1 | = |F i | + |U i+1 | - |U i+1 | j=0 |F i | j • |V |-|F i | |U i+1 |-j |V | |U i+1 | • j
In particular, the formula used by Zhang et al. would always underestimate the average size of set F i . This fully supports our claiming: to reach the probabilities announced in both [START_REF] Zhang | Fast Near Collision Attack on the Grain v1 Stream Cipher[END_REF] and [START_REF] Zhang | Cryptanalysis of GSM Encryption in 2G/3G Networks Without Rainbow Tables[END_REF] the size of the set output by the refined self-contained method has to be bigger than they expected.

Finally there is a wrong assumption about the right value. More precisely, in both papers authors assume there is only one right value that will behave differently than the wrong ones. With enough keystream bits this is true that there is only one internal state solution. But the fast near collision only uses a small part of the known keystream bits and so the assumption of only one right value does not hold. For instance, for the attack against A5/1, the fast near collision technique is applied to only 5 keystream bits and we show Section 1.3.3 there are many more right values than only one.

In the next sections, we will show for both Grain v1 and A5/1, the observed deviation in the probabilities is wrong and will give the corrected complexities of the corresponding attacks.

Fast Near Collision on A5/1

In this Section we carefully study the attack presented in [START_REF] Zhang | Cryptanalysis of GSM Encryption in 2G/3G Networks Without Rainbow Tables[END_REF] on the A5/1 stream cipher. This attack is absed on a divide and conquer partition of the internal state. The first part of the internal state called the crucial part (CP) is The second part of the internal state called the rest part (RP) is obtained by leveraging the knowledge of the CP and the keystream with the attack proposed by Golić in [START_REF] Dj | Cryptanalysis of alleged A5 stream cipher[END_REF]. To be as complete as possible, we begin with recalling the design of A5/1 and Golić attack. Then, we describe Zhang used of fnca on A5/1 and explain why its complexity was underestimated.

Description of A5/1

A5/1 is a stream cipher underlined by a 64-bit internal state. The internal state is composed of three short linear feedback shift registers (LFSR) of length 19, 22 and 23 bits respectively. In the rest of the chapter we will refer to them as R1, R2, R3. As illustrated

Fast Near Collision on A5/1

in Figure 1.1, the feedback taps for each LFSR are positions 13, 16, 17 and 18 for R1, 20 and 21 for R2 and 7, 20, 21 and 22 for R3. Furthermore, each LFSR also possesses a clocking tap at position 8, 10, 10 for respectively R1, R2 and R3, represented with the red arrows in the figure. Figure 1.1 -Description of A5/1 (source: [START_REF] Jean | TikZ for Cryptographers[END_REF]). The 33 blue bits are the one required to compute the first 5 keystream bits.

A5/1 uses an asynchroneous clocking regime for the LFSRs: at each clock tick, a LFSR is clocked if its clock tap value is the majority value between the three clocking taps (refer to Table 1.1 for the plain list of the clocking). clock value of R1 0 0 0 0 1 1 1 1 R2 0 0 1 1 0 0 1 1 R3 0 1 0 1 0 1 0 1

register clocked R1 - - R2 - - R3 - - Table 1.1 -Clocking of A5/1
Finally, we review the utilisation of the A5/1 stream cipher during a GSM conversation session with Algorithm 2, the pseudo code for the generation of the 228 bits of keystream of one GSM session.

An attack from Golić

In [START_REF] Dj | Cryptanalysis of alleged A5 stream cipher[END_REF], Golić introduces a clever memory-less attack against A5/1. It is a basic divideand-conquer attack recovering the unknown initial state from a known keystream sequence (of 64 bits). Called the initial state S 0 and defined the sequence of internal states after n Chapter 1 -Revisiting the Fast Near Collision Attack Algorithm 2 The procedure used during a GSM session to generate 128 bits of keystream 1: P = (F, K) = (P 85 , . . . , P 0 ) an 86-bit word composed of a 64-bit key K and a 22-bit frame F 2: for i = 0 to 85 do Loading Parameters 3:

R1[0], R2[0], R3[0] ← R1[0] ⊕ P i , R2[0] ⊕ P i , R3[0] ⊕ P i 4:
clock R1, R2, R3 simultaneously 5: end for 6: for i = 0 to 99 do Initialization

z i = R1[18] ⊕ R2[21] ⊕ R3[22] 11:
clock R1, R2, R3 asynchronously 12: end for 13: Output z = (z 227 , . . . , z 0 ) the keystream clocking as S nn . In his attack, Golic reconstructs the internal state S 101 from the known keystream than uses it to determine S 0 .

First, the main idea to recover S 101 is quite simple: it is an elimination of the nonlinear operations by guessing the clock bits. Remarks that in his paper, Golic proved that only 5 • 2 61 ≈ 2 63.32 states S 101 were reachable from the inital state S 0 . In the following, we will search S 101 in this set of reachable states.

If, for each of the three LFSRs, one guesses the clock bit for n (asynchronous) clocks of the LFSRs, we can obtain 3n linear/affine equations. For instance, for n = 10 it means guessing on the initial state R1[0..8], R2[1..10], R3[1..10] as well as [18]. In this exemple, the equations obtained for the first register when guessed values are called g 1,i , i ∈ [0..9] are:

R1[13] ⊕ R1[16] ⊕ R1[17] ⊕ R1
∀i ∈ [0..8], R1[i] = g 1,i R1[13] ⊕ R1[16] ⊕ R1[17] ⊕ R1[18] = g 1,9
Furthermore, from those 3n guesses we know the beginning of the clocking sequence and obtains on average 1+4n/3 affine equations from the knowledge of the keystream bits

Fast Near Collision on A5/1

(the first keystream bit is computed before clocking with the guessed sequence). Indeed, at each step the probability for a register to be clocked is 3/4 (see Table 1.1) and as a consequence from the 3n guesses we know on average the clocking sequence for 4n/3 rounds, leading to the equations R1 i [18] ⊕ R2 i [21] ⊕ R3 i [22] = z i for 0 ≤ i ≤ 4n/3. Note that trivially these 1 + 4n/3 equations are linearly independent: each one has at least two new variables appearing from the minimum two registers that are clocked while n ≤ 18. They also are linearly independent of the first 3n equations if each of them contains at least one bit that was not guessed. This happen with high probability given that n ≤ 10. For now, we will consider that the 1 + 4n/3 equations are linearly independent of the 3n first. Hence, a naive solution would be to accumulate enough equations to solve the system by inverting a matrix. This would require n to be such that 1 + 4n/3 + 3n ≥ 63.32, so n ≥ 14.38 (respecting effectively the condition for the 1 + 4n/3 equations to be linearly independent). But actually, for n > 10, the equations are not linearly independent, and we need to increase the number of guesses to make.

To overcome this issue, Golić proposed a better algorithm close to the early abort technique [START_REF] Lu | Improving the Efficiency of Impossible Differential Cryptanalysis of Reduced Camellia and MISTY1[END_REF]. The basic idea he proposed was to used redundant equation as a consistency tool. First, one uses the method previously described with n = 10 to obtain 1 + 3n + 4n/3 ≈ 44.3 linearly independent equations on average. Than instead of guessing the remaining m ≈ (63.32-44.3) 3 missing bits in each LFSR, Golic proposed that at each step the adversary guesses/computes the majority bit, gets the corresponding equation from the corresponding keystream bit and checks whether it is consistent with the previously obtained equations. If the equation is consistent, the equation is added to the system, the missing clocking bits are guessed/computed from the majority bit and the already known clocking bits and the whole state is clocked. This process is repeated until the system uniquely determines the 64-bit state. Golić showed that the average complexity of the procedure is around 2 41.16 simple operations.

In his paper, Golic also presents a way to reconstruct the key and the frame number from the inital state S 0 . In this sense, the attack proposed by Golic in [START_REF] Dj | Cryptanalysis of alleged A5 stream cipher[END_REF] and by Zhang in [START_REF] Zhang | Cryptanalysis of GSM Encryption in 2G/3G Networks Without Rainbow Tables[END_REF] are key recovery attacks against A5/1.

Fast near collision attack against A5/1

At Asiacrypt'19, Zhang proposed an improved memory-less attack against A5/1, claiming a time complexity around 2 31 clocks [START_REF] Zhang | Cryptanalysis of GSM Encryption in 2G/3G Networks Without Rainbow Tables[END_REF]. Given a sufficiently long sequence of Chapter 1 -Revisiting the Fast Near Collision Attack keystream bits (around 64), he proposed a 2-step procedure to recover the full internal state.

1. The main observation is that 2 consecutive bits of keystream only depend on 15 variables of the internal states. Using the technique described in Section 1.2.1, Zhang constructs a set containing approximately 7835 values for the 15 variables and claims that the probability the value we want is in it to be around 99.09%. Four such sets are constructed, one for each pair (z i , z i+1 ) of keystream bits, for i from 0 to 3. Then a sophisticated merge procedure is applied to construct a set of 2 16.6 values for the 33 bits of the internal state leading to z 0 z 1 z 2 z 3 z 4 . Furthermore, Zhang claims that the probability for the set to contain the right value is round (0.9909) 4 = 96.41%. Note that 2 16.6 possibilities is much lower than 2 33-5 = 2 28 , which is what we would intuitively expect.

2. The 31 remaining state bits are recovered using the procedure of Golić described Section 1.3.2 with few refinements.

Complexity correction

In this section, we show the time complexity of the attack presented by Zhang at Asiacrypt'19 is actually much higher than announced in [START_REF] Zhang | Cryptanalysis of GSM Encryption in 2G/3G Networks Without Rainbow Tables[END_REF]. More precisely, we show it is impossible to restrict the number of possible values for the 33 bits of the crucial part (CP) from 2 33 to 2 16.6 using only the 5 first keystream bits without drastically decreasing the probability of success of the attack. Hence, it turns out Zhang's attack has the same complexity than the one of Golić.

Theoretical analysis. As explained in Section 1.3.3, the attack proposed by Zhang begins by the recovery of the crucial part (CP) corresponding to 33 bits of the internal state of A5/1. Those bits are coloured in blue on Figure 1.1. The only information used in the procedure to do so is the first five bits of keystream generated from the internal state.

Let x be a randomly chosen value for the CP part and k its corresponding 5-bit keystream output. In his attack, Zhang claims that from k he can extract a set of 2 16.6 CP configurations containing x with a very high probability. To invalidate this result we first make the following proposition: .22]) used to generate the keystream bits. Hence, once the 15 bits of the first group are fixed, the clocking sequence is known and so each of the five first keystream bits is computed as a linear combination of the 18 bits of the second groups. Furthermore, those 5 linear equations are independent since each of them depends on at least one bit that does not appear in the other ones (because at least two registers are clocked each round). Thus, for each possible value of k we have exactly 2 18-5 = 2 13 possible values for the 18 bits of the second groups.

According to Proposition 1.1, the claim of Zhang would imply that over the 2 33 possible values of the 33 bits of the CP part, only a subset of 2 16.6+5 = 2 21.6 values (a set of 2 16.6 for each of the 2 5 possible keystream values) can be actually reached after A5/1 initialization, the remaining ones being reached with marginal probability. While it seems quite obvious that such a big bias would have already been observed, we ran several experiments to refute the claim made by Zhang.

Experimental results. We first experimentally verified Proposition 1.1. We count for each of the 2 5 5-bit keystream prefix the number of CP values that generate it. As expected, we found that for 5 given bits of keystream prefix, there are exactly 2 28 CP combinations that generate it.

The second hypothesis we studied was a potential bias in reaching every CP configuration from the initialization phases of a GSM session. To test this hypothesis, we ran two experiments, sampling at random the 33-bit CP part after an A5/1 initialization.

For the first one, we simply drawn uniformly at random 2 36 64-bit keys and 22-bit frame counters. For each of them we performed the initialization process of A5/1 as detailed in Algorithm 2 and computed the corresponding value of the 33 bits of interest. To avoid any bias in the experiment we used AES in CTR mode as source of randomness. For the sake of clarity and to give more details about the random sampling, we give a pseudo-code description of the experiments in Algorithm 3.

The second experiment is exactly the same as the first one but the 64-bit key is composed of 54 random bits and 10 zeroes for its rightmost bits as it was traditionally done in some system, like comp128v2. We present in Figure 1.2 the distribution of occurrences of the 2 33 possible CP values for respectively GSM session key of 54 random bits and 64 random bits and for randomly selected internal states of 64-bit in the form of histograms mapping a value n to the number of CP configurations (in log scale) that are sampled n times.

No bias as strong as the one presented in the complexity announced by Zhang can be observed on those representative histograms.

Finally, we provide a last experiment definitely showing the attack presented in [START_REF] Zhang | Cryptanalysis of GSM Encryption in 2G/3G Networks Without Rainbow Tables[END_REF] is flawed.

1. Randomly generate a 5-bit word k s 2. Run the refined self-contained method to obtain a set X of size 2 16.6 . According to [START_REF] Zhang | Cryptanalysis of GSM Encryption in 2G/3G Networks Without Rainbow Tables[END_REF], this set should contain the secret which generated k s with probability 0.9641.

Do N times:

(a) Randomly generate a key and a frame counter and run the initialization process (b) Check whether the first five keystream bits match k s . If not repeat the previous step.

(c) Check whether the value of the CP part belongs to X. 4. Check whether the experimental probability matches the expected one.

We ran this experiment1 10 times with N = 2 28 and found the experimental probability to be very close to 2 -11.4 , confirming the probability of 0.9641 claimed by Zhang to be far from the reality.

Corrected complexity.

With the probability of success corrected, Zhang's attack becomes very similar to the one of Golić. The difference is that he would guess 18 extra bits while Golić would have 5 linear/affine equations between those 18 bits and the keystream.

Chapter 1 -Revisiting the Fast Near Collision Attack

Hence in Zhang attack one would proceed less keystream bits before obtaining an invertible system of equations and thus more keystream bits should be checked a posteriori, leading to an attack which cannot be better than Golić one.

Fast Near Collision on Grain v1

In this section, we study the attack proposed at Eurocrypt'18 [START_REF] Zhang | Fast Near Collision Attack on the Grain v1 Stream Cipher[END_REF] in the same way we did in the previous section for A5/1.

Description of Grain v1

Grain is a family of stream ciphers that was retained in the eSTREAM portfolio [09]. In this chapter, we focus on Grain v1 as specified in [START_REF] Hell | Grain: a stream cipher for constrained environments[END_REF]. This stream cipher is composed of one LFSR of 80 bits chained with a non-linear feedback shift register (NFSR) of 80 bits. The update function of the LFSR is defined as

s i+80 = s i+62 ⊕ s i+51 ⊕ s i+38 ⊕ s i+23 ⊕ s i+13 ⊕ s i ,
and the one of the NFSR as

b i+80 = s i ⊕ b i+62 ⊕ b i+60 ⊕ b i+52 ⊕ b i+45 ⊕ b i+37 ⊕ b i+33 ⊕ b i+28 ⊕ b i+21 ⊕ b i+14 ⊕ b i+9 ⊕ b i ⊕ b i+63 b i+60 ⊕ b i+37 b i+33 ⊕ b i+15 b i+9 ⊕ b i+60 b i+52 b i+45 ⊕ b i+33 b i+28 b i+21 ⊕ b i+63 b i+45 b i+28 b i+9 ⊕ b i+60 b i+52 b i+37 b i+33 ⊕ b i+63 b i+60 b i+21 b i+15 ⊕ b i+63 b i+60 b i+52 b i+45 b i+37 ⊕ b i+33 b i+28 b i+21 b i+15 b i+9 ⊕ b i+52 b i+45 b i+37 b i+33 b i+28 b i+21 .
At each step, the output bit is computed from 8 bits of the NFSR and 4 bits of the LFSR as

z i = h(s i+3 , s i+25 , s i+46 , s i+64 , b i+63 ) ⊕ k∈A b i+k ,
where h is a boolean function of degree 3 and A = {1, 2, 4, 10, 31, 43, 56}.

The initialization of Grain v1 is described in Algorithm 4. First, the 80-bit key is loaded into the NFSR and the 64-bit IV into the 64 first bits of the LFSR. Remaining bits of the LFSR are set to 1. Then, the internal state is clocked 160 times with a re-injection of the output bits.

Zhang et al. attack

At Eurocrypt'18, Zhang et al. presented a fast near collisions attack against Grain v1, claiming a time complexity around 2 75.7 ticks. Let x i be k∈A b i+k so that z i = x i ⊕ h(s i+3 , s i+25 , s i+46 , s i+64 , b i+63 ). For each 0 ≤ i < j ≤ 19, they applied the refined selfcontained method together with the amplified phase to (z i , z j ) and obtained a subset of the possible pre-images X i,j containing the right value with probability p. As x i can be directly computed from the value keystream bit z i and s i+3 , s i+25 , s i+46 , s i+64 and b i+63 , they did not store x i nor x j in the X i,j . As a result they claim that X i,j contains on average 848 elements (over 2 10 ) and p = 89.64%. The next step of the attack is to merge all those 190 sets to get a set X containing only values leading to the rightful first 20 bits of keystream. They claim that X would contain on average 2 6.67 elements and the probability for the right value of the internal state to be in X would be around p 343 = (0.8964) 343 = 2 -54. 09

Complexity correction

Experimental result on initialization. As for A5/1, we checked whether there are bias in the initialization phase of Grain v1 which could explain the probability given by Zhang et al. in [START_REF] Zhang | Fast Near Collision Attack on the Grain v1 Stream Cipher[END_REF]. We have drawn uniformly at random 2 30 keys and IVs, and for each them ran the initialization phase. We then looked at the 10 bits going through the function h to generate the 2 first keystream bits. As expected, we did not notice any bias in the distribution (see Figure 1.4).

Theoretical analysis.

As explained Section 1.2.2, assuming all the 2 160 possible internal states are equiprobable, and since the output function is balanced, the probability p for the right value to belong to X i,j has to be corrected to 848/1024 = 82.81%. In particular, the final probability becomes (0.8281) 343 = 2 -93.32 . But actually the whole attack is flawed. Indeed, since we merge 190 independent sets X i,j the probability for the right value to belong to X is p 190 and not p 343 . The mistake made by Zhang et al. lies in the merging process. First they construct the set X 0,1,2 by merging X 0,1 , X 0,2 and X 1,2 claiming a probability of p 3 which is correct. Then they construct the set X 1,2,3 by merging X 1,2 , X 1,3 and X 2,3 claiming a probability of p 3 which is also correct. But then they construct the set X 0,1,2,3 by merging X 0,1,2 , X 1,2,3 and X 0,3 and claim a probability of p 3 × p 3 × p = p 7 . This is wrong because X 0,1,2,3 is actually the merge of only 6 sets, X 1,2 being used twice, and the right probability is p 6 . Thus the corrected probability for the right value to belong to X is p 190 = (0.8281) 190 = 2 -51.7 . Surprisingly this is not so far from the 2 -54.09 claimed by Zhang et al.. But the 20 keystream bits z 0 . . . z 19 depend on 118 (linear combinations of) state bits (see Table 5 in [START_REF] Zhang | Fast Near Collision Attack on the Grain v1 Stream Cipher[END_REF]). Thus, according to Theorem 1.1, to reach such probability the set X has to contain 2 118-20 × 2 -51.7 = 2 47.3 elements and not only 2 6.67 . As a consequence, the overall complexity of the attack is increased by a factor 2 47.3+51.7-6.67-54.09 = 2 37.24 , making it slower than an exhaustive search.

Experimental result on p. Finally, as for A5/1 we provide the following experiment to support our claim regarding the correct complexity of the attack presented in [START_REF] Zhang | Fast Near Collision Attack on the Grain v1 Stream Cipher[END_REF].

1. Randomly generate a 3-bit word k s 2. Run the refined self-contained method to obtain a set X of size 2 14.2 which should contain the secret which generated k s with probability (0.8964) 3 = 0.7203 according to Zhang et al..

Do N times:

(a) Randomly generate a key and an IV and run the initialization process.

(b) Check whether the first three keystream bits from the current internal state match k s . If not repeat the previous step.

(c) Check whether the value of the internal state part belongs to X.

4. Check whether the experimental probability matches the expected one.

We ran this experiment 2 10 times with N = 2 26 and found the experimental probability to be very close to (0.8281) 3 = 0.5679, confirming the inaccuracy of the probability 0.7203 claimed by Zhang et al.. To ensure that the initialization process does not introduce and/or remove any biases, we repeated 10 times the experiment for random states during the keystream generation phase too. In more details, we sampled R < 2 10 and before generating the three keystream bits, we updated by R rounds the internal state. As expected, none of those experiments supported Zhang et al. claimed probability.

Conclusion

Conclusion

In the works about FNCA [START_REF] Zhang | Fast Near Collision Attack on the Grain v1 Stream Cipher[END_REF] and [START_REF] Zhang | Cryptanalysis of GSM Encryption in 2G/3G Networks Without Rainbow Tables[END_REF], authors seem to have experimentally verified their claimed probabilities. They wrote they have done a large number of experiments ... and almost all the experimental results conform to our theoretical predictions. This statement is quite unlikely. Indeed, it was enough to add a loop in the publicly available C codes of their works to observe the deviation in the claimed probabilities. Furthermore, as shown in this Chapter, we presented simple algorithms to disprove their claim complexities. In more details, we found an error in the theory proposed and by correcting it and running some algorithmic experiments, we confirm our hypothesis that the complexities of the Fast Near Collision Attacks are seriously underestimated in the papers that introduce them.

To avoid this type of problem, we need to develop more tools to check and verify attacks or to find a completely new theory to explain the security of symmetric primitives like the decorrelation theory at the time of its publication. Nevertheless, it stays important and crucial to evaluate and correct manually previous scientific works.

Chapter 2

EFFICIENT SEARCH FOR OPTIMAL DIFFUSION LAYERS OF GENERALIZED FEISTEL NETWORKS

Introduction

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 nonlinear function for the i-th round. One of the main advantage of this construction is that F i does not need to be invertible, and thus it allows to transform a pseudorandom function (PRF) into a pseudorandom permutation (PRP). Moreover, there are theoretical arguments suggesting that it is a good method to construct block ciphers, as Luby

) → (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. This is essentially a parallel application of k Feistels followed by a cyclic shift of the blocks. They also showed that when all F i,j are pseudorandom functions, then 2k + 1 rounds of such a construction provide a block cipher that is indistinguishable from a random permutation. Moreover, the Type-2 construction is inherently easier to compute in parallel, and the corresponding decryption function is basically the same except that the functions F i,j are applied in reverse order, i.e. for r rounds, the first round of decryption uses the functions F r,j . Both of these properties make this construction very efficient in practice, both on hardware and software, e.g. TWINE [START_REF] Suzaki | TWINE : A Lightweight Block Cipher for Multiple Platforms[END_REF] and Simpira [START_REF] Gueron | Simpira v2: A Family of Efficient Permutations Using the AES Round Function[END_REF]. All of these arguments lead to some block ciphers based on this Type-2 Feistel construction, such as HIGHT [START_REF] Hong | HIGHT: A New Block Cipher Suitable for Low-Resource Device[END_REF] and CLEFIA [START_REF] Shirai | The 128-Bit Blockcipher CLEFIA (Extended Abstract)[END_REF].

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. Such a construction was used to design block ciphers such as 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]. However, Nyberg only focused on one specific permutation. Suzaki and Minematsu thus studied at FSE'10 [SM10] a more general case where the cyclic shift is replaced by any other permutation of the blocks. Their work was focused on finding permutations with the lowest diffusion round. The diffusion round is close to the concept of diffusion introduced by Shannon in 1949 [START_REF] Shannon | Communication theory of secrecy systems[END_REF]. Essentially, a block cipher has full diffusion if every bit of the ciphertext depends on every bit of the plaintext. In the context of Generalized Feistel Network (GFN), [START_REF] Suzaki | Improving the generalized Feistel[END_REF] defined the diffusion round as the minimal number of rounds such that every block of the ciphertext depends on every block of the plaintext. Focusing on blocks instead of bits allows them to get rid of the precise specification of the functions F i,j as well as the exact size of the blocks, thus giving structural results. Especially, they tied the diffusion round of a given GFN to its resistance against Impossible Differential distinguishers [BBS99], proving that if a GFN has a diffusion round of DR, then it needs strictly more than 2DR + 1 rounds to avoid any Impossible Differential distinguisher. Along with a lower bound on the diffusion round of a GFN of 2k blocks, they gave optimal permutations (w.r.t the diffusion round) for 2 ≤ 2k ≤ 16. It is worthy to note that such an optimal permutation was then used to design block ciphers such as TWINE [START_REF] Suzaki | TWINE : A Lightweight Block Cipher for Multiple Platforms[END_REF]. At FSE'19, Cauchois et al. went further and gave optimal permutations for 18 ≤ 2k ≤ 26, as well as good candidates for 2k = 32 (which was already found in [START_REF] Suzaki | Improving the generalized Feistel[END_REF]), as well as for 2k = 64 and 128 using a sophisticated technique that they called Collision-free exhaustive search. Note that these permutations are even-odd, i.e. the image of an even number is an odd number. On a side note, relaxing the condition that the permutation is the same in each round make the problem easier and in [Kal+17], Kales et al. give such a construction for any number of blocks.

Our contribution. In this chapter, we focus on even-odd permutations and we complete the work on the 10-year-old problem (introduced by [SM10]) of finding optimal even-odd permutations for 32 blocks, as well as finding optimal even-odd permutations for 28, 30 and 36 blocks which were not given in the previous literature. To do so, we propose a new characterization of a permutation reaching full diffusion after a given number of rounds. Using this characterization, we are able to create a very efficient algorithm, which on the previously mentioned cases yields all the permutations that achieve full diffusion in 9 rounds. Note that our algorithm essentially uses branch-and-bound techniques, and thus it is hard to evaluate the exact complexity. However, the size of the search space goes from 2 43 for 2k = 28 up to 2 75 for 2k = 42, but we were able to treat each of these cases in less than one hour for each value of k when using 72 threads. Moreover, this characterization has a very efficient implementation which allowed us to re-find all optimal even-odd permutations for up to 26 blocks with a basic exhaustive search in a few hours, showing that for these cases, there is no need for sophisticated techniques as in [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF]. Furthermore, for 34, 38, 40 and 42 blocks, we prove with this method that there is no even-odd permutation with a diffusion round of 9, which is the lower bound on the diffusion round for these sizes given in [START_REF] Suzaki | Improving the generalized Feistel[END_REF]. We were also able to find evenodd permutations with a diffusion round of 10 for 2k = 34 (which is thus optimal), as well as even-odd permutations with diffusion round 11 for 2k = 38, 40, 42. Finally, we evaluate the security of our constructed permutations against impossible differentials and differentials (by computing the minimum number of active S-boxes). In particular, for the 32 blocks case, and the impossible differentials, all our permutations have a one-round shorter longest impossible differential distinguisher compared to what was proposed by [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF], which brings it down to 17 rounds.

Chapter 2 -Efficient Search for 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.1 -Generalized Feistel Network

Preliminaries

Generalized Feistel Networks (GFN)

Zheng et al. [START_REF] Zheng | On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses[END_REF] introduced Type-2 Feistels as a generalization of the original Feistel construction. Given an even number 2k of blocks (X 0 , . . . , X 2k-1 ), it first applies the Feistel construction on the pairs of blocks which yields (X 0 ⊕ S 0 (X 1 ), X 1 , . . . , X 2k-2 ⊕ S k-1 (X 2k-1 ), X 2k-1 ). The blocks are then cyclically right shifted to obtain the result. Later, it was proposed to use another permutation than the cyclic shift in [START_REF] Nyberg | Generalized Feistel Networks[END_REF], leading to Generalized Feistel Networks. Definition 2.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 of cryptographic keyed functions from F n 2 to F n 2 . Let π be a permutation over 2k elements. A Generalized Feistel Network (GFN) 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 )
Note that for this chapter, neither the exact definition of the keyed functions F i,j nor their sizes are relevant. We can thus consider all of them as an arbitrary S-box S, leading to the framework depicted in Figure 2.12 . As the only variable parameters are thus k and π, we denote by GFN k π a GFN with 2k blocks that uses the permutation π.

Preliminaries

Diffusion Round

We use the notations depicted in Figure 2.1. The input variables of the i-th round of a GFN are denoted by (X i 0 , X i 1 , . . . , X i 2k-1 ). We also denote by ( X i 0 , X i 1 , . . . , X i 2k-1 ) the variables which are at the input of the permutation π, i.e.

(X i+1 0 , X i+1 1 , . . . , X i+1 2k-1 ) = π( X i 0 , X i 1 , . . . , X i 2k-1 )
It is easy to see from Definition 2.1 that X 1 π(0) depends on X 0 0 and X 0 1 . More generally, any block X r j depends on a certain number of blocks from the round 0, i.e. computing X r j requires some blocks {X 0 j 0 , . . . , X 0 j l }. Note that this does not depend on the size of the functions F i,j in the GFN. As in [START_REF] Suzaki | Improving the generalized Feistel[END_REF], 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.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 2.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 2.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 ). Searching the best permutations (for the diffusion) directly can be difficult. As a result the methodology we adopt in this work is to search for permutations that diffuse totally in the forward direction and then check if their respective inverse also diffuses totally.

Even-odd Permutations

A naive way to search for optimal permutation 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. To reduce the number of permutations that will be tested, we will restrict ourselves to a specific class of permutations and give an equivalence relation which further reduces the number of permutations to be considered.

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. In the rest of this chapter, we will use the following notation for even-odd permutations. An even-odd permutation π of size 2k will be denoted by the 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.
According to this, [START_REF] Suzaki | Improving the generalized Feistel[END_REF] gives the following lower-bound on the diffusion round of even-odd permutations (p, q). Proposition 2.1. Let F i be the Fibonacci sequence, i.e. F 0 = 0, F 1 = 1 and F i = F i-1 + F i-2 , i ≥ 2. Let π = (p, q) be an even-odd permutation over 2k elements, and i be the smallest integer such that F i ≥ k. Then DR max (π) ≥ i + 1.

For a given permutation π, if the inequality is tight, we say that π is tight. A proof of this proposition already exists in both [START_REF] Suzaki | Improving the generalized Feistel[END_REF] and [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF]. According to our results, we will give another proof of this proposition in Section 2.3. We will also show in Section 2.3 that this bound is tight for the cases 2k = 28, 30, 32, 36 and strict for 2k = 34, 38, 40, 42.

Equivalence Classes of Even-odd Permutations

To further reduce the size of the search space, as in [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF], we use some equivalence classes, given by the following definition. Definition 2.4. Let π and π be two even-odd permutations over 2k elements. We say that π and π are equivalent if there exists a permutation ϕ over 2k elements such that

π = ϕ • π • ϕ -1 and ∀i ∈ [0, k -1], ϕ(2i + 1) = ϕ(2i) + 1.
From [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF], we can then give a set of permutations P k such that for any equivalence class, there exists at least one π ∈ P k which belongs to this class. This effectively gives us a set of class representatives (in which a few of them are redundant), and this set can be built from the following proposition, proven in [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF]. Recall that any permutation can be decomposed into a composition of cycles. We call cycle structure the unordered set of the length of these cycles, for example the permutation (0 1 2 3)(4 5)(6 7)(8) has a cycle structure of {4, 2, 2, 1}.

Proposition 2.2. Let P k be a set of even-odd permutations π = (p, q) over 2k elements constructed as follows. For each possible cycle structure c of a permutation over k elements, pick one permutation p which has a cycle structure equal to c. Then, for every permutation q over k elements, add (p, q) in the set P k . By doing so, P k contains at least one representative of each equivalence class induced by Definition 2.4. Moreover, P k contains exactly N k .k! elements, where N k is the number of partitions of the integer k. This allows us to only consider N k .k! permutations instead of (k!) 2 . This is a significant improvement, as for example with k = 16, there are only 231 × 16! 2 52 permutations to go through, instead of (16!) 2 2 88 . However when k grows, it is still too big a number to try an exhaustive search. As such, we propose in Section 2.4 an efficient search algorithm to find all optimal even-odd permutations for a given k, without needing to do an exhaustive search.

Characterization of Full Diffusion

In this section, we will explain our strategy to search for a tight even-odd permutation, that is, a permutation with a diffusion round reaching the Fibonacci bound given in Proposition 2.1. We will first give an algebraic characterization for a permutation to have full diffusion, then give an algorithm to exploit this characterization and quickly search all such permutations. Note that here we only focus on the diffusion round of the permutation when considering encryption. That is, for a given permutation π, we focus only on DR(π) = max 0≤i≤2k-1 {DR i (π)}. Then, once we found a permutation reaching the Fibonacci bound, we can easily check if π -1 also reaches this bound, and if that is the case, we found a tight permutation.

Chapter 2 -Efficient Search for Optimal Diffusion Layers of Generalized Feistel Networks

We describe here the main tools we used to design our search algorithm. Note that for two permutations p, q, we denote the composition p • q by pq for better reading. We first begin by giving the following proposition.

Proposition 2.3. Let π = (p, q) be an even-odd permutation over 2k elements. Then π achieves full diffusion after r rounds if and only if each block X 0 j is diffused to at least one block of each pair at the input of the (r -1)-th round, i.e. diffused to either X r-1 2j or X r-1 2j +1 for each j ∈ {0, . . . , k -1}.

Proof. Suppose that a given block X 0 i has been fully diffused, i.e. to every block X r 2j and X r 2j+1 , j ∈ {0, . . . , k -1}. Then X 0 i must have diffused to at least X r 2j+1 for every j, as it is the only way to reach X r 2j+1 . Thus, X 0 i must have diffused to X r-1 2j with j = p -1 (j), which means that it has diffused to either X r-1 2j or X r-1 2j +1 . On the other hand, suppose that a given block X 0 i has diffused to an even block X r-1 2j , then X 0 i will be diffused to only X r-1 2j . If X 0 i has diffused to an odd block X r-1 2j+1 , it will be diffused to both X r-1 2j and X r-1 2j+1 . In both cases, it will be diffused to X r-1 2j , then to X r 2j +1

with j = p(j), and finally to both X r 2j and X r 2j +1 . Thus, if for all j ∈ {0, . . . , k -1}, X 0 i is diffused to any block of the j-th pair at the input of the (r -1)-th round, it will be diffused to every block X r 2p(j) and X r 2p(j)+1 , and since p is a permutation, this means that we have full diffusion for X 0 i .

Corollary 2.1. Let π = (p, q) be an even-odd permutation over 2k elements. Then π achieves full diffusion after r rounds if and only if each even block X 0 2j , j ∈ {0, . . . , k -1} diffuses to every even block X r-1 2j , j ∈ {0, . . . , k -1}.

Proof. For the proof of the previous theorem, we can easily see that a block X 0 j diffuses to either X r-1 2j or X r-1 2j +1 if and only if X 0 j diffuses to X r-1 2j . Moreover, we can easily see that if X 0 2j is fully diffused, so is X 0 2j+1 . Indeed, X 0 2j being fully diffused is the same as X 0 2j being fully diffused, and X 0 2j+1 is always diffused to X 0 2j .

Thus we only need to focus on the diffusion of each block X 0 2j to each block X r-1 2j . Now we can take a look a what would happen in an ideal scenario. Assume that we are studying the diffusion of a block X 0 2j . Then X 0 2j is diffused to X 0 2j 1 0 with j 1 0 = j. It is then diffused to both X 1 2j 2 0 and X 1 2j 2 0 +1 , with j 2 0 = p(j 1 0 ). Then again :

• X 1 2j 2 0 is diffused to both X 2 2j 3 0 and X 2 2j 3 0 +1 , with j 3 0 = p(j 2 0 ). • X 1 2j 2 0 +1 is diffused to X 2 2j 3 1 with j 3 1 = q(j 2 0 ) 52 2.

Characterization of Full Diffusion

Assuming an ideal scenario, we would have j 3 0 = j 3 1 , i.e. X 0 2j has diffused to two different blocks after 4 rounds (minus the application of π on the fourth round). We can then keep going and get a series of j i which gives us the blocks on which X 0 2j has diffused after i + 1 rounds minus the last application of π, always assuming that we never have j i = j i for = . The propagation for up to 7 rounds is given in Figure 2.2. However, we cannot have j i = j i with = forever. Indeed, since we only have k blocks, we are bound at some point to have j i = j i and = . However, we can easily compute the actual value of each j i . Indeed, if we take for example j 6 6 in Figure 2.2, then we know that

j 6 6 = (qppqp)(j 1 0 ) = (qppqp)(j).
Denote by J i j the set of equations obtained by expressing every j i that way. For example, we would have According to this, we can give a generic way to compute J i j . We start with J 1 j = {j} and J 2 j = {p(j)}. To build J i j from J i-1 j , we begin by adding p(x) to J i j for every term x in J i-1 j . Then, for every term x in J i-1 j such that x can be written as x = p(y) for some y ∈ J i-2 j , we also add q(x) to J i j . We can justify this construction as follows. Suppose that a given j belongs to J i-2 j because X 0 2j diffuses to X i-2 2j . Then X 0 2j diffuses to both X i-1 2j and X i-1 2j +1 with j = p(j ). Thus for the next round, X 0 2j will diffuse to both X i 2 j+1 and X i 2 j , with j = p(j ) and j = q(j ).

J 6 j = {(ppppp)(j), (qpppp)(j)
On the other hand, suppose that j belongs to J i-2 j because X 0 2j diffuses to X i-2 2j +1 . In that case, X 0 2j will only diffuse to X i-1 2j with j = q(j ). For the next round, X 0 2j only diffuses to X i 2 j+1 with j = p(j ). Thus in both cases, we need to have j = p(j ), but we only require j = q(j ) in the first case, which corresponds exactly to the case where the previous term started with a composition by p.

Note that from this construction, we can deduce the following proposition.

Proposition 2.4. The size of J i j is exactly F i where F i is the i-th term of the Fibonacci sequence.

Proof. We can prove this by induction. Both J 1 j and J 2 j are of size 1, which corresponds to F 1 and F 2 . We first add an element p(x) to J i j for every x ∈ J i-1 j , thus F i-1 elements. Then, for every x in J i-1 j such that x = p(y) with y ∈ J i-2 j , we add q(x) to J i j . However, according to our construction, J i-1 j contains such an element x = p(y) for every term y ∈ J i-2 j . Thus, there are F i-2 such terms. In the end, J i j contains F i-1 + F i-2 = F i elements, which concludes the induction.

We can now use those sets J i j to fully characterize the fact that a block fully diffuses when using a given permutation.

Theorem 2.1. Let J r-1 j be the set of equations as defined above. Then for a given permutation π = (p, q) over 2k blocks, X 0 2j is fully diffused after r rounds if and only if J r-1 j contains every number in {0, . . . , k -1} at least once.

Proof. As J r-1 j = {j r-1 0 , . . . , j r-1 r-1 } is defined, it basically represents that X 0 2j diffuses to every X i 2j i . Thus, if J i j contains every number in {0, . . . , k -1} at least once, it exactly means that X 0 2j diffuses to each block X i 2j , j ∈ {0, . . . , k -1}. According to Corollary 2.1, this means that X 0 2j achieves full diffusion after i + 1 rounds.

We can then easily deduce the following corollary.

Corollary 2.2. Let π = (p, q) be a permutation over 2k elements. Then we have DR(π) = i+1 if and only if i is the smallest integer such that for every j ∈ {0, . . . , k-1}, J i j contains every number in {0, . . . , k -1} at least once. This gives us another proof for the Fibonacci bound given in Proposition 2.1. Indeed, for J i j to contain every number in {0, . . . , k -1} at least once, J i j must contain at least k terms. Thus, and since the size of J i j does not depend on j, the minimal number of rounds needed to have full diffusion for every block must be such that J i j = F i ≥ k. According to the previous corollary, if i is the smallest integer such that F i ≥ k, this exactly means that DR max (π) ≥ i + 1

Chapter 2 -Efficient Search for Optimal Diffusion Layers of Generalized Feistel Networks

Note that from the construction of any J i j , each term starts with a composition by p. Since p is a permutation, and we want full diffusion for every blocks, we can remove this first p from every term to get a smaller representation. Essentially, this means that we are considering the diffusion of the block p -1 (j), but we will still write J i j . As such, J 6 j for example is thus rewritten as

J 6 j = {(p 4 )(j), (qp 3 )(j), (pqp 2 )(j), (p 2 qp)(j),
(qpqp)(j), (p 3 q)(j),

(qp 2 q)(j), (pqpq)(j)}
To illustrate the previous characterization, we introduce what we call the diffusion table (of rank i) of an even-odd permutation (p, q) of size 2k. The columns are indexed by the numbers from 0 to k -1 and the row are indexed by the products of p and q used to generate all sets J i j . Each cell of the table is the value obtained by applying the permutation indexing the row to the value indexing the column of the cell. For example, the cell indexed by p i and 0 contains p i (0). This provides a clear visualization of our characterization, as the j-th column is exactly J i j . Thus, we can easily illustrate Corollary 2.2 by verifying that every column of this table contains every possible values. We thus add one more row at the end of diffusion table called diff which contains the number of different values in a column. By construction, this is exactly the number of elements of J i j where j is the index of the column. In tables constructed as described, the full diffusion of a permutation corresponds to a diff row containing only the value k.

For example, we give in Table 2.1 the diffusion tables for the cyclical shift (i.e. p = (7, 0, 1, 2, 3, 4, 5, 6) and q = (0, 1, 2, 3, 4, 5, 6, 7)) and one of the optimal permutation proposed by [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF] (i.e. p = (6, 3, 7, 1, 0, 2, 4, 5) and q = (3, 5, 1, 6, 4, 0, 2, 7)) for k = 8 and i = 7, thus the optimal permutation clearly have a diffusion round of 8. Finally, we can reformulate the problem of finding optimal even-odd permutations with 56

Searching for an Optimal Permutation over 9 Rounds

x 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 diff 4 4 4 4 4 4 4 4

x 0 1 2 4 5 6 7 p 5 4 3 5 6 7 0 2 p 4 q 3 2 1 0 6 7 5 p 3 qp 2 6 7 1 3 4 0 p 2 qp 2 6 7 4 5 2 3 1 pqp 3 1 4 3 0 6 7 5 qp 4 2 5 7 3 1 4 0 p 2 qpq 7 1 0 3 5 2 4 pqp 2 q 4 5 2 7 0 6 3 qp 3 q 5 0 6 4 3 1 7 pqpqp 5 0 6 2 4 1 7 qp 2 qp 0 3 1 6 5 2 4 qpqp 2 3 1 2 7 0 5 6 qpqpq 1 6 4 5 7 0 2 diff 8 8 8 8 8 8 8

Table 2.1 -Diffusion tables for the cyclical shift (left table) and one optimal permutation proposed by [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF] (right table).

these tables. Indeed, it corresponds to finding the minimal i and even-odd permutations of size 2k such that their diffusion table have their diff row containing only k.

Searching for an Optimal Permutation over 9 Rounds

Efficient Search Algorithm

First, we can see that our characterization can be very efficiently implemented, as testing if π = (p, q) has full diffusion mostly requires only a few table lookups. An example of an implementation for this test for 9 rounds is given in Appendix 2.B, and its efficiency allowed us to recover all optimal even-odd permutations for k ≤ 13 with a basic exhaustive search. Especially, for k = 13, we were able to go through all N 13 .13! 39 permutations and check them in about 410 minutes on a single core. While these optimal permutations were already known, it shows that the sophisticated techniques introduced in [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF] were not necessary for these cases.

However for k ≥ 14, it becomes too expensive to make this exhaustive search. We thus focus on finding optimal even-odd permutations for 14 ≤ k ≤ 21, hence such permutations would have a diffusion round of 9. Given a cycle structure for p, we can easily find a Chapter 2 -Efficient Search for Optimal Diffusion Layers of Generalized Feistel Networks permutation p with such structure and thus we need to search q such that π = (p, q) needs 9 rounds to reach full diffusion, i.e., such that each J 8 j contains all numbers from 0 to k -1.

Note that we cannot exploit J 8 j directly. Indeed, one might want to guess parts of q and check if J 8 j does not contains too many duplicates. However, to fully compute J 8 j , we need to guess q in its entirety, which makes this strategy too expensive. We thus describe an efficient way to exploit this characterization to find optimal even-odd permutations.

First for a given j, if we take a look at J 6 j , we can see that we need to make only 7 guesses over the images of q to fully compute J 6 j . Indeed, we need to know q(j), (qp)(j), (qp 2 )(j), (qp 3 )(j), (qpq)(j), (qp 2 q)(j) and (qpqp)(j).

Let X 6 j and Y 6 j be two subsets of J 6 j , such that X 6 j ∪ Y 6 j = J 6 j , with X 6 j = {p 4 (j), (pqp 2 )(j), (p 2 qp)(j), (p 3 q)(j), (pqpq)(j)} and Y 6 j = {(qp 3 )(j), (qpqp)(j), (qp 2 q)(j)}.

According to the construction of J 8 j , we can actually write

J 8 j = p 2 (X 6 j ∪ Y 6 j ) ∪ (pq)(X 6 j ) ∪ (qp)(X 6 j ∪ Y 6 j ).
Assume that we made the 7 guesses mentioned above. In that case, we know the exact values in both X 6 j and Y 6 j . Moreover, since p is known, we know exactly the values in p 2 (X 6 j ∪ Y 6 j ). Finally, since we guessed 7 images of q, there might be some values in (pq)(X 6 j ) and (qp)(X 6 j ∪ Y 6 j ) that are known. Hence, we create three sets K j , X 6 j and Y 6 j :

• K j is the set of all known values of J 8 j . Thus p 2 (X 6 j ∪ Y 6 j ) ⊂ K j and there might be a few elements from (pq)(X 6 j ) and (qp)(X 6 j ∪ Y 6 j ) in K j too.

• X 6 j is the subset of X 6 j such that for any x ∈ X 6 j , the value of q(x) yet remains to be determined.

• In the same way, Y 6 j is the subset of p(X 6 j ∪ Y 6 j ) such that for any x ∈ Y 6 j , the value of q(x) is not determined.

For j to be fully diffused, we thus have the constraint

C j : K j ∪ q( Y 6 j ) ∪ (pq)( X 6 j ) ≥ k.
We then check if this constraint is valid, i.e. if there exist some guesses for the remaining images of q such that C j holds, and this is described in the next section.

Now if we take a look at J 6 j where j = p(j), we can see that we only need 3 more guesses to compute it, instead of 7 as before. Indeed, we already guessed

(qp)(j) = q(j ) (qp 2 )(j) = (qp)(j ) (qp 3 )(j) = (qp 2 )(j ) (qpqp)(j) = (qpq)(j )
and thus it only remains to guess

(qp 4 )(j) = (qp 3 )(j ) (qp 2 qp)(j) = (qp 2 q)(j ) (qpqp 2 )(j) = (qpqp)(j ).
By doing these guesses, we can build the sets K j , X 6 j and Y 6 j as before, and thus get another constraint that needs to be checked

C j : K j ∪ q( Y 6 j ) ∪ (pq)( X 6 j ) ≥ k.
However by making those three new guesses, we might be able to compute new values in X 6 j and Y 6 j . We thus need to update the constraint C j according to these guesses, and then check again if C j is valid.

This can be repeated until we have fully guessed q, in which case we have a solution, or show that no matter which guesses we made there is no solution which satisfies all constraints. This is the core of our algorithm, which is described from a high-level point of view in Algorithm 5.

Note however that the actual algorithm is a bit more sophisticated. Indeed, it might occur at some point that p(j) was already processed, i.e. C p(j) is already a constraint we have. When this happens, we need to choose another starting block j, and re-apply the Chapter 2 -Efficient Search for Optimal Diffusion Layers of Generalized Feistel Networks Algorithm 5 Searching for optimal even-odd permutations over 9 rounds 1: function nextGuess(p, q, j, C)

C is the list of known constraints

2:
if q is fully determined then 3:

Print p, q 4: else 5: while all guesses are not made do 6:

Guess (qp 3 )(j), (qp 2 q)(j) and (qpqp)(j)

7:
Update every constraints in C according to those guesses 8:

Deduce the new constraint C j 9:

C ← C ∪ {C j } 10: if ∃ invalid constraint in C then 11:
Make a new guess Guess q(j), (qp)(j), (qp 2 )(j), (qp 3 )(j), (qpq)(j), (qp 2 q)(j) and (qpqp)(j)

22:

Deduce the constraint C j 23:

if C j is a valid constraint then 24: C ← {C j } 25:
nextGuess(p, q, p(j), C)

26:

end if 27: end while algorithm, while still keeping all previously computed constraints. In practice, we found that the most efficient strategy is to use an element from the shortest cycle of p as the first starting block. Then, if we need to choose another starting block, we pick an element in the next shortest cycle of p and so on. Moreover, when making some guesses for the images of q, it might happen that we already made this guess. This is not a problem, as this guess basically becomes free and does not add any more cost. Finally, except for the first seven guesses, we update and check all constraints after each guess.

Checking the Constraints

We first give a naive way to check if a constraint is valid. We are given three sets K, X and Y, resulting in the constraint

C : |K ∪ q(Y) ∪ (pq)(X)| ≥ k.
We know the full permutation p, and for any x ∈ X ∪ Y, q(x) is still unknown. Let A denote the set of values a for which we still do not know the preimage of a through q, i.e. for any a ∈ A, we do not know which x results in q(x) = a. Considering the guesses we already made on q, we always know this set A, and thus have the following two relations (pq)(X) ⊂ p(A) and q(Y) ⊂ A. According to this, we can write

|K ∪ q(Y) ∪ (pq)(X)| ≤ |K ∪ A ∪ p(A)| . Hence if |K ∪ A ∪ p(A)| < k,
we know that the constraint C cannot be valid. However, we can actually go further and get more precise information by doing the following.

We can formulate our problem in the following generic way. We are given three sets K, A, and B (= p(A)), and we search for two sets A ⊂ A and B ⊂ B such that |K ∪ A ∪ B| is maximal, with A = q(Y) and B = (pq)(X). Note that, since p and q are permutations, we have | A| = |X| and | B| = |Y|. Hence our idea is to determine whether there is at least one such pair ( A, B) satisfying |K ∪ A ∪ B| ≥ k. Indeed if no such pair exists then constraint C does not hold. Note that if X ∩ Y = ∅ then it is possible for such pair to exist while C does not hold. However we found this filter powerful enough for our need.

We can partition K ∪ A ∪ B into the following eight disjoint sets:

• First, using elements from S 5 to build A does not add any duplicate, thus we first pull elements from S 5 and k 5 A = min(k A , |S 5 |).

• As mentioned above, using one element from S 1 adds either zero or one duplicate, thus we then pull elements from S 1 and k

1 A = min(k A -k 5 A , |S 1 |).
• Finally, elements from either S 0 and S 3 necessarily add duplicates, so we freely choose any

k 0 A ≤ |S 0 | and k 3 A ≤ |S 3 | such that k 0 A + k 3 A = k A -k 5 A -k 1 A .
Finally, computing the maximal value for |K ∪ A ∪ B| only requires to compute |S 1 |, |S 4 | and |S 5 | and we then check how it compares to k.

Results

We ran our algorithm for every k such that we need at least 9 rounds to have full diffusion, according to Proposition 2.1. This corresponds to 14 ≤ k ≤ 21, and we were able to find all optimal even-odd permutations for k ∈ {14, 15, 16, 18}. For k ∈ {17, 19, 20, 21}, our algorithm allowed us to prove that there is no even-odd permutation leading to a full diffusion after 9 rounds. Since 9 rounds correspond to the Fibonacci bound, we know that for these cases, we need at least 10 rounds to have full diffusion, and we give later in this section an optimal solution for k = 17 reaching full diffusion in 10 rounds, as well as good permutations for k = 19, 20, 21 with a diffusion round of 11. We can thus give the following theorem to summarize our results.

Theorem 2.2. To build a Generalized Feistel Network GFN k π with full diffusion where π is an even-odd permutation, we have :

• 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.

We give in Table 2.2 an overview of our results. The first column gives the total time needed for our algorithm to either exhaust all optimal even-odd permutations, or prove that no such permutation exists. Note that this is the total CPU time, i.e. when using a single CPU, however our algorithm is highly parallelizable and thus the real time can be drastically reduced. 3 This shows that our algorithm is extremely efficient, as it can quickly solve the case k = 16 for which [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF] were not able to give an optimal solution. The second (resp. third) column gives the possible cycle structures of p (resp. q) in an optimal permutation, and the last column gives the number of solutions which have this structure. We can notice that not only the number of solutions is quite low, but also that the number of possible cycle structures is also quite limited. Moreover, we always have a fixed point in either p or q.

The most important result in this table is that there are actually even-odd permutations which have full diffusion after 9 rounds for k = 16, while both [START_REF] Suzaki | Improving the generalized Feistel[END_REF] and [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF] could only find a permutation with full diffusion after 10 rounds, leaving open the question of whether the theoretical bound of 9 rounds (from Proposition 2.1) could be reached.

Our results shows that it is indeed possible, and thus this proves that our permutations are optimal when considering even-odd permutations. We will see in the next section that we can further regroup these permutations into more precise equivalence classes, leading for the case k = 16 to four equivalence classes, given in Table 2.3.

Chapter 2 -Efficient Search for Optimal Diffusion Layers of Generalized Feistel Networks

have ϕ • π • ϕ -1 (2i) = ϕ • π(2r -1 (i)) = ϕ(2(p • r -1 )(i) + 1) = 2(r • p • r -1 )(i) + 1 = 2p(i) + 1 = π (2i).
In the same way, the image of an odd number 2i + 1 is

ϕ • π • ϕ -1 (2i + 1) = ϕ • π(2r -1 (i) + 1) = ϕ(2(q • r -1 )(i)) = 2(r • q • r -1 )(i) = π (2i + 1)
We thus have π = ϕ • π • ϕ -1 . Hence, π and π are conjugate and thus equivalent, according to Definition 2.4. This leads us to the equivalence classes given in Table 2.4 to 2.7 in Appendix 2.A for k = 14, 15, 18. The column (p, q) gives both permutations p and q. The column Imp. Diff. gives the number of rounds for the longest Impossible Differential distinguisher. Note that this is only considering structural Impossible Differentials, where we do not specify neither the size of the blocks nor the definition of the S-boxes, such that contradictions are obtained on blocks rather than bits. The columns S s,δ N give the minimal number of rounds to get at least N active S-boxes, where each S-box is of size s and the highest differential probability is 2 -δ . We chose to only consider three cases : S 4,2 N , S 8,6 N and S 8,7 N . The first case represents the best case for 4-bit S-boxes. Indeed, we know that there is no APN bijective S-boxes of size 4 (which would lead to a highest differential probability of 2 -3 ). As such, the best case is when the highest differential probability is 2 -2 . It is still unknown whether 8-bit APN bijective S-boxes exist, so we consider both cases. If such an APN 8-bit S-box exists, the column S 8,7

N is relevant, otherwise it would be S 8,6 N (for example the AES S-box). The last thing is that N depends on the size of the key (as well as δ). Indeed, if we have a key of size λ, then we want N to verify 2 -δN < 2 -λ , i.e. N > λ δ .

As the evaluation of the minimal number of rounds to get at least N S-boxes can be quite expensive, we limited ourselves to λ = 2ks, where k follows the notation in this chapter, i.e. we have 2k blocks of s bits and the key is of the same size as the state. Finally, the last column N 20 shows the minimal number of active S-boxes for 20 rounds, as both [START_REF] Suzaki | Improving the generalized Feistel[END_REF] and [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF] also gave this metric for the permutations they found. It is worth mentioning that while our permutations are optimal (w.r.t the diffusion round), for the case k = 16, they have a minimal number of active S-boxes over 20 rounds which is lower than for the permutations given in [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF] in the same case, where those permutations have a diffusion round of 10 and at least 70 actives S-boxes over 20 rounds. However for all our permutations, the longest Impossible Differentials distinguisher we can build is over 17 rounds, which is at least one round lower than for the permutations with k = 16 given in [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF].

Note that we were still able to find the following optimal even-odd permutation for k = 17, which thus has a diffusion round of 10 : p = (7, 1, 4, 13, 8, 16, 2, 3, 12, 5, 0, 9, 15, 14, 10, 11, 6) q = (8, 0, 9, 10, 3, 2, 16, 6, 14, 11, 7, 4, 1, 12, 5, 15, 13)

For this permutation, the longest Impossible Differential distinguisher is over 19 rounds, and S 4,2 69 , S 8,6 46 , S 8,7 39 , N 20 are respectively 20, 16, 15 and 20. For k = 19, 20, 21, we easily found permutations reaching full diffusion after 11 rounds with a random search, leaving open the question to find one permutation with a diffusion round of 10. We give an example for these cases below k = 19 : p = (18, 3, 5, 9, 13, 15, 10, 16, 11, 8, 6, 1, 0, 2, 14, 7, 17, 12, 4) q = (9, 14, 2, 6, 3, 8, 16, 4, 0, 13, 18, 15, 5, 11, 7, 17, 12, 1, 10) k = 20 : p = (14, 5, 15, 1, 17, 3, 11, 8, 4, 0, 6, 13, 19, 10, 2, 9, 18, 12, 16, 7) q = (1, 17, 5, 18, 12, 2, 0, 16, 13, 6, 3, 10, 14, 8, 11, 19, 9, 15, 7, 4) k = 21 : p = (19, 10, 7, 17, 2, 16, 20, 9, 6, 0, 3, 12, 18, 1, 4, 11, 15, 13, 14, 8, 5) q = (20, 12, 0, 8, 7, 1, 4, 2, 10, 13, 5, 6, 11, 14, 19, 15, 9, 16, 3, 17, 18)

Conclusion

We solved a 10-year-old problem which was to find an optimal (w.r.t diffusion round) even-odd permutation for a Generalized Feistel Network with 32 blocks. More specifically, we showed that there exist permutations which have a diffusion round of 9, while the best permutation found before had a diffusion round of 10. To do so, we give a precise characterization for the permutation to have full diffusion after a given number of rounds. This characterization allowed us to get a very efficient exhaustive search for k ≤ 13. Even if optimal permutations were already known for these sizes, this shows that our characterization is powerful, thus we have no need to use the elaborated techniques from [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF] to treat all these cases. We then exploit this characterization to design a very efficient algorithm that allows us to exhibit all optimal even-odd permutations for 32 blocks, as well as for 28, 30 and 36 blocks, which also have an optimal diffusion round of 9 and were not given in the previous literature. For 34, 38, 40 and 42 blocks, our algorithm also allows us to prove that there is no even-odd permutation with a diffusion round of 9 (which is the lower bound), which is again a new result. However for these cases, we were able to give better optimality bounds when considering even-odd permutations, namely for 2k = 34 the optimal number of rounds for full diffusion is exactly 10 rounds and for 2k = 38, 40, 42, at most 11 rounds. We also give some security evaluation for Impossible Differentials and Differentials (through the minimum number of active S-boxes). Especially for Impossible Differentials, for the 32 blocks case, all our permutations have their longest impossible differential distinguishers over 17 rounds, which is at least one round lower than every permutation given in [START_REF] Cauchois | General Diffusion Analysis: How to Find Optimal Permutations for Generalized Type-II Feistel Schemes[END_REF] for this case.

2.A Results for Optimal Permutations

2.B Efficient Implementation to Test 9 Round Full Diffusion

We give an example of a C++ implementation of the characterization for a permutation to have full diffusion over 9 rounds. This function takes powerp and q as parameters, which are respectively, the precomputed values of each power of p, i.e. powerp[i][j] = p i (j), and the permutation q.

(p, q) Imp. Diff S 4,2 57 S 8,6 38 S 8,7

33

N 20 p = (1, 2, 3, 4, 5, 0, 7, 8, 9, 10, 11, 6, 12, 13) 17 19 14 13 66 q = (10, 7, 13, 11, 9, 8, 4, 1, 12, 5, 3, 2, 6, 0) p = (1, 2, 3, 4, 5, 0, 7, 8, 9, 10, 11, 6, 12, 13) 17 19 14 13 66 q = (8, 6, 13, 10, 7, 9, 1, 12, 5, 2, 4, 3, 11, 0) p = (1, 2, 3, 4, 5, 0, 7, 8, 9, 10, 11, 6, 13, 12) 17 19 14 13 66 q = (9, 1, 13, 5, 2, 10, 3, 7, 12, 11, 8, 4, 6, 0) p = (1, 2, 3, 4, 5, 0, 7, 8, 9, 10, 11, 6, 13, 12) 17 19 14 13 66 q = (4, 1, 13, 5, 10, 9, 2, 11, 8, 12, 6, 3, 7, 0) p = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 13, 12) 17 22 14 13 52 q = (3, 5, 2, 13, 0, 10, 9, 11, 8, 12, 6, 4, 7, 1) p = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 13, 12) 17 22 14 13 52 q = (3, 1, 13, 11, 8, 10, 9, 7, 12, 5, 2, 4, 6, 0) p = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 12, 13) 17 22 14 13 52 q = (3, 11, 8, 13, 6, 10, 9, 5, 2, 12, 0, 4, 7, 1) p = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 12, 13) 17 22 14 13 52 q = (3, 7, 13, 5, 2, 10, 9, 1, 12, 11, 8, 4, 6, 0) p = (1, 2, 3, 4, 5, 0, 7, 8, 6, 10, 9, 12, 11, 13) 17 23 19 18 46 q = (4, 9, 6, 11, 13, 12, 10, 2, 8, 1, 5, 3, 7, 0) N 20 p = (1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 11, 10, 13, 12, 14) 17 20 16 14 61 q = (12, 5, 10, 3, 11, 1, 13, 9, 14, 7, 4, 6, 2, 8, 0) p = (1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 11, 10, 13, 12, 14) 17 42 28 24 30 q = (13, 9, 10, 7, 11, 5, 12, 3, 14, 1, 4, 6, 8, 2, 0) N 20 p = (1, 2, 3, 4, 5, 0, 7, 8, 9, 10, 11, 6, 13, 14, 12, 15) 17 33 22 19 40 q = (2, 6, 12, 10, 1, 13, 4, 15, 7, 9, 14, 5, 8, 3, 11, 0) p = (1, 2, 3, 4, 5, 0, 7, 8, 9, 10, 11, 6, 13, 14, 12, 15) 17 33 22 19 40 q = (5, 6, 13, 10, 4, 12, 9, 15, 2, 1, 14, 7, 11, 3, 8, 0) p = (1, 2, 3, 4, 5, 0, 7, 8, 9, 10, 11, 6, 13, 12, 15, 14) 17 50 33 29 26 q = (2, 1, 12, 8, 7, 14, 5, 4, 13, 11, 10, 15, 9, 3, 6, 0) p = (1, 2, 3, 4, 5, 0, 7, 8, 6, 10, 11, 9, 13, 12, 14, 15) 17 50 33 29 26 q = (7, 6, 14, 9, 11, 15, 1, 12, 2, 13, 5, 4, 10, 8, 3, 0) N 20 p = (1, 2, 3, 4, 5, 6, 7, 0, 9, 10, 11, 12, 13, 14, 15, 8, 16, 17) 17 31 22 19 q = (10, 9, 14, 12, 15, 11, 13, 17, 2, 1, 6, 4, 7, 3, 5, 16, 8, 0) p = (1, 2, 3, 4, 5, 6, 7, 0, 9, 10, 11, 12, 13, 14, 15, 8, 16, 17) 17 56 38 32 q = (14, 8, 12, 15, 13, 10, 9, 17, 7, 6, 16, 3, 5, 1, 4, 2, 11, 0) p = (1, 2, 3, 4, 5, 6, 7, 0, 9, 10, 11, 12, 13, 14, 15, 8, 17, 16) 17 31 22 19 q = (2, 1, 6, 12, 15, 3, 13, 16, 10, 9, 14, 4, 7, 11, 5, 17, 8, 0) p = (1, 2, 3, 4, 5, 6, 7, 0, 9, 10, 11, 12, 13, 14, 15, 8, 17, 16) 17 56 38 32 q = (11, 5, 9, 12, 2, 7, 6, 16, 3, 13, 1, 4, 10, 15, 14, 17, 8, 0)

Introduction

Differential cryptanalysis [START_REF] Biham | Differential Cryptanalysis of Feal and N-Hash[END_REF] evaluates the propagation of an input difference δX = X ⊕ X between two plaintexts X and X through the ciphering process. Indeed, differential attacks exploit the fact that the probability of observing a specific output difference given a specific input difference is not uniformly distributed. Today, differential cryptanalysis is public knowledge, and block ciphers such as AES have proven bounds against differential attacks. A classical extension of differential cryptanalysis is the so called related-key differential cryptanalysis [START_REF] Biham | New Types of Cryptanalytic Attacks Using related Keys (Extended Abstract)[END_REF] that allows an attacker to inject differences not only between the plaintexts X and X but also between the keys K and K (even if the secret key K stays unknown from the attacker). This attack has been recently extended to tweakable block ciphers [START_REF] Beierle | The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS[END_REF]. Those particular ciphers allow in addition to the key, a public value called a tweak. Thus, related-tweakey differential attacks allow related-key differences but also related-tweak differences (i.e. differences in a pair of tweaks (T, T )). In differential attacks, two notions are considered: first, differentials where only the input and the output differences are known; and differential characteristics where each difference after each round is completely specified. A classical approach to evaluate the resistance against differential attacks is to compute the probability of the best differential characteristic of the cipher.

Finding optimal (related-tweakey) differential characteristics is a highly combinatorial problem that hardly scales. To limit this explosion, a common solution consists in using a truncated representation [START_REF] Knudsen | Truncated and Higher Order Differentials[END_REF] for which cells are abstracted by single bits that indicate whether sequences contain differences or not. Typically, each cell (i.e. byte or nibble) is Chapter 3 -Efficient Methods to Search for Best Differential Characteristics on SKINNY abstracted by a single bit (or, equivalently, a Boolean value). In this case, the goal is no longer to find the exact input and output differences, but to find the positions of these differences, i.e., the presence or absence of a difference for every cell. When a difference is present at the input of an S-box, we talk about an active S-box or an active byte/nibble. However, some truncated representations may not be valid (i.e., there do not exist actual byte values corresponding to these difference positions) because some constraints at the byte level are relaxed when reasoning on difference positions.

Hence, the optimal (related-tweakey) differential characteristic problem is usually solved in two steps [START_REF] Biryukov | Automatic Search for Related-Key Differential Characteristics in Byte-Oriented Block Ciphers: Application to AES, Camellia, Khazad and Others[END_REF][START_REF] Abdelkhalek | MILP Modeling for (Large) S-boxes to Optimize Probability of Differential Characteristics[END_REF]. In the first one, every differential byte is abstracted by a Boolean variable, denoted by ∆, that indicates whether there is a difference or not at this position, and we search for all truncated representations of low weight as the less differences passing through S-boxes there are, the more the probability is increased. Then, for each of these low weight truncated representations, the second step aims at deciding whether it is valid (i.e., whether it is possible to find actual cell values, denoted δ, for every Boolean variable) and, if it is valid, at finding the actual cell values that maximize the probability of obtaining the output difference given the input difference. Related Work. Many techniques have been proposed to search for the Step 1 solutions using automatic tools such as Boolean satisfiability (SAT) [SNC09; MP13], [START_REF] Sun | Automatic Search of Bit-Based Division Property for ARX Ciphers and Word-Based Division Property[END_REF] or Mixed Integer Linear Programming (MILP) [Sun+14; ST17; Bei+16] and Satisfiability Modulo Theories (SMT) [START_REF] Kölbl | Observations on the SI-MON Block Cipher Family[END_REF]. Dedicated solutions have also been proposed [START_REF] Matsui | On Correlation Between the Order of S-boxes and the Strength of DES[END_REF].

Regarding the search of the best instantiation of a truncated characteristic, most of the approaches were ad-hoc and dedicated to a precise cipher [Laf18; SWW18; FJP13b; BN10; Gér+18; ENP19]. Concerning the use of SAT solvers, [START_REF] Sun | More Accurate Differential Properties of LED64 and Midori64[END_REF] implements a SAT model for differential cryptanalysis based on Cryptominisat5 [START_REF] Soos | Extending SAT Solvers to Cryptographic Problems[END_REF] for Midori64 and LED64. This model implies a sufficiently small number of clauses to model the non-zero values of the DDT and to be applicable. However, no result concerning 8-bit S-boxes are given. As SAT uses Boolean formulas, it seems that the same problem than for MILP appears for modeling S-box: a huge number of Boolean formulas will be necessary to correctly model this step even if dedicated tools as Logic Friday or the Expresso algorithm [START_REF] Abdelkhalek | MILP Modeling for (Large) S-boxes to Optimize Probability of Differential Characteristics[END_REF] are used. In [START_REF] Abdelkhalek | MILP Modeling for (Large) S-boxes to Optimize Probability of Differential Characteristics[END_REF], 16 days are needed to find the best related tweakey differential characteristics on SKINNY-128 for the SK model. Recently, in [Ger+20; Gér+18], the authors introduce Constraint Programming (CP) models for Step 2 and the performance results are really promising regarding AES-192 and AES-256.

Our contribution. In this chapter, we refine the security bounds on the SKINNY-n tweak-able block cipher regarding differential cryptanalysis for the four following attack models according to the size of the tweakey: the SK model focuses on single-key attack, the TK1 model considers related-tweakey attack when the tweakey has only one component, the TK2 model in the related-tweakey settings considers 2 components and the TK3 model, 3 components.

To do so, we implement Step 1 using an ad-hoc method inspired from [START_REF] Fouque | Structural Evaluation of AES and Chosen-Key Distinguisher of 9-Round AES-128[END_REF]. We also propose a CP model for Step 2 taking as input the solutions outputted by Step 1. Thus, we provide, for the first time, the best differential related-tweakey characteristics up to 14 rounds for the TK1 model. We also consider the TK2 and TK3 models and we were able to find some differential characteristics up to 16 rounds for the TK2 model and up to 17 rounds for the TK3 model of SKINNY-128. However, we were not able to test all the solutions Step 1, and thus these differential characteristics are not necessarily optimal. This is an important improvement compared to previous results. For instance, in [LGS17] Liu et al. could only find the best differential characteristics up to 7 and 9 rounds for TK1 and TK2. Finally we also show there is no differential characteristic with probability higher than 2 -128 against 15 rounds in the TK1 model, 19 rounds for TK2 and 23 rounds for TK3. All those results clearly show that SKINNY is much more resistant to differential cryptanalysis than one would expect while counting the number of active S-boxes.

As a feedback, we also provide the time results we obtain when implementing the Step 1 using another tool, a MILP model for the 4 attack settings. As a result we show that MILP is not always the best choice. First, for Step 1, the ad-hoc method is able to surpass the MILP model. Second, the CP model proposed for Step 2 is incomparably much faster than the MILP model proposed in [START_REF] Abdelkhalek | MILP Modeling for (Large) S-boxes to Optimize Probability of Differential Characteristics[END_REF] that requires 16 days according their paper.

All the codes to reproduce these results can be found at [START_REF] Delaune | SKINNY with Scalpel Comparing Tools for Differential Analysis[END_REF].

Organization of the chapter. Section 3.1 gives a short description of SKINNY-n; Section 3.4 presents our Ad-Hoc tool and gives performance results comparing our Ad-Hoc model with a MILP one; Section 3.5 presents our dedicated modeling for Step 2 based on CP and analyzes the obtained results. Finally, some differential characteristics we found are given in the appendices (Appendix 3.A for SKINNY-64 and Appendix 3.B for SKINNY-128).

Cipher under study: SKINNY-n

In this section, we briefly review the tweakable block cipher SKINNY-n where n denotes the block size and can be equal to 64 or 128 bits. All the details that have been overlooked can be found in [START_REF] Beierle | The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS[END_REF].

As its name indicates, it enciphers blocks of length 64 or 128 bits seen as a 4 × 4 matrix of cells (nibbles for n = 64 or bytes for n = 128). We denote x i,j,k the cell at row i and column j of the internal state at the beginning of round k (i.e. 0 ≤ i, j ≤ 3 and 0 ≤ k ≤ r + 1 where r is the number of rounds depending on the tweak length and on the key length). SKINNY-n follows the TWEAKEY framework from [START_REF] Jean | Tweaks and Keys for Block Ciphers: The TWEAKEY Framework[END_REF]. SKINNY-n has three main tweakey size versions: the tweakey size can be equal to t = 64 or 128 bits, t = 128 or 256 bits and t = 192 or 384 bits and we denote z = t/n the tweakey size to block size ratio. Then, the number of rounds is directly derived from the z value: between 32 rounds for the 64/64 version up to 56 for the 128/384 version.

The tweakey state is also viewed as a collection of z 4×4 square arrays of cells (nibbles for n = 64 or bytes for n = 128). We denote these arrays T K1 when z = 1, T K1 and T K2 when z = 2, and finally T K1, T K2 and T K3 when z = 3. We also denote by T Kk i,j the nibble or the byte at position [i, j] in T Kk. Moreover, we define the associated adversarial model SK (resp. TK1, TK2 or TK3) where the attacker cannot (resp. can) introduce differences in the tweakey state.

One encryption round of SKINNY is composed of five operations applied in the following order: SubCells (SC), AddConstants (AC), AddRoundTweakey (ART), ShiftRows (SR) and MixColumns (MC) (see Fig. AddRoundTweakey. The first and second rows of all tweakey arrays are extracted and bitwise exclusive-ored to the cipher internal state, respecting the array positioning.

More formally, we have:

• x i,j = x i,j ⊕ T K1 i,j when z = 1, • x i,j = x i,j ⊕ T K1 i,j ⊕ T K2 i,j when z = 2, • x i,j = x i,j ⊕ T K1 i,j ⊕ T K2 i,j ⊕ T K3 i,j when z = 3.
Then, the tweakey arrays are updated. First, a permutation P T is applied on the cells positions of all tweakey arrays: if = 4 * i + j where i is the row index and j is the column index, then the cell is moved to position P T ( ) where P T = [9, 15, 8, 13, 10, 14, 12, 11, 0, 1, 2, 3, 4, 5, 6, 7]. Second, every cell of the first and second rows of T K2 and T K3 are individually updated with an LFSR on 4 bits (when n = 64) or on 8 bits (when n = 128) with a period equal to 15.

ShiftRows. The rows of the cipher state cell array are rotated to the right. More precisely, the second (resp. third and fourth) cell row is rotated by 1 position (resp. 2 and 3 positions).

MixColumns. Each column of the cipher internal state array is multiplied by the 4 × 4 binary matrix M :

        1 0 1 1 1 0 0 0 0 1 1 0 1 0 1 0        
Since 2016 and the birth of SKINNY-128, the cryptographic world never stopped trying to attack it. Among all the cryptanalysis results, we could cite the following ones in the related-tweakey settings and classified according the type of attacks. First, in [SQH19; Zha+20; LGS17], boomerang and rectangle related-tweakey attacks are considered. The best result is on 28 rounds with a complexity of 2 315 in time based on a boomerang distinguisher of 23 rounds in the TK3 scenario. Concerning impossible related-tweakey attack [START_REF] Sun | Analysis of AES, SKINNY, and Others with Constraint Programming[END_REF] LGS17], the best attack has 23 rounds using a distinguisher with 15 rounds in the TK2 scenario. Even if the distinguishers presented here have less rounds, they do not look at the same attack scenario. This work essentially goes further than [START_REF] Abdelkhalek | MILP Modeling for (Large) S-boxes to Optimize Probability of Differential Characteristics[END_REF] concerning the search of the best related-tweakey differential trails and aims at refining the best security bounds of SKINNY in this attack model.

Best known differential characteristics on SKINNY

Analysis concerning the differential characteristics of SKINNY already exist in the literature. The designers of SKINNY proposed the first analysis of security of the primitive done in their design paper. The first result concerning truncated differential characteristics were published in this occasion. The authors proposed a MILP model to compute the best truncated differential characteristic of SKINNY under the different tweakeys settings. In particular, they were able to reduce the search space of the differences in the tweakeys in the TK2 and TK3 settings. Details on this work are reviewed in Subsection 3.2.1.

In [START_REF] Liu | Security Analysis of SKINNY under Related-Tweakey Settings (Long Paper)[END_REF], Liu et al. proposed a more targeted analysis of the security of SKINNY in the TK models against boomerang and rectangle attacks. For their analysis, they need to know some differential characteristics for SKINNY-64 and SKINNY-128 in the different TK models. They were able to find some optimal differential characteristics for SKINNY-64 and some goods for SKINNY-128 which to the best of our knowledge were the best known before the work we realized. We review briefly the part of their work concerning differential characteristics in Subsection 3.2.2.

Finally, [START_REF] Abdelkhalek | MILP Modeling for (Large) S-boxes to Optimize Probability of Differential Characteristics[END_REF] proposed a way to integrate large S-boxes in MILP models with the S-boxes of AES and SKINNY-128. More importantly for us, their idea allows them to construct and run a MILP model searching for differential characteristics of SKINNY-128. They found with it the best differential characteristic for SKINNY-128 in the SK models for 13 rounds and prove that no differential characteristics with a better probability than 2 -128 exist for 14 rounds in the same model. Their work regarding SKINNY is explained in Subsection 3.2.3.

Best truncated differentail characteristics

To give a first idea of the security of SKINNY, its designer proposed a simple MILP model up to 30 rounds to search for the best truncated differential characteristics. Remarks that this model is the same for SKINNY-128 and SKINNY-64.

For a model searching the truncated characteristics, the only operations that need to be represented are the ShiftRows, the MixColumn and the AddRoundTweakeys (if there are differences in the keys). In their models, Bierle et al. have three sets of variables:

• {x k,i,j |i, j ∈ [0..3], k ∈ [0.
.r]} corresponding to the activity pattern of the internal state round by round. x k,i,j is the activity of the cell of row i and column j at round k: it is equal to 1 if there is a difference in the cell and 0 otherwise.

• {y k,i,j |i, jin[0..3], k ∈ [0.
.r]} corresponds to the activity pattern after the tweakeys are added to the state.

• {κ i,j |i, j ∈ [0..3]} corresponds to the initial activity pattern of the tweakey state.

With these variables, it is easy to see that the ShiftRows operations can be modeled in another constraint by using the correct indexes between the different variables. In addition, the two others are only composed of XOR operations. As a result, Bierle et al. decomposed them to their xor levels and used a classical way to model the xor of binary variables to obtain a complete model of SKINNY.

For SK and TK1, the model can be run directly with an objective of minimizing the number of x r,i,j that are equal to 1. For TK2 and TK3, Bierle et al. choose to not represent the activity patterns of each tweakeys but the one of their sum. This approach needs a lot less variables than modeling each activity pattern: going from 2 or 3 times 16r to 16r variables. Furthermore, they remark that cancellation could happened in the sums of the tweakeys but only a limited number of times (depending on the tweakey setting considered) for each cell (followed after the permutation of the tweakeys states). This limited number of cancellations appears from the updates by LFSRs of the second and third tweaks. For example, for TK2, if at round k the sums of the first and second tweakeys canceled, then at round k + 1 it cannot cancel again: since the first tweakey is unchanged (up to a permutation of the cells) whereas the second one was updated by a LFSR (up to the permutation of the cells). Or as the LFSR has a cycle length of 15, up to two cancellations can happen for the up to 30 rounds considered. The only difference in this model between TK2 and TK3 is the maximum number of cancellations for each cell: 2 for TK2 and 3 for TK3 for each of the original active cells in κ. It is however not clear with this modeling if the found bounds will be tight for TK1, TK2 and TK3. In our work, we keep the idea concerning the cancellations in our Step 1 process and build upon it (see details in Section 3.4). Running these models gave results to the designers of SKINNY that we give again here in

Result in related-tweakeys models

In their works on boomerang and rectangle attacks against SKINNY, they needed good differential characteristics for their analysis and proposed in their works to find them with different tools. The results they found are summarized in Table 3.2.

For SKINNY-64 , Liu et al. repurposed the MILP models of [START_REF] Liu | Security Analysis of SKINNY under Related-Tweakey Settings (Long Paper)[END_REF] and proceed in three steps:

1. Generate every truncated differential characteristics with exactly the minimum number AS min of active S-boxes for the given parameters;

2. Try to instantiate (with a MILP modeling of the 4-bit S-box) them and keep the best probability found p. If p = 2 -2AS min -i with i ∈ {0, 1, 2} then the solutions found are necessary optimal. Otherwise, do the third step;

3. Find all truncated differential characteristics with less than log 2 (p) 2 active S-boxes. Then, try to instantiate them with a MILP model. With this method, Liu et al. were able to find the optimal differential characteristics of SKINNY-64 up to 13 rounds in the different TKs settings. But they remark that it works as long as the number of truncated differential characteristics to consider is small (less than 5000). with MILP truncated differential characteristics. The dedicated algorithm begins with fixing the values of the (few) active cells in the initial tweakeys of the truncated solutions.

For

Then they compute the whole tweakey schedule. Once the tweakey schedule is known, it is easy to find differential characteristics or verify there is no differential. They run their methods only on a small number of truncated characteristics with a minimum of active S-boxes.

The best differential characteristic

As Liu et al. remark in [START_REF] Liu | Security Analysis of SKINNY under Related-Tweakey Settings (Long Paper)[END_REF], the fact that MILP cannot model 8-bit S-boxes (because it would be too costly) was admitted in the cryptographer community. Abdelkhalek et al. in [START_REF] Abdelkhalek | MILP Modeling for (Large) S-boxes to Optimize Probability of Differential Characteristics[END_REF] proved that it was in fact possible. Their work is an improvement of the MILP model of Sun et al. in [Sun+14] which proposed to search for truncated differential characteristics but used an elegant way to remove truncated solutions that do not correspond to existing differential characteristics. They add as a criteria for the MILP the existence of an instantiation by modeling only possible input/output differences and ignoring probability: the DDT is truncated in terms of probability: every non-zero entry is replaced by 1. They called this truncated version of the DDT the *-DDT.

In [START_REF] Abdelkhalek | MILP Modeling for (Large) S-boxes to Optimize Probability of Differential Characteristics[END_REF], Abdelkhalek et al. used the classical approaches to first compute the truncated differential characteristics with less than a target number of active S-boxes with a MILP model. Then, they searched again with a MILP model instantiation of the truncated characteristics. For the model of this second step, they reused the *-DDT to build a MILP model able to treat 8-bit S-boxes. They split the DDT of the 8-bit S-box over the different probabilities in different *-DDT. More precisely, for each probability p in the DDT, they create one *-DDT corresponding to every entry that has probability p. The non-zeroes entries being identical, they can be changed to 1. With this decomposition, they split the modeling of S-boxes transitions in value in two steps: a first constraint, representing the selection of a *-DDT or said in another manner, a constraint representing the choice of the probability of the transition and a second constraint selecting one precise transition with the selected probability. With this method, they were able to find the best differential characteristics (with a probability of 2 -123 ) for 13 rounds SKINNY-128 in the SK setting. Furthermore, they were able to prove no differential characteristic with a better probability than 2 -128 exists for 14 rounds in the SK setting.

Overview of the search method

During this PhD, we studied the search of differential characteristics with a very classical approach. In Subsection 3.3.1, we review this approach and give details on how we treat the different steps in Section 3.4 and Section 3.5. Subsection 3.3.2 is a digression on other tools that could be used for this approach and a brief argumentation to explain why we did not use them.

A classical approach

As said previously, we adopt a very classical approach to search for the differential characteristics of SKINNY. Just like [LGS17; Abd+17] for SKINNY or [GMS16; Ger+20] for AES, we use a two step process that we called Step 1 and Step 2:

• Step 1 consists in computing for a given number of rounds the truncated differential characteristics with a given number of active S-boxes. In our work, we proposed an ad-hoc tool to replace the MILP modeling done in previous works based on dynamic programming. We try other approaches to solve this step but keep only the ad-hoc tool to compute our results. Comments on the other approaches are found in Subsection 3.3.2. Details concerning our process are in Section 3.4.

• Step 2 searches for instantiation of truncated differential characteristics with better probability than a target p. Such an instantiation of a truncated solution gives us a better upper bound for the probability. In particular since the best S-boxes transitions of SKINNY-128 have a probability of 2 -2 , there were already rounds (represented with a lower opacity in Table 3.1) for which it is not necessary at all to search for a 3.3. Overview of the search method differential characteristic. The same reasoning can be followed for SKINNY-64 with 32 active S-boxes.

It is possible to automatize completely the exchange of informations between the first and second steps. In reality, we run our process manually by calling generating some truncated solutions then trying to instantiate them and if necessary go back to the Step 1. With our method, we obtained new optimal differential characteristics for the TKs settings and some good differential characteristics for TK2 and TK3 settings. The precise results concerning them obtained from our works can be found in Section 3.5.3.

The major contribution of our work was the way we implement the search for each step. More precisely, in Section 3.4, we explained in details how we search the truncated differential characteristics. Then, in Section 3.5 we give details on the way we treat the instantiation of the truncated differential characteristics we found in the first step.

About other tools

When we began working on this project, one of the goas was to study the efficiency of different types of tools for searching differential characteristics. We dropped this idea quite fast because such a comparison would need other targets than SKINNY, For Step 1. We tried different approaches to solve the Step 1 problem, including MILP, SAT and CP models.

Our SAT model is encoded through the high level modeling language MiniZinc while our CP model is based on the Choco-solver. Unfortunately, the results of both the SAT and the CP models are really bad: for example, for all instances greater than 16 rounds we were unable to obtain solutions in reasonable time. This is mainly due to the need to enumerate solutions for SAT, which implies to prohibit all solutions previously found. For CP, on the other hand, this has to do with the nature of the Boolean variables themselves where the Choco-solver can not efficiently propagate lower bounds and upper bounds on Boolean variables.

Our MILP model was much better than our SAT and CP ones. We started from the original model presented in [START_REF] Beierle | The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS[END_REF] but made several optimizations. First, we added constraints in the SK model to obtain all solutions up to column shifts in order to remove symmetries. Moreover, as the original model only describes the way to find the minimal number of active S-boxes, we added a constraint in each model to set a lower bound on the number of active S-boxes and thus, we were able to enumerate all the Step 1 solutions given a particular lower bound for the number of active S-boxes. Then, in the original MILP model all xor operations were modeled using dummy variables which is known to be inefficient. Thus we replaced the corresponding inequalities, using that x ⊕ y ⊕ z = 0 can be described with the three inequalities:

{x + y ≥ z}, {x + z ≥ y}, {y + z ≥ x}.
Finally, regarding the resolutions of the MILP models, the parallelization were left to the Gurobi solver.1

We compared the MILP model to our ad-hoc tool and we found that our MILP model is much slower in most cases and actually too slow to output all the Step 1 solutions needed to perform Step 2. Running times are given in Table 3 Note that while our ad-hoc tool gave very good running times, it may require a lot of memory to store the array C. For instance, for 30 rounds in TK3 mode, our tool required up to 500GB of RAM to finish the search. It is also important to note that it did not take fully advantage of the 128 cores of our server, and most often used less than 40 cores.

For

Step 2. With preliminary results with CP solver proving to be far faster than what exists up to now with MILP and with the complexity of building an efficient ad-hoc tool for Step 2, we basically only explored the uses of CP solver for this step of the search. All details of our method for the resolution of Step 2 can be found in Section 3.5.

Models and Results for Step 1

As explained in the introduction, in a first step called Step 1, we abstract each possible difference at cell (nibble or byte) level by a binary variable which symbolizes the presence/absence of a difference value at a given position of the cipher. The main concern regarding this step is the combinatorial explosion induced by the abstract XOR operation for which the sum of two non-zero values can lead to the presence or the absence of a difference.

Possible Transitions

Since the S-box is bijective and the ShiftRows operation only permutes cells, both those operations do not affect truncated differences. But for the AddRoundTweakey and MixColumns transformations we need to take care of the XOR operation. More precisely, given two truncated differences a and b we know that the possible values of (a, b, a ⊕ b) are:

(0, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1)

However we have to pay attention to uninstantiable solutions. For instance, given three truncated differences a, b and c, (1, 1, 1, 0, 0, 1) is a possible value for (a, b, c, a⊕b, a⊕c, b⊕c) but it is impossible to instantiate it because if a = b and a = c then b = c.

Hence we rewrite the equation y = MixColumns•AddRoundTweakey(x, k) to avoid such patterns:

• y

[1] = x[0] ⊕ k[0], • y[3] = y[1] ⊕ x[2], • y[0] = y[3] ⊕ x[3], • y[2] = x[1] ⊕ k[1] ⊕ x[3]
We experimentally verified that each truncated solution of this system can be instantiated.

Keyschedule. When looking at the key schedule of SKINNY at the cell level and for truncated differential characteristics it is mostly a simple cell permutation. In the model SK, there are no differences in the round keys. In the TKx models, differences in the round keys are possible. If the number of rounds targeted is at most 30, the rule for active cells on the round keys is quite simple: either the cell is inactive for all round keys, either it is active for all round keys but one (TK2) or two (TK3).

Ad-hoc Models for Step 1

To the best of our knowledge, the most efficient algorithm to search for truncated differential characteristics on SPN ciphers is the one described in [START_REF] Fouque | Structural Evaluation of AES and Chosen-Key Distinguisher of 9-Round AES-128[END_REF] by Fouque et al. which was applied on the 3 versions of AES. It is mostly dynamic programming as Round i is independent of the paths of rounds 0, 1, . . . , i-1 and at each step we only have to save, for each truncated state, the minimal number of active S-boxes to reach it. Hence, the complexity of this algorithm is exponential in the state size but linear in the number of rounds. The algorithm is specified in Algorithm 6. At the end of the algorithm we obtain an array C such that C[r][s] contains the minimal number of active S-boxes required to reach state s after r rounds. Retrieving the truncated representations is then done quite easily using C, starting from the last state to the first. Let say we want to exhaust all truncated differential characteristics on R rounds with at most b active S-boxes ending with state s. From C[R -1][s], we know whether such characteristic exists or not. If

C[R -1][s] ≤ b
we exhaust all states s such that the transition s → s through one round is possible and, for each of them, we now need to exhaust all truncated differential characteristics on R -1 rounds with at most b -|s| active S-boxes ending with state s .

The complexity of the algorithm in the single key model is very low, and we experimentally counted around (R -1) × 2 20 simple operations for R rounds. A naive solution to search for truncated representations in the TK1, TK2 and TK3 models would be to apply the previous algorithm for each possible configuration of the key. While for TK1 this would only increase the overall complexity by a factor 2 16 , the search would not be practical for both the TK2 and TK3 models. Indeed, because of the possible cancellations occurring in the round keys, the number of configurations is very high:

  8 k=0 8 k tk-1 i=0 (R -1)/2 i k     8 k=0 8 k tk-1 i=0 (R -1)/2 i k   .
For instance, for R = 30, there are more than 2 64 configurations in the TK2 model.

In the following we present the first practical algorithm which tackles down the problem for the TK models without relying on a black box solver as MILP, SAT or CP solvers. Actually this is the only algorithm fast enough to generate all the Step 1 solutions required 86

Models and Results for Step 1

Algorithm 6 Search for the best truncated representation (SK). end for 17: end for 18: Return C to perform the Step 2. Indeed, the best differential characteristic is rarely based on the truncated differential characteristics minimizing the number of active S-boxes and thus we need to generate a large number of truncated characteristics to find the one instantiating with the best probability. As we will explain in Section 3.3.2, all other approaches we tried to generate them failed.

The idea of our ad-hoc method is quite similar to the one used in the single key model. Actually, to compute the minimal number of active S-boxes at round r + 1 we only need to know the minimal number of active S-boxes for each possible state at round r together with the number of cancellations for each key cell occurred so far. Indeed, we do not need to know at which rounds the cancellations occurred but only how many times they did. A simplified version of this algorithm is described in Algorithm 7. The most important part is related to the variable cancelled which count how many times each key cell is cancelled through the encryption. It is a vector of 16 cells, each cell taking values among {0, 1, . . . , x -1, r} for the TKx model. The main advantage of our representation is that at each step of the algorithm, C[r][s] contains at most (x + 1) 16 elements for the TKx model which is much lower than the number of possible sequences of round keys.

Finally we introduce a new improvement which greatly speeds up the search procedure. It is based on the so-called early abort technique principle and the idea is to handle the key cell by cell. Indeed, we expect that the best truncated differential characteristics do not involve many active cells in the round key and so we want to quickly cut those branches during the search. To do so we first pick a key cell and guess whether it is active or not. At this step we have not decided yet if any cancellations occur nor their positions but only if it is always 0 or at least once 1. Then we apply the algorithm partially and guess another key cell if and only if it seems possible to find a truncated differential characteristic with a small enough number of active S-boxes. More precisely, along the search we have the relation y = x ⊕ k where k is the round key. We introduce a new 16-bit variable g such that g i = 0 if we made a choice for bit i of k and 1 otherwise. To compute the possible truncated transitions from x to y through k for all the possible key (according to g) we can restrict ourself at looking at the possible truncated transitions from (x|g) to y through (k|g) where | is the bitwise OR. Indeed, we use the fact that in truncated setting 1 ⊕ 1 is 0 or 1 and thus our technique allows to handle all the possible keys by looking only at few transitions.

Modeling Step 2 with CP

The aim of Step 2 is to try to instantiate the abstracted solutions provided by Step 1 while maximizing the probability of the differential characteristic. Thus, Step 2 takes as input a solution of Step 1 with the objective function of maximizing the probability of the differential characteristic. However, some solutions of Step 1 could not be instantiated in Step 2 as refining the abstraction level of Step 2 will induce non-consistent solutions. In the literature, this step has been modeled using ad-hoc methods [START_REF] Biryukov | Automatic Search for Related-Key Differential Characteristics in Byte-Oriented Block Ciphers: Application to AES, Camellia, Khazad and Others[END_REF], MILP [START_REF] Abdelkhalek | MILP Modeling for (Large) S-boxes to Optimize Probability of Differential Characteristics[END_REF], SAT [START_REF] Sun | More Accurate Differential Properties of LED64 and Midori64[END_REF] or CP [START_REF] Gerault | Computing AES related-key differential characteristics with constraint programming[END_REF]. As MILP [START_REF] Abdelkhalek | MILP Modeling for (Large) S-boxes to Optimize Probability of Differential Characteristics[END_REF] and SAT [START_REF] Sun | More Accurate Differential Properties of LED64 and Midori64[END_REF] seem to hardly scale due to prohibitive computational times (linked with the size of the 8-bit S-boxes that must be represented in the form of linear inequalities or of clauses), we focus here on a dedicated CP method implemented using the Choco solver [START_REF] Prud'homme | Choco Documentation[END_REF]. We also provide, in the second part of this section, the results we obtain when instantiating the differential characteristics in the 4 attack scenarios.

Constraint Programming

Although less usual than MILP to tackle cryptanalytic problems, CP has already been used in e.g. [GMS16; ENP19]. We recall some basic principles of CP and we refer the reader to [START_REF] Rossi | Handbook of Constraint Programming[END_REF] for more details.

CP is used to solve Constraint Satisfaction Problems (CSPs). A CSP is defined by a triple (X, D, C) such that X = {x 1 , x 2 , . . . , x n } is a finite set of variables, D is a function that maps every variable x i ∈ X to its domain D(x i ) and C = {c 1 , c 2 , . . . , c m } is a set of constraints. D(x i ) is a finite ordered set of integer values to which the variable x i can be assigned to, whereas c j defines a relation between some variables vars(c j ) ⊆ X. This relation restricts the set of values that may be assigned simultaneously to vars(c j ). Each constraint is equipped with a filtering algorithm which removes from the domains of vars(c j ), the values that cannot satisfy c j .

In CP, constraints are classified in two categories. Extensional constraints, also called table constraints, explicitly define the allowed (or forbidden) tuples of the relation. Intentional constraints define the relation using mathematical operators. For instance, in a CSP with X = {x 1 , x 2 , x 3 } such that D(x 1 ) = D(x 2 ) = D(x 3 ) = {0, 1}, a constraint ensuring that the sum of the variables in X is different from 1 can be either expressed in extension (1) or in intention (2):

1. Table ( x 1 , x 2 , x 3 , (0, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1) )

Chapter 3 -Efficient Methods to Search for Best Differential Characteristics on SKINNY 2.

x 1 + x 2 + x 3 = 1
Actually, any intentional constraint can be encoded with an extensional one provided enough memory space, and conversely [START_REF] Demeulenaere | Compact-Table: Efficiently Filtering Table Constraints with Reversible Sparse Bit-Sets[END_REF]. However, they may offer different performances.

The purpose of a CSP is to find a solution, i.e. an assignment of all variables to a value from their respective domains such that all the constraints are simultaneously satisfied. When looking for a solution, a two-phase mechanism is operated: the search space exploration and the constraint propagation. The exploration of the search space is processed using a depth-first search. At each step, a decision is taken, i.e. a non-assigned variable is selected and its domain is reduced to a singleton. This modification requires to check the satisfiability of all the constraints. This is achieved thanks to constraint propagation which applies each constraint filtering algorithm. Any application may trigger modifications in turn; the propagation ends when either no modification occurs and all constraints are satisfied or a failure is thrown, i.e., at least one constraint cannot be satisfied. In the former case, if all variables are assigned, a solution has been found. Otherwise a new decision is taken and the search is pursued. In the latter case, a backtrack to the first refutable decision is made and the search is resumed.

Turning a CSP into a Constrained Optimisation Problem (COP) is done by adding an objective function. Such a function is defined over variables of X, the purpose is then to find the solution that optimizes the objective function. Finding the optimal solution is done by repeatedly applying the two-phase mechanism above, and by adding a cut on the objective function that prevents from finding a same cost solution in the future.

Modeling Step 2 with CP

Given a Boolean solution for Step 1, Step 2 aims at searching for the byte-consistent solution with the highest (related-tweakey) differential characteristic probability (or proving that there is no byte-consistent solution). In this section, Model 1 describes the CP model we used for SKINNY-128 (SK). Actually, the ones used to model the other variants, as well as SKINNY-64 are rather similar.

For each Boolean variable ∆X r,i,j of Step 1, we define an integer variable δX r,i,j . The domain of this integer variable depends on the value of the Boolean variable in the Step 1 solution: If ∆X r,i,j = 0, then the domain is D(δX r,i,j ) = {0} (i.e., δX r,i,j is also assigned to 0); otherwise, the domain is D(δX r,i,j ) = [1, 255]. For each byte that passes through an S-box, we define an integer variable δSB r,i,j which corresponds to the difference after the S-box. Its domain is {0} if ∆X r,i,j is assigned to 0 in the Step 1 solution; otherwise, it is D(δSB r,i,j ) = [1,255]. This is expressed in (3.3) of Model 1.

Finally, as we look for a byte-consistent solution with maximal probability, we also add an integer variable P r,i,j for each byte in an S-box: this variable corresponds to the absolute value of the base 2 logarithm of the probability of the transition through the Sbox. Actually, a factor 10 has been applied to avoid considering floats. Thus we define a Table constraint (3.4) composed of valid triplets of the form (δX r,i,j , δSB r,i,j , P r,i,j ). Note that these triplets only contain non-zero values and that P r,i,j takes only 2 different values for the 4-bit S-box (SKINNY-64) and 7 different values for the 8-bit S-box (SKINNY-128). There are roughly 2 14 triplet elements in the Table constraint for the SKINNY-128 case. As the S-box layer is the only non-linear layer, the other operations could be directly implemented in a deterministic way at the cell level. The associated constraints thus follow the SKINNY-128 linear operations. When possible, i.e. when one element is known to be zero, we replace XOR constraints (encoded using Table constraints) by a simple equality constraint. This corresponds to Table constraints (3.5), (3.6), (3.7) and (3.8) in Model 1.

The overall goal is finally to find a byte-consistent solution which maximizes differential characteristic probability. Thus, we define an integer variable Obj Step2 to minimize the sum of all P r,i,j variables (3.1). This value mainly depends on the number of S-boxes outputted by Step1 Obj Step1 and can be bounded to [[20 • Obj Step1 , 70 • Obj Step1 ]] (3.2).

The differences for the models TK1, TK2 and TK3 are the modeling of the XORs induced by the lanes of the tweakey through XOR table constraints. Each XOR constraint depicted in Model 1 provides high quality filtering but requires 65536 tuples to be stored which results in prohibitive memory usage. This may limit the number of threads that can be used for the resolution, which was the case for TK2 and TK3. To get around this issue, we encoded the XOR constraint in intention (by defining filtering rules), providing a more memory efficient algorithm, at the expense of filtering strength (see Model 2). It can be sum up as using the two most constraint variables to sieve the reachable values for the third variable. This last choice was applied for TK2 and TK3 (SKINNY-128 only). We also rely on Table constraints to model the LFSRs applied on TK2 and TK3.

Concerning the search space strategy, for the TK2 and the TK3 attack settings, the Step 1 only outputs the truncated value of the sum of the T Ki. Thus, the search space strategy first looks at the cancellation places of the sum of the T Ki and then instantiates

X C = ∀x ∈ X A , ∀y ∈ X B X C = X C {x ⊕ y} X C = X C X C (3.9)
the T Ki values according to those positions. For the TK1 setting, we simply apply the default Choco-solver strategy.

Concerning the parallelization, we affect one solution outputted by Step 1 per thread and we share between the threads the value of Obj Step2 .

Step 2 Performance Results

We run our Step 2 model on the two versions of SKINNY (SKINNY-64 and SKINNY-128) using our CP models written in Choco-solver. We conduct all our experiments on our server composed of 2× AMD EPYC 7742 64-Core and 1TB of RAM. All the reported times are real system times.

Up to our knowledge, we only found [START_REF] Abdelkhalek | MILP Modeling for (Large) S-boxes to Optimize Probability of Differential Characteristics[END_REF] that gives time results concerning finding the best SK differential characteristic probability on SKINNY-128 using a MILP tool based on Gurobi.

More precisely, the authors say: "In our experiments, we used Gurobi Optimizer with Xeon Processor E5-2699 (18 cores) in 128 GB RAM." and, for 13 rounds, "in our environment, the test of 6 classes [Step 1 solutions with 58 active S-boxes without symmetries] finished in 16 days. Finally, it is proven that the tight bound on the probability of differential characteristic for 13 rounds is 2 -123 " in the SK model.

Regarding the TK models, the best known results were obtained by Liu et al. also using MILP models [START_REF] Liu | Security Analysis of SKINNY under Related-Tweakey Settings (Long Paper)[END_REF]. They could only find the best differential characteristics up to 7, 9 and 13 rounds for TK1, TK2 and TK3 respectively.

Results for SKINNY-64.

We sum up in Table 3.5 all the results we obtain for SKINNY-64 in the four different attack models (SK,TK1,TK2 and TK3). The overall time, in this case, is not a bottleneck.

We only give results concerning number of rounds that are at the limit (just under and just upper) when regarding the number of active S-boxes which is equal to 32 in the case of SKINNY-64 as the state size is 64 bits and as the best differential probability of the S-box is equal to 2 -2 . Thus, the best overall differential characteristic probability must be under 2 -64 .

Note that sometimes, we need to browse several Obj Step1 bounds to find the optimal differential characteristic probability when the number of rounds is fixed. Indeed, we need to proactively adapt the probability bound we found. For example, in the case of TK2 SKINNY-64 with 13 rounds, the optimal Obj Step1 is equal to 25 and when providing the Step 2 process with this Obj Step1 bound, we find a best differential characteristic probability equal to 2 -55 . Thus, we need to enumerate all the Step 1 solutions with Obj Step1 = 26 and Obj Step1 = 27 to be sure that the previous probability is really the best one. Then, before running again Step 2 on those new results we adapt the best probability to the new bound equal to 2 -55 instead of the old bound equal to 2 -64 .

We also provide in Appendix 3.A the details of the best found differential characteristics. Results for SKINNY-128.

Nb Rounds Obj

In the same way, we provide in Table 3.6 the best differential characteristic probability with the total time required for this search for the 4 different attack models. As one can see, we also verify all the possible values for Obj Step1 for a given number of rounds, depending on the probability value previously found. Thus, this time, the number of solutions outputted by Step 1 could be huge when we move away from the optimal Step 1 value v * . However, as the time spent to solve one solution is reasonable (at least when considering SK and TK1), our model scales reasonably well: the worst case requires 25 days of real time on our server on 8 threads and 31 GB of RAM 2 . Our TK2 and TK3 models are based on XOR constraints encoded in intention (and not using tables) and these experiences have been launched using the 128 threads of our server.

Concerning TK2 and TK3, we were not able to perform all the computations due to the huge number of Step 1 solutions. Hence we decided to handle only the Step 1 solutions with exactly one active byte in the round keys in order to limit the number of truncated characteristics to instantiate. Those results are given in Table 3.7. We provide in Appendix 3.B the best TK2 differential characteristic we found for 16 rounds, and the best TK3 differential characteristic we found for 17 rounds. Note that we do not know if these differential characteristics are optimal in terms of probability as we were not able to test all the solutions Step 1.

Lessons learnt.

The overall gap is not to find the optimal value of Obj Step1 = v * for a given number of rounds and to enumerate the corresponding overall solutions if the Step 1 model is sufficiently tight. The real gap is if the value obtained for Obj Step2 (here equal to 2 × v * as the best differential probability for the S-box is equal to 2 -2 ) is far from the optimal bound then we have to increase Obj Step1 up to the bound Obj Step2 /2 . Further we are from v * in the Step 1 resolution, more numerous are the Step 1 solutions (in fact this number grows exponentially as could be seen in Table 3.6). Thus, the time for the Step 2 resolution becomes the bottleneck.

Conclusion

In this chapter, we improve the security bounds regarding differential characteristics search on the block cipher SKINNY. As usually done, we have divided the search procedure into two steps: Step 1 which abstracts the difference values into Boolean variables 2. It seems that the use of the 128 threads was prohibited by the memory usage of XOR tables (i.e. XOR in extension).

and finds the truncated characteristics with the smallest number of active S-boxes; and

Step 2 which inputs the results of Step 1 to output the best possible probability instantiating the abstract solutions outputted by Step 1. Of course, each solution of Step 1 could not always be instantiated in Step 2.

For Step 1, an ad-hoc method which heavily uses the structure of the problem is proposed. For solving Step 2, we have implemented a Choco-solver model. Regarding

Step 2, our Choco-solver model is much faster than any other approaches. It allowed us to find, for the first time, the best (related-tweakey) differential characteristics in the TK1 model up to 14 rounds for SKINNY-128 and to show there is no differential trail on 15 rounds with a probability better than 2 -128 . Regarding the TK2 model, we were able to find the best differential trails up to 16 rounds. For TK3, we are able to exhibit a differential characteristic up to 17 rounds. Note that in [LGS17] Liu et al. were only able to reach 7 and 9 rounds in the TK1 and TK2 model respectively. Our approach is thus an important improvement.

3.A Best (related-tweakey) differential characteristics for SKINNY-64

The best SK differential characteristics on 7 rounds of SKINNY-64 with probability equal to 2 -52 is given in Table 3.8. The best TK1 differential characteristics on 10 rounds of SKINNY-64 with probability equal to 2 -46 is given in Table 3.9. The Best TK2 differential characteristics on 13 rounds of SKINNY-64 with probability equal to 2 -55 is given in Table 3.10. Best TK3 differential characteristics on 15 rounds of SKINNY-64 with probability equal to 2 -54 is given in Table 3

CONCLUSION

In this thesis, we have presented our works on the uses and constructions of different algorithms for differential cryptanalysis from the study of particular and general primitives and we have revisited an attack.

In Chapter 1, we revisit the fast near collision attack (FNCA), a new generic attack for stream ciphers applied successfully by their authors against Grain v1 and A5/1. The FNCA is an internal state recovery attack based on divide-and-conquer strategy applied with a near collision property on the targeted stream ciphers. The divide-and-conquer strategy begins with splitting the internal state in two parts: the crucial part (CP) which is recovered by leveraging the near collision property with the new self-refined method proposed for the FNCA and the rest part (RP) which is efficiently computable when the CP is known. In our work as presented in Chapter 1, we show that the self-refined method has an incorrectly evaluated complexity by Zhang et al.. We proved this error doubly by first exhibiting the incorrect theorem in the work of Zhang et al. and proposed a corrected version and used it to compute the real complexity of the attacks proposed by Zhang et al.. The second way we proved the error in the FNCA is by using some information theory elements in an absurd reasoning: if the FNCA was correct, we should be able to observe some bias in the distribution of the internal state after the initialization phases of the stream ciphers. We ran several experiments with some simple codes to disprove the existence of those bias and so proved that the FNCA cannot be correct (regarding its claim complexity).

Chapter 2 presents our work concerning the diffusion round of Generalized Feistel networks of type 2. We built an efficient algorithm based on our new characterization of the diffusion round that constructs optimal even-odd permutations or gives better lower bounds for GFN of up to 42 branches (although our analysis is still valid for bigger cases, the computation cost becomes too great). More precisely, our characterization can be used to directly exhaust every optimal even-odd solutions up to 26 branches and the efficient algorithm is used for GFNs between 28 and 42 branches. For these values, we found optimal even-odd permutations for 28, 30, 32, 34 and 36 branches which were unknown to the best of our knowledge with a diffusion round of 9 except for the 34 branches case which has a diffusion round of 10. For the other cases, we prove that the best evenodd permutations have a diffusion round of at least 10 and found permutations with a diffusion round of 11 without ensuring the optimality of the results. However, the optimal permutations have a worse differential resistance than non-optimal (with a diffusion round of one more) permutations as remarked in the selection of the permutation in WARP, a new Feistel primitive [START_REF] Banik | WARP: Revisiting GFN for Lightweight 128-bit Block Cipher[END_REF].

In Chapter 3, we show how we were able to obtain better and sometimes the best differential characteristics for SKINNY in the different attacker settings namely single key, one tweakey, two tweakeys and three tweakeys. We used in our analysis a very classical approach of splitting the search of differential characteristics in two: computing good truncated differential characteristics for SKINNY (Step1) and trying to instantiate them in values (Step2). In addition to the new differential characteristics we found, this work offers two major contributions. For Step1, we developed a new algorithm to compute efficiently truncated differential characteristics with dynamic programming. More precisely, we leveraged that a differential characteristic can be seen as a smaller differential characteristic extended by one round and that not all information must be remembered for this smaller differential characteristic in this problem. The Step2 process used a Constraint Programming solver which allows for a straightforward modeling of SKINNY in particular for the S-box compared to previous works using MILP or SAT. Our contribution concerning Step2 is the precise search strategy given to the solver to be more efficient in the search. With the way we implement the two steps search, we were able to find again the best differential characteristics for SKINNY-64 in a few seconds and for SKINNY-128 in the SK setting and to find for the first time the best differential characteristic for SKINNY-128 in the TK1 setting. We also gave new results for in TK2 and TK3 settings, optimal up to 12 and 13 rounds and better than previously known up to 16 and 17 rounds respectively. The next step for the automation of the search of differential characteristics is to give a description of the cipher and to have the whole analysis done by the computer in this work corresponding to the creation of the models. TAGADA [START_REF] Libralesso | Automatic Generation of Declarative Models for Differential Cryptanalysis[END_REF], a Tool for Automatic Generation of Abstraction-based Differential Attacks proposes to do exactly this automatic generation of models but is still in development. Nous commençons par revisiter les attaques rapides par collision proche publiées en 2018. Nous prouvons avec des algorithmes inspirés de la théorie de l'information que la complexité de ces attaques était sérieusement sous-estimée et donnons la version corrigée.

Nous proposons ensuite une nouvelle caractérisation d'un aspect particulier des réseaux de Feistel. Elle nous permet de déduire un algorithme efficace pour trouver (construire) les permutations optimales en ce sens, apportant ainsi une solution à un problème vieux de 10 ans.

Nous terminons avec l'utilisation de solveurs, des algorithmes généraux prenant en entrée la description d'un problème et renvoyant en sortie une solution à celui-ci pour le calcul de meilleures caractéristiques différentielles du chiffrement par bloc SKINNY.

Title: Algorithms for differential cryptanalysis

Keywords: Cryptography, Symmetric cipher, Differential cryptanalysis

Abstract:

Security in symmetric cryptography seems to be a vague notion for non specialists. To simplify the reasoning done by cryptanalysts, a symmetric primitive is secured when no practical attack have been found against it. A large part of the security demonstration of a primitive consists in trying every classical attack against the studied primitives. In this thesis, we review our cryptanalysis works with this idea by using different algorithms to construct or test our results.

We begin by revisiting the fast near collision attacks proposed in 2018. We proved with test algorithms inspired by information theory that the complexity of this attack is se-riously underestimated and gave the correct estimation.

We then gave a new characterization of a particular property of Feistel networks. It allowed us to build a new efficient algorithm to find the optimal permutations (for this property) solving with the constructed permutations a 10 year old problem.

We end this document with the use of solvers, generic algorithms taking a description of a problem in input and returning as output a solution to this problem. In this work, they are used to compute better differential characteristics of the block cipher SKINNY.

Figure 1 -

 1 Figure 1 -Exemple de chiffrement de Vigenère. La table haute donne la correspondance entre les lettres en clair ( colonne ), les lettres de la clé ( ligne ) et le chiffré ( entrée ). La table basse donne le chiffrement de « LOREM IPSUM DOLOR SIT AMET » avec la clé « LATIN ».

Définition 0. 1

 1 (Chiffrement). Une fonction de chiffrement est une fonction E : F * 2 ×F * 2 → F * 2 telle que pour toute clé dans F * 2 , la fonction E(clé, •) est une surjection et son inverse D(clé, •) peut être efficacement calculé lorsque la clé est connue.

Figure 3 -

 3 Figure3-Chiffrement jouet avec une permutation orientée au niveau des bits de[START_REF] Jean | TikZ for Cryptographers[END_REF]

Figure 5 -Figure 6 -

 56 Figure 5 -Schéma d'un chiffrement par flot générique

Figure 9 -

 9 Figure9-Toy SPN with a bit oriented permutation layer. From[START_REF] Jean | TikZ for Cryptographers[END_REF]

Theorem 1. 2 (

 2 Corrected version). Let V be a set and let draw uniformly at random a collection (U i ) of subsets of V . Let F i = k≤i U k . Then on average the following relation 29 Chapter 1 -Revisiting the Fast Near Collision Attack holds:

  0

  for i = 0 to 227 do Keystream generation 10:

1. 3 .

 3 Fast Near Collision on A5/1 Proposition 1.1. Given a 5-bit keystream output k, there are exactly 2 28 values for the 33 bits of the CP part leading to k. Proof. The 33 bits of the CP part can be divided into two groups: one composed of 15 bits (R1[4...8], R2[6..10] and R3[6...10]) used only to determine the clocking sequence and one composed of 18 bits (R1[13..18], R2[16...21], R3[17.

Chapter 1 -

 1 Revisiting the Fast Near Collision Attack Algorithm 3 Experiment 1: sample a 128-bit word key from /dev/rand Setup 2: initialize a 128-bit word counter at 0 3: initialize a 2 33 array called configuration; 4: for i = 0 to 2 36 do Experiment 5: random = AES-CTR(key, counter) and increase counter 6: extract from random one A5/1-key, keyExp and one A5/1-frame, frameExp 7: do an A5/1 initialization with keyExp and frameExp 8: select the 33-bit of the CP part of the obtained internal state 9: increment the corresponding field in configuration 10: end for 11: Output configuration

Figure 1 . 2 -

 12 Figure 1.2 -One diagram represents the number of 33-bit CP part values (in log scale) from experimental data in ordinates that are reached exactly x times on the horizontal axe. The experimental data for the two red diagrams are generated as described in Algorithm 3 with 54-bit keys for the left one and 64-bit keys for the right one. The experimental data of the blue diagram comes from directly randomly generating the 33-bit CP part of the A5/1 internal state.

bFigure 1 . 3 -

 13 Figure 1.3 -Simple representation of the grain v1 cipher

  Figure 1.4 -Histogram plotting how many times each of the 2 10 possible two successive input of the function h were reached after 2 30 Grain v1 initialization using random key and iv values.

Figure 2

 2 Figure 2.2 -Propagation tree for 7 rounds (minus the last application of π)

Figure 3

 3 Figure 3.1 -the SKINNY round function with its five transformations [Jea16].

1:

  for each state s do 2: M [s] ←-list of states s reachable from s through one round 3: end for 4: for each state s do 5: C [0] [s] ←-number of active cells of s 6: end for 7: for 1 ≤ r < R do 8: foreach state s do C [r] [s] ←-∞ 9: for each state s do 10: for each state s in M [s] do 11: c ←-C [r -1] [s] + number of active cells of s 12: if c < C [r] [s ] then 13: C [r] [s ] ←-c

  88

3. 4 .Algorithm 7

 47 Models and Results forStep 1 Search for the best truncated representation (TK).

1:

  for each state s, round key k do 2: M [k] [s] ←-list of states s reachable from s and k through one round 3: end for 4: for each state s do 5: C [0] [s] ←-{(number of active cells of s, 0)} 6: end for 7: for r = 1 doR -1 8: foreach state s do C [r] [s] ←-∅ 9: for each state s do 10: for each (cost, cancelled) ∈ C [r -1] [s] do 11: for each round key k compatible with cancelled do 12: for state s in M [k] [s] do 13: c ←-cost + number of active cells of s 14: C [r] [s ] ←-C [r] [s ] ∪ {(c, update(cancelled, k))} foreach state s do keepOptimals(C [r] [s]) 20: end for 21: Return C

  94

3. 5 .

 5 Modeling Step 2 with CP Model 2 The XOR constraint in intention Model for a ⊕ b ⊕ c = 0 with a, b, c ∈ X A , X B , X C where a and b are more constraint than c.

Titre:

  Algorithmes pour la cryptanalyse différentielle Mot clés : Cryptographie, Chiffrement symétrique, Cryptanalyse différentielle Résumé : La sécurité en cryptographie symétrique semble être une notion très floue pour des non-spécialistes du domaine. Pour simplifier le raisonnement fait par les cryptanalystes, une primitive symétrique est sûre lorsqu'aucune attaque pratique n'est trouvée contre celle-ci. Une grande part de cette démonstration consiste à essayer des attaques classiques contre les différentes primitives existantes. Dans cette thèse, nous présentons nos travaux de cryptanalyse dans cette optique en utilisant différents algorithmes constructifs ou algorithmes de test.

  ECB) où le message est simplement découpé en blocs, chacun chiffré individuellement avec la même clé. Malheureusement, bien que très simple de conception, ce mode n'offre pas de sécurité contre la manipulation de chiffré pour ne nommer que cette attaque : échanger la position de deux blocs crée un chiffré valide sans connaissance de la clé.

Le premier usage des modes d'opération est d'étendre l'utilisation des chiffrements par bloc à des messages de taille supérieure à celle du bloc. Le mode d'opération le plus naïf pour les chiffrements par bloc est le mode Elecxiii tronic CodeBook (

  al. pour tester des composants de leur attaque. Nous nous sommes donc attelés à la réévaluation des complexités en corrigeant les théorèmes utilisés pour leurs calculs et en vérifiant expérimentalement qu'aucun biais existant ne pouvait expliquer les complexités annoncées par Zhang et al.. Nous donnons aussi les complexités corrigées des FNCAs prouvant donc que Zhang et al. ont sérieusement sous-estimé le coût réel de leur attaque. Ces travaux ont été publiés à FSE : Patrick Derbez, Pierre-Alain Fouque et Victor Mollimard, "Fake Near Collisions Attacks", in : IACR Transactions on Symmetric Cryptology 2020.4 (déc. 2020), p. 88-103, doi : 10.46586/tosc.v2020.i4.88-103, url : https://tosc.iacr.org/index.

	php/ToSC/article/view/8749

III.iii Méthodes efficaces pour la recherche des meilleures caractéristiques différentielles de SKINNY SKINNY est une famille de SPNs paramétrables créée en 2016 par Beierle et al. [Bei+16]. Six versions de SKINNY existent groupées en deux familles dépendentes de la taille de l'état interne : SKINNY-64 et SKINNY-128 utilisant respectivement des états internes de 64 et 128 bits. Pour donner une première idée de la sécurité contre la cryptanalyse différentielle, ses créateurs ont inclus dans le papier des spécifications [Bei+16] un modèle pour

	quelques caractéristiques pour étudier la résistance de SKINNY contre les attaques boome-
	rangs et rectangles dans le cas des clés paramétrées reliées. En utilisant un modèle MILP
	pour SKINNY-64 et un outil ad hoc pour SKINNY-128, ils ont trouvé les meilleures caracté-
	ristiques différentielles jusqu'à 13 tours pour SKINNY-64 et de meilleures caractéristiques
	pour SKINNY-128 pour un petit nombre de tours ( mais sans l'optimalité ).
	L'autre publication concernant les caractéristiques de SKINNY que nous avons trouvée
	dans la littérature a été publiée par Abdelkhalek et al. dans [Abd+17]. Ils construisent Introduction et Résumé en français	v
	les meilleures caractéristiques différentielles de SKINNY-128 dans le modèle de clé simple I Chiffrement symétrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
	jusqu'à 13 tours avec un modèle MILP contenant une description efficace jugée inexistante I.i Chiffrement par bloc . . . . . . . . . . . . . . . . . . . . . . . . . . ix
	pour les boites-S de 8 bits. Ils montrent en plus qu'aucune caractéristique différentielle I.ii Chiffrement par flot . . . . . . . . . . . . . . . . . . . . . . . . . . . xii
	avec une meilleure probabilité que 2 -128 n'existe pour 14 tours ( et plus ) dans le modèle I.iii Mode d'opération . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii
	28, 30, 32, 34 et 36 branches ainsi que des bons candidats Analyse et sécurité des chiffrements symétriques . . . . . . . . . . . . . . . xiv de la clé simple. II
	pour l'optimalité pour 38, 40 et 42 branches. Ces travaux ont été publiés à FSE : Dans nos travaux, nous complétons les bornes sur les caractéristiques différentielles de II.i Modèle de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv
	Patrick Derbez et al., "Efficient Search for Optimal Diffusion Layers of Generalized SKINNY en utilisant une approche très classique qui sépare la recherche en deux étapes. La II.ii Distingueur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi
	Feistel Networks", in : IACR Transactions on Symmetric Cryptology 2019.2 (juin 2019), première étape consiste à chercher des caractéristiques différentielles tronquées ayant un II.iii Cryptanalyse différentielle . . . . . . . . . . . . . . . . . . . . . . . xvi
	p. 218-240, doi : 10.13154/tosc.v2019.i2.218-240, url : https://tosc.iacr.org/ nombre de boites-S actives égal ou inférieur à une cible donnée. La seconde étape prend III Résumé des chapitres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xix
	index.php/ToSC/article/view/8321 les résultats de la première et essaye d'instancier en valeur les caractéristiques tronquées. III.i Revisiter les attaques rapides par collision proche . . . . . . . . . . xix
	Notre contribution dans ces travaux, outre la publication de meilleures bornes, est l'uti-III.ii Recherche efficace de couche de diffusion pour les réseaux de Feistel
	lisation adaptée d'outils pour chacune des étapes. La première étape est réalisée avec un généralisés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xx
	outil ad hoc fondé sur de la programmation dynamique, la seconde utilise un modèle de III.iii Méthodes efficaces pour la recherche des meilleures
	programmation par contrainte, un autre type de solveur que le MILP qui permet une caractéristiques différentielles de SKINNY . . . . . . . . . . . . . . . xxi
	description bien plus directe dans ce cas que ce dernier où nous avons raffiné les stra-
	tégies de résolution. Avec ces choix de méthode, nous retrouvons et terminons l'analyse Table of Contents	1
	chercher les caractéristiques différentielles tronquées ayant le minimum de boites-S actives ( avec différents modèles d'attaques où des différences peuvent être introduites dans les clés paramétrées ).Le modèle qu'ils proposent est résolu par un solveur et plus précisément un solveur de programme linéaire ( "mixed integer linear programming" MILP ). En MILP, les variables sont des entiers et les contraintes à considérer sont des inéquations linéaires en ces variables. Depuis la publication des spécifications, peu de résultats ont été publiés concernant les caractéristiques différentielles de SKINNY. Dans les limites de nos connaissances, seulement deux autres articles ont des résultats sur ce sujet : Liu et al. [LGS17] avaient besoin de sur les caractéristiques différentielles de SKINNY-64 en quelques secondes. Concernant Introduction 5 SKINNY-128, nous retrouvons les résultats de [Abd+17] en quelques minutes, au lieu de I Symmetric Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 16 jours à l'origine. Nous trouvons aussi les meilleures caractéristiques différentielles de I.i Block cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 SKINNY-128 dans les différents modèles de clés reliées pour certains tours ainsi que des I.ii Stream cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 meilleures caractéristiques différentielles ( sans optimalité ) pour un plus grand nombre I.iii Modes of operation . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 de tours et des preuves qu'aucune caractéristique différentielle n'existe ( avec une bonne II Analysis and Security of symmetric ciphers . . . . . . . . . . . . . . . . . . 14 probabilité ) pour certains nombres de tours. Les résultats détaillés sont dans la Sous-II.i Model of security . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 partie 3.5.3 du Chapitre 3. Ces travaux ont été publié à ACNS : II.ii Distinguishers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Stéphanie Delaune et al., "Efficient Methods to Search for Best Differential Characte-II.iii Differential cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . 15 ristics on SKINNY", in : International Conference on Applied Cryptography and Network III Overview of the manuscript . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Security, Springer, 2021, p. 184-207 III.i Revisiting Fast Near Collision Attacks (FNCA) . . . . . . . . . . . 18
	xxii	xxi 1

TABLE OF CONTENTS

 OF III.ii Efficient Search for Optimal Diffusion Layers of Generalized Feistel Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	III.iii Efficient Methods to Search for Best Differential Characteristics on
	SKINNY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	1 Revisiting the Fast Near Collision Attack
	1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	1.2 Fast Near Collision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	1.2.1 The refined self-contained method . . . . . . . . . . . . . . . . . . .
	1.2.2 About probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . .
	1.2.3 Several issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	1.3 Fast Near Collision on A5/1 . . . . . . . . . . . . . . . . . . . . . . . . . .
	1.3.1 Description of A5/1 . . . . . . . . . . . . . . . . . . . . . . . . . . .
	1.3.2 An attack from Golić . . . . . . . . . . . . . . . . . . . . . . . . . .
	1.3.3 Fast near collision attack against A5/1 . . . . . . . . . . . . . . . .
	1.3.4 Complexity correction . . . . . . . . . . . . . . . . . . . . . . . . .
	1.4 Fast Near Collision on Grain v1 . . . . . . . . . . . . . . . . . . . . . . . .
	1.4.1 Description of Grain v1 . . . . . . . . . . . . . . . . . . . . . . . .
	1.4.2 Zhang et al. attack . . . . . . . . . . . . . . . . . . . . . . . . . . .
	1.4.3 Complexity correction . . . . . . . . . . . . . . . . . . . . . . . . .
	1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Efficient Search for Optimal Diffusion Layers of Generalized Feistel Net- works

  Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	2.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	2.2.1 Generalized Feistel Networks (GFN) . . . . . . . . . . . . . . . . .
	2.2.2 Diffusion Round . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
	2.2.3 Even-odd Permutations . . . . . . . . . . . . . . . . . . . . . . . . .
	2.2.4 Equivalence Classes of Even-odd Permutations . . . . . . . . . . . .
	2.3 Characterization of Full Diffusion . . . . . . . . . . . . . . . . . . . . . . .
	2.4 Searching for an Optimal Permutation over 9 Rounds . . . . . . . . . . . .
	2.4.1 Efficient Search Algorithm . . . . . . . . . . . . . . . . . . . . . . .
	2.4.2 Checking the Constraints . . . . . . . . . . . . . . . . . . . . . . . .
	2.4.3

68 3 Efficient Methods to Search for Best Differential Characteristics on

  Security Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2.A Results for Optimal Permutations . . . . . . . . . . . . . . . . . . . . . . . 68 2.B Efficient Implementation to Test 9 Round Full Diffusion . . . . . . . . . . . Overview of the search method . . . . . . . . . . . . . . . . . . . . . . . . 82 3.3.1 A classical approach . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3.3.2 About other tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.4 Models and Results for Step 1 . . . . . . . . . . . . . . . . . . . . . . . . . 85 3.4.1 Possible Transitions . . . . . . . . . . . . . . . . . . . . . . . . . Caesar cipher consists in transforming a message into a gibberish sequence of letters called a ciphertext by changing each letter of the message into the n-th (fix) next letter in the alphabet. The receiver can then de-transform the ciphertext into the original message using the inverse operation on the letter of the ciphertext. Over time, cipher gained in design complexity, with the use for example of multiple alphabets and in practical complexity, with the use of helping mechanisms like slide rules. During the 16th century, Giovan Battista Bellaso created the Vigenère cipher (misattributed to the diplomat Blaise de Vigenère).

		TABLE OF CONTENTS
	INTRODUCTION 73 Cryptography from the Greek kryptos, "secret, hidden" and graphein, "to write" is an old 2.4.4 SKINNY
	3.1 Cipher under study: SKINNY-n . . . . . . . . . . . . . . . . . . . . . . . . . 76 field of study concerning way to hide secret messages to a third eavesdropping party. Its
	3.2 Best known differential characteristics on SKINNY . . . . . . . . . . . . . . 78 first known use (in a sense) can be dated to 1900 BC with an inscription in the tomb
	3.2.1 Best truncated differentail characteristics . . . . . . . . . . . . . . . 78 of Khnumhotep II where non-standard hieroglyphs were used. Approximately 1850 years
	3.2.2 Result in related-tweakeys models . . . . . . . . . . . . . . . . . . . 80 later, Julius Caesar used a cipher for his military affairs named now after him. The
	3.2.3 The best differential characteristic . . . . . . . . . . . . . . . . . . 81
	3.3 . . 85
	3.4.2 Ad-hoc Models for Step 1 . . . . . . . . . . . . . . . . . . . . . . . 86
	3.4.3 Results for Step 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
	3.5 Modeling Step 2 with CP . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
	3.5.1 Constraint Programming . . . . . . . . . . . . . . . . . . . . . . . . 91
	3.5.2 Modeling Step 2 with CP . . . . . . . . . . . . . . . . . . . . . . . 92
	3.5.3 Step 2 Performance Results . . . . . . . . . . . . . . . . . . . . . . 95
	3.A Best (related-tweakey) differential characteristics for SKINNY-64 . . . . . . 98
	3.B Best (related-tweakey) differential characteristics for SKINNY-128 . . . . . . 103
	Conclusion	107
	Bibliography	109

  This work is presented in Chapter 3 and was published at ACNS: Stéphanie Delaune et al., "Efficient Methods to Search for Best Differential Characteristics on SKINNY", in: International Conference on Applied Cryptography and Network

	Chapter 1
	Security, Springer, 2021, pp. 184-207

  al. published [BD00], another attack needing 2 39.91 clockings and 2 20.8 plaintexts. In 2003 Ekdhal et al. proposed a new attack [EJ03] against the initialization process of A5/1. It is improved a first time in 2004, by Maximov et al. in [MJB04] and a second time by

  ← chosen permutation with a given structure cycle 19: j ← an element from the smallest cycle of p 20: while all guesses are not made do

	12:	else
	13:	nextGuess(p, q, p(j), C )
	14:	end if
	15:	end while
	16:	end if
	17: end function
	18: p 21:

Table 2

 2 Chapter 2 -Efficient Search for Optimal Diffusion Layers of Generalized Feistel Networks

	k	Time	Structure of p	Structure of q	Number of solutions
			(6, 6, 1, 1)	(6, 6, 2)	144
			(6, 6, 2)	(6, 6, 1, 1)	144
	14 180 min	(6, 3, 2, 2, 1)	(6, 3, 2, 2, 1)	144
			(12, 2)	(12, 1, 1)	24
			(12, 1, 1)	(12, 2)	24
	15 480 min	(10, 2, 2, 1)	(10, 2, 2, 1)	160
			(6, 6, 3, 1)	(6, 6, 3, 1)	432
	16 1023 min	(6, 6, 2, 2)	(6, 3, 3, 2, 1, 1)	288
			(6, 3, 3, 2, 1, 1)	(6, 6, 2, 2)	216
	17 1700 min	-	-	0
	18 2213 min	(8, 8, 1, 1) (8, 8, 2)	(8, 8, 2) (8, 8, 1, 1)	256 256
	19 1913 min	-	-	0
	20 1116 min	-	-	0
	21 400 min	-	-	0

.2 -Results for optimal permutations with DR max (π) = 9

Table 2

 2

	.4 -Security evaluation for the best equivalence classes with k = 14
	(p, q)	Imp. Diff S 4,2 61	S 8,6 41	S 8,7 35

Table 2 .

 2 5 -Security evaluation for the best equivalence classes with k = 15

	bool checkDiffusion ( vector < vector < unsigned int > > const & powerp ,
	vector < unsigned int > const & q ){

Table 2 .

 2 6 -Security evaluation for the best equivalence classes with k = 16

	(p, q)	Imp. Diff S 4,2 73	S 8,6 49	S 8,7 42

Table 2 .

 2 7 -Security evaluation for the best equivalence classes with k = 18

Table 3 .

 3 Table 3.1. 1 -Minimum number of active S-boxes, Table 7 in [Bei+16]. Minimum number of active S-boxes in a truncated differential characteristic. Numbers in parenthesis are upper bound on the minimum.

	# rounds 1 2 3 4 5	6	7	8	9	10	11	12	13	14	15
	SK	1 2 5 8 12 16 26	36	41	46	51	55	58	61	66
	TK1	0 0 1 2 3	6	10	13	16	23	32	38	41	45	49
	TK2	0 0 0 0 1	2	3	6	9	12	16	21	25	31	35
	TK3	0 0 0 0 0	0	1	2	3	6	10	13	16	19	24
	# rounds 16 17 18 19 20 21 22	23	24	25	26	27	28	29	30
	SK	75 82 88 92 96 102 108 (114) (116) (124) (132) (138) (136) (148) (158)
	TK1	54 59 62 66 70 75 79	83	85	88	95	102 (108) (112) (120)
	TK2	40 43 47 52 57 59 64	67	72	75	82	85	88	92	96
	TK3	27 31 35 43 45 48 51	55	58	60	65	72	77	81	85

  SKINNY-128 , Liu et al. remark that modeling the 8-bit S-box is too heavy for MILP and proposed to replace it by a dedicated search algorithm used after computing Table 3.2 -Probability of the best differential characteristics found in [LGS17] (summary of Table 6 and Table 7 of their work).

		# rounds	6	7	8	9	10	11	12	13
	TK1	SKINNY-64 2 -12 2 -20 2 -26 2 -32 2 -46 2 -64 2 -76 2 -82 SKINNY-128 2 -12 2 -20 2 -54
	TK2	SKINNY-64 2 -4 2 -6 2 -12 2 -20 2 -28 2 -35 2 -48 2 -55 SKINNY-128 2 -12 2 -34.42
	TK3	SKINNY-64 SKINNY-128	2 0	2 -2 2 -4	2 -6	2 -12 2 -20 2 -28 2 -38 2 -12 2 -21 2 -62.83

  .3.

	Rounds	Model	Obj Step1	MILP	Ad-hoc
	14	TK1	45 → 59	> 6h	5m
	19	TK2	52 → 63	> 6h	19m
	20	SK	96	342m	16s
	20	TK1	70	38m	28s
	20	TK2	57	745s	193s
	20	TK3	45	998s	326s
	Table 3.3 -Comparison of the running times required to generate all Step 1 solutions
	between our MILP and ad-hoc approaches.

  Step1 Nb sol. Step 1 Step 2 time Best P r

	SK	7	26	2	1s	2 -52
	SK	8	36	17	1s	< 2 -64
	TK1	10	23	1	1s	2 -46
	TK1	11	32	2	1s	= 2 -64
	TK2	13	25 → 27	10	1s	2 -55
	TK2	14	31	1	1s	< 2 -64
	TK3	15	24 → 26	46	2s	2 -54
	TK3	16	27 → 31	87	4s	= 2 -64
	TK3	17	31	2	1s	< 2 -64

Table 3 .

 3 5 -Overall results concerning SKINNY-64 in the four attack models. Step 2 time corresponds to the Step 2 time taken over all Step 1 solutions when Obj step1 takes the values precise in the first column. Best P r corresponds to the best found probability of a differential characteristic.

  .11. Nb Rounds Obj step1 Nb sol. Step 1 Step 2 time Best P r

	SK	9	41 → 43	52	16s	2 -86
	SK	10	46 → 48	48	11s	2 -96
	SK	11	51 → 52	15	4s	2 -104
	SK	12	55 → 56	11	6s	2 -112
	SK	13	58 → 61	18	2m27s	2 -123
	SK	14	61 → 63	6	21s	≤ 2 -128
	TK1	8	13 → 16	14	4s	2 -33
	TK1	9	16 → 20	6	3s	2 -41
	TK1	10	23 → 27	6	4s	2 -55
	TK1	11	32 → 36	531	37s	2 -74
	TK1	12	38 → 46	186 482	213m	2 -93
	TK1	13	41 → 53	2 385 482	2 days	2 -106.2
	TK1	14	45 → 59	11 518 612	20 days	2 -120
	TK1	15	49 → 63	7 542 053	25 days	≤ 2 -128
	TK2	9	9 → 10	7	3s	2 -20
	TK2	10	12 → 17	132	11s	2 -34.4
	TK2	11	16 → 25	4203	6m	2 -51.4
	TK2	12	21 → 35	1 922 762	512m	2 -70.4
	TK2	19	52 → 63	530 693	280m	≤ 2 -128
	TK3	10	6	3	3s	2 -12
	TK3	11	10	3	10s	2 -21
	TK3	12	13 → 17	373	1h	2 -35.7
	TK3	13	16 → 25	34 638	85h	2 -51.8
	TK3	23	55 → 63	47 068	11h	≤ 2 -128

Table 3 .

 3 6 -Overall results concerning SKINNY-128 in the four attack models. Step 2 time corresponds to the Step 2 time taken over all solutions of Step1-enum when Obj step1 takes the values precise in the first column. Best P r corresponds to the best found probability of a differential characteristic. Chapter 3 -Efficient Methods to Search for Best Differential Characteristics on SKINNY Table 3.7 -Overall results concerning SKINNY-128 with exactly one active cell in the tweakey.

		Nb Rounds Obj step1	Best P r
	TK2	13	25 → 44	2 -86.2
	TK2	14	31 → 54 ≥ 2 -105.8
	TK2	15	35 → 56 ≥ 2 -113.8
	TK2	16	40 → 63 ≥ 2 -127.6
	TK3	14	19 → 33	2 -67
	TK3	15	24 → 40	2 -81
	TK3	16	27 → 48	2 -98
	TK3	17	31 → 54	2 -110
	TK3	19	43 → 63	≤ 2 -128
	TK3	20	45 → 63	≤ 2 -128
	TK3	21	48 → 63	≤ 2 -128
	TK3	22	51 → 63	≤ 2 -128

During the thesis, our works mainly focus on differential cryptanalysis over different perspectives from the study of one differential criteria in one type of Feistel construction, the study of a precise primitive SKINNY and revisiting some attacks that use differential cryptanalysis. Nevertheless, in this three works we always developed algorithms to construct or check our results. In this section, we give a brief review of each chapter of this thesis. In Chapter 1, we revisit the Fast Near Collision Attack (FNCA), a new type of attack proposed by Zhang et al.[START_REF] Zhang | Fast Near Collision Attack on the Grain v1 Stream Cipher[END_REF]. The FNCA was applied to two ciphers:

Actually at each trial we took for X the set of the 2 16.6 values reached the most. This highlights the refined self-contained method is irrelevant and can be replaced by any algorithm outputting a set of size 2 16.6 .

As for A5/1, we simply took for X the set of size 2 14.2 composed of the values reached the most during the experiment.

In practice, one should carefully study the primitive if the same F-function is used, e.g.[START_REF] Gueron | Simpira v2: A Family of Efficient Permutations Using the AES Round Function[END_REF]

Less than one hour for each k using 72 threads.

see: https://www.gurobi.com/documentation/9.0/refman/threads.html

Round δX i = X i ⊕ X i (before SB)

ACRYPT 2014 -Part II, vol. 8874, LNCS, Springer, 2014, pp. 274-288.

Chapter 2 -Efficient Search for Optimal Diffusion Layers of Generalized Feistel Networks

Let k A (resp. k B ) denote the cardinality of A (resp. B), and k i A , k i B be such that

Since all S i are disjoint, A ⊂ A and B ⊂ B, notice that we have

By selecting the two sets A ∩ S 1 and B ∩ S 1 as disjoint as possible we have:

Indeed, first we have at most |K| + k A + k B elements in K ∪ A ∪ B. However among all those elements, some might be the same, which explains the remaining terms :

• Elements of A and B included in S 0 , S 2 or S 3 are duplicates since they all belong to K.

• We need to take k 1 A (resp. k 1 B ) elements from A (resp. from B), where all those elements belongs to S 1 . We thus have two cases. If k 1 A + k 1 B ≤ |S 1 |, we can freely choose all those elements without having duplicates between A and B. Indeed for example, if we have k 1 A = k 1 B = 1 and S 1 = {0, 1, 2}, then we can put 0 in A and 1 in B, thus resulting in no duplicates between A and B . However if we have

no matter what, we will have duplicates. Thus in the best case, we have max(k 1 A + k 1 B -|S 1 |, 0) duplicates that we need to count out.

Hence, maximizing |K ∪ A ∪ B| is straightforward as there is one specific order in which to find the values of k i A and k i B that always maximize the size of the union. We only give the way to optimally build A since it is fully similar for B :

Searching for an Optimal Permutation over 9 Rounds

(p, q) p = (1, 2, 3, 4, 5, 0, 7, 8, 9, 10, 11, 6, 13, 14, 12, 15) q = (2, 6, 12, 10, 1, 13, 4, 15, 7, 9, 14, 5, 8, 3, 11, 0) p = (1, 2, 3, 4, 5, 0, 7, 8, 9, 10, 11, 6, 13, 14, 12, 15) q = (5, 6, 13, 10, 4, 12, 9, 15, 2, 1, 14, 7, 11, 3, 8, 0) p = (1, 2, 3, 4, 5, 0, 7, 8, 9, 10, 11, 6, 13, 12, 15, 14) q = (2, 1, 12, 8, 7, 14, 5, 4, 13, 11, 10, 15, 9, 3, 6, 0) p = (1, 2, 3, 4, 5, 0, 7, 8, 6, 10, 11, 9, 13, 12, 14, 15) q = (7, 6, 14, 9, 11, 15, 1, 12, 2, 13, 5, 4, 10, 8, 3, 0)

Security Analysis

Recall that our search space P k defined in Proposition 2.2 contains at least one representative for each class. Hence, among all the permutations we found, some of them might actually be in the same equivalence class. We can thus go further and regroup all representatives that belong to the same class using the following proposition.

Proposition 2.5. Let π = (p, q) be a permutation over 2k elements. Then for any permutation r such that r • p • r -1 = p, (p, q) and (p, r • q • r -1 ) are equivalent.

Proof. Let π = (p, q) and π = (p, r•q•r -1 ) where r is a permutation such that r•p•r -1 = p. Recall that we have π(2i) = 2p(i) + 1 and π(2i + 1) = 2q(i), for all i ∈ {0, . . . , k -1}. Now let ϕ be the permutation over 2k elements defined as

Then we have π = ϕ • π • ϕ -1 . Indeed, if we look at the image of an even number 2i, we

2.B. Efficient Implementation to Test 9 Round Full Diffusion

Results for Step 1

For Step 1, we run our ad-hoc tool on the four attack scenarios (SK, TK1, TK2, and TK3) when varying the number of rounds between 3 and 20. We conducted all our experiments on our server composed of 2× AMD EPYC 7742 64-Core and 1TB of RAM. In particular, we were able to complete the security analysis made in [START_REF] Beierle | The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS[END_REF][START_REF] Gianira | ShiftRows Alternatives for AES-like Ciphers and Optimal Cell Permutations for Midori and Skinny[END_REF] and claim that the minimal number of active S-boxes in TK1 for 28, 29 and 30 rounds are 105, 109 and 113 respectively (as shown in Table 3 However, the optimal solution of Step 2, in terms of differential characteristic probability, could be obtained for a number of active S-boxes which is not the optimal one. Hereafter, we denote Obj Step1 the number of active S-boxes we consider when solving the problems. For example, assume that, when processing Step 2, one obtains a differential characteristic with the best probability equal to 2 -3×6 = 2 -18 with Obj Step1 = 6 and whereas the optimal differential probability of the S-box is 2 -2 . It means that one has to test all solutions outputted by Step 1 until Obj Step1 < 18/2 = 9 to be sure that none has a better differential characteristic probability. This is exactly what happened for the case of SKINNY-128 in the TK models. We only want to stress here that computing the optimal bounds is often not enough and we need to go further. However, increasing the value of Obj Step1 induces an increase of the possible number of Step 1 solutions as illustrated in the third column of Table 3.6. As one can see, this number of solutions tends to grow exponentially when we increase v. For example, for SKINNY-128 with 14 rounds in the TK1 model, for the optimal value v * = 45, Step 1 outputs only 3 solutions; whereas we have 897 solutions for v = v * + 5 = 50; 137 019 solutions for v = v * + 10 = 55 and finally 7 241 601 solutions for v = 59. So, the time required to output all those Step 1 solutions and the time required for the Step 2 computations on 1 solution outputted by the Step 1 become the bottleneck of the overall process.

0000 0002 0020 0200 0000 0001 0010 0100 1000 0000 0B80 0000 2 -2•3 2 1000 1000 0000 0000 B000 8000 0000 0000 B000 8000 1000 0000 2 -2•2 3 0000 0000 0000 0000 0000 0000 0000 0000 0010 0000 B000 8000 -4 0010 0010 0000 0010 00B0 00A0 0000 00B0 00B0 0080 0010 0000 2 -2•3 5 0B00 0000 0002 0000 0100 0000 0001 0000 0000 1000 00B0 0080 2 -2•2 6 0000 0100 0000 0000 0000 0800 0000 0000 0000 B800 0000 1000 2 -2•1 7 0000 0000 0B00 0000 0000 0000 0100 0000 0000 0010 0000 B800 2 -2•1 8 0001 0000 0000 0001 0008 0000 0000 0008 0008 00B0 0000 0010 2 -2•2 9 0080 0000 000B 0000 0040 0000 0001 0000 0000 0100 0008 00B0 2 -2•2 10 0140 0040 0110 0140 0820 0020 0880 0820 0000 0B08 0000 0100

Table 3.9 -The Best TK1 differential characteristics on 10 rounds of SKINNY-64 with probability equal to 2 -46 . The four words represent the four rows of the state and are given in hexadecimal notation.

3.A. Best (related-tweakey) differential characteristics for SKINNY-64

Round

0000 8200 0080 0000 0000 4100 0040 0000 0000 0008 0502 0000 0000 000C 060C 0000

2 4000 0000 0410 4000 2000 0000 02A0 2000 5000 0002 0000 0008 D000 0008 0000 000C

3 0000 A000 0002 0002 0000 6000 0006 0003 0800 0000 5000 0002 0800 0000 D000 0008

4 0630 0000 0000 0600 03F0 0000 0000 0100 0250 0000 0800 0000 01A0 0000 0800 0000

5 1000 0000 0000 0000 9000 0000 0000 0000 8000 0000 0250 0000 1000 0000 01A0 0000

6 0000 0000 0000 0000 0000 0000 0000 0000 2000 5000 8000 0000 2000 5000 1000 0000 -7 0000 0000 0000 0000 0000 0000 0000 0000 0080 0000 2000 5000 0020 0000 2000 5000 -8 00A0 00A0 0000 00A0 0060 0050 0000 0050 0020 0050 0080 0000 0040 00B0 0020 0000

9 0500 0000 000B 0000 0C00 0000 000C 0000 0000 8000 0020 0050 0000 4000 0040 00B0

10 0000 0C00 0000 0000 0000 0200 0000 0000 0000 2500 0000 8000 0000 9700 0000 4000

11 0000 0000 0B00 0000 0000 0000 0100 0000 0000 0080 0000 2500 0000 0090 0000 9700

12 0001 0000 0000 0001 000A 0000 0000 0008 0005 0020 0000 0080 000F 0030 0000 0090

13 0080 0000 0001 0000 0040 0000 0008 0000 0000 0800 0005 0020 0000 0300 000F 0030

0000 0001 4000 0004 0000 0008 2000 0002 0000 080D 0000 0800 0000 0408 0000 0500 0000 0E0D 0000 0C00

2 0000 0000 0000 0020 0000 0000 0000 0010 0008 0000 0000 080D 000B 0000 0000 0408 000E 0000 0000 0E0D

2 -2 3 010D 000D 0000 000D 0A0E 0002 0000 0002 0D08 0000 0008 0000 0109 0000 000B 0000 060F 0000 000E 0000

4 0020 0000 2000 0000 0030 0000 3000 0000 0000 0008 0D08 0000 0000 0007 0109 0000 0000 000F 060F 0000

5 0000 0030 0030 0000 0000 00C0 00C0 0000 D000 0008 0000 0008 2000 0003 0000 0007 3000 0007 0000 000F

6 0000 C000 000C 0000 0000 2000 0002 0000 0800 0000 D000 0008 0F00 0000 2000 0003 0700 0000 3000 0007

7 0200 0000 0000 0200 0500 0000 0000 0300 08D0 0000 0800 0000 0640 0000 0F00 0000 0B90 0000 0700 0000

8 3000 0000 0000 0000 D000 0000 0000 0000 8000 0000 08D0 0000 E000 0000 0640 0000 B000 0000 0B90 0000 2 -3 9 0000 0000 0000 0000 0000 0000 0000 0000 8000 D000 8000 0000 D000 9000 E000 0000 5000 4000 B000 0000 -10 0000 0000 0000 0000 0000 0000 0000 0000 0080 0000 8000 D000 00C0 0000 D000 9000 0050 0000 5000 4000 -11 0010 0010 0000 0010 0080 0090 0000 00A0 0080 00D0 0080 0000 00A0 0030 00C0 0000 00A0 0020 0050 0000

12 0A00 0000 0005 0000 0A00 0000 000A 0000 0000 8000 0080 00D0 0000 8000 00A0 0030 0000 A000 00A0 0020

13 0000 0A00 0000 0000 0000 0A00 0000 0000 0000 8D00 0000 8000 0000 5600 0000 8000 0000 D100 0000 A000

2 -3 14 0000 0000 0000 0000 0000 0000 0000 0000 0000 0080 0000 8D00 0000 0010 0000 5600 0000 00D0 0000 D100 -15 0000 0000 0004 0000 0000 0000 0002 0000 000D 0080 0000 0080 000D 00B0 0000 0010 0008 0060 0000 00D0 . The four words represent the four rows of the state and are given in hexadecimal notation.

3.B. Best (related-tweakey) differential characteristics for SKINNY-128

3.B Best (related-tweakey) differential characteristics for SKINNY-128

Concerning the best SK differential characteristics on 13 rounds of SKINNY-128, We obtain the same best SK differential characteristics on 13 rounds of SKINNY-128 with probability equal to 2 -123 given in Table 11 of Appendix D of [START_REF] Abdelkhalek | MILP Modeling for (Large) S-boxes to Optimize Probability of Differential Characteristics[END_REF]. The best TK1 differential characteristics on 14 rounds of SKINNY-128 with probability equal to 2 -120 is given in Table 3.12. The best TK2 differential characteristics on 16 rounds of SKINNY-128 with probability equal to 2 -127.6 we found is given in Table 3.13. The best TK3 differential characteristics on 17 rounds of SKINNY-128 with probability equal to 2 -110 we found is given in Table 3.14.

Chapter 3 -Efficient Methods to Search for Best Differential Characteristics on SKINNY

02000002 00000200 00020000 00020040 08000008 00000800 00080000 00080004 00000000 00000000 01000000 00000000

2 00000400 08000008 00000000 08000000 00000100 10000010 00000000 10000000 00000100 00000000 00000000 00000000

3 00000010 00000000 10100000 00000000 00000040 00000000 40400000 00000000 00000000 00000000 00000100 00000000

4 00004000 00000040 00004040 00004000 00000400 00000004 00000404 00000400 00000000 01000000 00000000 00000000

5 04000400 00000400 00050000 04040400 05000500 00000100 00050000 05050500 00000000 00000000 00000000 01000000

6 00050500 05000500 00000004 05000505 00050500 01000100 00000005 05000505 00000000 00000100 00000000 00000000

7 00050005 00050500 00040000 00000500 00050005 00050500 00050000 00000500 00000000 00000000 00000000 00000100

8 00000000 00050005 00000500 00050000 00000000 00010005 00000500 00050000 00000000 00010000 00000000 00000000

9 00000000 00000000 00000000 05000000 00000000 00000000 00000000 05000000 00000000 00000000 00000000 00010000

10 00000005 00000000 00000000 00000000 00000001 00000000 00000000 00000000 00000001 00000000 00000000 00000000

11 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001 00000000 -12 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001 00000000 00000000 -13 00000000 00000000 01000000 00000000 00000000 00000000 20000000 00000000 00000000 00000000 00000000 00000001

14 00002000 00000000 00002000 00002000 00008000 00000000 00008000 00008000 00010000 00000000 00000000 00000000

Table 3.12 -The Best TK1 differential characteristics on 14 rounds of SKINNY-128

with probability equal to 2 -120

. The four words represent the four rows of the state and are given in hexadecimal notation.

3.B. Best (related-tweakey) differential characteristics for SKINNY-128

00000000 00404010 40400000 40000000 00000000 00000000 00000000 00007700 2 -2•6 00000000 00040440 04040000 04000000 00000000 00000000 00000000 00003900 2 00000400 00000000 40000000 00000404 00000000 00770000 00000000 00000000 2 -2•3 2 -3 00000500 00000000 04000000 00000101 00000000 00730000 00000000 00000000 3 00010000 00000500 00000000 00000100 00000000 00000000 00000000 00770000 2 -2•2 2 -3 00200000 00000500 00000000 00002000 00000000 00000000 00000000 00730000 4 00000000 00200000 00000005 00200000 00000077 00000000 00000000 00000000 2 -2•2 2 -3 00000000 00800000 00000005 00800000 000000E7 00000000 00000000 00000000 5 80050090 00000090 00058000 00050090 00000000 00000000 00000077 00000000 2 -2•8 03010002 00000002 00010200 00010003 00000000 00000000 000000E7 00000000 6 00010303 03010002 00000001 01010003 00000000 00000077 00000000 00000000 2 -2•6 2 -3•4 00202020 20200009 00000020 20200020 00000000 000000CE 00000000 00000000 7 20000000 00202020 B0002000 00002020 00000000 00000000 00000000 00000077 2 -2•6 2 -2.4 2 -3 80000000 00808080 80008000 00009380 00000000 00000000 00000000 000000CE 8 00930000 80000000 00000080 00008000 00770000 00000000 00000000 00000000 2 -2•3 2 -6 00EA0000 03000000 00000003 00000300 009D0000 00000000 00000000 00000000 9 00000000 00000000 00000000 00030000 00000000 00000000 00770000 00000000 2 -5 00000000 00000000 00000000 00BC0000 00000000 00000000 009D0000 00000000 10 BC000000 00000000 00000000 00000000 77000000 00000000 00000000 00000000 2 -6 4C000000 00000000 00000000 00000000 3B000000 00000000 00000000 00000000 11 00000000 00000000 00000000 00000000 00000000 00000000 77000000 00000000 -00000000 00000000 00000000 00000000 00000000 00000000 3B000000 00000000 12 00000000 00000000 00000000 00000000 00007700 00000000 00000000 00000000 -00000000 00000000 00000000 00000000 00007700 00000000 00000000 00000000 13 00000000 00000000 00000000 00000000 00000000 00000000 00007700 00000000 -00000000 00000000 00000000 00000000 00000000 00000000 00007700 00000000 14 0000000 00000000 00000000 00000000 00000000 77000000 00000000 00000000 -00000000 00000000 00000000 00000000 00000000 EF000000 00000000 00000000 15 00000000 00000000 00980000 00000000 00000000 00000000 00000000 77000000 2 -5 00000000 00000000 00420000 00000000 00000000 00000000 00000000 EF000000 16 00000042 00000000 00000042 00000042 -2 -2.4•3 00000008 00000000 00000008 00000008 Table 3.13 -The Best TK2 differential characteristics we found on 16 rounds of SKINNY-128 with probability equal to 2 -127.6 . The four words represent the four rows of the state and are given in hexadecimal notation.

00000200 00320000 08000000 00000808 00000000 00BA0000 00000000 00000000 2 -2•3 2 -3•2 00000800 00920000 18000000 00001010 00000000 00430000 00000000 00000000 00000000 00730000 00000000 00000000 2 00100000 00000800 00000000 00001000 00000000 00000000 00000000 00BA0000 2 -2•3 00400000 00001000 00000000 00004000 00000000 00000000 00000000 00430000 00000000 00000000 00000000 00730000 3 00000000 00400000 00000010 00400000 000000BA 00000000 00000000 00000000 2 -2•3 00000000 00040000 00000040 00040000 00000086 00000000 00000000 00000000 00000039 00000000 00000000 00000000 4 04400005 00000005 00400400 00400005 00000000 00000000 000000BA 00000000 2 -2•6 2 -3•2 05040001 00000001 00040100 00040005 00000000 00000000 00000086 00000000 00000000 00000000 00000039 00000000 5 00040505 05040001 00000004 04040005 00000000 000000BA 00000000 00000000 2 -2•9 2 -3 00010101 01010028 00000001 01010001 00000000 0000000D 00000000 00000000 00000000 0000009C 00000000 00000000 6 01000000 00010101 03000100 00000101 00000000 00000000 00000000 000000BA 2 -2•6 2 -3 2 -4 20000000 00202020 20002000 0000B320 00000000 00000000 00000000 0000000D 00000000 00000000 00000000 0000009C 7 00B30000 20000000 00000020 00002000 00BA0000 00000000 00000000 00000000 2 -2•3 2 -7 00EE0000 80000000 00000080 00008000 001A0000 00000000 00000000 00000000 004E0000 00000000 00000000 00000000 8 00000000 00000000 00000000 00800000 00000000 00000000 00BA0000 00000000 2 -2 00000000 00000000 00000000 00030000 00000000 00000000 001A0000 00000000 00000000 00000000 004E0000 00000000 9 03000000 00000000 00000000 00000000 BA000000 00000000 00000000 00000000 2 -4 29000000 00000000 00000000 00000000 34000000 00000000 00000000 00000000 A7000000 00000000 00000000 00000000 10 00000000 00000000 00000000 00000000 00000000 00000000 BA000000 00000000 -00000000 00000000 00000000 00000000 00000000 00000000 34000000 00000000 00000000 00000000 A7000000 00000000 11 00000000 00000000 00000000 00000000 0000BA00 00000000 00000000 00000000 -00000000 00000000 00000000 00000000 00006900 00000000 00000000 00000000 0000D300 00000000 00000000 00000000 12 00000000 00000000 00000000 00000000 00000000 00000000 0000BA00 00000000 -00000000 00000000 00000000 00000000 00000000 00000000 00006900 00000000 00000000 00000000 0000D300 00000000 13 00000000 00000000 00000000 00000000 00000000 BA000000 00000000 00000000 -00000000 00000000 00000000 00000000 00000000 D3000000 00000000 00000000 00000000 69000000 00000000 00000000 14 00000000 00000000 00000000 00000000 00000000 00000000 00000000 BA000000 -00000000 00000000 00000000 00000000 00000000 00000000 00000000 D3000000 00000000 00000000 00000000 69000000 15 0000000 00000000 00000000 00000000 00000000 0000BA00 00000000 00000000 -00000000 00000000 00000000 00000000 00000000 0000A700 00000000 00000000 00000000 00003400 00000000 00000000 16 00000000 00000000 00000029 00000000 00000000 00000000 00000000 0000BA00 2 -3 00000000 00000000 00000030 00000000 00000000 00000000 00000000 0000A700 00000000 00000000 00000000 00003400 17 00300000 00000000 00300000 00300000 -2 -2•3 00400000 00000000 00400000 00400000 Table 3.14 -The Best TK3 differential characteristics we found on 17 rounds of SKINNY-128 with probability equal to 2 -110 . The four words represent the four rows of the state and are given in hexadecimal notation.