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.

Nous nous sommes intéressé au problème de décodage des codes de Reed-Muller d'ordre r à travers différents types de canaux et dans différents contextes. Dans notre contexte, le mot du code Reed-Muller bruité est tous simplement une fonction booléenne. Une question naturelle avant de faire du décodage, est de savoir s'il existe ou non au moins un mots de ce code de Reed-Muller d'ordre r qui est à une distance d donnée de notre mot bruité. Ainsi on a développé dans cette thèse de tels testeurs en caractéristique 2. Dans le but d'obtenir des attaques cryptographiques, on a développé des algorithmes adaptatifs de décodage des codes de Reed-Muller d'ordre 1 et 2 en très grande longueur. Une partie application importante est consacrée à l'étude des propriétés statistiques du DES. Enfin une digression est faite sur la construction des courbes modulaires.

La sécurité des chiffrements par bloc évolue constamment au fur et à mesure que de nouvelles techniques de cryptanalyse sont découvertes. Lors de la conception de nouveaux chiffrements par bloc, il est donc nécessaire de considérer ces nouvelles techniques dans l'analyse de sécurité. Dans cette thèse, nous montrons comment construire certaines opérations internes des chiffrements par bloc pour améliorer la résistance à certaines attaques. Nous commençons par donner une méthode pour trouver les permutations paires-impaires optimales selon un certain critère pour les Réseaux de Feistel Généralisés. Grâce à une nouvelle caractérisation et à un algorithme efficace, nous sommes notamment capables de résoudre un problème ouvert depuis 10 ans. Nous donnons ensuite de nouvelles techniques de cryptanalyse pour améliorer la division property, qui nous permet également de donner un nouveau critère optimal pour la conception de boîtes-S. Nous continuons avec de nouvelles observations pour un cadencement de clé alternatif pour AES. Ceci nous permet de donner un nouveau cadencement de clé, à la fois plus efficace et augmentant la sécurité face à certaines attaques par rapport à l’original. Pour finir, nous présentons un algorithme général très effiace permettant d’attaquer la majorité des propositions pour la cryptographie en boîte blanche, ainsi qu’une attaque dédiée sur un schéma non attaqué jusque là, donnant lieu à une attaque qui n’a besoin que de quelques secondes pour retrouver la clé. / Along with new cryptanalysis techniques, the security of block ciphers is always evolving. When designing new block ciphers, we thus need to consider these new techniques during the security analysis. In this thesis, we show how to build some core operations for block ciphers to improve the security against some attacks. We first start by describing a method to find optimal (according to some criterion) even-odd permutations for a Generalized Feistel Network. Using a new characterization and an efficient algorithm, we are able to solve a 10-years old problem. We then give new cryptanalysis techniques to improve the division property, along with a new proven optimal criterion for designing S-boxes. We continue with new observations for the design of an alternative key-schedule for AES. We thus give a new key-schedule, which is both more efficient and more secure against some attacks compared to the original one. Finally, we describe a very efficient generic algorithm to break most proposals in white-box cryptography, as well as a dedicated attack on a previously not analyzed scheme, leading to a key-recovery attack in a few seconds.

