Dissertations / Theses on the topic 'Cryptanalyse différentielle'

Le travail de recherche présenté dans cette thèse se place en cryptographie symétrique. En particulier, nous nous intéressons à l'analyse et à la conception des systèmes de chiffrement par blocs. Les années 90 ont vu l'avènement de nombreuses attaques statistiques sur ces systèmes de chiffrement. Durant cette thèse, je me suis intéressée aux généralisations de la cryptanalyse différentielle. La première partie de ce manuscrit est dédiée à la présentation d'un certain nombre d'attaques statistiques sur les systèmes de chiffrement par blocs. Dans cette thèse nous donnons une méthode générale qui permet de calculer la complexité en donnée et la probabilité de succès des attaques statistiques simples. En en utilisant plusieurs différentielles nous généralisons la cryptanalyse différentielle et la cryptanalyse différentielle tronquée et nous étudions les complexités de cette attaque différentielle multiple. La seconde partie de cette thèse est dédiée à l'étude des critères sur les boîtes-S des systèmes de chiffrement par blocs qui permettent de prémunir ces systèmes de chiffrement contre les attaques différentielles. À la suite d'une étude approfondie de la résistance des boîtes-S, nous avons introduit un nouveau critère, plus précis que l'uniformité différentielle, nous permettant de mesurer la vulnérabilité des boîtes-S aux attaques différentielles. Dans cet manuscrit, nous introduisons la notion de spectre différentiel et étudions le spectre différentiel de différentes classes de fonctions puissances.

Les travaux réalisés dans cette thèse ont pour objet l'analyse de la sécurité de chiffrements à clef secrète. Plus précisément, nous y décrivons la cryptanalyse de plusieurs chiffrements par blocs et à flot ayant pour point commun d'avoir été conçus récemment pour répondre aux nouveaux enjeux de la cryptographie symétrique. Nous mettons en avant des attaques des versions complètes de cinq chiffrements, prouvant ainsi que ces primitives cryptographiques n'apportent pas la sécurité annoncée par leurs concepteurs.La première partie de cette thèse est dédiée à l'analyse de chiffrements par blocs avec des techniques de cryptanalyse différentielle. Nous montrons comment mener une attaque par différentielles tronquées sur la famille de chiffrements à bas coût KLEIN en exploitant la faible diffusions de sa fonction de tour. Ensuite, nous nous intéressons à Zorro et à Picaro, deux chiffrements conçus de sorte à être faciles à protéger contre les attaques par canaux auxiliaires, et montrons que les choix de conception guidés par cette contrainte ont engendré des faiblesses dans leurs propriétés différentielles, pouvant ensuite être exploitées dans des attaques.La seconde partie du manuscrit porte sur la cryptanalyse de chiffrements à flot. Nous y étudions Sprout et Flip, deux chiffrements aux structures innovantes visant respectivement à limiter la taille du circuit matériel nécessaire à l'implémentation et une bonne adaptation dans un schéma de FHE
The main subject of this thesis is the security analysis of symmetric key ciphers. Specifically, we study several recently proposed block and stream ciphers and prove that the level of security stated by their designers is overestimated. The ciphers we study were all designed in order to meet the needs of one of the new applications of symmetric cryptography, which include symmetric ciphers for very constrained environments.The first part of the thesis is dedicated to the analysis of block ciphers with techniques based on differential cryptanalysis. We start with the description of a truncated differential attack on the family of lightweight ciphers KLEIN. Next, we analyse two ciphers that were designed in such a way that they could be easily and effectively protected against side-channel attacks: Zorro and Picaro. We show that the design choices made by their designers lead to weak diffusion properties. We exploit these imperfections to devise a differential cryptanalysis of Zorro and a related key attack on Picaro.The second part of this thesis deals with stream ciphers and gives an analysis of two innovative designs: Sprout and Flip. Sprout was designed in order to limit its hardware area size and to suit very constrained environments, while Flip reaches efficient performances when used in FHE schemes. In both cases, we find flaws that lead to attacks of the particular set of parameters proposed for these ciphers

La cryptographie multivariée peut être définie comme la cryptographie à clé publique basée sur la difficulté de résoudre des systèmes polynomiaux à plusieurs variables. Bien que la recherche de tels schémas soit apparue dès le début des années 80, elle s'est surtout développée depuis une dizaine d'années, et a conduit à plusieurs propositions jugées promet-teuses, telles que le cryptosystème HFE et le schéma de signature SFLASH. Les shémas multivariés se posent ainsi en alternative possible aux schémas traditionnels basés sur des problèmes de théorie des nombres, et constituent des solutions efficaces pour l'implantation des fonctionnalités de la cryptographie à clé publique. Lors d'Eurocrypt 2005, Fouque, Granboulan et Stern ont proposé une nouvelle approche cryptanalytique pour les schémas multivariés basée sur l'étude d'invariants liés à la différentielle, et ont démontré la pertinence de cette approche par la cryptanalyse du schéma PMI proposé par Ding. Au cours de cette thèse, nous avons développé l'approche différentielle proposée par Fouque et al. dans deux directions. La première consiste en un traitement combinatoire des invariants dimensionnels de la différentielle. Ceci nous a permis de montrer qu'une clé publique HFE pouvait être distinguée d'un système quadratique aléatoire en temps quasipolynomial. Une seconde application de cette même approche nous a permis de cryptanalyser une variation de HFE proposée par Ding et Schmidt à PKC 2005. Le second développement de la thèse est la découverte d'invariants fonctionnels de la différentielle et nous a permis de montrer la faiblesse du schéma SFLASH.

