La thèse traite de l’utilisation des systèmes hybrides dans le contexte particulier des communications sécurisées et de la cryptographie. Ce travail est motivé par les faits suivants. L’essor considérable des communications qui a marqué ces dernières décennies nécessite des besoins croissants en terme de sécurité des échanges et de protection de l’information. Dans ce contexte, la cryptographie joue un rôle central puisque les informations transitent la plupart du temps au travers de canaux publics. Parmi les nombreuses techniques de chiffrement existants, le chiffrement par flot se distingue tout particulièrement lorsqu’on le débit d’une communication sécurisée est privilégié. Les chiffreurs par flot sont construits à partir de générateurs de séquences complexes décrits par des systèmes dynamiques et devant être synchronisés de part et d’autre du canal d’échanges. Les objectifs et les résultats de ce travail se déclinent en trois points. Tout d’abord, l’intérêt d’utiliser des systèmes hybrides en tant que primitives cryptographiques est motivé. Par la suite, une étude comparative est menée afin d’établir une connexion entre les algorithmes de masquage de l’information basés sur le chaos et les algorithmes de chiffrement usuels. L’étude porte exclusivement sur des considérations structurelles et repose sur des concepts de la théorie du contrôle, en particulier l’inversibilité à gauche et la platitude. On montre que la technique de masquage dite par inclusion, qui consiste à injecter l’information à protéger dans une dynamique complexe, est la plus efficace. De plus, on montre que sous la condition de platitude, un système de masquage par inclusion est structurellement équivalent à un chiffreur par flot particulier appelé auto-synchronisant. Enfin, des méthodes de cryptanalyse pour évaluer la sécurité du masquage par inclusion sont proposées pour une classe particulières de systèmes hybrides à savoir les systèmes linéaires à commutations. A nouveau, des concepts de la théorie du contrôle sont utilisés, il s’agit de l’identifiabilité paramétrique et des algorithmes d’identification. Des spécificités relatives au contexte particulier de la cryptographie sont prises en compte. En effet, contrairement à la plupart des cas rencontrés dans le domaine du contrôle où les variables des modèles dynamiques sont continues car relatives à des systèmes physiques, les variables prennent ici des valeurs discrètes. Les modèles dynamiques sont en effet décrits non plus dans le corps des réels mais dans des corps finis en vue d’une implémentation sur des machines à états finis tels ordinateur ou tout autre dispositif numérique / This manuscript deals with a specific engineering application involving hybrid dynamical systems : secure communications and cryptography. The work is motivated by the following facts. The considerable progress in communication technology during the last decades has led to an increasing need for security in information exchanges. In this context, cryptography plays a major role as information is mostly conveyed through public networks. Among a wide variety of cryptographic techniques, stream ciphers are of special interest for high speed encryption. They are mainly based on generators of complex sequences in the form of dynamical systems, which must be synchronized at the transmitter and receiver sides. The aim of this work is threefold. First, the interest of resorting to hybrid dynamical systems for the design of cryptographic primitives is motivated. Secondly, a connection between chaotic and conventional cryptography is brought out by comparing the respective algorithms proposed in the open literature. The investigation focuses on structural consideration. Control theoretical concepts, in particular left invertibility and flatness, are the central tools to this end. It is shown that the so-called message-embedding technique, consisting in injecting the information to be concealed into a dynamical system, is the most relevant technique. Furthermore, it is shown that, under the flatness condition, the resulting cipher acts as a self-synchronizing stream cipher. Finally, cryptanalytic methodologies for assessing the security of the message-embedded cryptosystem involving a special class of hybrid systems, namely the switched linear systems, are proposed. Again concepts borrowed from control theory, namely identifiability and identification, are considered. Specificities related to the context are taken into account. The variables describing the dynamical systems do not take values in a continuum unlike what usually happens in automatic control when physical models are considered. They rather take values in finite cardinality sets, especially finite fields, since an implementation in finite state machines, say computers or digital electronic devices, is expected