Cette thèse porte sur les problèmes algorithmiques qui apparaissent lorsque l'on souhaite mettre en œuvre un cryptosystème basé sur un code correcteur d'erreur ou bien une cryptanalyse d'un tel système. L'intérêt de ces système provient de leur excellente complexité algorithmique, meilleure de plusieurs ordres de grandeurs en termes de complexité que les schémas à clé publique traditionnels. Ils fournissent également une alternative crédible aux systèmes actuels qui pour la plupart se repose sur la théorie des nombres et sur le problème de la factorisation et celui du logarithme discret. Outre l'absence de preuve mathématique de la réelle difficulté de ces problèmes, P. Shor a montré que ces deux problèmes pouvaient être résolus en temps polynomial dans le modèle de l’ordinateur quantique. Cet ordinateur quantique est encore loin d'être fonctionnel mais il faudra, le jour venu, disposer d'alternatives de confiance et disposant de mises en œuvre performantes. / This thesis is about algorithmic problems arising when someone wants to implement a cryptosystem based on error correcting codes or a cryptanalysis of such a system. The benefits of these systems come from their excellent algorithmic complexity, better of several orders than the classical public key schemes. They also bring a credible alternative to the current systems that for most of them rely on number theory and on the problems of factorisation and discrete logarithm. P.Shor showed that these two problems could be solved in polynomial time in the quantum computer model. This computer is far from being operational but we will need alternatives we can trust and that have efficient implementations.

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'évolution des architectures de systèmes d'information n'a de cesse depuis l'avènement des télécommunications. Pour s'adapter aux nouvelles dimensions en nombre d'utilisateurs et taille des données, les systèmes d'information modernes sont répartis et hétérogènes. Ce constat ouvre de nouveaux enjeux de sûreté de fonctionnement pour les systèmes d'information, il s'agit de garantir disponibilité, fiabilité, innocuité, confidentialité, intégrité et maintenabilité tout au long du cycle de vie du système. C'est dans ce contexte que cette thèse a été conduite, les fruits des travaux de recherche gravitent autour de plusieurs notions de la sûreté de fonctionnement : – La confidentialité et l'intégrité avec le design, l'implémentation et l'étude de robustesse des chiffres symétriques par bloc. Les chiffres DES, AES et CS-Cipher ont été étudiés dans un spectre large rassemblant les implémentations logicielles et matérielles et leurs performances, la maléabilité des structures de diffusion, la cryptographie conventionnelle et les attaques par canaux auxiliaires. – La fiabilité avec le développement d'algorithmes auto-tolérants aux fautes et la certification de résultats. Cette étude est dédiée aux systèmes distribués de calcul tels que les clusters, les grilles ou encore les réseaux pair-à-pairs utilisés pour des calculs d'algèbre linéaires.

Une fonction de hachage est une fonction prenant comme argument un élément de taille arbitraire finie et renvoyant un élément de longueur fixée. Il existe différents types de fonctions de hachage qui correspondent à autant de domaines d'utilisation. Parmi ces fonctions, les fonctions de hachage cryptographiques se distinguent par la variété des missions qui leur sont confiées et par l'exigence qui leur est faîte de respecter de nombreux impératifs de sécurité. Les fonctions de hachage cryptographiques les plus utilisées en pratiques appartiennent à la famille MD-SHA, dont les membres les plus connus sont les fonctions MD5 et SHA-1. Durant ces dernières années, de nouvelles techniques de crytptanalyses ont fait leur apparition. Ces techniques, bien que très complexes, se sont montrés si efficaces qu'elles ont conduit à l'abandon de l'utilisation des fonctions MD5 et SHA-1, et à l'ouverture d'une compétition internationale pour le développement d'un nouvel algorithme de hachage cryptographique. Les travaux de recherche que nous avons menés dans le cadre de cette thèse s'inscrivent à la fois dans une démarche d'analyse et de conception. Nous étudions les nouvelles avancées dans la cryptanalyse des fonctions de hachage, et plus particulièrement leurs mise en oeuvre dans le cadre des fonctions SHA-0 et SHA-1. Nous présentons à ce titre la meilleure attaque pratique connue à ce jour contre SHA-0 et proposons la première classification des vecteurs de perturbations utilisés par les attaques par collision contre la fonction SHA-1. Nous abordons ensuite la conception de nouvelle fonctions par le biais des fonction XOR-Hash et FSB.

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.

