Avec l'utilisation de notre carte bancaire pour payer un achat sur Internet ou de notre téléphone portable pour nous connecter aux réseaux sociaux, les transactions électroniques font partie de notre quotidien et sont désormais incontournables. Malheureusement, lors de tels échanges, un grand nombre de données personnelles sont transférées et une telle informatisation n'est pas sans conséquence. Les problèmes de sécurisation et de protection de ces données sont bien présents. Dans cette thèse, nous nous concentrons sur la problématique de la protection de la vie privée des utilisateurs dans des systèmes informatiques. Pour cela, nous nous intéressons à trois domaines d'actualité. Dans un premier temps, nous proposons un système de gestion des données centré sur l'utilisateur. Ainsi, lors de sa navigation sur Internet, l'internaute sera guidé et aura la possibilité de faire appel aux huit fonctionnalités offertes par l'application. Un second problème, sur lequel nous avons travaillé, est le cas des dossiers médicaux des patients et de l'accès à ces documents confidentiels. Nous proposons une architecture de e-santé permettant la protection des informations personnelles des patients au sein d'un établissement de santé et entre plusieurs établissements. Pour finir, nous avons travaillé dans le domaine de la monétique et plus précisément sur le paiement en ligne. Nous exposons ainsi trois nouveaux protocoles respectant davantage les données personnelles des internautes. Deux d'entre eux sont une amélioration de protocoles existants : 3D-Secure et le protocole d'Ashrafi et Ng. La dernière architecture, totalement nouvelle, permet de procéder à un paiement sur Internet sans fournir aucune information bancaire du client. Pour chacune de ces infrastructures, des exigences de sécurité et de protection de la vie privée sont décrites. Les solutions existantes, ainsi que celles proposées, sont détaillées et analysées en fonction de ces exigences. Les propositions d'architectures respectueuses de la vie privée ont toutes fait l'objet d'une preuve de concept avec une implémentation logicielle.

Au début des années 90, l'apparition de nouvelles méthodes de cryptanalyse a bouleversé la sécurité des dispositifs cryptographiques. Ces attaques se basent sur l'analyse de consommation en courant lorsque le microprocesseur d'une carte est en train de dérouler l'algorithme cryptographique. Dans cette thèse nous explorons, principalement, les attaques template, et y apportons quelques améliorations pratiques notamment par l'utilisation de différentes techniques de traitement du signal. Nous commençons par étudier l'efficacité de ces attaques sur des mises en oeuvre matérielles non protégées, et explorons au fur et à mesure quelque modèles de fuite d'information. Après cela, nous examinons la pertinence du cadre théorique sur les attaques par profilage présenté par F.-X. Standaert et al. à Eurocrypt 2009. Ces analyses consistent en des études de cas basées sur des mesures de courant acquises expérimentalement à partir d'un accélérateur cryptographique. À l'égard de précédentes analyses formelles effectuées sur des mesures par " simulations ", les investigations que nous décrivons sont plus complexes, en raison des différentes architectures et de la grande quantité de bruit algorithmique. Dans ce contexte, nous explorons la pertinence des différents choix pour les variables sensibles, et montrons qu'un attaquant conscient des transferts survenus pendant les opérations cryptographiques peut sélectionner les distingueurs les plus adéquats, et augmenter ainsi son taux de succès. Pour réduire la quantité de données, et représenter les modèles en deux dimensions, nous utilisons l'analyse en composantes principales (ACP) et donnons une interprétation physique des valeurs propres et vecteurs propres. Nous introduisons une méthode basée sur le seuillage de la fuite de données pour accélérer le profilage ainsi que l'attaque. Cette méthode permet de renforcer un attaquant qui peut avec un minimum de traces, améliorer 5 fois sa vitesse dans la phase en ligne de l'attaque. Aussi, il a été souligné que les différents modèles utilisés, ainsi que les échantillons recueillis durant la même acquisition peuvent transporter des informations complémentaires. Dans ce contexte, nous avons eu l'occasion d'étudier comment combiner au mieux différentes attaques en se basant sur différentes fuites. Cela nous a permis d'apporter des réponses concrètes au problème de la combinaison des attaques. Nous nous sommes concentrés également sur l'identification des problèmes qui surgissent quand il y a une divergence entre les templates et les traces attaquées. En effet, nous montrons que deux phénomènes peuvent entraver la réussite des attaques lorsque les templates sont obsolètes, à savoir, la désynchronisation des traces, et le redimensionnement des traces en amplitudes. Nous suggérons deux remèdes pour contourner ce type de problèmes : le réajustement des signaux et la normalisation des campagnes d'acquisitions. Finalement, nous proposons quelques méthodes du traitement du signal dans le contexte des attaques physiques. Nous montrons que lorsque les analyses sont effectuées en multi-résolution, il y a un gain considérable en nombre de traces nécessaires pour récupérer la clé secrète, par rapport à une attaque ordinaire.