Les travaux exposés dans cette thèse se situent à l’interface des mathématiques discrètes, des corps finis et de la cryptographie symétrique.Les 'boîtes-S’ sont des fonctions non-linéaires de petites tailles qui constituent souvent la partie de confusion, indispensable, des chiffrements par blocs ou des fonctions de hachages.Dans la première partie de cette thèse, nous nous intéressons à la construction de boîtes-S bijectives résistantes aux attaques différentielle. Nous étudions l’inverse pour la composition des monômes de permutations optimaux vis-à-vis du critère différentiel. Nous explorons ensuite des classes spécifiques de polynômes creux. Enfin, nous construisons des boîtes-S à partir de leurs dérivées discrètes.Dans la deuxième partie, nous portons notre attention sur la cryptanalyse différentielle impossible. Cette cryptanalyse à clairs choisis très performante pour attaquer des chiffrements par blocs itératifs, exploite la connaissance d’une différentielle de probabilité zéro pour écarter les clés candidates. Elle est très technique, et de nombreuses erreurs ont été repérées dans des travaux passés, invalidant certaines attaques. Le but de ces travaux est de formaliser et d’automatiser l’évaluation des complexités d’une telle attaque afin d’unifier et d’optimiser les résultats obtenus. Nous proposons aussi de nouvelles techniques réduisant les complexités cette cryptanalyse. Nous démontrons enfin l’efficacité de notre approche en fournissant les meilleures cryptanalyses différentielles impossibles contre les chiffrements CLEFIA, Camellia, LBlock et Simon
The work I have carried out in this thesis lie between discrete mathematics, finite fields theory and symmetric cryptography. In block ciphers, as well as in hash functions, SBoxes are small non-linear and necessary functions working as confusion layer.In the first part of this document, we are interesting in the design of bijective SBoxes that have the best resistance to differential attacks. We study the compositional inverse of the so-called Almost Perfect Nonlinear power functions. Then, we extensively study a class of sparse permutation polynomials with low differential uniformity. Finally, we build functions, over finite fields, from their discrete derivatives.In the second part, we realize an automatic study of a certain class of differential attacks: impossible differential cryptanalysis. This known plaintexts attack has been shown to be very efficient against iterative block ciphers. It exploits the knowledge of a differential with probability zero to occur. However this cryptanalysis is very technical and many flaws have been discovered, thus invalidating many attacks realized in the past. Our goal is to formalize, to improve and to automatize the complexity evaluation in order to optimize the results one can obtain. We also propose new techniques that aims at reducing necessary data and time complexities. We finally prove the efficiency of our method by providing some of the best impossible differential cryptanalysis against Feistel oriented block ciphers CLEFIA, Camellia, LBlock and Simon

Les travaux exposés dans cette thèse se situent à l’interface des mathématiques discrètes, des corps finis et de la cryptographie symétrique.Les 'boîtes-S’ sont des fonctions non-linéaires de petites tailles qui constituent souvent la partie de confusion, indispensable, des chiffrements par blocs ou des fonctions de hachages.Dans la première partie de cette thèse, nous nous intéressons à la construction de boîtes-S bijectives résistantes aux attaques différentielle. Nous étudions l’inverse pour la composition des monômes de permutations optimaux vis-à-vis du critère différentiel. Nous explorons ensuite des classes spécifiques de polynômes creux. Enfin, nous construisons des boîtes-S à partir de leurs dérivées discrètes.Dans la deuxième partie, nous portons notre attention sur la cryptanalyse différentielle impossible. Cette cryptanalyse à clairs choisis très performante pour attaquer des chiffrements par blocs itératifs, exploite la connaissance d’une différentielle de probabilité zéro pour écarter les clés candidates. Elle est très technique, et de nombreuses erreurs ont été repérées dans des travaux passés, invalidant certaines attaques. Le but de ces travaux est de formaliser et d’automatiser l’évaluation des complexités d’une telle attaque afin d’unifier et d’optimiser les résultats obtenus. Nous proposons aussi de nouvelles techniques réduisant les complexités cette cryptanalyse. Nous démontrons enfin l’efficacité de notre approche en fournissant les meilleures cryptanalyses différentielles impossibles contre les chiffrements CLEFIA, Camellia, LBlock et Simon
The work I have carried out in this thesis lie between discrete mathematics, finite fields theory and symmetric cryptography. In block ciphers, as well as in hash functions, SBoxes are small non-linear and necessary functions working as confusion layer.In the first part of this document, we are interesting in the design of bijective SBoxes that have the best resistance to differential attacks. We study the compositional inverse of the so-called Almost Perfect Nonlinear power functions. Then, we extensively study a class of sparse permutation polynomials with low differential uniformity. Finally, we build functions, over finite fields, from their discrete derivatives.In the second part, we realize an automatic study of a certain class of differential attacks: impossible differential cryptanalysis. This known plaintexts attack has been shown to be very efficient against iterative block ciphers. It exploits the knowledge of a differential with probability zero to occur. However this cryptanalysis is very technical and many flaws have been discovered, thus invalidating many attacks realized in the past. Our goal is to formalize, to improve and to automatize the complexity evaluation in order to optimize the results one can obtain. We also propose new techniques that aims at reducing necessary data and time complexities. We finally prove the efficiency of our method by providing some of the best impossible differential cryptanalysis against Feistel oriented block ciphers CLEFIA, Camellia, LBlock and Simon