La cryptographie à base de réseaux euclidiens est un domaine prometteur pour la construction de primitives cryptographiques post-quantiques. Un problème fondamental, lié aux réseaux, est le problème du plus court vecteur (ou SVP, pour Shortest Vector Problem). Ce problème est supposé être difficile à résoudre même avec un ordinateur quantique. Afin d’améliorer l’efficacité des protocoles cryptographiques, on peut utiliser des réseaux structurés, comme par exemple des réseaux idéaux ou des réseaux modules (qui sont une généralisation des réseaux idéaux). La sécurité de la plupart des schémas utilisant des réseaux structurés dépend de la difficulté du problème SVP dans des réseaux modules, mais un petit nombre de schémas peuvent également être impactés par SVP dans des réseaux idéaux. La principale construction pouvant être impactée par SVP dans des réseaux idéaux est la fonction multilinéaire GGH13. Cette fonction multilinéaire est principalement utilisée aujourd’hui pour construire des obfuscateurs de programmes, c’est-à-dire des fonctions qui prennent en entrée le code d’un programme et renvoie le code d’un programme équivalent (calculant la même fonction), mais qui doit cacher la façon dont le programme fonctionne.Dans cette thèse, nous nous intéressons dans un premier temps au problème SVP dans les réseaux idéaux et modules. Nous présentons un premier algorithme qui, après un pre-calcul exponentiel, permet de trouver des vecteurs courts dans des réseaux idéaux plus rapidement que le meilleur algorithme connu pour des réseaux arbitraires. Nous présentons ensuite un algorithme pour les réseaux modules de rang 2, également plus efficace que le meilleur algorithme connu pour des réseaux arbitraires, à condition d’avoir accès à un oracle résolvant le problème du plus proche vecteur dans un réseau fixé. Le pré-calcul exponentiel et l’oracle pour le problème du plus proche vecteurs rendent ces deux algorithmes inutilisables en pratique.Dans un second temps, nous nous intéressons à la fonction GGH13 ainsi qu’aux obfuscateurs qui l’utilisent. Nous étudions d’abord l’impact des attaques statistiques sur la fonction GGH13 et ses variantes. Nous nous intéressons ensuite à la sécurité des obfuscateurs utilisant la fonction GGH13 et proposons une attaque quantique contre plusieurs de ces obfuscateurs. Cette attaque quantique utilise entre autres un algorithme calculant un vecteur court dans un réseau idéal dépendant d’un paramètre secret de la fonction GGH13. / Lattice-based cryptography is a promising area for constructing cryptographic primitives that are plausibly secure even in the presence of quantum computers. A fundamental problem related to lattices is the shortest vector problem (or SVP), which asks to find a shortest non-zero vector in a lattice. This problem is believed to be intractable, even quantumly. Structured lattices, for example ideal lattices or module lattices (the latter being a generalization of the former), are often used to improve the efficiency of lattice-based primitives. The security of most of the schemes based on structured lattices is related to SVP in module lattices, and a very small number of schemes can also be impacted by SVP in ideal lattices.In this thesis, we first focus on the problem of finding short vectors in ideal and module lattices.We propose an algorithm which, after some exponential pre-computation, performs better on ideal lattices than the best known algorithm for arbitrary lattices. We also present an algorithm to find short vectors in rank 2 modules, provided that we have access to some oracle solving the closest vector problem in a fixed lattice. The exponential pre-processing time and the oracle call make these two algorithms unusable in practice.The main scheme whose security might be impacted by SVP in ideal lattices is the GGH13multilinear map. This protocol is mainly used today to construct program obfuscators, which should render the code of a program unintelligible, while preserving its functionality. In a second part of this thesis, we focus on the GGH13 map and its application to obfuscation. We first study the impact of statistical attacks on the GGH13 map and on its variants. We then study the security of obfuscators based on the GGH13 map and propose a quantum attack against multiple such obfuscators. This quantum attack uses as a subroutine an algorithm to find a short vector in an ideal lattice related to a secret element of the GGH13 map.