Les travaux réalisés au cours de cette thèse se situent au carrefour de la cryptographie symétrique et du monde des environnements contraints. Le but de cette cryptographie, dite cryptographie à bas coût, est de fournir et d'évaluer des algorithmes symétriques pouvant être implémentés sur des systèmes très limités en ressources. Les contributions de cette thèse portent d'une part sur l'évaluation de la sécurité des registres à décalage à rétroaction avec retenue (FCSR) face à de nouvelles attaques et d'autre part sur une vision unifiée des différents schémas de Feistel généralisés (GFN) qui permet de mieux cerner leurs propriétés cryptographiques. Ces études ont donné lieu à deux nouveaux algorithmes à bas coût~; d'une part GLUON une fonction de hachage à base de FCSR et d'autre part le chiffrement LILLIPUT basé sur une famille étendant plus avant la notion de GFN. Enfin, une méthode générique permettant de réaliser des attaques différentielles en fautes sur des GFN est esquissée. / The work done during this Ph.D. lies at the crossroads of symmetric cryptography and constraints environments. The goal of such cryptography, called lightweight cryptography, is to propose and evaluate symmetric algorithms that can be implemented on very ressource limited devices. The contributions of this thesis are first on the security evaluations of feedback with carry shift registers (FCSR) to some new attacks and second on a unified vision of generalized Feistel networks (GFNs) that allows to better understand their cryptographic properties. These studies gave rise to two new lightweight algorithms: first GLUON a hash function based upon FCSRs and second the cipher LILLIPUT based on a family further extanding the notion of generalized Feistel network. Finally, a generic method for carrying out a differential fault attack on GFNs is outlined.

La cryptographie à base de codes correcteurs, introduite par Robert McEliece en 1978, est un candidat potentiel au remplacement des primitives asymétriques vulnérables à l'émergence d'un ordinateur quantique. Elle possède de plus une sécurité classique éprouvée depuis plus de trente ans, et permet des fonctions de chiffrement très rapides. Son défaut majeur réside dans la taille des clefs publiques. Pour cette raison, plusieurs variantes du schéma de McEliece pour lesquelles les clefs sont plus aisées à stocker ont été proposées ces dernières années. Dans cette thèse, nous nous intéressons aux variantes utilisant soit des codes alternants avec symétrie, soit des codes de Goppa sauvages. Nous étudions leur résistance aux attaques algébriques et exhibons des faiblesses parfois fatales. Dans chaque cas, nous révélons l'existence de structures algébriques cachées qui nous permettent de décrire la clef secrète par un système non-linéaire d'équations en un nombre de variables très inférieur aux modélisations antérieures. Sa résolution par base de Gröbner nous permet de trouver la clef secrète pour de nombreuses instances hors de portée jusqu'à présent et proposés pour un usage à des fins cryptographiques. Dans le cas des codes alternants avec symétrie, nous montrons une vulnérabilité plus fondamentale du processus de réduction de taille de la clef.Pour un déploiement à l'échelle industrielle de la cryptographie à base de codes correcteurs, il est nécessaire d'en évaluer la résistance aux attaques physiques, qui visent le matériel exécutant les primitives. Nous décrivons dans cette optique un algorithme de déchiffrement McEliece plus résistant que l'état de l'art. / Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art.Code-based cryptography, introduced by Robert McEliece in 1978, is a potential candidate to replace the asymetric primitives which are threatened by quantum computers. More generral, it has been considered secure for more than thirty years, and allow very vast encryption primitives. Its major drawback lies in the size of the public keys. For this reason, several variants of the original McEliece scheme with keys easier to store were proposed in the last years.In this thesis, we are interested in variants using alternant codes with symmetries and wild Goppa codes. We study their resistance to algebraic attacks, and reveal sometimes fatal weaknesses. In each case, we show the existence of hidden algebraic structures allowing to describe the secret key with non-linear systems of multivariate equations containing fewer variables then in the previous modellings. Their resolutions with Gröbner bases allow to find the secret keys for numerous instances out of reach until now and proposed for cryptographic purposes. For the alternant codes with symmetries, we show a more fondamental vulnerability of the key size reduction process. Prior to an industrial deployment, it is necessary to evaluate the resistance to physical attacks, which target device executing a primitive. To this purpose, we describe a decryption algorithm of McEliece more resistant than the state-of-the-art.

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.

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.