L'objet de cette thèse est de raffiner les critères classiques de résistance des réseaux de substitution-permutation aux attaques linéaires et différentielles. Nous présentons une nouvelle borne sur le MEDP2 et le MELP2, qui ne dépend que de la boîte-S et du branch number de la fonction de diffusion, lorsque celle-ci est linéaire sur l'alphabet de la boîte-S. De plus, pour toute boîte-S, nous montrons qu'il existe toujours au moins une permutation linéaire de branch number maximal pour laquelle le MEDP2 (resp. MELP2) dépasse une certaine quantité. Ainsi, sous certaines conditions sur la boîte-S S et le branch number d, il est impossible de trouver une meilleure borne ne dépendant que de S et de d. Par ailleurs, nous introduisons une nouvelle propriété des boîtes-S qui simplifie le calcul de la borne. Si S et son inverse la vérifient, nous prouvons que la borne inférieure précédente est satisfaite pour toute fonction de diffusion de branch number maximal. En particulier, si S est l'inversion dans le corps à 2^m éléments, la valeur exacte de MEDP2 (et de MELP2) est toujours la plus grande possible parmi les boîtes-S de la même classe d'équivalence et la composition avec une permutation affine permet en général de diminuer ces valeurs. D'autre part, pour de nombreux chiffrements, le MEDP2 est atteint par une différentielle ayant le minimum de boîtes-S actives. Nous montrons que ceci est toujours vrai pour certaines familles de boîtes-S. Cependant, nous présentons aussi des SPN pour lesquels le MEDP2 est atteint par une différentielle dont le nombre de boîtes-S actives est supérieur au branch number de M
In this work, we refine the classical criteria for the resistance of substitution-permutation networks against differential and linear cryptanalyses. We provide a new upper bound on the MEDP2 and MELP2 when the diffusion layer is linear over the finite field defined by the Sbox alphabet. This bound only depends on the Sbox and on the branch number of the linear layer. We also provide a lower bound on these quantities and we show that, under some condition, it is optimal in the sense that there exists a diffusion layer for which the bound is tight. Moreover, we introduce a particular class of Sboxes, for which the bounds are easier to compute. If S and its inverse are in this class, then the lower bound is tight for any MDS linear layer. Furthermore, we prove that the inversion in the field with 2^m elements is the mapping in its equivalence class which has the highest MEDP2 and MELP2, independently of the choice of the linear diffusion layer. This situation mainly originates from the fact that it is an involution. We also focus on the differentials that reach the MEDP2. Though it appears to be the case for most known examples, there is a priori no reason to believe that these differentials correspond to a differential with the lowest number of active Sboxes. We detail some situations for which we prove that the MEDP2 is achieved by a differential with the smallest number of active Sboxes, for instance when the Sbox is carefully chosen. However, this phenomenon is not general as we exhibit the first examples of SPNs where the MEDP2 is achieved by a differential in which the number of active Sboxes exceeds the branch number