La thèse traite de l'utilisation des systèmes hybrides dans le contexte particulier des communications sécurisées et de la cryptographie. Ce travail est motivé par les faits suivants. L'essor considérable des communications qui a marqué ces dernières décennies nécessite des besoins croissants en terme de sécurité des échanges et de protection de l'information. Dans ce contexte, la cryptographie joue un rôle central puisque les informations transitent la plupart du temps au travers de canaux publics. Parmi les nombreuses techniques de chiffrement existants, le chiffrement par flot se distingue tout particulièrement lorsqu'on le débit d'une communication sécurisée est privilégié. Les chiffreurs par flot sont construits à partir de générateurs de séquences complexes décrits par des systèmes dynamiques et devant être synchronisés de part et d'autre du canal d'échanges. Les objectifs et les résultats de ce travail se déclinent en trois points. Tout d'abord, l'intérêt d'utiliser des systèmes hybrides en tant que primitives cryptographiques est motivé. Par la suite, une étude comparative est menée afin d'établir une connexion entre les algorithmes de masquage de l'information basés sur le chaos et les algorithmes de chiffrement usuels. L'étude porte exclusivement sur des considérations structurelles et repose sur des concepts de la théorie du contrôle, en particulier l'inversibilité à gauche et la platitude. On montre que la technique de masquage dite par inclusion, qui consiste à injecter l'information à protéger dans une dynamique complexe, est la plus efficace. De plus, on montre que sous la condition de platitude, un système de masquage par inclusion est structurellement équivalent à un chiffreur par flot particulier appelé auto-synchronisant. Enfin, des méthodes de cryptanalyse pour évaluer la sécurité du masquage par inclusion sont proposées pour une classe particulières de systèmes hybrides à savoir les systèmes linéaires à commutations. A nouveau, des concepts de la théorie du contrôle sont utilisés, il s'agit de l'identifiabilité paramétrique et des algorithmes d'identification. Des spécificités relatives au contexte particulier de la cryptographie sont prises en compte. En effet, contrairement à la plupart des cas rencontrés dans le domaine du contrôle où les variables des modèles dynamiques sont continues car relatives à des systèmes physiques, les variables prennent ici des valeurs discrètes. Les modèles dynamiques sont en effet décrits non plus dans le corps des réels mais dans des corps finis en vue d'une implémentation sur des machines à états finis tels ordinateur ou tout autre dispositif numérique.

La thèse traite de l'utilisation des systèmes hybrides dans le contexte particulier des communications sécurisées et de la cryptographie. Ce travail est motivé par les faits suivants. L'essor considérable des communications qui a marqué ces dernières décennies nécessite des besoins croissants en terme de sécurité des échanges et de protection de l'information. Dans ce contexte, la cryptographie joue un rôle central puisque les informations transitent la plupart du temps au travers de canaux publics. Parmi les nombreuses techniques de chiffrement existants, le chiffrement par flot se distingue tout particulièrement lorsqu'on le débit d'une communication sécurisée est privilégié. Les chiffreurs par flot sont construits à partir de générateurs de séquences complexes décrits par des systèmes dynamiques et devant être synchronisés de part et d'autre du canal d'échanges. Les objectifs et les résultats de ce travail se déclinent en trois points. Tout d'abord, l'intérêt d'utiliser des systèmes hybrides en tant que primitives cryptographiques est motivé. Par la suite, une étude comparative est menée afin d'établir une connexion entre les algorithmes de masquage de l'information basés sur le chaos et les algorithmes de chiffrement usuels. L'étude porte exclusivement sur des considérations structurelles et repose sur des concepts de la théorie du contrôle, en particulier l'inversibilité à gauche et la platitude. On montre que la technique de masquage dite par inclusion, qui consiste à injecter l'information à protéger dans une dynamique complexe, est la plus efficace. De plus, on montre que sous la condition de platitude, un système de masquage par inclusion est structurellement équivalent à un chiffreur par flot particulier appelé auto-synchronisant. Enfin, des méthodes de cryptanalyse pour évaluer la sécurité du masquage par inclusion sont proposées pour une classe particulières de systèmes hybrides à savoir les systèmes linéaires à commutations. A nouveau, des concepts de la théorie du contrôle sont utilisés, il s'agit de l'identifiabilité paramétrique et des algorithmes d'identification. Des spécificités relatives au contexte particulier de la cryptographie sont prises en compte. En effet, contrairement à la plupart des cas rencontrés dans le domaine du contrôle où les variables des modèles dynamiques sont continues car relatives à des systèmes physiques, les variables prennent ici des valeurs discrètes. Les modèles dynamiques sont en effet décrits non plus dans le corps des réels mais dans des corps finis en vue d'une implémentation sur des machines à états finis tels ordinateur ou tout autre dispositif numérique.