La cryptographie basée sur le logarithme discret a connu de nombreuses avancées dans les dix dernières années, notamment avec l'utilisation de tores algébriques introduite par Lenstra et Verheul. Ici on axe notre travail sur la facette constructive de ces idées et se penche sur le paramétrage de ces structures. Van Dijk et Woodruff ont récemment proposé une solution pour représenter de manière compacte une famille de points d'un tore algébrique. Afin d'améliorer la complexité asymptotique de cet algorithme, on a recours à plusieurs outils. D'une part on utilise un nouveau type de bases pour les extensions de corps finis, les bases normales elliptiques dues à Couveignes et Lercier. Par ailleurs, les tailles des objets manipulés font intervenir des polynômes cyclotomiques et leurs inverses modulaires. L'amplitude de leurs coefficients intervient directement dans l'étude de complexité. Dans le cas où leurs indices sont des diviseurs d'un produit de deux nombres premiers, on parvient à des bornes voire des expressions explicites pour ces coefficients, qui permettent de conclure quant à l'amélioration du coût de communication dans des protocoles cryptographiques comme une négociation de clefs multiples de Diffie-Hellman.

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 aborde le problème de la reconstruction des composants d'un système de transmission à partir de l'interception d'une communication bruitée. Les deux grandes parties de ce travail s'intéressent successivement aux deux maillons principaux de la chaîne~: le brasseur et le code correcteur d'erreur, dans l'ordre où ils doivent être traités par l'attaquant, c'est-à-dire dans l'ordre inverse de leur apparition dans la chaîne de transmission.<br /><br />La première partie traite donc du problème de la reconstruction d'un code linéaire binaire à partir de la connaissance de mots de code bruités. Dans un premier temps, nous présentons et analysons une méthode suggérée par A. Valembois dans sa thèse. Cette analyse nous amène à présenter un nouveau test statistique permettant de trouver des mots susceptibles d'appartenir au dual du code utilisé lors de la transmission. Puis nous présentons un nouvel algorithme de décodage fondé sur les techniques classiques de décodage<br />itératif. Cet algorithme nous permet de corriger des erreurs même si certaines des équations de parité trouvées par le test statistique ne sont pas valides. Nous décrivons alors un nouvel algorithme de reconstruction utilisant cet algorithme de décodage.<br /><br />La seconde partie traite du problème de la reconstruction d'un brasseur linéaire. Dans un premier temps, nous supposons que l'attaquant dispose de la sortie exacte du brasseur. Nous présentons alors différentes techniques permettant de reconstruire un brasseur synchrone ou auto-synchronisant en fonction des hypothèses envisagées sur l'entrée du brasseur. Ensuite, nous nous intéressons au cas général et nous présentons alors une technique algébrique permettant de reconstruire un brasseur synchrone quand<br />l'attaquant connaît simplement l'image de sa sortie par une transformation linéaire par bloc et une partie de la suite en entrée.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.