Les travaux réalisés dans cette thèse ont pour objet l'analyse de la sécurité de chiffrements à clef secrète. Plus précisément, nous y décrivons la cryptanalyse de plusieurs chiffrements par blocs et à flot ayant pour point commun d'avoir été conçus récemment pour répondre aux nouveaux enjeux de la cryptographie symétrique. Nous mettons en avant des attaques des versions complètes de cinq chiffrements, prouvant ainsi que ces primitives cryptographiques n'apportent pas la sécurité annoncée par leurs concepteurs.La première partie de cette thèse est dédiée à l'analyse de chiffrements par blocs avec des techniques de cryptanalyse différentielle. Nous montrons comment mener une attaque par différentielles tronquées sur la famille de chiffrements à bas coût KLEIN en exploitant la faible diffusions de sa fonction de tour. Ensuite, nous nous intéressons à Zorro et à Picaro, deux chiffrements conçus de sorte à être faciles à protéger contre les attaques par canaux auxiliaires, et montrons que les choix de conception guidés par cette contrainte ont engendré des faiblesses dans leurs propriétés différentielles, pouvant ensuite être exploitées dans des attaques.La seconde partie du manuscrit porte sur la cryptanalyse de chiffrements à flot. Nous y étudions Sprout et Flip, deux chiffrements aux structures innovantes visant respectivement à limiter la taille du circuit matériel nécessaire à l'implémentation et une bonne adaptation dans un schéma de FHE
The main subject of this thesis is the security analysis of symmetric key ciphers. Specifically, we study several recently proposed block and stream ciphers and prove that the level of security stated by their designers is overestimated. The ciphers we study were all designed in order to meet the needs of one of the new applications of symmetric cryptography, which include symmetric ciphers for very constrained environments.The first part of the thesis is dedicated to the analysis of block ciphers with techniques based on differential cryptanalysis. We start with the description of a truncated differential attack on the family of lightweight ciphers KLEIN. Next, we analyse two ciphers that were designed in such a way that they could be easily and effectively protected against side-channel attacks: Zorro and Picaro. We show that the design choices made by their designers lead to weak diffusion properties. We exploit these imperfections to devise a differential cryptanalysis of Zorro and a related key attack on Picaro.The second part of this thesis deals with stream ciphers and gives an analysis of two innovative designs: Sprout and Flip. Sprout was designed in order to limit its hardware area size and to suit very constrained environments, while Flip reaches efficient performances when used in FHE schemes. In both cases, we find flaws that lead to attacks of the particular set of parameters proposed for these ciphers

L'objet de cette thèse est de raffiner les critères classiques de résistance des réseaux de substitution-permutation aux attaques linéaires et différentielles. Nous présentons une nouvelle borne sur le MEDP2 et le MELP2, qui ne dépend que de la boîte-S et du branch number de la fonction de diffusion, lorsque celle-ci est linéaire sur l'alphabet de la boîte-S. De plus, pour toute boîte-S, nous montrons qu'il existe toujours au moins une permutation linéaire de branch number maximal pour laquelle le MEDP2 (resp. MELP2) dépasse une certaine quantité. Ainsi, sous certaines conditions sur la boîte-S S et le branch number d, il est impossible de trouver une meilleure borne ne dépendant que de S et de d. Par ailleurs, nous introduisons une nouvelle propriété des boîtes-S qui simplifie le calcul de la borne. Si S et son inverse la vérifient, nous prouvons que la borne inférieure précédente est satisfaite pour toute fonction de diffusion de branch number maximal. En particulier, si S est l'inversion dans le corps à 2^m éléments, la valeur exacte de MEDP2 (et de MELP2) est toujours la plus grande possible parmi les boîtes-S de la même classe d'équivalence et la composition avec une permutation affine permet en général de diminuer ces valeurs. D'autre part, pour de nombreux chiffrements, le MEDP2 est atteint par une différentielle ayant le minimum de boîtes-S actives. Nous montrons que ceci est toujours vrai pour certaines familles de boîtes-S. Cependant, nous présentons aussi des SPN pour lesquels le MEDP2 est atteint par une différentielle dont le nombre de boîtes-S actives est supérieur au branch number de M
In this work, we refine the classical criteria for the resistance of substitution-permutation networks against differential and linear cryptanalyses. We provide a new upper bound on the MEDP2 and MELP2 when the diffusion layer is linear over the finite field defined by the Sbox alphabet. This bound only depends on the Sbox and on the branch number of the linear layer. We also provide a lower bound on these quantities and we show that, under some condition, it is optimal in the sense that there exists a diffusion layer for which the bound is tight. Moreover, we introduce a particular class of Sboxes, for which the bounds are easier to compute. If S and its inverse are in this class, then the lower bound is tight for any MDS linear layer. Furthermore, we prove that the inversion in the field with 2^m elements is the mapping in its equivalence class which has the highest MEDP2 and MELP2, independently of the choice of the linear diffusion layer. This situation mainly originates from the fact that it is an involution. We also focus on the differentials that reach the MEDP2. Though it appears to be the case for most known examples, there is a priori no reason to believe that these differentials correspond to a differential with the lowest number of active Sboxes. We detail some situations for which we prove that the MEDP2 is achieved by a differential with the smallest number of active Sboxes, for instance when the Sbox is carefully chosen. However, this phenomenon is not general as we exhibit the first examples of SPNs where the MEDP2 is achieved by a differential in which the number of active Sboxes exceeds the branch number