Dans ce mémoire nous étudions le domaine des fonctions de hachage, qui sont utilisées par de nombreux mécanismes cryptographiques. Les travaux présentés ici abordent à la fois la conception et l'analyse de la sécurité de ces fonctions. La première partie de ce mémoire est une introduction générale au domaine des fonctions de hachage. Nous décrivons la manière dont elles sont utilisées en la cryptographie et la manière de formaliser leur sécurité. Nous exposons également les principes de conception sur lesquels les fonctions de hachage les plus utilisées sont fondées. Enfin, nous évoquons la situation actuelle. La cryptanalyse différentielle a donné lieu à des attaques contre les principales fonctions de hachage. Le NIST organise actuellement une compétition de conception de fonctions de hachage (la compétition SHA-3), dans le but de définir une nouvelle norme de hachage. Dans la deuxième partie nous présentons nos travaux liés à la conception d'un candidat à cette compétition : Shabal. Nous commençons par décrire cette fonction, ainsi que les différentes évaluations de sa sécurité. En nous plaçant dans le modèle de l'indifférenciabilité d'un oracle aléatoire, nous montrons la sécurité du mode utilisé par Shabal lorsque la fonction de compression est idéalisée, puis la sécurité d'un mode plus classique lorsque cette fonction est affaiblie. Enfin, dans la troisième partie, nous abordons le domaine de la cryptanalyse de fonctions de hachage. Nous présentons la meilleure attaque connue contre RadioGatun, qui a été définie avant la compétition SHA-3 ainsi qu'une attaque contre Hamsi-256, une fonction sélectionnée pour le deuxième tour de la compétition SHA-3.

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.

Ma thèse porte sur l'étude des couplages, et plus particulièrement leur utilisation en cryptographie. Mes premiers travaux ont portés sur l'arithmétique des couplages à travers une comparaison des complexités en nombre d'opérations des couplages de Weil et Tate. Puis je me suis intéressée à l'étude de l'arithmétique utile pour les couplages. Un de mes travaux propose d'utiliser une représentation alternative des corps finis pour améliorer l'efficacité des calculs impliqués dans les couplages. Le second étudie en détail l'arithmétique des couplages pour les courbes dont le degré d'enfoncement est 15. Ces premiers travaux m'ont permis de me familiariser avec les couplages et je me suis alors orientée vers la résistance aux attaques par canaux cachés des algorithmes de couplage. J'ai étudié les faiblesses de l'algorithme de Miller lorsqu'il subit des attaques par analyse de consommation de courant et par injection de fautes.