La cryptologie est une des disciplines des mathématiques, elle est composée de deux sous-ensembles: la cryptographie et la cryptanalyse. Tandis que la cryptographie s'intéresse aux algorithmes permettant de modifier une information afin de la rendre inintelligible sans la connaissance d'un secret, la seconde s'intéresse aux méthodes mathématiques permettant de recouvrer l'information originale à partir de la seule connaissance de l'élément chiffré.La cryptographie se subdivise elle-même en deux sous-ensembles: la cryptographie symétrique et la cryptographie asymétrique. La première utilise une clef identique pour les opérations de chiffrement et de déchiffrement, tandis que la deuxième utilise une clef pour le chiffrement et une autre clef, différente de la précédente, pour le déchiffrement. Enfin, la cryptographie symétrique travaille soit sur des blocs d'information soit sur des flux continus d'information. Ce sont les algorithmes de chiffrement par blocs qui nous intéressent ici.L'objectif de la cryptanalyse est de retrouver l'information initiale sans connaissance de la clef de chiffrement et ceci dans un temps plus court que l'attaque par force brute. Il existe de nombreuses méthodes de cryptanalyse comme la cryptanalyse fréquentielle, la cryptanalyse différentielle, la cryptanalyse intégrale, la cryptanalyse linéaire...Beaucoup de ces méthodes sont maintenues en échec par les algorithmes de chiffrement modernes. En effet, dans un jeu de la lance et du bouclier, les cryptographes développent des algorithmes de chiffrement de plus en plus efficaces pour protéger l'information chiffrée d'une attaque par cryptanalyse. C'est le cas notamment de l'Advanced Encryption Standard (AES). Cet algorithme de chiffrement par blocs a été conçu par Joan Daemen et Vincent Rijmen et transformé en standard par le National Institute of Standards and Technology (NIST) en 2001. Afin de contrer les méthodes de cryptanalyse usuelles les concepteurs de l'AES lui ont donné une forte structure algébrique.Ce choix élimine brillamment toute possibilité d'attaque statistique, cependant, de récents travaux tendent à montrer, que ce qui est censé faire la robustesse de l'AES, pourrait se révéler être son point faible. En effet, selon ces études, cryptanalyser l'AES se ``résume'' à résoudre un système d'équations quadratiques symbolisant la structure du chiffrement de l'AES. Malheureusement, la taille du système d'équations obtenu et le manque d'algorithmes de résolution efficaces font qu'il est impossible, à l'heure actuelle, de résoudre de tels systèmes dans un temps raisonnable.L'enjeu de cette thèse est, à partir de la structure algébrique de l'AES, de décrire son algorithme de chiffrement et de déchiffrement sous la forme d'un nouveau système d'équations booléennes. Puis, en s'appuyant sur une représentation spécifique de ces équations, d'en réaliser une analyse combinatoire afin d'y détecter d'éventuels biais statistiques. / Cryptology is one of the mathematical fields, it is composed of two subsets: cryptography and cryptanalysis. While cryptography focuses on algorithms to modify an information by making it unintelligible without knowledge of a secret, the second focuses on mathematical methods to recover the original information from the only knowledge of the encrypted element.Cryptography itself is subdivided into two subsets: symmetric cryptography and asymmetric cryptography. The first uses the same key for encryption and decryption operations, while the second uses one key for encryption and another key, different from the previous one, for decryption. Finally, symmetric cryptography is working either on blocks of information either on continuous flow of information. These are algorithms block cipher that interests us here.The aim of cryptanalysis is to recover the original information without knowing the encryption key and this, into a shorter time than the brute-force attack. There are many methods of cryptanalysis as frequency cryptanalysis, differential cryptanalysis, integral cryptanalysis, linear cryptanalysis...Many of these methods are defeated by modern encryption algorithms. Indeed, in a game of spear and shield, cryptographers develop encryption algorithms more efficient to protect the encrypted information from an attack by cryptanalysis. This is the case of the Advanced Encryption Standard (AES). This block cipher algorithm was designed by Joan Daemen and Vincent Rijmen and transformed into standard by the National Institute of Standards and Technology (NIST) in 2001. To counter the usual methods of cryptanalysis of AES designers have given it a strong algebraic structure.This choice eliminates brilliantly any possibility of statistical attack, however, recent work suggests that what is supposed to be the strength of the AES, could prove to be his weak point. According to these studies, the AES cryptanalysis comes down to ``solve'' a quadratic equations symbolizing the structure of the AES encryption. Unfortunately, the size of the system of equations obtained and the lack of efficient resolution algorithms make it impossible, at this time, to solve such systems in a reasonable time.The challenge of this thesis is, from the algebraic structure of the AES, to describe its encryption and decryption processes in the form of a new Boolean equations system. Then, based on a specific representation of these equations, to achieve a combinatorial analysis to detect potential statistical biases.