Cette thèse en informatique se concentre sur le domaine de la cryptographie, en particulier sur la cryptanalyse différentielle. Dans cette thèse, je présente différentes méthodes de cryptanalyse et applications de ces dernières. Un chapitre sera consacré aux optimisations de la cryptanalyse différentielle-linéaire des constructions ARX, ainsi que son application à Chaskey. Dans le chapitre suivant, je présenterai une attaque complète contre la version principale du chiffrement par bloc Speedy, montrant alors comment utiliser des techniques puissantes lors d une cryptanalyse différentielle. Ensuite, je présenterai une nouvelle technique de cryptanalyse en cryptographie symétrique : cryptanalyse différentielle meet-in-the-middle, qui consiste à combiner des éléments de différentielle avec des éléments meet-in-the-middle. Enfin je présenterai version quantique de la cryptanalyse différentielle impossible : cryptanalyse différentielle quantique
This thesis in computer science focuses on the field of cryptography, in particular on differential cryptanalysis. In this thesis, I present different cryptanalysis methods and applications of them. A chapter will be devoted to optimizations of differential-linear cryptanalysis of ARX constructs, as well as its application to Chaskey. In the next chapter, I will present a complete attack against the main version of the Speedy block cipher, showing then how to use powerful techniques during differential cryptanalysis. Next, I will present a new cryptanalysis technique in symmetric cryptography: differential meet-in-the-middle cryptanalysis, which consists of combining differential elements with meet-in-the-middle elements. Finally I will present quantum version of impossible differential cryptanalysis: quantum differential cryptanalysis

La première partie de la thèse porte sur l'utilisation de la méthode des variances dans le cadre des attaques différentielles sur des schémas de Feistel généralisés. Cette méthode permet d'améliorer des attaques sur deux points : la complexité en données ou le nombre de tours couvert par l'attaque.Afin d'atteindre ce but, un outil a été développé permettant de calculer la valeur exacte de l'espérance et de la variance et nous nous servons alors de cette précision pour améliorer les attaques.La seconde partie porte sur une famille de schémas de chiffrement : les EGFN.Nous avons utilisé la méthode des variances et notre outil afin de construire des attaques différentielles. Des simulations ont été effectuées afin de confirmer les résultats.Dans la dernière partie, nous nous intéressons à LILLIPUT, un système de chiffrement concret issu des EGFN. Nous avons effectué une analyse différentielle et monté des attaques avec une structure spécifique.Ces attaques sont trouvées par un programme cherchant des attaques automatiquement. Nous avons notamment mis en avant la possibilité d'études sur les attaques différentielles improbables
The first part of the thesis is the cryptanalysis of generalized Feistel networks with the use of the variance method.This method allows to improve existing attacks by two ways: data complexity or the number of rounds. In order to do that, we have developed a tool which computes the right values of expectations and variances.It provides a better analysis of the attacks.In the second part, we have studied the EGFN a new family of generalized Feistel networks. We have used the variance method and our tool in order to build some differential attacks. Simulations were made to confirm the theoritical study.In the last part, we have studied LILLIPUT, a concret cipher based on the EGFN.We have provided a differential analysis and build differential attacks which have unusual conditions. These attacks were found empirically by a tool that automatically look for differential attacks. In particular, we have highlighted some improbable differential attacks

Les travaux exposés dans ce document portent essentiellement sur l'étude des cryptanalyses statistiques des chiffrements par blocs. Certains des résultats présentés sont cependant suffisamment généraux pour pouvoir être utilisés dans d'autres contextes comme les chiffrements à flot, les attaques par canaux cachés, ... Après avoir donné quelques notions de base nécessaires à la compréhension du document, l'on s'intéresse aux deux grandes familles de cryptanalyses statistiques : les cryptanalyses linéaires et cryptanalyses différentielles. Un état de l'art est effectué afin de pouvoir appréhender les différentes problématiques liées à ces cryptanalyses. Dans un second temps, le document présente les travaux effectués durant ces trois années de thèse. Ceux-ci portent en majorité sur l'analyse de la complexité en données et de la probabilité de succès des cryptanalyses statistiques. Est aussi présenté un algorithme de décodage des codes linéaires qui peut être utilisé pour retrouver la clef lors d'une cryptanalyse linéaire. Notons que deux attaques sont proposées sur des schémas de chiffrement reconnus. Une cryptanalyse linéaire multiple sur la totalité du DES et une cryptanalyse différentielle multiple sur 18 tours du chiffrement PRESENT. Ces deux attaques sont, à ce jour, les meilleures attaques connues de leur catégorie sur ces chiffrements. Enfin, un appendice contient tous les détails techniques et preuves calculatoires permettant d'obtenir les résultats importants de ce document.

Cette thèse présente une étude approfondie de la protection cryptographique des bases de données. Elle aborde tous les aspects de ce domaine : la législation l'encadrant, les produits commerciaux et " open-source " offrant ce type de service, et les travaux effectués par les communautés de cryptographie et de base de données. Cette étude se focalise notamment sur les systèmes d'information qui contiennent des données hautement sensibles. Dans ce contexte, nous avons étudié la sécurité de plusieurs propositions. En particulier, nous avons effectué une cryptanalyse de l'algorithme de chiffrement Fast Comparison Encryption (FCE) proposé par Ge et Zdonik en 2007, ainsi que d'une variante suggérée par les auteurs en réaction à notre première cryptanalyse. Ces deux attaques ont l'avantage d'être pratiques, c'est-à-dire qu'elles s'exécutent en temps raisonnable sur un PC standard. Ces travaux nous ont également conduit à proposer des façons sûres de protéger les bases de données en utilisant des algorithmes dont la sécurité a été éprouvée par la communauté cryptographique. Cela permet d'avoir des solutions robustes, à défaut d'être parfaites, pour protéger des données sensibles.