La sécurité des transmissions et du stockage des données est devenue un enjeu majeur de ces dernières années et la cryptologie, qui traite de la protection algorithmique de l'information, est un sujet de recherche extrêmement actif. Elle englobe la conception d'algorithmes cryptographiques, appelée cryptographie, et l'analyse de leur sécurité, appelée cryptanalyse.Dans cette thèse, nous nous concentrons uniquement sur la cryptanalyse, et en particulier celle des algorithmes de chiffrement symétrique, qui reposent sur le partage d'un même secret entre l'entité qui chiffre l'information et celle qui la déchiffre. Dans ce manuscrit, trois attaques contre des algorithmes de chiffrement symétriques sont présentées. Les deux premières portent sur deux candidats de l'actuelle compétition cryptographique CAESAR, les algorithmes AEZ et NORX, tandis que la dernière porte sur l'algorithme Kravatte, une instance de la construction Farfalle qui utilise la permutation de la fonction de hachage décrite dans le standard SHA-3. Les trois algorithmes étudiés présentent une stratégie de conception similaire, qui consiste à intégrer dans une construction nouvelle une primitive, i.e. une fonction cryptographique élémentaire, déjà existante ou directement inspirée de travaux précédents.La compétition CAESAR, qui a débuté en 2015, a pour but de définir un portefeuille d'algorithmes recommandés pour le chiffrement authentifié. Les deux candidats étudiés, AEZ et NORX, sont deux algorithmes qui ont atteint le troisième tour de cette compétition. Les deux attaques présentées ici ont contribué à l'effort de cryptanalyse nécessaire dans une telle compétition. Cet effort n'a, en l'occurrence, pas permis d'établir une confiance suffisante pour justifier la présence des algorithmes AEZ et NORX parmi les finalistes.AEZ est une construction reposant sur la primitive AES, dont l'un des principaux objectifs est d'offrir une résistance optimale à des scénarios d'attaque plus permissifs que ceux généralement considérés pour les algorithmes de chiffrement authentifié. Nous montrons ici que dans de tels scénarios il est possible, avec une probabilité anormalement élevée, de retrouver l'ensemble des secrets utilisés dans l'algorithme.NORX est un algorithme de chiffrement authentifié qui repose sur une variante de la construction dite en éponge employée par exemple dans la fonction de hachage Keccak. Sa permutation interne est inspirée de celles utilisées dans BLAKE et ChaCha. Nous montrons qu'il est possible d'exploiter une propriété structurelle de cette permutation afin de récupérer la clé secrète utilisée. Pour cela, nous tirons parti du choix des concepteurs de réduire les marges de sécurité dans le dimensionnement de la construction en éponge.Enfin, la dernière cryptanalyse remet en cause la robustesse de l'algorithme Kravatte, une fonction pseudo-aléatoire qui autorise des entrées et sorties de taille variable. Dérivée de la permutation Keccak-p de SHA-3 au moyen de la construction Farfalle, Kravatte est efficace et parallélisable. Ici, nous exploitons le faible degré algébrique de la permutation interne pour mettre au jour trois attaques par recouvrement de clé : une attaque différentielle d'ordre supérieur, une attaque algébrique "par le milieu" et une attaque inspirée de la cryptanalyse de certains algorithmes de chiffrement à flot. / Nowadays, cryptology is heavily used to protect stored and transmitted data against malicious attacks, by means of security algorithms. Cryptology comprises cryptography, the design of these algorithms, and cryptanalysis, the analysis of their security.In this thesis, we focus on the cryptanalysis of symmetric encryption algorithms, that is cryptographic algorithms that rely on a secret value shared beforehand between two parties to ensure both encryption and decryption. We present three attacks against symmetric encryption algorithms. The first two cryptanalyses target two high profile candidates of the CAESAR cryptographic competition, the AEZ and NORX algorithms, while the last one targets the Kravatte algorithm, an instance of the Farfalle construction based on the Keccak permutation. Farfalle is multipurpose a pseudo-random function (PRF) developed by the same designers' team as the permutation Keccak used in the SHA-3 hash function.The CAESAR competition, that began in 2015, aims at selecting a portfolio of algorithms recommended for authenticated encryption. The two candidates analysed, AEZ and NORX, reached the third round of the CAESAR competition but were not selected to be part of the finalists. These two results contributed to the cryptanalysis effort required in such a competition. This effort did not establish enough confidence to justify that AEZ and NORX accede to the final round of the competition.AEZ is a construction based on the AES primitive, that aims at offering an optimal resistance against more permissive attack scenarios than those usually considered for authenticated encryption algorithms. We show here that one can recover all the secret material used in AEZ with an abnormal success probability.NORX is an authenticated encryption algorithm based on a variant of the so-called sponge construction used for instance in the SHA-3 hash function. The internal permutation is inspired from the one of BLAKE and ChaCha. We show that one can leverage a strong structural property of this permutation to recover the secret key, thanks to the designers' non-conservative choice of reducing the security margin in the sponge construction.Finally, the last cryptanalysis reconsiders the robustness of the Kravatte algorithm. Kravatte is an efficient and parallelizable PRF with input and output of variable length. In this analysis, we exploit the low algebraic degree of the permutation Keccak used in Kravatte to mount three key-recovery attacks targeting different parts of the construction: a higher order differential attack, an algebraic meet-in-the-middle attack and an attack based on a linear recurrence distinguisher.

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.

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.