Cette thèse étudie l'effet des techniques algébriques sur certains cryptosystèmes post-quantiques. Nous donnons des attaques contre des schémas multivariés et à base de codes en métrique rang dont certains ont été proposés à la standardisation par le NIST. La plupart de ces travaux font intervenir le problème MinRank et des versions structurées. Nous avons introduit de nouvelles modélisations algébriques pour certaines de ces versions et contribué à l'analyse d'autres existantes, notamment la modélisation Support-Minors (Bardet et al., EUROCRYPT 2020). Notre cassage d'un schéma de chiffrement multivarié récent (Raviv et al. , PKC 2021) est aussi une attaque MinRank. Enfin, nous avons étudié d'autres systèmes polynomiaux non reliés à MinRank provenant de la cryptanalyse du Regular Syndrome Decoding (Augot et al. Mycrypt 2005) et de celle d'une primitive symétrique adaptée aux preuves zero-knowledge (Bouvier et al., CRYPTO 2023)
This thesis studies the effect of algebraic techniques on certain post-quantum cryptosystems. We give attacks on multivariate and code-based schemes in the rank metric, some of which have been proposed to standardization by NIST. Most of these works involve the MinRank problem or structured versions of it. We have devised new polynomial modelings for some of these versions and contributed to analysis of existing ones, in particular the Support-Minors modeling (Bardet et al., EUROCRYPT 2020). Our break of a recent multivariate encryption scheme (Raviv et al. , PKC 2021) is also a MinRank attack. Finally, we studied other algebraic systems no longer related to MinRank arising from the cryptanalysis of Regular Syndrome Decoding (Augot et al. Mycrypt 2005) and that of a symmetric primitive tailored to zero-knowledge proofs (Bouvier et al., CRYPTO 2023)

Dans cette thèse, nous étudions le domaine de la diffusion de données chiffrés avec traçage de traîtres et nous avons trois contributions. Tout d’abord, dans le contexte de traçage de traîtres, nous rappelons les trois modèles dans la litérature: modèle de traçage sans boîte-noire, modèle de traçage avec boîte-noire à une clé, et modèle de traçage boîte-noire générale. Le dernier modèle est évidemment le plus important car il couvre toutes les stratégies d’adversaires, mais les deux premiers modèles sont également utiles car il couvre de nombreux scénarios pratiques. Nous proposons un schéma optimal dans le modèle traçage sans boîte-noire et dans le modèle de traçage avec boîte-noire à une clé. Ensuite, nous étudions les deux nouveaux types d’attaques avancés (à savoir les pirates évolutifs et les Pirates 2. 0) qui ont été proposées pour souligner certaines faiblesses des schémas du paradigme de subset-cover, ou plus généralement les schémas combinatoires. Comme les schémas du paradigme de subset-cover ont été largement mis en oeuvre dans la pratique, il est nécessaire de trouver des contre-mesures pour résister à ces deux types d’attaque. Dans notre travail, nous construisons deux types de schémas qui sont relativement efficaces et qui résistent bien deux types d’attaque. Enfin, nous étudions un modèle généralisé de la diffusion de données chiffrés qui peut être appliquée dans la pratique comme dans les systèmes de télévision à péage. Dans ce contexte, le centre peut chiffrer plusieurs messages à plusieurs ensembles des utilisateurs légitimes “en même temps”. Nous appelons cette nouvelle primitive la diffusion de données chiffrés multi-chaîne. Nous arrivons à construire un schéma efficace avec les chiffrés de taille constante
In this thesis, we work on the domain of broadcast encryption and tracing traitors. Our contributions can be divided into three parts. We first recall the three tracing models: non-black-box tracing model, single-key black box tracing model, and general black box tracing model. While the last model is the strongest model, the two former models also cover many practical scenarios. We propose an optimal public key traitor tracing scheme in the two first models. We then consider two new advanced attacks (pirate evolution attack and Pirates 2. 0) which were proposed to point out some weaknesses of the schemes in the subset-cover framework, or more generally of combinatorial schemes. Since these schemes have been widely implemented in practice, it is necessary to find some counter-measures to these two types of attacks. In the second contribution, we build two schemes which are relatively efficient and which resist well these two types of attacks. In the last contribution, we study a generalized model for broadcast encryption which we call multi-channel broadcast encryption. In this context, the broadcastor can encrypt several messages to several target sets “at the same time”. This covers many scenarios in practice such as in pay-TV systems in which providers have to send various contents to different groups of users. We propose an efficient scheme with constant size ciphertext

Les attaques cryptographiques que nous décrivons dans cette thèse reposent sur des approches combinatoires, relevant notamment de la théorie des graphes et de la satisfaction sous contraintes. Notre objectif principal concerne l'étude du problème du logarithme discret sur courbes elliptiques. Dans un premier temps, nous nous concentrons sur l'attaque de calcul d'index pour le cas des courbes elliptiques définies sur des extensions de corps finis de degré premier. Au cœur de l'attaque sur ces courbes réside la résolution des systèmes polynomiaux en caractéristique 2. Ainsi, la première phase du calcul d'index, phase de recherche de relations, consiste à résoudre des systèmes d'équations obtenus à partir de polynômes de Semaev, dont les zéros représentent des coordonnées de points. La résolution de ces systèmes répond au problème de décomposition de points. Dans le cadre de cette attaque, premièrement, nous modélisons le problème de décomposition de points sous la forme d'une formule logique et nous le définissons comme une instance du problème SAT. En ajout de cela, nous développons un solveur SAT dédié à ce problème spécifique, nommé WDSat. Le solveur est muni d'une extension qui vise à éliminer les solutions symétriques des polynômes de Semaev sans agrandir le modèle SAT et sans introduire de coût de calcul supplémentaire. Les temps d'exécution expérimentaux montrent que notre approche de résolution utilisant WDSat est significativement plus rapide que les méthodes algébriques actuelles basées sur le calcul de bases de Gröbner. De plus, notre solveur a des meilleures performances que d’autres solveurs SAT couramment utilisés, pour ce problème spécifique. Au final, nous abordons le problème du logarithme discret sur courbes elliptiques dans le cas générique. Notamment, pour la mise en oeuvre de l'attaque de recherche de collisions en contexte parallèle de van Oorschot et Wiener, nous proposons une nouvelle structure de données, ayant des conséquences importantes sur la complexité en mémoire et en temps
In this thesis, we explore the use of combinatorial techniques, such as graph-based algorithms and constraint satisfaction, in cryptanalysis. Our main focus is on the elliptic curve discrete logarithm problem. First, we tackle this problem in the case of elliptic curves defined over prime-degree binary extension fields, using the index calculus attack. A crucial step of this attack is solving the point decomposition problem, which consists in finding zeros of Semaev’s summation polynomials and can be reduced to the problem of solving a multivariate Boolean polynomial system. To this end, we encode the point decomposition problem as a logical formula and define it as an instance of the SAT problem. Then, we propose an original XOR-reasoning SAT solver, named WDSat, dedicated to this specific problem. As Semaev’s polynomials are symmetric, we extend the WDSat solver by adding a novel symmetry breaking technique that, in contrast to other symmetry breaking techniques, is not applied to the modelization or the choice of a factor base, but to the solving process. Experimental running times show that our SAT-based solving approach is significantly faster than current algebraic methods based on Gröbner basis computation. In addition, our solver outperforms other state-of-the-art SAT solvers, for this specific problem. Finally, we study the elliptic curve discrete logarithm problem in the general case. More specifically, we propose a new data structure for the Parallel Collision Search attack proposed by van Oorschot and Wiener, which has significant consequences on the memory and time complexity of this algorithm

Les travaux de cette thèse portent sur les critères de sécurité des
algorithmes de chiffrement à clé secrète et ont été menés suivant deux
axes. Le premier concerne la sécurité des chiffrements symétriques
itératifs par blocs contre les attaques par distingueur sur le dernier
tour. Les résultats portent en particulier sur la généralisation d'une
attaque différentielle d'ordre supérieur menée sur l'algorithme
MISTY1. L'origine de cette attaque ainsi que de sa généralisation a pu
être expliquée grâce aux propriétés du spectre de Walsh des fonctions
de non-linéarité maximale utilisées. Ainsi il a été possible
d'élaborer une attaque générique sur tous les chiffrements de Feistel
à cinq tours utilisant des fonctions dont le spectre de Walsh est
divisible par une grande puissance de 2 car cette propriété permet
d'obtenir une borne supérieure sur le degré de la composition de
telles fonctions, nettement plus faible que la borne
triviale. Cette attaque suggère ainsi un nouveau critère de sécurité
qui porte sur la divisibilité du spectre de Walsh des fonctions de
tour utilisées dans les chiffrements itératifs par blocs. La deuxième
partie de la thèse porte sur l'étude des fonctions booléennes
symétriques, et en particulier sur l'existence éventuelle de
propriétés cryptographiques. À partir d'une propriété structurelle de
périodicité d'une représentation d'une fonction booléenne symétrique,
les propriétés de degré algébrique, d'équilibre, de résilience, de
critère de propagation et de non-linéarité ont été étudiées, ce qui a
permis d'améliorer les résultats existants. Par ailleurs, le calcul
explicite du spectre de Walsh des fonctions booléennes symétriques de
degré 2 et 3 a été réalisé, ainsi que la détermination de toutes les
fonctions symétriques équilibrées de degré inférieur ou égal à 7,
indépendamment du nombre de variables.

En 2008, l'Institut National des Standards et de la Technologie américain (NIST) a initié une compétition publique, nommée SHA-3, afin de sélectionner une nouvelle norme pour les fonctions de hachage. Nous étudions ici des propriétés algébriques de certaines des fonctions candidates à ce concours. Parmi les fonctions étudiées se trouve l'algorithme Keccak, qui est depuis peu la fonction qui a remporté la compétition et qui est devenue le nouveau standard SHA-3. Dans un premier temps nous avons étudié et analysé un nouveau type de distingueur introduit en 2009 et appelé distingueur par partition en sommes nulles. Nous l'avons appliqué sur plusieurs candidats du concours SHA-3. Nous nous sommes ensuite intéressés au degré algébrique des permutations itérées. Nous avons établi une première borne qui exploite la structure des fonctions non-linéaires usuellement employées dans les constructions de type SPN. Après, nous avons étudié le rôle de la permutation inverse dans les constructions itérées et nous avons prouvé une deuxième borne, plus générale, sur le degré. Nous présentons également une étude sur une nouvelle notion concernant les boîtes-S, qui exprime le fait que certaines composantes d'une boîte-S peuvent s'exprimer comme des fonctions affines sur un sous-espace bien choisi et sur tous ses translatés. L'analyse de ce type de propriétés a mené à l'amélioration d'une cryptanalyse de la fonction de hachage Hamsi. Enfin, nous avons étudié la résistance contre les attaques par canaux cachés de deux candidats au concours SHA-3 et nous avons proposé des contre-mesures au niveau logiciel.

Cette thèse est consacrée à l’étude de la sécurité physique des algorithmesde couplage. Les algorithmes de couplage sont depuis une quinzaine d’années utilisésà des fins cryptographiques. D’une part, les systèmes d’information évoluent, et denouveaux besoins de sécurité apparaissent. Les couplages permettent des protocolesinnovants, tels que le chiffrement basé sur l’identité, les attributs et l’échange tripartien un tour. D’autre part, l’implémentation des algorithmes de couplages est devenueefficace, elle permet ainsi d’intégrer des solutions cryptographiques à base de couplagedans les systèmes embarqués.La problématique de l’implémentation sécurisée des couplages dans les systèmesembarqués va être étudiée ici. En effet, l’implémentation d’algorithmes dédiés à lacryptographie sur les systèmes embarqués soulève une problématique : la sécurité del’implémentation des couplages face aux attaques physiques. Les attaques par canauxauxiliaires, dites passives, contre les algorithmes de couplages sont connues depuisbientôt une dizaine d’années. Nous proposons des études pour valider l’efficacité desattaques en pratique et avec des atouts théoriques. De notre connaissance, il y a uneseule attaque pratique dans la littérature, nous l’optimisons d’un facteur dix en termesde nombres de traces. Nous proposons aussi une attaque horizontale, qui nous permetd’attaquer le couplage twisted Ate en une seule trace.Par ailleurs, les contre-mesures n’ont été que peu étudiées. Nous complétons cettepartie manquante de la littérature. Nous proposons de nouveaux modèles d’attaquessur la contre-mesure de randomisation des coordonnées. L’attaque en collision proposéepermet ainsi de donner une réévaluation de la contre-mesure ciblée. Ainsi nousproposons la combinaison de contre-mesures qui, à moindres coûts, protégerait de cesattaques
This thesis focuses on the resistance of Pairing implementations againstside channel attacks. Pairings have been studied as a cryptographic tool for the pastfifteen years and have been of a growing interest lately. On one hand, Pairings allowthe implementation of innovative protocols such as identity based encryption, attributebased encryption or one round tripartite exchange to address the evolving needs ofinformation systems. On the other hand, the implementation of the pairings algorithmshave become more efficient, allowing their integration into embedded systems.Like for most cryptographic algorithms, side channel attack schemes have beenproposed against Pairing implementations. However most of the schemes describedin the literature so far have had very little validation in practice. In this thesis, westudy the practical feasibility of such attacks by proposing a technique for optimizingcorrelation power analysis on long precision numbers. We hence improve by a factorof 10 the number of side-channel leakage traces needed to recover a 256-bit secret keycompared to what is, to our best knowledge, one of the rare practical implementationsof side channel attacks published. We also propose a horizontal attack, which allow usto attack the twisted Ate pairing using a single trace.In the same way, countermeasures have been proposed to thwart side channel attacks,without any theoretical or practical validation of the efficiency of such countermeasures.We here focus on one of those countermeasures based on coordinatesrandomization and show how a collision attack can be implemented against this countermeasure.As a result, we describe how this countermeasure would have to be implementedto efficiently protect Pairing implementations against side channel attacks.The latter studies raise serious questions about the validation of countermeasures whenintegrated into complex cryptographic schemes like Pairings